Poisson-Voronoi Spanning Trees with Applications to the Optimization of Communication Networks

François Baccelli and Sergei Zuyev
Additional contact information
François Baccelli: INRIA-École Normale Supérieure, Département de Mathématiques et d'Informatique, LIENS, 45 Rue d'Ulm, 75230 Paris, Cedex 05, France
Sergei Zuyev: Statistics and Modelling Science Department, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, UK

Operations Research, 1999, vol. 47, issue 4, 619-631

Abstract: We define a family of random trees in the plane. Their nodes of level k , k = 0, …, m are the points of a homogeneous Poisson point process Π k , whereas their arcs connect nodes of level k and k + 1, according to the least distance principle: If V denotes the Voronoi cell w.r.t. Π k +1 with nucleus x , where x is a point of Π k +1 , then there is an arc connecting x to all the points of Π k that belong to V . This creates a family of stationary random trees rooted in the points of Π m . These random trees are useful to model the spatial organization of several types of hierarchical communication networks. In relation to these communication networks, it is natural to associate various cost functions with such random trees. Using point process techniques, like the exchange formula between two Palm measures, and integral geometry techniques, we show how to compute these average costs as functions of the intensity parameters of the Poisson processes. The formulas derived for the average value of these cost functions can then be exploited for parametric optimization purposes. Several applications to classical and mobile cellular communication networks are presented.

Keywords: probabiltiy; stochastic model applications; networks/graphs; stochastic; communications; transportation; network models (search for similar items in EconPapers)
Date: 1999
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.4.619 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:4:p:619-631

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().