Scheduling Wireless Charging Tasks With Precedence Constraints

The development and improvement of Wireless Power Transfer(WPT)has greatly expanded the application of Wireless Rechargeable Sensor Network(WRSN),such as environmental monitoring,mobile communication,medical care,transportation and logistics applications.Flexibility of operation,durability of product and user-friendliness are some advantages of WRSN,which overcome the defects of traditional wired charging,and receive extensive attention from the academia and industry field of wireless sensor network.In a sensor network,sensors are mainly responsible for tasks of data collection,data processing and data communication.These tasks usually have a specific order of execution.Most of the existing related works mainly focus on researching and optimizing the charging model and network performance,but ignore the precedence constraints among tasks.In view of this case,considering that the Mobile Charger(MC)in WRSN has limited battery capacity,and the charging tasks submitted by sensors have a deadline requirement,in this paper,we are the first to research the problem of Scheduling wireless Charging tasks with Precedence Constraints(SCPC),and we formulate the SCPC problem with the optimization objective of minimizing the total completion time of all the charging tasks under precedence constraints while guaranteeing that the energy capacity of mobile charger is not exhausted,and the deadlines of charging tasks are not expired.The main contributions of this paper are as follows:(1)For the problem that the topological sequence of task scheduling in wireless rechargeable sensor network is not unique,a priority-based topological Sort algorithm(TS-P)is proposed in order to derive a unique feasible sequence on directed acyclic graph(DAG)and further obtain the unique linear sequence of task scheduling.(2)For the problem that the planning for mobile chargers in wireless rechargeable sensor networks is NP-hard,a topological sort based genetic algorithm(TS-GA)is proposed.We apply the result of TS-P scheme to the execution process of the genetic algorithm with the intention of obtaining the final optimal solution of the whole algorithm through the sequential operation of a series of genetic operators.(3)For the proposed problem is with multiple constraints,a original adaptive evaluation function is proposed.We formalize a fitness objective function with a penalty factor term to constrain the length of time for the completion of the charging tasks and the excess consumed energy of the mobile charger,so as to solve the SCPC problem with multiple constraints and then to obtain the global optimal solution of the whole algorithm.(4)The basic theoretical model utilized for solving problem is constructed,and meanwhile,we devise three comparison algorithms and conduct extensive simulation experiments to verify the correctness,effectiveness and efficiency of our proposed algorithm under the condition of three different network sizes,and moreover,the influence of different experimental parameter settings on the performance of the algorithm is also evaluated.The simulation results show that our proposed algorithm in this paper outperforms the other three comparison algorithms by up to 37.2% in terms of completion time.