Zigzag decoding: combating hidden terminals in wireless networks

ABSTRACT

This paper presents ZigZag, an 802.11 receiver design that combats hidden terminals. ZigZag's core contribution is a new form of interference cancellation that exploits asynchrony across successive collisions. Specifically, 802.11 retransmissions, in the case of hidden terminals, cause successive collisions. These collisions have different interference-free stretches at their start, which ZigZag exploits to bootstrap its decoding.

ZigZag makes no changes to the 802.11 MAC and introduces no overhead when there are no collisions. But, when senders collide, ZigZag attains the same throughput as if the colliding packets were a priori scheduled in separate time slots. We build a prototype of ZigZag in GNU Radio. In a testbed of 14 USRP nodes, ZigZag reduces the average packet loss rate at hidden terminals from 72.6% to about 0.7%.

REFERENCES

• 1: Broadcom Wireless LAN Adapter User Guide.
• 2: Reference Manual for the NETGEAR ProSafe 802.11g Wireless AP WG102.
• 3: ISL3873: Wireless LAN Integrated Medium Access Controller with Baseband Processor, 2000.
• 4: J. Andrews. Interference cancellation for cellular systems: A contemporary overview. IEEE Wireless Communications, 2005.
• 5: 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
• 6: D. G. Brennan. On the Maximal Signal-to-Noise Ratio Realizable from Several Noisy Signals. Proc. IRE, 43:1530, October 1955.
• 7: Piero Castoldi, Multiuser Detection in CDMA Mobile Terminals, Artech House, Inc., Norwood, MA, 2002
• 8: Yu-Chung Cheng , John Bellardo , Péter Benkö , Alex C. Snoeren , Geoffrey M. Voelker , Stefan Savage, Jigsaw: solving the puzzle of enterprise 802.11 analysis, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 9: G. FSF. GNU Radio - GNU FSF Project.
• 10: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, Solutions to hidden terminal problems in wireless networks, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.39-49, September 14-18, 1997, Cannes, France
• 11: R. G. Gallager. A Perspective on Multiaccess Channels. IEEE Transactions on Information Theory, IT-31(2), march 1985.
• 12: S. Gollakota and D. Katabi. Zigzag decoding: Combating hidden terminals in wireless networks. Technical Report MIT-CSAIL-TR-2008-018, MIT, 2008.
• 13: Ramakrishna Gummadi , David Wetherall , Ben Greenstein , Srinivasan Seshan, Understanding and mitigating the impact of RF interference on 802.11 networks, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 14: D. Halperin, J. Ammer, T. Anderson, and D. Wetherall. Interference Cancellation: Better Receivers for a New Wireless MAC. In Hotnets, 2007.
• 15: Daniel Halperin , Thomas Anderson , David Wetherall, Taking the sting out of carrier sense: interference cancellation for wireless LANs, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409983]
• 16: J. Hou, J. Smee, H. D. Pfister, and S. Tomasin. Implementing Interference Cancellation to Increase the EV-DO Rev A Reverse Link Capacity. IEEE Communication Magazine, February 2006.
• 17: E. Inc. Universal software radio peripheral. http://ettus.com.
• 18: Glenn Judd , Peter Steenkiste, Using emulation to understand and improve wireless networks and applications, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.203-216, May 02-04, 2005
• 19: P. Karn. MACA-A New Channel Access Method for packet Radio. 9th Computer Networking Conf., 1990.
• 20: Sachin Katti , Shyamnath Gollakota , Dina Katabi, Embracing wireless interference: analog network coding, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 21: Sumit Khurana , Anurag Kahol , Anura P. Jayasumana, Effect of Hidden Terminals on the Performance of IEEE 802.11 MAC Protocol, Proceedings of the 23rd Annual IEEE Conference on Local Computer Networks, p.12, October 11-14, 1998
• 22: E. A. Lee and D. G. Messerschmitt. Digital Communications. Boston: Kluwer Academic, 1988.
• 23: Jeongkeun Lee , Wonho Kim , Sung-Ju Lee , Daehyung Jo , Jiho Ryu , Taekyoung Kwon , Yanghee Choi, An experimental study on the capture effect in 802.11a networks, Proceedings of the the second ACM international workshop on Wireless network testbeds, experimental evaluation and characterization, September 10-10, 2007, Montreal, Quebec, Canada [doi>10.1145/1287767.1287772]
• 24: Heinrich Meyr , Marc Moeneclaey , Stefan Fechtel, Digital Communication Receivers: Synchronization, Channel Estimation, and Signal Processing, John Wiley & Sons, Inc., New York, NY, 1997
• 25: Alaa Muqattash , Marwan Krunz, CDMA-based MAC protocol for wireless ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778434]
• 26: P. C. Ng, S. C. Liew, K. C. Sha, and W. T. To. Experimental Study of Hidden node Problem in IEEE 802.11 Wireless Networks. In Sigcomm Poster, 2005.
• 27: Charles Reis , Ratul Mahajan , Maya Rodrig , David Wetherall , John Zahorjan, Measurement-based models of delivery and interference in static wireless networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 28: J. K. Tan. An Adaptive Orthogonal Frequency Division Multiplexing Baseband Modem for Wideband Wireless Channels. Master's thesis, MIT, 2006.
• 29: David Tse , Pramod Viswanath, Fundamentals of wireless communication, Cambridge University Press, New York, NY, 2005
• 30: D. Tse, P. Viswanath, and L. Zheng. Diversity-Multiplexing Tradeoff in Multiple Access Channels.
• 31: IEEE Transaction on Information Theory, 2004.
• 32: Sergio Verdu, Multiuser Detection, Cambridge University Press, New York, NY, 1998
• 33: A. J. Viterbi. Very Low Rate Convolutional Codes for Maximum Theoretical Performance of Spread-Spectrum Multiple-Access Channels. IEEE JSAC, May 1990.
• 34: C. Ware, J. Judge, J. Chicharo, and E. Dutkiewicz. Unfairness and capture behaviour in 802.11 adhoc networks. volume 1, pages 159--163 vol.1, 2000.
• 35: I. . WG. Wireless lan medium access control (mac) and physical layer (phy) specifications. Standard Specification,IEEE, 1999.
• 36: Grace R. Woo , Pouya Kheradpour , Dawei Shen , Dina Katabi, Beyond the bits: cooperative packet recovery using physical layer information, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287871]
• 37: K. Xu, M. Gerla, , and S. Bae. Effectiveness of RTS/CTS Handshake in IEEE 802.11 Based Ad Hoc Networks. In Ad Hoc Network Journal, 2003.
• 38: J. Zhu, X. Guo, S. Roy, and K. Papagiannaki. CSMA Self-Adaptation based on Interference Differentiation. In IEEE Globecom, 2007.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
hidden terminals, interference cancellation, wireless