A Novel Family of Geometric Planar Graphs for Wireless Ad Hoc Networks

Abstract : We propose a radically new family of geometric graphs, i.e., Hypocomb, Reduced Hypocomb and Local Hypocomb. The first two are extracted from a complete graph; the last is extracted from a Unit Disk Graph (UDG). We analytically study their properties including connectivity, planarity and degree bound. All these graphs are connected (provided the original graph is connected) planar. Hypocomb has unbounded degree while Reduced Hypocomb and Local Hypocomb have maximum degree 6 and 8, respectively. To our knowledge, Local Hypocomb is the first strictly-localized, degree-bounded planar graph computed using merely 1-hop neighbor position information. We present a construction algorithm for these graphs and analyze its time complexity. Hypocomb family graphs are promising for wireless ad hoc networking. We report our numerical results on their average degree and their impact on FACE routing. We discuss their potential applications and some open problems.
Type de document :
Communication dans un congrès
Proc. 30th IEEE International Conference on Computer Communications (IEEE INFOCOM 2011), Apr 2011, Shanghai, China. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00587873
Contributeur : Nathalie Mitton <>
Soumis le : jeudi 21 avril 2011 - 15:47:45
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 22 juillet 2011 - 02:59:46

Fichier

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

Identifiants

  • HAL Id : inria-00587873, version 1

Collections

Citation

Xu Li, Nathalie Mitton, Isabelle Simplot-Ryl, David Simplot-Ryl. A Novel Family of Geometric Planar Graphs for Wireless Ad Hoc Networks. Proc. 30th IEEE International Conference on Computer Communications (IEEE INFOCOM 2011), Apr 2011, Shanghai, China. 2011. 〈inria-00587873〉

Partager

Métriques

Consultations de la notice

363

Téléchargements de fichiers

160