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

摘要

We consider a network with n nodes distributed uniformly in a unit square. We show that, under the protocol model, when n_s = Ω (log(n)^{1+α} ) out of the n nodes, each act as source of independent information for a multicast group consisting of m randomly chosen destinations, the per-session capacity in the presence of network coding (NC) has a tight bound of Θ(frac{sqrt{n}}{n_ssqrt{mlog(n)}}) when m = O(frac{n}{log(n)}) and Θ(frac{1}{n_s}) when m = Ω(frac{n}{log(n)}). In the case of the physical model, we consider n_s = n and show that the per-session capacity under the physical model has a tight bound of Θ(frac{1}{sqrt{mn}}) when m = O(frac{n}{(log(n))^3}), and Θ(frac{1}{n}) when m = Ω(frac{n}{log(n)}). Prior work has shown that these same order bounds are achievable utilizing only traditional store-and-forward methods. Consequently, our work implies that the network coding gain is bounded by a constant for all values of m. For the physical model we have an exception to the above conclusion when m is bounded by O(frac{n}{(log(n))^3}) and Ω(frac{n}{log(n)}). In this range, the network coding gain is bounded by O((log(n))^frac{1}{2} ).