More Web Proxy on the site http://driver.im/

research-article

Free access

Zigzag decoding: combating hidden terminals in wireless networks

Authors:

Shyamnath Gollakota,

Dina KatabiAuthors Info & Claims

SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 conference on Data communication

Pages 159 - 170

https://doi.org/10.1145/1402958.1402977

Published: 17 August 2008 Publication History

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.

Digital Library

[5]

V. Bharghavan, A. J. Demers, S. Shenker, and L. Zhang. MACAW: A Media Access Protocol for Wireless LAN's. In ACM SIGCOMM 1994.

Digital Library

[6]

D. G. Brennan. On the Maximal Signal-to-Noise Ratio Realizable from Several Noisy Signals. Proc. IRE, 43:1530, October 1955.

[7]

P. Castoldi. Multiuser Detection in CDMA Mobile Terminals. Artech house Publishers, 2002.

Digital Library

[8]

Y.-C. Cheng, J. Bellardo, P. Benk, A. C. Snoeren, G. M. Voelker, and S. Savage. Jigsaw: solving the puzzle of enterprise 802.11 analysis. In SIGCOMM, 2006.

Digital Library

[9]

G. FSF. GNU Radio - GNU FSF Project.

[10]

C. L. Fullmer and J. J. Garcia-Luna-Aceves. Solutions to Hidden Terminal Problems in Wireless Networks. In SIGCOMM, pages 39--49, 1997.

Digital Library

