Stochastic geometry models of wireless networks


In mathematics and telecommunications, stochastic geometry models of wireless networks refer to mathematical models based on stochastic geometry that are designed to represent aspects of wireless networks. The related research consists of analyzing these models with the aim of better understanding wireless communication networks in order to predict and control various network performance metrics. The models require using techniques from stochastic geometry and related fields including point processes, spatial statistics, geometric probability, percolation theory, as well as methods from more general mathematical disciplines such as geometry, probability theory, stochastic processes, queueing theory, information theory, and Fourier analysis.
In the early 1960s a stochastic geometry model was developed to study wireless networks. This model is considered to be pioneering and the origin of continuum percolation. Network models based on geometric probability were later proposed and used in the late 1970s and continued throughout the 1980s for examining packet radio networks. Later their use increased significantly for studying a number of wireless network technologies including mobile ad hoc networks, sensor networks, vehicular ad hoc networks, cognitive radio networks and several types of cellular networks, such as heterogeneous cellular networks. Key performance and quality of service quantities are often based on concepts from information theory such as the signal-to-interference-plus-noise ratio, which forms the mathematical basis for defining network connectivity and coverage.
The principal idea underlying the research of these stochastic geometry models, also known as random spatial models, is that it is best to assume that the locations of nodes or the network structure and the aforementioned quantities are random in nature due to the size and unpredictability of users in wireless networks. The use of stochastic geometry can then allow for the derivation of closed-form or semi-closed-form expressions for these quantities without resorting to simulation methods or deterministic models.

Overview

The discipline of stochastic geometry entails the mathematical study of random objects defined on some space. In the context of wireless networks, the random objects are usually simple points or shapes and the Euclidean space is either 3-dimensional, or more often, the plane, which represents a geographical region. In wireless networks the underlying geometry plays a fundamental role due to the interference of other transmitters, whereas in wired networks the underlying geometry is less important.

Channels in a wireless network

A wireless network can be seen as a collection of channels sharing space and some common frequency band. Each channel consists of a set of transmitters trying to send data to a set of receivers. The simplest channel is the point-to-point channel which involves a single transmitter aiming at sending data to a single receiver. The broadcast channel, in information theory terminology, is the one-to-many situation with a single transmitter aiming at sending different data to different receivers and it arises in, for example, the downlink of a cellular network. The multiple access channel is the converse, with several transmitters aiming at sending different data to a single receiver. This many-to-one situation arises in, for example, the uplink of cellular networks. Other channel types exist such as the many-to-many situation. These channels are also referred to as network links, many of which will be simultaneously active at any given time.

Geometrical objects of interest in wireless networks

There are number of examples of geometric objects that can be of interest in wireless networks. For example, consider a collection of points in the Euclidean plane. For each point, place in the plane a disk with its center located at the point. The disks are allowed to overlap with each other and the radius of each disk is random and independent of all the other radii. The mathematical object consisting of the union of all these disks is known as a Boolean model and may represent, for example, the sensing region of a sensor network. If all the radii are not random, but common positive constant, then the resulting model is known as the Gilbert disk model.
Instead of placing disks on the plane, one may assign a disjoint subregion to each node. Then the plane is partitioned into a collection of disjoint subregions. For example, each subregion may consist of the collection of all the locations of this plane that are closer to some point of the underlying point pattern than any other point of the point pattern. This mathematical structure is known as a Voronoi tessellation and may represent, for example, the association cells in a cellular network where users associate with the closest base station.
Instead of placing a disk or a Voronoi cell on a point, one could place a cell defined from the information theoretic channels described above. For instance, the point-to-point channel cell of a point was defined as the collection of all the locations of the plane where a receiver could sustain a point-to-point channel with a certain quality from a transmitter located at this point. This, given that the other point is also an active transmitter, is a point-to-point channel in its own right.
In each case, the fact that the underlying point pattern is random or deterministic or some combination of both, will influence the nature of the Boolean model, the Voronoi tessellation, and other geometrical structures such as the point-to-point channel cells constructed from it.

