Data Collection Latency in Wireless Sensor Networks with Multiple Mobile Elements
Liang He, Jianping Pan and Jingdong Xu
The introduction of mobile elements has created a new dimension to reduce and balance the energy consumption of sensor nodes in wireless sensor networks. However, the data collection latency may become higher due to the relatively low travel speed of the mobile elements. The scheduling of the mobile elements, i.e., how they traverse through the sensing field and when they collect data from which sensor, is of ultimate importance and has attracted increasing attention from the research community. The scenario where a single mobile element is available to conduct the data collection can be formulated as the Traveling Salesman Problem with Neighborhoods (TSPN), but due to its NP-hardness, so far only approximation and heuristic algorithms have appeared in the literature, and the former only have theoretical value due to their large approximation factors. In this paper, following a progressive optimization approach, we propose a combine-skip substitute (CSS) scheme to design the data collection path when only one single mobile element is available, which is shown to outperform the state-of-the-art heuristic algorithm. In addition, an extension of the CSS scheme where multiple mobile elements are available to collect data collaboratively is presented to address the scalability bottleneck if only one mobile element is employed. The performance of the proposed schemes, along with their correctness and complexity analysis, is verified through extensive simulation.
Keywords: Wireless sensor networks, mobile elements, data collection latency, tour selection, TSPN, k-TSP