K-barrier Construction And Optimal Charging Scheduling Of Wireless Rechargeable Sensor Network

Coverage and wireless charging has been a hot topic in wireless sensor networks.According to different coverage objects,coverage problems can be divided into: barrier coverage,area coverage and target coverage.In barrier coverage,k barriers are generally constructed to improve the monitoring quality.The life time of k-barrier is limited due to that battery capacity of each sensor node is fixed.In the case of wireless charging,the sensor nodes are usually charged and maintained by mobile charger or fixed charger.In recent years,there has been a lot of research on barrier coverage and wireless charging.Some researchers have used rechargeable sensors to address energy problems in sensor networks.Indeed,most of them concentrate on energy harvesting,which can be easily affected by adverse weather conditions.The coverage network with rechargeable sensors can use wireless charging vehicles or fixed chargers to provide energy,and the source of energy is more reliable.To our knowledge,this is the first study to investigate the recharging schedule problem in the k-barrier coverage.In this paper,based on the rechargeable sensor,we consider the problem of k-weak barrier construction and charging schedule,and the optimization goal is to minimize the network energy consumption.Among them,wireless charging vehicle scheduling is a NP-hard problem.We proved the sufficient condition of MEK-WB that there exists a feasible charging schedule to assure continuous operation of k-weak barrier.Then,we proposed a bounded approximation charging schedule algorithm based on minimum cost maximum flow with provable approximation ratio and time complexity.Finally,the simulation results show that the algorithm is effective.Considering the differences of different network environments,fixed chargers are arranged to supplement the energy of sensor nodes in the k-barrier network.In this work,we assume the energy cost of each sensor includes coverage and communication.In order to combine the barrier coverage problem with the wireless charging problem,we first carried out a phased optimization of the problem:(1)minimum coverage energy k-barrier problem;(2)minimum number of chargers deployed problem.In problem(1),we use the minimum cost maximum flow algorithm to construct the k-barrier network with the minimum perceived energy consumption.And the minimum energy consumption communication tree is constructed based on the shortest path algorithm to determine the energy consumption of each sensor node.In problem(2),we proposed two approximate algorithms named Maximum Charging Utility Greedy Algorithm(MCUGA)and Location First Greedy Selection Algorithm(LFGSA)based on different charger selection strategies.Finally,according to the characteristics of k-barrier network,we put forward the concept of equivalent node.In the two approximation algorithms,equivalent node substitution is used respectively,which greatly improves the performance of the two algorithms.In the simulation experiment,we use a series of parameters to evaluate the performance of the two algorithms.