NDLI: Bounds on the Gain of Network Coding and Broadcasting in Wireless Networks

Content Provider	IEEE Xplore Digital Library
Author	Junning Liu Goeckel, D. Towsley, D.
Copyright Year	2007
Description	Author affiliation: Univ. of Massachusetts, Amherst (Junning Liu)
Abstract	Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales (poorly) as lambda(n) = Theta (1 / radic(n log n)) with an increasing number of nodes n. However, Gupta and Kumar did not consider the possibility of network coding and broadcasting in their model, and recent work has suggested that such techniques have the potential to greatly improve network throughput. In [1], we have shown that for the protocol communication model of Gupta and Kumar [2], the multi-unicast throughput of schemes using arbitrary network coding and broadcasting in a two-dimensional random topology also scales as lambda(n) = Theta (1 / radic(n log $n))^{1},$ thus showing that network coding provides no order difference improvement on throughput. Of course, in practice the constant factor of improvement is important; thus, here we derive bounds for the throughput benefit ratio -the ratio of the throughput of the optimal network coding scheme to the throughput of the optimal non-coding flow scheme. We show that the improvement factor is 1+ Delta / 1+Delta /2for 1D random networks, where Delta > 0 is a parameter of the wireless medium that characterizes the intensity of the interference. We obtain this by giving tight bounds (both upper and lower) on the throughput of the coding and flow schemes. For 2D networks, we obtain an upper bound for the throughput benefit ratio as alpha (n) les $2c_{Delta}$ radic(pi = 1+Delta/Delta) for large n, wnere $c_{Delta}$ = max {2, $radic(Delta^{2}$ + 2Delta)}. This is obtained by finding an upper bound for the coding throughput and a lower bound for the flow throughput. We then consider the more general physical communication model as in Gupta and Kumar. We show that the coding scheme throughput in this case is upper bounded by Theta (1/n) for the 1D random network and by Theta(1/radic(n)) for the 2D case. We also show the flow scheme throughput for the ID case can achieve the same order throughput as the coding scheme. Combined with previous work on a 2D lower bound [3], we conclude that the throughput benefit ratio under the physical model is also bounded by a constant; thus, we have shown for both the protocol and physical model that the coding benefit in terms of throughput is a constant factor. Finally, we evaluate the potential coding gain from another important perspective - total energy efficiency - and show that the factor by which the total energy is decreased is upper bounded by 3.
Starting Page	724
Ending Page	732
File Size	659094
Page Count	9
File Format	PDF
ISBN	1424410479
ISSN	0743166X
DOI	10.1109/INFCOM.2007.90
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-05-06
Publisher Place	Spain
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Network coding Broadcasting Wireless networks Throughput Protocols Upper bound Ad hoc networks Unicast Telecommunication traffic Traffic control
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

Cooperative Network Coding-Aware Routing for Multi-Rate Wireless Networks

The Capacity of Ad Hoc Networks with Heterogeneous Traffic Using Cooperation

Capacity of Wireless Networks with Heterogeneous Traffic

Identifying the network coding opportunity

Bounding the power rate function of wireless ad hoc networks

Improving throughput in multihop wireless networks

Characterising the Behaviour of IEEE 802.11 Broadcast Transmissions in Ad Hoc Wireless LANs

An efficient opportunistic multicast routing for mobile ad hoc networks

Bounds on the Gain of Network Coding and Broadcasting in Wireless Networks

Similar Documents

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

Cooperative Network Coding-Aware Routing for Multi-Rate Wireless Networks

The Capacity of Ad Hoc Networks with Heterogeneous Traffic Using Cooperation

Capacity of Wireless Networks with Heterogeneous Traffic

Identifying the network coding opportunity

Bounding the power rate function of wireless ad hoc networks

Improving throughput in multihop wireless networks

Characterising the Behaviour of IEEE 802.11 Broadcast Transmissions in Ad Hoc Wireless LANs

An efficient opportunistic multicast routing for mobile ad hoc networks

Bounds on the Gain of Network Coding and Broadcasting in Wireless Networks