Analytical investigation of intersection based range-free localization

Abstract

The localization of mobile devices is essential for the provisioning of location-based services, e.g., to locate people facing an accident or to provide relevant information to device users, depending on their current whereabouts. Several localization mechanisms have been developed using estimates of absolute distances or angles between the devices and the base stations of the networks. These mechanisms often require expensive enhancements of the existing base stations or mobile devices. In recent years, so-called range-free approaches have been proposed, which limit the possible positions of a device to the coverage areas of radio network cells, without relying on precise distances or angles. The accuracy of the corresponding information can be refined by computing the intersection area of all cells that cover the current position of the device. However, the computation of this intersection area, e.g., by the location server of a network carrier, can be a complex task. To avoid unnecessary workload, one would like to preestimate the possible reduction of location uncertainty, i.e., the information gain that can be achieved. The contribution of this paper is an analytical and numerical investigation of the problem. Several approaches are presented for the computation of the information gain, based on stochastic geometry and on a Monte-Carlo method. We show that simple scaling arguments can be used to estimate the order of magnitude of the average information gain, while more complex approximations based on Voronoi cells lead to relatively good results.

1 Introduction

The provisioning of location-based services [1] for users of mobile and mostly wireless devices requires proper knowledge about their current geographical positions. Because most mobile devices, such as notebooks, personal digital assistants, or cellular phones, are unable to determine their positions on their own, e.g., by means of a global positioning system, they rely on the support of the network for this task.

Several proposals have been made in recent years for the determination of device positions. These can be classified in range-based and range-free approaches (see [2]). For the range-based mechanisms, the distance (trilateration) or the angle (triangulation) between a mobile device and at least three of its currently available base stations is required. Based on this information and a precise knowledge of the positions of the stations, the location of the mobile device can be computed. However, determining such distances or angles can be rather difficult, and the inaccuracy might be quite high. Additionally, the realization of range-based mechanisms often requires costly enhancements of the mobile devices or base stations, like special location measurement units [3].

As long as no additional mechanisms are being deployed, the determination of the positions can be achieved by so-called range-free approaches. Statements about a position can be obtained via information about the base stations that can communicate with a mobile device at its current position, without relying on estimates of absolute distances or angles.

Range-free approaches use different algorithms and information about the base stations to give an estimate for the current location of a mobile device. A convenient mechanism uses approximations of base station coverage areas. These areas can be acquired by the mobile devices and provided by respective databases [4]. In other cases, the carriers of a wireless network possess detailed descriptions of the deployed network equipment being used for network planning [5], which can also be used to obtain estimates of the coverage areas. If a mobile device finds itself in the overlapping coverage areas of several base stations at once, the intersection of these areas will be geometrically computed, and the possible positions of the device can be limited to this intersection area.

Computing the intersection of base station coverage areas can be a complex task. Thus, it is desirable to have estimates about the potential refinement of the location information before performing the computation. Because we are interested in the uncertainty of location information, i.e., the entropy of the random variable associated with the exact position of a device, we will use the term information gain for the reduction of this entropy. In the sequel, we focus on analytical investigations of the information gain. Different approaches to the computation of the information gain are investigated, based on stochastic geometry and a Monte-Carlo method.

The rest of the paper is organized as follows: related work is presented in the next section. In Section 3, a model for the considered system is described. Then, in Section 4, the notion of information gain that will be used in the sequel is presented. In Section 5, several approaches for the determination of the information gain are displayed. Some significant numerical results are presented in Section 6, and the last section concludes the paper by giving an outlook into the next steps of our ongoing work.

2 Related work

If the information of a single station is used for range-free localization, the accuracy depends critically on the cell size. For certain technologies with small transmission ranges, like Bluetooth, it might be sufficient. However, other radio cells can cover large parts of a geographical territory, and using a single base station to localize a mobile device might lead to a very coarse position information.

The accuracy can be significantly enhanced by using the information from several stations. In this section, the basics of the existing range-free approaches and the mechanisms for the computation of the device positions will be presented. Some of these have originally been proposed in the context of wireless sensor or ad-hoc networks, but the algorithms are almost independent of the underlying technologies and can also be deployed in other wireless networks.

Centroid computation The authors of [6] propose a mechanism that relies on the deployment of location-aware nodes in a wireless sensor network. If another node wants to determine its whereabout, it will listen to beacon signals of all the location-aware nodes that can be received at its current position. The device is assumed to be located at the centroid of the positions of these nodes. However, computing such centroids yields no information regarding the accuracy of this positioning method. Figure 1 shows the deployment of the mechanism in a wireless network.

Fig. 1

Using the centroids of location-aware nodes (e.g., base stations) for localization

Intersection area computation Using the intersection area of different coverage areas has been proposed in [7]. The authors present a distributed algorithm for the localization of nodes in ad hoc networks. Some of the nodes are assumed to be location-aware, other nodes determine their positions by computing the intersection of the coverage areas of the location-aware nodes. For computational simplicity, the algorithm uses a discretization of positions and rectangular coverage areas (see Fig. 2). In [8], an analytical investigation of the intersection protocol is presented, assuming circular coverage areas of the nodes (Fig. 3). Additionally, the authors present and analyze an enhancement of the protocol that achieves the same accuracy but halves the number of required location-aware nodes.

Fig. 2

Simplified computation of an intersection area for localization

Fig. 3

Intersection area based approach, using circular coverage areas

In [9], a cell-ID-based location-sensing method for wireless networks is proposed, using the intersection area of different base stations for localization. In this paper, the positioning accuracy of the mechanism is computed assuming the base stations are aligned in a hexagonal or mesh structure. Additionally, the optimal accuracy is computed when the transmission power of the stations can be modified for localization purposes. The authors use circular coverage areas of the base stations for their computation. All of the presented approaches for location determination assume circular coverage areas of the nodes or stations being used for the localization, without taking the interference between their radio signals into account.

Approximate point in triangulation test The authors of [2] present a localization algorithm that partitions the geographical territory into triangular regions with location-aware nodes as vertices. These nodes send beacons with their positions to other nodes whose positions should be determined. For localization purposes, a node uses the positions in the beacons that it can currently receive, determines the resulting triangles, and checks whether its current position lies inside the triangles. The intersection region of all triangles returning a “true” result is then computed, and the node is assumed to be located at the center of gravity of this region (see Fig. 4). A perfect test as to whether the current position lies within a given triangle could hardly be realized. Thus, the protocol relies on approximations of the test results.

Fig. 4

Using the (approximate) point in triangulation test for localization

From a mathematical standpoint, previous work has been achieved most noticeably in [10]. This paper contains, amongst other results, a first mathematical study of intersections $\left( C^A\cap C^B\right)$, where C ^A and C ^B are the cells covering a fixed reference point in two independent and stationary Poisson–Voronoi tessellations. However, statements regarding the probabilistic distribution of $\left( C^A\cap C^B\right)$ are essentially limited to a computation of the mean value of its area.

3 System model

We consider a large geographical territory T having an area size |T|. The territory is covered by a wireless network. The network has a set of base stations S, and the members of the set are denoted by $\mathit{s}$.

Coverage model To estimate the base station coverage areas, we use a simplified model (see [11]), which has been widely deployed for information theoretical analyses, e.g., in [12]. The pathloss, i.e., the weakening of the received signal power P _RX between a base station located at position X _i and a mobile device at position U during the transmission, is computed via

$$P_{RX}=P_{TX}\cdot\frac{K}{|U-X_i|^\alpha}$$

(1)

P _TX denoting the power transmitted by the base station. The constant K and distance power gradient α approximate the attenuation characteristics of the considered environment (see [13]). As long as the strength of the received signal and the ratio between the signal and some received noise (SNR) remain above a certain threshold, a communication with the station is possible and the device is in its coverage area.

Assuming that the signals of the different base stations do not interfere at the receiver, the SNR can be computed via

$$\mathrm{SNR}=\frac{P_{RX}}{P_N}$$

(2)

P _N denoting the equivalent power of the noise.

Network model In real scenarios, base stations can sometimes only be installed at a limited number of suitable locations, e.g., on certain rooftops. Such restrictions lead to spatial variability for the locations and density of the base stations.

Following [14], we model the positions of the base stations as realizations of a stationary Poisson point process to take this spatial variability into account. Accordingly, letting λ denote the intensity of the base stations process (mean number of base stations per square kilometer), the probability for the total number of base stations |S| in the territory to be n is given by

$$p(n)=\mathbb{P}[|S|=n]=\frac{e^{-\lambda^{}|{T}|} (\lambda^{}|{T}|)^n}{n!}$$

(3)

and, conditionally to |S| = n, the n positions of the base stations are distributed independently and uniformly over the territory T.

The set of base stations S consists of several subsets of stations S _j  ⊂ S. All stations whose radio transmissions heavily interfere with each other belong to the same subset j (e.g., cochannel interference of base stations using the same frequency in IEEE 802.11 WLAN). For stations of different subsets, we assume that the interference between them is negligibly small due to respective characteristics of the filters in the transceivers.

The subsets of the base stations are modeled according to the entire set S. The spatial variability of the base stations of a subset is modeled by a Poisson point process with density λ _j , where ∑  _j λ _j  = λ.

The territory under consideration is populated by a set of mobile devices M. If required, a certain device m ∈ M can determine the ID of the base station in whose coverage area it currently resides. For the interfering base stations of a single subset, we assume that only the station with best SNR can be determined.

If the parameters of all base stations are equal, the last assumption leads to a determination of the station of each subset being closest to the current position of a mobile device. The partitioning of the geographical territory by the coverage areas of the stations leads to a Voronoi tessellation [15] of the territory with the station positions as nuclei (see Fig. 5). Considering the model for the placement of the stations, such partitioning of the territory T is also called a Poisson-Voronoi tessellation.

Fig. 5

Coverage areas of two different base station subsets using a Poisson–Voronoi model

4 The notion of information gain

Taking only the information of a first base station s _A into account (“The user of device m finds himself in cell C ^A attached to base station s _A ”) allows one to consider that the exact position of the user is a random variable U that is uniformly distributed over the cell C ^A. The entropy of such a random variable is simply given as the logarithm of the total surface |C ^A| of the corresponding cell (see [16]).

Now, when one is also taking the information of a second base station s _B into account (“The user of device m finds himself in cell C ^B attached to base station s _B ”), the exact position of the user becomes a random variable that is uniformly distributed over $\left( C^A\cap C^B\right)$. Here again, the entropy attached to such a uniformly distributed random variable is simply the logarithm of the corresponding total surface, i.e., log(|C ^A ∩ C ^B|). This means that the information gain G obtained by taking both informations into account simultaneously (instead of just the first one) may be quantified as

$$G=\log(|C^A|)-\log(|C^A\cap C^B|)$$

(4)

Hence, C ^A and C ^B denoting the cells covering a given reference point in each network, one is particularly interested in the distribution of the random variable $\log\left(\frac{|C^A|}{|C^A\cap C^B|}\right)$.

5 Computing the information gain

In this section, we present several approaches to the computation of the information gain, discussing first the use of random tessellations and then the implementation of Monte-Carlo methods.

In the sequel, we will be assuming that the networks under consideration are spatially stationary and that user localizations are being performed a large number of times (N times), so that if the user of device m _k be reported to find himself in cell $C_{m_k}^A$, as well as in cell $C_{m_k}^B$, then

$$\frac{1}{N}\sum_{k=1}^N\log\!\left(\!\frac{|C_{m_k}^A|}{|C_{m_k}^A\cap C_{m_k}^B|}\!\right) \!\!\approx\mathbb{E}\left[\!\log\left(\!\frac{|C^A(O)|}{|C^A(O)\cap C^B(O)|}\!\right) \!\right],$$

where C ^A(O) stands for the cell in the first network that happens to cover an arbitrary fixed point, taken to be the origin O of the plane, and C ^B(O) stands for the corresponding cell in the second network. The above approximation uses the law of large numbers (the user locations are assumed to be independent and uniformly distributed over the territory) together with Wiener’s ergodic theorem, which holds true for any stationary random tessellation of the plane satisfying a mixing condition (see the Appendix for more precise statements and further references). In any of the cellular network models we shall be considering, be it the model described in Section 3 or a simplified Poisson–Voronoi tessellation model, or even some simpler model of the network at hand, we are thus using the fact that the cellular network may be viewed as a realization of a stationary random tessellation satisfying a mixing property, as well as the fact that the true locations of the successive users are mutually independent and uniformly distributed over the territory.

At any rate, this leaves us with the basic task of computing mean values such as $\mathbb{E}\left[ \log(|C^A(O)|)\right]$ or $\mathbb{E}\left[ \log(|C^A(O)\cap C^B(O)|)\right]$. As we shall see, there are several approaches to these computations. The choice of a relevant approach depends in an essential way on the model chosen for the cellular network.

5.1 Using a Poisson–Voronoi tessellation

Assume both cellular networks are being modelled as Poisson–Voronoi tessellations of the plane: the base stations of the first (resp. second) network are thus spread upon the territory according to a Poisson point process $\left\{ X^A_i\right\}$ of intensity $\lambda^{A} \big(\text{resp.} \big\{ X^B_j\big\}\text{of intensity}$ $\lambda^{B}\big)$, and a device m located at the position U belongs to the cell $C^A_i$ attached to the ith base station in the first network whenever its distance to $X^A_i$ is smaller than its distance to any other base station in the first network (see Fig. 5). The cell $C^B_j$ attached to the jth base station in the second network is defined similarly. For a typical realization of the Poisson random clouds $\left\{ X^A_i\right\}$ and $\big\{ X^B_j\big\}$, there is precisely one cell C ^A(O) in the first network covering the origin O in the plane, as well as one cell C ^B(O) covering the origin in the second network. Having in mind a computation of the stochastic mean values mentioned above, one would like to get a hold of the distribution functions attached to the random variables |C ^A(O)| and |C ^A(O) ∩ C ^B(O)|. Interestingly, some recent works [17] have shown that an explicit computation of the distribution function attached to the area |C ^A(O)| is possible. To give a brief description of this distribution function, let us present another kind of random cell commonly considered in such a context: the Palm cell $\mathcal{C}^A$, constructed from a typical realization of the Poisson cloud $\left\{ X^A_i\right\}$, may be defined to be the set of all points lying closer to O than to any other point in the cloud (so it is simply the new cell obtained by adding the point O to the original cloud). The construction shows that $\mathcal{C}^A$ is smaller than the cell C ^A(O) considered precedingly. However, as a consequence of Campbell’s formula (see [18]), each of the main geometric characteristics of the random cells C ^A(O) and $\mathcal{C}^A$ (area, perimeter, number of sides) has a distribution that may be seen to be closely related to each other via an “area bias.” For example, the first moment of the area |C ^A(O)| may be obtained by multiplying the second moment of $|\mathcal{C}^A|$ through the intensity λ ^A:

$$\mathbb{E}\left[ |C^A(O)|\right]=\lambda^{A}\mathbb{E}\left[ |\mathcal{C}^A|^2\right] =\frac{\mathbb{E}\left[ |\mathcal{C}^A|^2\right]}{\mathbb{E}\left[ |\mathcal{C}^A|\right]}.$$

More generally, for moments of higher order, one has

$$\mathbb{E}\left[ |C^A(O)|^k\right]=\lambda^{A}\mathbb{E}\left[ |\mathcal{C}^A|^{k+1}\right],$$

and for the logarithms of the areas:

$$\mathbb{E}\left[ \log|C^A(O)|\right]= \lambda^{A}\mathbb{E}\left[ |\mathcal{C}^A|\cdot\log|\mathcal{C}^A|\right].$$

(5)

On the other hand, [17] provides us with an explicit expression for the density function of the random variable $|\mathcal{C}^A|$. This in turn enables the computation of probabilities such as $\mathbb{P}\left\lbrace |\mathcal{C}^A|\geq x\right\rbrace$ or $\mathbb{P}\left\lbrace |\mathcal{C}^A|\leq x\right\rbrace$, and one then has:

$$\begin{aligned}&\mathbb{E}\left[ |\mathcal{C}^A|\cdot\log|\mathcal{C}^{A}|\right] \\ & \quad =\mathbb{E}\left[\int_1^{|\mathcal{C}^{A}|}(1+\log x)dx\right] \\ & \quad =\int_1^{+\infty}(1+\log x)\mathbb{P}\left\lbrace |\mathcal{C}^{A}|\geq x\right\rbrace dx \\ & \qquad -\int_0^{1}(1+\log x)\mathbb{P}\left\lbrace |\mathcal{C}^{A}|\leq x\right\rbrace dx. \end{aligned}$$

(6)

So, in the context of Poisson–Voronoi tessellations, the first half of our task, namely, computing the stochastic mean value of log|C ^A(O)|, may be achieved analytically. However, it turns out that the explicit expression of the density function attached to $|\mathcal{C}^A|$ is not particularly easy to handle, its integration necessitating the use of numerical methods (see the Appendix).

More importantly, it seems that an explicit computation of the distribution associated with the random variable |C ^A(O) ∩ C ^B(O)| remains completely out of reach (reference [10] only has an explicit expression for the mean value of |C ^A(O) ∩ C ^B(O)|). A central difficulty here is that the compound tessellation, obtained by superimposing the cells of the second network to those of the first one, is of a truly new kind: some of the new cells thus obtained contain no base station at all, some other cells have just one base station (of the first or of the second network), some other cells contain two base stations (one of each network), and there is no obvious way in which one could come back to the earlier setting (e.g., by trying to attach one “virtual station” to each of the new cells). Having faced this essential difficulty, one may turn to a further simplification of the cellular network modelling, which allows for an explicit computation of the information gain via scaling arguments, or else opt for a numerical evaluation of the information gain, in which case some other network models may be implemented (see [12]). These two complementary approaches are presented in the following paragraphs.

5.2 Scaling arguments

One way of circumventing the difficulties alluded to above would be to change the notion of cell used in the modelling of the network, e.g. by replacing the Poisson–Voronoi tessellations through Poisson line tessellations: for a given realization $\left\lbrace Y^A_i\right\rbrace$ of a Poisson random cloud, the corresponding line tessellation is defined by drawing a straight line $\Delta^A_i$ through each point $Y^A_i$, in such a way that the segment joining the origin O to $Y^A_i$ be orthogonal to $\Delta^A_i$ (see Fig. 6). This procedure yields a (very rough) model for the cells of the first network, and the cells in the second network could be modelled similarly, using a second random cloud $\big\{ Y^B_j\big\}$ independent of the first one. Note, however, that these two clouds should be given intensity measures proportional to $d\rho d\theta=\frac{dxdy}{\sqrt{x^2+y^2}}$ to ensure that the resulting tessellations are stationary (see the Appendix for more details). Letting, thus, λ ^A dρ dθ be the intensity measure of the first cloud and λ ^B dρ dθ be the intensity measure of the second one, we are then in the advantageous situation where the tessellation obtained through a superposition of the first line tessellation and of the second one is of the same nature: it is precisely the line tessellation associated with the cumulated cloud $\big(\big\lbrace Y^A_i\big\rbrace\cup\big\{Y^B_j\big\}\big)$. This last cloud is, again, a Poisson random cloud, of intensity measure λ ^C dρ dθ, where λ ^C = λ ^A + λ ^B. Hence, each of the three Poisson random clouds $\big\lbrace Y^A_i\big\rbrace, \big\lbrace Y^B_j\big\rbrace, \big(\big\lbrace Y^A_i\big\rbrace\cup\big\lbrace Y^B_j\big\rbrace\big)$ may be obtained as a dilation about the origin of an auxiliary Poisson cloud $\big\lbrace Z_i\big\rbrace$ having the intensity measure dρ dθ, the dilation factors being $1/\sqrt{\lambda^{A}},1/\sqrt{\lambda^{B}}$ and $1/\sqrt{\lambda^{C}}=1/\sqrt{\lambda^{A}+\lambda^{B}}$, respectively. Letting $C_O(\left\lbrace Z_i\right\rbrace)$ denote the cell covering the origin in the Poisson line tessellation associated with $\left\lbrace Z_i\right\rbrace$, and using dilations about the origin to represent $\left\lbrace Y^A_i\right\rbrace$, as well as $\big( \big\lbrace Y^A_i\big\rbrace\cup\big\lbrace Y^B_j\big\rbrace\big)$, one then finds out that the corresponding information gain may be simply quantified as

$$\log\left(\frac{1}{\lambda^{A}}\right)-\log\left(\frac{1}{\lambda^{A}+\lambda^{B}}\right) = \log\left(1+\frac{\lambda^{B}}{\lambda^{A}}\right)$$

(7)

Note that such concise expression of the information gain could also be obtained in the context of Poisson–Voronoi tessellations, again via scaling arguments: one would simply need to replace the true compound Poisson–Voronoi tessellation $\mathcal{T}^{Comp}$ by the Poisson–Voronoi tessellation $\mathcal{T}\big( \big\lbrace X^A_i\big\rbrace\! \cup\! \big\lbrace X^B_j\big\rbrace\big)$ associated with the cumulated cloud $\big( \big\lbrace X^A_i\big\rbrace \cup \big\lbrace X^B_j\big\rbrace\big)$. Actually, this kind of scaling argument may be significantly improved by taking into account the fact that the cells in the compound tessellation $\mathcal{T}^{Comp}$ tend to be smaller than those of $\mathcal{T}\big( \big\lbrace X^A_i\big\rbrace \cup \big\lbrace X^B_j\big\rbrace\big)$. More precisely, by attaching its center of gravity G _k to each cell C _k in the compound tessellation, one obtains a new point process { G _k }, which is again stationary and has the intensity

$$\Lambda^{Comp}(\lambda^A,\lambda^B)=\lambda^A+\lambda^B+\frac{8}{\pi}\sqrt{\lambda^A\lambda^B}$$

(8)

(see [10] for a proof, upon which we expand in the Appendix). This new point process is non-Poissonian; however, the area of the cell about the origin in $\mathcal{T}^{Comp}$ should be close to the area of the corresponding cell in a Poisson–Voronoi tessellation when the intensity of the underlying Poisson process is given the value Λ^Comp(λ ^A,λ ^B). This approximation and a scaling argument lead to the following expression:

$$\log\left(\Lambda^{Comp}(\lambda^A,\lambda^B)\right) \!-\!\log\lambda^A \!=\! \log\left( 1\!+\!\frac{\lambda^{B}}{\lambda^{A}}\!+\!\frac{8}{\pi}\sqrt{\frac{\lambda^B}{\lambda^A}}\right) \label{eq:ig_log} $$

(9)

for the information gain.

Fig. 6

A Poisson line tessellation of the territory

Similarly, considering three independent, homogeneous Poisson clouds of respective intensities λ ^A, λ ^B, λ ^C, and superimposing the cells associated with their Voronoi tessellations, one obtains a new compound tessellation where cells come up with the intensity

$$\Lambda^{Comp}(\lambda^A,\lambda^B,\lambda^C)\!=\!\lambda^A\!+\!\lambda^B\!+\!\lambda^C + \frac{8}{\pi}\left(\sqrt{\lambda^A\lambda^B}\!+\!\sqrt{\lambda^A\lambda^C}\!+\!\sqrt{\lambda^B\lambda^C}\right)$$

(10)

Accordingly, approximating this new compound tessellation through a Poisson–Voronoi tessellation of intensity Λ^Comp(λ ^A,λ ^B,λ ^C) and using a scaling argument enables one to quantify the corresponding information gain as

$$\begin{aligned}&\log\left( \Lambda^{Comp}(\lambda^A,\lambda^B, \lambda^C)\right) -\log\lambda^A \\ & \quad = \log\left( 1+\frac{\lambda^{B}}{\lambda^{A}}+\frac{\lambda^{C}}{\lambda^{A}}\right.\\ & \qquad\qquad\;\; \left. +\frac{8}{\pi}\left(\sqrt{\frac{\lambda^B}{\lambda^A}}+\sqrt{\frac{\lambda^C}{\lambda^A}} +\frac{\sqrt{\lambda^B\lambda^C}}{\lambda^A}\right)\right)\end{aligned}$$

(11)

However, such expressions for the information gain were obtained by approximating compound tessellations through Poisson–Voronoi tessellations of equal cell intensity, and the corresponding values of the information gain should be carefully compared with those obtained through Monte-Carlo simulations.

5.3 Using a Monte-Carlo method

Using a Monte-Carlo method for the computation of the information gain provides the best accuracy because the model of the network can be directly used for the computation without requiring further simplifications.

According to the system model presented in Section 3, we are assuming that the base stations of each network are spread out on the territory as several Poisson clouds, e.g., $\big\{X^A_i\big\}$, $\big\{X^B_j\big\}$ having the intensities λ ^A, λ ^B. Each base station $X^A_i$ in the first network has a random variable $P^A_{\textrm{TX,}i}$ standing for transmission power, as well as technology and environment specific values K, P _N and α.

A given mobile device located at U is said to lie in the cell attached to base station $X^A_{i_0}$ in the first network whenever the product $\frac{P^A_{\mathrm{TX,}i_0}}{P_{\mathrm{N}}}\cdot\frac{K}{|U-X^A_{i_0}|^{\alpha}}$ is greater than any of the analogous quantities $\frac{P^A_{\mathrm{TX,}i}}{P_{\mathrm{N}}}\cdot\frac{K}{|U-X^A_{i}|^{\alpha}}$ for i ≠ i ₀. We denote by $\hat{C}^A_i$ this new notion of a cell attached to the base station located at $X^A_i$, and by $\hat{C}^B_j$ the cell attached to $X^B_j$ in a similar way in the second network, using some further family $\big\{P^B_{\mathrm{TX,}j} \big\}$ of random variables.

These families of random variables are naturally assumed to be independent of each other. $\big\{ P^A_i\big\} \big(\text{resp.}$ $\big.\big\{ P^B_j\big\}\big)$ may be modeled, e.g., as an i.i.d. sequence of uniform or Beta distributed random variables.

Using again the spatial ergodicity underlying the network model at hand, one may define the long-term information gain as the difference of stochastic mean values

