TY - JOUR

T1 - Network Simplification in Half-Duplex

T2 - Building on Submodularity

AU - Ezzeldin, Yahya H.

AU - Cardone, Martina

AU - Fragouli, Christina

AU - Tuninetti, Daniela

N1 - Publisher Copyright:
© 1963-2012 IEEE.

PY - 2019/10

Y1 - 2019/10

N2 - This paper explores the network simplification problem in the context of Gaussian half-duplex diamond networks. Specifically, given an N -relay diamond network, this problem seeks to derive fundamental guarantees on the capacity of the best k -relay subnetwork, as a function of the full network capacity. Simplification guarantees are presented in terms of a particular approximate capacity, termed Independent-Gaussian (IG) approximate capacity, that characterizes the network capacity to within an additive gap, which is independent of the channel coefficients and operating SNR. The main focus of this work is when k\!=\!N\!-\!1 relays are selected out of N relays in a diamond network. First, a simple algorithm is proposed which selects all relays except the one with the minimum IG approximate half-duplex capacity. It is shown that the selected (N\!-\!1) -relay subnetwork has an IG approximate half-duplex capacity that is at least 1/2 of the IG approximate half-duplex capacity of the full network and that for the proposed algorithm, this guarantee is tight. Furthermore, this work proves the following tight fundamental guarantee: there always exists a subnetwork of k\!=\!N\!-\!1 relays that have an IG approximate half-duplex capacity that is at least equal to (N-1)/N of the IG approximate half-duplex capacity of the full network. Finally, these results are extended to derive lower bounds on the fraction guarantee when k \in [1:N] relays are selected. The key steps in the proofs lie in the derivation of properties of submodular functions, which provide a combinatorial handle on the network simplification problem for Gaussian half-duplex diamond networks.

AB - This paper explores the network simplification problem in the context of Gaussian half-duplex diamond networks. Specifically, given an N -relay diamond network, this problem seeks to derive fundamental guarantees on the capacity of the best k -relay subnetwork, as a function of the full network capacity. Simplification guarantees are presented in terms of a particular approximate capacity, termed Independent-Gaussian (IG) approximate capacity, that characterizes the network capacity to within an additive gap, which is independent of the channel coefficients and operating SNR. The main focus of this work is when k\!=\!N\!-\!1 relays are selected out of N relays in a diamond network. First, a simple algorithm is proposed which selects all relays except the one with the minimum IG approximate half-duplex capacity. It is shown that the selected (N\!-\!1) -relay subnetwork has an IG approximate half-duplex capacity that is at least 1/2 of the IG approximate half-duplex capacity of the full network and that for the proposed algorithm, this guarantee is tight. Furthermore, this work proves the following tight fundamental guarantee: there always exists a subnetwork of k\!=\!N\!-\!1 relays that have an IG approximate half-duplex capacity that is at least equal to (N-1)/N of the IG approximate half-duplex capacity of the full network. Finally, these results are extended to derive lower bounds on the fraction guarantee when k \in [1:N] relays are selected. The key steps in the proofs lie in the derivation of properties of submodular functions, which provide a combinatorial handle on the network simplification problem for Gaussian half-duplex diamond networks.

KW - Half-duplex relay networks

KW - approximate capacity

KW - relay scheduling

KW - relay selection

KW - submodularity

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

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

U2 - 10.1109/TIT.2019.2923994

DO - 10.1109/TIT.2019.2923994

M3 - Article

AN - SCOPUS:85077398730

SN - 0018-9448

VL - 65

SP - 6801

EP - 6818

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 10

M1 - 8742589

ER -