Simple schedules for half-duplex networks

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)