Finding Good Mobile Sink Information Collection Paths with Quicker Search Time: A Single-Particle Multi-dimensional Search Algorithm-Based Approach

Energy consumption is the first-class constraint for the battery-powered Internet of Things (IoT) devices and sensors. By moving around a sensor network to gather data, a mobile sink (MS) can greatly save sensor energy for multi-hop communication. To unlock the potential of mobile sinks, we need to carefully plan the path a mobile sink moves within the network for collecting information without compromising its coverage and its battery life. This paper presents a new way to find the optimal information collection path for mobile sinks. We achieve this by formulating the optimization problem as a classical Traveling Salesman Problem with Neighborhoods (TSPN). We then design a novel solver based on the particle multi-dimensional search algorithm to quickly locate a good path schedule in the TSPN optimization space. As a significant departure from prior work which uses multiple particles to explore multiple potential solutions, our method uses only one particle for problem-solving. Doing so significantly reduces the complexity of the algorithm, allowing it to scale to a larger sensor network. To ensure the quality of the chosen solution, we have carefully designed the evolutionary process for problem-solving. We show that our approach finds a solution with similar quality as those given by a multi-particle-based search, but with significantly less time. Simulation results show that our approach can find a high-quality path schedule compared to the state-of-the-art algorithm in a large sensor network.