Authors: Zhigang Chen, Feng Zeng
Addresses: School of Information Science and Engineering, Central South University, Changsha, 410083, China. ' School of Information Science and Engineering, Central South University, Changsha, 410083, China
Abstract: In wireless mesh networks (WMNs), gateway optimal placement is key to network performance, QoS and construction cost. This paper focuses on gateway placement with QoS constraints in WMNs, and aims to minimise the cost of gateway placement. Firstly, a new concept of limited dominating set (LDS) in graph is presented to address the minimum-cost gateway placement problem, which is converted to find the minimum weighted LDS in a graph. Secondly, we propose a heuristic algorithm WMB-LDS to find the minimum weighted LDS for a graph, which takes the performance/cost ratio of gateway candidates as heuristic information. Furthermore, we design a genetic algorithm GA-LDS to search for the global optimal solution. At last, simulation is done, and the experimental results show that, compared with previous work, WMB-LDS has better performance and lower computing complexity, and GA-LDS has the best experiment result at the price of the increasing computing complexity.
Keywords: wireless mesh networks; WMN; gateway placement; dominating sets; QoS constraints; genetic algorithms; quality of service.
International Journal of Communication Networks and Distributed Systems, 2010 Vol.4 No.4, pp.389 - 406
Received: 17 Feb 2009
Accepted: 30 Sep 2009
Published online: 10 May 2010 *