Modeling media access in embedded two-flow topologies of multi-hop wireless networks

ABSTRACT

In this paper, we decompose a large- or small-scale multi-hop wireless network into embedded subgraphs, each consisting of four nodes and two flow pairs. We systematically study all twelve possible topologies that arise according to whether the different nodes are in radio range of each other. We show that under both a random spatial distribution of nodes and random waypoint mobility with shortest-path routing, a critical and highly probable scenario is a class in which the channel state shared by the two flows is not only incomplete (i.e., the graph is not fully connected), but there is also asymmetry in the state between the two flows. We develop an accurate analytical model validated by simulations to characterize the long-term unfairness that naturally arises when CSMA with two- or four-way handshake is employed as a random access protocol. Moreover, we show that another key class of topologies consists of incomplete but symmetric shared state. We show via modeling and simulations that in this case, the system achieves long-term fairness, yet endures significant durations in which one flow dominates channel access with many repeated transmissions before relinquishing the channel. The model predicts the time-scales of this unfairness as a function of system parameters such as the maximum retransmission limit.

REFERENCES

• 1: G. Berger-Sabbatel, A. Duda, M. Heusse, and F. Rousseau. Short-term fairness of 802.11 networks with several hosts. In Proceedings of the 6th IFIP/IEEE International Conference on Mobile and Wireless Communication Networks, Paris, France, October 2004.
• 2: 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
• 3: V. Bharghvan. Performance evaluation of algorithms for wireless medium access. In Proceedings of IEEE International Computer Performance and Dependability Symposium (IPDS '98), Durham, NC, March 1998.
• 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: Marcelo M. Carvalho , J. J. Garcia-Luna-Aceves, Delay Analysis of IEEE 802.11 in Single-Hop Networks, Proceedings of the 11th IEEE International Conference on Network Protocols, p.146, November 04-07, 2003
• 6: Claude Chaudet , Dominique Dhoutaut , Isabelle Guerin Lassous, Experiments of Some Performance Issues with IEEE 802.11b in Ad Hoc Networks, Proceedings of the Second Annual Conference on Wireless On-demand Network Systems and Services (WONS'05), p.158-163, January 19-21, 2005 [doi>10.1109/WONS.2005.16]
• 7: B. P. Crow, I. K. Widjaja, G. Jeong, and P. T. Sakai. IEEE 802.11 wireless local area networks. IEEE Communications Magazine, 35(9):116--126, September 1997.
• 8: J. J. Garcia-Luna-Aceves , Asimakis Tzamaloukas, Reversing the collision-avoidance handshake in wireless networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.120-131, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313516]
• 9: M. Garetto, T. Salonidis, and E. Knightly. Starvation in CSMA-Based Multi-hop Wireless Networks: Model and Solutions. Technical report, Rice University, Houston, TX, 2005.
• 10: N. Gupta and P. R. Kumar. A Performance Analysis of the 802.11 Wireless LAN Medium Access Control. Communications in Information and Systems, 3(4):279--304, 2004.
• 11: V. Kanodia , A. Sabharwal , B. Sadeghi , E. Knightly, Ordered packet scheduling in wireless ad hoc networks: mechanisms and performance analysis, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513808]
• 12: P. Karn. MACA: A new channel access method for packet radio. In ARRL/CRRL Amateur Radio 9th Computer Networking Conference, April 1990.
• 13: A. Kumar, E. Altman, D. Miorandi, and M. Goyal. New insights from a fixed point analysis of single cell IEEE 802.11 WLANs. In Proceedings of IEEE INFOCOM '05, Miami, FL, 2005.
• 14: L. E. Miller. Distribution of link distances in a wireless network. Journal of Research of the National Institute of Standards and Technology, 106(2):401--412, 2001.
• 15: Saikat Ray , Jeffrey B. Carruthers , David Starobinski, Evaluation of the Masked Node Problem in Ad Hoc Wireless LANs, IEEE Transactions on Mobile Computing, v.4 n.5, p.430-442, September 2005 [doi>10.1109/TMC.2005.66]
• 16: S. Ray, D. Starobinski, and J. Carruthers. Performance of wireless networks with hidden nodes: A queueing-theoretic analysis. Journal of Computer Communications (Special Issue on the Performance of Wireless LANs, PANs, and Ad-Hoc Networks), in press.
• 17: Y. Sun, X. Gao, E. M. Belding-Royer, and J. Kempf. Model-based resource prediction for multi-hop wireless networks. In Proceedings of the 1st IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS), Ft. Lauderdale, FL, October 2004.
• 18: F. A. Tobagi and L. Kleinrock. Packet switching in radio channels: Part II - the hidden terminal problem in carrier sense multiple access and the busy tone solution. IEEE Transactions on Communications, 23(12):1417--1433, 1975.
• 19: Y. Wang and J.J. Garcia-Luna-Aceves. A new hybrid channel access scheme for ad hoc networks. In Proceedings of Med-Hoc-Net, Sardegna, Italy, September 2002.
• 20: Yu Wang , J. J. Garcia-Luna-Aceves, Channel Sharing of Competing Flows in Ad Hoc Networks, Proceedings of the Eighth IEEE International Symposium on Computers and Communications, p.189, June 30-July 03, 2003
• 21: R. W. Wolff. Stochastic Modeling and the Theory of Queues. Prentice Hall, 1989.
• 22: Jungkeun Yoon , Mingyan Liu , Brian Noble, Sound mobility models, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939007]

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, analytical modeling, fairness