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

research-article

Taming uncertainties in real-time routing for wireless networked sensing and control

Authors:

Xi JuAuthors Info & Claims

MobiHoc '12: Proceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing

Pages 75 - 84

https://doi.org/10.1145/2248371.2248385

Published: 11 June 2012 Publication History

Abstract

Real-time routing is a basic element of closed-loop, real-time sensing and control, but it is challenging due to dynamic, uncertain link/path delays. The probabilistic nature of link/path delays makes the basic problem of computing the probabilistic distribution of path delays NP-hard, yet quantifying probabilistic path delays is a basic element of real-time routing and may well have to be executed by resource-constrained devices in a distributed manner; the highly-varying nature of link/path delays makes it necessary to adapt to in-situ delay conditions in real-time routing, but it has been observed that delay-based routing can lead to instability, estimation error, and low data delivery performance in general. To address these challenges, we propose the Multi-Timescale Estimation (MTE) method; by accurately estimating the mean and variance of per-packet transmission time and by adapting to fast-varying queueing in an accurate, agile manner, MTE enables accurate, agile, and efficient estimation of probabilistic path delay bounds in a distributed manner. Based on MTE, we propose the Multi-Timescale Adaptation (MTA) routing protocol; MTA integrates the stability of an ETX-based directed-acyclic-graph (DAG) with the agility of spatiotemporal data flow control within the DAG to ensure real-time data delivery in the presence of dynamics and uncertainties. We also address the challenges of implementing MTE and MTA in resource-constrained devices such as TelosB motes. We evaluate the performance of MTA using the NetEye and Indriya sensor network testbeds. We find that MTA significantly outperforms existing protocols, e.g., improving deadline success ratio by 89% and reducing transmission cost by a factor of 9.7.

References

[1]

An event traffic trace for sensor networks. http://www.cs.wayne.edu/~hzhang/group/ publications/Lites-trace.txt.

[2]

Indriya testbed. http://indriya.comp.nus.edu.sg/.

[3]

IEEE 802.15 smart utility networks task group 4g. http://www.ieee802.org/15/pub/TG4g.html.

[4]

IEEE 802.15.4e Working Group. http://www.ieee802.org/15/pub/TG4e.html.

[5]

NetEye testbed. http://neteye.cs.wayne.edu/neteye/home.php, 2008.

[6]

S. Bapat, V. Kulathumani, and A. Arora. Analyzing the yield of exscal, a large-scale wireless sensor network experiment. In IEEE ICNP, pages 53--62, 2005.

Digital Library

[7]

S. Biswas and R. Morris. ExOR: Opportunistic multi-hop routing for wireless networks. In ACM SIGCOMM, 2005.

Digital Library

[8]

M. Caesar, M. Casado, T. Koponen, J. Rexford, and S. Shenker. Dynamic route computation considered harmful. ACM SIGCOMM Computer Communication Review, 40(2), 2010.

Digital Library

[9]

A. Chakrabarti and G. Manimaran. Reliability constrained routing in QoS networks. IEEE/ACM Transactions on Networking, 13(3):662--675, 2005.

Digital Library

[10]

S. Chakrabarti and A. Mishra. QoS issues in ad hoc wireless networks. IEEE Communications Magazine, pages 142--148, February 2001.

Digital Library

[11]

L. Chen and W. B. Heinzelman. QoS-aware routing based on bandwidth estimation for mobile ad hoc networks. IEEE JSAC, 23(3):561--571, 2005.

Digital Library

[12]

S. Chen, M. Song, and S. Sahni. Two techniques for fast computation of constrained shortest paths. IEEE/ACM Transactions on Networking, 16(1), February 2008.

Digital Library

[13]

O. Chipara, Z. He, G. Xing, Q. Chen, X. Wang, C. Lu, J. Stankovic, and T. Abdelzaher. Real-time power-aware routing in sensor networks. In IWQoS, 2006.

[14]

D. S. J. D. Couto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In ACM MobiCom, 2003.

Digital Library

[15]

