Computing Half-Duplex Schedules in Gaussian Relay Networks via Min-Cut Approximations
Computing Half-Duplex Schedules in Gaussian Relay Networks via Min-Cut Approximations
复制标题
通过最小割近似计算高斯中继网络中的半双工调度
DOI：
10.1109/tit.2014.2359440
复制
发表时间：
2014
影响因子：
2.5
通讯作者：
A. Avestimehr
中科院分区：
文献类型：
--
作者：
R. Etkin;F. Parvaresh;Ilan Shomorony;A. Avestimehr
计算最佳的半双工调度在高斯中继网络是一个具有挑战性的问题，由于缺乏一个准确的容量特性和大量的发送-接收配置，必须考虑。我们的做法的问题，使用一个恒定的间隙容量近似的基础上，独立编码的节点上的割集界。我们提出了一个优化问题来获得割集最优半双工调度，发现这个问题一般很难求解。这是因为它涉及指数数量的变量，因为将每个节点分配到发送器或接收器模式的方式的数量在节点数量中是指数的。我们提出了一个通用的技术，利用特定的结构在一个给定的网络的拓扑结构，使我们能够降低这个问题的复杂性。在某些类别的网络拓扑结构，我们的方法产生多项式时间算法，找到半双工的时间表，实现容量在一个恒定的差距。我们使用模拟来显示运行时间的改进，在不同的SNR制度，并比较各种半双工调度方法的性能。
Computing optimal half-duplex schedules in Gaussian relay networks is a challenging problem due to the lack of an exact capacity characterization and the large number of transmit-receive configurations that must be considered. We approach the problem using a constant-gap capacity approximation based on the cut-set bound with independent encoding at the nodes. We formulate an optimization problem to obtain the cut-set optimal half-duplex schedule and find that it is hard to solve in general. This is because it involves an exponential number of variables, since the number of ways to assign each node to either transmitter or receiver mode is exponential in the number of nodes. We present a general technique that takes advantage of specific structures in the topology of a given network and allows us to reduce the complexity of this problem. In certain classes of network topologies, our approach yields polynomial time algorithms for finding half-duplex schedules that achieve capacity within a constant gap. We use simulations to show running time improvements over alternative methods and compare the performance of various half-duplex scheduling approaches in different SNR regimes.