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

作　　者：曾锋 陈志刚 

机构地区：[1]CCF [2]School of Information Science and Engineering,Central South University

出　　处：《Journal of Computer Science & Technology》2009年第4期775-785,共11页计算机科学技术学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China under Grant Nos.60773012 and 60873082

摘　　要：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.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.

关 键 词：wireless mesh network gateway placement load balance QoS constraint genetic algorithm 

分 类 号：TN929.5[电子电信—通信与信息系统]