Minimum Latency Multiple Data MULE Trajectory Planning in Wireless Sensor Networks

Abstract

This paper investigates the problem of computing the optimal trajectories of multiple data MULEs (e.g., robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks. By relying on a slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood ( k-TSPN) and the k-rooted path cover problem with neighborhood ( k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them along with two simpler heuristic algorithms. We also conduct simulations to compare the performance of the proposed approaches with the existing alternatives. Our simulation results indicate that the proposed algorithms outperform the competitors on average.