| Abstract | : | In this work, we design distributed link scheduling algorithms for large adhoc networks. We model the interference in the adhoc network using a graph, and the set of independent sets of the graph constitute the interference-free schedules. Under this setting, we propose two classes of scheduling algorithms that generate interference-free schedules by appropriately sampling the independent sets: (i) Gibbs sampling based schedulers (ii) Greedy sampling based schedulers. The Gibbs sampling based algorithms with appropriately chosen potentials maximize the throughput, and are suited for networks with high data-rate requirements. However, the problem of computing these potentials is NP-hard. One of our key contributions is to propose an free energy approximations based framework to learn the potentials of the Gibbs distribution. Greedy sampling based algorithms offer a good trade off between the throughput and the delay, and are suited for delay-sensitive applications. In particular, we prove that they support a constant fraction of the maximum throughput with a constant delay. Further, the parameters of these greedy algorithms can be easily computed unlike the Gibbs sampling based algorithms. |
