Tags:Genetic algorithm, Precedence constraints, Wireless Power Transfer and Wireless Rechargeable Sensor Networks
Abstract:
The development of Wireless Power Transfer (WPT) facilitates wireless rechargeable sensor networks (WRSNs) receiving considerable attention in the sensor network research community. Most existing works mainly focus on general charging patterns and metrics while overlooking the precedence constraints among tasks, resulting in charging inefficiency. In this paper, we are the first to advance the issue of Scheduling wireless Charging tasks with precedence Constraints (SCPC) with the optimization objective of minimizing the completion time of all the charging tasks under precedence constraints while guaranteeing that the energy capacity of mobile charger (MC) is not exhausted, and the deadlines of charging tasks are not exceeded. In order to address the problem, we first propose the so-called priority-based topological sort scheme to derive an unique feasible sequence on directed acyclic graph (DAG). Then, we combine the proposed priority-based topological sort scheme with the procedure of genetic algorithm to obtain the optimal solution through a series of genetic operators. Finally, we conduct extensive simulations to validate our proposed algorithm under the condition of three different network sizes. The results show that our proposed algorithm outperforms the other two comparison lgorithms by up to 35.5% in terms of completion time.
Scheduling of Mobile Charging Tasks with Precedence Constraints