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

Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast trafc scales with an increasing number of nodes as , thus indicating that network performance does not scale well. 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. Here, for multiple unicast ows in a random topology under the protocol communication model of Gupta and Kumar [1], we show that for arbitrary network coding and broadcasting in a random topology that the throughput scales as !#$ where is the total number of nodes and !# is the transmission radius. When !# is set to ensure connectivity, %& \u27() , which is of the same order as the lower bound for the throughput without network coding and broadcasting; in other words, network coding and broadcasting at most provides a constant factor improvement in the throughput. This result is also extended to other dimensional random deployment topologies, where it is shown that * +, for the - topology, * / 021.3547680 for 9( networks and ;:\u3c \u3e=? A 0 135@ 4 ACBED 0 in F# , combined with the lower bounds of non-coding throughput, we show coding&broadcasting provide no order difference improvement. Of course, in practice the constant factor of improvement is important; thus, to more precisely characterize the benet of network coding for multi-pair communication in wireless networks, we derive tight bounds for the throughput benet ratio - the ratio of optimal network coding scheme throughput to the optimal non-coding ow scheme throughput. We show that the improvement factor is .G2.+G HJHI5K for - random networks, where LNMO 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 ow schemes. For networks, we obtain an upper bound for the throughput benet ratio as P$ *=QR HTS U .G2H H for large , where RHTS ?VXW,Y7Z#[ L K\u3e\ (L^]. This is obtained by nding a tighter upper bound for the coding scheme throughput and a tighter lower bound for the ow scheme throughput. We then consider the more general physical communication model as in Gupta and Kumar [1]. We show that the coding scheme throughput under the physical model is upper bounded by 0. for the random network and by \u27a .0 for the case. We also show the ow scheme throughput for the - case can achieve the same order throughput as the coding scheme. Combined with previous work on a lower bound [2], we conclude that the throughput benet ratio under the physical model is also bounded by a constant. Thus we have shown for both the protocol and physical model, the coding benet on throughput is a constant factor. Finally, we evaluate the potential coding gain from another important perspective - total energy efciency - and show that the factor by which the total energy is decreased is upper bounded by 9