On delay-minimized data harvesting with mobile elements in wireless sensor networks

We consider the problem of routing and scheduling a set of mobile elements that act as mechanical carriers of data, harvesting them from sensor nodes and delivering them to a sink. The objective is to minimize the data delivery latency. Most of the existing work has focused on designing delay minimizing routes for the mobile nodes by leveraging variants of the Traveling Salesman Problem (TSP). We show that TSP-based routes can lead to delay that is arbitrarily worse than the optimal. The main insight is that as data generation rates of sensors may vary, some sensors need to be visited more frequently than others. To that end, we consider a network with a single sink and develop a path splitter algorithm that “splits” a TSP-based route into several loops intersecting at the sink. Numerical results show that our algorithm can improve average delay by more than 40% in some instances while requiring a modest computational effort to modify the TSP-based route. The work is useful in prolonging sensor network lifetime and in relaying data in partitioned networks.