Efficient Capacity Computation and Power Optimization for Relay Networks
Efficient Capacity Computation and Power Optimization for Relay Networks
复制标题
中继网络的高效容量计算和功率优化
DOI：
10.1109/tit.2013.2295099
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
R. Etkin
中科院分区：
文献类型：
--
作者：
F. Parvaresh;R. Etkin
各种单源单目的中继网络模型的容量或容量近似值已根据割集上界来表征。原则上，直接计算这个界限需要评估切割能力指数许多削减。我们证明了在某些特殊的假设下，中继网络的最小截容量可以转化为一个次模函数的极小化，因此，可以有效地计算。我们使用这个结果表明，容量，或近似的高斯，无线擦除，和Avestimehr-Diggavi-Tse确定性中继网络模型中的一个恒定的间隙内的容量可以在多项式时间内计算。我们提出了一些经验的结果表明，计算恒定间隙近似高斯中继网络的容量约300个节点可以在几分钟内完成。对于高斯网络，割集容量也是分配给节点的功率的函数。我们考虑一个家庭的权力优化问题，并表明，他们可以在一个多项式时间内解决。特别是，我们表明，分配给节点的权力的总和最小化的最小速率约束（测量方面的割集界限）可以计算在多项式时间。我们提出了一个启发式算法来解决这个问题，并通过随机高斯网络上的模拟来衡量其性能。我们观察到，在最佳分配，大部分的功率被分配给一个小的中继子集，这表明网络简化可能没有过度的性能下降。
The capacity or approximations to capacity of various single-source single-destination relay network models has been characterized in terms of the cut-set upper bound. In principle, a direct computation of this bound requires evaluating the cut capacity over exponentially many cuts. We show that the minimum cut capacity of a relay network under some special assumptions can be cast as a minimization of a submodular function, and as a result, can be computed efficiently. We use this result to show that the capacity, or an approximation to the capacity within a constant gap for the Gaussian, wireless erasure, and Avestimehr-Diggavi-Tse deterministic relay network models can be computed in polynomial time. We present some empirical results showing that computing constant-gap approximations to the capacity of Gaussian relay networks with around 300 nodes can be done in order of minutes. For Gaussian networks, cut-set capacities are also functions of the powers assigned to the nodes. We consider a family of power optimization problems and show that they can be solved in a polynomial time. In particular, we show that the minimization of the sum of powers assigned to the nodes subject to a minimum rate constraint (measured in terms of cut-set bounds) can be computed in the polynomial time. We propose a heuristic algorithm to solve this problem and measure its performance through simulations on random Gaussian networks. We observe that in the optimal allocations, most of the power is assigned to a small subset of relays, which suggests that network simplification may be possible without excessive performance degradation.