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

赵 煜，降爱莲

(太原理工大学 计算机科学与技术学院，山西 太原030024)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)广泛应用在很多重点领域，如国防、环境监测、工农业控制等，具有较高的应用价值。传感器节点由电池供电，电量有限，能量一旦耗尽将不能继续正常工作，所以，在保证网络连通的前提下，如何能够更有效地提高能量使用效率，延长系统生命周期，是目前亟待解决的重要问题。

在无线传感器网络中，广播操作通常使用“泛洪(flooding)”来完成，经过分析表明［1］，“泛洪”可能会带来广播风暴问题。在保证覆盖和连通的前提下，使用连通支配集(CDS)算法可以构造一个临时转发数据的骨干网络。只有网络中的骨干节点负责转发数据，而那些非骨干节点在不发送数据时，可关闭通信模块以节省能量。为了使网络寿命最大化，需要构造一个最小连通支配集(MCDS)的骨干网络。然而，求解一个网络图的MCDS 是一个NP 难题［2］，目前还没有成熟算法，因此，需要设计一种高效的近似算法来求解网络图的MCDS。

1 现有算法描述

目前求解MCDS 的方法主要有两种:一是先找出一个CDS，然后逐步对进行CDS 优化，减少其顶点总数从而得到MCDS［3，4］;二是先找出一个极大独立集(MIS)，再寻找连接点，将MIS 中的顶点连接起来最终得到MCDS［5，6］。

文献［7］利用分布式算法Leader Election 构建一棵有根树，接着找到MIS，最后在此基础上求解CDS。在文献［7］的基础上，文献［8，9］分别对连接MIS 的顶点方式和构造MIS 的方式做出了改进。

文献［6］在文献［8，9］的基础上，提出首先通过BFS 建立一棵有根树，获得顶点的等级和优先次序表，再次凭借优先次序表得到MIS，最后找到连接点将MIS 中的节点连接起来形成MCDS。文献［10］在文献［6］启发下，考虑了能量问题，但是需要连续两个算法才能降低能耗，稍显复杂。

本文在参考以上文献基础上，提出一种参考能量的MCDS 高效近似算法。本算法既可以得到一个MCDS，还可以均衡整个网络的能耗，有效延长生命周期。

2 CDS 相关术语

2.1 CDS 基本概念

定义1 (独立集):G=(V，E)是简单无向图，S⊆V 且，若S 中任何两个顶点都不相邻，则称S 为G 的独立集。如果在S 中再添加任何节点vi∈V，且vi∉S，都不再是G 的独立集，则S 为G 的MIS。

定义2 (支配集):在简单连通无向图G=(V，E)中，有S⊂V 且S≠∅，对于∀vi∈V，若vi∉S，则vi至少与S 中的一个顶点相邻，称S 为G 的一个支配集(DS)。若支配集S 中的顶点数最少，则称S 为G 的MDS;若支配集S 的生成子图是连通的，则S 为一个CDS，若连通支配集S 中的顶点数最少，则称S 为G 的MCDS。图1、图2 所示分别为图G的MDS，MCDS。

图1 顶点{3，6，7}为MDSFig 1 Vertex{3，6，7}as MDS

图2 顶点{4，5，7}为MCDSFig 2 Vertex{4，5，7}as MCDS

2.2 相关定义及其说明

Value 的定义:对图中任意一个节点 u，定义Value(u)=(weight(u)，id(u))，其中，weight(u)为节点u的度与剩余能量的权值，id(u)为节点U 的编号。对于任意两个节点A，B，若Value(A)＞ Value(B)，当且仅当weight(A)＞weight(B)。

表1 中所列符号为文中需要的重要符号。

3 构造参考能量的MCDS 算法

本文设计的求解最小连通支配集算法分为以下若干步骤:1)构造一个以顶点的度和剩余能量值的权值为判断值的顶点优先次序表;2)根据得出的顶点优先次序表构造MIS;3)根据MIS 中顶点的邻接点集合和顶点优先次序表找到连接点，构成连通支配集;4)对CDS 进行优化，最终得到MCDS。

表1 符号说明Tab 1 Symbol description

接下来将对以上步骤进行详细阐述。

3.1 构造顶点优点次序表

1)全网各节点首先广播Hello 信令，节点在接收到Hello 信令后，各节点计算得到自身的度degree(u)，邻接点集合N(u)以及邻居节点剩余能量值energy(u)。计算节点的度与剩余能量的均值公式(1)为

式中 du为节点u 的度，n 为网络节点总数，Eu为节点u的当前剩余能量，Emax为节点u 及其邻居节点中剩余能量的最大值，α 为权重因子。

2)计算全网每一个节点的Value 值，并根据Value 值从大到小对节点进行排序，将节点相对应的ID 保存到节点优先次序表L 的表项li中。

通过上述步骤可知，在全网中优先选择连通度大、剩余能量更多的节点作为CDS 节点，增强了CDS 节点选择的针对性，并且，由于MCDS 组成的骨干网络节点在信息转发时会消耗更多的能量，所以，考虑了节点的剩余能量，使网络能量保持动态平衡。

