Article

Lazy cross-link removal for geographic routing

Authors:

Young-Jin Kim Ramesh Govindan,

Scott ShenkerAuthors Info & Claims

SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems

Pages 112 - 124

https://doi.org/10.1145/1182807.1182819

Published: 31 October 2006 Publication History

Abstract

Geographic techniques promise highly scalable any-to-any routing in wireless sensor networks. In one thread of research on geographic routing, researchers have explored robust, distributed graph planarization. Arguing that such planarization techniques have high overhead, researchers have more recently pursued a thread in which they propose precomputation of routing structures (e.g., hull trees and grids) to achieve low-overhead geographic routing.In this paper we introduce a third approach, LCR, that does not involve any precomputation of distributed routing structures, nor full a priori planarization. Instead, LCR removes non-planarities lazily only when they interfere with correct geographic routing. Lazy removal of link crossings results in an order of magnitude or more lower overhead than any previously proposed approach.

References

[1]

BOSE, P., MORIN, P., STOJMENOVIC, I., AND URRUTIA, J. Routing with guaranteed delivery in ad hoc wireless networks. In Proc. ACM DIALM Workshop (Seattle, WA, USA, Aug. 1999), ACM, pp. 48--55.]]

Digital Library

[2]

BRUCK, J., GAO, J., AND JIANG, A.A. MAP: medial axis based geometric routing in sensor networks. In Proc. ACM/IEEE MobiCom (New York, NY, USA, 2005), ACM Press, pp. 88--102.]]

Digital Library

[3]

FANG, Q., GAO, J., GUIBAS, L.J., DE SILVA, V., AND ZHANG, L. GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks. In Proc. IEEE Infocom (2005).]]

[4]

FINN, G. Routing and addressing problems in large metropolitan-scale internetworks. Tech. Rep. ISI/RR-87-180, USC/Information Sciences Institute, Mar. 1987.]]

[5]

FONSECA, R., RATNASAMY, S., ZHAO, J., EE, C., CULLER, D., SHENKER, S., AND STOICA, I. Beacon Vector Routing: Scalable Point-to-point Routing in Wireless Sensor Networks. In Proc. USENIX Symposium on Networked Systems Design and Implementation (Boston, MA, April 2005).]]

Digital Library

[6]

GABRIEL, K., AND SOKAL, R. A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969), 259--278.]]

[7]

GAO, J., GUIBAS, L., HERSHBERGER, J., ZHANG, L., AND ZHU, A. Geometric spanner for routing in mobile networks. In Proc. ACM MobiHoc (Oct. 2001), pp. 45--55.]]

Digital Library

[8]

HILL, J., SZEWCZYK, R., WOO, A., HOLLAR, S., CULLER, D., AND PISTER, K. System architecture directions for networked sensors. In Proc. 9th ACM ASPLOS (Cambridge, MA, USA, Nov. 2000), ACM, pp. 93--104.]]

Digital Library

[9]

KARP, B. Geographic Routing for Wireless Networks. PhD thesis, Harvard University, 2000.]]

Digital Library

[10]

KARP, B. Challenges in geographic routing: Sparse networks, obstacles, and traffic provisioning. Presentation at the DIMACS Workshop on Pervasive Networking, May 2001.]]

[11]

KARP, B., AND KUNG, H.T. GPSR: Greedy perimeter stateless routing for wireless networks. In Proc. ACM/IEEE MobiCom (Boston, Mass., USA, Aug. 2000), ACM, pp. 243--254.]]

Digital Library

[12]

KIM, D., AND MAXEMCHUK, N. Simple Robotic Routing in Ad-Hoc Networks. In Proc. IEEE International Conference on Network Protocols (2004).]]

Digital Library

[13]

KIM, Y.J., GOVINDAN, R., KARP, B., AND SHENKER, S. Geographic Routing Made Practical. In Proc. USENIX Symposium on Networked Systems Design and Implementation (Boston, MA, April 2005).]]

Digital Library

[14]

KIM, Y.J., GOVINDAN, R., KARP, B., AND SHENKER, S. On the Pitfalls of Geographic Routing. In Proc. of the 3rd International Workshop on DIAL-M-POMC (Cologne, Germany, September 2005).]]

