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

Abstract

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+1with nucleus x, where xis a point of Π_k+1, then there is an arc connecting xto all the points of Π_kthat 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.