Low Complexity Stable Link Scheduling for Maximizing Throughput in Multihop Wireless Networks

This paper presents novel distributed algorithms for scheduling trans-missions in multi-hop wireless networks. Our algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. Two classes of algorithms are designed: one assumes known location information of all wireless nodes, and the other does not. Both classes of algorithms are parameterized by an integer k (called algorithm-k). We show that algorithm-k of our class that uses geometry location achieves (1 − 2/k)2 of the ca-pacity region, for every k ≥ 3; algorithm-k of our class that did not use geometry location achieves 1/ρ of the capacity region, for every k ≥ 3 and a constant ρ depending on k. Our algorithms have small worst-case overheads. Both classes of algorithms can gener-ate a new schedule by requiring communications within Θ(k) hops for every node. The parameter k explicitly captures some tradeoffs between control overhead and the throughput performance of any scheduler. Additionally, the class of algorithms with known geom-etry location of nodes can find a new schedule in time Θ(k2∆), where ∆ is the minimum mini-time-slots such that each of the n nodes can communicate with its neighbors once, which is clearly the minimum time-slots required by any scheduling algorithm. 1