一种参考能量的最小连通支配集近似算法  

A reference energy approximation algorithm for minimum connected dominating set

作　　者：赵煜[1] 降爱莲[1] 

机构地区：[1]太原理工大学计算机科学与技术学院,山西太原030024

出　　处：《传感器与微系统》2015年第1期145-147,共3页Transducer and Microsystem Technologies

摘　　要：在无线传感器网络中,能量效率问题至关重要,构造精简的虚拟骨干网可以节约有限资源,这等同于在图论中求解最小连通支配集(MCDS)问题。由此,提出一种构造MCDS的启发式算法。首先根据均值公式为顶点建立次序表,其次构造极大独立集(MIS),再次连接MIS节点,最后优化。仿真实验表明:该算法能够在短时间内找到规模较小的连通支配集(CDS),并且有效地均衡了各节点能量,延长了网络生命周期。To make efficient use of limited energy resources is significant in WSNs, a major way to save limited energy resources is constructing a smaller virtual backbone, which is equivalent to find the minimum connected dominating set（MCDS） in graph theory. Thus, a heuristic Mgorithm to construct the MCDS is proposed. Firstly, according to average formula, establish ordered list for vertex, then construct the maximum independent set（ MIS）, and then connect nodes of MIS, finally, optimize CDS. Simulation experiments show that the algorithm can find smaller connected dominating set in short time, and effectively balances energy of each node to extend lifetime of network.

关 键 词：无线传感器网络 最小连通支配集 极大独立集 网络生命周期 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]