Stochastic geometry models of wireless networks

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.[1][2][3][4]

In the early 1960s a pioneering stochastic geometry model [5] was developed to study wireless networks. This model is considered to be the origin of continuum percolation.[6] Network models based on geometric probability were later proposed and used in the late 1970s [7] and continued throughout the 1980s [8][9] 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.[10][11][12] 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.[11]

The principal idea underlying the research of these stochastic geometry models, also known as random spatial models,[10] 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.[10]

Overview[edit]

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[edit]

Different channel types in wireless networks .
Three channel types or connection situations in wireless networks.

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,[13] 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.[14] The multiple access channel is the converse, with several transmitters aiming at sending different data to a single receiver.[13] This many-to-one situation arises in, for example, the uplink of cellular networks.[14] 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[edit]

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) model [15][16] 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.[17]

Possible coverage model.
A Boolean model as a coverage model in a wireless network.
Percolation in the Boolean-Poisson (constant disk) model.
Simulation of four Poisson–Boolean (constant-radius or Gilbert disk) models as the density increases with largest clusters in red.

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, on 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 [18] 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[edit]

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:

\mathrm{SINR}=\frac{S}{I+N}

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[edit]

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 lesser than or equal to some network-dependent threshold.[19] 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

p_{\mathrm{out}}=P(\mathrm{SINR}\leq t)

and

p_{\mathrm{c}}=P(\mathrm{SINR}>t)=1-p_{\mathrm{out}}.
SINR cells.
SINR cells of a wireless network model expand as the transmitter powers increase.

Channel capacity[edit]

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):

C= B  \log_2(1+\mathrm{SINR})

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[edit]

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.[20] In the setting of stochastic geometry models, Edgar Gilbert [5] in the 1960s proposed a mathematical model for wireless networks, now known as a Gilbert disk model,[17] that gave rise to the field of continuum percolation theory, which in turn is a generalization of discrete percolation.[6] Starting in the late 1970s, Leonard Kleinrock and others used wireless models based on Poisson processes to study packet forward networks.[7][8][9] This work would continue until the 1990s where it would cross paths with the work on shot noise.

Shot noise[edit]

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. Indeed, given some mathematical function of a point process, a standard method for finding the average (or expectation) of the sum of these functions is Campbell's formula [21] or theorem,[22] which has its origins in the pioneering work by Norman R. Campbell on shot noise over a century ago.[23][24] Much later in the 1960s Gilbert alongside Henry Pollak studied the shot noise process [25] 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,[26][27] 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[edit]

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.[28] Independently, researchers [19][29] successfully developed Fourier and Laplace transform techniques for the interference experienced by a user in a wireless network in which the locations of the (interfering) 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 [29] by use of characteristic functions or, equivalently, Laplace transforms, which are often easier to work with than the corresponding probability distributions.[1][2][30]

Moreover, the assumption of the received (i.e. useful) signal power being exponentially distributed (for example, due to Rayleigh fading) and the Poisson shot noise (for which the Laplace is known) allows for explicit closed-form expression for the coverage probability based on the SINR.[19][31] This observation helps to explain why the Rayleigh fading assumption is frequently made when constructing stochastic geometry models.[1][2][4]

SINR coverage and connectivity models[edit]

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.[18] 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.[32][33]

Model fundamentals[edit]

A wireless network consists of nodes (each of which is a transmitter, receiver or both, depending on the system) 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 (idealizes and) 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 (for instance cellular) and the channel or medium access control (MAC) 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[edit]

Suitable and manageable models are needed for the propagation of electromagnetic signals (or waves) through various media, such as air, taking into account multipath propagation (due to reflection, refraction, diffraction and dispersion) 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 (or non-random) 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 (from its source) for modeling the power decay of electromagnetic signals. The distance-dependent path-loss function may be a simple power-law function (for example, the Hata model), 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

  \ell(|x-y|){{=}}  |x-y|^{\alpha},

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 (implying exponential random variables for the power), 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[edit]

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 (idealized) points in some space (often Euclidean Rn, and even more often in the plane R2), which means they form a stochastic or random structure known as a (spatial) point process.[10]

