Tuning Up the Performance of Constant-Time Distributed Scheduling Algorithms via Majorization

Scheduling algorithms assign contention probability for each link in wireless ad hoc networks and plays a key role in deciding the system performance. Recently, many low-cost distributed scheduling algorithms are proposed. In this paper, we propose to improve the performance of a class of distributed collision-based scheduling algorithms, called constant-time distributed scheduling algorithms, by exploring the advantage brought by the unevenness of links´ contention probabilities. Specifically, we prove that there exists ordering relationship for the success probability of any neighborhood when the contention probability vectors are ordered in the sense of majorization. We show how to modify the existing algorithms so as to find a new contention probability vector that majorizes the original one in a distributed manner. Our simulation results indicate that by using our modified algorithms, the average queue-lengths of a stable system can be reduced by 25% to 50%, while the capacity region remains the same. Our modification to the existing algorithms is extremely simple and entails essentially zero additional cost.