Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints

In wireless mesh networks （WMNs）, gateway placement is the key to network performance, QoS and construction cost. This paper focuses on the optimization of the cost and load balance in the gateway placement strategy, ensuring the QoS requirements. Firstly, we define a metric for load balance on the gateways, and address the minimum cost and load balancing gateway placement problem. Secondly, we propose two algorithms for gateway placement. One is a heuristic algorithm, which is sensitive to the cost, selects the gateway candidates according to the capacity/cost ratio of the nodes, and optimizes the load balance on the gateways through scanning and shifting methods. The other is a genetic algorithm, which can find the global optimal solution. The two algorithms differ in their computing complexity and the quality of the generated solutions, and thus provide a trade-off for WMN design. At last, simulation is done, and experimental results show that the two algorithms outperform the others. Compared with OPEN/CLOSE, the average cost of gateway placement generated by our algorithms is decreased by 8%~32%, and the load variance on the gateways decreased by 77%-86%. For the genetic algorithm, the performance improvement is at the price of the increase of the CPU execution time.

Router and gateway node placement in wireless mesh networks for emergency rescue scenarios

The focus of this paper is on base functionalities required for UAV-based rapid deployment of an ad hoc communication infrastructure in the initial phases of rescue operations.The main idea is to use heterogeneous teams of UAVs to deploy communication kits that include routers,and are used in the generation of ad hoc Wireless Mesh Networks(WMN).Several fundamental problems are considered and algorithms are proposed to solve these problems.The Router Node Placement problem(RNP)and a generalization of it that takes into account additional constraints arising in actual field usage is considered first.The RNP problem tries to determine how to optimally place routers in a WMN.A new algorithm,the RRT-WMN algorithm,is proposed to solve this problem.It is based in part on a novel use of the Rapidly Exploring Random Trees(RRT)algorithm used in motion planning.A comparative empirical evaluation between the RRT-WMN algorithm and existing techniques such as the Covariance Matrix Adaptation Evolution Strategy(CMA-ES)and Particle Swarm Optimization(PSO),shows that the RRT-WMN algorithm has far better performance both in amount of time taken and regional coverage as the generalized RNP problem scales to realistic scenarios.The Gateway Node Placement Problem(GNP)tries to determine how to locate a minimal number of gateway nodes in a WMN backbone network while satisfying a number of Quality of Service(QoS)constraints.Two alternatives are proposed for solving the combined RNP-GNP problem.The first approach combines the RRT-WMN algorithm with a preexisting graph clustering algorithm.The second approach,WMNbyAreaDecomposition,proposes a novel divide-and-conquer algorithm that recursively partitions a target deployment area into a set of disjoint regions,thus creating a number of simpler RNP problems that are then solved concurrently.Both algorithms are evaluated on real-world GIS models of different size and complexity.WMNbyAreaDecomposition is shown to outperform existing algorithms using 73%to 92%fewer router nodes while at the same time satisfying all QoS requirements.