Data gathering tour optimization for Dubins' vehicles
Douglas Guimarães Macharet, Armando Alves Neto, Vilar F. da Camara Neto, Mário F. M. Campos · 2012
A Wireless Sensor Network consists of several sensor nodes deployed in an environment having as primary goal to collect data. However, due to limited sensor communication range, oftentimes it is necessary to use a mobile node that will visit other nodes to gather up their collected data. This work addresses the problem of planning efficient paths for data collection by a mobile node modeled as a nonholonomic vehicle with curvature constraints. We propose an efficient algorithm to identify areas of intersection among the nodes RF footprints which will guide the identification of a smaller set of waypoints through which the vehicle needs to traverse in order to collect available data. Then, a metric similar to the classical Traveling Salesman Problem is used to determine the best circuit that includes all these collecting points. In order to reduce the total path length for the mobile node, a meta-heuristic is used. The classical Dubins' path technique is employed to generate a feasible tour for the vehicle and a new heuristic is used to generate the required orientation at the collecting points. The methodology was validated in a simulated environment. Our methodology outperforms the classical Alternating Algorithm and the best performing state-of-the-art algorithm.