UC Santa Cruz

The protocols used in ad hoc networks today are based on the assumption that the best way to approach multiple access interference (MAI) is to avoid it. Unfortunately, as the seminal work by Gupta and Kumar has shown, this approach does not scale. Recently, Ahlswede, Ning, Li, and Yeung showed that network coding (NC) can attain the max-flow min-cut throughput for multicast applications in directed graphs with point-to-point links. Motivated by this result, many researchers have attempted to make ad hoc net- works scale using NC. However, the work by Liu, Goeckel, and Towsley has shown that NC does not increase the order capacity of wireless ad hoc networks for multi-pair unicast applications. We demonstrate that protocol architectures that exploit multi-packet reception (MPR) do increase the order capacity of random wireless ad hoc networks by a fac- tor Θ(log n) under the protocol model. We also show that MPR provides a better capacity improvement for ad hoc net- works than NC when the network experiences a single-source multicast and multi-pair unicasts. Based on these results, we introduce design problems for channel access and rout- ing based on MPR, such that nodes communicate with one another on a many-to-many basis, rather than one-to-one as it is done today, in order to make ad hoc networks truly scalable.