research-article

Neighbour-Disjoint Multipath for Low-Power and Lossy Networks

Authors:

A. K. M. Mahtab Hossain,

Cormac J. Sreenan,

Rodolfo De Paz AlberolaAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 12, Issue 3

Article No.: 23, Pages 1 - 25

https://doi.org/10.1145/2914792

Published: 29 August 2016 Publication History

Abstract

In this article, we describe a neighbour disjoint multipath (NDM) scheme that is shown to be more resilient amidst node or link failures compared to the two well-known node disjoint and edge disjoint multipath techniques. A centralised NDM was first conceptualised in our initial published work utilising the spatial diversity among multiple paths to ensure robustness against localised poor channel quality or node failures. Here, we further introduce a distributed version of our NDM algorithm adapting to the low-power and lossy network (LLN) characteristics. We implement our distributed NDM algorithm in Contiki OS on top of LOADng—a lightweight On-demand Ad hoc Distance Vector Routing protocol. We compare this implementation's performance with a standard IPv6 Routing Protocol for Low power and Lossy Networks (RPL), and also with basic LOADng, running in the Cooja simulator. Standard performance metrics such as packet delivery ratio, end-to-end latency, overhead and average routing table size are identified for the comparison. The results and observations are provided considering a few different application traffic patterns, which serve to quantify the improvements in robustness arising from NDM. The results are confirmed by experiments using a public sensor network testbed with over 100 nodes.

References

[1]

I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. 2002. Wireless sensor networks: A survey. Comput. Network. 38, 4 (March 2002), 393--422.

Digital Library

[2]

A. Annamalai and Vijay K. Bhargava. 1998. Analysis and optimization of adaptive multicopy transmission ARQ protocols for time-varying channels. IEEE Trans. Commun. 46, 10 (1998), 1356--1368.

[3]

A. Avizienis, J.-C. Laprie, B. Randell, and C. Landwehr. 2004. Basic concepts and taxonomy of dependable and secure computing. IEEE Trans. Depend. Secure Comput. 1, 1 (2004), 11--33.

Digital Library

[4]

Thomas Clausen, Axel Verdiere, Jiazi Yi, Afshin Niktash, Yuichi Igarashi, Hiroki Satoh, Ulrich Herberg, Cedric Lavenu, Thierry Lys, and Justin Dean. 2014. The Lightweight On-demand Ad-hoc Distance-vector Routing Protocol - Next Generation (LOADng). Internet-Draft draft-clausen-lln-loadng-12.

[5]

Contiki OS. 2016. The Open Source Operating System for the Internet of Things. http://www.contiki-os.org/. (2016). Accessed: 25/03/2016.

[6]

Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001. Introduction to Algorithms (2nd ed.). McGraw-Hill Higher Education, New York, NY.

Digital Library

[7]

E. W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1 (Dec. 1959), 269--271.

Digital Library

[8]

D. R. Ford and D. R. Fulkerson. 2010. Flows in Networks. Princeton University Press, Princeton, NJ.

Digital Library

[9]

Deepak Ganesan, Ramesh Govindan, Scott Shenker, and Deborah Estrin. 2001. Highly-resilient, energy-efficient multipath routing in wireless sensor networks. Mobile Comput. Commun. Rev. 5, 4 (2001), 11--25.

Digital Library

[10]

Vlado Handziski, Andreas Köpke, Andreas Willig, and Adam Wolisz. 2006. TWIST: A scalable and reconfigurable testbed for wireless indoor experiments with sensor networks. In Proceedings of the 2nd International Workshop on Multi-hop Ad Hoc Networks: From Theory to Reality (REALMAN’06). New York, 63--70.

Digital Library

[11]

Tian He, J. A. Stankovic, Chenyang Lu, and T. Abdelzaher. 2003. SPEED: A stateless protocol for real-time communication in sensor networks. In Proceedings of the International Conference on Distributed Computing Systems. 46--55.

Digital Library

[12]

W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wireless Commun. 1, 4 (October 2002), 660--670.

Digital Library

[13]

Ulrich Herberg and Thomas Clausen. 2011. A comparative performance study of the routing protocols LOAD and RPL with bi-directional traffic in low-power and lossy networks (LLN). In Proc. of the 8th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks. New York, NY, 73--80.

Digital Library

[14]

A. K. M. M. Hossain, C. J. Sreenan, and S. Fedor. 2014. A neighbour disjoint multipath scheme for fault tolerant wireless sensor networks. In Proc. of IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), 6th International Workshop on Performance Control in Wireless Sensor Networks (PWSN). 308--315.

Digital Library

[15]

C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva. 2003. Directed diffusion for wireless sensor networking. IEEE/ACM Trans. Network. 11, 1 (February 2003), 2--16.

Digital Library

[16]

J. Kulik, W. Heinzelman, and H. Balakrishnan. 2002. Negotiation-based protocols for disseminating information in wireless sensor networks. Wireless Networks 8, 2/3 (May 2002), 169--185.

Digital Library

[17]

Chi-Anh La, Martin Heusse, and Andrzej Duda Grenoble. 2013. Link reversal and reactive routing in low power and lossy networks. In Proc. of IEEE PIMRC. 3386--3390.