Digital Library

[15]

KLEINROCK, L., AND TAKAGI, H. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Comm. 32, 3 (1984), 246--257.]]

[16]

KO, Y.-B., AND VAIDYA, N. Location-aided routing in mobile ad hoc networks. In Proc. ACM/IEEE MobiCom (Aug. 1998).]]

Digital Library

[17]

KUHN, F., WATTENHOFER, R., ZHANG, Y., AND ZOLLINGER, A. Geometric ad-hoc routing: Of theory and practice. In Proc. ACM PODC (Boston, MA, USA, July 2003).]]

Digital Library

[18]

KUHN, F., WATTENHOFER, R., AND ZOLLINGER, A. Ad-hoc networks beyond unit disk graphs. In Proc. ACM DIALM POMC Workshop (Sept. 2003).]]

Digital Library

[19]

KUHN, F., WATTENHOFER, R., AND ZOLLINGER, A. Worst-case Optimal and Average-case Efficient Geometric Ad-Hoc Routing. In Proc. ACM MobiHoc (2003).]]

Digital Library

[20]

LI, J., JANNOTTI, J., DE COUTO, D.S.J., KARGER, D.R., AND MORRIS, R. A scalable location service for geographic ad hoc routing. In Proceedings of the 6th ACM International Conference on Mobile Computing and Networking (MobiCom '00) (Boston, Massachusetts, August 2000), pp. 120--130.]]

Digital Library

[21]

LIANG, B., LISKOV, B., AND MORRIS, R. Geographic Routing without Planarization. In Proc. USENIX Symposium on Networked Systems Design and Implementation (April 2006).]]

Digital Library

[22]

NEWSOME, J., AND SONG, D. GEM: Graph embedding for routing and data-centric stroage in sensor networks with geographic information. In Proc. ACM Sensys (Nov. 2003).]]

Digital Library

[23]

RAO, A., RATNASAMY, S., SHENKER, S., AND STOICA, I. Geographic routing without location information. In Proc. ACM/IEEE MobiCom (Oct. 2003), pp. 96--108.]]

Digital Library

[24]

RATNASAMY, S., KARP, B., YIN, L., YU, F., ESTRIN, D., GOVINDAN, R., AND SHENKER, S. GHT: A geographic hash table for data-centric storage. In Proc. ACM WSNA Workshop (Atlanta, Georgia, USA, Sept. 2002), ACM, pp. 78--87.]]

Digital Library

[25]

SEADA, K., HELMY, A., AND GOVINDAN, R. Localization errors on geographic face routing in sensor networks. In Proc. IEEE IPSN Workshop (Berkeley, CA, USA, Apr. 2004).]]

Digital Library

[26]

TOUSSAINT, G. The relative neighborhood graph of a finite planar set. Pattern Recognition 12, 4 (1980), 261--268.]]

Cited By

Bhuiyan MWeiss GWang TMin G(2019)Mobile Target Tracking with Multiple Objectives in Wireless Sensor NetworksMission-Oriented Sensor Networks and Systems: Art and Science10.1007/978-3-319-91146-5_12(437-495)Online publication date: 19-Sep-2019
https://doi.org/10.1007/978-3-319-91146-5_12
Wang JZhang RYuan JDu X(2018)A 3-D Energy-Harvesting-Aware Routing Scheme for Space Nanosatellite NetworksIEEE Internet of Things Journal10.1109/JIOT.2018.28031115:4(2729-2740)Online publication date: Aug-2018
https://doi.org/10.1109/JIOT.2018.2803111
Król MSchiller ERousseau FDuda ARömer KLangendoen KVoigt T(2016)WEAVE: Efficient Geographical Routing in Large-Scale NetworksProceedings of the 2016 International Conference on Embedded Wireless Systems and Networks10.5555/2893711.2893726(89-100)Online publication date: 15-Feb-2016
https://dl.acm.org/doi/10.5555/2893711.2893726
Show More Cited By

Index Terms

Lazy cross-link removal for geographic routing
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

Fault tolerant greedy perimeter stateless routing in wireless network
ICCCS '11: Proceedings of the 2011 International Conference on Communication, Computing & Security

