Connectivity in device-to-device networks in Poisson-Voronoi cities

Here’s a recently uploaded manuscript:

  • 2023 – Keeler, Błaszczyszyn, Cali – Connectivity and interference in device-to-device networks in Poisson-Voronoi cities.

https://arxiv.org/abs/2309.02137

This work presents numerical results complementing mathematical work carried out by us. The work concerns (continuum) percolation results for a special network model based on Poisson-Voronoi tessellations.

The most relevant work are these two papers (the first being somewhat seminal):

  1. Dousse, Franceschetti, Macris, Meester, Thiran, Percolation in the signal to interference ratio graph, 1996.
  2. Le Gall, Błaszczyszyn, Cali, and En-Najjary, Continuum line-of-sight percolation on Poisson-Voronoi tessellations, 2021

Our work effectively seeks to combine these two papers. We obtain the equivalents results from the first paper by coupling its connectivity model with the connectivity model and network model (based on a Cox point process) presented in the second paper.

If you want a more detailed version, here’s the abstract:

To study the overall connectivity in device-to-device networks in cities, we incorporate a signal-to-interference-plus-noise connectivity model into a Poisson-Voronoi tessellation model representing the streets of a city. Relays are located at crossroads (or street intersections), whereas (user) devices are scattered along streets. Between any two adjacent relays, we assume data can be transmitted either directly between the relays or through users, given they share a common street. Our simulation results reveal that the network connectivity is ensured when the density of users (on the streets) exceeds a certain critical value. But then the network connectivity disappears when the user density exceeds a second critical value. The intuition is that for longer streets, where direct relay-to-relay communication is not possible, users are needed to transmit data between relays, but with too many users the interference becomes too strong, eventually reducing the overall network connectivity. This observation on the user density evokes previous results based on another wireless network model, where transmitter-receivers were scattered across the plane. This effect disappears when interference is removed from the model, giving a variation of the classic Gilbert model and recalling the lesson that neglecting interference in such network models can give overly optimistic results. For physically reasonable model parameters, we show that crowded streets (with more than six users on a typical street) lead to a sudden drop in connectivity. We also give numerical results outlining a relationship between the user density and the strength of any interference reduction techniques.

In future posts I’ll detail the above work as well as our more mathematical work on this type of percolation model.

The Laplace functional

When working with random variables, a couple useful tools are the characteristic function and the moment-generating function, which for a random variable \(Y\) are defined respectively as
$$
\phi_Y(t)= \mathbb{E}\left [ e^{itY} \right ]\,
$$
and
$$
M_Y(t)= \mathbb{E}\left [ e^{tY} \right ]\,,
$$
where the imaginary number \(i=\sqrt{-1}\) and the real variable \(t\in \mathbb{R}\). For continuous random variables, these two respective functions are essentially the Fourier and Laplace transforms of the probability densities. (The moment-generating function \(M(t)\) may not exist due to the integral not converging to a finite value, whereas the characteristic function \(\phi_Y(t)\) always exists.)

If \(Y\) is a discrete random variable, a useful object is the probability-generating function, which is defined as
$$
G_Y(z)= \mathbb{E}\left [z^Y \right ]\,.
$$
This function is the Z-transform of the probability mass function of the random variable \(Y\).

By using these tools, results such as sums of random variables and convergence theorems can be proven. There exist equivalent tools which prove useful for studying point processes (and, more generally random measures).

Laplace functional

For a point process \(\Phi \) defined on some underlying space \(\mathbb{S}\), such as \(\mathbb{R}^d\), the Laplace functional is defined as
$$
L_{\Phi}(f)=\mathbb{E}[e^{-\int_{ \mathbb{S}} f(x){\Phi}(dx)}]\,,
$$
where \(f\) is any (Borel) measurable non-negative function on the space \(\mathbb{S}\).

A simple point process is one for which two or more points coincide in location with probability zero. For a simple point process, we can write the random integral (or sum) using set theory notation, giving
$$
\int_{\mathbb{S}} f(x){\Phi}(dx)=\sum\limits_{x\in \Phi} f(x) \,.
$$

Name

