Abstract:
Charging scheduling optimization for low-duty-cycle sensor networks is an important and challenging issue. To this end, a novel paid charging service model is proposed, and based on this model, the problem of minimizing charging cost for low-duty-cycle sensor networks is studied. That is, how to find a charging schedule decision that satisfies the charging needs of all sensor devices in low duty cycle sensor networks within a limited charging scheduling period constraint, in order to achieve a trade-off optimization between charging service fee and the quality of network service. Firstly, the interference degree of network service quality and the charging cost under the low-duty-cycle working mode are formalized, the target problem is modeled and its NP-hardness is proved. Then, the target problem is transformed into an equivalent minimum cost submodular coverage problem by constructing a non-negative and monotonically non-decreasing submodular function. Furthermore, an efficient polynomial-time greedy algorithm is designed, and the approximation ratio performance of the proposed algorithm is analyzed. Finally, through extensive simulation experiments, the proposed algorithm is compared with three other baselines from multiple dimensions such as changes in the number of sensor devices, the number of charging stations, battery capacity, charging scheduling period, per-time-slot charging service fee, charging power, and various model parameters. The experimental results show that the proposed algorithm reduces charging cost by at least an average of 14.6%, 12.4% and 17.1% respectively, verifying the superior performance of the proposed algorithm.