Distributed Link Scheduling for TDMA Mesh Networks

We present a distributed scheduling algorithm for provisioning of guaranteed link bandwidths in ad hoc mesh networks. The guaranteed link bandwidths are necessary to provide deterministic end-to-end bandwidth guarantees. Using Time Division Multiple Access (TDMA), links are assigned slots in each frame and during each slot a number of non-conflicting links can transmit simultaneously. The bandwidth of each link is given by the number of slots assigned to it the frame and the modulation used in the slots. Our scheduling algorithm has two parts. The first part of the algorithm is an iterative procedure that finds locally feasible schedules by exchanging link scheduling information between nodes. The iterative procedure is based on the distributed Bellman-Ford algorithm running on the conflict graph, whose partial view is available at every node. The second part of the algorithm is a wave based termination procedure used to detect when all nodes are locally scheduled and a new schedule should be activated. We use analysis to show the worst case convergence time of the algorithm and simulations to show performance of the algorithm in practice.