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 |
| _version_ | 1826192156751036416 |
|---|---|
| author | Tassiulas, Leandros Sinha, Abhishek Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Tassiulas, Leandros Sinha, Abhishek Modiano, Eytan H |
| author_sort | Tassiulas, Leandros |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:07:06Z |
| format | Article |
| id | mit-1721.1/106542 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:07:06Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1065422022-09-30T13:33:06Z Throughput-optimal broadcast in wireless networks with dynamic topology Tassiulas, Leandros Sinha, Abhishek Modiano, Eytan H Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Sinha, Abhishek Modiano, Eytan H 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. National Science Foundation (U.S.) (CNS-1217048) National Science Foundation (U.S.) (CNS-1524317) United States. Office of Naval Research (N00014-14-1-2190) 2017-01-19T21:08:46Z 2017-01-19T21:08:46Z 2016-07 Article http://purl.org/eprint/type/ConferencePaper 9781450341844 http://hdl.handle.net/1721.1/106542 Sinha, Abhishek, Leandros Tassiulas, and Eytan Modiano. “Throughput-Optimal Broadcast in Wireless Networks with Dynamic Topology.” Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2016, Paderborn, Germany, July 05 - 08, 2016, pp. 21-30. https://orcid.org/0000-0001-7220-0691 https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1145/2942358.2942389 Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing - MobiHoc '16 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Tassiulas, Leandros Sinha, Abhishek Modiano, Eytan H Throughput-optimal broadcast in wireless networks with dynamic topology |
| title | Throughput-optimal broadcast in wireless networks with dynamic topology |
| title_full | Throughput-optimal broadcast in wireless networks with dynamic topology |
| title_fullStr | Throughput-optimal broadcast in wireless networks with dynamic topology |
| title_full_unstemmed | Throughput-optimal broadcast in wireless networks with dynamic topology |
| title_short | Throughput-optimal broadcast in wireless networks with dynamic topology |
| title_sort | throughput optimal broadcast in wireless networks with dynamic topology |
| url | http://hdl.handle.net/1721.1/106542 https://orcid.org/0000-0001-7220-0691 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT tassiulasleandros throughputoptimalbroadcastinwirelessnetworkswithdynamictopology AT sinhaabhishek throughputoptimalbroadcastinwirelessnetworkswithdynamictopology AT modianoeytanh throughputoptimalbroadcastinwirelessnetworkswithdynamictopology |