Delay minimization for random scheduling in centralized wireless networks

We consider a centralized network scheme, where all nodes communicate with a base station (BS). The communication happens in a time slotted fashion and the BS has multi-packet reception capability. Assuming that the success probability of transmissions is always 1 (perfect reception), we prove a lower bound on the delay performance for arbitrary policy. We then study the imperfect reception case in which the success probability of transmissions is not always 1. A convex optimization problem is proposed, which can minimize the upper bound on the expected delay of random scheduling (RS). An approximation and a lower bound on the delay of RS are also developed for the case in which the BS can support simultaneous transmission of up to two users. We implement a recently proposed algorithm that separates multiple simultaneous transmissions in a blind fashion, and show that the approximated delays and the delay bounds match the simulation results very well.