Key performance quantities

In wired communication, the field of information theory motivates the need for studying the signal-to-noise ratio. In a wireless communication, when a collection of channels is active at the same time, the interference from the other channels is considered as noise, which motivates the need for the quantity known as the signal-to-interference-plus-noise ratio. For example, if we have a collection of point-to-point channels, the SINR of the channel of a particular transmitter–receiver pair is defined as:
where S is the power, at the receiver, of the incoming signal from said transmitter, I is the combined power of all the other transmitters in the network, and N is the power of some thermal noise term. The SINR reduces to SNR when there is no interference. In networks where the noise is negligible, also known as "interference limited" networks, we N = 0, which gives the signal-to-interference ratio.

Coverage

A common goal of stochastic geometry wireless network models is to derive expressions for the SINR or for the functions of the SINR which determine coverage and connectivity. For example, the concept of the outage probability pout, which is informally the probability of not being able to successfully send a signal on a channel, is made more precise in the point-to-point case by defining it as the probability that the SINR of a channel is less than or equal to some network-dependent threshold. The coverage probability pc is then the probability that the SINR is larger than the SINR threshold. In short, given a SINR threshold t, the outage and coverage probabilities are given by
and

Channel capacity

One aim of the stochastic geometry models is to derive the probability laws of the Shannon channel capacity or rate of a typical channel when taking into account the interference created by all other channels.
In the point-to-point channel case, the interference created by other transmitters is considered as noise, and when this noise is Gaussian, the law of the typical Shannon channel capacity is then determined by that of the SINR through Shannon's formula :
where B is the bandwidth of the channel in hertz. In other words, there is a direct relationship between the coverage or outage probability and the Shannon channel capacity. The problem of determining the probability distribution of C under such a random setting has been studied in several types of wireless network architectures or types.

Early history

In general, the use of methods from the theories of probability and stochastic processes in communication systems has a long and interwoven history stretching back over a century to the pioneering teletraffic work of Agner Erlang. In the setting of stochastic geometry models, Edgar Gilbert in the 1960s proposed a mathematical model for wireless networks, now known as a Gilbert disk model, that gave rise to the field of continuum percolation theory, which in turn is a generalization of discrete percolation. Starting in the late 1970s, Leonard Kleinrock and others used wireless models based on Poisson processes to study packet forward networks. This work would continue until the 1990s where it would cross paths with the work on shot noise.

Shot noise

The general theory and techniques of stochastic geometry and, in particular, point processes have often been motivated by the understanding of a type of noise that arises in electronic systems known as shot noise. For certain mathematical functions of a point process, a standard method for finding the average of the sum of these functions is Campbell's formula or theorem, which has its origins in the pioneering work by Norman R. Campbell on shot noise over a century ago. Much later in the 1960s Gilbert alongside Henry Pollak studied the shot noise process formed from a sum of response functions of a Poisson process and identically distributed random variables. The shot noise process inspired more formal mathematical work in the field of point processes, often involving the use of characteristic functions, and would later be used for models of signal interference from other nodes in the network.

Network interference as shot noise

Around the early 1990s, shot noise based on a Poisson process and a power-law repulse function was studied and observed to have a stable distribution. Independently, researchers successfully developed Fourier and Laplace transform techniques for the interference experienced by a user in a wireless network in which the locations of the nodes or transmitters are positioned according to a Poisson process. It was independently shown again that Poisson shot noise, now as a model for interference, has a stable distribution by use of characteristic functions or, equivalently, Laplace transforms, which are often easier to work with than the corresponding probability distributions.
Moreover, the assumption of the received signal power being exponentially distributed and the Poisson shot noise allows for explicit closed-form expression for the coverage probability based on the SINR. This observation helps to explain why the Rayleigh fading assumption is frequently made when constructing stochastic geometry models.

SINR coverage and connectivity models

Later in the early 2000s researchers started examining the properties of the regions under SINR coverage in the framework of stochastic geometry and, in particular, coverage processes. Connectivity in terms of the SINR was studied using techniques from continuum percolation theory. More specifically, the early results of Gilbert were generalized to the setting of the SINR case.

