Optimal throughput-delay scaling in wireless networks - part I: the fluid model

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is /spl Theta/(1//spl radic/(nlogn)). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n)=/spl Theta/(nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of /spl Theta/(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be /spl Theta/(nlogn). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of /spl Oscr/(1//spl radic/(nlogn)), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n)=/spl Theta/(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be /spl Theta/(nlogn), which is the delay for throughput of /spl Theta/(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.     

Capacity of interference-limited ad hoc networks with infrastructure support

In this letter, we consider the capacity of ad hoc networks with infrastructure support. Although Grossglauser-Tse mobile network model enables /spl Theta/(1) per-node throughput scaling, the mobility assumption may be too unrealistic to be accepted in some practical situations. One of the key observations we acquired is that the infrastructure support plays the same role played by the mobility in the Grossglauser-Tse model. We show that nodes can utilize the randomly located infrastructure support instead of mobility when nodes are nearly static. In this case, we show that the per-node throughput of /spl Theta/(1) is still achievable when the number of access points grows linearly with respect to the number of nodes.     

Dynamic power allocation and routing for time-varying wireless networks

We consider dynamic routing and power allocation for a wireless network with time-varying channels. The network consists of power constrained nodes that transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices (/spl lambda//sub ij/) that the system can stably support-where /spl lambda//sub ij/ represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed that stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad hoc wireless network, where channel variations are due to user mobility. Centralized and decentralized implementations are compared, and the stability region of the decentralized algorithm is shown to contain that of the mobile relay strategy developed by Grossglauser and Tse (2002).     

Hierarchical Cooperation in Ad Hoc Networks: Optimal Clustering and Achievable Throughput

For a wireless network with n nodes distributed in an area A, and with n source-destination pairs communicating with each other at some common rate, the hierarchical cooperation scheme proposed in (Ozgur, Leveque, and Tse, 2007) is analyzed and optimized by choosing the number of hierarchical stages and the corresponding cluster sizes that maximize the total throughput. It turns out that increasing the number of stages does not necessarily improve the throughput, and the closed-form solutions for the optimization problem can be explicitly obtained. Based on the expression of the maximum achievable throughput, it is found that the hierarchical scheme achieves a scaling with the exponent depending on n . In addition, to apply the hierarchical cooperation scheme to random networks, a clustering algorithm is developed, which divides the whole network into quadrilateral clusters, each with exactly the number of nodes required.     

Delay and Capacity Trade-Offs in Mobile Ad Hoc Networks: A Global Perspective

Since the original work of Grossglauser and Tse, which showed that mobility can increase the capacity of an ad hoc network, there has been a lot of interest in characterizing the delay-capacity relationship in ad hoc networks. Various mobility models have been studied in the literature, and the delay-capacity relationships under those models have been characterized. The results indicate that there are trade-offs between the delay and capacity, and that the nature of these trade-offs is strongly influenced by the choice of the mobility model. Some questions that arise are: (i) How representative are these mobility models studied in the literature? (ii) Can the delay-capacity relationship be significantly different under some other "reasonable" mobility model? (iii) What sort of delay-capacity trade-off are we likely to see in a real world scenario? In this paper, we take the first step toward answering some of these questions. In particular, we analyze, among others, the mobility models studied in recent related works, under a unified framework. We relate the nature of delay-capacity trade-off to the nature of node motion, thereby providing a better understanding of the delay-capacity relationship in ad hoc networks in comparison to earlier works.     

Wireless Ad Hoc Networks: Strategies and Scaling Laws for the Fixed SNR Regime

This paper deals with throughput scaling laws for random ad hoc wireless networks in a rich scattering environment. We develop schemes to optimize the ratio lambda(n) of achievable network sum capacity to the sum of the point-to-point capacities of source-destinations (S-D) pairs operating in isolation. Our focus in this paper is on fixed signal-to-noise ratio (SNR) networks, i.e., networks where the worst case SNR over the S-D pairs is fixed independent of n. For such fixed SNR networks, which include fixed area networks as a special case, we show that collaborative strategies yield a scaling law of lambda(n)=Omega(1/n^1/3) in contrast to multihop strategies which yield a scaling law of lambda(n)=Theta(1/radicn). While networks where worst case SNR goes to zero do not preclude the possibility of collaboration, multihop strategies achieve optimal throughput. The plausible reason is that the gains due to collaboration cannot offset the effect of vanishing receive SNR. This suggests that for fixed SNR networks, a network designer should look for network protocols that exploit collaboration     

On the improvement of scaling laws for large-scale MANETs with network coding

This paper investigates the problem of how much benefit network coding can contribute to the network performance in terms of throughput, delay, and storage requirements for mobile ad hoc networks (MANETs), compared to when only replication, storage and forwarding are allowed in relay nodes. We characterize the throughput-delay-storage tradeoffs under different node mobility patterns, i.e., i.i.d. and random walk mobility, with and without network coding. Our results show that when random linear coding instead of replication is used in MANETs, an order improvement on the scaling laws of MANETs can be achieved. Note that previous work showed that network coding could only provide constant improvement on the throughput of static wireless networks. Our work thus differentiates MANETs from static wireless networks by the role network coding plays.     

Queuing network models for delay analysis of multihop wireless ad hoc networks

In this paper we analyze the average end-to-end delay and maximum achievable per-node throughput in random access multihop wireless ad hoc networks with stationary nodes. We present an analytical model that takes into account the number of nodes, the random packet arrival process, the extent of locality of traffic, and the back off and collision avoidance mechanisms of random access MAC. We model random access multihop wireless networks as open G/G/1 queuing networks and use the diffusion approximation in order to evaluate closed form expressions for the average end-to-end delay. The mean service time of nodes is evaluated and used to obtain the maximum achievable per-node throughput. The analytical results obtained here from the queuing network analysis are discussed with regard to similarities and differences from the well established information-theoretic results on throughput and delay scaling laws in ad hoc networks. We also investigate the extent of deviation of delay and throughput in a real world network from the analytical results presented in this paper. We conduct extensive simulations in order to verify the analytical results and also compare them against NS-2 simulations.     

Performance analysis of slotted ALOHA and network coding for single-relay multi-user wireless networks

Deployment of wireless relay nodes can enhance system capacity, extend wireless service coverage, and reduce energy consumption in wireless networks. Network coding enables us to mix two or more packets into a single coded packet at relay nodes and improve performances in wireless relay networks. In this paper, we succeed in developing analytical models of the throughput and delay on slotted ALOHA (S-ALOHA) and S-ALOHA with network coding (S-ALOHA/NC) for single-relay multi-user wireless networks with bidirectional data flows. The analytical models involve effects of queue saturation and unsaturation at the relay node. The throughput and delay for each user node can be extracted from the total throughput and delay by using the analytical models. One can formulate various optimization problems on traffic control in order to maximize the throughput, minimize the delay, or achieve fairness of the throughput or the delay. In particular, we clarify that the total throughput is enhanced in the S-ALOHA/NC protocol on condition that the transmission probability at the relay node is set at the value on the boundary between queue saturation and unsaturation. Our analysis provides achievable regions in throughput on two directional data flows at the relay node for both the S-ALOHA and S-ALOHA/NC protocols. As a result, we show that the achievable region in throughput can be enhanced by using network coding and traffic control.     

Optimal Delay–Throughput Tradeoffs in Mobile Ad Hoc Networks

In this paper, we investigate the delay–throughput tradeoffs in mobile ad-hoc networks. We consider four node mobility models: 1) two-dimensional independent and identically distributed (i.i.d.) mobility, 2) two-dimensional hybrid random walk, 3) one-dimensional i.i.d. mobility, and 4) one-dimensional hybrid random walk. Two mobility time scales are included in this paper. i) Fast mobility, where node mobility is at the same time scale as data transmissions. ii) Slow mobility, where node mobility is assumed to occur at a much slower time scale than data transmissions. Given a delay constraint $D$ , we first characterize the maximum throughput per source–destination (S-D) pair for each of the four mobility models with fast or slow mobiles. We then develop joint coding–scheduling algorithms to achieve the optimal delay–throughput tradeoffs.      

