標題: Role and channel assignments for wireless mesh networks using hybrid approach
作者: Jeng, Andy An-Kai
Jan, Rong-Hong
資訊工程學系
Department of Computer Science
關鍵字: Wireless mesh network;Multi-channel multi-interface;Channel assignment;Role assignment;NP-hardness;Greedy algorithm
公開日期: 13-Aug-2009
摘要: The wireless mesh network has been considered one of the most promising techniques to extend the broadband access to the last mile. To utilize multiple channels on more than one interface, a number of approaches have been proposed. In particular, the hybrid strategy that combines the benefits of high channel diversity and low coordination cost has seen growing interest in recent studies. In this paper, we define two optimization problems, named the role assignment and the semi-fixed channel assignment, to characterize the unique feature in the hybrid strategy. We proved that the two problems are NP-hard even if the transmission ranges of interfaces are equal. In order to solve our problems in reasonable time, we design efficient algorithms. For the role assignment problem, we give an 1/2-approximate algorithm to find a nearly optimal solution. For the semi-fixed channel assignment problem, a heuristic algorithm, based on transferring from a coloring-based problem, is proposed. Experimental results show that optimizing the defined problems is indeed beneficial to improve the network throughput, and the proposed algorithms are significantly superior to existing methods. (C) 2009 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.comnet.2009.03.020
http://hdl.handle.net/11536/6817
ISSN: 1389-1286
DOI: 10.1016/j.comnet.2009.03.020
期刊: COMPUTER NETWORKS
Volume: 53
Issue: 12
起始頁: 2225
結束頁: 2240
Appears in Collections:Articles


Files in This Item:

  1. 000268415700016.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.