On Time-Constrained Data Harvesting in Wireless Sensor Networks: Approximation Algorithm Design

摘要

In wireless sensor networks, data harvesting using mobile data ferries has recently emerged as a promising alternative to the traditional multi-hop communication paradigm. The use of data ferries can significantly reduce energy consumption at sensor nodes and increase network lifetime. However, it usually incurs long data delivery latency as the data ferry needs to travel through the network to collect data, during which some delay-sensitive data may become obsolete. Therefore, it is important to optimize the trajectory of the data ferry with data delivery latency bound for this approach to be effective in practice. To address this problem, we formally define the time-constrained data harvesting problem, which seeks an optimal data harvesting path in a network to collect as much data as possible within a time duration. We then investigate the formulated data harvesting problem in the generic m-dimensional context, of which the cases of m=1, 2, 3 are particularly pertinent. We first characterize the performance bound given by the optimal data harvesting algorithm and show that the optimal algorithm significantly outperforms the random algorithm, especially when network scales. However, we mathematically prove that finding the optimal data harvesting path is NP-hard. We therefore devise an approximation algorithm and mathematically prove the output being a constant-factor approximation of the optimal solution. Our experimental results also demonstrate that our approximation algorithm significantly outperforms the random algorithm in a wide range of network settings.