Markov Paths on the Poisson-Delaunay Graph with applications to routing in mobile networks

Abstract : Consider the Delaunay graph and the Voronoi tessellation constructed with respect to a planar Poisson point process. The sequence of nuclei of the Voronoi cells that are crossed by a line defines a path on the Delaunay graph. We show that the evolution of this path is governed by a Markov chain. We study the ergodic properties of the chain and find its stationary distribution. As a corollary we obtain the ratio of the mean path length to the Euclidean distance between the end points, and hence a bound for the mean asymptotic length of the shortest path. We apply these results to define a family of simple incremental algorithms for constructing short paths on the Delaunay graph and discuss potential applications to routing in mobile communications networks.
Type de document :
Rapport
RR-3420, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073269
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:23:26
Dernière modification le : samedi 27 janvier 2018 - 01:31:03
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:40:31

Fichiers

Identifiants

  • HAL Id : inria-00073269, version 1

Collections

Citation

François Baccelli, Konstantin Tchoumatchenko, Sergei Zuyev. Markov Paths on the Poisson-Delaunay Graph with applications to routing in mobile networks. RR-3420, INRIA. 1998. 〈inria-00073269〉

Partager

Métriques

Consultations de la notice

204

Téléchargements de fichiers

185