How do wireless chains behave?: the impact of MAC interactions

ABSTRACT

In a Multi-hop Wireless Networks (MHWN), packets are routed between source and destination using a chain of intermediate nodes; chains are a fundamental communication structure in MHWNs whose behavior must be understood to enable building effective protocols. The behavior of chains is determined by a number of complex and interdependent processes that arise as the sources of different chain hops compete to transmit their packets on the shared medium. In this paper, we show that MAC level interactions play the primary role in determining the behavior of chains. We evaluate the types of chains that occur based on the MAC interactions between different links using realistic propagation and packet forwarding models. We discover that the presence of destructive interactions, due to different forms of hidden terminals, does not impact the throughput of an isolated chain significantly. However, due to the increased number of retransmissions required, the amount of band-width consumed is significantly higher in chains exhibiting destructive interactions, substantially influencing the over-all network performance. These results are validated by testbed experiments. We finally study how different types of chains interfere with each other and discover that well behaved chains in terms of self-interference are more resilient to interference from other chains.

REFERENCES

• 1: Atheros/AR5006chipset.
• 2: MadWifi-Driver.
• 3: Soekris4826.
• 4: V. Bharghavan, A. Demers, S. Shenker, and L. Zhang. MACAW: a media access protocol for wireless LANs. In SIGCOMM, 1994.
• 5: G. Bianchi. Performance analysis of the ieee 802.11 distributed coordination function. IEEE Journal on Selected Areas in Comm., 18(3), 2000.
• 6: J. Bicket, D. Aguayo, S. Biswas, and R. Morris. Architecture and evaluation of an unplanned 802.11b mesh network. In MobiCom, pages 31--42, 2005.
• 7: R. R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin. Throughput analysis in multihop csma packet radio networks. IEEE Trans. on Communication, 1987.
• 8: D. DeCouto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In MobiCom '03, 2003.
• 9: R. Draves, J. Padhye, and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks. In MobiCom, pages 114--128, 2004.
• 10: C. L. Fullmer and J. J. Garcia-Luna-Aceves. Solutions to hidden terminal problems in wireless networks. SIGCOMM Comput. Commun. Rev., 27(4):39--49, 1997.
• 11: M. Garetto, T. Salonidis, and E. W. Knightly. Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks. In IEEE INFOCOM, 2006.
• 12: M. Garetto, J. Shi, and E. W. Knightly. Modeling media access in embedded two-flow topologies of multi-hop wireless networks. In MobiCom '05, 2005.
• 13: S. Gollakota and D. Katabi. Zigzag decoding: combating hidden terminals in wireless networks. SIGCOMM Comput. Commun. Rev., 38(4):159--170, 2008.
• 14: P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot. Optimized link state routing protocol for ad hoc networks. In Proc. IEEE INMIC 2001, pages 62--68, 2001.
• 15: K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu. Impact of interference on multi-hop wireless performance. In MobiCom, 2003.
• 16: J. G. Jetcheva, Y. C. Hu, S. Palchaudhuri, A. K. Saha, and D. B. Johnson. Design and evaluation of a metropolitan area multitier wireless ad hoc network architecture. In Proc. IEEE Workshop on Mobile Computing Systems and Applications, pages 32--43, October 2003.
• 17: D. Johnson, D. Maltz, and Y.-C. Hu. The dynamic source routing protocol for mobile ad hoc networks (DSR). In IETF draft, 2003.
• 18: P. Karn. Maca - a new channel access method for packet radio. In ARRL/CRRL 9th Computer Networking Conference, 1990.
• 19: A. Kochut, A. Vasan, A. U. Shankar, and A. Agrawala. Sniffing out the correct physical layer capture model in 802.11b. In ICNP '04, pages 252--261, 2004.
• 20: S. Lee, B. Bhattacharjee, and S. Banerjee. Efficient geographic routing in multihop wireless networks. In MobiHoc, pages 230--241, 2005.
• 21: J. Li, C. Blake, D. DeCouto, H. Lee, and R. Morris. Capacity of ad hoc wireless networks. In MobiCom, pages 61--69, 2001.
• 22: P. Ng and S. Liew. Throughput analysis of 802.11 multi-hop ad hoc networks. IEEE/ACM Trans. Netw., 15(2):309--322, 2007.
• 23: The network simulator-ns2. http://www.isi.edu/nsnam/ns.
• 24: C. E. Perkins and P. Bhagwat. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. In SIGCOMM, pages 234--244, 1994.
• 25: B. Raman and K. Chebrolu. Experiences in using WiFi for rural internet in India. IEEE Comm. Magazine, pages 104--110, Jan. 2007.
• 26: S. Razak and N. Abu-Ghazaleh. Self-Interference in Multi-hop wireless chains. In Proc. ADHOC-NOW, 2008.
• 27: S. Razak, N. B. Abu-Ghazaleh, and V. Kolar. Modeling of two-flow interactions under sinr model in multi-hop wireless networks. In Proc. LCN, pages 297--304, 2008.
• 28: S. Razak, V. Kolar, and N. Abu-Ghazaleh. Modeling and Analysis of Two-Flow Interactions in Wireless Networks. In Wireless On demand Network Systems and Services, 2008.
• 29: X. Wang and K. Kar. Throughput modelling and fairness issues in csma/ca based ad-hoc networks. In INFOCOM, 2005.
• 30: S. Xu and T. Saadawi. Revealing the problems with 802.11 medium access control protocol in multi-hop wireless ad hoc networks. Comput. Networks, 38(4):531--548, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Experimentation, Measurement, Performance

Keywords:
CSMA, MAC, interference, multihop, wireless