Robot routing using clustering-based parallel genetic algorithm with migration

Abstract

Wireless sensor network (WSN) technology is widely used in environment monitoring, health care, surveillance systems and unmanned space or planet exploration. This paper focuses on routing problems with data gathering by a mobile robot in a WSN, also referred to as a Traveling Salesman Problem with Neighborhoods (TSPN) or NP-hard problem. In this paper, we propose a clustering-based parallel genetic algorithm with migration (CBPGA), so that the mobile robot can gather all data from all sensors and the travel costs of the mobile robot clearly decrease. First, a clustering algorithm is used to effectively reduce the number of visited nodes, especially in situations with dense sensor distributions or large sensing radii. Next, the set of visited nodes is encoded as chromosomes by a chromosome generation algorithm (CGA), and the master-slave parallel genetic algorithm with migration is performed to more efficiently generate the near-optimal route. Lastly, a travel cost-reduction scheme is used to remove redundant travel costs. Simulation results confirm that the clustering-based parallel genetic algorithm with migration more efficiently generates a near-optimal route that reduces the travel costs of a mobile robot in robot routing problems with WSN.