R. Draves, J. Padhye, and B. Zill. Comparison of routing metrics for static multi-hop wireless networks. In ACM SIGCOMM, 2004.

Digital Library

[16]

R. Draves, J. Padhye, and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks. In ACM MobiCom, 2004.

Digital Library

[17]

S. C. Ergen and P. Varaiya. Energy efficient routing with delay guarantee for sensor networks. Wireless Networks, 13(5), 2007.

Digital Library

[18]

M. Erol-Kantarci and H. T. Mouftah. Wireless sensor networks for cost-efficient residential energy management in the smart grid. IEEE Transactions on Smart Grid, 2(2):314--325, 2011.

[19]

Y. P. Fallah, C. Huang, R. Sengupta, and H. Krishnan. Design of cooperative vehicle safety systems based on tight coupling of communication, computing and physical vehicle dynamics. In ACM/IEEE ICCPS, 2010.

Digital Library

[20]

X. Fang, D. Yang, P. Gundecha, and G. Xue. Multi-constrained anypath routing in wireless mesh networks. In IEEE SECON, 2010.

[21]

E. Felemban, C.-G. Lee, E. Ekici, R. Boder, and S. Vural. Probabilistic QoS guarantee in reliability and timeliness domains in wireless sensor networks. In IEEE INFOCOM, 2005.

[22]

O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis. Collection tree protocol. In ACM SenSys, 2009.

Digital Library

[23]

R. A. Guerin and A. Orda. QoS routing in networks with inaccurate information: Theory and algorithms. IEEE/ACM Transactions on Networking, 7(3):350--364, 1999.

Digital Library

[24]

T. He, J. Stankovic, C. Lu, and T. Abdelzaher. SPEED: A stateless protocol for real-time communication in sensor networks. In IEEE ICDCS, 2003.

Digital Library

[25]

J. Hellerstein, Y. Diao, S. Parekh, and D. M. Tilbury. Feedback Control of Computing Systems. Wiley-IEEE Press, 2004.

Digital Library

[26]

B. Hobijn, P. H. Franses, and M. Ooms. Generalizations of the KPSS-test for stationarity. Statistica Neerlandica, 58(4):483--502, 2004.

[27]

X. Huang and Y. Fang. Multiconstrained QoS multipath routing in wireless sensor networks. Wireless Networks, 14:465--478, 2008.

Digital Library

[28]

IETF. Routing over low power and lossy networks (ROLL) working group. http://www.ietf.org/html. charters/roll-charter.html.

[29]

R. Jain and I. Chlamtac. The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations. Communications of the ACM, 28(10), 1985.

Digital Library

[30]

S. Kandula, D. Katabi, B. Davie, and A. Charny. Walking the tightrope: Responsive yet stable traffic engineering. In ACM SIGCOMM, 2005.

Digital Library

[31]

T. Korkmaz and M. Krunz. Bandwidth-delay constrained path selection under inaccurate state information. IEEE/ACM Transactions on Networking, 11(3), 2003.

Digital Library

[32]

A. LaJoie. Wireless sensors enjoy timely role in factory automation. Industrial Ethernet Book, April 2010.

[33]

H. Li, Y. Cheng, and C. Zhou. Minimizing end-to-end delay: A novel routing metric for multi-radio wireless mesh networks. In IEEE INFOCOM, 2009.

[34]

S. Lin, G. Zhou, K. Whitehouse, Y. Wu, J. A. Stankovic, and T. He. Towards stable network performance in wireless sensor networks. In IEEE RTSS, 2009.

Digital Library

[35]

X. Liu, H. Zhang, and Q. Xiang. Towards predictable real-time routing for wireless networked sensing and control. In CPS Week RealWin workshop, 2011.

[36]

