An Efficient Scheduling Algorithm for Data Collection through Multi-path Routing Structures in Wireless Sensor Networks

Multi-path routing is essential in wireless sensor data collection to overcome the high loss rates in wireless environments. In this paper, we propose an efficient scheduling algorithm for data collection through multi-path routing structures in wireless sensor networks. The message complexity of our proposed scheduling algorithm is O(n(Δ + 3)), where n is the number of sensor nodes in the network and Δ is the maximum node degree. The best existing scheduling algorithm for single-path routing structures has the message complexity of O(n(χ + Δ + 2)), where χ is the number of 2-hop neighbors of a sensor node. The complexity of the proposed scheduling algorithm is a significant improvement since χ is normally on the order of O(Δ²). In addition, we also develop a method for deriving a (super) lower bound on the shortest possible length of the data collection schedule generated by any algorithm. Extensive experimental results show that the proposed scheduling algorithm produces good data collection schedules with greatly reduced running time and fewer messages generated as compared to existing algorithms. The length of the data collection schedule produced by our algorithm is within 2.3 times of the lower bound estimate across a wide range of network settings.