无线网络中全调度问题的一种随机分布式算法

A RANDOMIZED DISTRIBUTED ALGORITHM FOR TOTAL SCHEDULING PROBLEM

无线网络中的全调度，要确保网络中每个节点所可能的链路信息和广播信息都能无冲突地进行传输．通过简单的构造方法，证明了多项式时间内，能找到一个长度为O（△^2out △in）的全调度；并且给出了全调度问题的一种随机分布式算法，证明了这种随机分布式算法，对任意的常数h，0〈h〈1，能以1-h的概率，得到一长度为O（△in △^out Inn/h）的全调度．

In multihop radio network, total scheduling occurs when stations communicate one-to-one and broadcast simultaneously. In this paper, a global upper bound for total scheduling is proved by a simple construction method. A randomized distributed algorithm is also presented.