Visibility-Graph-based Shortest-Path Geographic Routing in Sensor Networks

Guang Tan 1 Marin Bertier 1 Anne-Marie Kermarrec 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 : We study the problem of shortest-path geographic routing in a static sensor network. Existing algorithms often make routing decisions based on node information in local neighborhoods. However, it is shown by Kuhn et al. that such a design constraint results in a highly undesirable lower bound for routing performance: if a best route has length c, then in the worst case a route produced by any localized algorithm has length Ω(c^2), which can be arbitrarily worse than the optimal. We present VIGOR, a VIsibility-Graph-based rOuting pRotocol that produces routes of length Θ(c). Our design is based on the construction of a much reduced visibility graph, which guides nodes to find near-optimal paths. The per-node protocol overheads in terms of state information and message transmission depend only on the complexity of the field's large topological features, rather than on the network size. Simulation results show that our protocol dramatically outperforms localized protocols such as GPSR and GOAFR+ in both average and worst cases, with reasonable extra overheads.
Type de document :
Communication dans un congrès
INFOCOM 2009, Apr 2009, Rio de Janeiro, Brazil. 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00430147
Contributeur : Guang Tan <>
Soumis le : jeudi 5 novembre 2009 - 18:04:25
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:32:20

Fichier

vigor.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00430147, version 1

Citation

Guang Tan, Marin Bertier, Anne-Marie Kermarrec. Visibility-Graph-based Shortest-Path Geographic Routing in Sensor Networks. INFOCOM 2009, Apr 2009, Rio de Janeiro, Brazil. 2009. 〈inria-00430147〉

Partager

Métriques

Consultations de la notice

606

Téléchargements de fichiers

740