Research On Mobile Charging Planning Algorithms Based On Meta-Heuristic Method In Wireless Sensor Network

With the development and application of emerging technologies such as 5G,Artificial Intelligence and Big Data,etc,Wireless Sensor Network(WSN)which is as the main component of Internet of Thing(IOT)has been faced with unprecedented opportunities and challenges.However,the energy problems caused by the energy-limited battery and energy holes phenomenon severely restrict the application of WSN,and are the key and difficult points in this research field.Recently,to prolong the lifetime of the WSN,the wireless charging equipment(WCE)carrying energy was introduced to charge the sensor nodes based on wireless charging technology,which has become a research hotspot and provided a new idea to solve the energy problems of WSN.Due to the mobility of the WCE,in different network scenarios,how to determine the charging path and charging time of the WCE in each sensor node(i.e.the charging planning of the WCE)becomes the key issue.In this thesis,the charging planning problems in different network scenarios are studied.The optimization model of the problems are formulated respectively,aiming at the combinational scenarios of single-WCE or multi-WCE,single-node charging or multi-node charging(the WCE only charges one node at a time or charges many nodes at the same time),the limited-energy or sufficient-energy of WCE and the charging time constraint.Based on the Meta-heuristic methods,several hybrid meta-heuristic algorithms are proposed to solve the problems.The proposed charging planning methods can be applied in different scale and application network scenarios,and can improve the energy utility and service quality of WCE and extend the lifetime of WSN.The main contents and contributions of this thesis can be listed as follows.(1)Aiming at the single-node charging planning problem with an energy-limited WCE,the periodic charging planning model of the previous research is improved,and the necessary conditions to construct the periodic charging planning are proved.Three situations of limited moving energy of WCE,imbalanced energy consumption rate of sensor nodes and combination of the two are analyzed,and their charging strategy are designed.The optimization problem to maximize the vacation time radio of WCE is formulated.As the problem is nonlinear and belongs to combination optimization problem,the Hybrid Particle Swarm Optimization Genetic Algorithm(HPSOGA)is proposed to solve the problem,and the PSO mutation operator is introduced into GA and the cross operator is improved.Experiments show that HPSOGA is superior to PSO,GA,MMAS and DFWA in three situations,and the best charging planning of WCE under the three situations are shown.(2)Aiming at single-node charging planning problem of WCE with charging time window,the two reasons of introducing charging time window is discussed,and the penalty function of violating the time window and related constraint conditions are analyzed.The optimization problem is built in order to minimize the charging cost,and the NP-Complete complexity of the problem is proved.To solve the problem,the Discrete Tabu Search Firework Algorithm(DTSFWA)is proposed.Based on DFWA,the tabu search mechanism is introduced in the DTSFWA,which can accept the inferior solutions with tabu strategy and amnesty criteria to jump out of local optimal solution.Experiments show that DTSFWA is superior to Line Appr and En Greedy in the six combination scenarios of three network distributions and two kinds of penalty functions.The charging planning solutions in linear penalty function random distributed scenario and nonlinear penalty function random distributed scenario are shown.(3)Aiming at multi-node charging planning problem with an energy-limited WCE,the network is partitioned based on virtual cellular grid method,the working states and constraints of WCE are analyzed,and the necessary conditions to construct the charging planning in ideal assumption are proved.The optimization problem to maximize the energy utilization of WCE is formulated.Three situations of limited moving energy,limited charging energy and both of limited moving and charging energy of WCE are analyzed,and the moving path determination strategy and the charging time determination strategy are designed.Based on DFWA,the Hybrid Simulated Annealing-Discrete Firework Algorithm(HSA-DFWA)is proposed to solve the problem,and the simulated annealing strategy and 4-opt method are introduced to improve the global search and the local search respectively,the Metropolis criteria is introduced to accept the inferior solutions.Experiments show that HSA-DFWA is superior to MM-ANT,DFWA,P-greedy and E-greedy in three situations,and the best charging planning of the three situations are shown.(4)Aiming at multi-WCE charging planning problem(MWCP),the constraints of the problem are analyzed,and the optimization problem with the objective of maximizing the sum charging time and the energy consumption of the WCEs is built.The NP-Complete complexity of the problem is proved.Then,through the mapping relationship between MWCP and Reinforcement Learning(RL),the MWCP is transformed into the RL model,and the time step,state space,action space,state transition function and return function are designed.Based on the swarm optimization of the Meta-heuristic methods,the Discrete Firework Algorithm Q-learning(DFWA-Q)is porposed to solve the problem,and the multi-learner strategy is introduced to exchange the information of each learner and accelerate the speed of the RL.Experiments show that DFWA-Q is superior to AVG-Q,PSO-Q,Single-Q and CMCS in different network scale,and the DFWA-Q has a fast convergence performance than the other algorithms.The best charging planning solution of WCE in 50 sensor nodes network is shown.