article

PPR: partial packet recovery for wireless networks

Authors:

Hari BalakrishnanAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 37, Issue 4

Pages 409 - 420

https://doi.org/10.1145/1282427.1282426

Published: 27 August 2007 Publication History

Abstract

Bit errors occur in wireless communication when interference or noise overcomes the coded and modulated transmission. Current wireless protocols may use forward error correction (FEC) to correct some small number of bit errors, but generally retransmit the whole packet if the FEC is insufficient. We observe that current wireless mesh network protocols retransmit a number of packets and that most of these retransmissions end up sending bits that have already been received multiple times, wasting network capacity. To overcome this inefficiency, we develop, implement, and evaluate a partial packet recovery (PPR) system.

PPR incorporates two new ideas: (1) SoftPHY, an expanded physical layer (PHY) interface that provides PHY-independent hints to higher layers about the PHY's confidence in each bit it decodes, and (2) a postamble scheme to recover data even when a packet preamble is corrupted and not decodable at the receiver.

Finally, we present PP-ARQ, an asynchronous link-layer ARQ protocol built on PPR that allows a receiver to compactly encode a request for retransmission of only those bits in a packet that are likely in error. Our experimental results from a 31-node Zigbee (802.15.4) testbed that includes Telos motes with 2.4 GHz Chipcon radios and GNU Radio nodes implementing the 802.15.4 standard show that PP-ARQ increases end-to-end capacity by a factor of 2x under moderate load.

References

[1]

Boulder, CO, Nov. 2006.

[2]

Wireless LAN Medium Access Control and Physical Layer Specifications, August 1999. IEEE 802.11 Standard.

[3]

D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris. Link-Level Measurements From an 802.11b Mesh Network. In Proc. ACM SIGCOMM Conf., pages 121--132, Portland, OR, Aug. 2004.

Digital Library

[4]

J.-S. Ahn, S.-W. Hong, and J. Heidemann. An Adaptive FEC Code Control Algorithm for Mobile Wireless Sensor Networks. Journal of Communications and Networks, 7(4):489--499, 2005.

[5]

A. Avudainayagam, J. M. Shea, T. F. Wong, and L. Xin. Reliability Exchange Schemes for Iterative Packet Combining in Distributed Arrays. In Proc. of the IEEE WCNC Conf., volume 2, pages 832--837, Mar. 2003.

[6]

L. Bahl, J. Cocke, F. Jelinek, and J. Raviv. Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate. IEEE Trans. Info. Theory, 20(2):284--287, Mar. 1974.

Digital Library

[7]

D. Barry, E. Lee, and D. Messerschmitt. Digital Communication. Springer, New York, NY, 3rd. edition, 2003.

Digital Library

[8]

C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes. In Proc. of the IEEE ICC Conf., pages 54--83, May 1993.

[9]

J. Bicket. Bit-Rate Selection in Wireless Networks. Master's thesis, Massachusetts Institute of Technology, Feb. 2005.

[10]

S. Biswas and R. Morris. ExOR: Opportunistic Multi-hop Routing for Wireless Networks. In Proc. ACM SIGCOMM Conf., pages 133--144, Philadelphia, PA, Aug. 2005.

Digital Library

[11]

D. Chase. Code Combining: A Maximum-Likelihood Decoding Approach for Combining an Arbitrary Number of Noisy Packets. IEEE Trans. on Comm., 33(5):385--393, May 1985.

[12]

S. Eisenman and A. Campbell. Structuring Contention-Based Channel Access in Wireless Sensor Networks. In Proc. of ACM/IEEE IPSN Conf., pages 226--234, Nashville, TN, Apr. 2006.

Digital Library

[13]

M. Ettus. Ettus Research, LLC. http://www.ettus.com.

[14]

R. Ganti, P. Jayachandran, H. Luo, and T. Abdelzaher. Datalink Streaming in Wireless Sensor Networks. In Proc. of the SenSysConf.{1}, pages 209--222.

Digital Library

[15]

The GNU Radio Project. http://www.gnu.org/software/gnuradio/.

[16]

J. Hagenauer and P. Hoeher. A Viterbi Algorithm with Soft-Decision Outputs and its Applications. In Proc. of the IEEE GLOBECOM Conf., Dallas, TX, Nov. 1989.

[17]

F. Harris. Multirate Signal Processing for Communication Systems. Prentice Hall PTR, Upper Saddle River, NJ, 2004.

