Stability of Spatial Wireless Systems with Random Admissible-Set Scheduling

We examine the stability of wireless networks whose users are distributed over a torus. Users arrive at spatially uniform locations with intensity l and each user has a random number of packets to transmit with mean b. In each time slot, an admissible subset of users is selected uniformly at random to transmit one packet. A subset of users is called admissible when their simultaneous activity obeys the prevailing interference constraints. We consider the SINR model and the protocol model as two canonical models for interference, and denote by m the maximum number of users in an admissible subset for the model under consideration. We show that the necessary condition l*b<m is also sufficient for random admissible-set scheduling to achieve stability. Thus random admissible-set scheduling achieves stability, if feasible to do so at all, for a wide range of interference scenarios. The proof relies on a description of the system as a measure-valued process and the identification of a Lyapunov function.