Model fundamentals

A wireless network consists of nodes that produce, relay or consume data within the network. For example, base stations and users in a cellular phone network or sensor nodes in a sensor network. Before developing stochastic geometry wireless models, models are required for mathematically representing the signal propagation and the node positioning. The propagation model captures how signals propagate from transmitters to receivers. The node location or positioning model represents the positions of the nodes as a point process. The choice of these models depends on the nature of the wireless network and its environment. The network type depends on such factors as the specific architecture and the channel or medium access control protocol, which controls the channels and, hence, the communicating structures of the network. In particular, to prevent the collision of transmissions in the network, the MAC protocol dictates, based on certain rules, when transmitter-receiver pairs can access the network both in time and space, which also affects the active node positioning model.

Propagation model

Suitable and manageable models are needed for the propagation of electromagnetic signals through various media, such as air, taking into account multipath propagation caused by signals colliding with obstacles such as buildings. The propagation model is a building block of the stochastic geometry wireless network model. A common approach is to consider propagation models with two separate parts consisting of the random and deterministic components of signal propagation.
The deterministic component is usually represented by some path-loss or attenuation function that uses the distance propagated by the signal for modeling the power decay of electromagnetic signals. The distance-dependent path-loss function may be a simple power-law function, a fast-decaying exponential function, some combination of both, or another decreasing function. Owing to its tractability, models have often incorporated the power-law function
where the path-loss exponent α > 2, and |x − y| denotes the distance between point y and the signal source at point x.
The random component seeks to capture certain types of signal fading associated with absorption and reflections by obstacles. The fading models in use include Rayleigh, log-normal, Rice, and Nakagami distributions.
Both the deterministic and random components of signal propagation are usually considered detrimental to the overall performance of a wireless network.

Node positioning model

An important task in stochastic geometry network models is choosing a mathematical model for the location of the network nodes. The standard assumption is that the nodes are represented by points in some space, which means they form a stochastic or random structure known as a point process.
n city of Sydney resemble a realization of a Poisson point process.

Poisson process

A number of point processes have been suggested to model the positioning of wireless network nodes. Among these, the most frequently used is the Poisson process, which gives a Poisson network model. The Poisson process in general is commonly used as a mathematical model across numerous disciplines due to its highly tractable and well-studied nature. It is often assumed that the Poisson process is homogeneous with some constant node density λ. For a Poisson process in the plane, this implies that the probability of having n points or nodes in a bounded region B is given by
where |B| is the area of B and n! denotes n factorial. The above equation quickly extends to the R3 case by replacing the area term with a volume term.
The mathematical tractability or ease of working with Poisson models is mostly because of its 'complete independence', which essentially says that two disjoint bounded regions respectively contain two a Poisson number of points that are independent to each other. This important property characterizes the Poisson process and is often used as its definition.
The complete independence or `randomness' property of Poisson processes leads to some useful characteristics and results of point process operations such as the superposition property: the superposition of Poisson processes with densities λ1 to λn is another Poisson process with density
Furthermore, randomly thinning a Poisson process, where each point is independently removed with some probability p, forms another Poisson process while the kept points also form a Poisson process that is independent to the Poisson process of removed points.
These properties and the definition of the homogeneous Poisson process extend to the case of the inhomogeneous Poisson process, which is a non-stationary stochastic process with a location-dependent density λ where x is a point . For more information, see the articles on the Poisson process.

Other point processes

Despite its simplifying nature, the independence property of the Poisson process has been criticized for not realistically representing the configuration of deployed networks. For example, it does not capture node "repulsion" where two nodes in a wireless network may not be normally placed close to each other. In addition to this, MAC protocols often induce correlations or non-Poisson configurations into the geometry of the simultaneously active transmitter pattern. Strong correlations also arise in the case of cognitive radio networks where secondary transmitters are only allowed to transmit if they far from primary receivers. To answer these and other criticisms, a number of point processes have been suggested to represent the positioning of nodes including the binomial process, cluster processes, Matérn hard-core processes, H. Q. Nguyen, F. Baccelli, and D. Kofman. A stochastic geometry analysis of dense IEEE 802.11 networks. In INFOCOM'07, pages 1199–1207, 2007. 6–12 May 2007, Anchorage, Alaska, USA. T. V. Nguyen and F. Baccelli. A stochastic geometry model for cognitive radio networks. Comput. J., 55:534–552, 2012. and Strauss and Ginibre processes. For example, Matérn hard-core processes are constructed by dependently thinning a Poisson point process. The dependent thinning is done in way such that for any point in the resulting hard-core process, there are no other points within a certain set radius of it, thus creating a "hard-core" around each point in the process. On the other hand, soft-core processes have point repulsion that ranges somewhere between the hard-core processes and Poisson processes. More specifically, the probability of a point existing near another point in a soft-core point process decreases in some way as it approaches the other point, thus creating a "soft-core" around each point where other points can exist, but are less likely.
Although models based on these and other point processes come closer to resembling reality in some situations, for example in the configuration of cellular base stations, they often suffer from a loss of tractability while the Poisson process greatly simplifies the mathematics and techniques, explaining its continued use for developing stochastic geometry models of wireless networks. Also, it has been shown that the SIR distribution of non-Poisson cellular networks can be closely approximated by applying a horizontal shift to the SIR distribution of a Poisson network.

Classification of models

The type of network model is a combination of factors such as the network architectural organization, the medium access control protocol being used, the application running on it, and whether the network is mobile or static.

Models based on specific network architectures

Around the beginning of the 21st century a number of new network technologies have arisen including mobile ad hoc networks and sensor networks. Stochastic geometry and percolation techniques have been used to develop models for these networks. The increases in user traffic has resulted in stochastic geometry being applied to cellular networks.

Mobile ''ad hoc'' network models

Poisson bipolar network model is a type of stochastic geometry model based on the Poisson process and is an early example of a model for mobile ad hoc networks, which are a self-organizing wireless communication network in which mobile devices rely on no infrastructure. In MANET models, the transmitters form a random point process and each transmitter has its receiver located at some random distance and orientation. The channels form a collection of transmitter-receiver pairs or "bipoles"; the signal of a channel is that transmitted over the associated bipole, whereas the interference is that created by all other transmitters than that of the bipole. The approach of considering the transmitters-receive bipoles led to the development and analysis of one of the Poisson bipolar network model. The choice of the medium access probability, which maximizes the mean number of successful transmissions per unit space, was in particular derived in.

Sensor network models

A wireless sensor network consists of a spatially distributed collection of autonomous sensor nodes. Each node is designed to monitor physical or environmental conditions, such as temperature, sound, pressure, etc. and to cooperatively relay the collected data through the network to a main location. In unstructured sensor networks, the deployment of nodes may be done in a random manner. A chief performance criterion of all sensor networks is the ability of the network to gather data, which motivates the need to quantify the coverage or sensing area of the network. It is also important to gauge the connectivity of the network or its capability of relaying the collected data back to the main location.
The random nature of unstructured sensors networks has motivated the use of stochastic geometry methods. For example, the tools of continuous percolation theory and coverage processes have been used to study the coverage and connectivity. One model that is used to study to these networks and wireless networks in general is the Poisson-Boolean model, which is a type of coverage process from continuum percolation theory.
One of the main limitations of sensor networks is energy consumption where usually each node has a battery and, perhaps, an embedded form of energy harvesting. To reduce energy consumption in sensor networks, various sleep schemes have been suggested that entail having a sub-collection of nodes go into a low energy-consuming sleep mode. These sleep schemes obviously affect the coverage and connectivity of sensor networks. Rudimentary power-saving models have been proposed such as the simple uncoordinated or decentralized "blinking" model where each node independently powers down with some fixed probability. Using the tools of percolation theory, a new type model referred to as a blinking Boolean-Poisson model, was proposed to analyze the latency and connectivity performance of sensor networks with such sleep schemes.

Cellular network models

A cellular network is a radio network distributed over some region with subdivisions called cells, each served by at least one fixed-location transceiver, known as a cell base station. In cellular networks, each cell uses a different set of frequencies from neighboring cells, to mitigate interference and provide higher bandwidth within each cell. The operators of cellular networks need to known certain performance or quality of service metrics in order to dimension the networks, which means adjusting the density of the deployed base stations to meet the demand of user traffic for a required QoS level.
In cellular networks, the channel from the users to the base station is known as the uplink channel. Conversely, the downlink channel is from he base station to the users. The downlink channel is the most studied with stochastic geometry models while models for the uplink case, which is a more difficult problem, are starting to be developed.
In the downlink case, the transmitters and the receivers can be considered as two separate point processes. In the simplest case, there is one point-to-point channel per receiver, and for a given receiver, this channel is from the closest transmitter to the receiver. Another option consists in selecting the transmitter with the best signal power to the receiver. In any case, there may be several channels with the same transmitter.
A first approach for analyzing cellular networks is to consider the typical user, who can be assumed to be located anywhere on the plane. Under the assumption of point process ergodicity, the results for the typical user correspond to user averages. The coverage probability of the typical user is then interpreted as the proportion of network users who can connect to the cellular network.
Building off previous work done on an Aloha model, the coverage probability for the typical user was derived for a Poisson network. The Poisson model of a cellular network proves to be more tractable than a hexagonal model. Meanwhile, this observation could be argued by the fact that a detailed and precise derivation for the channel attenuation probability distribution function between a random node and a reference base-station for a hexagonal model was explicitly derived in; and this result could be used to tractably derive the outage probability.
In the presence of sufficiently strong and independent log-normal shadow fading and a singular power-law attenuation function, it was observed by simulation for hexagonal networks and then later mathematically proved that for general stationary networks that quantities like the SINR and SIR of the typical user behave stochastically as though the underlying network were Poisson. In other words, given a path loss function, using a Poisson cellular network model with constant shadowing is equivalent to assuming sufficiently large and independent fading or shadowing in the mathematical model with the base stations positioned according to either a deterministic or random configuration with a constant density.
The results were originally derived for log-shadowing, but then extended to a large family of fading and shadowing models For log- normal shadowing, it has also been mathematically shown that the wireless networks can still appear Poisson if there some correlation among the shadowing.

Heterogeneous cellular network models

In the context of cellular networks, a heterogeneous network is a network that uses several types of base stations macro-base stations, pico-base stations, and/or femto-base stations in order to provide better coverage and bit rates. This is in particular used to cope with the difficulty of covering with macro-base stations only open outdoor environment, office buildings, homes, and underground areas. Recent Poisson-based models have been developed to derive the coverage probability of such networks in the downlink case. The general approach is to have a number or layers or "tiers"' of networks which are then combined or superimposed onto each other into one heterogeneous or multi-tier network. If each tier is a Poisson network, then the combined network is also a Poisson network owing to the superposition characteristic of Poisson processes. Then the Laplace transform for this superimposed Poisson model is calculated, leading to the coverage probability in of a cellular network with multiple tiers when a user is connected to the instantaneously strongest base station and when a user is connected to the strongest base station on average.

Cellular network models with multiple users

In recent years the model formulating approach of considering a "typical user" in cellular networks has been used considerably. This is, however, just a first approach which allows one to characterize only the spectral efficiency of the network. In other words, this approach captures the best possible service that can be given to a single user who does not need to share wireless network resources with other users.
Models beyond the typical user approach have been proposed with the aim of analyzing QoS metrics of a population of users, and not just a single user. Broad speaking, these models can be classified into four types: static, semi-static, semi-dynamic and dynamic. More specifically:
The ultimate goal when constructing these models consists of relating the following three key network parameters: user traffic demand per surface unit, network density and user QoS metric. These relations form part of the network dimensioning tools, which allow the network operators to appropriately vary the density of the base stations to meet the traffic demands for a required performance level.

Models based on MAC protocols

The MAC protocol controls when transmitters can access the wireless medium. The aim is to reduce or prevent collisions by limiting the power of interference experienced by an active receiver. The MAC protocol determines the pattern of simultaneously active channels, given the underlying pattern of available channels. Different MAC protocols hence perform different thinning operations on the available channels, which results in different stochastic geometry models being needed.

Aloha MAC models

A slotted Aloha wireless network employs the Aloha MAC protocol where the channels access the medium, independently at each time interval, with some probability p. If the underlying channels are positioned according to a Poisson process, then the nodes accessing the network also form a Poisson network, which allows the use of the Poisson model. ALOHA is not only one of the simplest and most classic MAC protocol but also was shown to achieve Nash equilibria when interpreted as a power control schemes.
Several early stochastic models of wireless networks were based on Poisson point processes with the aim of studying the performance of slotted Aloha. Under Rayleigh fading and the power-law path-loss function, outage probability expressions were derived by treating the interference term as a shot noise and using Laplace transforms models, which was later extended to a general path-loss function, F. Baccelli, P. Mühlethaler, and B. Błaszczyszyn. Stochastic analysis of spatial and opportunistic aloha. IEEE Journal on Selected Areas in Communications, 27:1105–1119, 2009. and then further extended to a pure or non-slotted Aloha case.

Carrier sense multiple access MAC models

The carrier sense multiple access MAC protocol controls the network in such a way that channels close to each other never simultaneously access the medium simultaneously. When applied to a Poisson point process, this was shown to naturally lead to a Matérn-like hard-core point process which exhibits the desired "repulsion". The probability for a channel to be scheduled is known in closed-form, as well as the so-called pair-correlation function of the point process of scheduled nodes.

Code division multiple access MAC models

In a network with code division multiple access MAC protocol, each transmitter modulates its signal by a code that is orthogonal to that of the other signals, and which is known to its receiver. This mitigates the interference from other transmitters, and can be represented in a mathematical model by multiplying the interference by an orthogonality factor. Stochastic geometry models based on this type of representation were developed to analyze the coverage areas of transmitters positioned according to a Poisson process.

Network information theoretic models

In the previous MAC-based models, point-to-point channels were assumed and the interference was considered as noise. In recent years, models have been developed to study more elaborate channels arising from the discipline of network information theory. More specifically, a model was developed for one of the simplest settings: a collection of transmitter-receiver pairs represented as a Poisson point process. In this model, the effects of an interference reduction scheme involving "point-to-point codes" were examined. These codes, consisting of randomly and independently generated codewords, give transmitters-receivers permission when to exchange information, thus acting as a MAC protocol. Furthermore, in this model a collection or "party" of channels was defined for each such pair. This party is a multiple access channel, namely the many-to-one situation for channels. The receiver of the party is the same as that of the pair, and the transmitter of the pair belongs to the set of transmitters of the party, together with other transmitters. Using stochastic geometry, the probability of coverage was derived as well as the geometric properties of the coverage cells. It was also shown that when using the point-to-point codes and simultaneous decoding, the statistical gain obtained over a Poisson configuration is arbitrarily large compared to the scenario where interference is treated as noise.

Other network models

Stochastic geometry wireless models have been proposed for several network types including cognitive radio networks, relay networks, and vehicular ad hoc networks.

Textbooks on stochastic geometry and related fields

  • Stochastic Geometry for Wireless Networks – Haenggi
  • Stochastic Geometry and its Applications – Stoyan, Kendall and Mecke
  • New Perspectives in Stochastic Geometry – Kendall and Molchanov, eds.
  • Stochastic Geometry and Wireless Networks Volume I: Theory – Baccelli and Błaszczyszyn
  • Stochastic Geometry and Wireless Networks Volume II: Applications – Baccelli and Błaszczyszyn
  • Random networks for Communication: From Statistical Physics to Information Systems – Franceschetti and Meester
  • Analytical Modeling of Heterogeneous Cellular Networks: Geometry, Coverage, and Capacity – Mukherjee
  • Poisson processes – Kingman