摘要
针对传感器网络最大独立集的构造方法中并行构造算法生成的连通支配集尺寸没有明确的上界且难以确定边界节点的问题,在串行最大独立集构造算法的基础上,提出了基于权重和时序的触发式连通支配集构造算法.仿真结果表明:该算法无需构造生成树,降低了计算时延和通信开销;此外,由于最大独立集节点存在时间上的先后关系,因而使得边界节点的数量显著减少,最终求得的连通支配集存在明确的上界.
In the constructing algorithms of sensor networks MIS （maximum independent set）, the parallel-algorithm would construct a CDS （connected dominating set） with uncertain upper-limit size and edge nodes. In this case, based upon serial MIS constructing algorithm, a weight and timing based triggering CDS constructing algorithm was presented. The presented algorithm need not con- struct spanning tree, thus reduces the computation delay and communication overhead. Meanwhile, the nodes orderly join the MIS one after another in the algorithm, thus it greatly reduces the number of edge nodes, and builds a CDS with certain upper-limit.
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2011年第3期61-65,共5页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
关键词
无线传感器网络
最大独立集
连通支配集
通信复杂度
计算复杂度
wireless sensor networks
maximum independent set （MIS）
connected dominating set （CDS）
communication complexity
computation complexity
