Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T02:56:45.981Z Has data issue: false hasContentIssue false

Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networks

Published online by Cambridge University Press:  01 July 2016

F. Baccelli*
Affiliation:
École Normale Supérieure
K. Tchoumatchenko*
Affiliation:
École Normale Supérieure
S. Zuyev*
Affiliation:
University of Strathclyde
*
∗ Postal address: École Normale Supérieure, Dept. of Mathematics and Computer Science, 45 rue d'Ulm, 75230 Paris cedex 05, France. Email address: baccelli@dmi.ens.fr
∗∗ Postal address: France Telecom CNET/DAC/OAT, 38-40 rue du General Leclerc, 92 794 Essy-les-Moulineaux, Cedex 9, France. Email address: Konstantin.Tchoumatchenko@cnet.francetelecom.fr
∗∗∗ Postal address: Statistics and Modelling Science Dept., University of Strathclyde, Livingston Tower, 26 Richmond St., Glasgow, G1 1XH, UK. Email address: sergei@stams.strath.ac.uk

Abstract

Consider the Delaunay graph and the Voronoi tessellation constructed with respect to a 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 routeing in mobile communication networks.

Information

Type
Stochastic Geometry and Statistical Applications
Copyright
Copyright © Applied Probability Trust 2000 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable