On the Optimality of Simple Schedules for Networks with Multiple Half-Duplex Relays

Martina Cardone, Daniela Tuninetti, Raymond Knopp

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

This paper studies networks that consist of N half-duplex relays assisting the communication between a source and a destination. In ISIT'12 Brahma et al. 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, we 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 class of memoryless half-duplex N-relay networks 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ász 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 for linear programs, proves the conjecture. As an example, for N-relay Gaussian networks with independent noises, where each node is equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most N+1 active states, irrespectively of the total number of antennas in the system, is proved.

Original languageEnglish (US)
Article number7469879
Pages (from-to)4020-4034
Number of pages15
JournalIEEE Transactions on Information Theory
Volume62
Issue number7
DOIs
StatePublished - Jul 2016

Fingerprint

scheduling
Scheduling
Antennas
Structural properties
Diamonds
Topology
Communication
communication

Keywords

  • Approximate capacity
  • half-duplex networks
  • linear programming
  • relay scheduling policies
  • submodular functions

Cite this

On the Optimality of Simple Schedules for Networks with Multiple Half-Duplex Relays. / Cardone, Martina; Tuninetti, Daniela; Knopp, Raymond.

In: IEEE Transactions on Information Theory, Vol. 62, No. 7, 7469879, 07.2016, p. 4020-4034.

Research output: Contribution to journalArticle

@article{f0dd51908a4f490e9aa9d78ce50d2b83,
title = "On the Optimality of Simple Schedules for Networks with Multiple Half-Duplex Relays",
abstract = "This paper studies networks that consist of N half-duplex relays assisting the communication between a source and a destination. In ISIT'12 Brahma et al. 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, we 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 class of memoryless half-duplex N-relay networks 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{\'a}sz 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 for linear programs, proves the conjecture. As an example, for N-relay Gaussian networks with independent noises, where each node is equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most N+1 active states, irrespectively of the total number of antennas in the system, is proved.",
keywords = "Approximate capacity, half-duplex networks, linear programming, relay scheduling policies, submodular functions",
author = "Martina Cardone and Daniela Tuninetti and Raymond Knopp",
year = "2016",
month = "7",
doi = "10.1109/TIT.2016.2568918",
language = "English (US)",
volume = "62",
pages = "4020--4034",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE",
number = "7",

}

TY - JOUR

T1 - On the Optimality of Simple Schedules for Networks with Multiple Half-Duplex Relays

AU - Cardone, Martina

AU - Tuninetti, Daniela

AU - Knopp, Raymond

PY - 2016/7

Y1 - 2016/7

N2 - This paper studies networks that consist of N half-duplex relays assisting the communication between a source and a destination. In ISIT'12 Brahma et al. 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, we 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 class of memoryless half-duplex N-relay networks 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ász 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 for linear programs, proves the conjecture. As an example, for N-relay Gaussian networks with independent noises, where each node is equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most N+1 active states, irrespectively of the total number of antennas in the system, is proved.

AB - This paper studies networks that consist of N half-duplex relays assisting the communication between a source and a destination. In ISIT'12 Brahma et al. 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, we 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 class of memoryless half-duplex N-relay networks 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ász 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 for linear programs, proves the conjecture. As an example, for N-relay Gaussian networks with independent noises, where each node is equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most N+1 active states, irrespectively of the total number of antennas in the system, is proved.

KW - Approximate capacity

KW - half-duplex networks

KW - linear programming

KW - relay scheduling policies

KW - submodular functions

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

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

U2 - 10.1109/TIT.2016.2568918

DO - 10.1109/TIT.2016.2568918

M3 - Article

AN - SCOPUS:84976603293

VL - 62

SP - 4020

EP - 4034

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 7

M1 - 7469879

ER -