Starvation mitigation through multi-channel coordination in CSMA multi-hop wireless networks

ABSTRACT

Existing multi-channel protocols have been demonstrated to significantly increase aggregate throughput compared to single-channel protocols. However, we show that despite such improvements in aggregate throughput, existing protocols can lead to flow starvation in a multi-hop network, a phenomenon that also occurs with single-channel protocols. In this paper, we devise Asynchronous Multi-channel Coordination Protocol (AMCP), a distributed medium access protocol that not only increases aggregate throughput, but more importantly, addresses the fundamental coordination problems that lead to starvation. Based on AMCP's counter-starvation mechanisms, we analytically derive and experimentally validate an ap-proximate lower bound on the throughput of any flow in an arbitrary topology. We also demonstrate that AMCP can deliver significantly higher per-flow throughput than both IEEE 802.11 and existing multi-channel solutions. In addition to its performance properties, AMCP is both simple in that it operates using the primitives of IEEE 802.11 DCF, and cost-effective in that it requires only a single half-duplex transceiver and no infrastructure support.

REFERENCES

• 1: Atul Adya , Paramvir Bahl , Jitendra Padhye , Alec Wolman , Lidong Zhou, A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.344-354, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.8]
• 2: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023742]
• 3: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 4: G. Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 18(3):535--547, March 2000.
• 5: Imrich Chlamtac , András Faragó , Hongbiao Zhang, Time-spread multiple-access (TSMA) protocols for multihop mobile radio networks, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.804-812, Dec. 1997 [doi>10.1109/90.650140]
• 6: I. Chlamtac and A. Lerner. Fair Algorithms for Maximal Link Activation in Multihop Radio Networks. IEEE Transactions on Communications, 35, July 1987.
• 7: T.A. ElBatt and A. Ephremides. Joint Scheduling and Power Control for Wireless Ad-hoc Networks. In Proc. IEEE INFOCOM, New York, NY, USA, June 2002.
• 8: A. Ephremides and T.V. Truong. Scheduling Broadcasts in Multihop Radio Networks. IEEE Transactions on Communications, 38(4), April 1990.
• 9: A. Ephremides, J.E. Wieselthier, and D.J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. of IEEE, 75(1):56--73, 1987.
• 10: J. J. Garcia-Luna-Aceves , Chane L. Fullmer, Floor acquisition multiple access (FAMA) in single-channel wireless networks, Mobile Networks and Applications, v.4 n.3, p.157-174, Oct 1999 [doi>10.1023/A:1019146831447]
• 11: J.J. Garcia-Luna-Aceves and Y. Wang. Throughput and Fairness of Collision Avoidance Protocols in Ad Hoc Networks. Ad Hoc Networks: Technologies and Protocols, Kluwer Academic Publishers, 2004.
• 12: M. Garetto, T. Salonidis, and E. Knightly. Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks. In Proc. IEEE INFOCOM, Barcelona, Spain, 2006.
• 13: Michele Garetto , Jingpu Shi , Edward W. Knightly, Modeling media access in embedded two-flow topologies of multi-hop wireless networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080851]
• 14: IEEE 802.11 Working Group. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications. 1997.
• 15: Haiyun Luo , Songwu Lu , Vaduvur Bharghavan, A new model for packet scheduling in multihop wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.76-86, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345923]
• 16: B. Hajek and G. Sasaki. Link Scheduling in Polynomial Time. IEEE Transactions on Information Theory, 34(5):910--917, September 1988.
• 17: Xiao Long Huang , Brahim Bensaou, On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501447]
• 18: N. Jain and S.R. Das. A Multichannel CSMA MAC Protocol with Receiver-Based Channel Selection for Multihop Wireless Networks. In Proc. IC3N, Scottsdale, AZ, USA, October 2001.
• 19: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 20: A. Kumar, E. Altman, D. Miorandi, and M. Goyal. New insights from a fixed point analysis of single cell IEEE 802.11 WLANs. In Proc. IEEE INFOCOM,Miami,FL, March 2005.
• 21: C.R. Lin. On-demand QoS routing in Multihop mobile networks. In Proc. IEEE INFOCOM, Anchorage, AK, April 2001.
• 22: H. Luo, J. Cheng, and S. Lu. Self-coordinating localized fair queueing in wireless ad hoc networks. IEEE Transaction on Mobile Computing, 3(1), January-March 2004.
• 23: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 24: A. Nasipuri and S. Das. A Multichannel CSMA MAC Protocol for Multihop Wireless Networks. In Proc. IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, September 1999.
• 25: M.J. Neely, E. Modiano, and C.E. Rohrs. Dynamic Power Allocation and Routing for Time Varying Wireless Networks. IEEE Journal on Selected Areas in Communications, 23(1):89--103, Jan 2005.
• 26: Timucin Ozugur , Mahmoud Naghshineh , Parviz Kermani , C. Michael Olsen , Babak Rezvani , John A. Copeland, Balanced media access methods for wireless networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.21-32, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288244]
• 27: S. Ramanathan, A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.900, April 09-11, 1997
• 28: Theodoros Salonidis , Leandros Tassiulas, Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062709]
• 29: S. Sarkar and L. Tassiulas. End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks . In Proc. Control and Decision Conference (CDC), Maui, HI, USA, December 2003.
• 30: Jungmin So , Nitin H. Vaidya, Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989487]
• 31: L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless networks. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002.
• 32: Y.C-. Tseng, C.S-. Hsu, and T.-Y. Hsieh. Power-saving protocols for IEEE 802.11-based Multi-hop Wireless Networks. In Proc. IEEE INFOCOM, New York, NY, USA, June 2002.
• 33: S.-L. Wu , C.-Y Lin , Y.-C. Tseng , J.-P. Sheu, A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks, Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), p.232, December 07-07, 2000
• 34: Chenxi Zhu , M. S. Corson, A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks, Wireless Networks, v.7 n.4, p.371-384, 08/01/2001 [doi>10.1023/A:1016683928786]
• 35: C. Zhu and M.S. Corson. QoS routing for mobile ad hoc networks. In Proc. IEEE INFOCOM, NewYork, NY, June 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Design, Performance

Keywords:
CSMA, CSMA/CA, multiple channels, starvation