Delay-optimal buffered decode-and-forward for two-hop networks with random link connectivity

Delay-optimal control of multi-hop networks remains a challenging problem even in the simplest scenarios. In this paper, we consider delay-optimal control of a two-hop half-duplex network with i.i.d. on-off fading. Both the source node and the relay node are equipped with infinite buffers and have exogenous bit arrivals. We focus on delay-optimal link selection to minimize the average bit delay subject to a half-duplex constraint. To solve the problem, we introduce a new approach whereby an actual discrete time system (ADTS) is approximated using a virtual continuous time system (VCTS). Using dynamic programming, we recursively solve the delay minimization problem in the VCTS in terms of a simpler prototype problem, which can be addressed using continuous-time optimal control techniques. We show that the obtained solution in the VCTS is asymptotically optimal in the ADTS. Our solution has a closed-form expression and does not require knowledge of the arrival statistics. Finally, using renewal theory and the theory of random walks, we analyze the average delay resulting from the asymptotically optimal solution.