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 |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/114603 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0001-7220-0691 |
| _version_ | 1826212968350613504 |
|---|---|
| author | Paschos, Georgios Li, Chih-Ping Modiano, Eytan H Sinha, Abhishek |
| 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 Modiano, Eytan H Sinha, Abhishek |
| 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-23T15:41:01Z |
| format | Article |
| id | mit-1721.1/114603 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:41:01Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1146032022-10-02T03:24:30Z Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless Networks Paschos, Georgios Li, Chih-Ping Modiano, Eytan H Sinha, Abhishek Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Modiano, Eytan H Sinha, Abhishek 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 (N00014-12-1-0064) United States. Office of Naval Research. Multidisciplinary University Research Initiative (Grant W911NF-08-1-02380 2018-04-06T22:35:50Z 2018-04-06T22:35:50Z 2016-07 2018-04-05T17:42:08Z Article http://purl.org/eprint/type/JournalArticle 1063-6692 1558-2566 http://hdl.handle.net/1721.1/114603 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-8238-8130 https://orcid.org/0000-0001-7220-0691 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) arXiv |
| spellingShingle | Paschos, Georgios Li, Chih-Ping Modiano, Eytan H Sinha, Abhishek 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/114603 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0001-7220-0691 |
| work_keys_str_mv | AT paschosgeorgios throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks AT lichihping throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks AT modianoeytanh throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks AT sinhaabhishek throughputoptimalmultihopbroadcastondirectedacyclicwirelessnetworks |