Role and channel assignments for wireless mesh networks using hybrid approach

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.