4215803
Summary
Kleinberg, R. (2007) Geographic Routing Using Hyperbolic Space. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. may, pages 1902 -1909. ((URL))
Abstract
We propose a scalable and reliable point-to-point routing algorithm for ad hoc wireless networks and sensor-nets. Our algorithm assigns to each node of the network a virtual coordinate in the hyperbolic plane, and performs greedy geographic routing with respect to these virtual coordinates. Unlike other proposed greedy routing algorithms based on virtual coordinates, our embedding guarantees that the greedy algorithm is always successful in finding a route to the destination, if such a route exists. We describe a distributed algorithm for computing each node's virtual coordinates in the hyperbolic plane, and for greedily routing packets to a destination point in the hyperbolic plane. (This destination may be the address of another node of the network, or it may be an address associated to a piece of content in a Distributed Hash Table. In the latter case we prove that the greedy routing strategy makes a consistent choice of the node responsible for the address, irrespective of the source address of the request.) We evaluate the resulting algorithm in terms of both path stretch and node congestion. #4215803Bib
Bibtex entry
@INPROCEEDINGS { 4215803,
AUTHOR = { Kleinberg, R. },
BOOKTITLE = { INFOCOM 2007. 26th IEEE International Conference on Computer Communications },
TITLE = { Geographic Routing Using Hyperbolic Space },
YEAR = { 2007 },
MONTH = { may },
VOLUME = { },
NUMBER = { },
PAGES = { 1902 -1909 },
ABSTRACT = { We propose a scalable and reliable point-to-point routing algorithm for ad hoc wireless networks and sensor-nets. Our algorithm assigns to each node of the network a virtual coordinate in the hyperbolic plane, and performs greedy geographic routing with respect to these virtual coordinates. Unlike other proposed greedy routing algorithms based on virtual coordinates, our embedding guarantees that the greedy algorithm is always successful in finding a route to the destination, if such a route exists. We describe a distributed algorithm for computing each node's virtual coordinates in the hyperbolic plane, and for greedily routing packets to a destination point in the hyperbolic plane. (This destination may be the address of another node of the network, or it may be an address associated to a piece of content in a Distributed Hash Table. In the latter case we prove that the greedy routing strategy makes a consistent choice of the node responsible for the address, irrespective of the source address of the request.) We evaluate the resulting algorithm in terms of both path stretch and node congestion. },
KEYWORDS = { ad hoc wireless sensor network;distributed algorithm;geographic routing;greedy geographic routing;hyperbolic space;point-to-point routing algorithm;virtual coordinate;ad hoc networks;greedy algorithms;telecommunication network routing;wireless sensor networks; },
URL = { http://dx.doi.org/10.1109/INFCOM.2007.221 },
ISSN = { 0743-166X },
}