Title :
A Systematic Study of Maximal Scheduling Algorithms in Multiradio Multichannel Wireless Networks
Author :
Yu Cheng ; Hongkun Li ; Shila, Devu Manikantan ; Xianghui Cao
Author_Institution :
Dept. of Electr. & Comput. Eng., Illinois Inst. of Technol., Chicago, IL, USA
Abstract :
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.
Keywords :
distributed control; optimal control; radio networks; telecommunication control; telecommunication scheduling; wireless channels; MR-MC wireless network node; NRC tuple-based GMS scheduling; NRC tuple-based MS scheduling; SR-SC wireless network; decomposable cross-layer control framework; distributed MS algorithm; greedy maximal scheduling algorithm; local pooling factor analysis; low-complexity approximation algorithm; low-complexity scheduling policies; maximal scheduling algorithm; multiple node radio channel tuple; multiradio multichannel wireless network; single-radio single-channel wireless network; throughput-optimal control; tuple-based back-pressure algorithm; Context; Interference; Resource management; Schedules; Scheduling; Scheduling algorithms; Wireless networks; Capacity region; local-pooling factor; maximal scheduling; multiradio multichannel; throughput-optimal control;
Journal_Title :
Networking, IEEE/ACM Transactions on
DOI :
10.1109/TNET.2014.2324976