skip to main content

Explore Research Products in the NSF-PAR

This content will become publicly available on September 25, 2024

Title: On the Performance of Nash Equilibria for Data Preservation in Base Station-less Sensor Networks
Base station-less sensor networks (BSNs) refer to emerging sensing applications deployed in challenging environments (e.g., underwater exploration). As installing a base station in such an environment is not feasible, data generated in the BSN will be preserved in the network before being collected by the uploading opportunities. This process is called data preservation in the BSN. Considering that sensor nodes are intelligent and selfish, this paper studies the Nash Equilibrium (NE) for data preservation in BSNs. We design a suite of data preservation algorithms, examine whether they achieve NEs, and rigorously analyze the performance of the NEs using existing (i.e., price of anarchy and price of stability) and our own designed metrics (i.e., rate of efficiency loss). We find that a minimum cost flow-based algorithm produces a NE that achieves the social optimal with minimum energy consumption in the data preservation process. We show the NE from one of our straightforwardly designed greedy algorithms achieves a price of anarchy of 3. On the other hand, we prove that a greedy algorithm always exists (although non-straightforward), achieving the socially optimal NE. Finally, we conduct extensive simulations to investigate the performances of various data preservation NEs and validate our theoretical results under different network parameters.  more » « less
Award ID(s):
2131309
NSF-PAR ID:
10483602
Author(s) / Creator(s):
; ;
Publisher / Repository:
IEEE
Date Published:
Journal Name:
the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2023)
Page Range / eLocation ID:
252 to 260
Format(s):
Medium: X
Location:
Toronto, ON, Canada
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ( , ACM Transactions on Sensor Networks)

    We aim to preserve a large amount of data generated insidebase station-less sensor networks(BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration); as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP:datapreservationproblem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design a minimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit.

    In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of the failure of the DPG-1. It is due to the packet dropping by the selfish nodes that manipulate the AMD technique. We then design a data preservation game DPG-2 for DPP that traces and punishes manipulative nodes in the BSN. We show that DPG-2 delivers dominant strategies for truth-telling nodes and achieves provably optimal data preservation with cheat-proof guarantees. Via extensive simulations under different network parameters and dynamics, we show that our games achieve system-wide data preservation solutions with optimal energy cost while enforcing truth-telling of sensor nodes about their private cost types. One salient feature of our work is its integrated game theory and network flows approach. With the observation of flow level sensor node behaviors provided by the network flows, our proposed games can synthesize “microscopic” (i.e., selfish and local) behaviors of sensor nodes and yield targeted “macroscopic” (i.e., optimal and global) network performance of data preservation in the BSN.

     
    more » « less
  2. ; ; ( , 3rd International Workshop on Time-Sensitive and Deterministic Networking (TENSOR), IFIP Networking 2023.)
    We design a data preservation game called Data-VCG for base station-less sensor networks ( BSNs ). In the BSN, sensor nodes do not have connected paths to a base station thus, sensory data must be preserved inside the network before uploading opportunities arise. Data-VCG incorporates data values into the classic Vickrey-Clark-Groves (VCG) mechanism, a generic truthful mechanism for achieving a socially-optimal solution. It motivates all the sensor nodes (i.e., source, storage, and transition) to voluntarily participate in the data preservation process while achieving minimum data preservation cost. We give a detailed analysis of the performance guarantee of the Data-VCG and show that under certain conditions, its worst-case budget imbalance is at most n−3 times the efficiency gain, where n is the number of sensor nodes in the network. We conduct extensive simulations to validate our results in both grids and randomly generated BSNs under different network dynamics. 
    more » « less
  3. ; ; ( , 2020 IEEE 17th International Conference on Mobile Ad Hoc and Sensor Systems (MASS))
    null (Ed.)
    We focus on sensor networks that are deployed in challenging environments, wherein sensors do not always have connected paths to a base station, and propose a new data resilience problem. We refer to it as DRE2: data resiliency in extreme environments. As there are no connected paths between sensors and the base station, the goal of DRE2 is to maximize data resilience by preserving the overflow data inside the network for maximum amount of time, considering that sensor nodes have limited storage capacity and unreplenishable battery power. We propose a quadratic programming-based algorithm to solve DRE2 optimally. As quadratic programming is NP-hard thus not scalable, we design two time efficient heuristics based on different network metrics. We show via extensive experiments that all algorithms can achieve high data resilience, while a minimum cost flow-based is most energy-efficient. Our algorithms tolerate node failures and network partitions caused by energy depletion of sensor nodes. Underlying our algorithms are flow networks that generalize the edge capacity constraint well-accepted in traditional network flow theory. 
    more » « less
  4. ; ; ( , IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2020))
    null (Ed.)
    We focus on sensor networks that are deployed in challenging environments, wherein sensors do not always have connected paths to a base station, and propose a new data resilience problem. We refer to it as DRE2: data resiliency in extreme environments. As there are no connected paths between sensors and the base station, the goal of DRE2 is to maximize data resilience by preserving the overflow data inside the network for maximum amount of time, considering that sensor nodes have limited storage capacity and unreplenishable battery power. We propose a quadratic programming-based algorithm to solve DRE2 optimally. As quadratic programming is NP-hard thus not scalable, we design two time efficient heuristics based on different network metrics. We show via extensive experiments that all algorithms can achieve high data resilience, while a minimum cost flow-based is most energy-efficient. Our algorithms tolerate node failures and network partitions caused by energy depletion of sensor nodes. Underlying our algorithms are flow networks that generalize the edge capacity constraint well-accepted in traditional network flow theory. 
    more » « less
  5. ; ; ( , 12th EAI International Conference on Game Theory for Networks (GameNets 2022).)
    We consider the problem of preserving a large amount of data generated inside base station-less sensor networks, when sensor nodes are controlled by different authorities and behave selfishly. We modify the VCG mechanism to guarantee that each node, including the source nodes with overflow data packets, will voluntarily participate in data preservation. The mechanism ensures that each node truthfully reports its private type and network achieves efficiency for all the preserved data packets. Extensive simulations are conducted to further validate our results. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email