HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00073269
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:23:26 PM
Last modification on : Friday, February 4, 2022 - 3:16:09 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:40:31 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

130

Files downloads

225