求解圆盘图中最小连通支配集的近似算法  

Approximation algorithm for minimum connected dominating set in unit disk graphs

作　　者：赵学锋[1] 

机构地区：[1]西北师范大学数学与信息科学学院,兰州730070

出　　处：《计算机应用》2011年第7期1962-1965,共4页journal of Computer Applications

基　　金：甘肃省科技攻关项目(2GS035-A052-011)

摘　　要：针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。Minimum Connected Dominating Set（MCDS） problem is a classical optimization issue in the design of wireless networks.For the construction of MCDS in the Unit Disk Graph（UDG） to model wireless sensor networks,an efficient approximation algorithm,DDT,was proposed based on distributed greedy strategy.In each round,it repeatedly selected a node to link a determined node according to weights and state information among one-hop neighborhood,and finally,found a dominating tree for the graph.The maximum node degree in the dominating tree was studied using probabilistic method.By analyzing the relationship between the size of the maximal independent set and the minimum connected dominating set,the algorithm produced a new approximation ratio.The experimental results show the superiority of the DDT algorithm over other existing distributed algorithms in terms of the CDS size.

关 键 词：最小连通支配集 极大独立集 近似算法 支配树 单位圆盘图 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]