A Framework for Topology-Transparent Scheduling in Wireless Networks

Transmission scheduling is a key design problem in wireless multi-hop networks. Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time division multiple access (TDMA) frame length. There exists some interesting scheduling algorithms called topology-transparent TDMA scheduling algorithms, which do not require the detailed topology information, and are suitable for the wireless environment. However, a framework to compare the performance of these algorithms properly and fairly is still lacking. The objective of this work is to propose a uniform framework for topology-transparent scheduling algorithms. Under some fundamental constraints, an optimal solution is provided to the scheduling problem of topology-transparent algorithms. Furthermore, under the proposed framework, we analyze the relationship among all existing topology-transparent algorithms. We then develop an adaptive topology-transparent algorithm, which can always give an optimal solution under a set of the system design parameters.