Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks
In this paper, we provide and study a general framework that facilitates the development of distributed mechanisms to achieve full utilization of multihop wireless networks. In particular, we describe a generic randomized routing, scheduling, and flow control scheme that allows for a set of imperfec...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/66298 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1826205508686577664 |
|---|---|
| author | Eryilmaz, Atilla Ozdaglar, Asuman E. Shah, Devavrat Modiano, Eytan H. |
| author2 | Lincoln Laboratory |
| author_facet | Lincoln Laboratory Eryilmaz, Atilla Ozdaglar, Asuman E. Shah, Devavrat Modiano, Eytan H. |
| author_sort | Eryilmaz, Atilla |
| collection | MIT |
| description | In this paper, we provide and study a general framework that facilitates the development of distributed mechanisms to achieve full utilization of multihop wireless networks. In particular, we describe a generic randomized routing, scheduling, and flow control scheme that allows for a set of imperfections in the operation of the randomized scheduler to account for potential errors in its operation. These imperfections enable the design of a large class of low-complexity and distributed implementations for different interference models. We study the effect of such imperfections on the stability and fairness characteristics of the system and explicitly characterize the degree of fairness achieved as a function of the level of imperfections. Our results reveal the relative importance of different types of errors on the overall system performance and provide valuable insight to the design of distributed controllers with favorable fairness characteristics. In the second part of the paper, we focus on a specific interference model, namely the secondary interference model, and develop distributed algorithms with polynomial communication and computation complexity in the network size. This is an important result given that earlier centralized throughput-optimal algorithms developed for such a model relies on the solution to an NP-hard problem at every decision. This results in a polynomial complexity cross-layer algorithm that achieves throughput optimality and fair allocation of network resources among the users. We further show that our algorithmic approach enables us to efficiently approximate the capacity region of a multihop wireless network. |
| first_indexed | 2024-09-23T13:14:11Z |
| format | Article |
| id | mit-1721.1/66298 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:14:11Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/662982022-09-28T12:50:44Z Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks Eryilmaz, Atilla Ozdaglar, Asuman E. Shah, Devavrat Modiano, Eytan H. Lincoln Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Modiano, Eytan H. Modiano, Eytan H. Ozdaglar, Asuman E. Shah, Devavrat In this paper, we provide and study a general framework that facilitates the development of distributed mechanisms to achieve full utilization of multihop wireless networks. In particular, we describe a generic randomized routing, scheduling, and flow control scheme that allows for a set of imperfections in the operation of the randomized scheduler to account for potential errors in its operation. These imperfections enable the design of a large class of low-complexity and distributed implementations for different interference models. We study the effect of such imperfections on the stability and fairness characteristics of the system and explicitly characterize the degree of fairness achieved as a function of the level of imperfections. Our results reveal the relative importance of different types of errors on the overall system performance and provide valuable insight to the design of distributed controllers with favorable fairness characteristics. In the second part of the paper, we focus on a specific interference model, namely the secondary interference model, and develop distributed algorithms with polynomial communication and computation complexity in the network size. This is an important result given that earlier centralized throughput-optimal algorithms developed for such a model relies on the solution to an NP-hard problem at every decision. This results in a polynomial complexity cross-layer algorithm that achieves throughput optimality and fair allocation of network resources among the users. We further show that our algorithmic approach enables us to efficiently approximate the capacity region of a multihop wireless network. United States. Defense Threat Reduction Agency (DTRA Grant HDTRA1-08-1-0016) United States. Defense Advanced Research Projects Agency (Control- Based Mobile Ad-Hoc Networking (CBMANET) Program, Subcontract 060786) United States. Army Research Office (ARO Muri Grant W911NF-08-1-0238) 2011-10-17T18:38:46Z 2011-10-17T18:38:46Z 2010-04 2009-03 Article http://purl.org/eprint/type/JournalArticle 1063-6692 INSPEC Accession Number: 11228753 http://hdl.handle.net/1721.1/66298 Eryilmaz, A. et al. “Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks.” Networking, IEEE/ACM Transactions on 18.2 (2010): 638-651. ©2011 IEEE. https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1109/tnet.2009.2030681 Proceedings of the IEEE/ACM Transactions on Networking Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Eryilmaz, Atilla Ozdaglar, Asuman E. Shah, Devavrat Modiano, Eytan H. Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks |
| title | Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks |
| title_full | Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks |
| title_fullStr | Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks |
| title_full_unstemmed | Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks |
| title_short | Distributed Cross-Layer Algorithms for the Optimal Control of Multihop Wireless Networks |
| title_sort | distributed cross layer algorithms for the optimal control of multihop wireless networks |
| url | http://hdl.handle.net/1721.1/66298 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT eryilmazatilla distributedcrosslayeralgorithmsfortheoptimalcontrolofmultihopwirelessnetworks AT ozdaglarasumane distributedcrosslayeralgorithmsfortheoptimalcontrolofmultihopwirelessnetworks AT shahdevavrat distributedcrosslayeralgorithmsfortheoptimalcontrolofmultihopwirelessnetworks AT modianoeytanh distributedcrosslayeralgorithmsfortheoptimalcontrolofmultihopwirelessnetworks |