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 metadatas

https://hal.inria.fr/inria-00073269
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 12:23:26 PM
Last modification on : Saturday, January 27, 2018 - 1:31:03 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

221

Files downloads

243