Planarisation de graphes dans les réseaux ad-hoc
Résumé
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 pinpoint some interesting open problems for future research.
Nous proposons une toute nouvelle famille de graphes géométriques, i.e., Hypocomb, Reduced Hypocomb et Local Hypocomb. Les deux premiers sont extraits d'un graphe complet; le dernier est extrait d'un graphe unitaire (Unit Disk Graph (UDG)). Nous étudions de manière analytique leurs propriétés et en particulier la connexité, la planarité et l'existence d'une borne au degré. Nous montrons que tous ces graphes sont connexes (si le graphe original l'est) et planaires. Nous montrons que le graphe Hypocomb est de degré non borné tandis que les graphes Reduced Hypocomb et Local Hypocomb voient respectivement leur degré borné par 6 et 8. À notre connaissance, le graphe Local Hypocomb est le premier graphe strictement local, planaire et de degré borné, calculé en utilisant simplement les informations de voisinage à un saut. La famille des graphes Hypocomb est prometteuse pour les réseaux sans fil multi-sauts. Nous montrons par simulation ses bénéfices lorsqu'appliquée à une Face routing. Nous discutons de ses applications potentielles et mettons en évidence des perspectives pour les travaux futurs.
Origine : Fichiers produits par l'(les) auteur(s)