Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks
Authors:
Open Access
- 9 July 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 25 (1) , 377-391
Abstract
We study the problem of efficiently disseminating packets in multi-hop wireless networks. At each time slot, the network controller activates a set of non-interfering links and forward selected copies of packets on each activated link. The maximum rate of commonly received packets is referred to as the broadcast capacity of the network. Existing policies achieve the broadcast capacity by balancing traffic over a set of spanning trees, which are difficult to maintain in a large and time-varying wireless network. In this paper, we propose a new dynamic algorithm that achieves the broadcast capacity when the underlying network topology is a directed acyclic graph (DAG). This algorithm is decentralized, utilizes local information only, and does not require the use of spanning trees. The principal methodological challenge inherent in this problem is the absence of work-conservation principle due to the duplication of packets, which renders usual queuing modeling inapplicable. We overcome this difficulty by studying relative packet deficits and imposing in-order delivery constraints to every node in the network. We show that in-order delivery is throughput-optimal in DAGs and can be exploited to simplify the design and analysis of optimal algorithms. Our capacity characterization also leads to a polynomial time algorithm for computing the broadcast capacity of any wireless DAG under the primary interference constraints. In addition, we propose a multiclass extension of our algorithm, which can be effectively used for broadcasting in any network with arbitrary topology. Simulation results show that the our algorithm has a superior delay performance as compared with the traditional tree-based approaches.Keywords
All Related Versions
Funding Information
- NSF (CNS-1217048, AST-1547331)
- ONR (N00014-12-1-0064)
- ARO MURI (W911NF-08-1-0238)
- WiNC Project through the National and Community Funds (European Social Fund)
This publication has 18 references indexed in Scilit:
- Optimal distributed broadcasting with per-neighbor queues in acyclic overlay networks with arbitrary underlay capacity constraints2013
- An efficient broadcasting scheme in support of military ad hoc communications in battle field2013
- Stochastic Network Optimization with Application to Communication and Queueing SystemsSynthesis Lectures on Communication Networks, 2010
- A survey on sensor networksIEEE Communications Magazine, 2002
- A framework for routing and congestion control for multicast information flowsIEEE Transactions on Information Theory, 2002
- A Randomized Algorithm for Gossiping in Radio Networks2001
- A mobility-transparent deterministic broadcast mechanism for ad hoc networksIEEE/ACM Transactions on Networking, 1999
- Optimal Power-of-Two Replenishment Strategies in Capacitated General Production/Distribution NetworksManagement Science, 1993
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992
- A survey of gossiping and broadcasting in communication networksNetworks, 1988