Multicast Throughput Order of Network Coding in Wireless Ad-hoc Networks

We show that network coding (NC) does not provide any order gain in the multicast capacity of random wireless ad hoc networks. We consider a network with n nodes distributed uniformly in a unit square, with each node acting as a source for independent information to be sent to a multicast group consisting of m randomly chosen destinations. We show that, in the presence of NC, the per-session capacity under the protocol model has a tight bound of Theta (1/(mnlog(n))) when m = O (n/log(n)) Theta (1/n) when m = Omega (n/log/n). Furthermore, we show that the per-session capacity under the physical model has a tight bound of Theta (1/(mn)) when m = O (n/(log(n))³), and Theta (1/n) when m = Omega (n/log(n)). Prior work has shown that these same order bounds are achievable utilizing only traditional store-and- forward methods.