Research On Approximation Algorithms Based On Data Collection With UAV In Wireless Sensor Networks

Wireless sensor network(WSN)is composed of a large number of sensor nodes with the ability of sensing,computing and wireless communication,which can sense and collect the data of the monitored area in a cooperative way through multi-hop and self-organization.Through data processing and transmission,it presents valuable information for people.However,due to the limitation of cost and other conditions,the ability of communication and endurance of sensor nodes is limited,and due to the worse node deployment environment,the cost of regular charging or battery replacement is too high,so unmanned aerial vehicle(UAV)and other mobile collectors with low cost and flexible control are produced.However,due to the limitation of power supply,it is very important to plan the data collection path of UAV reasonably.The purpose of this paper was to minimize the time of flight of UAV based on one to many data collection in wireless sensor networks(FTM-MSDC).The goal of this problem was to minimize the data collection time and flight time of UAV while successfully collecting the data of all sensor nodes in wireless sensor networks.In this problem,UAV can collect data from multiple sensor nodes at the same time.By reducing the set covering problem to FTM-MSDC problem,this paper proves that FTM-MSDC problem is NP-hard.This paper first considered a special case of the FTM-MSDC problem,that is,when the sensor nodes were all placed on a straight line.The UAV can only collect data by hovering at a certain point.Based on this,an approximation algorithm has been proposed to solve this problem.The algorithm consisted of two steps:first,the set of sensor nodes were divided into multiple subsets that may overlap with each other;then,we found some hovering points and the corresponding hovering time for data collection of all the sensors for each subset.After discussing the special case,this paper considered the general situation of the problem,that is,when the sensor nodes were randomly placed in two-dimensional space.We still assumed that the UAV can only collect data by hovering at a certain point.Based on the above assumptions,this paper proposed an improved approximation algorithm to solve the generalization problem.Finally,the simulation experiments have been presented in this paper,and the effectiveness of the algorithm has been proved by comparing the algorithm with other existing research results.