Research On Node Deployment Algorithm Of Wireless Mesh Network For Emergency Communication

In emergency communication scenarios,existing basic communication facilities are often destroyed due to disasters,which cannot meet the communication needs of emergency rescue operations.Wireless Mesh Network(WMN)has the characteristics of no center,selforganization and self-configuration,which is very suitable for the construction of temporary emergency communication networks.To provide communication service support for rescue operations.The key to build an emergency communication wireless Mesh network is how to quickly determine the deployment location of nodes in the target area so that the deployed network can achieve the target network performance.Relevant studies show that this kind of Router Node Placement(RNP)problem with multiple constraints and multiple optimization objectives belongs to NP-hard problem,and its solution space increases exponentially with the increase of problem size,and the optimal solution cannot be obtained in polynomial time.At present,many scholars use heuristic or swarm intelligent optimization methods to obtain the approximate optimal solution.However,when there are obstacles in the target area that affect the deployment position of network nodes and affect the communication link between nodes(such as causing line-of-sight link interruption),the search efficiency of heuristic or swarm intelligent optimization algorithm will be sharply reduced,restricting the practical application of the algorithm.This thesis focuses on the research and design of efficient WMN initial node deployment algorithm and node dynamic adjustment algorithm for RNP problems based on Unmanned Aerial Vehicle(UAV)platform under such complex constraints.The main research contents and innovative achievements of this thesis include:(1)Aiming at the communication coverage requirements in the initial stage of emergency rescue operations,an obstacle avoidance A-star Minimum Steiner tree node deployment algorithm(OAMST-RNP)was designed to minimize the number of nodes and maximize user coverage.In this thesis,the initial deployment network model is established according to the characteristics of emergency communication scenarios,and then the minimum Steiner tree algorithm for generating the shortest network is combined with the A-star algorithm for path planning to solve the node deployment problem in the initial stage.Firstly,the minimum Steiner tree algorithm was used to generate the backbone network contour connecting the gateway node and several hot spot centers,and a Steiner point obstacle avoidance strategy was designed to ensure the convergence of the subsequent generation of obstacle avoidance paths and the obstacle avoidance deployment of nodes.Then the A-star algorithm is used to generate the obstacle avoidance paths along the backbone network contour and deploy the backbone nodes.An adaptive neighborhood location search strategy along the circumference is designed.According to the position relationship between the current candidate location and the target node,On the circumference with the current candidate location as the center of the circle,a unilateral neighborhood location set was generated at an Angle of 30° or a single neighborhood location was generated along the line-of-sight direction.At the same time,the neighborhood location filtering mechanism was improved to ensure the line-of-sight link,which not only improved the search accuracy but also reduced the number of deployed nodes.Finally,a node expansion deployment algorithm based on greedy strategy is designed to select the location with the highest coverage rate among the neighborhood locations of deployed nodes,so as to improve the user coverage rate of the whole network.The simulation results show that compared with similar algorithms,the emergency communication network constructed by OAMST-RNP algorithm in the same environment requires fewer nodes,higher user coverage,and less maximum and average hops to reach the gateway node.(2)According to the communication coverage requirements during emergency rescue operations,the layered composite virtual force node dynamic adjustment algorithm(HCVF-dynRNP)was designed to dynamically optimize and adjust the deployed network nodes,so as to provide continuous network communication services for the disasterstricken people and rescue workers during the rescue operations.In this thesis,a dynamic network model is established to simulate the rescue and evacuation action,and the evacuation path is planned for the disasteraffected people and the random changes of users are considered.The HCVF-dynRNP algorithm makes hierarchical optimization adjustment according to the different contributions of nodes to network connectivity:Based on the hierarchical traversal order of the tree structure,firstly,a strategy for generating candidate positions oriented to the stade-of-sight link is designed to ensure the connectivity between the branch node and the original parent node as far as possible,so as to reduce the changes of the network topology.Meanwhile,the running cost and node movement cost of the algorithm are optimized during the generation of candidate positions.Then,the composite virtual force that does not cover the user area is designed and explored to guide the leaf node to adjust,so as to improve the coverage of the user demand of the network.To ensure the connectivity of the network after adjustment,the isolated nodes generated in the adjustment process are adjusted twice by expanding the candidate area.The simulation results show that compared with similar algorithms,the deployment network adjusted by HCVF-dynRNP algorithm can better adapt to the real-time distribution of user needs and maintain a higher coverage rate of user needs with lower node movement cost.Finally,the thesis summarizes the full text and looks forward to the next step.