Date Added: Apr 2011
In this paper, the authors investigate the optimal dynamic packet scheduling policy in a Wireless Relay Network (WRN). They model this network by two sets of parallel queues that represent the Subscriber Stations (SS) and the Relay Stations (RS), with random link connectivity. An optimal policy minimizes, in stochastic ordering sense, the process of cost function of the SS and RS queue sizes. They prove that, in a system with symmetrical connectivity and arrival distributions, a policy that tries to balance the lengths of all the system queues, at every time slot, is optimal. They use stochastic dominance and coupling arguments in their proof. They also provide a low-overhead algorithm for optimal policy implementation.