Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks
Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks
复制标题
DOI：
10.1145/1062689.1062709
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
Theodoros Salonidis;L. Tassiulas
中科院分区：
文献类型：
--
作者：
Theodoros Salonidis;L. Tassiulas
我们提出了一个框架，在无线ad hoc网络中提供确定性的端到端的带宽保证。在一组本地可行性条件的指导下，多跳会话被动态地提供分配，进一步转化为链路需求。使用分布式时分多址（TDMA）协议，节点通过本地的、无冲突的时隙重新分配来适应其相邻链路上的需求变化。一旦需求变化稳定，节点必须逐渐收敛到实现全球链路的TDMA调度（和届会）需求分配.我们首先推导出足够的局部可行性条件，某些拓扑类，并表明树可以最大限度地利用.然后，我们介绍了一个收敛的分布式链路调度算法，利用逻辑树结构，出现在几个ad hoc网络应用.解耦从链路调度到多跳会话的带宽分配允许支持各种端到端服务质量（QoS）目标。我们专注于最大最小公平性（MMF）的目标，并设计了一个端到端的异步分布式算法的会话MMF率的计算。一旦端到端的算法收敛，链路调度算法收敛到一个TDMA调度，实现这些rates.We证明了这个框架的适用性，通过现有的无线技术的实现。这种实现方式是免费的限制性假设以前的TDMA方法：它不需要任何先验知识的网络中的节点的数量，甚至网络范围的时隙同步。
We present a 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 Time Division Multiple Access (TDMA) protocol nodes adapt to the demand changes on their adjacent links by local, conflict-free slot reassignments. As soon as the demand changes stabilize, the nodes must incrementally converge to a TDMA schedule that realizes the global link (and session) demand allocation.We first derive sufficient local feasibility conditions for certain topology classes and show that trees can be maximally utilized.We then introduce a converging distributed link scheduling algorithm that exploits the logical tree structure that arises in several ad hoc network applications.Decoupling bandwidth allocation to multi-hop sessions from link scheduling allows support of various end-to-end Quality of Service (QoS) objectives. We focus on the max-min fairness (MMF) objective and design an end-to-end asynchronous distributed algorithm for the computation of the session MMF rates. Once the end-to-end algorithm converges, the link scheduling algorithm converges to a TDMA schedule that realizes these rates.We demonstrate the applicability of this framework through an implementation over an existing wireless technology. This implementation is free of 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.