The user capacity of barrage relay networks

Barrage relay networks (BRNs) are a class of mobile ad hoc networks based on an autonomous cooperative communications scheme that affords a distributed, rapid, and robust broadcast mechanism. BRN-based radios are currently being used operationally; understanding scaling laws for BRNs can thus shed light on how future systems ought be designed to address a wider range of military missions. It has previously been shown that BRNs scale optimally for broadcast traffic (in terms of sum throughput and latency). Furthermore, experimental evidence supports the scalability of BRNs in practice: a 215-node network of TrellisWare´s BRN-based CheetahNet radios was demonstrated in 2010 as part of the Rim of the Pacific (RIMPAC) exercise. In this work, we study scaling laws for unicast in BRNs. The spatial extent of unicast transmissions in BRNs can be contained via controlled barrage regions (CBRs), while barrage access control protocols - which are a type of path-oriented medium access control (PO-MAC) protocol - can be used to schedule CBRs in space and time. Traditional techniques for scaling analysis support neither autonomous cooperation nor PO-MAC protocols; we therefore study the fundamental limits of CBR-based protocols through the lens of user capacity, which we define as the maximum number of constant-rate, delay-optimal unicast flows that an n-node network can simultaneously support. The user capacity of dense networks operating under a CBR protocol is shown to scale as Θ(√n) when source-destination pairs are chosen randomly. BRNs are thus able to transport Θ(√(n/log n)) bit-meters/sec, which is order optimal (in the Gupta-Kumar sense). If the source-destination pairs are instead chosen so that their separation (in hops) is a geometric random variable, then the user capacity scales as Θ(n/ log n). Thus, in a wireless network dominated by localized traffic, BRNs can achieve throughput that is almost linear in the number of users- Finally, it is shown via software simulation that distributed, greedy algorithms provide order optimal scheduling of CBRs for both the random and localized traffic models. This suggests that scalable protocols for unicast in BRNs can be realized in practice.