Title: Minimum-cost gateway placement in wireless mesh networks with QoS constraints

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.

DOI: 10.1504/IJCNDS.2010.033161

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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article