$$\mathbb{E}\left[ \log(|\hat{C}^A(O)|)\right]- \mathbb{E}\left[ \log(|\hat{C}^A(O)\cap \hat{C}^B(O)|)\right],$$

(12)

where $\hat{C}^A(O)$ (resp. $\hat{C}^B(O)$) is defined as the unique cell covering the origin O in the first network (resp. the second network). Recalling that the above mean values may be simply expressed as integrals featuring the distribution functions of the relevant areas, so that, e.g.,

$$\begin{array}{rll} \mathbb{E}\left[ \log(|\hat{C}^A(O)|)\right]&=& \int_1^{+\infty}\frac{1}{x}\mathbb{P}\left\lbrace |\hat{C}^A(O)|\geq x\right\rbrace dx \\ &&-\int_0^{1}\frac{1}{x}\mathbb{P}\left\lbrace |\hat{C}^A(O)|\leq x\right\rbrace dx, \end{array}$$

(13)

one is left with the task of finding a satisfactory way of approximating probabilities such as

$$p(x)=\mathbb{P}\left\lbrace |\hat{C}^A(O)|\geq x\right\rbrace.$$

(14)

A Monte-Carlo simulation can be performed along the following steps:

• 1. Draw a random natural number n according to the Poisson distribution having parameter $\left( \lambda^{A}\cdot |T|\right)$ and then n i.i.d. points X ¹,X ²,..., X ⁿ distributed uniformly in the territory T (simulation of the base station locations in the first network).

• 2. For i = 1,...,n, generate the i.i.d. r.v. P _TX,i . Choose P _N and K according to the investigated technology.

• 3. For i = 1,...,n, evaluate the quantity $\frac{P_{\mathrm{TX,}i}}{P_{\mathrm{N}}}\cdot\frac{K}{|X_i|^{\alpha}}$, and denote by i ₀ the index for which this quantity is maximal (so that the origin lies in the cell attached to the tower located at $X_{i_0}$).

• 4. Simulate a (large) number U ₁,U ₂,...,U _N of i.i.d. points (mobile device positions) distributed uniformly in the territory T.

• 5. For i = 1,...,n and j = 1,...,N, evaluate the quantities $\frac{P_{\mathrm{TX,}i}}{P_{\mathrm{N}}}\cdot\frac{K}{|U_{\!\!j}-X_i|^{\alpha}}$ and attach a variable ξ _j to the point U _j in such a way that

  $$\xi_j= \begin{cases} 1&\text{ if $\frac{P_{\mathrm{TX,}i}}{P_{\mathrm{N}}}\cdot \frac{K}{|U_{\!\!j}-X_i|^{\alpha}}$ is maximal for $i=i_0$,}\\ 0&\text{ otherwise.} \end{cases}$$

• 6. Evaluate the proportion $\kappa=\frac{1}{N}\sum_{j=1}^N\xi_j$, and define Υ ∈ ℝ by

  $$ \Upsilon=\log(\kappa\cdot|T|)=\log(|T|)-\log\left(\frac{N}{\sum_{j=1}^N\xi_j}\right) $$

  Store Υ and go back to step 1, unless this step has been repeated sufficiently many times (M times).

• 7. Once steps 1–6 have been repeated sufficiently many times, yielding the successive outputs Υ₁,Υ₂,...,Υ _M , take the approximation

  $$\mathbb{E}\left[ \log(|\hat{C}_O(\Phi)|)\right]\approx\frac{1}{M}\sum_{k=1}^M\Upsilon_k$$

The stochastic mean value of $\log(|\hat{C}^A(O)\cap \hat{C}^B(O)|)$ may be computed similarly. In parallel to the first base station set, steps 1 to 3 are performed for the second set using the corresponding parameters, i.e., we draw n _B using λ ^B, select the transmission powers, and finally determine the index $i_{0}^{B}$ of the base station from the second set which covers the origin. Step 4 remains unchanged. In step 5, ξ _j takes up the value “1” only if the quantities for both sets are maximal; otherwise, value “0” is taken. Step 6 is performed based on this ξ _j . In step 7, the desired stochastic mean value is obtained.

6 Numerical results

In this section, we present some numerical results that have been obtained by the different mechanisms for the computation of the information gain. First, we will investigate the gain that can be achieved by a computation of the intersection areas of the base stations. Secondly, the results for the approximation of the information gain via Voronoi cells and scaling arguments will be presented and the deviations between the different approaches will be shown. Afterwards, the distribution of the different cell sizes and their intersection areas will be presented for some distinct scenarios.

6.1 Average information gain

Its very definition shows that the information gain depends on the number of base station sets being used, as well as on the sizes of the cells in each set.

First, we consider a territory with a size of 1×1 km, covered by two different base station sets. The expected station number of each set varies between 10 and 200, reflecting different scenarios like indoor, urban, and rural. The transmission power of the stations is uniformly distributed between [0.25 P _{TX, Max};P _{TX, Max}] with P _{TX, Max} = 100mW, i.e., we have chosen values being typical for IEEE 802.11 WLANs.

In Fig. 7, the average information gain is presented for different base station densities λ ^B when λ ^A is fixed. The results have been obtained by the Monte-Carlo method. For each point in the plots, the mean value has been computed based on 250 random base station constellations. The intervals being displayed in the graph denote 95% confidence intervals.

Fig. 7

Average information gain obtained by the Monte-Carlo method for fixed base station densities λ ^A

The resulting information gain when both base station densities vary is displayed in Fig. 8. Twenty different base station intensities have been investigated for each set. Again, a mean value has been computed based on 250 random base station constellations for each point on the surface in the figure. As expected, the information gain increases as the number of base stations in the second set increases, and the largest gain is achieved when the number of base stations in the first set is relatively small.

Fig. 8

Average information gain if two base station sets with different densities exist

For Fig. 9, we considered the case where location information is obtained via three different base station sets. In addition to the previous scenario, a third set with fixed λ ^C = 100 is used for the positioning, leading to an overall increase of the information.

Fig. 9

Average information gain if a third base station set with λ ^C = 100 is added

6.2 Approximations and resulting deviations

Let us now consider the average information gain being obtained if the coverage areas of the base stations are approximated by Voronoi cells and a scaling argument is used.

Figure 10 shows the average information gain being computed based on the Voronoi cell assumption. When a large number of base stations is considered, the computed information gain is very close to that of the Monte-Carlo approach. On the other hand, when the first set of base stations is small, this deviation becomes rather large. The relative deviation of the information gain using the Monte-Carlo and Voronoi approaches is presented in Fig. 11. The average deviation results is 10.1% in the considered parameter range.

Fig. 10

Average information gain obtained by the approximation via Voronoi cells

Fig. 11

Relative deviation between the original information gain and the approximation via Voronoi cells

