Efficiently Finding Simple Schedules in Gaussian Half-Duplex Relay Line Networks
| Autor: | Ezzeldin, Yahya H., Cardone, Martina, Fragouli, Christina, Tuninetti, Daniela |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/ISIT.2017.8006572 |
| Popis: | 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. Additionally, it is shown using this closed-form that the problem of Half-Duplex routing is NP-Hard. Comment: A short version of this paper was submitted to ISIT 2017 |
| Databáze: | arXiv |
| Externí odkaz: |
|