3.2 构造MIS

1)设置全网节点为未标号，表示节点未遍历。

2)根据L 中的优先级顺序由高到低依次对各节点进行标记，L 中第一个节点li标记为Black，并将其ID 加入到M 的表项m1中。

3)从L 中第二个节点l2起，若N(li)中没有任何一个节点标记为Black，则将节点ID 加入到M 的表项mj中;否则，i=i+1。

4)若L 中全部节点均已遍历完毕，则算法结束;否则，转至步骤(3)。

3.3 连接MIS

1)将M 中的节点赋予集合C;

2)遍历M 中各节点及其邻接点集合N(u)，根据顶点优先次序表L，将N(u)中节点优先级最高的一个节点加入到集合C 中。得到的集合C 即为CDS，算法结束。

3.4 构造MCDS

构造的CDS 中可能有冗余节点，将按以下步骤进行优化得到较小的MCDS:

1)删除集合C 中所有度为1 的节点;

2)遍历集合C 中各节点的邻接点集合N(u)中的每一个节点v，若在N(v)中都可以找到除节点u 以外的集合C中的任意一个节点，则在集合C 中将节点u 删除，并更新相应的集合;优化后的集合C 即为MCDS，算法结束。

4 算法仿真与性能分析

本文利用Matlab 仿真平台来考察本算法的性能，仿真环境设为200 m×200 m 的正四边形区域，随机投放一定数量的节点传感器，均具有相同的通信半径，α=0.1，节点剩余能量在［0.8Emax，Emax］范围内随机取值(Emax=1)。为保证仿真结果可靠性，每次仿真实验运行50 次，取仿真结果平均值。实验用参数为网络覆盖范围为200 m×200 m;节点个数为100～500 个;通信半径为20～45 m。

第一组实验是计算网络节点数目为300 时，不同通信半径条件下各算法得到的MCDS 平均大小，结果如图3 所示。

图3 不同通信半径对应的MCDS 平均大小Fig 3 Average size of MCDS according to different communication radius

第二组实验是计算节点发送半径r 为30 m 时，分布不同传感器节点数目条件下各算法得到的MCDS 的平均大小，结果如图4 所示。

图4 不同传感器节点数目对应的MCDS 平均大小Fig 4 Average size of MCDS according to different number of sensor nodes

从上图中可以看出:在不同通信半径和分布不同节点数量条件下，本文提出的算法所找到的MCDS 较其他两个都小，具有较好的性能。

第三组实验比较随机产生的500 个节点在不同算法作用下，其平均能量随时间的变化，结果如图5 所示。

图5 节点平均能量变化趋势Fig 5 Change trend of average energy of nodes

5 结 论

本文设计出一种参考能量的求解MCDS 的近似算法，经过实验仿真结果证明:本算法在减小CDS 规模和延长网络生命周期方面是有效的，为延长无线传感器使用寿命创造了条件。

［1］ Tseng Y，Ni S，Chen Y，et al.The broadcast storm problem in a mobile Ad－Hoc network［J］.Wireless Networks，2002，8(2/3):153－167.

［2］ Gao S，Vu C T，Li Y S.Sensor scheduling for k－coverage in wireless sensor networks［C］∥Proc of the MSN，2006:268－280.

［3］ 卞永钊，于海斌，曾 鹏.无线传感器网络中一种启发式最小连通支配集算法［J］.信息与控制，2009，38(3):193－199.

［4］ Ravi Prakash.A routing algorithm for wireless Ad Hoc networks with unidirectional links［J］.Wireless Networks，2001，7:617－625.

［5］ 孙 超，尹荣荣，郝晓辰，等.WSNs 中基于能量代价的最小权和支配集拓扑控制算法［J］.电子与信息学报，2010，32(4):857－863.

［6］ 廖飞雄，马 良，范炳全.一种求解最小连通支配集的高效近似算法［J］.小型微型计算机系统，2008，29(5):875－878.

［7］ Alzoubi K M，Wan P J，Freider O.Distributed heuristics for connected dominating set in wireless Ad Hoc networks［J］.IEEE Com Soc/KICS Journal on Communication Networks，2002，4(1):22－29.

［8］ Han Bo，Fu Haohuan，Lin Lidong，et al.Efficient construction of connected dominating set in wireless Ad Hoc networks［C］∥2004 IEEE International Conference on Mobile Ad－Hoc and Sensor Systems，2004:570－572.

［9］ Gao Bo，Yang Yuhang，Ma Huiye.A new distributed approximation algorithm for constructing minimum connected dominating set in wireless Ad Hoc networks［C］∥Proceedings of the Second International Symposium on Parallel and Distributed Processing and Applications，ISPA 2004，Hong Kong，China，2004:3358.

［10］黄行波，程红举.无线传感器网络中使用连通支配集的最小能耗广播算法［J］.小型微型计算机系统，2014(1):74－79.