In Fig. 12, the resulting deviation of the information gain for three base station sets is displayed. Like in Fig. 9, the density λ ^C = 100 has been chosen for the third set. One can clearly see that the deviation is quite small in comparison to the results for two base station sets.

Fig. 12

Relative deviation between the original information gain and the approximation via Voronoi cells for three base station sets

The relative deviation of the Monte-Carlo numerical results respective to the values obtained via Eq. 9 are displayed in Fig. 13. These two sets of results are closer to each other when λ ^A is kept small, but on the whole, the average deviation is higher (31.2%) compared with the Voronoi-based approximation.

Fig. 13

Relative deviation between the original information gain and the one being computed via a scaling argument

6.3 Distributions of the cell sizes

Next, we were interested in the distributions of the cell sizes and the intersection areas. In Fig. 14, the distribution of the original cell sizes and the intersection areas is presented. We started with one base station set with λ ^A = 30. Afterwards, a second set with λ ^B = 100 was added. The corresponding histogram for the two sets shows the size of the intersection areas. Roughly 65% of the intersection areas are smaller than 10 000 m². If an additional third set with λ ^C = 100 is used for the location determination, the possible whereabouts of a mobile device can be theoretically limited to an area of 5 000 m² and below in 75% of the cases.

Fig. 14

Original cell sizes and intersection areas. The first histogram shows the distribution of the cell sizes from one set (λ ^A = 30). The second histogram shows the distribution of the intersection areas of this set with a second set (λ ^B = 100). The last one presents the distribution of the intersection areas of these two sets with a third set (λ ^C = 100)

In Fig. 15, the distributions of the cell sizes and the intersection areas for the Voronoi-based approximations are shown, using the same intensities as before. All histograms are generated based on 250 samples of the cell sizes and intersection areas.

Fig. 15

Voronoi cell sizes and intersection areas. The figure shows the distributions of the cell sizes and intersection areas of the Voronoi cells, using the same parameters as in Fig. 14

7 Conclusion

In this paper, we presented novel approaches to the computation of the information gain that can be achieved by intersection-based range-free localization. We applied methods from Stochastic Geometry to obtain approximations of the information gain that can be achieved for different base station densities. In contrast to previous work, we modeled the interference of different stations because the assumption of noninterfering stations may hardly be valid for the investigated networks. Additionally, we assumed spatial variability of the station placements, which had rarely been investigated up to now.

The displayed numerical results show that the quality of the approximation increases with the complexity of the techniques involved. Scaling arguments may be used to estimate the order of magnitude of the gain, while approximations based on Voronoi cells lead to more precise results.

Generally speaking, the possible whereabouts of a mobile device can be significantly reduced by using the information from different base stations. For instance, in an indoor scenario with a person in distress, the number of rooms that need to be scanned by a rescue team can be extremely reduced.

An application area of the presented approach has been presented in [19]. Location information of mobile devices is normally provided by so-called location servers in a carrier access network. If the position of a device is to be provided, the servers trigger the respective location determination processes. However, the location determination in a network can be quite costly and the outcome might not meet the expectations of the requester, especially if a request should be used to refine existing location information. To avoid unnecessary workload, the present approach offers requesters the possibility to add the desired accuracy or information gain before they send their queries to the location servers. By using the approaches that have been presented in this paper and information about the deployed base stations, the servers can estimate the accuracy or the gain that can be achieved. Based on these estimates, a server can determine in advance whether the procedure should be started. Regarding the next steps of our ongoing work, we will investigate the effect of different coverage models, suited mathematical approximations, and the correctness of the resulting information gain.

Appendix

Let us now give some brief explanations, as well as a few references concerning translation invariance and ergodicity for random tessellations of the plane. Recall that a Poisson–Voronoi tessellation of the plane may be defined by considering a planar Poisson point process $\left\lbrace X_i\right\rbrace$ and attaching a convex polygonal cell C _i to each of the random points X _i in a very simple fashion: C _i consists of all points Y in the plane lying closer to X _i than to any of the other points X _j in the Poisson cloud (see Fig. 5). Such a construction may certainly be carried out for any Poisson point process in the plane; however, the resulting tessellation will be translation-invariant only if the underlying Poisson random cloud has constant intensity λ. The translation-invariance property we have in mind is the following: denoting by T _V :Y↦Y + V the translation along an arbitrarily fixed planar vector V, one asks for the statistical properties of the random tessellation $\left\lbrace C_i\right\rbrace$ to be left unchanged when applying T _V to each of the cells, i.e., changing $\left\lbrace C_i\right\rbrace$ into $\left\lbrace T_V\left( C_i\right) \right\rbrace$. A more precise statement of this property requires considering an arbitrary bounded measurable functional Ψ of the random tessellation $\left\lbrace C_i\right\rbrace$, as well as an arbitrary planar translation T _V , and requiring that the mean value of $\Psi\left[ \left\lbrace C_i\right\rbrace\right]$ be left unchanged when composing Ψ with T _V :

$$\mathbb{E}\left( \Psi\left[ \left\lbrace T_V\left( C_i\right)\right\rbrace\right]\right) = \mathbb{E}\left( \Psi\left[\left\lbrace C_i\right\rbrace\right]\right)$$

(one may think of Ψ as a geometric characteristic of the polygonal cell covering the origin O in the plane, e.g., number of vertices, perimeter, or area, even though such reasonable functionals are not bounded). A Poisson–Voronoi tessellation of the plane satisfying such translation-invariance property is said to be stationary.

Of course, one might be interested in the stationarity of some other kind of random tessellation, for example, the Poisson line tessellations mentioned in Section 5.2, where a straight line Δ _i is drawn through each point X _i of the random cloud, orthogonally to the segment joining O and X _i (see Fig. 6). In the latter case, however, the intensity of the underlying Poisson random cloud should be taken proportional to $d\rho d\theta=\frac{dxdy}{\sqrt{x^2+y^2}}$ in order for the resulting line tessellation to be stationary. Indeed, assuming that the lines in such random tessellation are being translated along some fixed vector V = (V ₁;V ₂), consider a particular line Δ and its translate Δ′, as well as the point X on Δ lying closest to the origin O and the point X′ on Δ′ lying closest to O. Denoting by (ρ;θ) the polar coordinates of X and by (ρ′;θ′) those of X′, one obviously has θ′ = θ or θ′ = θ±π (Δ′ is parallel to Δ), whereas

$$\rho'=\rho+(V_{\!1}\cos\theta + V_2\sin\theta)=\rho+\left\langle V;U_{\theta}\right\rangle .$$

(see Fig. 16). Thus, for an arbitrary bounded measurable function (ρ;θ)↦F(ρ;θ), one certainly has

