DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks
DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks
复制标题
DOI：
10.1145/1132905.1132927
复制
发表时间：
2006-05
影响因子：
7.9
通讯作者：
I. Rhee;A. Warrier;J. Min;Lisong Xu
中科院分区：
文献类型：
--
作者：
I. Rhee;A. Warrier;J. Min;Lisong Xu
本文提出了一种分布式实现的兰德，随机时隙调度算法，称为DRAND。DRAND运行在O（delta）时间和消息复杂度，其中delta是无线网络中两跳邻域的最大大小，而消息复杂度保持O（delta），假设消息延迟可以由未知常数限制。DRAND是兰德的第一个完全分布式版本。该算法适用于大多数节点不移动的无线网络，如无线网状网络和无线传感器网络。我们在TinyOS中实现了该算法，并在Mica2节点的真实的测试床中展示了其性能。该算法不需要任何时间同步，并且可以有效地适应局部拓扑变化，而不会在调度中产生全局开销。由于这些特征，它甚至还可以用于其它调度问题，例如频率或码调度（对于FDMA或CDMA）或用于不强制时间同步的无线网络的本地标识符分配。我们进一步评估了无线链路的时变性质对DRAD分配时隙的无冲突属性的影响。该实验是在由最新的MicaZ传感器节点组成的55个节点测试床上进行的。
This paper presents a distributed implementation of RAND, a randomized time slot scheduling algorithm, called DRAND. DRAND runs in O(delta) time and message complexity where delta is the maximum size of a two-hop neighborhood in a wireless network while message complexity remains O(delta), assuming that message delays can be bounded by an unknown constant. DRAND is the first fully distributed version of RAND. The algorithm is suitable for a wireless network where most nodes do not move, such as wireless mesh networks and wireless sensor networks. We implement the algorithm in TinyOS and demonstrate its performance in a real testbed of Mica2 nodes. The algorithm does not require any time synchronization and is shown to be effective in adapting to local topology changes without incurring global overhead in the scheduling. Because of these features, it can also be used even for other scheduling problems such as frequency or code scheduling (for FDMA or CDMA) or local identifier assignment for wireless networks where time synchronization is not enforced. We further evaluate the effect of the time-varying nature of wireless links on the conflict-free property of DRAND-assigned time slots. This experiment is conducted on a 55-node testbed consisting of the more recent MicaZ sensor nodes.