Minimizing the Number of Mobile Chargers to Keep Large-Scale WRSNs Working Perpetually

Abstract

Wireless Rechargeable Sensor Networks, in which mobile chargers ([Formula: see text]s) are employed to recharge the sensor nodes, have attracted wide attention in recent years. Under proper charging schedules, the [Formula: see text]s could keep all the sensor nodes working perpetually. Since [Formula: see text]s can be very expensive, this paper tackles the problem of deciding the minimum number of [Formula: see text]s and their charging schedules to keep every sensor node working continuously. This problem is NP-hard; we divide it into two subproblems and propose a GCHA ( Greedily Construct, Heuristically Assign) scheme to solve them. First, the GCHA greedily addresses a Tour Construction Problem to construct a set of tours to 1-cover the WRSN. Energy of the sensor nodes in each of these tours can be timely replenished by one [Formula: see text] according to the decision condition derived from a Greedy Charging Scheme (GCS). Second, the GCHA heuristically solves a Tour Assignment Problem to assign these tours to minimum number of [Formula: see text]s. Then each of the [Formula: see text]s can apply the GCS to charge along its assigned tours. Simulation results show that, on average, the number of [Formula: see text]s obtained by the GCHA scheme is less than 1.1 over a derived lower bound and less than 0.5 over related work.