Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Wireless Personal Communications
Published in: Wireless Personal Communications 1/2016

01-07-2016

A Multipath Prefix Routing for Wireless Sensor Networks

Authors: Moufida Maimour, Zahia Bidai

Published in: Wireless Personal Communications | Issue 1/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

When a spanning tree is built on top of a wireless network and an appropriate labelling scheme is applied, the complexity of the routing mechanism in terms of memory usage and control messages can be drastically reduced using compact routing. In this paper, we propose multipath prefix routing (MPR), a multipath routing protocol for wireless sensor networks. MPR is a hybrid (both reactive and proactive) protocol that operates on an already built spanning tree rooted at the sink (the collect station). Besides the tree path, additional paths are built based on an appropriate labelling scheme and neighbourhood relationships. For practical implementation, we propose and evaluate two different labelling schemes. We mainly show that in a perfect W-ary tree, the additional number of bits required to encode labels is at most \((H-1)\) where H is the height of the tree. Finally, we apply MPR to the ZigBee standard and evaluate its performance using simulations. MPR has a small state routing while control messages overhead is maintained low compared to traditional multipath routing protocols.
previous article A Novel Multi-Server Authentication Scheme for e-commerce Applications Using Smart Card
next article On the Performance of Opportunistic Relay Selection in Cognitive Radio Networks with Primary User’s Interference and Direct Channel

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
This assumption is a necessary condition to be able to use reverse paths.
 
2
paths in trees are unique. If we assume that another path exists, this would lead to a cycle in T which is in contradiction to tree definition.
 
3
The case \(R=1\) is not considered since it does not allow building multiple disjoint paths: at least the last link is common.
 