[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.

Digital Library

[13]

R. Gummadi, D. Wetherall, B. Greenstein, and S. Seshan. Understanding and Mitigating the Impact of RF Interference on 802.11 Networks. In SIGCOMM, 2007.

Digital Library

[14]

D. Halperin, J. Ammer, T. Anderson, and D. Wetherall. Interference Cancellation: Better Receivers for a New Wireless MAC. In Hotnets, 2007.

[15]

D. Halperin, T. Anderson, and D.Wetherall. Practical interference cancellation for wireless lans. In Proc. of ACM MOBICOM 2008.

Digital Library

[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.

Digital Library

[17]

E. Inc. Universal software radio peripheral. http://ettus.com.

[18]

G. Judd and P. Steenkiste. Using Emulation to Understand and Improve Wireless Networks and Applications. In NSDI, 2005.

Digital Library

[19]

P. Karn. MACA-A New Channel Access Method for packet Radio. 9th Computer Networking Conf., 1990.

[20]

S. Katti, S. Gollakota, and D. Katabi. Embracing Wireless Interference: Analog Network Coding. In ACM SIGCOMM, 2007.

Digital Library

[21]

S. Khurana, A. Kahol, and A. P. Jayasumana. Effect of Hidden Terminals on the Performance of IEEE 802.11 MAC Protocol, 1998.

Digital Library

[22]

E. A. Lee and D. G. Messerschmitt. Digital Communications. Boston: Kluwer Academic, 1988.

[23]

J. Lee, W. Kim, S.-J. Lee, D. Jo, J. Ryu, T. Kwon, and Y. Choi. An Experimental Study on the Capture Effect in 802.11a Networks, 2007.

Digital Library

[24]

H. Meyr, M. Moeneclaey, and S. A. Fechtel. Digital Communication Receivers: Synchronization, Channel Estimation, and Signal Processing. John Wiley & Sons, 1998.

Digital Library

[25]

A. Muqattash and M. Krunz. CDMA-Based MAC Protocol for Wireless Ad Hoc Networks. In ACM MOBIHOC, 2003.

Digital Library

[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]

C. Reis, R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Measurement-Based Models of Delivery and Interference. In SIGCOMM, 2006.

Digital Library

[28]

J. K. Tan. An Adaptive Orthogonal Frequency Division Multiplexing Baseband Modem for Wideband Wireless Channels. Master's thesis, MIT, 2006.

[29]

D. Tse and P. Vishwanath. Fundamentals of Wireless Communications. Cambridge University Press, 2005.

Digital Library

[30]

D. Tse, P. Viswanath, and L. Zheng. Diversity-Multiplexing Tradeoff in Multiple Access Channels.

[31]

IEEE Transaction on Information Theory, 2004.

[32]

S. Verdu. Multiuser Detection. Cambridge University Press, 1998.

Digital Library

[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]

G. Woo, P. Kheradpour, and D. Katabi. Beyond the Bits: Cooperative Packet Recovery Using PHY Information. In ACM MobiCom, 2007.

Digital Library

[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.

Cited By

Zhao YZhang YLau FYu HZhu ZZhang B(2024)Expanding-Window Zigzag Decodable Fountain Codes for Scalable Multimedia TransmissionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/3664610Online publication date: 11-May-2024
https://doi.org/10.1145/3664610
Jiang JWang JChen YTong SXie PLiu YLiu YOkoshi TKo JLiKamWa R(2024)Willow: Practical WiFi Backscatter Localization with Parallel TagsProceedings of the 22nd Annual International Conference on Mobile Systems, Applications and Services10.1145/3643832.3661853(265-277)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3643832.3661853
Dai MHuang RWang JLi B(2024)Low overhead vector codes with combination property and zigzag decoding for edge‐aided computing in UAV networkComputational Intelligence10.1111/coin.1264240:3Online publication date: 6-Jun-2024
https://doi.org/10.1111/coin.12642
Show More Cited By

Index Terms

Zigzag decoding: combating hidden terminals in wireless networks
1. Networks
  1. Network protocols

Recommendations

Zigzag decoding: combating hidden terminals in wireless networks

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 ...
An iterative zigzag decoding for combating collisions in wireless networks

Business and entertainment increasingly depend on WLANs, as they provide flexibility of locations and low maintenance efforts. However in the presence of hidden terminals sender-receiver pairs experience severe packet loss due to collisions. ZigZag ...
Throughput Improvement of IEEE802.11DCF with Adaptive RTS/CTS Control on the Basis of Existence of Hidden Terminals
CISIS '11: Proceedings of the 2011 International Conference on Complex, Intelligent, and Software Intensive Systems

IEEE802.11 RTS/CTS handshake to avoid a packet collision with the transmissions from hidden terminals. Although RTS/CTS handshake effectively reduces packet collisions with hidden terminals, it also increases transmission overhead of IEEE802.11. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 conference on Data communication

August 2008

452 pages

ISBN:9781605581750

DOI:10.1145/1402958

General Chairs:
Victor Bahl
Microsoft Research
,
David Wetherall
Intel Research & University of Washington
,
Program Chairs:
Stefan Savage
University of California, San Diego
,
Ion Stoica
University of California, Berkeley

ACM SIGCOMM Computer Communication Review Volume 38, Issue 4
October 2008
436 pages
ISSN:0146-4833
DOI:10.1145/1402946
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM '08

Sponsor:

SIGCOMM '08: ACM SIGCOMM 2008 Conference

August 17 - 22, 2008

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

529
Total Citations
View Citations
2,908
Total Downloads

Downloads (Last 12 months)240
Downloads (Last 6 weeks)41

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao YZhang YLau FYu HZhu ZZhang B(2024)Expanding-Window Zigzag Decodable Fountain Codes for Scalable Multimedia TransmissionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/3664610Online publication date: 11-May-2024
https://doi.org/10.1145/3664610
Jiang JWang JChen YTong SXie PLiu YLiu YOkoshi TKo JLiKamWa R(2024)Willow: Practical WiFi Backscatter Localization with Parallel TagsProceedings of the 22nd Annual International Conference on Mobile Systems, Applications and Services10.1145/3643832.3661853(265-277)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3643832.3661853
Dai MHuang RWang JLi B(2024)Low overhead vector codes with combination property and zigzag decoding for edge‐aided computing in UAV networkComputational Intelligence10.1111/coin.1264240:3Online publication date: 6-Jun-2024
https://doi.org/10.1111/coin.12642
Dai MZhang ZZheng ZZhang ZLin XWang H(2024)2D-SAZD: A Novel 2D Coded Distributed Computing Framework for Matrix-Matrix MultiplicationIEEE Transactions on Services Computing10.1109/TSC.2024.339593117:3(705-717)Online publication date: May-2024
https://doi.org/10.1109/TSC.2024.3395931
Cong RZhao ZZhang LMin G(2024)Cost-Effective Server Deployment for Multi-Access Edge Networks: A Cooperative SchemeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.342652335:9(1583-1597)Online publication date: Sep-2024
https://doi.org/10.1109/TPDS.2024.3426523
Chiang YLin YChang CHong Y(2024)Throughput Analysis for Parallel Decoding of Irregular Repetition Slotted ALOHA With NoiseIEEE/ACM Transactions on Networking10.1109/TNET.2024.339296032:4(3544-3558)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3392960
You LTang ZWang PWang ZDai HFu L(2024)Quick and Reliable LoRa Data Aggregation Through Multi-Packet ReceptionIEEE/ACM Transactions on Networking10.1109/TNET.2023.332301832:2(1616-1630)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3323018
Wang JTong SXu ZXie P(2024)Real-Time Concurrent LoRa Transmissions Based on Peak TrackingIEEE Transactions on Mobile Computing10.1109/TMC.2024.336579723:10(9582-9594)Online publication date: Oct-2024
https://doi.org/10.1109/TMC.2024.3365797
Chen JShen YWan Sung C(2024)A New Shift-Add Secret Sharing Scheme for Partial Data Protection With Parallel Zigzag DecodingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.348849819(10221-10232)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3488498
Liu YWang HCai LHu JShen X(2024)Longevity-Oriented and Reliable Forwarding Percolation Routing in Underwater Acoustic Sensor NetworksIEEE Internet of Things Journal10.1109/JIOT.2023.332971511:6(11031-11045)Online publication date: 15-Mar-2024
https://doi.org/10.1109/JIOT.2023.3329715
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents