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

A RANDOMIZED DISTRIBUTED ALGORITHM FOR TOTAL SCHEDULING PROBLEM

作　　者：肖岚[1] 闫桂英[1] 任伟[1] 李旭[2] 

机构地区：[1]中国科学院数学与系统科学研究院,北京100190 [2]北京交通大学,北京100044

出　　处：《系统科学与数学》2008年第11期1331-1336,共6页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(10531070，10721101)和(60674009)资助课题．

摘　　要：无线网络中的全调度，要确保网络中每个节点所可能的链路信息和广播信息都能无冲突地进行传输．通过简单的构造方法，证明了多项式时间内，能找到一个长度为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.

关 键 词：无线网络 链路调度 广播调度 全调度 随机分布式算法. 

分 类 号：TN92[电子电信—通信与信息系统]