Why’s it called a Laplace functional? From its definition, it’s clear that the first half of the name stems from the Laplace transform. Mapping from the space \(\mathbb{S}\), it’s called a functional because it is a function of a non-negative function \(f\).

Characterization

The Laplace functional characterizes the point process, meaning each point process (or, more generally, random measure) has its own unique Laplace functional. For a given point process, the challenge is to derive the mathematical expression for the Laplace functional by using its definition.

Poisson example

For deriving the Laplace functional, perhaps not surprisingly, one of the easiest one of the easiest point processes is the Poisson point process due to its independence property. For a Poisson process \(\Phi\) with intensity measure \(\Lambda\) defined on the state space \(\mathbb{S}\), the Laplace functional is given by
$$
L_{\Phi}(f)=e^{-\int_{ \mathbb{S}} [1-e^{-f(x)}]\,\Lambda(dx) } \,.
$$

If the Poisson point process is homogeneous, then

$$
L_{\Phi}(f)=e^{-\lambda\int_{ \mathbb{S}} [1-e^{-f(x)}]\,dx } \,,
$$

where \(\lambda\) is the intensity function (that is, the average density of points).

Applications

Proof techniques

Given a Laplace functional characterizes a point process, it can be used prove results on the distributions of point processes, where the proofs often simpler. For example, it can used to see what happens when you perform a point process operation on a point process, such as proving that the independent thinning a Poisson point process gives another Poisson point process. Laplace functionals are used to prove results on the superposition and (random or deterministic) mapping of point processes.

Interference in wireless network models

In the previous post, I covered the concept of the signal-to-interference ratio or SIR in wireless networks. (If noise is included, then then signal-to-interference-plus-noise ratio or just SINR.) Under such wireless network models, the interference term is a type of shot noise of the point process used for the transmitter locations.

Researchers commonly assume Rayleigh fading of the signal energy, which corresponds to the power values randomly varying according to an exponential distribution (due to a square root being taken). The tail distribution of an exponential variable \(F\) with mean \(\mu\) is simply \(\mathbb{P}(F>t)= e^{-t/\mu}\). This means that the exponential assumption and some conditioning arguments lead to Laplace transforms of random variables, including the interference, which can be recast as the Laplace functional of the point process used for the transmitter locations.

Related functionals

For random variables, the characteristic, moment-generating, and probability-generating functions are similarly defined and closely related. We now define two other functionals used for studying point processes.

Characteristic functional

For a point process \(\Phi \) defined on \(\mathbb{S}\), the characteristic functional is defined as
$$
L_{\Phi}(f)=\mathbb{E}[e^{i\int_{ \mathbb{S}} g(x){\Phi}(dx)}]\,,
$$
where \(i=\sqrt{-1}\) and \(g\) is any (Borel) measurable function on the space \(\mathbb{S}\).

Probability-generating functional

For a point process \(\Phi \) defined on \(\mathbb{S}\), the probability-generating functional is defined as
$$
G_{\Phi}(v)=\mathbb{E}[ \prod_{x\in \Phi } v(x)]\,,
$$
where \(v\) is any bounded non-negative (Borel) measurable function on the space \(\mathbb{S}\) such that \(0\leq v(x)\leq 1\) for any point \(x\in \mathbb{S}\). (Some authors use an alternative definition with a function \(u(x)=1-v(x)\).)

Further reading

There is a Wikipedia article on the Laplace functional.

The usual sources on point processes (and, more generally, random measures) cover Laplace functionals. For example, see section 7.2.1 of the text Stochastic Geometry and its Applications by Chiu, Stoyan, Kendall and Mecke. The Laplace and other functionals are covered in Section 9.4 of the second volume of An Introduction to the Theory of Point Processes by Daley and Vere-Jones.

Baccelli and Błaszczyszyn use the Laplace to prove some results on the Poisson point process in Section 1.2 in the first volume of Stochastic Geometry and Wireless Networks. In an approachable manner, Haenggi details the Laplace and probability-generating functionals in Stochastic Geometry for Wireless networks.

