Challenges

TLDR

Ad hoc network protocols that avoid multiple access interference do not scale, and although network coding can achieve optimal multicast throughput, it fails to increase order capacity for multi‑pair unicast, motivating the search for scalable solutions. The study aims to show that multi‑packet reception protocols can increase the order capacity of random wireless ad hoc networks and to propose scalable channel access and routing designs based on MPR. The authors analyze random wireless ad hoc networks under the protocol model, showing that multi‑packet reception protocols raise order capacity by Θ(log n) and propose many‑to‑many channel access and routing designs to achieve scalability. The results reveal that multi‑packet reception boosts order capacity by Θ(log n) and outperforms network coding for single‑source multicast and multi‑pair unicast scenarios.

Abstract

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 networks 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 factor Θ(log n) under the protocol model. We also show that MPR provides a better capacity improvement for ad hoc networks 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 routing 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.