基于二跳独立邻居覆盖的极小连通支配集构造算法  

Minimum Connected Dominating Set Construction Algorithms Based on Two-hop Independent Neighbor Covered

作　　者：汤强[1,2] 谢明中 罗元盛[1,2] 李平[1,2] 

机构地区：[1]长沙理工大学综合交通运输大数据智能处理湖南省重点实验室,长沙410114 [2]长沙理工大学计算机与通信工程学院,长沙410114

出　　处：《小型微型计算机系统》2016年第6期1245-1249,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61303043)资助;湖南省自然科学基金项目(13JJ4052)资助;湖南省教育厅资助科研项目(13C1022)资助;湖南省教育厅资助科研项目(13C1023)资助;湖南省教育厅重点项目(14A004)资助

摘　　要：提出两个基于二跳独立邻居覆盖的无线传感器网络极小连通支配集构造算法.在两个构造算法中,已选择的支配节点推举新的支配节点,并要求新推举的支配节点完全覆盖该支配节点的二跳独立邻居节点.第一个算法不考虑能量因子,以被推举节点的一跳和部分二跳独立邻居节点集合大小之和最大作为新支配节点推举依据;第二个算法以被推举节点剩余能量与其覆盖的二跳独立邻居节点个数之商最大化作为推举依据.所提出的算法具有较好的时间复杂度和消息复杂度,且均为O(n),第一个算法的性能比为O(n^(1/2)).仿真结果表明,本文提出的算法可构造较小规模的连通支配集以及延长网络生命时间.A Minimum Connected Dominating Set（ MCDS ） construction algorithm based on the two-hop independent neighbor set covered is proposed in this paper for wireless sensor networks. In the two algorithms,the newly selected dominators are required to cover the two-hop independent neighbor nodes of the dominators which select the newly selected dominators. The first algorithm se- lects the node as the dominator which has the maximum weight calculated by the sum of the size of the one-hop independent neighbor set and the size of part of the two-hop independent neighbor set. The second algorithm selects the node as the dominator which covers the two-hop independent neighbor nodes and has the maximum weight calculated by the divide of the residual energy and the covered two-hop independent neighbor. The proposed algorithms have good time and message complexity, which are both O （ n^1/2）, and the first algorithm＇s performance ratio is O（ n^1/2 ）. The simulation results show that the algorithms proposed in this paper can construct MCDS with small size and prolong the network lifetime.

关 键 词：二跳独立邻居覆盖 极小连通支配集 能量有效 启发式算法 无线传感器网络 

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