Hierarchical Cooperation Achieves Optimal Capacity Scaling in Ad Hoc Networks

n source and destination pairs randomly located in an area want to communicate with each other. Signals transmitted from one user to another at distance r apart are subject to a power loss of r^-alpha as well as a random phase. We identify the scaling laws of the information-theoretic capacity of the network when nodes can relay information for each other. In the case of dense networks, where the area is fixed and the density of nodes increasing, we show that the total capacity of the network scales linearly with n. This improves on the best known achievability result of n^2/3 of Aeron and Saligrama. In the case of extended networks, where the density of nodes is fixed and the area increasing linearly with n, we show that this capacity scales as n^2-alpha/2 for 2lesalpha<3 and radicn for a alphages3. The best known earlier result of Xie and Kumar identified the scaling law for alpha > 4. Thus, much better scaling than multihop can be achieved in dense networks, as well as in extended networks with low attenuation. The performance gain is achieved by intelligent node cooperation and distributed multiple-input multiple-output (MIMO) communication. The key ingredient is a hierarchical and digital architecture for nodal exchange of information for realizing the cooperation.     

End-to-end delay in wireless random networks

The focus of this letter is to derive a scaling law for the ene-to-end delay of wireless random networks under node mobility, where n nodes randomly move with the speed of v. To that end, we apply the cover time analysis and relate it to the delay scaling law. As a result, we derive that the mean delay per S-D pair as θ(n) or θ(√n÷v), and the worst case delay is θ(n log n) or θ(√log n÷v), corresponding to one slot time length that is either constant or 1÷v√n .     

Optimum transmission ranges in a direct-sequence spread-spectrummultihop packet radio network

The authors obtain the optimum transmission ranges to maximize throughput for a direct-sequence spread-spectrum multihop packet radio network. In the analysis, they model the network self-interference as a random variable which is equal to the sum of the interference power of all other terminals plus background noise. The model is applicable to other spread-spectrum schemes where the interference of one user appears as a noise source with constant power spectral density to the other users. The network terminals are modeled as a random Poisson field of interference power emitters. The statistics of the interference power at a receiving terminal are obtained and shown to be the stable distributions of a parameter that is dependent on the propagation power loss law. The optimum transmission range in such a network is of the form CK^α where C is a constant, K is a function of the processing gain, the background noise power spectral density, and the degree of error-correction coding used, and α is related to the power loss law. The results obtained can be used in heuristics to determine optimum routing strategies in multihop networks     

Performance Optimization of Interference-Limited Multihop Networks

The performance of a multihop wireless network is typically affected by the interference caused by transmissions in the same network. In a statistical fading environment, the interference effects become harder to predict. Information sources in a multihop wireless network can improve throughput and delay performance of data streams by implementing interference-aware packet injection mechanisms. Forcing packets to wait at the head of queues and coordinating packet injections among different sources enable effective control of copacket interference. In this paper, throughput and delay performance in interference-limited multihop networks is analyzed. Using nonlinear probabilistic hopping models, waiting times which jointly optimize throughput and delay performances are derived. Optimal coordinated injection strategies are also investigated as functions of the number of information sources and their separations. The resulting analysis demonstrates the interaction of performance constraints and achievable capacity in a wireless multihop network.      

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.     

Modeling throughput gain of network coding in multi-channel multi-radio wireless ad hoc networks

In this paper, we model the network throughput gains of two types of wireless network coding (NC) schemes, including the conventional NC and the analog NC schemes, over the traditional non-NC transmission scheduling schemes in multihop, multi-channel, and multi-radio wireless ad hoc networks. In particular, we first show that the network throughput gains of the conventional NC and analog NC are (2n)/(2n-1) and n/(n-1), respectively, for the n-way relay networks where n ges 2. Second, we propose an analytical framework for deriving the network throughput gain of the wireless NC schemes over general wireless network topologies. By solving the problem of maximizing the network throughput subject to the fairness requirements under our proposed framework, we quantitatively analyze the network throughput gains of these two types of wireless NC schemes for a variety of wireless ad hoc network topologies with different routing strategies. Finally, we develop a heuristic joint link scheduling, channel assignment, and routing algorithm that aims at approaching the optimal solution to the optimization problem under our proposed framework.     

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.     

