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 language||English (US)|
|Title of host publication||2017 IEEE International Symposium on Information Theory, ISIT 2017|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||5|
|State||Published - Aug 9 2017|
|Event||2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany|
Duration: Jun 25 2017 → Jun 30 2017
|Name||IEEE International Symposium on Information Theory - Proceedings|
|Other||2017 IEEE International Symposium on Information Theory, ISIT 2017|
|Period||6/25/17 → 6/30/17|
Bibliographical noteFunding 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.