Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach

Anne-Marie Kermarrec 1 Guang Tan 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : In geographic (or geometric) routing, messages are expected to route in a {\em 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 alone does not guarantee delivery due to the existence of local minima (or dead ends). Overcoming local minima requires nodes to maintain extra non-local state or to use auxiliary mechanisms. We study how to facilitate greedy forwarding by using a minimum amount of such non-local state in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of {\em Greedily Routable Components} (GRC), where greedy routing is guaranteed to work. We approach it by considering an approximate version in a continuous domain, with a central concept called the {\em Greedily Routable Region} (GRR). A full characterization of GRR is given concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. These results lead to a practical routing protocol that has a routing stretch below 7 in a continuous domain, and close to 1 in several realistic network settings.
Type de document :
Communication dans un congrès
ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Sep 2010, Chicago, United States. 2010
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00493387
Contributeur : Guang Tan <>
Soumis le : vendredi 2 juillet 2010 - 14:44:25
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : lundi 4 octobre 2010 - 11:41:56

Fichier

GreedyRoutableComponent-full.p...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00493387, version 1

Citation

Anne-Marie Kermarrec, Guang Tan. Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Sep 2010, Chicago, United States. 2010. 〈inria-00493387〉

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

498