Throughput-optimal broadcast in wireless networks with dynamic topology
We consider the problem of throughput-optimal broadcasting in time-varying wireless network with an underlying Directed Acyclic Graph (DAG) topology. Known broadcast algorithms route packets along pre-computed spanning trees. In large wireless networks with time-varying connectivities, the optimal t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106542 https://orcid.org/0000-0001-7220-0691 https://orcid.org/0000-0001-8238-8130 |
| Summary: | We consider the problem of throughput-optimal broadcasting in time-varying wireless network with an underlying Directed Acyclic Graph (DAG) topology. Known broadcast algorithms route packets along pre-computed spanning trees. In large wireless networks with time-varying connectivities, the optimal trees are difficult to compute and maintain. In this paper we propose a new online throughput-optimal broadcast algorithm, which takes packet-by-packet scheduling and routing decisions, obviating the need for maintaining any global topological structures, such as spanning-trees. Our algorithm utilizes certain queue-like system-state information for making transmission decisions and hence, may be thought of as a generalization of the well-known back pressure algorithm, which makes point-to-point unicast transmission decisions based on local queue-length information. Technically, the back-pressure algorithm is derived by stabilizing the packet-queues. However, because of packet-duplications, the work-conservation principle is violated and appropriate queuing processes are difficult to define in the broadcast setting. To address this fundamental issue, we identify certain state-variables whose dynamics behave like virtual queues. By stochastically stabilizing these virtual queues, we devise a throughput-optimal broadcast policy. We also derive new characterizations of the broadcast-capacity of time-varying wireless DAGs and derive an efficient algorithm to compute the capacity exactly under certain assumptions, and a poly-time approximation algorithm for computing the capacity approximately under less restrictive assumptions. |
|---|