Approximation algorithms for vehicle-aided periodic data collection from mobile sensors with obstacle avoidance in WSNs

Data collection from the sensors in time is an integral part of many applications of wireless sensor networks (WSNs). Vehicles, referred to as Mobile Sinks (SNKs), may be used to collect data from the sensors by visiting them. Since the sensors have limited memory, the sensed data needs to be collected by the SNKs within a predefined time interval to avoid memory overflow. Periodic data collection by SNKs becomes even more challenging when the sensors are mobile. Moreover, the presence of obstacles in the area makes the path planning for SNKs even more complicated. In this paper, an optimization problem, referred to as Minimum Mobile Sink Aided Periodic Data Collection (MinSnkDC) problem, is formulated, where the objective is to determine the minimum number of SNKs that collect data for every time period from the mobile sensors in the WSN, while avoiding collision with the obstacles in the area. The problem is proved to be NP-complete. Two constant factor approximation algorithms, namely MinSnkDC and Modified MinSnkDC (M-MinSnkDC), are proposed to solve the problem. From the simulation results, it is evident that M-MinSnkDC can produce a better solution compared to the existing obstacle-aware SNK-based data collection algorithms, while using a small number of SNKs.