By exploiting multi-radio multi-channel technology, wireless mesh networks can effectively provide wireless broadband access to the Internet for mobile users. Due to the limited number of orthogonal channels, overlapping channel assignment is one of the main factors that greatly affect the network capacity. However, current results in this area are not so satisfying. In this paper, we first propose a model for measuring achieved network capacity in MR-WMNs. Then we prove that finding an optimal overlapping channel assignment in a given MR-WMN with odd number of channels, is equivalent to finding an optimal assignment by only using its orthogonal channels. This theory allows us to use fewer channels to solve complicated channel assignment problems. Third, we prove that in 802.11b/g MR-WMN the simplified optimization problem is a Max-3-Cut problem. Although this problem is NP-hard, it has an efficient approximation algorithm that achieves approximation ratio of 1.19616 probabilistically by using the algorithm for Max-Cut whose approximation ratio is 1.1383 probabilistically. Based on the algorithm for Max-Cut, this paper proposes Max-Cut based channel assignment (MCCA) which uses a heuristic method to adjust the result produced by the Max-Cut algorithm to achieve an even better result. Finally, we perform extensive simulations to compare the MCCA with a state-of-the-art Tabu-Search based algorithm. The results show that the Max-Cut based overlapping channel assignment algorithm effectively and efficiently improves on the network capacity compared with existing algorithms.

multi-radio multi-channel wireless mesh network, overlapping channel assignment, capacity optimization, graph coloring, Max-Cut