A Systematic Study of Maximal Scheduling Algorithms in Multiradio Multichannel Wireless Networks

The greedy maximal scheduling (GMS) and maximal scheduling (MS) algorithms are well-known low-complexity scheduling policies with guaranteed capacity region in the context of single-radio single-channel (SR-SC) wireless networks. However, how to design maximal scheduling algorithms for multiradio multichannel (MR-MC) wireless networks and the associated capacity analysis are not well understood yet. In this paper, we develop a new model by transforming an MR-MC network node to multiple node-radio-channel (NRC) tuples. Such a framework facilitates the derivation of a tuple-based back-pressure algorithm for throughput-optimal control in MR-MC wireless networks and enables the tuple-based GMS and MS scheduling as low-complexity approximation algorithms with guaranteed performance. An important existing work on GMS and MS for MR-MC networks is that of Lin and Rasool (IEEE/ACM Trans. Networking, vol. 17, no. 6, 1874-1887, Dec. 2009), where link-based algorithms are developed. Compared to the link-based algorithms, the tuple-based modeling has significant advantages in enabling a fully decomposable cross-layer control framework. Another theoretical contribution in this paper is that we, for the first time, extend the local-pooling factor analysis to study the capacity efficiency ratio of the tuple-based GMS in MR-MC networks and obtain a lower bound that is much tighter than those known in the literature. Moreover, we analyze the communications and computation overhead in implementing the distributed MS algorithm and present simulation results to demonstrate the performance of the tuple-based maximal scheduling algorithms.