Efficiently finding simple schedules in Gaussian half-duplex relay line networks
Efficiently finding simple schedules in Gaussian half-duplex relay line networks
复制标题
在高斯半双工中继线路网络中有效地找到简单的调度
DOI：
10.1109/isit.2017.8006572
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Daniela Tuninetti
中科院分区：
文献类型：
--
作者：
Yahya H. Ezzeldin;Martina Cardone;C. Fragouli;Daniela Tuninetti
由于需要考虑指数数量的监听/传输网络状态，最佳地操作高斯半双工 (HD) 中继网络的问题具有挑战性。最近的结果表明，对于具有 N 个中继的高斯 HD 网络类别，始终存在一个简单的调度，即最多具有 N+1 个活动状态，足以进行近似（即达到恒定间隙）容量表征。本文研究了如何通过线路网络有效地找到这样一个简单的时间表。为此，设计并证明了多项式时间算法可以输出达到近似容量的简单调度。该算法的关键要素是利用高清网络状态和图中边缘着色之间的相似性。它还表明，该算法允许导出高斯线网络近似容量的封闭式表达式，该表达式可以在线性时间内进行分布式评估。
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.