Digital Library

[18]

G. Holland, N. Vaidya, and P. Bahl. A Rate-Adaptive MAC Protocol for Multihop Wireless Networks. In Proc. ACM MobiCom Conf., pages 236--251, Rome, Italy, July 2001.

Digital Library

[19]

S. Lin and D. J. Costello. Error Control Coding. Prentice Hall, Upper Saddle River, NJ, 2nd. edition, 2004.

Digital Library

[20]

S. Lin and P. S. Yu. A Hybrid ARQ Scheme with Parity Retransmission for Error Control of Satellite Channels. IEEE Trans.on Comm., 30(7):1701--1719, July 1982.

[21]

D. Mandelbaum. An Adaptive-Feedback Coding Scheme Using Incremental Redundancy (Corresp.). IEEE Trans. on Information Theory, 20(3):388--389, May 1974.

Digital Library

[22]

J. Metzner. Improvements in Block-Retransmission Schemes. IEEE Trans. on Comm., 27(2):524--532, Feb. 1979.

[23]

A. Miu, H. Balakrishnan, and C. E. Koksal. Improving Loss Resilience with Multi-Radio Diversity in Wireless Networks. In Proc. MobiCom Conf., pages 16--30, Cologne, Germany, Aug. 2005.

Digital Library

[24]

K. Mueller and M. Müller. Timing Recovery in Digital Synchronous Data Receivers. IEEE Trans. on Comm., 24(5), May 1976.

[25]

S. Pasupathy. Minimum Shift Keying: A Spectrally-Efficient Modulation. IEEE Communications Magazine, 7(4):14--22, July 1979.

Digital Library

[26]

M. Perrott. The CppSim Behavioral Simulator. http://www-mtl.mit.edu/researchgroups/perrottgroup/tools.html.

[27]

N. B. Priyantha. The Cricket Indoor Location System. PhD thesis, MIT, May 2005.

Digital Library

[28]

B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly. Opportunistic Media Access for Multirate Ad Hoc Networks. In Proc. ACM MobiCom Conf., pages 24--35, Atlanta, GA, Sept. 2002.

Digital Library

[29]

T. Schmid. Personal communication.

[30]

R. Sinha, C. Papadopoulos, and J. Heidemann. Internet Packet Size Distributions: Some Observations. http://netweb.usc.edu/~rsinha/pkt-sizes.

[31]

D. Son, B. Krishnamachari, and J. Heidemann. Experimental Analysis of Concurrent Packet Transmissions in Low-Power Wireless Networks. In Proc. of the SenSys Conf. {1}, pages 237--250.

Digital Library

[32]

K. Srinivasan, P. Dutta, A. Tavakoli, and P. Levis. Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks. Technical Report SING-06-00, Stanford Univ., 2006.

Digital Library

[33]

TI/Chipcon Products CC2420 Data Sheet. http://www.chipcon.com/files/CC2420_Data_Sheet_1_3.pdf.

[34]

K. Whitehouse, A. Woo, F. Jiang, J. Polastre, and D. Culler. Exploiting the Capture Effect for Collision Detection and Recovery. In IEEE EmNets Workshop, Sydney, Australia, May 2005.

Digital Library

[35]

T. F. Wong, L. Xin, and J. M. Shea. Iterative Decoding in a Two-Node Distributed Array. In Proc. of the IEEE MILCOM Conf., volume 2, pages 1320--1324, Oct. 2002.

Cited By

Jiang XLiu SGember-Jacobson ABhagoji ASchmitt PBronzino FFeamster N(2024)NetDiffusion: Network Data Augmentation Through Protocol-Constrained Traffic GenerationProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36390378:1(1-32)Online publication date: 21-Feb-2024
https://dl.acm.org/doi/10.1145/3639037
Yang WCai LShu SPan JSepahi A(2024)MAMS: Mobility-Aware Multipath Scheduler for MPQUICIEEE/ACM Transactions on Networking10.1109/TNET.2024.338226932:4(3237-3252)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3382269
Lun YRinaldi CD’Innocenzo ASantucci F(2024)Co-Designing Wireless Networked Control Systems on IEEE 802.15.4-Based Links Under Wi-Fi InterferenceIEEE Access10.1109/ACCESS.2024.340208212(71157-71183)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3402082
Show More Cited By

Index Terms

PPR: partial packet recovery for wireless networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

PPR: partial packet recovery for wireless networks
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications

