Article

On the pitfalls of geographic face routing

Authors:

Ramesh Govindan,

Scott ShenkerAuthors Info & Claims

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

Pages 34 - 43

https://doi.org/10.1145/1080810.1080818

Published: 02 September 2005 Publication History

Abstract

Geographic face routing algorithms have been widely studied in the literature [1, 8, 13]. All face routing algorithms rely on two primitives: planarization and face traversal. The former computes a planar subgraph of the underlying wireless connectivity graph, while the latter defines a consistent forwarding mechanism for routing around "voids." These primitives are known to be provably correct under the idealized unit-disk graph assumption, where nodes are assumed to be connected if and only if they are within a certain distance from each other.In this paper we classify the ways in which existing planarization techniques fail with realistic, non-ideal radios. We also demonstrate the consequences of these pathologies on reachability between node pairs in a real wireless testbed. We then examine the various face traversal rules described in the literature, and identify those [12, 16] that are robust to violations of the unit-disk graph assumption.

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), pp. 48--55.

Digital Library

[2]

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

[3]

Gabriel, K., and Sokal, R. A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969), 259--278.

[4]

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

[5]

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).

Digital Library

[6]

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

Digital Library

[7]

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

[8]

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

[9]

Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S. Geographic routing made practical. In Proc. USENIX Symposium on Network Systems Design and Implementation (Boston, Massachusetts, USA, May 2005), USENIX.

Digital Library

[10]

Kleinrock, L., and Takagi, H. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Comm. 32, 3 (1984), 246--257.

[11]

Ko, Y.-B., and Vaidya, N. Location-aided routing in mobile ad hoc networks. In Proc. ACM/IEEE MobiCom (Aug. 1998).

Digital Library

[12]

Kranakis, E., Singh, H., and Urrutia, J. Compass routing on geometric networks. In Proc. 11th Canadian Conference on Computational Geometry, Aug. 1999.

[13]

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

[14]

Kuhn, F., Wattenhofer, R., and Zollinger, A. Asymptotically optimal geometric mobile ad-hoc routing. In Proc. ACM DIALM POMC Workshop (Sept. 2002).

Digital Library

[15]

Kuhn, F., Wattenhofer, R., and Zollinger, A. Ad-hoc networks beyond unit disk graphs. In Proc. ACM DIALM POMC Workshop (Sept. 2003).

Digital Library

[16]

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

[17]

Li, X., Kim, Y. J., Govindan, R., and Hong, W. Multi-dimensional range queries in sensor networks. In Proc. ACM Sensys (Nov. 2003).

Digital Library

[18]

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

[19]

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

[20]

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

[21]

