Channel assignment for wireless meshes with tree topology

The capacity of wireless mesh networks can be enhanced with judicious channel assignment. This paper deals with one particular type of mesh network topology - the tree topology. The unique characteristics of this topology is that all the traffic to/from the mesh nodes goes through the root. This enables design of an efficient channel allocation algorithm that utilizes the intrinsic characteristics of the tree topology and the traffic pattern over this topology. We use the unique connection characteristics of the tree topology to create an auxiliary contention graph over which we execute our coloring algorithm. This mitigates the burden of ensuring connectivity that channel allocation algorithms for mesh have to consider and the algorithm can solely focus on the task of capacity maximization. Our algorithm has a low complexity of O(N²) for a mesh network with N nodes.