research-article

Practical 3D geographic routing for wireless sensor networks

Authors:

Pratibha Sundar SundaramoorthyAuthors Info & Claims

SenSys '10: Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems

Pages 337 - 350

https://doi.org/10.1145/1869983.1870016

Published: 03 November 2010 Publication History

Abstract

Geographic routing is of interest for sensor networks because a point-to-point primitive is an important building block for data-centric applications. While there is a significant body of work on geographic routing algorithms for two-dimensional (2D) networks, geographic routing for practical three-dimensional (3D) sensor networks is relatively unexplored. We show that existing 2D geographic routing algorithms like CLDP/GPSR and GDSTR perform poorly in practical 3D sensor network deployments and describe GDSTR-3D, a new 3D geographic routing algorithm that uses 2-hop neighbor information in greedy forwarding and 2D convex hulls to aggregate node location information. We compare GDSTR-3D to existing algorithms, including CLDP/GPSR, GDSTR, AODV, VRR and S4, both in a real wireless sensor testbed and with TOSSIM simulations to show that GDSTR-3D is highly scalable, requires only a modest amount of storage and achieves routing stretch close to 1.

References

[1]

P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks, 7(6):609--616, 2001.

Digital Library

[2]

M. Caesar, M. Castro, and E. B. Nightingale. Virtual ring routing: network routing inspired by DHTs. In Proceedings of ACM SIGCOMM 2006, pages 351--362. ACM Press, 2006.

Digital Library

[3]

M. Doddavenkatappa, A. L. Ananda, and M. C. Chan. INDRIYA: A wireless sensor network testbed, 2009. http://indriya.ddns.comp.nus.edu.sg.

[4]

S. Durocher, D. Kirkpatrick, and L. Narayanan. On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Wireless Networks, 16(1):227--235, 2010.

Digital Library

[5]

R. Flury and R. Wattenhofer. Randomized 3D geographic routing. In Proceedings of the IEEE INFOCOMM 2008, 2008.

[6]

R. Fonseca, S. Ratnasamy, J. Zhao, C. T. Ee, D. Culler, S. Shenker, and I. Stoica. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In Proceedings of NSDI 2005, May 2005.

Digital Library

[7]

P. S. Geoffrey Werner-Allen and M. Welsh. Motelab: A wireless sensor network testbed. In Proceedings of IPSN 2005, 2005.

Digital Library

[8]

R. Govindan. Data-centric routing and storage in sensor networks. Wireless sensor networks, pages 185--205, 2004.

Digital Library

[9]

V. Handziski, A. Köpke, A. Willig, and A. Wolisz. TWIST: a scalable and reconfigurable testbed for wireless indoor experiments with sensor networks. In Proceedings of REALMAN '06, pages 63--70, New York, NY, USA, 2006. ACM.

Digital Library

[10]

B. Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In Proceedings of Mobicom 2000, pages 243--254, Boston, MA, August 2000.

Digital Library

[11]

Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker. Geographic routing made practical. In Proceedings of NSDI 2005, May 2005.

Digital Library

[12]

Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker. On the pitfalls of geographic face routing. In Proceedings of DIAL-M-POMC 2005, September 2005.

Digital Library

[13]

Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker. Lazy cross-link removal for geographic routing. In Proceedings of SenSys 2006, November 2006.

Digital Library

[14]

E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proceedings of the 11th Canadian Conference on Computational Geometry, pages 51--54, Vancouver, August 1999.

[15]

F. Kuhn, R. Wattenhofer, and A. Zollinger. Worst-case optimal and average-case efficient geometric ad-hoc routing. In Proceedings of MobiHoc 2003, June 2003.

Digital Library

[16]

S. S. Lam and C. Qian. Geographic routing with low stretch in d-dimensional spaces. Technical report, The University of Texas at Austin, January 2010.

[17]

B. Leong, B. Liskov, and R. Morris. Geographic routing without planarization. In Proceedings of NSDI 2006, May 2006.

Digital Library

[18]

B. Leong, S. Mitra, and B. Liskov. Path vector face routing: Geographic routing with local face information. In Proceedings of ICNP 2005, November 2005.

Digital Library

[19]

C. Liu and J. Wu. Efficient geometric routing in three dimensional ad hoc networks. In Proceedings of INFOCOM 2009, April 2009.

[20]

Y. Mao, F. Wang, L. Qiu, S. S. Lam, and J. M. Smith. S4: Small state and small stretch routing protocol for large wireless sensor networks. In Proceedings of NSDI 2007, April 2007.

Digital Library

[21]

J. Newsome and D. Song. GEM: Graph embedding for routing and data-centric storage in sensor networks without geographic information. In Proceedings of SenSys 2003, November 2003.

Digital Library

[22]

C. Perkins. Ad-hoc on-demand distance vector routing. In Proceedings of IEEE MILCOM 1997, November 1997.

[23]

C. Qing and A. Tarek. A scalable logical coordinates framework for routing in wireless sensor networks. In Proceedings of RTSS 2004, pages 349--358, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[24]

S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu. Data-centric storage in sensornets with ght, a geographic hash table. Mobile Networks and Applications (MONET), Journal of Special Issues on Mobility of Systems, Users, Data, and Computing, 2003.

Digital Library

[25]

S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker. GHT: A geographic hash table for data-centric storage in sensornets. In Proceedings of WSNA 2002, September 2002.

Digital Library

[26]

K. Seada, A. Helmy, and R. Govindan. On the effect of localization errors on geographic face routing in sensor networks. In Proceedings of IPSN 2004, pages 71--80, 2004.

Digital Library

[27]

TelosB. TelosB datasheet. web. http://www.xbow.com.

[28]

J. Zhou, Y. Chen, B. Leong, and B. Feng. Practical virtual coordinates for large wireless sensor networks. In Proceedings of ICNP 2010, October 2010.

