摘要
在无线传感器网络中,能量效率问题至关重要,构造精简的虚拟骨干网可以节约有限资源,这等同于在图论中求解最小连通支配集(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.
出处
《传感器与微系统》
CSCD
2015年第1期145-147,共3页
Transducer and Microsystem Technologies
关键词
无线传感器网络
最小连通支配集
极大独立集
网络生命周期
wireless sensor networks （ WSNs ）
minimum connected dominating set （ MCDS ）
maximum independent set（MIS）
lifetime of network
