Wireless packet scheduling based on the cumulative distribution function of user transmission rates

In this paper, we present a new wireless scheduling algorithm based on the cumulative distribution function (cdf) and its simple modification that limits the maximum starving time. This cdf-based scheduling (CS) algorithm selects the user for transmission based on the cdf of user rates, in such a way that the user whose rate is high enough, but least probable to become higher, is selected first. We prove that the CS algorithm is equivalent to a scheduling algorithm that regards the user rates as independent and identically distributed, and the average throughput of a user is independent of the probability distribution of other users. So, we can evaluate the exact user throughput only if we know the user's own distribution, which is a distinctive feature of this proposed algorithm. In addition, we try a modification on the CS algorithm to limit the maximum starving time, and prove that the modification does not affect the average interservice time. This CS with starving-time limitation (CS-STL) algorithm turns out to limit the maximum starving time at the cost of a negligible throughput loss.