Hypocomb: Bounded-degree Localized Geometric Planar Graphs for Wireless Ad Hoc Networks - Archive ouverte HAL Access content directly
Journal Articles IEEE Transactions on Parallel and Distributed Systems Year : 2013

Hypocomb: Bounded-degree Localized Geometric Planar Graphs for Wireless Ad Hoc Networks

(1) , (1) , (1) , (1)
1

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. We discuss their potential applications and some open problems for future research.
Fichier principal
Vignette du fichier
Hypocomb-TPDS.pdf (246.06 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00704682 , version 1 (03-12-2013)

Identifiers

Cite

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, 2013, 24 (7), pp.1341-1354. ⟨10.1109/TPDS.2012.180⟩. ⟨hal-00704682⟩

Collections

INRIA INRIA2
258 View
193 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More