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.F. Baccelli and B. Błaszczyszyn. Stochastic Geometry and Wireless Networks, Volume I — Theory, volume 3, No 3–4 of Foundations and Trends in Networking. NoW Publishers, 2009.F. Baccelli and B. Błaszczyszyn. Stochastic Geometry and Wireless Networks, Volume II — Applications, volume 4, No 1–2 of Foundations and Trends in Networking. NoW Publishers, 2009.W. S. Kendall and I. Molchanov, eds. New Perspectives in Stochastic Geometry. Oxford University Press, 2010.M. Haenggi. Stochastic geometry for wireless networks. Cambridge University Press, 2012.
In the early 1960s a stochastic geometry modelE. N. Gilbert. Random plane networks. Journal of the Society for Industrial \& Applied Mathematics, 9(4):533–543, 1961. was developed to study wireless networks. This model is considered to be pioneering and the origin of continuum percolation.M. Franceschetti and R. Meester. Random networks for communication: from statistical physics to information systems, volume 24. Cambridge University Press, 2007. Network models based on geometric probability were later proposed and used in the late 1970sL. Kleinrock and J. Silvester. Optimum transmission radii for packet radio networks or why six is a magic number. In IEEE National Telecommunications, pages 4.31–4.35, 1978. and continued throughout the 1980sL. Kleinrock and J. Silvester. Spatial reuse in multihop packet radio networks. Proceedings of the IEEE, 75(1):156–167, 1987.H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246–257, 1984. 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.J. G. Andrews, R. K. Ganti, M. Haenggi, N. Jindal, and S. Weber. A primer on spatial modeling and analysis in wireless networks. Communications Magazine, IEEE, 48(11):156–163, 2010.M. Haenggi, J. Andrews, F. Baccelli, O. Dousse, and M. Franceschetti. Stochastic geometry and random graphs for the analysis and design of wireless networks. IEEE JSAC, 27(7):1029–1046, September 2009.S. Mukherjee. Analytical Modeling of Heterogeneous Cellular Networks: Geometry, Coverage, and Capacity. Cambridge University Press, 2014. 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 (possibly intractable or inaccurate) deterministic models.
Overview
The discipline of stochastic geometry entails the mathematical study of random objects defined on some (often Euclidean) space. In the context of wireless networks, the random objects are usually simple points (which may represent the locations of network nodes such as receivers and transmitters) or shapes (for example, the coverage area of a transmitter) and the Euclidean space is either 3-dimensional, or more often, the (2-dimensional) plane, which represents a geographical region. In wireless networks (for example, cellular networks) the underlying geometry (the relative locations of nodes) plays a fundamental role due to the interference of other transmitters, whereas in wired networks (for example, the Internet) the underlying geometry is less important.
Channels in a wireless network
A wireless network can be seen as a collection of (information theoretic) 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,Cover, Thomas M and Thomas, Joy A, Elements of information theory,2012, John Wiley & Sons. 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.Tse David and Pramod Viswanath, Fundamentals of wireless communication, 2005, Cambridge university press. 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 (information theoretic) 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 (stochastically) independent of all the other radii. The mathematical object consisting of the union of all these disks is known as a Boolean (random disk) modelD. Stoyan, W. S. Kendall, J. Mecke, and L. Ruschendorf. Stochastic geometry and its applications, volume 2. Wiley Chichester, 1995.P. Hall. Introduction to the theory of coverage processes, volume 1. Wiley New York, 1988. 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 (Boolean) model.Balister, Paul and Sarkar, Amites and Bollobás, Béla, Percolation, connectivity, coverage and colouring of random geometric graphs, Handbook of Large-Scale Random Networks, 117–142, 2008
Instead of placing disks on the plane, one may assign a disjoint (or non-overlapping) 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 definedF. Baccelli and B. Błaszczyszyn. On a coverage process ranging from the Boolean model to the Poisson–Voronoi tessellation with applications to wireless communications. Advances in Applied Probability, 33(2):293–323, 2001. 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 (for example, a point process) or deterministic (for example, a lattice of points) 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 (in particular, the Shannon–Hartley theorem) motivates the need for studying the signal-to-noise ratio (SNR). 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 (SINR). 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 (interfering) transmitters in the network, and N is the power of some thermal noise term. The SINR reduces to SNR when there is no interference (i.e. I = 0). In networks where the noise is negligible, also known as "interference limited" networks, we N = 0, which gives the signal-to-interference ratio (SIR).
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 (or outage) 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.M. Zorzi and S. Pupolin. Outage probability in multiple access packet radio networks in the presence of fading. Vehicular Technology, IEEE Transactions on, 43(3):604–610, 1994. 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 (in bits per second):
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