Path planning of a data mule in wireless sensor network using an improved implementation of clustering-based genetic algorithm

摘要

In recent years, use of mobile robot acting as a data mule for collecting data in the wireless sensor network has become an important issue. This data collection problem of generating a path as short as possible for a data mule to gather all data from all of sensor nodes is known as a NP-hard problem named Traveling Salesman Problem with Neighborhoods (TSPN). We proposed a clustering-based genetic algorithm (CBGA) capable of further shortening the TSPN route provided by clustering with demonstrated effectiveness and reduced computational complexity. In this paper, we seek effective implementation of CBGA by extensive simulations. An improved clustering-based genetic algorithm is proposed, which consists of a waypoint selection method and a GA with an appropriate combination of modified sequential constructive crossover (MSCX) operator and a mutation operator based on local optimization heuristics of 2-opt developed for TSP. Extensive simulations are performed to illustrate the effectiveness and improved performance of CBGA with a more effective GA implementation composed of a combination of MSCX crossover operator and 2-opt for path planning of a data mule.