$$\int\int F(\rho';\theta')d\rho'd\theta'=\int\int F(\rho;\theta)d\rho d\theta,$$

because the corresponding Jacobian is unitary, but this identity breaks down when replacing the differential dρ dθ, e.g., by ρd ρd θ = dx dy.

Fig. 16

The effect of a translation on a Poisson line tessellation

One of the main consequences of such translation-invariance property lies in the validity of Wiener’s ergodic theorem: assuming that $\left\lbrace C_i\right\rbrace$ is a stationary random tessellation of the plane and that Ψ is a square integrable measurable functional of $\left\lbrace C_i\right\rbrace$ (i.e., such that $\mathbb{E}\left( \left\vert\Psi\left[\left\lbrace C_i\right\rbrace\right]\right\vert^2\right)$ be finite), one may assert the almost sure existence of the limit¹

$$\lim_{R\rightarrow +\infty} \frac{1}{|B_R|}\underset{B_R}{\int\int} \Psi\left[ \left\lbrace T_V\left( C_i\right)\right\rbrace\right] dV =L(\Psi),$$

where B _R stands for the Euclidian ball of radius R centered at the origin, and |B _R | for the corresponding area (see [20] for a series of precise statements of such theorems and their proofs). At this stage, some further condition on the random tessellation $\left\lbrace C_i\right\rbrace$ is needed to make sure that the limit L(Ψ) coincides (almost surely) with the stochastic mean value $\mathbb{E}\left( \Psi\left[\left\lbrace C_i\right\rbrace\right]\right)$. A very natural sufficient condition of this kind is the following: the stationary random tessellation $\left\lbrace C_i\right\rbrace$ is said to satisfy a mixing condition whenever

$$\lim_{R\rightarrow +\infty} \mathbb{E}\left( \Phi\left[\left\lbrace C_i\right\rbrace\right] \cdot\Psi\left[ \left\lbrace T_{R.V}\left( C_i\right)\right\rbrace\right]\right) = \mathbb{E}\left( \Phi\left[\left\lbrace C_i\right\rbrace\right]\right) \cdot\mathbb{E}\left( \Psi\left[\left\lbrace C_i\right\rbrace\right]\right),$$

holds true for any unit vector V and bounded measurable functionals Φ, Ψ. Roughly speaking, this means that the geometric characteristics of two parts of the random tessellation located far from each other are nearly uncorrelated. Such property holds true for any of the stationary random tessellations $\left\lbrace C_i\right\rbrace$ we have been considering so far, and as a consequence, one may assert the validity of the identity

$$L(\Psi)\!=\!\! \lim_{R\rightarrow +\infty} \frac{1}{|B_R|}\underset{B_R}{\int\!\int} \!\Psi\left[ \left\lbrace T_V\left( C_i\right)\right\rbrace\right] dV \!=\! \mathbb{E}\left( \Psi\left[\left\lbrace C_i\right\rbrace\right]\right),$$

almost surely in the realizations of $\left\lbrace C_i\right\rbrace$. Readers interested in rigorous applications of Wiener’s or Birkhoff’s ergodic theorems to stochastic geometry should certainly consult [21] or [22]. Some of the main applications of this kind go under the name of “mean-value relationships” for stationary random tessellations. Here is an important example of such mean value relationships (many more may be found in Section 10.3 of [23]): denoting by λ ₀ (resp. λ ₂) the mean number of vertices (resp. cells) of the tessellation $\left\lbrace C_i\right\rbrace$ to be found per unit area, and by $\overline{n}_{0,2}$ the mean number of cells touching a vertex in this tessellation, one has

$$\overline{n}_{0,2}=2+\frac{2\lambda_2}{\lambda_0} .$$

In the simple situation where $\left\lbrace C^A_i\right\rbrace$ is the Poisson–Voronoi tessellation attached to a Poisson random cloud of constant intensity λ, one has λ ₀ = 2λ and λ ₂ = λ, so that $\overline{n}_{0,2}=3$. In fact, in such a simple situation, there are exactly three polygons meeting at each of the vertices, almost surely in the realizations of $\left\lbrace C^A_i\right\rbrace$. Let us consider a further Poisson–Voronoi tessellation $\big\{ C^B_j\big\}$ attached to a second Poisson random cloud of constant intensity μ, independent of the first one. In the compound tessellation $\big\lbrace C^{Comp}_k\big\rbrace$ obtained by superimposing the cells in $\big\lbrace C^B_j\big\rbrace$ to those of $\left\lbrace C^A_i\right\rbrace$, there are three kinds of vertices:

• Vertices already present in the tessellation $\left\lbrace C^A_i\right\rbrace$: these come up with intensity 2λ and are adjacent to three polygons in the compound tessellation.

• Vertices already present in the tessellation $\big\lbrace C^B_j\big\rbrace$: these come up with intensity 2μ and are adjacent to three polygons in the compound tessellation.

• Vertices appearing at the intersection of an edge in $\left\lbrace C^A_i\right\rbrace$ with an edge in $\left\lbrace C^B_j\right\rbrace$: these come up with intensity $\frac{8}{\pi}\sqrt{\lambda\mu}$ and are adjacent to four polygons in the compound tessellation. (The original paper [24] should be consulted for more details on this third intensity).

As a result of the preceding considerations, one may state that the mean number of polygons adjacent to a vertex in the compound tessellation is given by

$$\overline{n}^{Comp}_{0,2}=\frac{6(\lambda+\mu)}{2\lambda + 2\mu+\frac{8}{\pi}\sqrt{\lambda\mu}} +\frac{\frac{32}{\pi}\sqrt{\lambda\mu}}{2\lambda + 2\mu+\frac{8}{\pi}\sqrt{\lambda\mu}} .$$

Using the above stated mean-value relationship then leads to the following value Λ^Comp for the cell intensity in the compound tessellation:

$$\begin{array}{rll}\Lambda^{Comp}(\lambda,\mu)&=&\left(2\lambda + 2\mu+\frac{8}{\pi}\sqrt{\lambda\mu}\right)\cdot\left(\frac{\overline{n}^{Comp}_{0,2}}{2}-1\right)\\ &=&\lambda+\mu+\frac{8}{\pi}\sqrt{\lambda\mu}. \end{array}$$

The very same method may be used to determine the cell intensity of a compound tessellation where a third Poisson–Voronoi tessellation built upon a new Poisson cloud of intensity ν is superimposed to the preceding compound tessellation: the resulting cell intensity is then

$$\Lambda^{Comp}(\lambda,\mu,\nu)\!=\! \lambda\!+\!\mu\!+\!\nu\!+\!\frac{8}{\pi}\left(\sqrt{\lambda\mu}\!+\!\sqrt{\lambda\nu}\!+\!\sqrt{\mu\nu}\right).$$

