Circular pipelining: Minimizing round-trip delay in low-duty-cycle wireless networks

Jia Li, Song Min Kim, Tian He

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

In wireless networks, duty-cycling operations have been widely used to reduce the energy cost of RF idle listening at wireless receivers. Such operations, however, introduce delays in data forwarding because a sender has to wait for a targeted receiver to wake up. To reduce end-to-end delivery delays, researchers have proposed scheduling techniques [1], [2], [3] to wake up nodes along the data forwarding path at the right moment. However, these techniques consider only one-way delivery from a sink to nodes (or vice versa), failing to optimally support round-trip network operations such as (i) query and response, (ii) command and control and (iii) data fetching. In this work, we interestingly reveal that the optimal roundtrip delay in a low-duty-cycle network depends only on (i) duty cycle period and (ii) the number of 2-connected network components between the source and destination nodes. We prove that optimality in the round-trip delay can be achieved by establishing a simple circular path and its related cords, in which nodes are assigned wake-up slots in an ascending order in each network component, and connecting these paths into a circular pipeline. We compared our Circular Pipelining (CP) algorithm with the state-of-art solutions [3], and the experimental results show that without using circular forwarding, existing solutions have a round-trip delay proportional to the network diameter, while CP remains a minimal constant delay of T as long as the network is 2-connected. We also implement the Circular Pipelining (CP) algorithm in a test bed consisting of 30 MICAz nodes, achieving significant delay reduction compared to three baseline solutions in the literature.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 22nd International
PublisherIEEE Computer Society
Pages421-432
Number of pages12
ISBN (Electronic)9781479962044
DOIs
StatePublished - Dec 9 2014
Event22nd IEEE International Conference on Network Protocols, ICNP 2014 - Research Triangle, United States
Duration: Oct 21 2014Oct 24 2014

Publication series

NameProceedings - International Conference on Network Protocols, ICNP
ISSN (Print)1092-1648

Other

Other22nd IEEE International Conference on Network Protocols, ICNP 2014
CountryUnited States
CityResearch Triangle
Period10/21/1410/24/14

Fingerprint Dive into the research topics of 'Circular pipelining: Minimizing round-trip delay in low-duty-cycle wireless networks'. Together they form a unique fingerprint.

  • Cite this

    Li, J., Kim, S. M., & He, T. (2014). Circular pipelining: Minimizing round-trip delay in low-duty-cycle wireless networks. In Proceedings - IEEE 22nd International (pp. 421-432). [6980404] (Proceedings - International Conference on Network Protocols, ICNP). IEEE Computer Society. https://doi.org/10.1109/ICNP.2014.65