Queue Length Stability in Trees Under Slowly Convergent Traffic Using Sequential Maximal Scheduling

In this paper, we consider queue-length stability in wireless networks under a general class of arrival processes that only requires that the empirical average converges to the actual average polynomially fast. We present a scheduling policy, sequential maximal scheduling, and use novel proof techniques to show that it attains 2/3 of the maximum stability region in tree-graphs under primary interference constraints, for all such arrival processes. For degree bounded networks, the computation time of the policy varies as the the logarithm of the network size. Our results are a significant improvement over previous results that attain only 1/2 of the maximum throughput region even for graphs that have a simple path topology, in similar computation time under stronger (i.e., Markovian) assumptions on the arrival process