On the Complexity of Scheduling in Half-Duplex Diamond Networks
On the Complexity of Scheduling in Half-Duplex Diamond Networks
复制标题
半双工钻石网络调度的复杂性研究
DOI：
10.1109/tit.2016.2548467
复制
发表时间：
2016
影响因子：
2.5
通讯作者：
Ayfer Özgür
中科院分区：
文献类型：
--
作者：
Siddhartha Brahma;C. Fragouli;Ayfer Özgür
我们考虑一个 n 中继高斯钻石网络，其中源借助 n 个半双工中继与目的地进行通信。要实现接近该网络容量的速率，需要在最佳传输/接收调度下使用所有 n 个中继。即使对于中等的 n 值，这也可能具有显着的操作复杂性，因为最佳调度可能具有 2n 个不同的网络状态（因为每个中继都可以处于发送或接收模式）。在本文中，我们研究是否可以通过使用仅具有很少活动状态的发送/接收调度以及仅使用很少的中继来实现大部分网络容量。首先，我们推测近似最优调度最多有 n+1 个状态，而不是 2n 个可能的状态。我们通过开发证明策略并通过计算实现它来证明大小为 n ≤ 6 的网络的这一猜想。其次，我们表明，仅采用点对点通信和仅具有两个活动状态的半双工调度的两个中继的路由策略可以实现至少一半（大约）的网络容量。使用线性规划和子模函数的技术来得出结果。
We consider an n-relay Gaussian diamond network where a source communicates to a destination with the help of n half-duplex relays. Achieving rates close to the capacity of this network requires to employ all the n relays under an optimal transmit/receive schedule. Even for the moderate values of n, this can have significant operational complexity as the optimal schedule may possibly have 2n different states for the network (since each of the relays can be in either transmitting or receiving mode). In this paper, we investigate whether a significant fraction of the network capacity can be achieved by using transmit/receive schedules that have only few active states and by using only few relays. First, we conjecture that the approximately optimal schedule has at most n+1 states instead of the 2n possible states. We prove this conjecture for networks of size n ≤ 6 by developing a proof strategy and implementing it computationally. Second, we show that routing strategies that only employ the point-to-point communication and two of the relays with a half-duplex schedule that has only two active states can achieve at least half the capacity (approximately) of the network. Techniques from linear programming and submodular functions are used to derive the results.