Energy-efficient data gathering with tour length-constrained mobile elements in wireless sensor networks

Several studies in recent years have considered the use of mobile elements for data gathering in wireless sensor networks, so as to reduce the need for multi-hop forwarding among the sensor nodes and thereby prolong the network lifetime. Since, typically, practical constraints preclude a mobile element from visiting all nodes in the sensor network, the solution must involve a combination of a mobile element visiting a subset of the nodes (cache points), while other nodes communicate their data to the cache points wirelessly. This leads to the optimization problem of minimizing the communication distance of the sensor nodes, while keeping the tour length of the mobile element below a given constraint. Several algorithms in existing literature have tackled this problem by separating the construction of the mobile element tour from the computation of the forwarding trees to the cache points. In this paper, we propose a new algorithm that alternates between these phases and iteratively improves the outcome of each phase, based on the result of the other. We compare the resulting performance of our algorithm with that of previous work, and show that it closes a considerable portion of the gap from the theoretical optimal solution.