Minimum-cost gateway placement in wireless mesh networks with QoS constraints. (11th May 2010)

• Record Type: Journal Article
• Authors: Chen, Zhigang; Zeng, Feng
• Is Part Of: International journal of communication networks and distributed systems. Volume 4:Number 4(2010)
• Page Start: 389
• Page End: 406
• Publication Date: 2010-05-11
• Subjects: wireless mesh networks -- WMN -- gateway placement -- dominating sets -- QoS constraints -- genetic algorithms -- quality of service; Computer networks -- Periodicals; Telecommunication systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; 004.6
• Languages: English
• ISSNs: 1754-3916

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.