[18]

S. Lindsey and C. S. Raghavendra. 2002. PEGASIS: Power-efficient gathering in sensor information system. Proc. IEEE Aerospace Conf. 3 (March 2002), 1125--1130.

[19]

J. Martocci, P. D. Mil, N. Riou, and W. Vermeylen. 2010. Building Automation Routing Requirements in Low-Power and Lossy Networks. IETF RFC 5867. (2010).

[20]

G. Montenegro, N. Kushalnagar, J. Hui, and D. Culler. 2007. Transmission of IPv6 Packets over IEEE 802.15.4 Networks. IETF RFC 4944. (September 2007).

[21]

Maimour Moufida. 2008. Maximally radio-disjoint multipath routing for wireless multimedia sensor networks. In Proc. of the 4th ACM WMuNeP. 26--31.

Digital Library

[22]

B. Nath and D. Niculescu. 2003. Routing on a curve. ACM SIGCOMM Comput. Commun. Rev. 33, 1 (2003), 155--160.

Digital Library

[23]

M. Patil and R. C. Biradar. 2012. A survey on routing protocols in wireless sensor networks. In Proceedings of the 18th IEEE International Conference on Networks (ICON). 86--91.

[24]

Charles E. Perkins and Elizabeth M. Royer. 1999. Ad-hoc on-demand distance vector routing. In Proc. of the 2nd IEEE Workshop on Mobile Computing Systems and Applications. 90--100.

Digital Library

[25]

Marjan Radi, Behnam Dezfouli, Kamalrulnizam Abu Bakar, and Malrey Lee. 2012. Multipath routing in wireless sensor networks: Survey and research challenges. Sensors 12, 1 (2012), 650--685.

[26]

T. S. Rappaport. 2001. Wireless Communications: Principles and Practice, 2nd Edition. Prentice Hall, Upper Saddle River, NJ.

Digital Library

[27]

Siuli Roy, Somprakash Bandyopadhyay, Tetsuro Ueda, and Kazuo Hasuike. 2002. Multipath routing in ad hoc wireless networks with omni directional and directional antenna: A comparative study. In Distributed Computing. Lecture Notes in Computer Science, Vol. 2571. 184--191.

Digital Library

[28]

Kewei Sha, Jegnesh Gehlot, and Robert Greve. 2013. Multipath routing techniques in wireless sensor networks: A survey. Wireless Pers. Commun. 70, 2 (2013), 807--829.

Digital Library

[29]

Lanny Sitanayah, Kenneth N. Brown, and Cormac J. Sreenan. 2014. A fault-tolerant relay placement algorithm for ensuring k vertex-disjoint shortest paths in wireless sensor networks. Ad Hoc Networks 23 (2014), 145--162.

Digital Library

[30]

K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie. 2000. Protocols for self-organization of a wireless sensor network. IEEE Pers. Commun. 7, 5 (October 2000), 16--27.

[31]

Jenn-Yue Teo, Yajun Ha, and Chen-Khong Tham. 2008. Interference-minimized multipath routing with congestion control in wireless sensor network for high-rate streaming. IEEE TMC 7, 9 (Sept 2008), 1124--1137.

Digital Library

[32]

NS-3. 2016. A discrete-event network simulator. http://www.nsnam.org. (2016). Accessed: 25/03/2016

[33]

J. W. Tsai and T. Moors. 2007. Interference-aware multipath selection for reliable routing in wireless mesh networks. In Proc. of IEEE MASS. 1--6.

[34]

Nicolas Tsiftes, Joakim Eriksson, Niclas Finne, Fredrik Österlind, Joel Höglund, and Adam Dunkels. 2010. A framework for low-power IPv6 routing simulation, experimentation, and evaluation. SIGCOMM Comput. Commun. Rev. 40, 4 (2010), 479--480.

Digital Library

[35]

M. Vučinić, B. Tourancheau, and A. Duda. 2013. Performance comparison of the RPL and LOADng routing protocols in a home automation scenario. In Proc. of IEEE WCNC. 1974--1979.

[36]

A. Willig. 2005. Redundancy concepts to increase transmission reliability in wireless industrial LANs. IEEE Trans. Industr. Inform. 1, 3 (2005), 173--182.

[37]

T. Winter, P. Thubert, A. Brandt, J. Hui, R. Kelsey, P. Levis, K. Pister, R. Struik, J. Vasseur, and R. Alexander. 2012. RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks. IETF RFC 6550. (March 2012).

[38]

Kui Wu and Janelle Harms. 2001. Performance study of a multipath routing method for wireless mobile ad hoc networks. In Proc. of MASCOTS. 99--107.

Digital Library

[39]

Jiazi Yi, T. Clausen, and Y. Igarashi. 2013. Evaluation of routing protocol for low power and lossy networks: LOADng and RPL. In Proc. of IEEE Conference on Wireless Sensor (ICWISE). 19--24.

[40]

Y. Yu, R. Govindan, and D. Estrin. 2001. Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks. Technical Report UCLA/CSD-TR-01-0023. UCLA Computer Science Department.

