Path Planning for Time-Constrained Data Gathering in Wireless Sensor Networks Using Mobile Nodes

Abstract: We consider the problem of gathering data from a sensor network using mobile elements. The goal is to plan the paths for the mobile elements that minimize the total length travelled. We propose an algorithmic solution that builds node disjoint tours that always include the sink, cover the network, and optimize the total length travelled. We provide an integer linear programming formulation for the problem, and propose two novel heuristics for building the tours. We evaluate the performance of our algorithm by comparing it to the optimal solution as well as to an alternative heuristic, commonly used in related time-window vehicle routing problems, and demonstrate the superior performance of our approach.

Keywords: Wireless sensor network (WSN), WIMAX technology, novel heuristics, Wireless Distribution System (WDS).