Lifetime-Aware Data Collection Using a Mobile Sink in WSNs with Unreachable Regions

Using mobile sinks to collect sensed data in WSNs (Wireless Sensor Network) is an effective technique for significantly improving the network lifetime. We investigate the problem of collecting sensed data using a mobile sink in a WSN with unreachable regions such that the network lifetime is maximized and the total tour length is minimized, and propose a polynomial-time heuristic, an ILP-based (Integer Linear Programming) heuristic and an MINLP-based (Mixed-Integer Non-Linear Programming) algorithm for constructing a shortest path routing forest for the sensor nodes in unreachable regions, two energy-efficient heuristics for partitioning the sensor nodes in reachable regions into disjoint clusters, and an efficient approach to convert the tour construction problem into a TSP (Travelling Salesman Problem). We have performed extensive simulations on 100 instances with 100, 150, 200, 250 and 300 sensor nodes in an urban area and a forest area. The simulation results show that the average lifetime of all the network instances achieved by the polynomial-time heuristic is 74% of that achieved by the ILP-based heuristic and 65% of that obtained by the MINLP-based algorithm, and our tour construction heuristic significantly outperforms the state-of-the-art tour construction heuristic EMPS.