Digital Library

Cited By

R. MM. J(2024)Comprehensive Study on Routing in FANETIntelligent Decision Making Through Bio-Inspired Optimization10.4018/979-8-3693-2073-0.ch011(195-217)Online publication date: 24-May-2024
https://doi.org/10.4018/979-8-3693-2073-0.ch011
Ahmed MFuger KKuladinithi KTimm-Giel A(2024)Enhancing Geographic Greedy Routing in Sparse LDACS Air-to-Air Networks through k-Hop Neighborhood Exploitation2024 IEEE 49th Conference on Local Computer Networks (LCN)10.1109/LCN60385.2024.10639650(1-7)Online publication date: 8-Oct-2024
https://doi.org/10.1109/LCN60385.2024.10639650
Kim DJung JKwon Y(2022)3D Void Handling Geographic P2P-RPL for Indoor Multi-Hop IR-UWB NetworksElectronics10.3390/electronics1104062511:4(625)Online publication date: 17-Feb-2022
https://doi.org/10.3390/electronics11040625
Show More Cited By

Index Terms

Practical 3D geographic routing for wireless sensor networks
1. Networks
  1. Network protocols
  2. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Energy-aware geographic routing in wireless sensor networks with anchor nodes

Energy efficiency has become an important design consideration in geographic routing protocols for wireless sensor networks because the sensor nodes are energy constrained and battery recharging is usually not feasible. However, numerous existing energy-...
Energy efficient geographic routing for wireless sensor networks
On greedy geographic routing algorithms in sensing-covered networks
MobiHoc '04: Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing

Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SenSys '10: Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems

November 2010

461 pages

ISBN:9781450303446

DOI:10.1145/1869983

General Chair:
Jan Beutel
ETH Zurich, Switzerland
,
Program Chairs:
Deepak Ganesan
University of Massachusetts, Amherst
,
Jack Stankovic
University of Virginia

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ministry of Education - Singapore

Conference

SenSys10

Sponsor:

SenSys10: The 8th ACM Conference on Embedded Network Sensor Systems

November 3 - 5, 2010

Zürich, Switzerland

Acceptance Rates

Overall Acceptance Rate 174 of 867 submissions, 20%

Upcoming Conference

SenSys '24

Sponsor:
sigbed
sigbed
sigbed
sigbed
sigbed

The 22nd ACM Conference on Embedded Networked Sensor Systems

November 4 - 7, 2024

Hangzhou , China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
535
Total Downloads

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

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

R. MM. J(2024)Comprehensive Study on Routing in FANETIntelligent Decision Making Through Bio-Inspired Optimization10.4018/979-8-3693-2073-0.ch011(195-217)Online publication date: 24-May-2024
https://doi.org/10.4018/979-8-3693-2073-0.ch011
Ahmed MFuger KKuladinithi KTimm-Giel A(2024)Enhancing Geographic Greedy Routing in Sparse LDACS Air-to-Air Networks through k-Hop Neighborhood Exploitation2024 IEEE 49th Conference on Local Computer Networks (LCN)10.1109/LCN60385.2024.10639650(1-7)Online publication date: 8-Oct-2024
https://doi.org/10.1109/LCN60385.2024.10639650
Kim DJung JKwon Y(2022)3D Void Handling Geographic P2P-RPL for Indoor Multi-Hop IR-UWB NetworksElectronics10.3390/electronics1104062511:4(625)Online publication date: 17-Feb-2022
https://doi.org/10.3390/electronics11040625
Nemati MAl Homssi BKrishnan SPark JLoke SChoi J(2022)Non-Terrestrial Networks with UAVs: A Projection on Flying Ad-Hoc NetworksDrones10.3390/drones61103346:11(334)Online publication date: 31-Oct-2022
https://doi.org/10.3390/drones6110334
Fu JWang NNie LCui BBhargava B(2022)Defending Trace-Back Attack in 3D Wireless Internet of ThingsIEEE/ACM Transactions on Networking10.1109/TNET.2022.314929330:4(1765-1779)Online publication date: Aug-2022
https://doi.org/10.1109/TNET.2022.3149293
Zheng ZLi JYong TWen Z(2022)Research of Routing Protocols for Unmanned Aerial Vehicle Ad Hoc Network2022 2nd International Conference on Consumer Electronics and Computer Engineering (ICCECE)10.1109/ICCECE54139.2022.9712805(518-524)Online publication date: 14-Jan-2022
https://doi.org/10.1109/ICCECE54139.2022.9712805
Rovira-Sugranes ARazi AAfghah FChakareski J(2022)A review of AI-enabled routing protocols for UAV networksAd Hoc Networks10.1016/j.adhoc.2022.102790130:COnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.adhoc.2022.102790
Dhall RDhongdi S(2022)Review of Protocol Stack Development of Flying Ad-hoc Networks for Disaster Monitoring ApplicationsArchives of Computational Methods in Engineering10.1007/s11831-022-09791-y30:1(37-68)Online publication date: 27-Jul-2022
https://doi.org/10.1007/s11831-022-09791-y
Guillen-Perez AMontoya ASanchez-Aarnoutse JCano M(2021)A Comparative Performance Evaluation of Routing Protocols for Flying Ad-Hoc Networks in Real ConditionsApplied Sciences10.3390/app1110436311:10(4363)Online publication date: 11-May-2021
https://doi.org/10.3390/app11104363
Gupta NYadav RNagaria RGupta D(2021)An Angular 3D Path Selection Protocol in Wireless Sensor NetworksOpen Computer Science10.1515/comp-2020-020311:1(190-207)Online publication date: 27-Jan-2021
https://doi.org/10.1515/comp-2020-0203
Show More Cited By

View Options

Get Access

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