X. Liu, H. Zhang, Q. Xiang, X. Che, and X. Ju. Taming uncertainties in real-time routing for wireless networked sensing and control. Technical Report DNC-TR-11-04 (https://sites.google.com/site/dnctrs/ DNC-TR-11-04.pdf),Wayne State University, 2011.

[37]

M. Loeve. Probability Theory. Springer-Verlag, 1977.

[38]

J. R. Moyne and D. M. Tilbury. Control and communication challenges in networked real-time systems. Proceedings of the IEEE, 95(1), 2007.

[39]

S. Munir, S. Lin, E. Hoque, S. M. S. Nirjon, J. A. Stankovic, and K. Whitehouse. Addressing burstiness for reliable communication and latency bound generation in wireless sensor networks. In IEEE/ACM IPSN, 2010.

Digital Library

[40]

S. M. Ross. Introduction to Probability Models. Academic Press, 2006.

Digital Library

[41]

ISA SP100.11a. http://www.isa.org//MSTemplate.cfm? MicrositeID=1134\&CommitteeID=6891.

[42]

H.-M. Tsai, C. Saraydar, T. Talty, M. Ames, A. Macdonald, and O. K. Tonguz. Zigbee-based intra-car wireless sensor network. In IEEE ICC, 2007.

[43]

J. V. Uspensky. Introduction to Mathematical Probability. McGraw-Hill Book Company Inc., 1937.

[44]

W. Wang, Y. Xu, and M. Khanna. A survey on the communication architectures in smart grid. Computer Networks, 55:3604--3629, 2011.

Digital Library

[45]

A. Willig. Recent and emerging topics in wireless industrial communications: A selection. IEEE Transactions on Industrial Informatics, 4(2), May 2008.

[46]

WirelessHART. http://www.hartcomm2.org/hart_protocol/ wireless_hart/wireless_hart_main.html.

[47]

Y. Xue, B. Ramamurthy, and M. C. Vuran. SDRCS: A service-differentiated real-time communication scheme for event sensing in wireless sensor networks. Computer Networks, 55:3287--3302, 2011.

Digital Library

[48]

S. Yin, Y. Xiong, Q. Zhang, and X. Lin. Traffic-aware routing for real-time communications in wireless multi-hop networks. Wireless Communications and Mobile Computing, 6:825--843, 2006.

Digital Library

[49]

F. R. Yu, P. Zhang, W. Xiao, and P. Choudhury. Communication systems for grid integration of renewable energy resources. IEEE Network, pages 22--29, September/October 2011.

Digital Library

[50]

H. Zhang, A. Arora, Y. ri Choi, and M. Gouda. Reliable bursty convergecast in wireless sensor networks. Computer Communications (Elsevier), Special Issue on Sensor-Actuator Networks, 30(13), 2007.

Digital Library

[51]

H. Zhang, A. Arora, and P. Sinha. Link estimation and routing in sensor network backbones: Beacon-based or data-driven? IEEE Transactions on Mobile Computing, 8(5), May 2009.

Digital Library

[52]

H. Zhang, L. Sang, and A. Arora. On biased link sampling in data-driven link estimation and routing in low-power wireless networks. ACM Transactions on Autonomous and Adaptive Systems, 4(3), July 2009.

Digital Library

[53]

H. Zhang, L. Sang, and A. Arora. Comparison of data-drive link estimation methods in low-power wireless networks. IEEE Transactions on Mobile Computing, 9(11), November 2010

Digital Library

Cited By

Cheng LKong LSong YNiu JLuo CGu YMumtaz SHe T(2020)Adaptive Forwarding With Probabilistic Delay Guarantee in Low-Duty-Cycle WSNsIEEE Transactions on Wireless Communications10.1109/TWC.2020.298730819:7(4775-4792)Online publication date: Jul-2020
https://doi.org/10.1109/TWC.2020.2987308
(2016)BibliographyCommunications for Control in Cyber Physical Systems10.1016/B978-0-12-801950-4.09997-2(277-285)Online publication date: 2016
https://doi.org/10.1016/B978-0-12-801950-4.09997-2
Li H(2016)Introduction to cyber physical systemsCommunications for Control in Cyber Physical Systems10.1016/B978-0-12-801950-4.00001-9(1-8)Online publication date: 2016
https://doi.org/10.1016/B978-0-12-801950-4.00001-9
Show More Cited By

Index Terms

Taming uncertainties in real-time routing for wireless networked sensing and control
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

Real-time routing in wireless sensor networks: A potential field approach

Wireless Sensor Networks (WSNs) are embracing an increasing number of real-time applications subject to strict delay constraints. Utilizing the methodology of potential field in physics, in this article we effectively address the challenges of real-time ...
A Novel Real-Time Routing Protocol for Wireless Sensor Networks
SNPD '09: Proceedings of the 2009 10th ACIS International Conference on Software Engineering, Artificial Intelligences, Networking and Parallel/Distributed Computing

In recent years, many routing protocols for wireless sensor networks (WSNs) have been designed to achieve high energy-efficiency, high reliability, low overhead, etc. However, few routing protocols for WSNs were designed to minimize the communication ...
Opportunistic real-time routing in multi-hop wireless sensor networks
SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing

Wireless sensor networks (WSNs) are subject to significant resource constraints. Particularly, routing protocols for low-rate WSNs suffer from maintaining routing metrics and stable links of paths. Even though opportunistic routing protocols are well-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '12: Proceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing

June 2012

280 pages

ISBN:9781450312813

DOI:10.1145/2248371

General Chair:
Asis Nasipuri
University of North Carolina at Charlotte, USA
,
Program Chairs:
Yih-Chun Hu
University of Illinois at Urbana-Champaign, USA
,
Sanjay Shakkottai
University of Texas at Austin, USA

Copyright © 2012 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

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc '12

Sponsor:

SIGMOBILE

MobiHoc '12: The Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing

June 11 - 14, 2012

South Carolina, Hilton Head, USA

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
285
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng LKong LSong YNiu JLuo CGu YMumtaz SHe T(2020)Adaptive Forwarding With Probabilistic Delay Guarantee in Low-Duty-Cycle WSNsIEEE Transactions on Wireless Communications10.1109/TWC.2020.298730819:7(4775-4792)Online publication date: Jul-2020
https://doi.org/10.1109/TWC.2020.2987308
(2016)BibliographyCommunications for Control in Cyber Physical Systems10.1016/B978-0-12-801950-4.09997-2(277-285)Online publication date: 2016
https://doi.org/10.1016/B978-0-12-801950-4.09997-2
Li H(2016)Introduction to cyber physical systemsCommunications for Control in Cyber Physical Systems10.1016/B978-0-12-801950-4.00001-9(1-8)Online publication date: 2016
https://doi.org/10.1016/B978-0-12-801950-4.00001-9
Bi RLi JGao HChen Q(2015)Deadline aware retransmission threshold setting protocol in Cyber-Physical SystemsInternational Journal of Distributed Sensor Networks10.1155/2015/2712592015(25-25)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1155/2015/271259
Lin SZhou GAl-Hami MWhitehouse KWu YStankovic JHe TWu XLiu H(2015)Toward Stable Network Performance in Wireless Sensor Networks: A Multilevel PerspectiveACM Transactions on Sensor Networks10.1145/270027211:3(1-26)Online publication date: 17-Feb-2015
https://dl.acm.org/doi/10.1145/2700272
Cheng LNiu JGu YHe TZhang Q(2015)Energy-efficient statistical delay guarantee for duty-cycled wireless sensor networks2015 12th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)10.1109/SAHCN.2015.7338290(46-54)Online publication date: Jun-2015
https://doi.org/10.1109/SAHCN.2015.7338290
Zhang HLiu XLi CChen YChe XLin FWang LYin G(2015)Scheduling with predictable link reliability for wireless networked control2015 IEEE 23rd International Symposium on Quality of Service (IWQoS)10.1109/IWQoS.2015.7404753(339-348)Online publication date: Jun-2015
https://doi.org/10.1109/IWQoS.2015.7404753
Li HDimitrovski ASong JHan ZQian L(2014)Communication Infrastructure Design in Cyber Physical Systems with Applications in Smart Grids: A Hybrid System FrameworkIEEE Communications Surveys & Tutorials10.1109/SURV.2014.052914.0013016:3(1689-1708)Online publication date: Nov-2015
https://doi.org/10.1109/SURV.2014.052914.00130

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 Table of Contents