TY - JOUR

T1 - Gaussian half-duplex relay networks

T2 - Improved constant gap and connections with the assignment problem

AU - Cardone, Martina

AU - Tuninetti, Daniela

AU - Knopp, Raymond

AU - Salim, Umer

PY - 2014/6

Y1 - 2014/6

N2 - This paper considers a Gaussian relay network where a source transmits a message to a destination with the help of N half-duplex relays. The information theoretic cut-set upper bound to the capacity is shown to be achieved to within 1.96(N+2) bits by noisy network coding, thereby reducing the previously known gap. This gap is obtained as a special case of a more general constant gap result for Gaussian half-duplex multicast networks. It is then shown that the generalized degrees-of-freedom of this network is the solution of a linear program, where the coefficients of the linear inequality constraints are proved to be the solution of several linear programs referred as the assignment problem in graph theory, for which efficient numerical algorithms exist. The optimal schedule, that is, the optimal value of the 2N possible transmit-receive configuration states for the relays, is investigated and known results for diamond networks are extended to general relay networks. It is shown, for the case of N=2 relays, that only N+1=3 out of the 2N=4 possible states have a strictly positive probability and suffice to characterize the capacity to within a constant gap. Extensive experimental results show that, for a general N -relay network with N\leq 8 , the optimal schedule has at most N+1 states with a strictly positive probability. As an extension of a conjecture presented for diamond networks, it is conjectured that this result holds for any half-duplex relay network and any number of relays. Finally, a network with N=2 relays is studied in detail to illustrate the channel conditions under which selecting the best relay is not optimal, and to highlight the nature of the rate gain due to multiple relays.

AB - This paper considers a Gaussian relay network where a source transmits a message to a destination with the help of N half-duplex relays. The information theoretic cut-set upper bound to the capacity is shown to be achieved to within 1.96(N+2) bits by noisy network coding, thereby reducing the previously known gap. This gap is obtained as a special case of a more general constant gap result for Gaussian half-duplex multicast networks. It is then shown that the generalized degrees-of-freedom of this network is the solution of a linear program, where the coefficients of the linear inequality constraints are proved to be the solution of several linear programs referred as the assignment problem in graph theory, for which efficient numerical algorithms exist. The optimal schedule, that is, the optimal value of the 2N possible transmit-receive configuration states for the relays, is investigated and known results for diamond networks are extended to general relay networks. It is shown, for the case of N=2 relays, that only N+1=3 out of the 2N=4 possible states have a strictly positive probability and suffice to characterize the capacity to within a constant gap. Extensive experimental results show that, for a general N -relay network with N\leq 8 , the optimal schedule has at most N+1 states with a strictly positive probability. As an extension of a conjecture presented for diamond networks, it is conjectured that this result holds for any half-duplex relay network and any number of relays. Finally, a network with N=2 relays is studied in detail to illustrate the channel conditions under which selecting the best relay is not optimal, and to highlight the nature of the rate gain due to multiple relays.

KW - Assignment problem

KW - capacity to within a constant gap

KW - generalized degrees-of-freedom

KW - half-duplex

KW - inner bound

KW - outer bound

KW - relay networks

KW - weighted bipartite matching problem

UR - http://www.scopus.com/inward/record.url?scp=84901268005&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84901268005&partnerID=8YFLogxK

U2 - 10.1109/TIT.2014.2314636

DO - 10.1109/TIT.2014.2314636

M3 - Article

AN - SCOPUS:84901268005

SN - 0018-9448

VL - 60

SP - 3559

EP - 3575

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 6

M1 - 6803066

ER -