On the Complexity of Scheduling in Half-Duplex Diamond Networks

Siddhartha Brahma, Christina Fragouli, Ayfer ÖzgürIEEE Trans. Information Theory 2016 · OpenReview

Abstract

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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> possible states. We prove this conjecture for networks of size n ≤ 6 by developing a proof strategy and implementing it computationally. Second, we show that routing strategies that only employ the point-to-point communication and two of the relays with a half-duplex schedule that has only two active states can achieve at least half the capacity (approximately) of the network. Techniques from linear programming and submodular functions are used to derive the results.
BibTeX
@article{brahma2016complexity,
  author = {Siddhartha Brahma and Christina Fragouli and Ayfer Özgür},
  title = {{On the Complexity of Scheduling in Half-Duplex Diamond Networks}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  url = {https://openreview.net/forum?id=PtEdqMSi2iS},
}

Loading related content...

Figure