On Sample-Path Optimal Dynamic Scheduling for Sum-Queue Minimization in Trees Under the K-Hop Interference Model
The authors investigate the problem of minimizing the sum of the queue lengths 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 K-hop interference model. They characterize the existence of causal sample-path optimal scheduling policies in these networks, i.e., they wish to find a policy such that at each time slot, for any traffic arrival pattern, the sum of the queue lengths of all the nodes is minimum among all policies. They provide an algorithm that takes any tree and K as inputs, and outputs whether a causal sample-path optimal policy exists for this tree under the K-hop interference model.