An Approximation Algorithm for Minimizing the Number of Distance Constrained Mobile Sinks for Data Collection from Static and Mobile Sensors

In this paper, we study a data collection problem that uses mobile sinks (MoSs) to collect data from the static and mobile sensors in a wireless sensor network (WSN) and subsequently deliver their data to the base station (BS). Since the battery capacity of an MoS is limited, the total distance travelled by the MoS is considered to be no longer than a given maximum length L. In this paper, we formulate an optimization problem whose objective is to minimize the number of MoSs and determine their data collection tours, which avoid any collision with obstacles in the area, subject to the constraint that the total distance travelled by an MoS is no greater than L. An approximation algorithm has been proposed to solve the problem, and the theoretical analysis of the algorithm has been provided. We evaluate the performance of the algorithm through simulations by comparing with existing obstacle-aware MoS-based data collection algorithms. The results reveal that our algorithm not only execute faster than the existing algorithms but also yield a lower number of MoSs.