Constant-Time Distributed Scheduling Policies for Ad Hoc Wireless Networks

We propose two new distributed scheduling policies for ad hoc wireless networks that can achieve provable capacity regions. Known scheduling policies that guarantee comparable capacity regions are either centralized or need computation time that increases with the size of the network. In contrast, the unique feature of the proposed distributed scheduling policies is that they are constant-time policies, i.e., the time needed for computing a schedule is independent of the network size. Hence, they can be easily deployed in large networks