Solution Space Characterization and a Fast Algorithm for the Channel Assignment Problem in Wireless Mesh Networks

In this paper we analyze the characteristics of the solution space of the channel assignment problem in wireless mesh networks where routers are equipped with multiple radio interfaces and can use multiple channels. We show that the solution space is exponentially scaled with respect to the number of communication links, however, high quality solutions lie in dense regions within the solution space. These regions exhibit a high degree of similarity and redundancy. We also analyze the effects of the radio interface constraints on the structure and the size of the solution space. Based on our analysis, we develop a new scheme for channel assignment that dramatically reduces the size of the original solution space into that of a much smaller unconstrained weighted graph coloring problem. This goal is achieved by finding sets of link groups or bindings to represent a good solution structure that meets the radio interface constraints by construction. This structure is then employed to construct a weighted graph coloring problem that is equivalent to the original problem but with a much smaller solution space. Finally, the graph is colored by a heuristic based graph coloring algorithm that takes advantage of the space symmetry to further speed up the assignment process. Experimental results illustrate the superiority of the proposed scheme.