Cited By

Kertiou ILaouid ASaber BHammoudeh MAlshaikh M(2023)A P2P multi-path routing algorithm based on Skyline operator for data aggregation in IoMT environmentsPeerJ Computer Science10.7717/peerj-cs.16829(e1682)Online publication date: 22-Nov-2023
https://doi.org/10.7717/peerj-cs.1682
Lydia EJovith ADevaraj ASeo CJoshi G(2021)Green Energy Efficient Routing with Deep Learning Based Anomaly Detection for Internet of Things (IoT) CommunicationsMathematics10.3390/math90505009:5(500)Online publication date: 1-Mar-2021
https://doi.org/10.3390/math9050500
Jemili IGhrab DBelghith AMosbah MAl-Ahmadi S(2021)Cross-layer multipath approach for critical traffic in duty-cycled wireless sensor networksJournal of Network and Computer Applications10.1016/j.jnca.2021.103154191(103154)Online publication date: Oct-2021
https://doi.org/10.1016/j.jnca.2021.103154
Show More Cited By

Index Terms

Neighbour-Disjoint Multipath for Low-Power and Lossy Networks
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Redundancy
  2. Embedded and cyber-physical systems
    1. Sensor networks
2. Networks
  1. Network algorithms
  2. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

Proactive versus reactive routing in low power and lossy networks: Performance analysis and scalability improvements

In this paper, the classical debate on suitability of proactive versus reactive routing approaches is revisited, however in the context of their application in Low-Power Lossy Networks (LLNs) as opposed to pure Mobile Ad Hoc Networks (MANETs). We argue ...
A reliable node-disjoint multipath routing with low overhead in wireless ad hoc networks
MSWiM '04: Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems

Wireless ad hoc networks are characterized by the use of wireless links with limited bandwidth, dynamically varying network topology and multi-hop connectivity. AODV and DSR are the two most widely studied on-demand ad hoc routing protocols. Previous ...
A Routing ID-based Node-disjoint Multipath Scheme for Ad Hoc Networks
UIC-ATC '12: Proceedings of the 2012 9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing

In ad hoc networks, many single-path-based routing methods have been proposed. With the single-path-based method, when route breakages occur, it is necessary to repair the route in each route break. As a countermeasures this, multipath routing methods ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 12, Issue 3

August 2016

304 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/2976745

Editor:
Chenyang Lu
Department of Computer Science and Engineering / School of Engineering and Applied Sciences / Washington University / 1 Brookings Drive / St. Louis, MO

Issue’s Table of Contents

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

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 29 August 2016

Accepted: 01 April 2016

Revised: 01 March 2016

Received: 01 September 2015

Published in TOSN Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Irish Research Council and United Technologies Research Center Ireland Ltd

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
216
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kertiou ILaouid ASaber BHammoudeh MAlshaikh M(2023)A P2P multi-path routing algorithm based on Skyline operator for data aggregation in IoMT environmentsPeerJ Computer Science10.7717/peerj-cs.16829(e1682)Online publication date: 22-Nov-2023
https://doi.org/10.7717/peerj-cs.1682
Lydia EJovith ADevaraj ASeo CJoshi G(2021)Green Energy Efficient Routing with Deep Learning Based Anomaly Detection for Internet of Things (IoT) CommunicationsMathematics10.3390/math90505009:5(500)Online publication date: 1-Mar-2021
https://doi.org/10.3390/math9050500
Jemili IGhrab DBelghith AMosbah MAl-Ahmadi S(2021)Cross-layer multipath approach for critical traffic in duty-cycled wireless sensor networksJournal of Network and Computer Applications10.1016/j.jnca.2021.103154191(103154)Online publication date: Oct-2021
https://doi.org/10.1016/j.jnca.2021.103154
Maimour M(2020)Interference-aware metrics impact on the performance of incremental multipath routing in WSNsJournal of High Speed Networks10.3233/JHS-20064026:3(225-240)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.3233/JHS-200640
Sobral JRodrigues JRabêlo RAl-Muhtadi JKorotaev V(2019)Routing Protocols for Low Power and Lossy Networks in Internet of Things ApplicationsSensors10.3390/s1909214419:9(2144)Online publication date: 9-May-2019
https://doi.org/10.3390/s19092144
Sobral JRodrigues JRabêlo RSaleem KFurtado V(2019)LOADng-IoT: An Enhanced Routing Protocol for Internet of Things Applications over Low Power NetworksSensors10.3390/s1901015019:1(150)Online publication date: 3-Jan-2019
https://doi.org/10.3390/s19010150
Sasidharan DJacob L(2018)Improving network lifetime and reliability for machine type communications based on LOADng routing protocolAd Hoc Networks10.1016/j.adhoc.2018.02.00773:C(27-39)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1016/j.adhoc.2018.02.007
Zhu LWang RYang H(2017)Multi-Path Data Distribution Mechanism Based on RPL for Energy Consumption and Time DelayInformation10.3390/info80401248:4(124)Online publication date: 9-Oct-2017
https://doi.org/10.3390/info8040124

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 Article

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