Research On Multi-UAV Scheduling For Energy Replenishment And Data Collection In Wireless Rechargeable Sensor Networks

Recently,Wireless Rechargeable Sensor Networks(WRSNs)have been rapidly developed because of their ability to provide convenient and efficient services.However,energy-limited sensors greatly reduce their ability for continuous monitoring,and in the scenario of data analysis,whether monitoring data is collected in time also affects the timeliness of WRSN.Therefore,it is necessary to study a service model that combines energy replenishment and data collection.For large-scale complicated scenarios such as rugged mountains,disaster areas and battlefields,Unmanned Aerial Vehicles(UAVs)are more suitable for energy replenishment and data collection than traditional wireless chargers due to their flexibility.Therefore,this thesis investigates the problem of using multiUAV with limited energy and quantity to assist in both energy replenishment and data collection in scenarios of target-sparse and target-intensive large-scale WRSNs.In target-sparse large-scale WRSNs,the density of targets is relatively low.This thesis formalizes the problem of multi-UAV-assisted energy replenishment and data collection,and proves that the problem studied is NP-Hard.The original problem is divided into three-stage subproblems to solve.Firstly,all sensors are divided into disjoint clusters according to different targets,and the Disjoint Clusters Construction(DCC)problem is solved by the Cooperative Clustering Game Algorithm(CCGA),which can converge to a stable coalition structure.Secondly,according to the concept of target k-coverage,the constrained Prim algorithm with polynomial time complexity is used to solve the Charging Sensors Selection(CSS)problem.Finally,to solve the UAV Trajectory Scheduling(UTS)problem,the nodes obtained from the previous two subproblems are used to schedule UAVs for energy replenishment and data collection.A 4-approximation algorithm based on a given edge weight threshold of the UTS problem is proposed to find all UAVs’ flight trajectories.We evaluate the performance of the proposed algorithms via extensive experiments,and the results show that this scheme can effectively accomplish both two tasks.Also,the average number of UAVs deployed by the proposed algorithms is at least 19.62% less than those of existing algorithms.In target-intensive large-scale WRSNs,the distance between the targets is relatively close and a set of UAV depots is given for recovery.Considering the high deployment cost of data aggregators,this thesis firstly studies the Data Aggregating Bundles Construction(DABG)problem,and proves that the problem is also NP-hard.A Min Disk-based greedy algorithm called DABGA is proposed to solve the DABG problem.The approximate ratio of DABGA is proved to be ln N,and the time complexity is polynomial,where N is the number of sensors.Then,the minimum UAV deployment algorithm based on the orienteering problem with an approximate ratio of()Oln(38)is proposed to solve the Multi-depot UAVs Trajectory Scheduling(MUTS)problem,where(38)is the total number of all to-be-charged sensors and data aggregators.Through a large number of simulation experiments,the solution proposed in this thesis effectively reduces the comprehensive deployment cost than traditional schemes in WRSNs,and the experimental effect is at least 12.05% higher than those of the existing algorithms.