Bit errors occur in wireless communication when interference or noise overcomes the coded and modulated transmission. Current wireless protocols may use forward error correction (FEC) to correct some small number of bit errors, but generally retransmit ...
Modeling TCP SACK performance over wireless channels with semi-reliable ARQ/FEC

Providing reliable data communications over wireless channels is a challenging task because time-varying wireless channel characteristics often lead to bit errors. These errors result in loss of IP packets and, consequently, TCP segments encapsulated ...
Performance Improvement in Broadband Networks Using Forward Error Correction for Lost Packet Recovery

In this paper we analyze and provide simulation results for the use of forward error control (FEC) to improve the delay-throughput performance of packetized high-speed networks. The major source of errors in high-speed networks is expected to be buffer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 37, Issue 4

October 2007

420 pages

ISSN:0146-4833

DOI:10.1145/1282427

Issue’s Table of Contents

SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications
August 2007
432 pages
ISBN:9781595937131
DOI:10.1145/1282380
General Chairs:
Jun Murai
Keio University, Japan
,
Kenjiro Cho
IIJ, Japan

Copyright © 2007 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2007

Published in SIGCOMM-CCR Volume 37, Issue 4

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

263
Total Citations
View Citations
1,837
Total Downloads

Downloads (Last 12 months)131
Downloads (Last 6 weeks)17

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang XLiu SGember-Jacobson ABhagoji ASchmitt PBronzino FFeamster N(2024)NetDiffusion: Network Data Augmentation Through Protocol-Constrained Traffic GenerationProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36390378:1(1-32)Online publication date: 21-Feb-2024
https://dl.acm.org/doi/10.1145/3639037
Yang WCai LShu SPan JSepahi A(2024)MAMS: Mobility-Aware Multipath Scheduler for MPQUICIEEE/ACM Transactions on Networking10.1109/TNET.2024.338226932:4(3237-3252)Online publication date: Aug-2024
https://doi.org/10.1109/TNET.2024.3382269
Lun YRinaldi CD’Innocenzo ASantucci F(2024)Co-Designing Wireless Networked Control Systems on IEEE 802.15.4-Based Links Under Wi-Fi InterferenceIEEE Access10.1109/ACCESS.2024.340208212(71157-71183)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3402082
Zhang LLiew S(2023)Reliable Wireless Networking via Soft-Source Information CombiningIEEE Internet of Things Journal10.1109/JIOT.2022.321998010:6(4970-4984)Online publication date: 15-Mar-2023
https://doi.org/10.1109/JIOT.2022.3219980
Liu HLi X(2023)Design of Coding Domain Non-orthogonal Demodulation Based on OFDM SystemLISS 202210.1007/978-981-99-2625-1_21(279-290)Online publication date: 14-Oct-2023
https://doi.org/10.1007/978-981-99-2625-1_21
Hamdan MMahmoud M(2022)Analysis and Challenges in Wireless Networked Control System: A SurveyInternational Journal of Robotics and Control Systems10.31763/ijrcs.v2i3.7312:3(492-522)Online publication date: 16-Aug-2022
https://doi.org/10.31763/ijrcs.v2i3.731
Chen RHuang KGao WGummeson JLee SGao JXing G(2022)AiFiProceedings of the 20th ACM Conference on Embedded Networked Sensor Systems10.1145/3560905.3568537(134-148)Online publication date: 6-Nov-2022
https://dl.acm.org/doi/10.1145/3560905.3568537
Vermeulen TReynders BRosas FVerhelst MPollin S(2021)Performance analysis of in-band collision detection for dense wireless networksEURASIP Journal on Wireless Communications and Networking10.1186/s13638-021-01940-42021:1Online publication date: 8-Apr-2021
https://doi.org/10.1186/s13638-021-01940-4
Jung RLevis P(2021)Receiving Colliding LoRa Packets with Hard Information Iterative Decoding2021 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOBECOM46510.2021.9685208(1-7)Online publication date: 7-Dec-2021
https://dl.acm.org/doi/10.1109/GLOBECOM46510.2021.9685208
Seneviratne CWijesekara PLeung H(2020)Performance Analysis of Distributed Estimation for Data Fusion Using a Statistical Approach in Smart Grid Noisy Wireless Sensor NetworksSensors10.3390/s2002056720:2(567)Online publication date: 20-Jan-2020
https://doi.org/10.3390/s20020567
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents