Joint Routing and Channel Assignment in Multi-Channel Wireless Infrastructure Networks

Multi-channel wireless networks are increasingly being employed as infrastructure networks in metro areas. In addition, nodes in these networks employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute a path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth. Such a path must satisfy the constraint that no two consecutive links on the path are assigned the same channel, referred to as "channel discontinuity constraint." In this paper, we develop two graph expansion techniques to compute the minimum cost path between a given node pair that satisfy the channel discontinuity constraint. The first expansion provides the exact solution in polynomial time using minimum cost perfect matching algorithm. The second expansion results in a lesser complexity algorithm compared to the former and is amenable to distributed implementation, while it may result in infeasible paths at times. Through extensive simulations, we study the effectiveness of the routing algorithms developed based on the two expansion techniques and the benefits of employing the minimum cost perfect matching based solution. We show that the lesser complexity algorithm may not be able to compute a path for less than 2% of the calls in the networks considered.