ImageAnalStereol2009;28:155-163 OriginalResearchPaper CAPACITYDISTRIBUTIONSINSPATIALSTOCHASTICMODELS FOR TELECOMMUNICATIONNETWORKS FLORIANVOSS1,CATHERINE GLOAGUEN2ANDVOLKERSCHMIDT1 1Ulm University,Institute ofStochastics,Ulm, Germany;2OrangeLabs,Issyles Moulineaux,France e-mail: florian.voss@uni-ulm.de (AcceptedSeptember1,2009) ABSTRACT Weconsiderthestochasticsubscriberlinemodelasaspatia lstochasticmodelfortelecommunicationnetworks andwe are interestedin the evaluationofthe requiredcapac itiesat differentlocationsof the networkin order to provide, in fine, an estimation of the cable system which ha s to be installed. In particular, we consider hierarchical telecommunication networks with higher–lev el components(HLC) and lower–level components (LLC)locatedontheroadsystemunderlyingthenetwork. The cablepathsaremodeledbyshortestpathsalong the edge set of a stationary random tessellation, whereas bo th HLC and LLC are modeled by Cox processes concentrated on the edges of this tessellation. We then intr oduce the notion of capacity which depends on the lengthofsome subtreeon the edgeset ofthe underlyingte ssellation. Moreover,we investigateestimators forthe densityand distributionfunctionof the typicallen gth of thissubtree which can be computedbased on Monte Carlo simulations of the typical serving zone. In a num erical study, the density of the typical subtree lengthisdeterminedfordifferentspecific models. Keywords:pointprocesses,randomtessellations,stochas tic geometry,telecommunicationsystems. INTRODUCTION A statistical method based on spatial stochastic modeling is proposed in order to analyze required capacities in hierarchical telecommunication networks. The networks considered in this paper possess higher-level components (HLC) and lower- level components (LLC) located on the cable system ofthenetwork.With eachHLCadomainisassociated which is called the serving zone of this HLC. All LLC within a serving zone are then connected to its HLC on the shortest path along the road system. Recently, such telecommunication networks have been studied in the context of the stochastic subscriber line model (SSLM), where a method has been developed to estimate the mean typical shortest path length and the mean typical subscriber line length from LLC to HLC (Gloaguen et al., 2009a). Note that the SSLM is particularly suitable in the analysisoftelecommunicationaccessnetworks. Further methods for the analysis and optimization of telecommunication networks based on spatial stochastic models have been developed, e.g., in Baccelli and Zuyev (1996), Baccelli et al.(2000), and BaccelliandBłaszczyszyn(2001). We investigate a network characteristic which is related to the typical shortest path length in the SSLM. In particular, we are interested in the distribution of capacities required at different locations of the network. The required capacity is an important characteristic in the strategic planning oftelecommunication networks. On the one hand, it is too expensive to install cables with large capacities at all locations of the network. On the other hand, it is important that the cable system of the network provides the capacities demanded by the subscribers. However, once the network is built, it is difficult to change the installed cables of the network. So it is essential to know the required capacities at given network locations in advance. Based on our stochastic model, the approach developed in the present paper provides a method to design capacities ofnewnetworksoranalyzeexistingcablesystems. The paper is organizedas follows. First we briefly mention how the density of the typical shortest path length can be estimated, which will be used later on in the paper. Then, we introduce the notion of capacity at given network locations and show how its distributiondependsonthelengthsofsomesubtreesof the network. The consideredlocationsare modeled by point processes, where we concentrate on two special cases. We analyze the capacity required at locations with a given shortest path length to the closest HLC and at network locations chosen at random, respectively. In both cases we derive representation formulae for distributional characteristics of the typical subtree length, which are suitable to construct estimators for these network characteristics based on samplesofthetypicalservingzone.Finally,wepresent the results of a numerical study, where the density of the typical subtree length is determined for different specificmodels. 155 VOSSFET AL:Capacitydistributions (a) PLT (b) PVT Fig. 1.HLCwith theirservingzones(blue)andLLC(green)with shor testpathsalongthe edgeset(red). SHORTESTPATHLENGTHS To begin with we briefly introduce our network model which is based on (marked) point processes, random tessellations and Palm theory. For details on these basic notions from stochastic geometry, see Stoyanet al.(1995) and Schneider and Weil (2008). The cable system is modeled by the edge set T(1)of a stationary and isotropic random tessellation Twith intensity γ=Eν1(T(1)∩[0,1)2), whereν1denotes the1-dimensionalHausdorffmeasure.Forexample, T can be a Poisson line tessellation (PLT), a Poisson– Voronoi tessellation (PVT), or a Poisson–Delaunay tessellation (PDT). The HLC and LLC are modeled as (conditionally independent) Cox processes XHand XLwith linear intensities λℓandλ′ ℓonT(1), where the random driving measure ΛofXHandXLis given by Λ(B) =/tildewideλν1(B∩T(1)),B∈B(R2)with/tildewideλ=λℓand /tildewideλ=λ′ ℓ, respectively. Each point XL,nofXLis then connected to its nearest neighbor of XHwith respect to the Euclidean distance. Thus XL,nis connected to a pointXH,jofXHif and only if XL,nis located in the Voronoi cell ΞH,jofXH,jinduced by XH. Furthermore, we assume that the physical connection betweenXL,nanditsnearestneighborof XHisobtained on the shortest path along the edge set T(1). However, the connection path may lie partly outside ΞH,j. Let s(XL,n)denote the length of this path and considerthe stationarymarkedpointprocess Xs L={(XL,n,s(XL,n))}. The typical mark of Xs Lis called the typical shortest path length. It is denoted by S∗and can formally be defined by the Palm mark distribution of Xs L. Inthe ergodic case, the empirical distribution of the markss(XL,n)belonging to a sampling window W converges to the distribution of S∗ifWunboundedly increases. Thus, S∗can be interpreted as the shortest path length of a location chosen at random among all LLC. Realizations of Xs Lare displayed in Fig. 1. Let TH={ΞH,n}denote the Voronoi tessellation of XH and consider the marked point process {(XH,n,Lo H,n)}, whereLo H,n= (T(1)∩ΞH,n)−XH,n, i.e., the points of XHare labelled with the (centered) segment systems ofT(1)inside the Voronoi cells of TH. The segment systemL∗ Hinside the typical cell of THis then defined asthetypicalmarkof {(XH,n,Lo H,n)}.Notethat L∗ Hcan be split into segments Si,i=1,...,Mwith endpoints Ai,Bisuch that s(Ai)0, letX={Xn}be the point process which consists of all points of {x∈T(1):s(x) =s}, wheres(x)denotes the shortest path length from xto XH,jifx∈LH,j,i.e.,Xis the point process of those points on T(1)with a fixed shortest path length to their HLC which is equal to s. Then, the statement of Theorem2 canbespecifiedin thefollowing way. Theorem3 Foranymeasurableh :[0,∞)→[0,∞), Eh(ν1(T∗ sub)) =λℓ fS∗(s)E/tildewideK ∑ i=1h(ν1(Tsub(/tildewideXi))),(6) where (/tildewideX1,Tsub(/tildewideX1)),...,(/tildewideX/tildewideK,Tsub(/tildewideX/tildewideK))denote the marked points of /tildewideXTon L∗ Hand/tildewideK is (random) total number of these points. In particular, the distribution functionF :R→[0,1]ofν1(T∗ sub)isgivenby F(x) =λℓ fS∗(s)E/tildewideK ∑ i=11 I[0,x](ν1(Tsub(/tildewideXi))),x≥0.(7) ProofUsingEq.4weonlyhavetoshowthat λH/λ= λℓ/fS∗(s). Moreover, since λH=γλℓ, it suffices to showthat λ=γfS∗(s).We havethat λ=E#{n:Xn∈[0,1)2} =E∞ ∑ i=1#{n:Xn∈LH,i∩[0,1)2} =λH/integraldisplay R2E#{n:/tildewideXn∈L∗ H∩([0,1)2−x)}dx, where the latter equality follows from the refined Campbell theorem for stationary marked point processes. Note that each point /tildewideXi,i=1,...,/tildewideKis contained almost surely in exactly one segment of L∗ H and each segment contains 0 or 1 points of /tildewideXT, so /tildewideK≤M. We can assume without loss of generality that/tildewideXi∈Sifori=1,...,/tildewideKand that the segments 158 ImageAnalStereol2009;28:155-163 Si,i=/tildewideK+1,...,Mdonotcontainapointwithshortest path length s.Thisyields λ=λH/integraldisplay R2E#{n:/tildewideXn∈L∗ H∩([0,1)2−x)}dx =γλℓE/tildewideK ∑ j=11 I[s(Aj),s(Bj))(s)/integraldisplay R21 I[0,1)2−/tildewideXj(x)dx =γλℓE/tildewideK ∑ j=11 I[s(Aj),s(Bj))(s) =γfS∗(s), where the latter equality follows from Lemma 1. This completestheproof. Note that fS∗(s)is not known analytically, but it canbeestimatedconsistentlybytheestimator /hatwidefS∗(x;n) given in Eq. 1. Thus, Theorem 3 leads to a natural estimatorfor F(x)whichisgivenby /hatwideF(x;n) =λℓ /hatwidefS∗(x;n)1 nn ∑ j=1/tildewideK(j) ∑ i=11 I[0,x](ν1(T(j) sub(/tildewideX(j) i))), (8) where /tildewideK(j)andT(j) sub(/tildewideX(j) i),j=1,...,narei.i.d.copies of/tildewideKandν1(Tsub(/tildewideXi)), respectively. It is easy to see that/hatwideF(x;n)is ratio–unbiased and strongly consistent forF(x). Moreover, since Fis continuous, it can be easilyshownthat P(lim n→∞sup x∈R|/hatwideF(x;n)−F(x)|=0) =1. RANDOMLOCATIONS In this section we assume that X={Xn}is a Cox process with linear intensity λ′′ ℓ=λ/γonT(1), which is conditionally independent of XHandXL, givenT(1). Recall that L∗ Hcan be split into segments Si,i=1,...,Mwith endpoints Ai,Bisuch that s(Ai)< s(Bi) =s(Ai) +ν1(Si). This leads to the following representation formula for the density f:R→[0,∞) of the typical subtree length ν1(T∗ sub), which is similar to the formula stated in Lemma 1 for the density fS∗ ofS∗. Theorem4 Itholdsthat f(x) =  λℓE/bracketleftbiggM ∑ i=11 I[l(Bi),l(Ai))(x)/bracketrightbigg ifx≥0, 0 otherwise, where l (Bi)denotes the subtree length at B i∈L∗ Hand l(Ai) =ν1(Si)+l(Bi).Note that Theorem 4 can be proven directly using Theorem 2 and the assumption that {Xn}is a Cox process on T(1). However, interestingly enough, there is an alternative proof which uses the following relationship between the distribution of the typical subtree length ν1(T∗ sub)at the points of {Xn}and the typical subtree length at the locations of the point process {Xs,n}with fixed shortest path length s consideredinthe precedingsection. Lemma2 Lets∈[0,∞),then itholdsthat P(ν1(T∗ sub)≤x|S∗ X=s) =Fs(x),(9) whereS∗ Xdenotestheshortestpathlengthatthetypical point of X and F sdenotes the distribution function introducedinEq. 7forfixedshortestpathlengths. ProofLet/tildewideKsand/tildewideXs,1,...,/tildewideXs,/tildewideKsbe the random variables which have been introduced in Theorem 3 for fixed s∈[0,∞),i.e.,s(/tildewideXs,i) =sfori=1,...,/tildewideKs, where /tildewideKsis the number of points on L∗ Hwith shortest path length sto the origin. Moreover, let /tildewideX={/tildewideXn} denote the Palm version of Xwith respectto the Palm distribution of XH. Since the density fS∗(s)does not depend on the intensity λ′ ℓof the underlying Cox process {XL,n}of LLC, see Lemma 1, the equality fS∗(s) =fS∗ X(s)holds almost everywhere. Thus we have P(ν1(T∗ sub)≤x|S∗ X=s) =lim εց0P(ν1(T∗ sub)≤x|S∗ X∈[s,s+ε)) =lim εց0E/parenleftBig 1 I[0,x](ν1(T∗ sub))1 I[s,s+ε)(S∗ X) /integraltexts+ε sfS∗ X(u)du/parenrightBig =lim εց0λℓ λ′′ ℓE∑ /tildewideXn∈L∗ H1 I[0,x](ν1(Tsub(/tildewideXn)))1 I[s,s+ε)(s(/tildewideXn)) /integraltexts+ε sfS∗(u)du =λℓlim εց0E/integraldisplay L∗ H1 I[0,x](ν1(Tsub(y)))1 I[s,s+ε)(s(y)) /integraltexts+ε sfS∗(u)duν1(dy), where the last but one equality is obtained by a slight modification of Theorem 2 and the last equality follows from the fact that the points {/tildewideXn}form a Cox process on L∗ Hwith linear intensity λ′′ ℓ, see Fleischer et al.(2009). We can divide L∗ Hinto the segments S1,...,SMasbefore andget P(ν1(T∗ sub)≤x|S∗ X=s) =λℓlim εց0EM ∑ i=1/integraldisplay Si1 I[0,x](ν1(Tsub(y)))1 I[s,s+ε)(s(y)) /integraltexts+ε sfS∗(u)duν1(dy). 159 VOSSFET AL:Capacitydistributions Furthermore, fS∗is right-continuous, thus we have almostsurely lim εց0M ∑ i=1/integraldisplay Si1 I[0,x](ν1(Tsub(y)))1 I[s,s+ε)(s(y)) /integraltexts+ε sfS∗(u)duν1(dy) =1 fS∗(s)/tildewideKs ∑ i=11 I[0,x](ν1(Tsub(/tildewideXs,i))). Since /integraldisplay Si1 I[0,x](ν1(Tsub(y)))1 I[s,s+ε)(s(y)) /integraltexts+ε sfS∗(u)duν1(dy) ≤/integraldisplay Si1 I[s,s+ε)(s(y)) εminx∈[s,s+1)fS∗(x)ν1(dy) ≤1 minx∈[s,s+1)fS∗(x)<∞, we can use the dominated convergence theorem in orderto get P(ν1(T∗ sub)≤x|S∗ X=s) =λℓ fS∗(s)E/tildewideKs ∑ i=11 I[0,x](Tsub(/tildewideXs,i)) =Fs(x), whichcompletesthe proof. Note that Lemma 2 states that the distribution function Fscan be regarded as the conditional distribution functionof ν1(T∗ sub)giventhat S∗ X=s. We nowusethisrelationshipin orderto proveTheorem4. ProofofTheorem4 Foreachx≥0Lemma2 yields F(x) =E(P(ν1(T∗ sub)≤x|S∗ X)) =/integraldisplay∞ 0P(ν1(T∗ sub)≤x|S∗ X=s)fS∗ X(s)ds =/integraldisplay∞ 0Fs(x)fS∗ X(s)ds =/integraldisplay∞ 0λℓ fS∗(s)E/tildewideKs ∑ i=11 I[0,x](Tsub(/tildewideXs,i))fS∗ X(s)ds, where the latter equality follows from Eq. 7 and /tildewideKs,/tildewideXs,1,...,/tildewideXs,/tildewideKsare the random variables introduced in the proof of Lemma 2. Since fS∗(s) =fS∗ X(s)for almostall s∈[0,∞),we have F(x) =λℓE/integraldisplay∞ 0/tildewideKs ∑ i=11 I[0,x](Tsub(/tildewideXs,i))ds =λℓEM ∑ i=1/integraldisplayl(Ai) l(Bi)1 I[0,x](s)ds =/integraldisplayx 0λℓEM ∑ i=11 I[l(Bi),l(Ai))(s)ds,whichprovesthe theorem. For each x≥0, Theorem 4 leads to the natural estimator /hatwidef(x;n) =λℓ1 nn ∑ j=1M(j) ∑ i=11 I[l(B(j) i),l(A(j) i))(x),(10) forf(x)which is based on nindependent and identically distributed copies of L∗ H. Clearly, /hatwidef(x;n)is unbiased and strongly consistent for f(x). For further usefulpropertiesof /hatwidef(x;n),seeVoss etal.(2009c). NUMERICALRESULTS We now consider two specific examples assuming thatTis a PLT or PVT, respectively. Then, it is not difficult to show that the distribution function F of the typical subtree length ν1(T∗ sub), considered in Eq. 7 for network locations with a fixed distance to their HLC, has a density. To see this, suppose that the typical segment system L∗ Hand the marked points (/tildewideX1,Tsub(/tildewideX1)),...,(/tildewideX/tildewideK,Tsub(/tildewideX/tildewideK))as well as the random tessellation T∗with respect to the Palm distribution of XHare given. If we only condition on T∗, the distribution of ∑/tildewideK i=11 IB(ν1(Tsub(/tildewideXi)))does not changeifeachHLCisreplacedbyanewHLCwhichis uniformlydistributedonthesamesegment.Underthis transformationthepointswithshortestpathlength son T∗arenotchanged,butsomenewpointsmaylieon L∗ H andsomepointsmaynotlieon L∗ Hanymore.However, thesubtreelengths Tsub(/tildewideXi),i=1,2,...arechangedin a continuous and non-constant way with probability one if HLC are shifted along the segments. Thus ∑/tildewideK i=11 IB(ν1(Tsub(/tildewideXi))) =0 almost surely if ν1(B) =0 and hence the distribution of ν1(T∗ sub)is absolutely continuous. Moreover, a scaling invariance can be observed if the scaling factor κ=γ/λℓis fixed,i.e., the structure of the network model is fixed, but on different scales (Gloaguen et al., 2009b; Voss et al., 2009a). We thus used the estimators introduced in the preceding sections to determine the density f(x)of the typical subtree length ν1(T∗ sub)for different values of κbased on i.i.d. samples of L∗ Hwhich were generated using simulation algorithms introduced in Gloaguen et al. (2005)andFleischer etal.(2009).Foreachrealization ofL∗ Hfirst the shortest path from oto all nodes of L∗ H were computed using Dijkstra’s algorithm (Dijkstra, 1959). In a second step, segments with distance peak were split and in this way L∗ Hwas transformed into a tree structure, the shortest path tree. Note that the distancepeaksare the leavesof the tree. Basedon this 160 ImageAnalStereol2009;28:155-163 0100200300400500600700 0 0.001 0.002 0.003 0.004 0.005 0.006 0.007f(x) xκ=100 κ=200 κ=300 κ=500 κ=700 κ=1000 (a) PLT050100150200250300350400450500550 0 0.001 0.002 0.003 0.004 0.005 0.006 0.007f(x) xκ=100 κ=200 κ=300 κ=500 κ=700 κ=1000 (b) PVT Fig. 4.Density f of ν1(T∗ sub)for Coxprocesses {Xn}.} 020406080100120140160180200220 0 0.003 0.006 0.009 0.012f(x) xPLTs=0.02 PVTs=0.02 PLTs=0.04 PVTs=0.04 (a)κ=300050100150200250300350400450500 0 0.0015 0.003 0.0045 0.006f(x) xPLTs=0.02 PVTs=0.02 PLTs=0.04 PVTs=0.04 (b)κ=700 Fig. 5.Density f of ν1(T∗ sub)for fixeddistances toHLC. tree we computed the subtree length l(Bi)andl(Ai) at the segment endpoints Ai,Bi,i=1,...,M. These results were then directly used for the computation of theestimator /hatwidef(x;n)inEq.10.Inordertocomputethe estimator /hatwideFs(x;n)in Eq. 8 we first chose the segments Si,i=1,...,/tildewideKwiths(Ai)≤s