skip to main content


Title: DRE 2 : Achieving Data Resilience in Wireless Sensor Networks: A Quadratic Programming Approach
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
Award ID(s):
1911191
NSF-PAR ID:
10297107
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
2020 IEEE 17th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)
Page Range / eLocation ID:
71 to 79
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. 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
  2. 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
  3. 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.

     
    more » « less
  4. Many emerging sensor network applications operate in challenging environments wherein the base station is unavailable. Data generated from such intermittently connected sensor networks (ICSNs) must be stored inside the network for some unpredictable time before uploading opportunities become available. Consequently, sensory data could overflow the limited storage capacity available in the entire network, making discarding valuable data inevitable. To overcome such overall storage overflow in ICSNs, we propose and study a new algorithmic framework called data aggregation for overall storage overflow ( DAO2 ). Utilizing spatial data correlation that commonly exists among sensory data, DAO2 employs data aggregation techniques to reduce the overflow data size while minimizing the total energy consumption in data aggregation. At the core of our framework are two new graph theoretical problems that have not been studied. We refer to them as traveling salesmen placement problem ( TSP2 ) and quota traveling salesmen placement problem (Q- TSP2 ). Different from the well-known multiple traveling salesman problem (mTSP) and its variants, which mainly focus on the routing of multiple salesmen initially located at fixed locations, TSP2 and Q- TSP2 must decide the placement as well as the routing of the traveling salesmen. We prove that both problems are NP-hard and design approximation, heuristic, and distributed algorithms. Our algorithms outperform the state-of-the-art data aggregation work with base stations by up to 71.8% in energy consumption. 
    more » « less
  5. 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