Structure of optimal schedules in diamond networks

Siddhartha Brahma, Christina Fragouli
Ieee, 2014
Article de conférence

Résumé

We consider Gaussian diamond networks with n half-duplex relays. At any point of time, a relay can either be in a listening (L) or transmitting (T) state. The capacity of such networks can be approximated to within a constant gap (independent of channel SNRs) by solving a linear program that optimizes over the 2(n) relaying states. We recently conjectured, and proved for the cases of n = 2, 3, that there exist optimal schedules with at most n+1 active states, instead of the possible 2(n). In this paper we develop a computational proof strategy that relies on submodularity properties of information flow across cuts in the network and linear programming duality to resolve the conjecture. We implement the strategy for n = 4, 5, 6 and show that indeed there exist optimal schedules with at most n+1 active states in these cases (1).

Official source

https://infoscience.epfl.ch/record/207180?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

, ,

We consider an n-relay Gaussian diamond network where a source communicates to a destination with the help of n half-duplex relays. Achieving rates close to the capacity of this network requires to employ all the n relays under an optimal transmit/receive schedule. Even for the moderate values of n, this can have significant operational complexity as the optimal schedule may possibly have 2(n) different states for the network (since each of the relays can be in either transmitting or receiving mode). In this paper, we investigate whether a significant fraction of the network capacity can be achieved by using transmit/receive schedules that have only few active states and by using only few relays. First, we conjecture that the approximately optimal schedule has at most n+1 states instead of the 2(n) possible states. We prove this conjecture for networks of size n

Ieee-Inst Electrical Electronics Engineers Inc2016

Chargement

Simple Relaying Strategies for Half-duplex Networks

Siddhartha Brahma, Christina Fragouli, Ayfer Özgür Aydin

We consider the diamond network where a source communicates with the destination through N non-interfering half-duplex relays. Using simple outer bounds on the capacity of the network, we show that simple relaying strategies having exactly two states and avoiding broadcast and multiple access communication can still achieve a significant constant fraction of the capacity of the 2 relay network, independent of the SNR values. The results are extended to the case of 3 relays for the special class of antisymmetric networks. We also study the structure of (approximately) optimal relaying strategies for such networks. Simulations show that optimal schedules have at most N + 1 states, which we conjecture to be true in general. We prove the conjecture for N = 2 and in special cases for N = 3.

2012

Chargement

Simple schedules for half-duplex networks

Siddhartha Brahma, Christina Fragouli

We consider the diamond network where a source communicates with the destination through N non-interfering half-duplex relays. Deriving a simple approximation to the capacity of the network, we show that simple schedules having exactly two states and avoiding broadcast and multiple access communication can still achieve a significant constant fraction of the capacity of the 2 relay network, independent of the channel SNRs. The results are extended to the case of 3 relays for the special class of antisymmetric networks. We also study the structure of (approximately) optimal relaying strategies for such networks. Simulations show that these schedules have at most N + 1 states, which we conjecture to be true in general. We prove the conjecture for N = 2 and for special cases for N = 3.(1)

Ieee2012

Chargement