Spatio-Temporal Optimization for Charging Scheduling in Wireless Rechargeable Sensor Networks

Wireless Rechargeable Sensor Networks (WRSNs) have been widely utilized and have played an important role in many surveillance application scenarios. The optimization of the charging process is beneficial for guaranteeing continuous coverage and enhancing the charging efficiency of WRSNs. And there are several influence factors of the charging process, like the sensors' battery consumption mode, the chargers' charging pattern and the environmental factors, which should be considered into the charging model. Based on the charging model via assigning sensors' charging priority weights, we introduce the spatio-temporal optimization for charging scheduling (STO-CS) Problem in WRSNs for the goals of meeting the on-demand charging requirements and saving the charging consumption. We prove the NP-hardness of the problem and propose two algorithms to solve it. The first algorithm is based on two-phase dynamic programming and is proved to find the optimal solution when the charging ability is sufficient; the second algorithm adopts the clustering idea with K-Means Algorithm which has better time complexity. A series of simulation experiments are performed to compare the performance of the proposed algorithms in terms of the charging cost and the running time, whose results are analyzed to conclude that they can be applied to the application scenarios with the accuracy requirements and the real-time requirements respectively.