Bounds on the throughput gain of network coding in unicast and multicast wireless networks

Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales with an increasing number of nodes n as lambda(n) = ominus(1/radic(n log n)), thus indicating that performance does not scale well. However, Gupta and Kumar did not consider network coding and wireless broadcasting, which recent works suggest have the potential to significantly improve throughput. Here, we establish bounds on the improvement provided by such techniques. For random networks of any dimension under either the protocol or physical model that were introduced by Gupta and Kumar, we show that network coding and broadcasting lead to at most a constant factor improvement in per node throughput. For the protocol model, we provide bounds on this factor. We also establish bounds on the throughput benefit of network coding and broadcasting for multiple source multicast in random networks. Finally, for an arbitrary network deployment, we show that the coding benefit ratio is at most O(log n) for both the protocol and physical communication models. These results give guidance on the application space of network coding, and, more generally, indicate the difficulty in improving the scaling behavior of wireless networks without modification of the physical layer.     

Noncooperative iterative MMSE beamforming algorithms for ad hoc networks

An asynchronous unicast ad hoc network is considered, where each node i is equipped with a receive/transmit beam-former pair (W/sub i/, g/sub i/) designed under a quality-of-service (QoS) SNR constraint. It is first shown that the minimum sum-power beamformers for the network satisfy a weak duality condition, in which the pairs ((g/sub i//sup opt/)*, (W/sub i//sup opt/)*) achieve the same sum power as the primal network. However, the optimum receive beamformer w/sub i//sup opt/ is not in general equal to (g/sub i//sup opt/)*, in contrast to the case of cellular and time-division duplexing networks. Iterative minimum mean-square error (IMMSE) beamforming algorithms are then proposed in which w/sub i/ = g/sub i/* is enforced. These algorithms are shown to be instances of the Power Algorithm in which gi is the maximizing eigenvector of an SNR-related objective matrix. The IMMSE algorithm can also be viewed as a noncooperative beamforming game, in which the payoff includes normalized SNR, and the tax is related to interference caused at other nodes. The existence of fixed points (Nash equilibria) is proved for IMMSE. Furthermore, fixed points of IMMSE are shown to satisfy the first-order necessary conditions for optimization using a network Lagrangian. The IMMSE game is modified to yield a sequential distortionless-response beamforming algorithm, which is shown to be convergent using a Total Interference Function. Extensive simulation results illustrate that IMMSE yields better power efficiency than a greedy noncooperative SNR-maximizing game.     

基于网络编码的无线网络多流问题研究

多流问题研究多对源、宿节点之间所能达到的最大吞吐。在无线网络中,解决该问题的关键在于量化无线干扰。由于网络编码能够在一定程度上克服无线干扰的影响,因此通过使用超边来描述编码发送,并构造关于超边的冲突图,可以实现对网络编码条件下无线干扰（以协议干扰模型为例）的量化,进而解决网络编码条件下的多流问题。此外,针对在超边冲突图中搜集所有极大独立集的NP难问题,提出了一种实用的搜集算法,并给出了相关的数字结果。     

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.     

Joint Optimization of Source Power Allocation and Relay Beamforming in Multiuser Cooperative Wireless Networks

Relay beamforming techniques have been shown to significantly enhance the sum capacity of a multiuser cooperative wireless network through the optimization of the relay weights, where concurrent communications of multiple source-destination pairs are achieved via spatial multiplexing. Further optimization of the transmit power allocation over the source nodes is expected to improve the network throughput as well. In this paper, we maximize the sum capacity of a multiuser cooperative wireless network through the joint optimization of power allocation among source nodes and relay beamforming weights across the relay nodes. We consider a two-hop cooperative wireless network, consisting of single-antenna nodes, in which multiple concurrent links are relayed by a number of cooperative nodes. When a large number of relay nodes are available, the channels of different source-destination pairs can be orthogonalized, yielding enhanced sum network capacity. Such cooperative advantage is particularly significant in high signal-to-noise ratio (SNR) regime, in which the capacity follows a logarithm law with the SNR, whereas exploiting spatial multiplexing of multiple links yields capacity increment linear to the number of users. However, the capacity performance is compromised when the input SNR is low and/or when the number of relay nodes is limited. Joint optimization of source power allocation and relay beamforming is important when the input SNR and/or the number of relay nodes are moderate or the wireless channels experience different channel variances. In these cases, joint optimization of source power and distributed beamforming weights achieves significant capacity increment over both source selection and equal source power spatial multiplexing schemes. With consideration of the needs to deliver data from each source node, we further examine the optimization of global sum capacity in the presence of individual capacity requirements by maximizing sum capacity of the network subject to a minimum capacity constraint over each individual user.     

On the throughput enhancement of the downstream channel in cellular radio networks through multihop relaying

In this paper, we study the effect of multihop relaying on the throughput of the downstream channel in cellular networks. In particular, we compare the throughput of the multihop system with that of the conventional cellular system, demonstrating the achievable throughput improvement by the multihop relaying. We also propose a hybrid control strategy for the multihop relaying, in which we advocate the use of both, the direct transmission and the multihop relaying. Our study shows that most of the throughput gain can be obtained with the use of a two- and three-hop relaying scheme. Substantial throughput improvement could be additionally obtained by operating the concurrent relaying transmission in conjunction with the nonconcurrent transmission. We also argue here that the multihop relaying technology can be utilized for mitigating unfairness in quality-of-service (QoS), which comes about due to the location-dependent signal quality. Our results show that the multihop system can provide more even QoS over the cell area. The multihop cellular network architecture can also be utilized as a self-configuring network mechanism that efficiently accommodates variability of traffic distribution. We have studied the throughput improvement for the uniform, as well as for the nonuniform traffic distribution, and we conclude that the use of multihop relaying in cellular networks would be relatively robust to changes in the actual traffic distribution.     

Scalability and Performance Evaluation of Hierarchical Hybrid Wireless Networks

This paper considers the problem of scaling ad hoc wireless networks now being applied to urban mesh and sensor network scenarios. Previous results have shown that the inherent scaling problems of a multihop ldquoflatrdquo ad hoc wireless network can be improved by a ldquohybrid networkrdquo with an appropriate proportion of radio nodes with wired network connections. In this work, we generalize the system model to a hierarchical hybrid wireless network with three tiers of radio nodes: low-power end-user mobile nodes (MNs) at the lowest tier, higher power radio forwarding nodes (FNs) that support multihop routing at intermediate level, and wired access points (APs) at the highest level. Scalability properties of the proposed three-tier hierarchical hybrid wireless network are analyzed, leading to an identification of the proportion of FNs and APs as well as transmission range required for linear increase in end-user throughput. In particular, it is shown analytically that in a three-tier hierarchical network with nA APs, nF FNs, and nM MNs, the low-tier capacity increases linearly with nF, and the high-tier capacity increases linearly with nA when nA = Omega(radic{nF}) and n _A = O(nF). This analytical result is validated via ns-2 simulations for an example dense network scenario, and the model is used to study scaling behavior and performance as a function of key parameters such as AP and FN node densities for different traffic patterns and bandwidth allocation at each tier of the network.     

Capacity regions for wireless ad hoc networks

We define and study capacity regions for wireless ad hoc networks with an arbitrary number of nodes and topology. These regions describe the set of achievable rate combinations between all source-destination pairs in the network under various transmission strategies, such as variable-rate transmission, single-hop or multihop routing, power control, and successive interference cancellation (SIC). Multihop cellular networks and networks with energy constraints are studied as special cases. With slight modifications, the developed formulation can handle node mobility and time-varying flat-fading channels. Numerical results indicate that multihop routing, the ability for concurrent transmissions, and SIC significantly increase the capacity of ad hoc and multihop cellular networks. On the other hand, gains from power control are significant only when variable-rate transmission is not used. Also, time-varying flat-fading and node mobility actually improve the capacity. Finally, multihop routing greatly improves the performance of energy-constraint networks.     

Throughput Behavior in Multihop Multiantenna Wireless Networks

Multiantenna or MIMO systems offer great potential for increasing the throughput of multihop wireless networks via spatial reuse and/or spatial multiplexing. This paper characterizes and analyzes the maximum achievable throughput in multihop, MIMO-equipped, wireless networks under three MIMO protocols, spatial reuse only (SRP), spatial multiplexing only (SMP), and spatial reuse and multiplexing (SRMP), each of which enhances the throughput, but via a different way of exploiting MIMO's capabilities. We show via extensive simulation that as the number of antennas increases, the maximum achievable throughput first rises and then flattens out asymptotically under SRP, while it increases "almost" linearly under SMP or SRMP. We also evaluate the effects of several network parameters on this achievable throughput, and show how throughput behaves under these effects.     

Distributed space-time coding for multihop transmission in power line communication networks

In this paper, we consider transmission in relatively wide-stretched power line communication (PLC) networks, where repeaters are required to bridge the source-to-destination distance. In particular, it is assumed that each network node is a potential repeater and that multihop transmission is accomplished in an ad hoc fashion without the need for complex routing protocols. In such a scenario, due to the broadcasting nature of the power line channel, multiple repeater nodes may receive and retransmit the source message simultaneously. It is shown that, if no further signal processing is applied at the transmitter, simultaneous retransmission often deteriorates performance compared with single-node retransmission. We therefore advocate the application of distributed space-time block codes (DSTBCs) to the problem at hand. More specifically, we propose that each network node is assigned a unique signature sequence, which allows efficient combining at the receiver. Most notably, DSTBC-based retransmission does not require explicit collaboration among network nodes for multihop transmission and detection complexity is not increased compared with single-node retransmission. Numerical results for multihop transmission over PLC networks show that DSTBC-based retransmission achieves a considerably improved performance in terms of required transmit power and multihop delay compared with alternative retransmission strategies.     

Network Lifetime Maximization for Estimation in Multihop Wireless Sensor Networks

We consider the distributed estimation by a network consisting of a fusion center and a set of sensor nodes, where the goal is to maximize the network lifetime, defined as the estimation task cycles accomplished before the network becomes nonfunctional. In energy-limited wireless sensor networks, both local quantization and multihop transmission are essential to save transmission energy and thus prolong the network lifetime. The network lifetime optimization problem includes three components: i) optimizing source coding at each sensor node, ii) optimizing source throughput of each sensor node, and iii) optimizing multihop routing path. Fortunately, source coding optimization can be decoupled from source throughput and multihop routing path optimization, and is solved by introducing a concept of equivalent 1-bit MSE function. Based on the optimal source coding, the source throughput and multihop routing path optimization is formulated as a linear programming (LP) problem, which suggests a new notion of character-based routing. The proposed algorithm is optimal and the simulation results show that a significant gain is achieved by the proposed algorithm compared with heuristic methods.     

Simple star multihop optical network

A new multihop wavelength division multiplexed (WDM) optical network with two wavelengths per node that can give the maximum throughput and minimum delay is proposed. It is called a “simple star” multihop network. This network has good characteristics in traffic balance and minimum average number of hops. Furthermore, unlike most existing networks, it does not impose an upper limit to the number of nodes     

WMN中一种基于干扰感知的负载均衡路由协议

无线信道干扰和负载分布的不均衡严重影响无线Mesh网络吞吐量、端到端延时和资源利用率。在已有基于信噪比和邻居节点个数的干扰模型基础上,进一步研究了无线Mesh网络的链路干扰。在综合考虑了无线Mesh网络流间干扰和和流内干扰的基础上,提出路由判据PIL（Path Interfer-ence Level）。在此基础上,提出一种新的基于干扰感知的负载均衡路由协议IA-DSR（Interference-Aware DSR）。IA-DSR考虑无线网络拥塞并选择受到干扰最小的路径。仿真结果表明,在不显著增加开销的情况下,IA-DSR可以有效地提高网络的整体吞吐量,降低网络端到端时延和丢包率。