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
This content will become publicly available on October 19, 2024
Truthful and Optimal Data Preservation in Base Station-less Sensor Networks: An Integrated Game Theory and Network Flow Approach
We aim to preserve a large amount of data generated inside
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- Award ID(s):
- 2131309
- NSF-PAR ID:
- 10471710
- Publisher / Repository:
- ACM Digital Library
- Date Published:
- Journal Name:
- ACM Transactions on Sensor Networks
- Volume:
- 20
- Issue:
- 1
- ISSN:
- 1550-4859
- Page Range / eLocation ID:
- 1 to 40
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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
-
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
-
more » « less
Abstract Recently, benefiting from rapid development of energy harvesting technologies, the research trend of wireless sensor networks has shifted from the battery‐powered network to the one that can harvest energy from ambient environments. In such networks, a proper use of harvested energy poses plenty of challenges caused by numerous influence factors and complex application environments. Although numerous works have been based on the energy status of sensor nodes, no work refers to the issue of minimizing the overall data transmission cost by adjusting transmission power of nodes in energy‐harvesting wireless sensor networks. In this paper, we consider the optimization problem of deriving the energy‐neutral minimum cost paths between the source nodes and the sink node. By introducing the concept of energy‐neutral operation, we first propose a polynomial‐time optimal algorithm for finding the optimal path from a single source to the sink by adjusting the transmission powers. Based on the work earlier, another polynomial‐time algorithm is further proposed for finding the approximated optimal paths from multiple sources to the sink node. Also, we analyze the network capacity and present a near‐optimal algorithm based on the Ford–Fulkerson algorithm for approaching the maximum flow in the given network. We have validated our algorithms by various numerical results in terms of path capacity, least energy of nodes, energy ratio, and path cost. Simulation results show that the proposed algorithms achieve significant performance enhancements over existing schemes. Copyright © 2016 John Wiley & Sons, Ltd.
