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

摘要 提出两个基于二跳独立邻居覆盖的无线传感器网络极小连通支配集构造算法.在两个构造算法中，已选择的支配节点推举新的支配节点，并要求新推举的支配节点完全覆盖该支配节点的二跳独立邻居节点.第一个算法不考虑能量因子，以被推举节点的一跳和部分二跳独立邻居节点集合大小之和最大作为新支配节点推举依据；第二个算法以被推举节点剩余能量与其覆盖的二跳独立邻居节点个数之商最大化作为推举依据.所提出的算法具有较好的时间复杂度和消息复杂度，且均为O（n），第一个算法的性能比为O（n1／2）.仿真结果表明，本文提出的算法可构造较小规模的连通支配集以及延长网络生命时间.