On Optimal Dynamic Scheduling for Sum-Queue Minimization in Trees
The authors investigate the problem of minimizing the sum of the queues of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root (sink). They consider a time-slotted system, and a primary interference model. They first consider the case where the root has only one child while the rest of the tree is arbitrary, and provide a causal sample-path delay optimal scheduling policy, i.e., at each time slot, for any traffic arrival pattern, the sum of the queues of all the nodes is minimum among all policies. They are able to fully characterize tree structures for which such policies exist.