More generally, superimposing J Voronoi tessellations built upon independent homogeneous Poisson clouds having the intensities λ ₁, λ ₂, ..., λ _J yields a stationary random tessellation whose cell intensity is given by

$$\Lambda^{Comp}(\lambda_1, \lambda_2, \ldots, \lambda_J)=\sum_{j=1}^J\lambda_j +\frac{8}{\pi}\sum_{1\leq j<k\leq J}\sqrt{\lambda_j\lambda_k}.$$

Let us finally give a brief description of some of the main results contained in [17]. { X _i } denoting a homogeneous Poisson cloud of unit intensity λ = 1 on the plane, recall that the Palm cell $\mathcal{C}=\mathcal{C}\left( \{ X_i\}\right)$ attached to { X _i } may be defined as the convex polygon consisting of all points X lying closer to the origin O than to any point X _i in the cloud (see Fig. 17). In other words, $\mathcal{C}$ is the Voronoi cell about O appearing when adding this point to the cloud. Letting $N_0(\mathcal{C})$ denote the number of vertices (or, equivalently, the number of sides) appearing in the random convex polygon $\mathcal{C}$, it turns out that a proper use of Slyvniak’s formula (Proposition 4.1.1 in [18]) enables one to compute $\mathbb{P}\left\lbrace N_0(\mathcal{C})=k\right\rbrace$ explicitly for arbitrary k ≥ 3, and one has:

$$\begin{array}{l} \mathbb{P}\left\lbrace N_0(\mathcal{C})=k\right\rbrace \\[6pt] \qquad =\displaystyle{\frac{(2\pi)^k}{k!} \int_{\Sigma_k}}d\sigma_k(\delta_1,\ldots,\delta_k)\displaystyle{\int_{\mathbb{R}_+^k}}dp_1\ldots dp_k\\[6pt] \qquad \quad \displaystyle{\prod_{i=1}^k} p_i e^{-H(\delta_i,p_i,p_{i+1})}\cdot \boldsymbol{1}_B(p_{i-1},p_i,p_{i+1},\delta_{i-1},\delta_i), \end{array}$$

(15)

where dσ _k (δ ₁,...,δ _k ) stands for the uniform probability measure on the (k − 1)-dimensional simplex

$$\Sigma_k=\left\lbrace (\delta_1,\ldots,\delta_k)\in [0;2\pi]^k:\sum_{i=1}^k\delta_i=2\pi\right\rbrace ,$$

whereas H is the function given by

$$\begin{array}{rll}H(\delta,p,q)\!&=&\! \frac{1}{2\sin(\delta)^2} \left\{\frac{\delta}{2}(p^2\!+\!q^2\!-\!2pq\cos\delta)\right. \\&& \left.\qquad\quad\; +pq\sin\delta\!-\!\frac{p^2}{4}\sin2\delta\!-\!\frac{q^2}{4}\sin2\delta\right\} \end{array}$$

and $\boldsymbol{1}_B$ stands for the indicator function of

$$\begin{array}{rll}B&=&\Big\{ (p,q,r,\alpha,\beta)\in (\mathbb{R}_+)^3\times(0;\pi)^2: p\sin\beta\\&&\ \ +r\sin\alpha\geq q\sin(\alpha+\beta)\Big\}. \end{array}$$

Fig. 17

Palm cell about the origin for a given cloud.

In the multiple integral appearing in Eq. 15, δ ₁,..., δ _k are angular variables, whereas p ₁,...,p _k stand for distances to the origin, and these variables are labelled cyclically, so that p ₀ = p _k , p _k + 1 = p ₁ and δ ₀ = δ _k .

Following [17], we further denote by (P _i ,Θ _i ) the polar coordinates of the vertices of the random cell $\mathcal{C}$, for $i=1,2,\ldots,N_0(\mathcal{C})$. Fixing again a natural number k ≥ 3, it turns out that, conditionally to $\left\lbrace N_0(\mathcal{C})=k\right\rbrace$, the joint distribution of the vector (P ₁,...,P _k ,Θ₂ − Θ₁,...,Θ _k  − Θ _k − 1,2π + Θ₁ − Θ _k ) may be explicitly described as the measure ν _k on $\mathbb{R}_+^k\times[0;2\pi]^k$ given through

$$\begin{array}{l} d\nu_k(p_1,\ldots,p_k,\delta_1,\ldots,\delta_k)\\[6pt] {\kern10pt} =\varphi_k(p_1,\ldots,p_k,\delta_1,\ldots,\delta_k)\\[6pt] {\kern21pt} \; \cdot dp_1\ldots dp_kd\sigma_k(\delta_1,\ldots,\delta_k), \end{array}$$

where dσ _k (δ ₁,...,δ _k ) again stands for the uniform pro bability measure on the (k − 1)-dimensional simplex Σ _k , whereas

$$\begin{array}{l} \!\varphi_k(p_1,\ldots,p_k,\delta_1,\ldots,\delta_k)\\ {\kern9pt} =\displaystyle{\frac{(2\pi)^k}{k!\cdot\mathbb{P}\left\lbrace N_0(\mathcal{C})=k\right\rbrace} \prod_{i=1}^k} p_i e^{-H(\delta_i,p_i,p_{i+1})}\\[6pt] {\kern21pt} \; \cdot\boldsymbol{1}_B(p_{i-1},p_i,p_{i+1},\delta_{i-1},\delta_i) \end{array}$$

In other words, conditionally to the event $\left\lbrace N_0(\mathcal{C})=k\right\rbrace$, the probability for (P ₁,...,P _k , Θ₂ − Θ₁,...,Θ _k  − Θ _k − 1, 2π + Θ₁ − Θ _k ) to realize any event $E\subset\mathbb{R}_+^k\times[0;2\pi]^k$ is given as the quotient of the integral

$$\underset{E}{\int \int}dp_1\ldots dp_k d\sigma_k(\delta_1,\ldots,\delta_k) \prod_{i=1}^k p_i e^{-H(\delta_i,p_i,p_{i+1})} \cdot \boldsymbol{1}_B(p_{i-1},p_i,p_{i+1},\delta_{i-1},\delta_i)$$

through a similar integral computed over the whole of $\mathbb{R}_+^k\times[0;2\pi]^k$.

This provides us with an explicit description of the behavior of the random cell $\mathcal{C}$. From there on, mean values such as $\mathbb{E}\left[ |\mathcal{C}|\right]$ or $\mathbb{E}\left[ |\mathcal{C}|\cdot\log|\mathcal{C}|\right]$ may readily be computed.