Hypocomb: Bounded-degree Localized 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. T he 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 I-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 [2]. We discuss their potential applications and some open problems for future research.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems - Spotlight Paper August 2012, 2013, 24 (7), pp.1341-1354
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00704682
Contributeur : Nathalie Mitton <>
Soumis le : mardi 3 décembre 2013 - 17:26:29
Dernière modification le : mercredi 29 novembre 2017 - 15:06:23
Document(s) archivé(s) le : lundi 3 mars 2014 - 22:05:19

Fichier

Hypocomb-TPDS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00704682, version 1

Collections

Citation

Xu Li, Nathalie Mitton, Isabelle Simplot-Ryl, David Simplot-Ryl. Hypocomb: Bounded-degree Localized Geometric Planar Graphs for Wireless Ad Hoc Networks. IEEE Transactions on Parallel and Distributed Systems - Spotlight Paper August 2012, 2013, 24 (7), pp.1341-1354. 〈hal-00704682〉

Partager

Métriques

Consultations de la notice

422

Téléchargements de fichiers

166