Succinct Greedy Geometric Routing Using Hyperbolic Geometry
Authors:
- 17 December 2010
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 60 (11) , 1571-1580
Abstract
We describe a method for performing greedy geometric routing for any n-vertex simple connected graph G in the hyperbolic plane, so that a message M between any pair of vertices may be routed by having each vertex that receives M pass it to a neighbor that is closer to M's destination. Our algorithm produces succinct embeddings, where vertex positions are represented using O(\log n) bits and distance comparisons may be performed efficiently using these representations. These properties are useful, for example, for routing in sensor networks, where storage and bandwidth are limited.Keywords
This publication has 29 references indexed in Scilit:
- Succinct Greedy Geometric Routing in the Euclidean PlaneLecture Notes in Computer Science, 2009
- A Distributed Graph Algorithm for Geometric Routing in Ad Hoc Wireless NetworksJournal of Networks, 2007
- Geographic Routing Using Hyperbolic Space2007
- On a conjecture related to geometric routingTheoretical Computer Science, 2005
- Geometric ad-hoc routing2003
- Worst-Case optimal and average-case efficient geometric ad-hoc routing2003
- Asymptotically optimal geometric mobile ad-hoc routing2002
- GPSR2000
- How to draw a planar graph on a gridCombinatorica, 1990
- Optimum binary search treesActa Informatica, 1971