Scheduling and Medium Access Control in Wireless Networks

Research Overview/Summary of Contributions:
With my co-researchers, I have been studying the question of optimal scheduling and access control in wireless networks, with the goal of attaining maximum throughput and fairness guarantees in a network-wide sense, while only using local topology information or low-complexity local coordination. We have shown that in a wireless network with Aloha-like random access model, link rates that are globally proportionally fair are attainable using only local network topology information [1]. We have recently obtained similar results for lexicographic maxmin fairness metric as well [5]. We have extended our solution to more complex random access models like CSMA/CA, and our solutions can be used to improve the fairness properties of the widely used 802.11 protocol [2]. Furthermore, for an Aloha-like random access model, we have shown how end-to-end proportional fairness can be attained through local coordination between nodes, and intelligent cross-layer coordination [3]. My co-workers and I have also been amongst the first researchers to characterize the schedulable region of maximal scheduling policies (which can be implemented through low-complexity local coordination), for arbitrary interference models; we have also proved that such scheduling policies attain a constant fraction of maximum throughput region [4]. With a PhD student, I am currently investigating optimal scheduling algorithms for multi-channel access point networks like the growingly popular WiMAX systems[6]. One of our research results [1] is discussed in depth in the book Wireless Networking: A Resource Allocation Perspective by Kumar, Manjunath and Kuri, that is due to be published in early 2008; another [3] is discussed in detail in Wireless Ad Hoc and Sensor Networks: A Cross-Layer Design Perspective ( Springer, 2007) by R. Jurdak.

My research on this topic has been supported by two research grants from NSF.

The key research papers on this topic are:

1. K. Kar, S. Sarkar, L. Tassiulas, Achieving Proportionally Fair Rates using Local Information in Aloha Networks, IEEE Transactions on Automatic Control, Vol . 49, No. 10, October 2004, pp. 1858-1862.
2. X. Wang and K. Kar, Throughput Modelling and Fairness Issues in CSMA/CA Based Ad-Hoc Networks, Proceedings of Infocom 2005, Miami , March 2005. 
3. X. Wang and K. Kar, Cross-Layer Rate Optimization in Multi-Hop Wireless Networks with Random Access, IEEE Journal on Selected Areas in Communications, Vol. 24, No. 8, pp. 1548-1559, August 2006.
4. P. Chaporkar, K. Kar, X. Luo and S. Sarkar, Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks, To appear in IEEE Transactions on Information Theory, Vol. 54, No. 2, February 2008.
5. X. Wang, K. Kar and J-S. Pang, Lexicographic Max-Min Fair Rate Allocation in Random Access Wireless Networks, Proceedings of the 45th IEEE Conf. On Decision and Control (CDC), San Diego, December 2006.
6. K. Kar, X. Luo and S. Sarkar, Throughput-optimal Scheduling in Multichannel Access Point Networks under Infrequent Channel Measurements, Proceedings of IEEE Infocom 2007, Anchorage, May 2007.

Other papers on this topic can be found on my full publication page.