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%similar to 32%, and the load variance on the gateways decreased by 77%similar to 86%. For the genetic algorithm, the performance improvement is at the price of the increase of the CPU execution time.