Title: Improving Scalability of Wireless Ad Hoc Networks Using MPR
Abstract: Improving Scalability Of Wireless Ad Hoc Networks Using MPR Zheng Wang, Hamid R. Sadjadpour, Department of Electrical Engineering University of California Santa Cruz Santa Cruz, CA 95064, USA Email: { wzgold,[email protected] } Abstract— Gupta and Kumar established that per node throughput capacity of wireless ad hoc networks with multi- pair unicast traffic scales as λ(n) = Θ(1/ n log n). Recent investigation of network coding (NC) and broadcasting has demonstrated that there is no increase in the throughput order of multi-pair unicast for wireless ad hoc networks. This paper investigates the throughput scalability of wireless ad hoc networks which allows multipacket reception (MPR) and successive inter- ference cancelation (SIC) capabilities for all receiver nodes in the network. The result shows that we can p improve the throughput capacity of random networks as Θ( log n/n) with MPR using protocol model, a gain of Θ(log n) compared with earlier results 1 . I. I NTRODUCTION The throughput of wireless ad hoc networks have been studied in [1]. Gupta and Kumar [1] showed that per node throughput of random networks √ for multi-pair unicast systems is proportional to λ(n) = Θ(1/ n log n) where n is the total number of nodes in the network. This result implies that per node throughput cannot scale when the number of nodes goes to infinity. The work by Ahlswede, Cai, Li and Yeung [2] introduced the concept of network coding (NC). It has been proved that NC can achieve max-flow min-cut throughput in a directed graph for single source multicast applications. The original result for (NC) concentrated on directed graphs while most wireless networks have undirected links using half-duplex communication. Junning et al. [3] showed that NC cannot increase the throughput order of wireless ad hoc networks for multi-pair unicast applications. The result has some similarity to the conjecture given by [4], which proved that NC had no throughput gain in a single session for unicast and broadcast, and only achieves at most twice improvement for multicast in undirected graphs. Thus the motivation for this paper is to find another method to increase the throughput order of wireless ad hoc networks. From the proof procedure in [1], it can be concluded that the capacity of wireless ad hoc networks is constrained by the 1 This work was supported in part by the US Army Research Office under grants W911NF-05-1-0246 and by the Basking Chair of Computer Engineering. Opinion, interpretations, conclusions and recommendations are those of the authors and are not necessarily endorsed by the Department of Defense. J.J Garcia-Luna-Aceves Department of Computer Engineering University of California Santa Cruz Santa Cruz, CA 95064, USA Email: [email protected] mutual interference of concurrent transmissions among nodes. Our objective is to reduce this interference by increasing the receiver complexity of each node in the network. Therefore, we assume that each node is endowed with MPR and SIC. Ghez et al. [5], [6] and Tong et al. [7] demonstrated a framework for many-to-one communications also known as MPR. In this context, multiple nodes cooperate to transmit their packets simultaneously to a single node using multiuser detection (MUD), directed antennas (DA), or multiple input multiple output (MIMO) techniques [8], [9]. The receiver node utilizes multiuser detection (MUD) and successive interfer- ence cancelation (SIC) to decode multiple packets. Recently, Toumpis and Goldsmith [10] have shown that the capacity regions for ad hoc networks are significantly increased when multiple access schemes are combined with spatial reuse (i.e., multiple simultaneous transmissions), multihop routing (i.e., packet relaying), and successive interference cancelation (SIC). The main contribution p of this paper is that the throughput of MPR can achieve Θ( log n/n) with high probability 2 . We p prove that the upper and lower bounds can converge to Θ( log n/n). Our assumptions for wireless ad hoc networks are similar to those of Gupta and Kumar [1] except that each node is equipped with MPR and SIC capabilities. The network model is based on the protocol model, and we only focus on the 2- D network analysis. First, the upper bound of the throughput capacity by the maximum flow through the sparsity cut of the square unit which is similar to the max-flow min-cut theorem is proved. Secondly, we use Chernoff bound to prove this upper bound can be achieved with high probability. In the other word, this achievable bound is a lower bound equal to the upper bound. Heuristically, the lower and the upper bounds converge to Θ(r(n)). With the connectivity condition, p the transmission radius is at least Θ( log n/n), thus the throughput capacity of the MPR p scheme in the static wireless ad hoc network is at least Θ( log n/n). Comparing with the results of [1], [3], MPR scheme achieves a gain of Θ(log n). 2 We say that in our stochastic model an event occurs with high probability (w.h.p.) if its probability tends to one as n → ∞. Per node throughput capacity of the network is defined as the number of bits per second that every node can transmit w.h.p. to its destination.
Publication Year: 2007
Publication Date: 2007-02-24
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot