On the optimality of simple schedules for networks with multiple half-duplex relays

Cardone, Martina; Tuninetti, Daniela; Knopp, Raymond
IEEE Transactions on Information Theory, Vol.62, N°7, July 2016

This paper studies networks that consist of N half-duplex relays assisting the communication between a source and a destination. In ISIT'12 Brahma, Özgür and Frago uli conjectured that in Gaussian half-duplex diamond networks (i.e., without a direct link between the source and the destination, and with N non-interfering relays) an approximately optimal relay scheduling policy (i.e., achieving the cut-set upper bound to within a constant gap uniformly over all channel gains) has at most N + 1 active states (i.e., at most N + 1 out of the 2N possible relay listen-transmit configurations have a
strictly positive probability). Such relay scheduling policies were referred to as simple. In ITW'13 the authors of this paper conjectured that simple approximately optimal relay scheduling policies exist for any Gaussian half-duplex multi-relay network irrespectively of the topology. This paper formally proves this more general version of the conjecture and shows it holds beyond Gaussian noise networks. In particular, for any memoryless half-duplex N-relay network with independent noises and for which independent inputs are approximately optimal in the cut-set upper bound, an approximately optimal simple relay scheduling policy exists. The key step of the proof is to write the minimum of the submodular cut-set function by means of its Lov´asz extension and use the greedy algorithm for
submodular polyhedra to highlight structural properties of the optimal solution. This, together with the saddle-point property of min-max problems and the existence of optimal basic feasible solutions

Systèmes de Communication
Eurecom Ref:
© 2016 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

PERMALINK : https://www.eurecom.fr/publication/4507