Savvides, A., Han, C.-C., and Srivastava, M. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proc. ACM/IEEE MobiCom (Rome, Italy, July 2001), {ACM, p. to appear.

Digital Library

[22]

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

[23]

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

[24]

Woo, A., Tong, T., and Culler, D. Taming the underlying challenges of reliable multihop routing. In Proc. ACM Sensys (Los Angeles, CA, Nov. 2003).

Digital Library

[25]

Zhao, J., and Govindan, R. Understanding packet delivery performance in dense wireless sensor networks. In Proc. ACM Sensys (Los Angeles, CA, Nov. 2003).

Digital Library

[26]

Zhou, G., He, T., Krishnamurthy, S., and Stankovic, J. A. Impact of radio irregularity on wireless sensor networks. In Proc. ACM Mobisys (June 2004).

Digital Library

Cited By

Ammari HAhmed A(2020)Sensor Data Geographic Forwarding in Two-Dimensional and Three-Dimensional SpacesSensor Technology10.4018/978-1-7998-2454-1.ch069(1459-1493)Online publication date: 2020
https://doi.org/10.4018/978-1-7998-2454-1.ch069
Singh PChen Y(2018)Energy efficient greedy forwarding based on residual energy for wireless sensor networks2018 27th Wireless and Optical Communication Conference (WOCC)10.1109/WOCC.2018.8372731(1-6)Online publication date: Apr-2018
https://doi.org/10.1109/WOCC.2018.8372731
Ammari HAhmed A(2017)Sensor Data Geographic Forwarding in Two-Dimensional and Three-Dimensional SpacesHandbook of Research on Wireless Sensor Network Trends, Technologies, and Applications10.4018/978-1-5225-0501-3.ch013(317-352)Online publication date: 2017
https://doi.org/10.4018/978-1-5225-0501-3.ch013
Show More Cited By

Index Terms

On the pitfalls of geographic face routing
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

Lazy cross-link removal for geographic routing
SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems

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 ...
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, ...
Modeling and analyzing the correctness of geographic face routing under realistic conditions

Geographic protocols are very promising for wireless ad hoc and sensor networks due to the low state storage and low message overhead. Under certain idealized conditions, geographic routing - using a combination of greedy forwarding and face routing - ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

September 2005

120 pages

ISBN:1595930922

DOI:10.1145/1080810

Program Chairs:
Suman Banerjee
University of Wisconsin-Madison
,
Samrat Ganguly
NEC Laboratories America

Copyright © 2005 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: 02 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

Dial M - POMC 05

Sponsor:

Dial M - POMC 05: Joint Workshop on Foundations of Mobile Computing 2005

September 2, 2005

Cologne, Germany

Acceptance Rates

Overall Acceptance Rate 21 of 68 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
569
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ammari HAhmed A(2020)Sensor Data Geographic Forwarding in Two-Dimensional and Three-Dimensional SpacesSensor Technology10.4018/978-1-7998-2454-1.ch069(1459-1493)Online publication date: 2020
https://doi.org/10.4018/978-1-7998-2454-1.ch069
Singh PChen Y(2018)Energy efficient greedy forwarding based on residual energy for wireless sensor networks2018 27th Wireless and Optical Communication Conference (WOCC)10.1109/WOCC.2018.8372731(1-6)Online publication date: Apr-2018
https://doi.org/10.1109/WOCC.2018.8372731
Ammari HAhmed A(2017)Sensor Data Geographic Forwarding in Two-Dimensional and Three-Dimensional SpacesHandbook of Research on Wireless Sensor Network Trends, Technologies, and Applications10.4018/978-1-5225-0501-3.ch013(317-352)Online publication date: 2017
https://doi.org/10.4018/978-1-5225-0501-3.ch013
Li SZeng WZhou DGu XGao J(2016)Compact Conformal Map for Greedy Routing in Wireless Mobile Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2015.247575215:7(1632-1646)Online publication date: 1-Jul-2016
https://doi.org/10.1109/TMC.2015.2475752
Tsai JHan Y(2016)Cooperative rotational sweep schemes for geographic routing2016 IEEE International Conference on Communications (ICC)10.1109/ICC.2016.7511314(1-7)Online publication date: May-2016
https://doi.org/10.1109/ICC.2016.7511314
Zollinger A(2016)Geographic RoutingEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_164(825-828)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_164
Chessa SEscolar SPelagatti SCarretero J(2015)Multi-dimensional recursive routing with guaranteed delivery in Wireless Sensor NetworksComputer Communications10.1016/j.comcom.2014.10.00757(85-99)Online publication date: Feb-2015
https://doi.org/10.1016/j.comcom.2014.10.007
Petrioli CNati MCasari PZorzi MBasagni S(2014)ALBA-RIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.6025:3(529-539)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1109/TPDS.2013.60
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
Cadger FCurran KSantos JMoffett S(2013)A Survey of Geographical Routing in Wireless Ad-Hoc NetworksIEEE Communications Surveys & Tutorials10.1109/SURV.2012.062612.0010915:2(621-653)Online publication date: Oct-2014
https://doi.org/10.1109/SURV.2012.062612.00109
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