| Wireless Mesh Networks is a key technology of new generation wireless networks, has tremendous advantages over other wireless networks, Wireless Mesh Network is a dynamic self-organizing and self-configuring multi-hop wireless network, There are many advantages such as high bandwidth, reliability, wide coverage, low cost of deployment, scalability, etc. In the grid architecture of Wireless Mesh Network, backbone network composed by mesh routers and mesh gateways and provide connectivity services to mesh client nodes. The connectivity and performance of Wireless Mesh Network is depends on the location of mesh network router, that means the structure of the backbone network is a decisive factor in achieving the connectivity and coverage of the network. Thus, finding an optimal or near-optimal mesh router node place plan is the key of this network.The backbone node deployment problem of Wireless Mesh Network is a typical NP-hard combinatorial optimization problem. Up to now, there are a lot of optimization algorithms purposed to solve this problem. The effective algorithms include: exact algorithms, such as, dynamic programming algorithms, mathematical modeling method, etc. the random search algorithms, such as, heuristic search algorithm, ant colony algorithm, particle swarm optimization, genetic algorithms and simulated annealing algorithm, etc. But, this algorithms unable to satisfy some constraints, such as traffic demand, and The MR and MG deployment optimization problems are considered separately. In this paper, aimed at optimizing the deployment of Wireless Mesh Networks backbone nodes, an effective MR deployment algorithm for minimizing the number of mesh routers under the premise of network connection and meeting the user’s demand of the bandwidth is proposed. Algorithm is divided into two stages. In the first phase, particle swarm algorithm is used to generate gateway deployment scheme meet the performance constraints; In the second phase, first selected the adjacent nodes of the current network topology and calculate the weight of each adjacent nodes, then add the largest weight of adjacent nodes to the backbone network and update the backbone network topology and the candidate nodes information, add nodes to the backbone network constantly using iterative methods until covers all requirements. The number of MR deployed in the second phase as a performance evaluation indicator of the gateway deployment scheme in first phase, improve the gateway deployment scenarios continuously. Experimental comparison test the performance of algorithm in uniform, normal, exponential and Weibull distribution scene, the experimental results prove that the best deployment scheme can be found under small deployment scale, when a larger scale, the number of MR deployed is much less than ILSearch algorithm, and is less than NF-Greedy algorithm around 5%-8% under uniform distribution and normal distribution. |
