Michele Garetto
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.
- 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.Google Scholar
- V. Bharghavan, S. Demers, S. Shenker, and L. Zhang. MACAW: A media access protocol for wireless LANs. In Proceedings of ACM SIGCOMM '94, London, UK, August 1994. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- M. Carvalho and J.J. Garcia-Luna-Aceves. Delay analysis of IEEE 802.11 in single-hop networks. In Proceedings of IEEE ICNP '03: 11th IEEE International Conference on Network Protocols, Atlanta, Georgia, November 2003. Google ScholarDigital Library
- C. Chaudet, D. Dhoutaut, and I. G. Lassous. Experiments of some performance issues with IEEE 802.11b in ad hoc networks. In Second Annual Conference on Wireless On-demand Network Systems and Services (WONS'05), St. Moritz, Switzerland, January 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J.J. Garcia-Luna-Aceves and A. Tzamaloukas. Reversing the collision-avoidance handshake in wireless networks. In Proceedings of ACM MobiCom '99, Seattle, Washington, August 1999. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- V. Kanodia, C. Li, A. Sabharwal, B. Sadeghi, and E. Knightly. Ordered packet scheduling in wireless ad hoc networks: Mechanisms and performance analysis. In Proceedings of ACM MobiHoc, Lausanne, Switzerland, June 2002. Google ScholarDigital Library
- P. Karn. MACA: A new channel access method for packet radio. In ARRL/CRRL Amateur Radio 9th Computer Networking Conference, April 1990.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- S. Ray, J. Carruthers, and D. Starobinski. Evaluation of the masked node problem in ad-hoc wireless LANs. IEEE Transactions on Mobile Computing, in press. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Y. Wang and J.J. Garcia-Luna-Aceves. Channel sharing of competing flows in ad hoc networks. In IEEE Symposium on Computers and Communications (ISCC '03), Kemer-Antalya, Turkey, July 2003. Google ScholarDigital Library
- R. W. Wolff. Stochastic Modeling and the Theory of Queues. Prentice Hall, 1989.Google Scholar
- J. Yoon, M. Liu, and B. Noble. Sound mobility models. In Proceedings of ACM MobiCom '03, San Diego, CA, September 2003. Google ScholarDigital Library
Index Terms
- Modeling media access in embedded two-flow topologies of multi-hop wireless networks
Recommendations
Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks
Multi-hop wireless networks employing random access protocols have been shown to incur large discrepancies in the throughputs achieved by the flows sharing the network. Indeed, flow throughputs can span orders of magnitude from near starvation to many ...
Contention in multi-hop wireless networks: model and fairness analysis
MSWiM '09: Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systemsIn multi-hop wireless networks with Carrier Sense Multiple Access (CSMA), unfairness may arise due to a number of reasons. A majority of the existing work focuses on fairness issues due to hidden terminals and the impact on backoff mechanisms. This ...
Starvation mitigation through multi-channel coordination in CSMA multi-hop wireless networks
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computingExisting 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 ...
Comments