Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116441 https://orcid.org/0000-0001-7220-0691 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1811081204247560192 |
|---|---|
| author | Paschos, Georgios Li, Chih-Ping Sinha, Abhishek Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Paschos, Georgios Li, Chih-Ping Sinha, Abhishek Modiano, Eytan H |
| author_sort | Paschos, Georgios |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:43:05Z |
| format | Article |
| id | mit-1721.1/116441 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:43:05Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1164412022-09-27T21:26:37Z Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks Paschos, Georgios Li, Chih-Ping Sinha, Abhishek Modiano, Eytan H Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Sinha, Abhishek Modiano, Eytan H 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. National Science Foundation (U.S.) (Grant CNS-1217048) United States. Office of Naval Research (Grant N00014-12-1-0064) United States. Army Research Office. Multidisciplinary University Research Initiative (Grant W911NF-08-1-0238) 2018-06-19T20:19:26Z 2018-06-19T20:19:26Z 2016-07 2016-02 Article http://purl.org/eprint/type/JournalArticle 1063-6692 1558-2566 http://hdl.handle.net/1721.1/116441 Sinha, Abhishek, Georgios Paschos, Chih-Ping Li, and Eytan Modiano. “Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks.” IEEE/ACM Transactions on Networking 25, no. 1 (February 2017): 377–391. https://orcid.org/0000-0001-7220-0691 https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/tnet.2016.2582907 IEEE/ACM Transactions on Networking Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Prof. Modiano |
| spellingShingle | Paschos, Georgios Li, Chih-Ping Sinha, Abhishek Modiano, Eytan H Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks |
| title | Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks |
| title_full | Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks |
| title_fullStr | Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks |
| title_full_unstemmed | Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks |
| title_short | Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks |
| title_sort | throughput optimal multihop broadcast on directed acyclic wireless networks |
| url | http://hdl.handle.net/1721.1/116441 https://orcid.org/0000-0001-7220-0691 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT paschosgeorgios throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks AT lichihping throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks AT sinhaabhishek throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks AT modianoeytanh throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks |