Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T08:42:12.991Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Graph theory Stochastic processes Geometric probability and stochastic geometry Markov processes

Published online by Cambridge University Press:  01 July 2016

F. Baccelli ,
K. Tchoumatchenko  and
S. Zuyev
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: [email protected]
∗∗ Postal address: France Telecom CNET/DAC/OAT, 38-40 rue du General Leclerc, 92 794 Essy-les-Moulineaux, Cedex 9, France. Email address: [email protected]
∗∗∗ Postal address: Statistics and Modelling Science Dept., University of Strathclyde, Livingston Tower, 26 Richmond St., Glasgow, G1 1XH, UK. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Poisson processDelaunay triangulationVoronoi tessellationshortest pathfirst-passage percolationrouteingmobile networks

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 60J05: Discrete-time Markov processes on general state spaces 60G55: Point processes 05C12: Distance in graphs 05C38: Paths and cycles
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 32 , Issue 1 , March 2000 , pp. 1 - 18
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.)

References

[1] Baccelli, F. and Brémaud, B. (1994). Elements of Queueing Theory. Springer, Berlin.Google Scholar
[2] Chew, P. (1986). There is a planar graph almost as good as the complete graph. In Proc. 2nd Symp. on Computational Geometry. Yorktown Heights, NY, pp. 169–177.Google Scholar
[3] Gondran, M. and Minoux, M. (1979). Graphes et Algorithmes. Editions Eyrolles, Paris.Google Scholar
[4] Howard, C. and Newman, C. (1997). Euclidean models of first-passage percolation. Prob. Theory Relat. Fields 108, 153–170.Google Scholar
[5] Keil, M. and Gutwin, C. (1992). Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom., 7, 13–28.Google Scholar
[6] Kingman, J. (1973). Subadditive ergodic theory. Ann. Prob. 1, 883–909.Google Scholar
[7] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Springer, Berlin.Google Scholar
[8] Okabe, A., Boots, B. and Sugihara, K. (1992). Spatial Tessellations. John Wiley, New York.Google Scholar
[9] Stoyan, D., Kendall, W. and Mecke, J. (1995). Stochastic Geometry and its Applications. John Wiley, New York.Google Scholar
[10] Tchoumatchenko, K. (1999). A Modeling of Communication Networks using Stochastic Geometry. { }, University of Nice-Sophia Antipolis.Google Scholar
[11] Vahidi-Asl, M. and Wierman, J. (1990). First-passage percolation on the Voronoi tessellation and Delaunay triangulation. In Random Graphs '87, eds Karoński, M. and Ruciński, A.. John Wiley, New York.Google Scholar