Sydney at night time.
Locations of cellular or mobile phone base stations resemble a Poisson point process in the Australian city of Sydney.[34]

Poisson process[edit]

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.[10] The Poisson process in general is commonly used as a mathematical model across numerous disciplines due to its highly tractable and well-studied nature.[15][22] It is often assumed that the Poisson process is homogeneous (implying it is a stationary process) 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

P(n){{=}}\frac{\lambda |B|^n}{n!} e^{-\lambda |B|},

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 (or more) disjoint (or non-overlapping) bounded regions respectively contain two (or more) 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.[22]

The complete independence or `randomness' [35] property of Poisson processes leads to some useful characteristics and results of point process operations such as the superposition property: the superposition of n Poisson processes with densities λ1 to λn is another Poisson process with density

\lambda{{=}}\sum_{i=1}^n\lambda_i.

Furthermore, randomly thinning a Poisson process (with density λ), where each point is independently removed (or kept) with some probability p (or 1 − p), forms another Poisson process (with density (1 − p)λ) while the kept points also form a Poisson process (with density ) that is independent to the Poisson process of removed points.[15][22]

These properties and the definition of the homogeneous Poisson process extend to the case of the inhomogeneous (or non-homogeneous) Poisson process, which is a non-stationary stochastic process with a location-dependent density λ(x) where x is a point (usually in the plane, R2) . For more information, see the articles on the Poisson process.

Other point processes[edit]

Despite its simplifying nature, the independence property of the Poisson process has been criticized for not realistically representing the configuration of deployed networks.[34] For example, it does not capture node "repulsion" where two (or more) nodes in a wireless network may not be normally placed (arbitrarily) close to each other (for examples, base stations in a cellular network). 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,[2][36][37] and Strauss and Ginibre processes.[10][38] 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.[15] On the other hand, soft-core processes have point repulsion that ranges somewhere between the hard-core processes and Poisson processes (which have no repulsion). 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,[34] 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.[10]

Classification of models[edit]

The type of network model is a combination of factors such as the network architectural organization (cellular, ad hoc, cognitive radio), the medium access control (MAC) protocol being used, the application running on it, and whether the network is mobile or static.

Models based on specific network architectures[edit]

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.[2][39] The increases in user traffic has resulted in stochastic geometry being applied to cellular networks.[40]

Mobile ad hoc network models[edit]

A mobile ad hoc network (MANET) is a self-organizing wireless communication network in which mobile devices rely on no infrastructure (base stations or access points). 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 first stochastic geometry models for MANETs known as a Poisson bipole model.[2][31][41] The choice of the medium access probability, which maximizes the mean number of successful transmissions per unit space, was in particular derived in.[31]

Sensor network models[edit]

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,[42] 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.[39][43] 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 (at each time interval) each node independently powers down (or up) 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.[39]

Cellular network models[edit]

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 (QoS) 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 (or phones) to the base station(s) is known as the uplink channel. Conversely, the downlink channel is from he base station(s) 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.[44]

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 (i.e. the user), and for a given receiver, this channel is from the closest transmitter (i.e. the base station) 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 a "typical user" located somewhere in the network. Under the assumption of network stationarity (satisfied when using homogeneous Poisson processes), 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,[41] the coverage probability for a typical user was derived for a Poisson network.[40][45] The Poisson model of a cellular network proves to be more tractable than a hexagonal model.[40] Moreover, in the presence of sufficiently large log-normal shadow fading (or shadowing) and a singular power-law attenuation function, it was observed by simulation [46] for hexagonal networks and then later mathematically proved [47] for general stationary (including hexagonal) 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 power-law attention function, using a Poisson cellular network model with constant shadowing is equivalent (in terms of SIR, SINR, etc.) to assuming large log-normal shadowing in the mathematical model with the base stations positioned according to either a deterministic or random configuration with a constant density.[47]

Heterogeneous cellular network models[edit]

In the context of cellular networks, a heterogeneous network (sometimes known as a HetNet) 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.[48][49] 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.[22] Then the Laplace transform for this superimposed Poisson model is calculated, leading to the coverage probability in (the downlink channel chainr) of a cellular network with multiple tiers.[48]

Cellular network models with multiple users[edit]

In recent years the model formulating approach of considering a "typical user" in cellular (or other) networks has been used considerably. This is, however, just a first approach which allows one to characterize only the spectral efficiency (or information rate) 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 (fully) dynamic.[50] More specifically:

  • Static models have a given number of active users with fixed positions.
  • Semi-static models consider the networks at certain times by representing instances or "snapshots" of active users as realizations of spatial (usually Poisson) processes.[51][52][53][54][55]
  • Semi-dynamic models have the phone calls of users occur at a random location and last for some random duration. Furthermore, it is assumed that each user is motionless during its call.[50][53][56] In this model, spatial birth-and-death processes,[57][58] which are, in a way, spatial extensions of (time-only) queueing models (for example, Erlang loss systems and processor sharing models), are used in this context to evaluate time averages of the user QoS metrics. Queueing models have been successfully used to dimension (or to suitably adjust the parameters of) circuit-switched and other communication networks. Adapting these models to the task of the dimensioning of the radio part of wireless cellular networks requires appropriate space-time averaging over the network geometry and the temporal evolution of the user (phone call) arrival process.[59]
  • Dynamic models are more complicated and have the same assumptions as the semi-dynamic model, but users may move during their calls.[60][61][62][63]

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(s). 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[edit]

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[edit]

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.[2] If the underlying channels (that is, their transmitters for the point-to-point case) are positioned according to a Poisson process (with density λ), then the nodes accessing the network also form a Poisson network (with density ), which allows the use of the Poisson model.

Several early stochastic models of wireleess networks were based on Poisson point processes with the aim of studying the performance of slotted Aloha.[7][64][65] Under Rayleigh fading and the power-law path-loss function, outage (or equivalently, coverage) probability expressions were derived by treating the interference term as a shot noise and using Laplace transforms models,[19][66] which was later extended to a general path-loss function,[31][41][67] and then further extended to a pure or non-slotted Aloha case.[68]

Carrier sense multiple access MAC models[edit]

The carrier sense multiple access (CSMA) 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 (or soft-core in the case of fading) point process which exhibits the desired "repulsion".[2][36] 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.[2]

Code division multiple access MAC models[edit]

In a network with code division multiple access (CDMA) 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.[18]

Network information theoretic models[edit]

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.[69] More specifically, a model was developed for one of the simplest settings: a collection of transmitter-receiver pairs represented as a Poisson point process.[70] 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,[69] 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.[70] It was also shown [69] 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[edit]

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

See also[edit]

Textbooks on stochastic geometry and related fields[edit]

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

External links[edit]

For further reading of stochastic geometry wireless network models, see the two-volume text by Baccelli and Błaszczyszyn [1][2] (available online) and the survey article.[11] For interference in wireless networks, see the monograph on interference by Ganti and Haenggi[30] (available online). For an introduction to stochastic geometry and spatial statistics in a more general setting, see the lectures notes by Baddeley [21] (available online with Springer subscription). For a complete and rigorous treatment of point processes, see the two-volume text by Daley and Vere-Jones [35][74] (available online with Springer subscription).

References[edit]

  1. ^ a b c d e 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.
  2. ^ a b c d e f g h i j k 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.
  3. ^ a b W. S. Kendall and I. Molchanov, eds. New Perspectives in Stochastic Geometry. Oxford University Press, 2010.
  4. ^ a b c M. Haenggi. Stochastic geometry for wireless networks. Cambridge University Press, 2012.
  5. ^ a b E. N. Gilbert. Random plane networks. Journal of the Society for Industrial \& Applied Mathematics, 9(4):533–543, 1961.
  6. ^ a b c M. Franceschetti and R. Meester. Random networks for communication: from statistical physics to information systems, volume 24. Cambridge University Press, 2007.
  7. ^ a b c L. 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.
  8. ^ a b L. Kleinrock and J. Silvester. Spatial reuse in multihop packet radio networks. Proceedings of the IEEE, 75(1):156–167, 1987.
  9. ^ a b H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246–257, 1984.
  10. ^ a b c d e f g 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.
  11. ^ a b c 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.
  12. ^ a b S. Mukherjee. Analytical Modeling of Heterogeneous Cellular Networks: Geometry, Coverage, and Capacity. Cambridge University Press, 2014.
  13. ^ a b Cover, Thomas M and Thomas, Joy A, Elements of information theory,2012, John Wiley & Sons.
  14. ^ a b Tse David and Pramod Viswanath, Fundamentals of wireless communication,2005, Cambridge university press.
  15. ^ a b c d e D. Stoyan, W. S. Kendall, J. Mecke, and L. Ruschendorf. Stochastic geometry and its applications, volume 2. Wiley Chichester, 1995.
  16. ^ P. Hall. Introduction to the theory of coverage processes, volume 1. Wiley New York, 1988.
  17. ^ a b 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
  18. ^ a b c F. 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.
  19. ^ a b c d 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.
  20. ^ A. K. Erlang. The theory of probabilities and telephone conversations. Nyt Tidsskrift for Matematik B, 20(33–39):16, 1909.
  21. ^ a b A. Baddeley, I. Barany, and R. Schneider. Spatial point processes and their applications. Stochastic Geometry: Lectures given at the CIME Summer School held in Martina Franca, Italy, September 13–18, 2004, pages 1–75, 2007. R
  22. ^ a b c d e f J. F. C. Kingman. Poisson processes, volume 3. Oxford university press, 1992.
  23. ^ N. Campbell. Discontinuities in light emission. In Proc. Cambridge Phil. Soc, volume 15, page 3, 1909.
  24. ^ N. Campbell. The study of discontinuous phenomena. In Proc. Camb. Phil. Soc, volume 15, page 310, 1909.
  25. ^ E. Gilbert and H. Pollak. Amplitude distribution of shot noise. Bell Syst. Tech. J, 39(2):333–350, 1960.
  26. ^ D. Daley. The definition of a multi-dimensional generalization of shot noise. Journal of Applied Probability, pages 128–135, 1971.
  27. ^ J. Rice. "On generalized shot noise." Advances in Applied Probability (1977): 553–565.
  28. ^ S. B. Lowen and M. C. Teich. Power-law shot noise. Information Theory, IEEE Transactions on, 36(6):1302–1318, 1990.
  29. ^ a b E. S. Sousa and J. A. Silvester. Optimum transmission ranges in a direct-sequence spread-spectrum multihop packet radio network. Selected Areas in Communications, IEEE Journal on, 8(5):762–771, 1990.
  30. ^ a b M. Haenggi and R. K. Ganti. Interference in large wireless networks. Now Publishers Inc, 2009.
  31. ^ a b c d F. Baccelli, B. Błaszczyszyn, and P. Mühlethaler. A spatial reuse Aloha MAC protocol for multihop wireless mobile networks. In Proc. of Annual Conf. on Communication, Allerton, September 2003.
  32. ^ O. Dousse, F. Baccelli, and P. Thiran. Impact of interferences on connectivity in ad hoc networks. Networking, IEEE/ACM Transactions on, 13(2):425–436, 2005.
  33. ^ O. Dousse, M. Franceschetti, N. Macris, R. Meester, and P. Thiran. Percolation in the signal to interference ratio graph. Journal of Applied Probability, pages 552–562, 2006.
  34. ^ a b c C.-H. Lee, C.-Y. Shih, and Y.-S. Chen. Stochastic geometry based models for modeling cellular networks in urban areas. Wireless Networks, pages 1–10, 2012.
  35. ^ a b D. J. Daley and D. Vere-Jones. An introduction to the theory of point processes. Vol. I. Probability and its Applications (New York). Springer, New York, second edition, 2003.
  36. ^ a b 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.
  37. ^ T. V. Nguyen and F. Baccelli. A stochastic geometry model for cognitive radio networks. Comput. J., 55(5):534–552, 2012.
  38. ^ N. Miyoshi and T. Shirai. A cellular network model with Ginibre configurated base stations. Research Reports on Mathematical and Computing Sciences, 2012.
  39. ^ a b c O. Dousse, P. Mannersalo, and P. Thiran. Latency of wireless sensor networks with uncoordinated power saving mechanisms. In Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, pages 109–120. ACM, 2004.
  40. ^ a b c J. G. Andrews, F. Baccelli, and R. K. Ganti. A tractable approach to coverage and rate in cellular networks. Communications, IEEE Transactions on, 59(11):3122–3134, 2011.
  41. ^ a b c F. Baccelli, B. Błaszczyszyn, and P. Mühlethaler. An aloha protocol for multihop mobile wireless networks. Information Theory, IEEE Transactions on, 52(2):421–436, 2006.
  42. ^ J. Yick, B. Mukherjee, and D. Ghosal. Wireless sensor network survey. Computer networks, 52(12):2292–2330, 2008.
  43. ^ C. Gui and P. Mohapatra. Power conservation and quality of surveillance in target tracking sensor networks. In Proceedings of the 10th annual international conference on Mobile computing and networking, pages 129–143. ACM, 2004.
  44. ^ T. Novlan, H. Dhillon, and J. Andrews. Analytical modeling of uplink cellular networks. 2012.
  45. ^ H. P. Keeler, B. Błaszczyszyn, M. K. Karray, et al. Sinr-based k-coverage probability in cellular networks with arbitrary shadowing. In ISIT 2013 IEEE International Symposium on Information Theory, 2013.
  46. ^ T. X. Brown. Cellular performance bounds via shotgun cellular systems. Selected Areas in Communications, IEEE Journal on, 18(11):2443–2455, 2000.
  47. ^ a b B. Błaszczyszyn, M. Karray, and H. Keeler. Using poisson processes to model lattice cellular networks. In INFOCOM, 2013 Proceedings IEEE, pages 773–781, 2013.
  48. ^ a b H. S. Dhillon, R. K. Ganti, F. Baccelli, and J. G. Andrews. Modeling and analysis of K-tier downlink heterogeneous cellular networks. Selected Areas in Communications, IEEE Journal on, 30(3):550–560, 2012.
  49. ^ P. Madhusudhanan, J. G. Restrepo, Y. Liu, T. X. Brown, and K. R. Baker. Multi-tier network performance analysis using a shotgun cellular system. In Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE, pages 1–6. IEEE, 2011.
  50. ^ a b F. Baccelli, B. Błaszczyszyn, and M. K. Karray. Blocking rates in large CDMA networks via a spatial erlang formula. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 1, pages 58–67. IEEE, 2005.
  51. ^ K. S. Gilhousen, I. M. Jacobs, R. Padovani, A. J. Viterbi, J. LA Weaver, and C. E. Wheatley III. On the capacity of a cellular CDMA system. Vehicular Technology, IEEE Transactions on, 40(2):303–312, 1991.
  52. ^ A. M. Viterbi and A. J. Viterbi. Erlang capacity of a power controlled CDMA system. Selected Areas in Communications, IEEE Journal on, 11(6):892–900, 1993.
  53. ^ a b Z. Liu and M. El Zarki. {SIR}-based call admission control for DS-CDMA cellular systems. Selected Areas in Communications, IEEE Journal on, 12(4):638–644, 1994.
  54. ^ F. Baccelli, B. Błaszczyszyn, and F. Tournois. Spatial averages of downlink coverage characteristics in CDMA networks. In INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 1, pages 381–390. IEEE, 2002.
  55. ^ B. Błaszczyszyn and M. K. Karray. Performance evaluation of scalable congestion control schemes for elastic traffic in cellular networks with power control. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 170–178. IEEE, 2007.
  56. ^ C. Preston. Spatial birth-and-death processes. In Proceedings of the 40th Session of the International Statistical Institute (Warsaw, 1975), volume 2, pages 371–391, 1977.
  57. ^ F. Baccelli, B. Błaszczyszyn, M. K. Karray, et al. A spatial markov queueing process and its applications to wireless loss systems. 2007.
  58. ^ B. Błaszczyszyn, M. Jovanovic, and M. K. Karray. Mean user throughput versus traffic demand in large irregular cellular networks-a typical cell approach explaining real field measurements. arXiv preprint arXiv:1307.8409, 2013.
  59. ^ M. Sidi and D. Starobinski. New call blocking versus handoff blocking in cellular networks. Wireless networks, 3(1):15–27, 1997.
  60. ^ K. Mitchell and K. Sohraby. An analysis of the effects of mobility on bandwidth allocation strategies in multi-class cellular wireless networks. In INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 2, pages 1005–1011. IEEE, 2001.
  61. ^ T. Bonald and A. Proutiere. Conservative estimates of blocking and outage probabilities in CDMA networks. Performance Evaluation, 62(1):50–67, 2005.
  62. ^ B. Błaszczyszyn and M. K. Karray. Impact of mean user speed on blocking and cuts of streaming traffic in cellular networks. In Wireless Conference, 2008. EW 2008. 14th European, pages 1–7. IEEE, 2008.
  63. ^ R. Nelson and L. Kleinrock. The spatial capacity of a slotted aloha multihop packet radio network with capture. Communications, IEEE Transactions on, 32(6):684–694, 1984.
  64. ^ J. Silvester and L. Kleinrock. On the capacity of multihop slotted aloha networks with regular structure. Communications, IEEE Transactions on, 31(8):974–982, 1983.
  65. ^ J.-P. Linnartz. Exact analysis of the outage probability in multiple-user mobile radio. Communications, IEEE Transactions on, 40(1):20–23, 1992.
  66. ^ F. Baccelli, P. Mühlethaler, and B. Błaszczyszyn. Stochastic analysis of spatial and opportunistic aloha. IEEE Journal on Selected Areas in Communications, 27(7):1105–1119, 2009.
  67. ^ B. Błaszczyszyn and P. Mühlethaler. Stochastic analysis of non-slotted aloha in wireless ad hoc networks. In INFOCOM, 2010 Proceedings IEEE, pages 1–9. IEEE, 2010.
  68. ^ a b c A. E. Gamal and Y. Kim. Lecture Notes on Network Information Theory. January 2010. web version: http://arxiv.org/abs/1001.3404.
  69. ^ a b F. Baccelli, A. E. Gamal, and D. Tse. Interference networks with point-to-point codes. Special issue of IEEE Tr. IT on Interference Networks, April 2011.
  70. ^ T. V. Nguyen and F. Baccelli. A probabilistic model of carrier sensing based cognitive radio. In Proc. IEEE Symposium Dynamic Spectrum Access Networks, DYSPAN'10, Singapore, Apr. 2010.
  71. ^ C. Yin, L. Gao, and S. Cui. Scaling laws for overlaid wireless networks: a cognitive radio network versus a primary network. IEEE/ACM Transactions on Networking (TON), 18(4):1317–1329, 2010.
  72. ^ O. Dousse, M. Franceschetti, and P. Thiran. On the throughput scaling of wireless relay networks. Information Theory, IEEE Transactions on, 52(6):2756–2761, 2006.
  73. ^ D. J. Daley and D. Vere-Jones. An introduction to the theory of point processes. Vol. {II}. Probability and its Applications (New York). Springer, New York, second edition, 2008.