Name
Abstract | ||
|---|---|---|
Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales (poorly) as lambda(n) = circle minus(1/root n logn) 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) = circle minus(1/root 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/2 for 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)< 2c(Delta)root pi 1+Delta/Delta for large n, where c(Delta) = max{2, -,root Delta(2) +2 Delta}. 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 [2]. We show that the coding scheme throughput in this case is upper bounded by e( 1) for the ID random network and by 19( for the 2D case. We also circle minus(1/root n) show the flow scheme throughput for the ID case can achieve the same order throughput as the coding scheme. Combined wit previous work on a 2D lower bound [31, 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/INFCOM.2007.90 | INFOCOM 2007, VOLS 1-5 |
Keywords | Field | DocType |
throughput of ad hoc networks with multi-pair unicast trafc scales poorly as,network coding,wireless networks,lower bound,throughput,encoding,wireless network,network performance,ad hoc network,protocols,ad hoc networks,unicast,upper bound,broadcasting,communication model | Linear network coding,Wireless network,Topology,Coding gain,Random graph,Upper and lower bounds,Computer science,Computer network,Throughput,Wireless ad hoc network,Time complexity | Conference |
ISSN | Citations | PageRank |
0743-166X | 107 | 6.66 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Junning Liu | 1 | 433 | 18.98 |
| Dennis Goeckel | 2 | 1060 | 69.96 |
| Don Towsley | 3 | 18693 | 1951.05 |