Research On Gateway Deployment Of Wireless Mesh Networks Based On Graph Theory And PSO Algorithm And Its Popularization

In wireless mesh networks, most network traffic aggregation at the gateway, deployment of gateway has a direct effect on network quality of service, reasonable gateway deployment is important to enhance network performance. Gateway deployment of wireless mesh networks is similar to the K-center facility location problem, reasonable facility location can effectively save resources, reduce costs and improve the social and economic benefits. Gateway deployment of wireless mesh networks and K-center facility location problem are studied in this paper. The main work is as follows:(1) Deployment of gateway can be classified vertex K-center problem and geometry K-center problem. vertex K-center problem and geometry K-center problem are used deploy gateway in the same network topology, by comparing the two deployment methods, geometry K-center problem is more universal, and can get the global optimal solution in theory. Likewise, the K-center facility location problem is classified discrete K-center facility location problem and continuous K-center facility location problem, the results show that continuous K-center facility location problem has greater flexibility and chosen better facilities location. In addition, different test functions are optimized by PSO algorithm, simulation results show that the state of convergence on PSO algorithm significantly affected by the initial value. When PSO algorithm is used to solve the geometry K-center gateway deployment problem, the initial position of particles is improved, network coverage radius can be reduced.(2) The Center PSO algorithm is proposed to solve the geometry K-center gateway deployment problem in wireless mesh networks. The algorithm can be described as to find full connected sub-graphs in given network topology, then great full connected sub-graphs with the most complete function are filtered out, and the position of initial center points are obtained by great full connected sub-graphs. Combining initial center points with PSO, the particles are initialized at the position of initial center points, and random inertia weight is introduced, the algorithm can get optimal solution. Compared with other algorithms, the simulation results show that the proposed method can achieve better optimization effect and convergence rate.(3) For continuous K-center facility location problem, a new solution model is constructed in this paper, the minimum weighted distance between service station to demand nodes as the optimization target, and PSOwSA algorithm is proposed to optimize the minimum weighted distance. Simulated annealing and random inertia weight are introduced, the algorithm is not easy to fall into local optimum, and convergence is accelerated. Compared with other algorithms, the simulation results show that the PSOwSA algorithm has small weighted distance, more stable result and faster convergence rate.Two classic issues are analyzed and studied in the above, and proposed feasible solutions to solve the two issues. The proposed methods are equally applicable to social networks, wireless sensor networks and logistics networks.