Efficient Capacity Computation and Power Optimization for Relay Networks

Details Efficient Capacity Computation and Power Optimization for Relay Networks Efficient Capacity Computation and Power Optimization for Relay Networks

2011-11-18

arxiv.org/abs/1111.4244v1

Computer Science

Information Theory

Submitted to IEEE Transactions on Information Theory

Scientific paper

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 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 polynomial time. We propose an 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.

Affiliated with

Also associated with

No associations

Rating

Efficient Capacity Computation and Power Optimization for Relay Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Capacity Computation and Power Optimization for Relay Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Capacity Computation and Power Optimization for Relay Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-548306