Capacity Scaling in Ad Hoc Networks With Heterogeneous Mobile Nodes: The Super-Critical Regime

We analyze the capacity scaling laws of mobile ad hoc networks comprising heterogeneous nodes and spatial inhomogeneities. Most of previous work relies on the assumption that nodes are identical and uniformly visit the entire network space. Experimental data, however, show that the mobility pattern of individual nodes is usually restricted over the area, while the overall node density is often largely inhomogeneous due to the presence of node concentration points. In this paper we introduce a general class of mobile networks which incorporates both restricted mobility and inhomogeneous node density, and describe a methodology to compute the asymptotic throughput achievable in these networks by the store-carry-forward communication paradigm. We show how the analysis can be mapped, under mild assumptions, into a Maximum Concurrent Flow (MCF) problem over an associated Generalized Random Geometric Graph (GRGG). Moreover, we propose an asymptotically optimal scheduling and routing scheme that achieves the maximum network capacity.     

Even One-Dimensional Mobility Increases the Capacity of Wireless Networks

We study the capacity of ad hoc wireless networks with mobile nodes. The mobility model examined is one where the nodes are restricted to move along one-dimensional paths. We examine the scaling laws for the per-user throughput achievable over long time-scales, making this suitable for applications with loose delay constraints. We show that under this regime of restricted mobility, we attain a constant throughput (i.e.,$Theta(1)$) per user, which is significantly higher than the throughput of fixed networks, which decays as$O(1over sqrtn)$with the number of nodes$n$, as shown by Gupta and Kumar.     

