Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks

Abstract

We present a novel framework for the provision of deterministic end-to-end bandwidth guarantees in wireless ad hoc networks. Guided by a set of local feasibility conditions, multi-hop sessions are dynamically offered allocations, further translated to link demands. Using a distributed TDMA protocol, nodes adapt to the demand changes on their adjacent links by local, conflict-free slot reassignments. As soon as the changes stabilize, the nodes must incrementally converge to a TDMA schedule that realizes the global link (and session) demand allocation. We first identify an inherent trade-off between the degree of topology control and fraction of feasible allocations that can be captured by the local conditions. We show that tree topologies can be maximally utilized in this respect and that a converging distributed link scheduling algorithm exists in this case. Decoupling end-to-end bandwidth allocation from link scheduling allows support of various end-to-end QoS objectives. Focusing on Available Bit Rate (ABR) service, we design an asynchronous distributed algorithm for sharing bandwidth to the sessions in a maxmin fair (MMF) manner. Finally, we present the implementation of this framework over Bluetooth, an existing wireless technology that enables the formation of ad hoc networks. This implementation is free of the usual restrictive assumptions of previous TDMA approaches: it does not require any a-priori knowledge on the number of nodes in the network nor even network-wide slot synchronization.