We consider the problem of packet access in wireless data networks. The maximum ergodic packet arrival rate is shown to be NP-hard. We give a spectral bound on the maximum ergodic throughput in terms of the path-gain matrix. We present simple heuristic packet access schemes that exhibit good behavior on preliminary simulations. We also give more sophisticated algorithms that yield optimal throughput. Our algorithms generalize to other scheduling problems under stochastic arrivals. In particular, we obtain a recent result of McKeown, Anantharam and Walrand on scheduling of input-queued switches as a byproduct.
[Based on joint work with Paul Wright]