An Approximation Algorithm for Path Planning of Vehicles for Data Collection in Wireless Rechargeable Sensor Networks

Abstract

Wireless rechargeable sensor networks (WRSNs) have been extensively used in various event detection and environmental monitoring applications, where it is important to collect environmental data from the sensors. Data may be collected at the base station (BS) through multi-hop communication. But it may cause sensors located near the BS to run out of their energy quickly. In a WRSN, data may also be collected using mobile vehicles that visit different sensors to collect data. However, in a large scale WRSN, travelling to all the sensors for data collection may cause vehicles to run out of their energy in the middle of their journey. In this paper, we formulate an optimization problem that minimizes the average travel distance of the vehicles while collecting data from maximum number of sensors. The problem is proved to be NP-complete. To avoid visiting all the sensors, our scheme selects a subset of sensors as anchor nodes that first collects data from neighboring sensors through one-hop transfer. Then, the anchor nodes are divided among the vehicles. Finally, a convex-hull based 3-approximation algorithm is proposed that finds the travel plan for each vehicle through the anchor nodes only, where the vehicle starts from the BS, collects data from the anchor nodes, while returning back to the BS at the end of its journey. Simulation results show that our scheme outperforms the existing schemes in terms of the average travel distance by vehicles, while collecting data from a large number of sensors. � 2023 ACM.