On capacity of random wireless networks with physical-layer network coding

Throughput capacity of a random wireless network has been studied extensively in the literature. Most existing studies were based on the assumption that each transmission involves only one transmitter in order to avoid interference. However, recent studies on physical-layer network coding (PLNC) have shown that such an assumption can be relaxed to improve throughput performance of a wireless network. In PLNC, signals from different senders can be transmitted to the same receiver in the same channel simultaneously. In this paper, we investigate the impact of PLNC on throughput capacity of a random wireless network. Our study reveals that, although PLNC scheme does not change the scaling law, it can improve throughput capacity by a fixed factor. Specifically, for a one-dimensional network, we observe that PLNC can eliminate the effect of interference in some scenarios. A tighter capacity bound is derived for a two-dimensional network. In addition, we also show achievable lower bounds for random wireless networks with network coding and PLNC.     

Multicast capacity and delay trade‐offs in ad hoc networks with random iid mobility model

In this paper, multicast capacity and delay trade‐offs of mobile ad hoc networks are considered under random independently and identically distributed (iid) mobility model. Compared with unicast, multicast can reduce the overall network load by a factor with high probability (whp) in static random ad hoc networks, where k is the number of destination nodes in a multicast session. So we firstly discuss whether the law still holds in mobile random ad hoc networks, and in this case what delay should be tolerated. Through the relation between average retransmissions and multicast capacity, we prove that order of multicast capacity is not achievable whp, and delay for multicast capacity is , where is the number of ad hoc nodes in the whole networks, and and c is a positive constant. Then achievable throughput whp is considered. The nearest neighbor transmission strategy is introduced by Grossglauser and Tse to achieve throughput which is so far the highest achievable unicast capacity. So the multicast capacity of mobile ad hoc networks under this strategy is studied. The analysis shows that under any multicast routing scheme based on the nearest neighbor transmission strategy, the upper bound on multicast capacity is whp. Then we propose a multicast routing and scheduling scheme by which mobile ad hoc networks can achieve throughput whp, and must tolerate total network delay. Copyright © 2009 John Wiley & Sons, Ltd.     

MrFbP: Markov random field-driven spatial entropy-based routing protocol in opportunistic networks

Recently, research towards technologies associated with the 5G communication is in full operation. Amongst these enabling technologies, device-to-device(D2D) communication is one of the critical factors for scaling up the network efficiency in 5G communication. Intermittent connections due to higher mobility lead to frequent path breaks, and hence a mobility-based opportunistic routing is suitable enough to control the forwarding process. Opportunistic networks (OppNet) use the pairwise opportunistic contacts and higher mobility to rely on the store-carry and forward mechanism for routing purpose. In this work, a novel mobility-induced context-based routing process has been designed to support D2D communication. The designed Markov random field-induced protocol (MrFbP) is based on spatial entropy for capturing the coverage span of the forwarding node in the network. The work relies on the monitored historic mobility of a node and is then used to capture the utility metric for taking forwarding decision. MrFbP is compared against the established Direct Delivery (DD), Epidemic (EP), Spray & Wait (SW), and PropHet (PR) on parameters like throughput, delay, hops, overheads, and energy consumption. Simulation has been carried out using ONE simulator to validate an improvement in the design of a designed protocol against the baseline protocols.     

Throughput analysis in mobile ad hoc networks with directional antennas

A major obstacle stunting the application of mobile ad hoc networks (MANETs) is the lack of a general throughput analysis theory for such networks. The available works in this area mainly focus on asymptotic throughput study (order sense) in MANETs with omnidirectional antennas or directional antennas. Although the order sense results can help us to understand the general scaling behaviors, it tells us little about the exact achievable throughput. This paper studies the achievable throughput of a MANET where each node is equipped with a directional antenna of beamwidth θ for transmission. A generalized two hop relay scheme with packet redundancy f is adopted for packet routing. Based on the Markov chain and automatic feedback theory, we explore a general theoretical framework that enables the achievable throughput analysis to be conducted for a directional antenna-based MANET. Based on the results of the achievable per node throughput, we further explore the throughput optimization problem for a fixed beamwidth θ and determine the corresponding optimal setting of f to achieve the optimal throughput. Numerical studies are also conducted to demonstrate the efficiency of these models.It shows that the maximum achievable throughput obtained from our theoretical framework matches nicely (with at most 7% difference) with that obtained from simulation under a realistic model.     

High-performance optical local and metropolitan area networks:enhancement of FDDI and IEEE 802.6 DQDB