The recent book Random Measures, Theory and Applications by Kallenberg also uses Laplace functionals; see Lemma 3.1. Finally, Baccelli, Błaszczyszyn, and Karray use the Laplace functional in the recent book (manuscript) Random Measures, Point Processes, and Stochastic Geometry, but they call it a Laplace transform; see Section 1.3.2, 2.1.1 and 2.2.2, among others.

Campbell’s theorem (formula)

In a previous post, I wrote about the concept of shot noise of a point process. In the simplest terms, shot noise is just the sum of some function over all the points of a point process. The name stems from the original mathematical models of the noise in old electronic devices, which was compared to shot (used in guns) hitting a surface.

In this post I will present a result known as Campbell’s theorem or  Campbell’s formula, which gives the expectation of shot noise as as simple integral expression. This both a general holding for all point processes. It is also useful, as shot noise naturally arises in mathematical models. One application is wireless network models, where the interference term is shot noise.

But to present the main result, I first need to give some basics of point processes, most of which I already covered in this post.

Point process basics

We consider a point processes \(\Phi\) defined on some underlying mathematical space \(\mathbb{S}\), which is often \(\mathbb{R}^n\).  Researchers typically interpret a point process as a random counting measure, resulting in the use of integral and measure theory notation. For example, \(\Phi(B)\) denotes the number of points located in some (Borel measurable) set \(B\), which is a subset of \(\mathbb{S}\).

For point processes, researchers often use a dual notation such that \(\Phi\) denotes both a random set or a random measure.  Then we can write, for example, \(\Phi=\{X_i\}_i\) to stress that \(\Phi\) is a random sets of points.  (Strictly speaking, you can only use the set notation if the point process is simple, meaning that no two points coincide with probability one.)

The first moment measure of a point process, also called the mean measure or intensity measure, is defined as

$$\Lambda(B)= \mathbb{E} [\Phi(B)]. $$

In other words, the first moment measure can be interpreted as the expected number of points of \(\Phi\) falling inside the set \(B \subseteq \mathbb{S}\).

Shot noise definition

We assume a point process \(\Phi=\{X_i\}_i\) is defined on some space \(\mathbb{S}\). We consider a non-negative function \(f\) with the domain \(\mathbb{S}\), so \(f:\mathbb{S} \rightarrow [0,\infty)\).  If the point process \(\Phi\) is a simple, we can use set notation and define the shot noise as

$$
S= \sum_{X_i\in \Phi} f(X_i)\,.
$$

More generally, the shot noise is defined as

$$
S= \int_{ \mathbb{S}} f(x) \Phi(dx)\,.
$$

(We recall that an integral is simply a more general type of sum, which is why the integral sign comes from the letter S.)

Campbell’s theorem

We now state Campbell’s theorem.

Campbell’s theorem says that for any point process \(\Phi\) defined on a space \(\mathbb{S}\) the following formula holds

$$
\mathbb{E}[ S] = \int_{ \mathbb{S}} f(x) \Lambda(dx)\,,
$$

where \(\Lambda= \mathbb{E} [\Phi(B)]\) is the intensity measure of the point process \(\Phi\).

Interpretation

The integral formula is just an application of Fubini’s theorem, as we have simply changed the order of integration.  The formula holds for general processes because it is simply a result on first moments, so it is leveraging the linearity of sums and integrals, including the expectation operator. Put more simply, the sum of parts does equal the whole.

Some history

At the beginning of the 20th century, Norman R. Campbell studied shot noise in Britain and wrote two key papers. In one of these papers appears a version of the result we now called Campbell’s theorem or Campbell’s formula. Interestingly, Campbell was a physicist who credited his mathematical result to renown pure mathematician G. H. Hardy.  Hardy claimed years later that, given he only researched pure mathematics, none of his work would lead to applications. But Hardy’s claim is simply not true due to this result, as well as his results in number theory, which are famously used in modern day cryptography.

Further reading

For some basics on point processes, I suggest the classic text Stochastic Geometry and its Applications by Chiu, Stoyan, Kendall and Mecke, which covers point processes and the varying notation in Chapters 2 and 4. Haenggi also wrote a very readable introductory book called Stochastic Geometry for Wireless networks, where he gives the basics of point process theory.

These moment formula are also presented with proofs in Applied Probability by Lange; see Section 6.9.

Shot noise

