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

We define a family of random trees in the plane. Their nodes of level k, k= 0, …, mare the points of a homogeneous Poisson point process Π k , whereas their arcs connect nodes of level kand k+ 1, according to the least distance principle: If Vdenotes the Voronoi cell w.r.t. Π k +1 with nucleus x, where xis a point of Π k +1 , then there is an arc connecting xto 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.