Literature
1.
Perkins, C., Royer, E., & Das, S. (1999). Ad hoc on demand distance vector (aodv) routing.
2.
Clausen, T., & Jacquet, P. (2003). Optimized link state routing protocol (olsr). IETF RFC 3626.
3.
Johnson, D. B., Maltz, D. A., & Broch, J. (2001). DSR: The dynamic source routing protocol for multi-hop wireless ad hoc networks, chap. 5 (pp. 139–172). Addison-Wesley.
4.
Karp, B., & Kung, H. T. (2000). GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th annual international conference on mobile computing and networking, MobiCom ’00 (pp. 243–254). New York, NY, USA: ACM.
5.
van Leeuwen, J., & Tan, R. B. (1995). Compact routing methods: A survey. In Department of Computer Science, Utrecht University (pp. 99–109). University Press.
6.
7.
van Leeuwen, J., & Tan, R. B. (1983). Routing with compact routing tables. Technical report RUU-CS-83-16, Department of Computer Science, University of Utrecht, Utrecht.
8.
Afsar, M. M., & Tayarani-N, M. H. (2014). Clustering in sensor networks: A literature survey. Journal of Network and Computer Applications, 46, 198–226.CrossRef
9.
Maimour, M., Zeghilet, H., & Lepage, F. (2010). Sustainable wireless sensor networks, chap. Cluster-based routing protocols for energy-efciency in wireless sensor networks (pp. 167–188). Intech.
10.
Banerjee, S., & Khuller, S. (2001). A clustering scheme for hierarchical control in multi-hop wireless networks. In INFOCOM 2001. Twentieth annual joint conference of the IEEE computer and communications societies. Proceedings. IEEE (vol. 2, pp. 1028–1037).
11.
Bakker, E. M., van Leeuwen, J., & Tan, R. B. (1993). Prefix routing schemes in dynamic networks. Computer Networks and ISDN Systems, 26(4), 403–421.CrossRefMATH
12.
Yu, Y., Estrin, D., & Govindan, R. (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.
13.
Sarkar, R., Zhu, X., & Gao, J. (2013). Distributed and compact routing using spatial distributions in wireless sensor networks. ACM Transactions on Sensor Networks (TOSN), 9(3), 32.CrossRef
14.
Mao, Y., Wang, F., Qiu, L., Lam, S. S., & Smith, J. M. (2007). S4: Small state and small stretch routing protocol for large wireless sensor networks. In USENIX NSDI. Cambridge, MA, USA.
15.
Thorup, M., & Zwick, U. (2001). Compact routing schemes. In Proceedings of the thirteenth annual ACM symposium on parallel algorithms and architectures (pp. 1–10). ACM.
16.
Iwanicki, K., & Steen, M. V. (2007). On hierarchical routing in wireless sensor networks. In IPSN (pp. 133–144).
17.
Ganesan, D., Govindan, R., Shenker, S., & Estrin, D. (2001). Highly-resilient, energy-efficient multipath routing in wireless sensor networks. ACM SIGMOBILE mobile computing and communications review, 5(4), 11–25.CrossRef
18.
Hou, X., Tipper, D., & Kabara, J. (2004). Label-based multipath routing (lmr) in wireless sensor routing. In Proceedings of the 6th international symposium on advanced radio technologies (ISART 04). Boulder, CO.
19.
Deb, B., Bhatnagar, S., & Nath, B. (2003). Reinform: Reliable information forwarding using multiple paths in sensor networks. In Proceedings of 28th annual IEEE international conference on local computer networks (pp. 406–415). Bonn, Germany.
20.
Zhong, F. Y. G. (2005). Gradient broadcast: A robust data delivery protocol for large scale sensor networks. ACM Wireless Networks (WINET 11, pp. 285–298).
21.
Maimour, M. (2008). Maximally radio-disjoint multipath routing for wireless multimedia sensor networks. In Proceedings of the 4th ACM workshop on wireless multimedia networking and performance modeling colocated with MSWIM’08. Vancouver, Canada.
22.
Huang, X., & Fang, Y. (2005). End-to-end delay differentiation by prioritized multipath routing in wireless sensor networks. In Military communications conference (MILCOM) (pp. 1277–1283). Atlantic City.
23.
Lee, S., & Gerla, M. (2001). Split multipath routing with maximally disjoint paths in ad hoc networks. In IEEE ICC (vol. 10, pp. 3201–3205).
24.
Lu, Y. M., & Wong, V. W. (2006). An energy-efficient multipath routing protocol for wireless sensor networks. Wiley international journal of communication systems, special issue on energy-efficient networks protocols and algorithms for wireless sensor networks.
25.
Ming Lu, Y., & WS Wong, V. (2007). An energy-efficient multipath routing protocol for wireless sensor networks: Research articles. International Journal of Communication Systems, 20(7), 747–766.CrossRef
26.
Lou, W. (2005). An efficient n-to-1 multipath routing protocol in wireless sensor networks. In IEEE international conference on mobile adhoc and sensor systems conference (pp. 672–679). IEEE, Washington, DC.
27.
Kim, T., Kim, D., Park, N., Yoo, S. E., & Lopez, T. (2007). Shortcut tree routing in zigbee networks. In Wireless pervasive computing, 2007. ISWPC ’07. 2nd international symposium on (2007).
28.
Subasri, M., & Ramesh, R. (2015). Neighbor table based shortcut tree routing in zigbee wireless networks. International Journal of Advances in Engineering, 1(3), 367–372.
29.
Ha, J., Park, H., Choi, S., & Kwon, W. (2007). EHRP: Enhanced hierarchical routing protocol for zigbee mesh networks. IEEE Communications Letters, 11, 1028–1030.CrossRef
30.
Tsai, C. H., Pan, M. S., Lu, Y. C., & Tseng, Y. C. (2009). Self-learning routing for zigbee wireless mesh networks. In IEEE Asia-Pacific wireless communications symposium (APWCS).
31.
Qiu, W., Skafidas, E., & Hao, P. (2009). Enhanced tree routing for wireless sensor networks. Ad hoc networks, 7(3), 638–650.CrossRef
32.
Bidai, Z., Haffaf, H., & Maimour, M. (2011). Node disjoint multi-path routing for zigbee cluster-tree wireless sensor networks. In International conference on multimedia computing and systems (ICMCS) (pp. 1–6).
33.
Bidai, Z., Maimour, M., & Haffaf, H. (2012). Multipath extension of the zigbee tree routing in cluster-tree wireless sensor networks. International Journal of Mobile Computing and Multimedia Communications, 4(2), 30–48.CrossRef
34.
Zigbee alliance. (July 2004). zigbee document 02130r9: Network specification.
35.
Bhatti, G., & Yue, G. (2007). A structured addressing scheme for wireless multi-hop networks. Cambridge, MA: Mitsubishi Electric Research Labs.
36.
Mohsin, M., & Prakash, R. (2002). IP address assignment in a mobile ad hoc network. In Proceedings of Milicom (vol. 2, pp. 856–861).
37.
Wu, J., & Sheng, L. (1999). Deadlock-free routing in irregular networks using prefix routing. In In Proceedings of parallel and distributed computing systems (pp. 424–430).
38.
IEEE standard for local and metropolitan area networks—part 15.4: Low-rate wireless personal area networks (LR-WPANs). IEEE Std 802.15.4-2011 (Revision of IEEE Std 802.15.4-2006) (pp. 1–314) (2011).
39.
Nefzi, B., & Song, Y. Q. (2007). Performance Analysis and improvement of ZigBee routing protocol. In 7th IFAC international conference on fieldbuses & networks in industrial & embedded systems—FeT’2007. Toulouse France.
40.
Wu, J., & Sheng, L. (1999). Deadlock-free routing in irregular networks using prefix routing. In ISCA 12th international conference on parallel and distributed computing systems (pp. 424–430).
41.
42.
43.
Bidai, Z., Kechar, B., & Haffaf, H. (2008). Node disjoint multipath routing protocol supporting quality of service in wireless sensor networks. In Proceedings of international conference on web information technologies (ICWIT’08) (pp. 281–286). Sidi Bel Abbes, Algeria (June 29–30 2008).
44.
Metadata
Title
A Multipath Prefix Routing for Wireless Sensor Networks
Authors
Moufida Maimour
Zahia Bidai
Publication date
01-07-2016
Publisher
Springer US
Published in
Wireless Personal Communications / Issue 1/2016
Print ISSN: 0929-6212
Electronic ISSN: 1572-834X
DOI
https://doi.org/10.1007/s11277-016-3463-x

Other articles of this Issue 1/2016

Wireless Personal Communications 1/2016 Go to the issue

OriginalPaper

Synchronization Algorithm for STBC MIMO-OFDM System at Low SNR

OriginalPaper

A Printed Semi-Circular Disc UWB MIMO/Diversity Antenna with Cross Shape Slot Stub

OriginalPaper

Adaptive Resource Allocation for Scalable Video Transmission over OFDMA Systems

OriginalPaper

On the Performance of Opportunistic Relay Selection in Cognitive Radio Networks with Primary User’s Interference and Direct Channel

OriginalPaper

Performance Analysis of CoMP in Ultra-Dense Networks with Limited Backhaul Capacity

OriginalPaper

An Efficient Practical MIMO–OFDM Scheme with Coded Modulation Diversity for Future Wireless Communications