Given a mathematical model based on a point process, a quantity of possible interest is the sum of some function applied to each point of the point process. This random sum is called shot noise, where the name comes from developing mathematical models of the noise measured in old electronic devices, which was likened to shot (used in guns) hitting a surface.

Researchers have long studied shot noise induced by a point process. One particularly application is wireless network models, in which the interference term is an example of shot noise. It is also possible to construct new point processes, called shot noise Cox point processes, by using based on the shot noise of some initial point process.

For such applications, we need a more formal definition of shot noise.

Definition

Shot noise of a point process

We consider a point processes \(\Phi=\{X_i\}_i\) defined on some space \(\mathbb{S}\), which is often \(\mathbb{R}^n\), and a non-negative function \(f\) with the domain \(\mathbb{S}\), so \(f:\mathbb{S} \rightarrow [0,\infty)\). This function \(f\) is called the response function.

Then the shot noise is defined as
$$
I= \sum_{X_i\in \Phi} f(X_i)\,.
$$

Shot noise of a marked point process

The previous definition of shot noise can be generalized by considering a marked point process \(\Phi’=\{(X_i, M_i)\}_i\), where each point \(X_i\) now has a random mark \(M_i\), which can be a random variable some other random object taking values in some space \(\mathbb{M}\). Then for a response function \(g:\mathbb{S}\times \mathbb{M} \rightarrow [0,\infty)\) , the shot noise is defined as
$$
I’= \sum_{(X_i, M_i)\in \Phi’} g(X_i,M_i)\,.
$$

Properties

Given a point process on a space, like the plane, at any point the shot noise is simply a random variable. If we consider a subset of the space, then shot noise forms a random field, where we recall that a random field is simply a collection of random variables indexed by some set. (By convention, the set tends to be Euclidean space or a manifold). The shot noise can also be considered as a random measure, for example
$$
I(B)= \sum_{X_i\in \Phi\cap B} f(X_i)\,,
$$
where \(B\subseteq \mathbb{S}\). This makes sense as the point process \(\Phi\) is an example of a random (counting) measure.

For Poisson point processes, researchers have studied resulting shot noise random variable or field. For example, given a homogeneous Poisson point process on \(\mathbb{R}^d\), if the response function is a simple power-law \(f(x)=|x|^{-\beta}\), where \(\beta> d\) and \(|x|\) denotes the Euclidean distance from the origin, then the resulting shot noise is alpha stable random variable with parameter \(\alpha=d/\beta\).

For a general point process \(\Phi\) with intensity measure \(\Lambda\), the first moment of the shot noise is simply
$$
\mathbb{E}(I)= \int_{\mathbb{S}} f(x) \Lambda (dx) \,.
$$

This is a result of Campbell’s theorem or formula. A similar expression exists for the shot noise of a marked point process.

Some history

Shot noise has been studied for over a century in science. In physics, Walter Schottky did research on shot noise in Germany at the beginning of the 20th century. In the same era, Norman R. Campbell studied shot noise in Britain and wrote two key papers, where one of them contains a result now called Campbell’s theorem or Campbell’s formula, among other names, which is a fundamental result in point process theory. Campbell was a physicist, but his work contains this mathematical result for which he credited the famed pure mathematician G. H. Hardy.

(It’s interesting to note that Hardy claimed years later that, given he did pure mathematics, none of his work would lead to applications, but that claim is simply not true for this and other reasons.)

The work on the physical process of shot noise motivated more probability-oriented papers on shot noise, including:

  • 1944, S. O. Rice, Mathematical Analysis of Random Noise;
  • 1960, Gilbert and Pollak, Amplitude distribution of shot noise;
  • 1971, Daley, The definition of a multi-dimensional generalization of shot noise;
  • 1977, J. Rice, On generalized shot noise;
  • 1990 Lowen and Teich, Power-law shot noise.

Further reading

As a model for interference in wireless networks, shot noise is covered in books such as the two-volume textbooks Stochastic Geometry and Wireless Networks by François Baccelli and Bartek Błaszczyszyn, where the first volume is on theory and the second volume is on applications. Martin Haenggi wrote a very readable introductory book called Stochastic Geometry for Wireless networks.