Routing in wireless network is a key research area. This paper proposes a fault tolerant greedy perimeter stateless routing protocol (FGPSR) suitable for wireless network with minimal routing overhead. FGPSR has four main phases-Fault testing, ...
Greedy geographic routing in large-scale sensor networks: a minimum network decomposition approach

In geographic (or geometric) routing, messages are by default routed in a greedy manner: The current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy ...
Efficient geographic routing in multihop wireless networks
MobiHoc '05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing

We propose a new link metric called normalized advance (NADV) for geographic routing in multihop wireless networks. NADV selects neighbors with the optimal trade-off between proximity and link cost. Coupled with the local next hop decision in geographic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems

October 2006

444 pages

ISBN:1595933433

DOI:10.1145/1182807

General Chair:
Andrew Campbell
Dartmouth University
,
Program Chairs:
Philippe Bonnet
University of Copenhagen (DIKU), Denmark
,
John Heidemann
University of Southern California/ISI, USA

Copyright © 2006 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: 31 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SenSys06

Sponsor:

SenSys06: ACM Conference on Embedded Network Sensor Systems

October 31 - November 3, 2006

Colorado, Boulder, USA

Acceptance Rates

Overall Acceptance Rate 174 of 867 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
512
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhuiyan MWeiss GWang TMin G(2019)Mobile Target Tracking with Multiple Objectives in Wireless Sensor NetworksMission-Oriented Sensor Networks and Systems: Art and Science10.1007/978-3-319-91146-5_12(437-495)Online publication date: 19-Sep-2019
https://doi.org/10.1007/978-3-319-91146-5_12
Wang JZhang RYuan JDu X(2018)A 3-D Energy-Harvesting-Aware Routing Scheme for Space Nanosatellite NetworksIEEE Internet of Things Journal10.1109/JIOT.2018.28031115:4(2729-2740)Online publication date: Aug-2018
https://doi.org/10.1109/JIOT.2018.2803111
Król MSchiller ERousseau FDuda ARömer KLangendoen KVoigt T(2016)WEAVE: Efficient Geographical Routing in Large-Scale NetworksProceedings of the 2016 International Conference on Embedded Wireless Systems and Networks10.5555/2893711.2893726(89-100)Online publication date: 15-Feb-2016
https://dl.acm.org/doi/10.5555/2893711.2893726
Dua AKumar NBawa SRodrigues J(2015)An Intelligent Context-aware Congestion Resolution Protocol for Data Dissemination in Vehicular Ad Hoc NetworksMobile Networks and Applications10.1007/s11036-015-0588-120:2(181-200)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s11036-015-0588-1
Sarkar RZhu XGao J(2013)Distributed and compact routing using spatial distributions in wireless sensor networksACM Transactions on Sensor Networks10.1145/2480730.24807359:3(1-20)Online publication date: 4-Jun-2013
https://dl.acm.org/doi/10.1145/2480730.2480735
Clouser TVora AFox TNesterenko M(2013)Void traversal for efficient non-planar geometric routingAd Hoc Networks10.1016/j.adhoc.2013.05.01311:8(2345-2355)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.adhoc.2013.05.013
Cairns DFayed MMouftah H(2013)Revisiting Planarity in Position-Based Routing for Wireless NetworksAd Hoc Networks10.1007/978-3-642-36958-2_7(87-102)Online publication date: 2013
https://doi.org/10.1007/978-3-642-36958-2_7
Khokhar RNgadi MLatiff MAmin M(2012)Reactive traffic-aware routing strategy for urban vehicular environmentsInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2012.04862510:3(149-163)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1504/IJAHUC.2012.048625
Mathews EFrey H(2012)A localized link removal and addition based planarization algorithmProceedings of the 13th international conference on Distributed Computing and Networking10.1007/978-3-642-25959-3_25(337-350)Online publication date: 3-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-25959-3_25
Erman ADilo AHoesel LHavinga P(2011)On Mobility Management in Multi-Sink Sensor Networks for Geocasting of QueriesSensors10.3390/s11121141511:12(11415-11446)Online publication date: 1-Dec-2011
https://doi.org/10.3390/s111211415
Show More Cited By

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