基于域的分布式最小连通支配集的启发式算法

摘要

在规模较大且移动较频繁的ad hoc网络中,针对构建树形连通支配集缓慢且网络开销大的问题,提出了基于域的分布式最小连通支配集的启发式算法(ZBCDS).ZBCDS在求得极大独立集的基础上,定义了节点阶势和候选节点的概念,通过判断节点的阶势,优化了域的生成和域边界上连接节点的调整,达到CDS重构快速高效地实现的目的.实验结果表明,ZBCDS算法能高效且快速的构建最小连通支配集,且比同类算法生成的连通支配集更小,时间复杂度有所降低.%With regard to the problem of slow progress and high overhead, when constructing a tree-like CDS in a fast-moving ad hoc networks, this paper puts forward a Zone-based distributed heuristic approximation algorithm for minimum connected dominating set(ZBCDS). ZBCDS defines the concept of potential-rank and candidate nodes, on the basis of calculating maximal independent set, optimizes the zone partition and the adjustment along the zone borders via nodes judging their own potential-rank, finally reaches the aim of rapidly and efficiently reconstructing CDS as topology change. Experimental results show that ZBCDS can rapidly and efficiently construct CDS, with smaller size of CDS and less time complexity.