DAO2: Overcoming Overall Storage Overflow in Intermittently Connected Sensor Networks
Bin Tang · 2018
Many emerging sensor network applications operate in challenging environments wherein sensor nodes do not always have connected paths to the base station. Data generated from such intermittently connected sensor networks therefore must be stored inside the network for some unpredictable period of time before uploading opportunities become available. Consequently, sensory data could overflow limited storage capacity available in the entire network, making discarding valuable data inevitable. To overcome such overall storage overflow in intermittently connected sensor networks, we propose and study a new algorithmic problem called data aggregation for overall storage overflow (DA02). Utilizing spatial data correlation that commonly exists among sensory data, DAO2employs data aggregation techniques to reduce the overflow data size while minimizing the total energy consumption. To solve DAO2, we uncover a new graph theoretic problem called multiple traveling salesman walks (MTSW), and show that with proper graph transformation, the DAO2is equivalent to the MTSW. We prove that MTSW is NP-hard and design a (2-1.)-approximation q algorithm, where q is the number of nodes to visit (i.e., the number of sensor nodes that aggregate their overflow data). The approximation algorithm is based on a novel routing structure called minimum q-edge forest that accurately captures information needed for energy-efficient data aggregation. We further put forward a heuristic algorithm and empirically show that it constantly outperforms the approximation algorithm by 15% -30% in energy consumption. Finally, we propose a distributed data aggregation algorithm that can achieve the same approximation ratio as the centralized algorithm under some condition, while incurring comparable energy consumption.