A Distributed Joint Channel-Assignment,
Scheduling and Routing Algorithm for
Multi-Channel Ad Hoc Wireless Networks
Xiaojun Lin and Shahzada Rasool
School of Electrical and Computer Engineering, Purdue University
West Lafayette, IN 47907, U.S.A.
{linx,srasool}@ecn.purdue.edu

Abstract— The capacity of ad hoc wireless networks can be substantially increased by equipping each network node with multiple radio interfaces that can operate on multiple non-overlapping channels. However, new scheduling, channelassignment, and routing algorithms are required to fully utilize the increased bandwidth in multi-channel multi-radio ad hoc networks. In this paper, we develop a fully distributed algorithm that jointly solves the channel-assignment, scheduling and routing problem. Our algorithm is an online algorithm, i.e., it does not require prior information on the offered load to the network, and can adapt automatically to the changes in the network topology and offered load. We show that our algorithm is provably efficient. That is, even compared with the optimal centralized and offline algorithm, our proposed distributed algorithm can achieve a provable fraction of the maximum system capacity.
Further, the achievable fraction that we can guarantee is larger than that of some other comparable algorithms in the literature.

I. I NTRODUCTION
Multi-channel multi-radio ad hoc wireless networks have recently received a substantial amount of interest, especially under the context of wireless mesh networks [1]–[13]. It has been shown that one can significantly increase the capacity of ad hoc wireless networks by equipping each network node with multiple radio interfaces that operate on multiple non-overlapping channels. This is motivated by some current wireless LAN standards (in particular, IEEE 802.11) where the entire frequency band is divided into