Distributed Throughput-Optimal Scheduling in Ad Hoc Wireless Networks
In this paper, the authors propose a distributed throughput optimal ad hoc wireless network scheduling algorithm, which is motivated by the celebrated simplex algorithm for solving Linear Programming (LP) problems. The scheduler stores a sparse set of basic schedules, and chooses the max-weight basic schedule for transmission in each time slot. At the same time, the scheduler tries to update the set of basic schedules by searching for a new basic schedule in a throughput increasing direction. The authors show that both of the above procedures can be achieved in a distributed manner.