Perpetual Sensor Networks with the Minimum Number of Mobile Chargers <Abstract> Wireless charging is a promising solution to resolving the energy constraint of wireless sensor networks. In a wireless rechargeable sensor network, mobile chargers (MCs) move around the network and charge the sensor nodes. This study focuses on the optimal deployment of MCs to perpetually maintain network operations. More specifically, we aim to determine the minimum number of MCs and their charging schedule to guarantee the perpetual lifetime of sensor nodes. To this end, we first mathematically formulate the targeted problem. We then propose a dynamic programming-based algorithm to determine the minimum number of MCs. Since the complexity of the dynamic programming-based algorithm is exponential, we introduce a lightweight algorithm based on local search.We conduct experiments to prove the effectiveness of the proposed algorithm compared to other alternatives. The experimental results show that our algorithm can reduce the number of sensors by at least 23.8% on average and 68% in the best case compared to the existing algorithms. In addition, we also perform theoretical analysis to derive the computational complexity of the proposed algorithm. |