Efficiently finding simple schedules in Gaussian half-duplex relay line networks

Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Daniela Tuninetti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

The problem of operating a Gaussian Half-Duplex (HD) relay network optimally is challenging due to the exponential number of listen/transmit network states that need to be considered. Recent results have shown that, for the class of Gaussian HD networks with N relays, there always exists a simple schedule, i.e., with at most N+1 active states, that is sufficient for approximate (i.e., up to a constant gap) capacity characterization. This paper investigates how to efficiently find such a simple schedule over line networks. Towards this end, a polynomial-time algorithm is designed and proved to output a simple schedule that achieves the approximate capacity. The key ingredient of the algorithm is to leverage similarities between network states in HD and edge coloring in a graph. It is also shown that the algorithm allows to derive a closed-form expression for the approximate capacity of the Gaussian line network that can be evaluated distributively and in linear time.

Original languageEnglish (US)
Title of host publication2017 IEEE International Symposium on Information Theory, ISIT 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages471-475
Number of pages5
ISBN (Electronic)9781509040964
DOIs
StatePublished - Aug 9 2017
Event2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany
Duration: Jun 25 2017Jun 30 2017

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2017 IEEE International Symposium on Information Theory, ISIT 2017
CountryGermany
CityAachen
Period6/25/176/30/17

Bibliographical note

Funding Information:
The work of Y. H. Ezzeldin, M. Cardone and C. Fragouli was supported in part by NSF under Awards 1514531 and 1314937. The work of D. Tuninetti was supported by NSF under Award 1527059.

Fingerprint Dive into the research topics of 'Efficiently finding simple schedules in Gaussian half-duplex relay line networks'. Together they form a unique fingerprint.

Cite this