Project topics and materials
Get Complete Project Material File(s) Now! »
Capacity of Wireless Networks
The assessment of the capacity of wireless networks is a challenging task and significant re-search efforts have been made to study this problem. The difficulty posed by this problem comes from the fact that it has to take into account the following three main aspects:
– propagation of electromagnetic waves through medium,
– geometry of wireless network, i.e., the positioning of nodes in the network and
– extraction of information from received signals.
In this chapter, we will discuss some of the important related works and find out how they address the above mentioned aspects of this problem.
Capacity of Single-hop Wireless Networks
In one of the first analyses, the article [Nelson & Kleinrock 1984] studied the capacity of wire-less network with slotted ALOHA and despite using a very simple geometric model for the reception of signals, the result is very similar to what can be obtained under a realistic SINR based interference model where a signal is received only if its SINR is above a desired thresh-old. Under a similar geometric model and assuming that all nodes are within range of each other, the article [Kleinrock & Tobagi 1975] evaluated CSMA scheme and compared it with slotted ALOHA in terms of throughput (bit-rate). The article [Blaszczyszyn et al. 2010] used simulations to analyze CSMA and compared it with ALOHA, both slotted and un-slotted. For simulations, the authors of this article assumed Poisson distributed transmitters with density λ. Each transmitter sends packets to its assigned receiver located at a fixed distance of a√λ, for some a > 0.
The articles [Weber et al. 2005, Weber et al. 2010] introduced the concept of transmission ca-pacity which is defined as the maximum number of successful transmissions per unit area at a specified outage probability, i.e., the probability that the SINR at the receiver is below a cer-tain threshold. The authors of these articles studied the transmission capacity of ALOHA and CDMA schemes under the assumption that simultaneous transmitters form a homogeneous Poisson point process and, as in the article [Blaszczyszyn et al. 2010], they also assumed that the receivers are located at fixed distance from their transmitters. The fact that the receivers are not a part of the network or node distribution model and are located at a fixed distance from their transmitters is a simplification. An accurate model of wireless network should consider that the transmitters, transmit to receivers which are randomly located within their neighborhood. Although, the article [Weber et al. 2005] also analyzed the case where receivers are located at a random distance but it was assumed that the transmitters employ transmit power control such that the signal power at their intended receivers is some fixed value.
Poisson point process can only accurately model an ALOHA based scheme where transmit-ters are independently and uniformly distributed in the network area. However, with MAC schemes based on exclusion rules, like node coloring or CSMA, modeling simultaneous trans-mitters as Poisson point process leads to an inaccurate representation of the distribution of signal level of interference. On the other hand, correlation between the location of simultane-ous transmitters makes it extremely difficult to develop a tractable analytical model and derive the closed-form expression for the distribution of interference and probability of successful re-ception. Some of the proposed approaches are as follows. In Chapter 18 of the book [Baccelli & Blaszczyszyn 2009], the authors used a Matérn point process for CSMA scheme whereas the ar-ticle [Busson & Chelius 2009] proposed to use Simple Sequential Inhibition (SSI) or an extension of SSI called SSIk point process. In articles [Hasan & Andrews 2007, Kaynia & Jindal 2008], si-multaneous interferers are modeled as Poisson point process and outage probability is obtained by excluding or suppressing some of the interferers in the guard zone around a receiver. The article [Ganti et al. 2011] analyzed transmission capacity in networks with general node distribu-tions under a restrictive hypothesis that density of interferers is very low and, asymptotically, approaches zero. The authors of this article derived bounds of high-SINR transmission capac-ity with ALOHA using Poisson point process and CSMA using Matérn point process. Other related works include the analysis of single-hop throughput and capacity with slotted ALOHA, in networks with random and deterministic node placement, and TDMA, in one-dimensional line-networks only, in the article [Haenggi 2009].
Capacity of Multi-hop Wireless Networks
Most of the works we have discussed so far, analyze the capacity of wireless network by taking into account only the simultaneous single-hop transmissions. However, when source and des-tination nodes are randomly distributed in the network area, packets are usually transported through multiple relays towards their respective destinations. Therefore, these analyses may not give an accurate assessment of the performance of wireless network using multi-hop communication.
Though computing the end-to-end capacity of wireless network is an extremely challenging task because of the possible impact of routing protocol on the hop length and spatial distribu-tion of simultaneous transmitters, there have been significant attempts to overcome the above mentioned limitations. In the seminal work of the article [Gupta & Kumar 2000], the authors used a spatial and temporal scheme for scheduling transmissions in the network and derived the scaling laws on the capacity when the number of nodes increases and approaches infinity. They showed that if nodes in the network transmit at constant rate, the effective radius of suc-cessful transmission scales as O(1/√n). Therefore, if nodes transmit to their nearest neighbors only, there can be O(n) simultaneous transmissions in the network with bit rate per source-destination pair of O(1) which is independent of n and the network capacity scales as O(n).
In case of multi-hop communication, Gupta & Kumar also introduced the concept of trans-port capacity which measures the sum of the end-to-end throughput of the network multiplied by the end-to-end distance and showed that if nodes are optimally located and traffic patterns are also optimally assigned, the network transport capacity scales as O(√n) or, in other words, bit-rate per source destination pair in multi-hop networks is upper bounded by O(1/√n). However, if nodes are randomly distributed, they showed that the throughput obtainable by each node for a randomly chosen destination drops to O(1/ n log n) where the log n factor comes from the fact that the network must be connected or, in other words, at least one route or path must exist between all pairs of nodes with high probability (w.h.p.) which approaches one as n approaches infinity. We can also obtain this result as follows. Let us assume that pn is the transmission rate of each node, i.e., the proportion of time each node is active and transmitting. Therefore, the effective radius of transmission is given by rn = κ , (2.1) n pn when n increases and approaches infinity, for some constant κ > 0 which depends on the pro-tocol and physical layer parameters, interference model, etc. Therefore, the average number of relays a packet has to traverse to reach its destination will be hn = O(1/rn ). Consequently, n pn must be divided by hn to get the useful network throughput capacity n pn √ = O( pn n) .
From the article [Gupta & Kumar 1998], we know that in order to ensure connectivity in a network, so that every source is able to communicate with its randomly chosen destination, pn must satisfy the limit pn ≤ O 1 , log n
and this leads to Gupta & Kumar’s throughput capacity of O( n/ log n).
The articles [Xue & Kumar 2006, Franceschetti et al. 2007] have shown that, even in case of randomly distributed nodes, the throughput capacity in wireless network can be increased to an upper bound of O(√n) and the log n factor can be overcome by constructing a complex system of highways of nodes to transport data and using different transmission ranges for dif-ferent transmissions. The authors of these articles used techniques from percolation theory to show that a system of horizontal and vertical highways can be formed in a network of ran-domly distributed nodes. Each highway is accessed by an O(√n) number of nodes and these highways can then use time sharing scheme to carry data over short hops (of length bounded by a constant) at constant bit-rate which gives the O(1/√n) rate of communication per node. Other nodes use single-hops of longer length of O(log √n) when data is to be pushed on these highways or delivered from these highways to destination nodes. In other related works, the article [Baccelli et al. 2006] gave a detailed analysis on the optimal probability of transmission for ALOHA which optimizes the spatial density of progress, i.e., the product of simultaneously successful transmissions per unit of space by the average range of each transmission. Instead of considering the average range of transmission, the authors of the article [Weber et al. 2008] proposed a variant where each transmitter selects its longest feasible edge and then identifies a packet in its buffer whose next hop is the associated receiver. Similarly, the article [Andrews et al. 2010] evaluated the random transport capacity of wireless network without taking into account any particular routing protocol and under the strong assumptions that simultaneous interferers form a Poisson point process and relays are equally spaced on a straight line be-tween a source and its destination.
An important aspect of the multi-hop communication is the transmission range of a trans-mitter as it has an impact on the hop-length as well as the probability of successful transmis-sion: both factors have critical impact on the capacity of multi-hop wireless network. There have been many studies on the transmission range under various constraints. For example, the article [Deng et al. 2007] studied the transmission range that achieves the most economi-cal energy usage in an ad hoc network of uniformly distributed nodes. The works [Santi & Blough 2003, Santi 2005] analyzed the critical transmission range required for connectivity in stationary and mobile wireless ad hoc networks. The article [Takagi & Kleinrock 1984] de-termined the optimal transmission range of slotted ALOHA and CSMA schemes which max-imizes the expected one-hop progress of a packet while considering the tradeoff between the probability of successful transmission and the progress of the packet. The authors assumed that all nodes use same transmit power and the range of transmission is controlled by tuning the density of simultaneous transmitters via parameters like probability of transmission (in case of ALOHA) and carrier sense threshold (in case of CSMA). The article [Zorzi & Pupolin 1995] determined the normalized optimum transmission range under the assumption that simulta-neous interferers form a Poisson point process. In an important analysis in the article [Gomez & Campbell 2004], the authors studied the impact of variable transmission range, by controlling the transmit power, on network connectivity, capacity and energy efficiency. They showed that log n routing in networks where transmitters have same transmission range can only achieve half of the traffic carrying capacity of networks where transmitters have variable transmission range.
Capacity of Wireless Networks with Multiple-Input-Multiple-Output Technology
The results we have discussed so far evaluate the capacity of wireless network by assuming that nodes are equipped with only one antenna and, at a time, a receiver can only receive data from one transmitter and signal from all other transmitters is considered as interference.
The communication performance in wireless network can be significantly improved by us-ing multiple-input-multiple-output (MIMO) technology. The earliest ideas in this field were in-troduced in articles [Kaye & George 1970, Brandenburg & Wyner 1974] and further developed in works of [Paulraj & Kailath 1993, Foschini 1996, Telatar 1999]. Following these pioneering works, there have been many articles which improved on these ideas progressively and eval-uated the performance of MIMO systems under various scenarios. Some of these analyses can also be found in articles like [Zheng & Tse 2003, Choi & Murch 2004, Chiani et al. 2010].
There can be two flavors of MIMO: classical MIMO and cooperative MIMO. In classical MIMO, nodes are equipped with multiple antennas and each transmitter uses spatial multi-plexing to transmit multiple streams of data in parallel. This technology has been in use in standards like fourth generation (4G) Long Term Evolution (LTE) which are presented in detail in specifications [3GPP 2005, 3GPP2 2007], Worldwide Interoperability for Microwave Access (WiMAX) based on IEEE 802.16e in the specification [802.16e 2009] and IEEE 802.11 wireless LANs based on the specification [802.11n 2009]. The capacity of wireless network consisting of nodes using classical MIMO has been studied in articles like [Bölcskei et al. 2006, Chen & Gans 2006, Jiang et al. 2011], where the latest work extended the result of Gupta & Kumar and showed that the capacity scales as O m , where each node is equipped with m antennas.
In the framework of pure information theoretic capacity, i.e. the Shannon capacity, informa-tion can be extracted from all parallel flows of data from simultaneous transmitters. The arti-cle [Jacquet 2009] evaluated the capacity in terms of information rate received by a randomly located node in a wireless network consisting of nodes distributed according to two dimen-sional (2D) Poisson point process. In this article, the author assumed that the receivers are equipped with MIMO-like technology and, from the received signal, extract information of all parallel flows, generated (transmitted) by simultaneous transmitters in the network, at a rate depending on the SINR of each information flow. Under this assumption, the author showed that the received information rate depends only on the attenuation coefficient α > 2 and is equal to α2 (log 2)−1 bits per Hertz. Starting with the works of [Gupta & Kumar 2003, Xie & Kumar 2004], there has also been an interest in the information theoretic capacity scaling laws of wireless network and a steady stream of articles have been addressing this topic. Some of these works can be found in articles like [Jovicic et al. 2004, Leveque & Telatar 2005, Ah-mad et al. 2006]. In networks employing cooperative MIMO, nodes cooperate, by allowing to transmit (or receive) signal to (or from) multiple nodes, to deliver data to their destinations. Examples of various schemes using cooperative MIMO can be found in articles like [Aeron & Saligrama 2007, Ozgur et al. 2007, Niesen et al. 2009]. Using pathloss model for propagation of electromagnetic waves through medium and statistical fading models, all these articles present various bounds or scaling laws on information theoretic capacity of wireless network: some of these results show bit-rate per source-destination pair which decays to zero as the number of nodes in the network approaches infinity, others show slower decay and some are even able to show an almost constant bit-rate using schemes based on cooperative MIMO.
Capacity-Delay Tradeoff in Mobile Multi-hop Wireless Net-works
In case of networks with immobile nodes, the packets are relayed immediately like hot potatoes and the packet delivery delay can be assumed negligible. So the question arises, what happens if nodes are allowed to move and how the mobility of nodes in the network has an impact on the capacity and delay? In the article [Grossglauser & Tse 2002], the authors showed that if nodes are mobile and follow independent and identically distributed (i.i.d.) ergodic motions in a square area, the throughput capacity can rise to O(n) by using the mobility of nodes. Under their proposed postman routing scheme, a source node relays its packet to a random mobile relay node which transmits this packet to its destination node only when they come close together, i.e., at a distance of O(1/√n). Therefore, the time it takes to deliver a packet to its destination would be O(√n/v) where v is the average speed of nodes. In contrast, in the analysis of Gupta & Kumar, where nodes are considered to be immobile, the packet delivery delay tends to be negligible because the packets are relayed toward their respective final destinations like hot potatoes but the network throughput capacity is also lower by a factor of n log n. It is also interesting to note that the article [Diggavi et al. 2005] showed that a constant throughput capacity per source-destination pair is also feasible even with a more restricted mobility model, i.e., when nodes are allowed to move along line segments only.
The main difference between the proposed models in the works of Gupta & Kumar and Grossglauser & Tse is that, in the former case, nodes are immobile or static and packets are transmitted between nodes like hot potatoes while, in the latter case, nodes are mobile and relays are allowed to carry buffered packets while they move. Earlier, in this chapter, we discussed the result of Gupta & Kumar and also discussed their result on throughput capacity in multi-hop networks under the condition that the network must remain connected. In contrast, in the context of Grossglauser & Tse, the network does not need to be connected as the packets are mostly carried in the buffer of a mobile relay. Therefore, there is no limit on pn other than the requirement that it must be smaller than some ε < 1 that depends on the protocol and some other physical parameters. Thus, in this case, rn is O(1/√n). In the first step of Grossglauser & Tse’s postman routing scheme, the source transmits its packet to the closest mobile relay or keeps it until it finds one. In the second step, this mobile relay delivers the packet to its des-tination when it comes within range of the destination node. Such a packet delivery requires a transmission phase which also includes retries and acknowledgements so that the packet delivery can be eventually guaranteed. The proposed model of Grossglauser & Tse should require a positing system like global positioning system (GPS) and the knowledge of the effec-tive transmission range rn . The estimate of rn could be achieved via a periodic beaconing from each node. Each beacon also contains the position coordinates of its transmitter and any other node, on receiving this beacon, knows the typical distance for a successful reception. How-ever, a relay cannot rely on beaconing in order to detect when it is in the reception range of the destination. The reason is that a node stays in the reception range of another node for a short time period of order rn /v = 1/√n and this cannot be detected via a periodic beaconing with bounded frequency since pn = O(1). In fact, the frequency of periodic beaconing should be of O(√n). We may also assume that the destination node is fixed and its cartesian coordinates are known by the mobile relays. Otherwise, if the destination node is mobile, there would be a requirement for this node to track its own coordinates and disseminate this information in the network. Some of these ideas are also proposed in articles like [Stojmenovic 1999,Li et al. 2000].
Table of contents :
1 Introduction
1.1 Types of Wireless Networks
1.2 The Problem
1.2.1 Single-hopWireless Networks
1.2.2 Multi-hop Wireless Networks
1.2.3 Mobile Multi-hop Wireless Networks
1.3 Organization of this Thesis and Our Contributions
1.3.1 Part 1: Single-hopWireless Networks
1.3.2 Part 2: Multi-hop Wireless Networks
1.3.3 Part 3: Mobile Multi-hop Wireless Networks
2 Capacity ofWireless Networks
2.1 Capacity of Single-hopWireless Networks
2.2 Capacity of Multi-hopWireless Networks
2.3 Capacity of Wireless Networks with Multiple-Input-Multiple-Output Technology
2.4 Capacity-Delay Tradeoff in Mobile Multi-hop Wireless Networks
3 Medium Access Control Schemes in Wireless Networks
3.1 Models and Assumptions
3.1.1 Timing Model
3.1.2 Network Model
3.1.3 Propagation Model
3.1.4 Transmission Model
3.1.5 Node Model
3.2 Slotted ALOHA Scheme
3.2.1 High-Level Specification of the Scheme
3.2.2 Model for Analytical Evaluation
3.3 MAC Schemes Based on Exclusion Rules
3.3.1 High-Level Specification of the Schemes
3.3.2 Model for Analytical Evaluation
3.4 Grid Pattern Based Schemes
3.4.1 High-Level Specification of the Schemes
3.4.2 Model for Analytical Evaluation
I Single-hop Wireless Networks
4 Local Capacity inWireless Networks
4.1 Model and Assumptions
4.2 Slotted ALOHA Scheme
4.2.1 Reception Areas
4.2.2 Local Capacity
4.3 MAC Schemes Based on Exclusion Rules
4.3.1 Reception Areas
4.3.2 Local Capacity
4.4 Grid Pattern Based Schemes
4.4.1 Optimality of Grid Pattern Based Schemes
4.4.2 Reception Areas
4.4.3 Local Capacity
4.5 Evaluation and Results
4.5.1 Slotted ALOHA Scheme
4.5.2 MAC Schemes Based on Exclusion Rules
4.5.3 Grid Pattern Based Schemes
4.5.4 Summary of Results
4.6 Impact of Fading on Local Capacity
4.7 Conclusions
5 Local Capacity and Coverage in Cellular Networks
5.1 The Context
5.2 Model and Assumptions
5.3 Scheme to Incorporate K Additional Base Stations
5.3.1 Points of Maximum Capacity
5.3.2 Points of Minimum Interference
5.3.3 Delaunay Triangulation
5.3.4 Gradient Descent Method
5.3.5 Heuristics
5.4 Evaluation and Results
5.4.1 Summary of Results
5.5 Conclusions
II Multi-hop Wireless Networks
6 Transmission Range inWireless Networks
6.1 Model and Assumptions
6.2 Normalized Optimum Transmission Range
6.3 Slotted ALOHA Scheme
6.3.1 Evaluation of Transmission Range
6.4 Grid Pattern Based Schemes
6.4.1 Evaluation of Transmission Range
6.5 Evaluation and Results
6.5.1 Slotted ALOHA Scheme
6.5.2 Grid Pattern Based Schemes
6.5.3 Summary of Results
6.6 Asymptotic Analysis of Grid Pattern Based Schemes
6.6.1 With Respect to SIR Threshold
6.6.2 With Respect to Attenuation Coefficient
6.7 Conclusions
7 Throughput Capacity in Wireless Network
7.1 Model and Assumptions
7.2 Optimization Parameters of MAC Schemes
7.2.1 Slotted ALOHA Scheme
7.2.2 MAC Schemes Based on Exclusion Rules
7.2.3 Grid Pattern Based Schemes
7.3 Evaluation and Results
7.3.1 Optimization of the Throughput Capacity
7.3.2 Summary of Results
7.4 Conclusions
III Mobile Multi-hop Wireless Networks
8 Capacity-Delay Tradeoff in Wireless Networks
8.1 Model and Assumptions
8.2 The Constrained Relative Bearing Georouting Scheme
8.2.1 Parameters
8.2.2 High-Level Specification With Radio Range Awareness
8.2.3 High-Level Specification Without Radio Range Awareness
8.3 Performance Analysis
8.3.1 Methodology
8.3.2 Delivery Delay
8.3.3 Number of Relay Changes
8.3.4 Number of Relay ChangesWith High Probability of Success
8.4 Evaluation and Results
8.4.1 Under UDG Model
8.4.2 Under SIR Model
8.5 Extensions and General Mobility Models
8.6 Conclusions
9 Conclusions
9.1 Summary of Contributions
9.2 Perspectives and Future Directions
A Appendix
A.1 Locating the Starting Point z on the Closed Curve Bounding the Reception Area
List of Notations
Bibliography