The fiber distributed data interface (FDDI) and the IEEE 802.6 distributed queueing dual bus (DQDB) are emerging standards for high-speed (45-150-Mb/s) local and metropolitan area networks. The authors describe several ways to build on these emerging standards to significantly increase the achievable throughput and lower th e end-to-end delay. Without increasing the number of transceivers or their rate, substantial throughput increases are obtained by a highly concurrent logical interconnection pattern of user modes, and the end-to-end delay is decreased by the use of more efficient media-access techniques. The most promising architecture is a multiconnected ring having only two transmitters and two receivers per node, where each node needs to handle or process only a small fraction of the network traffic. In one example, the authors describe a 24-node, distributed, packet-switched network, with only two 100-Mb/s transmitters and two 100-Mb/s receivers per node; it has a maximum throughput of 1.5 Gb/s-15 times the 100/Mb/s throughput of FDDI. Such a system has the potential to be a follow-on standard to FDDI (or IEEE 802.6) or to provide a high-performance LAN/MAN that can interwork with standard systems     

Opportunistic Relaying in Wireless Networks

Relay networks having n source-to-destination pairs and m half-duplex relays, all operating in the same frequency band and in the presence of block fading, are analyzed. This setup has attracted significant attention, and several relaying protocols have been reported in the literature. However, most of the proposed solutions require either centrally coordinated scheduling or detailed channel state information (CSI) at the transmitter side. Here, an opportunistic relaying scheme is proposed that alleviates these limitations, without sacrificing the system throughput scaling in the regime of large n. The scheme entails a two-hop communication protocol, in which sources communicate with destinations only through half-duplex relays. All nodes operate in a completely distributed fashion, with no cooperation. The key idea is to schedule at each hop only a subset of nodes that can benefit from multiuser diversity. To select the source and destination nodes for each hop, CSI is required at receivers (relays for the first hop, and destination nodes for the second hop), and an index-valued CSI feedback at the transmitters. For the case when n is large and m is fixed, it is shown that the proposed scheme achieves a system throughput of m/2 bits/s/Hz. In contrast, the information-theoretic upper bound of (m/2) log log n bits/s/Hz is achievable only with more demanding CSI assumptions and cooperation between the relays. Furthermore, it is shown that, under the condition that the product of block duration and system bandwidth scales faster than log n log log n, the achievable throughput of the proposed scheme scales as Theta (log n). Notably, this is proven to be the optimal throughput scaling even if centralized scheduling is allowed, thus proving the optimality of the proposed scheme in the scaling law sense. Simulation results indicate a rather fast convergence to the asymptotic limits with the system's size, demonstrating the practical importance of the scaling results.     

Stochastic Properties of Mobility Models in Mobile Ad Hoc Networks

The stochastic model assumed to govern the mobility of nodes in a mobile ad hoc network has been shown to significantly affect the network's coverage, maximum throughput, and achievable throughput-delay trade-offs. In this paper, we compare several mobility models, including the random walk, random waypoint, and Manhattan models on the basis of the number of states visited in a fixed time, the time to visit every state in a region, and the effect of the number of wandering nodes on the time to first enter a set of states. These metrics for a mobility model are useful for assessing the achievable event detection rates in surveillance applications where wireless-sensor-equipped vehicles are used to detect events of interest in a city. We also consider mobility models based on Correlated Random Walks, which can account for time dependency, geographical restrictions, and nonzero drift. We demonstrate that these models are analytically tractable by using a matrix-analytic approach to derive new, closed-form results in both the time and transform-domains for the probability that a node is at any location at any time for both semi-infinite and finite 1D lattices. We also derive first entrance time distributions for these walks. We find that a correlated random walk 1) covers more ground in a given amount of time and takes a smaller amount of time to cover an area completely than a random walk with the same average transition rate, 2) has a smaller first entrance time to small sets of states than the random waypoint and random walk models, and 3) leads to a uniform distribution of nodes (except at the boundaries) in steady state.     

Overcoming untuned radios in wireless networks with network coding

The drive toward the implementation and massive deployment of wireless sensor networks calls for ultralow-cost and low-power nodes. While the digital subsystems of the nodes are still following Moore's Law, there is no such trend regarding the performance of analog components. This work proposes a fully integrated architecture of both digital and analog components (including local oscillator) that offers significant reduction in cost, size, and overall power consumption of the node. Even though such a radical architecture cannot offer the reliable tuning of standard designs, it is shown that by using random network coding, a dense network of such nodes can achieve throughput linear in the number of channels available for communication. Moreover, the ratio of the achievable throughput of the untuned network to the throughput of a tuned network with perfect coordination is shown to be close to 1/e. This work uses network coding to leverage the fact that throughput equal to the max-flow in a graph is achievable even if the topology is not know a priori. However, the challenge here is finding the max-flow of the random graph corresponding to the network.