Joint scheduling and instantaneously decodable network coding
We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region o...
| 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/61717 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826200194509701120 |
|---|---|
| author | Traskov, Danail Medard, Muriel Sadeghi, Parastoo Koetter, Ralf |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Traskov, Danail Medard, Muriel Sadeghi, Parastoo Koetter, Ralf |
| author_sort | Traskov, Danail |
| collection | MIT |
| description | We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog. |
| first_indexed | 2024-09-23T11:32:37Z |
| format | Article |
| id | mit-1721.1/61717 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:32:37Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/617172022-09-27T20:12:56Z Joint scheduling and instantaneously decodable network coding Traskov, Danail Medard, Muriel Sadeghi, Parastoo Koetter, Ralf Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel Medard, Muriel We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog. United States. Defense Advanced Research Projects Agency (Subcontract # 18870740-37362- C) United States. Space and Naval Warfare Systems Command (Contract No. N66001-06-C-2020) Seventh Framework Programme (European Commission). Network of Excellence in Wireless Communications (Contract no. 216715) 2011-03-17T21:00:13Z 2011-03-17T21:00:13Z 2009-11 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-4148-8 1930-529X INSPEC Accession Number: 11170256 http://hdl.handle.net/1721.1/61717 Traskov, D. et al. “Joint Scheduling and Instantaneously Decodable Network Coding.” Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE. 2009. 1-6. © 2009, IEEE https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/GLOCOM.2009.5425315 IEEE Global Telecommunications Conference 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 | Traskov, Danail Medard, Muriel Sadeghi, Parastoo Koetter, Ralf Joint scheduling and instantaneously decodable network coding |
| title | Joint scheduling and instantaneously decodable network coding |
| title_full | Joint scheduling and instantaneously decodable network coding |
| title_fullStr | Joint scheduling and instantaneously decodable network coding |
| title_full_unstemmed | Joint scheduling and instantaneously decodable network coding |
| title_short | Joint scheduling and instantaneously decodable network coding |
| title_sort | joint scheduling and instantaneously decodable network coding |
| url | http://hdl.handle.net/1721.1/61717 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT traskovdanail jointschedulingandinstantaneouslydecodablenetworkcoding AT medardmuriel jointschedulingandinstantaneouslydecodablenetworkcoding AT sadeghiparastoo jointschedulingandinstantaneouslydecodablenetworkcoding AT koetterralf jointschedulingandinstantaneouslydecodablenetworkcoding |