Abstract
Wireless sensor networks are formed by small sensor nodes communicating over wireless links without using a fixed network infrastructure. Sensor nodes have a limited transmission range, and their processing and storage capabilities as well as their energy resources are also limited. Routing protocols for wireless sensor networks have to ensure reliable multi-hop communication under these conditions. We describe design challenges for routing protocols in sensor networks and illustrate the key techniques to achieve desired characteristics, such as energy efficiency and delivery guarantees. We give a survey of state-of-the-art routing techniques with a focus on geographic routing, a paradigm that enables a reactive message-efficient routing without prior route discovery or knowledge of the network topology. Different geographic routing strategies are described as well as beaconless routing techniques. We also show the physical layer impact on routing and outline further research directions.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
S. Ramanathan and Martha Steenstrup. A survey of routing techniques for mobile communications networks. Mobile Networks and Applications, 1(2):89–104, 1996.
Elizabeth M. Royer and Chai-Koeng Toh. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Personal Communications, 6(2):46–55, April 1999.
Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Proceedings of the 4th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom’98), pages 85–97, 1998.
Kemal Akkaya and Mohamed Younis. A survey on routing protocols for wireless sensor networks. Ad hoc Networks, 3(3):325–349, May 2005.
I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: a survey. Computer Networks, 38:393–422, 2002.
Jeffrey Hightower and Gaetano Borriella. Location systems for ubiquitous computing. IEEE Computer, 34(8):57–66, 2001.
Srdjan Capkun, Maher Hamdi, and Jean-Pierre Hubaux. GPS-free positioning in mobile ad-hoc networks. In Proceedings of the Hawaii International Conference on System Sciences (HICSS’01), 2001.
Ivan Stojmenovic. Location updates for efficient routing in ad hoc networks. In Ivan Stojmenovic, editor, Handbook of Wireless Networks and Mobile Computing, Chapter 21, pages 451–471. Wiley, 2002.
Ivan Stojmenovic and Stephan Olariu. Data-centric protocols for wireless sensor networks. In Handbook of Sensor Networks, Chapter 13, pages 417–456. Wiley, 2005.
Christopher Ho, Katia Obraczka, Gene Tsudik, and Kumar Viswanath. Flooding for reliable multicast in multi-hop ad hoc networks. In Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M’99), pages 64–71, 1999.
Ivan Stojmenovic and Xu Lin. Loop-free hybrid single-path ∕ flooding routing algorithms with guaranteed delivery for wireless networks. IEEE Transactions on Parallel and Distributed Systems, 12(10):1023–1032, October 2001.
Hideaki Takagi and Leonard Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246–257, March 1984.
Gregory G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI ∕ RR-87-180, Information Sciences Institute (ISI), March 1987.
Ting-Chao Hou and Victor O.K. Li. Transmission range control in multihop packet radio networks. IEEE Transactions on Communications, 34(1):38–44, January 1986.
Ivan Stojmenovic and Xu Lin. Power-aware localized routing in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 12(11):1122–1133, November 2001.
Randolph Nelson and Leonard Kleinrock. The spatial capacity of a slotted aloha multihop packet radio network with capture. IEEE Transactions on Communications, 32(6):684–694, June 1984.
Evangelos Kranakis, Harvinder Singh, and Jorge Urrutia. Compass routing on geometric networks. In Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG’99), pages 51–54, August 1999.
Xu Lin and Ivan Stojmenovic. Location-based localized alternate, disjoint and multi-path routing algorithms for wireless networks. Journal of Parallel and Distributed Computing, 63:22–32, 2003.
Stefano Basagni, Imrich Chlamtac, Violet R. Syrotiuk, and Barry A. Woodward. A distance routing effect algorithm for mobility (DREAM). In Proceedings of the 4th Annual ACM∕ IEEE International Conference on Mobile Computing and Networking (MOBICOM-98), pages 76–84, October 1998.
Young-Bae Ko and Nitin H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks. In Proceedings of the 4th Annual ACM∕IEEE International Conference on Mobile Computing and Networking (MOBICOM-98), pages 66–75, October 1998.
Ivan Stojmenovic, Anand Prakash Ruhil, and D. K. Lobiyal. Voronoi diagram and convex hull based geocasting and routing in wireless networks. In Proceedings of the 8th IEEE Symposium on Computers and Communications ISCC, pages 51–56, July 2003.
Johnson Kuruvila, Amiya Nayak, and Ivan Stojmenovic. Progress and location based localized power aware routing for ad hoc and sensor wireless networks. International Journal of Distributed Sensor Networks, 2(2):147–159, July 2006.
Prosenjit Bose, Pat Morin, Ivan Stojmenovic, and Jorge Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the 3rd ACM International Workshop on discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M’99), pages 48–55, August 1999.
Brad Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th ACM∕IEEE Annual International Conference on Mobile Computing and Networking (MobiCom’00), pages 243–254, August 2000.
K.R. Gabriel and R.R. Sokal. A new statistical approach to geographic variation analysis. Applied Zoology, 18:259–278, 1969.
G.T. Touissaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12:261–268, 1980.
Prosenjit Bose, Luc Devroye, William Evans, and David Kirkpatrick. On the spanning ratio of gabriel graphs and beta-skeletons. In Proceedings of the Latin American Theoretical Informatics (LATIN’02), April 2002.
J.M. Keil and C.A. Gutwin. Classes of graphs which approximate the complete euclidean graph. Discrete and Computational Geometry, 7:13–28, 1992.
Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, and An Zhu. Geometric spanner for routing in mobile networks. In Proceedings of the second ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’01), pages 45–55, October 2001.
Xiang-Yang Li, Gruia Calinescu, and Peng-Jun Wan. Distributed construction of a planar spanner and routing for ad hoc wireless networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM), pages 1268–1277, June 2002.
Xiang-Yang Li and Yu Wang. Quality guaranteed localized routing for wireless ad hoc networks. In IEEE ICDCS 2003 (MWN workshop), 2003.
Xiang-Yang Li, Ivan Stojmenovic, and Yu Wang. Partial delaunay triangulation and degree limited localized bluetooth scatternet formation. IEEE Transactions on Parallel and Distributed Systems, 15(4):350–361, 2004.
Susanta Datta, Ivan Stojmenovic, and Jie Wu. Internal node and shortcut based routing with guaranteed delivery in wireless networks. In Proceedings of the IEEE International Conference on Distributed Computing and Systems (Wireless Networks and Mobile Computing Workshop WNMC), pages 461–466, April 2001.
Jie Wu and Hailan Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks. In Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL M ’99), pages 7–14, August 1999.
Ivan Stojmenovic, Mahtab Seddigh, and Jovisa Zunic. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 13(1):14–25, January 2002.
Ivan Stojmenovic and Susanta Datta. Power and cost aware localized routing with guaranteed delivery in wireless networks. In Proceedings of the Seventh International Symposium on Computers and Communications (ISCC’02), pages 31–36, July 2002.
Jie Wu, Fei Dai, Ming Gao, and Ivan Stojmenovic. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. Journal of Communications and Networks, 4(1), March 2002.
Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. Worst-case optimal and average-case efficient geometric ad-hoc routing. In Proceedings of the 4th ACM International Symposium on Mobile Computing and Networking (MobiHoc 2003), pages 267–278, 2003.
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, and Aaron Zollinger. Geometric ad-hoc routing: Of theory and practice. In Proceedings of the 22nd ACM International Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, pages 63–72, July 2003.
Marc Heissenbüttel and Torsten Braun. BLR: Beacon-less routing algorithm for mobile ad-hoc networks. Elsevier’s Computer Communications Journal, pages 1076–1086, 2003.
Holger Füßler, Jörg Widmer, Michael Käsemann, Martin Mauve, and Hannes Hartenstein. Contention-based forwarding for mobile ad-hoc networks. Ad Hoc Networks, 1(4):351–369, November 2003.
Brian M. Blum, Tian He, Sang Son, and John A. Stankovic. IGF: A state-free robust communication protocol for wireless sensor networks. Technical Report CS-2003-11, Department of Computer Science, University of Virginia, April 21 2003.
H. Kalosha, A. Nayak, S. Rührup, and I. Stojmenovic. Select-and-protest-based beaconless georouting with guaranteed delivery in wireless sensor networks. In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), April 2008.
Wendi Rabiner Heinzelman, Joanna Kulik, and Hari Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks. In Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking (MobiCom’99), pages 174–185, 1999.
Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, and Fabio Silva. Directed diffusion for wireless sensor networking. IEEE/ACM Transactions on Networking, 11(1):2–16, 2003.
Narayanan Sadagopan, Bhaskar Krishnamachari, and Ahmed Helmy. Active query forwarding in sensor networks. Ad Hoc Networks, 3(1):91–113, January 2005.
Lali Barriere, Pierre Fraigniaud, Lata Narajanan, and Jaroslav Opatrny. Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In Proceedings of the fifth ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M’01), pages 19–27, 2001.
Karim Seada, Ahmed Helmy, and Ramesh Govindan. On the effect of localization errors on geographic face routing in sensor networks. Technical Report 03-797, University of Southern California USC, 2003.
David Braginsky and Deborah Estrin. Rumor routing algorthim for sensor networks. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications (WSNA’02), pages 22–31, 2002.
X.Y. Li, K. Moaveninejad, and W.Z. Song. Robust position-based routing for wireless ad hoc networks. Ad Hoc Networks, 3(5):546–559, September 2005.
Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. Ad-hoc networks beyond unit disk graphs. In Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pages 69–78, September 2003.
Ivan Stojmenovic, Amiya Nayak, and Johnson Kuruvila. Design guidelines for routing protocols in ad hoc and sensor networks with a realistic physical layer. IEEE Communications Magazine, 43(3):101–106, 2005.
Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A high-throughput path metric for multi-hop wireless routing. Wireless Networks, 11(4):419–434, 2005.
Karim Seada, Marco Zuniga, Ahmed Helmy, and Bhaskar Krishnamachari. Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys’04), pages 108–121, 2004.
Johnson Kuruvila, Amiya Nayak, and Ivan Stojmenovic. Hop count optimal position-based packet routing algorithms for ad hoc wireless networks with a realistic physical layer. IEEE Journal on Selected Areas in Communications, 23(6):1267–1275, 2005.
Johnson Kuruvila, Amiya Nayak, and Ivan Stojmenovic. Greedy localized routing for maximizing probability of delivery in wireless ad hoc networks with a realistic physical layer. Journal of Parallel and Distributed Computing, 66:499–506, 2006.
A. Rao, S. Rathasamy, C. Papadimitriou, S. Shenker, and I. Stoica. Geographic routing without location information. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom’03), pages 96–108, 2003.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag London Limited
About this chapter
Cite this chapter
Frey, H., Rührup, S., Stojmenović, I. (2009). Routing in Wireless Sensor Networks. In: Misra, S., Woungang, I., Misra, S. (eds) Guide to Wireless Sensor Networks. Computer Communications and Networks. Springer, London. https://doi.org/10.1007/978-1-84882-218-4_4
Download citation
DOI: https://doi.org/10.1007/978-1-84882-218-4_4
Published:
Publisher Name: Springer, London
Print ISBN: 978-1-84882-217-7
Online ISBN: 978-1-84882-218-4
eBook Packages: Computer ScienceComputer Science (R0)