基于连通支配集的WSN自适应数据调度算法

孔凡凤，欧红玉，龙林德，陈 曦

（1.湖南邮电职业技术学院移动通信系，长沙 410115；2.长沙理工大学计算机与通信工程学院，长沙 410114）

基于连通支配集的WSN自适应数据调度算法

孔凡凤1，欧红玉1，龙林德1，陈 曦2

（1.湖南邮电职业技术学院移动通信系，长沙 410115；2.长沙理工大学计算机与通信工程学院，长沙 410114）

在无线传感器网络中通过构建连通支配集来组成虚拟的骨干，使网络数据的收集变得层次化，更可以防止节点的死亡造成数据链的断裂，然而最小的连通支配集不能均衡各节点的能量消耗，导致部分节点过早死亡。为此，基于连通支配集的无线传感器网络，提出一种自适应的数据调度算法，通过选择能量和度比较大的节点组成支配集，支配集组成较高能量的网络骨干，数据经过自适应的调度沿着较小规模的网络骨干寻找路由直到发给基站。实验结果表明，该算法在较小的网络规模中具有容错性，可以减少能量消耗并延长网络生命周期。

无线传感器网络；虚拟骨干；连通支配集；数据调度；能量消耗；生命周期

DO I：10.3969/j.issn.1000-3428.2015.10.018

1 概述

现在无线传感器网络的应用越来越普遍，网络的构成都是由若干传感器节点通过自组织完成组网。但是，网络中的节点数量比较多，各个节点的数据汇聚到汇聚节点过程中，会有大量重叠，对于能量有限的无线传感器节点来说会造成信息冗余、能量浪费，影响了信息的实时操作［1］。针对这一问题，人们提出并研究各种数据调度技术，即通过建立更加高效、灵活、健壮的连通支配集减少通信过程中的能量消耗，延长网络生命周期［2］。

所谓连通支配集就是构造k-连通和m-支配的支配集作虚拟的骨干网，k-连通是集合中任2个支配节点至少存在k条路径，即使k-1条路径断开，

仍然能实现骨干网数据的连通。m-支配是指任一个被支配节点至少与m个支配节点连接。通过这个虚拟的骨干网让无线传感器网络的网络构造规模变小，减少节点间数据通信的次数［3］。

之前不少研究人员提出了一些基于连通支配集的算法。在CDS-BD-D［4］算法中，SINK通过单跳或者多跳给区域内的节点发送消息，节点接收到消息后根据跳数可以计算出距离SINK的距离。在算法初始，节点首先根据度的大小决定是否成为支配节点，度比邻居节点的大则首先成为支配节点，同时此支配节点比其他支配节点距SINK更近，则此节点发送一个connect消息，然后根据此消息改为支配节点，依次类推，最后形成以SINK为根的连通支配集。mr-CDS算法［5］根据能量的大小决定是不是连通支配集，能量高的首先成为支配节点，并向邻居节点广播消息，此时非支配节点可以获知邻居中支配节点的数量并把此消息广播出去，这样邻居也可以得到2跳的支配节点，然后搜索可以连通的路径，如果还没有通路就自己变为支配节点。但是非支配节点在自主变为支配节点时没有考虑能量因素，这样会造成较多的支配节点和过多的连通集。LDA［6］算法采用CDS-BD-D构造一个1-连通、m-支配的连通支配集。每个支配节点根据邻居信息构造一个局部k节点连通子图。最后每个支配节点通知该子图中的非支配节点加入连通支配集。

本文提出一种基于连通支配集的无线传感器自适应数据调度算法（Adaptive data Scheduling algorithm Based on Connected Dominating Set，ASCDS），通过选择能量和权值较大的节点为支配节点并形成连通支配集，非支配节点首先找到归属的支配节点，然后通过自适应的调度算法进行数据收集。在此算法中所有的数据在小范围内沿着虚拟骨干节点寻找转发路由，能节省能量，防止节点的早死亡。ASCDS算法通过生成小规模的连通支配集，防止节点的失效造成数据链的断裂，完成更多轮的数据传递。

2 系统模型及问题描述

2.1 连通支配集的模型

构成的连通支配集需能量消耗均衡，所以应该具有以下2个特点：（1）构造的支配集应尽可能小，这样数据可以更好地进行融合并传输，避免干扰和冲突造成能量浪费［7］。（2）构造的连通支配集应具有较高的能量水平，以延长网络的生命周期，也就是要求支配集中的汇聚节点应该有较高的能量水平。但是这是一个NP问题，如果要均衡以上2点，定义权值Wi=EiDegreei，让权重的节点优先成为骨干，其中，Degreei是邻居数量，定义为节点的度［8］。

2.2 连通支配集构造描述

在无线传感器网络，基站的数量较少，所以构建连通支配集网络很适合这一能量受限的网络环境：（1）连通支配集本身的优点有助于节省能量消耗；（2）支配集是由能量高但是度不一定大的节点组成，这样构成的连通支配集的规模比较大［9］。本文从延长网络生命周期和能量均衡来构造分布式的连通支配集。

定义 一个传感器网络G=（V，E），其中，V表示节点集合，有n个节点随机分布在一个L×L的区域内，设定SINK位于区域的中心［10］，每个节点的传输半径均为r。每个节点都具有权值Wi，color，ID属性，并有一个与邻居关系的LIST列表。

2.2.1 身份阶段

第1个阶段ASCDS算法节点身份确认，网络中节点跟邻居比较，权值最大者为支配节点，如果最大权值相同，则比较ID号，ID号小者成为支配节点，过程如图1所示，黑色的表示支配节点，灰色表示非支配节点，白色表示没有加入任何支配集。

图1 连通支配集形成过程

对该阶段的描述如下：

（1）对于所有的νi∈V，初始化参数color（νi）= white。

（2）任意一个节点跟邻居的权值做比较，如果Wi＞WNeigh，则color（νi）=black，如果（Wi=Wj）＞WNeigh，则根据ID号决定，如果IDi＜IDj，νi成为支配节点。此时 color（νi）=black，并广播消息参数dominator（νi）告知自己的邻居。

（3）当节点νj收到从νi来的dominator（νj）消息后，νi查看自己的color值，如果color（νi）=white，则color（νi）=gray，并发布广播dominator（νi）消息到周围邻居。

（4）如果节点νi接收到一个从νj的dominator（νj）消息，如果color（νi）=white，说明此节点还没有加入任何一个支配集。首先νi是否能成为支配节点，先把νj从νi的邻居集里面删除，然后跟其他邻居比较，如果Wi＞WNeigh，则νi成为支配节点，或者Wi＞WNeigh且IDi＜IDNeigh，则 νi也成为支配节点，此时节点color（νi）=black，并发送dominator（νi）通知邻居。2.2.2 支配集形成阶段

第2阶段ASCDS算法连通支配集形成过程，根据能量均衡及邻居与其他支配节点连接情况，产生连通支配集，如图1（d）所示。描述如下：

（1）如果color（νi）=gray，则νi为向相邻的支配节点νk广播消息Mesg1（νi，νk），让νi的邻居知道νk的存在。

（2）如果节点νi接收到广播消息Mesg（νj，νk），则νi要查看自身的color属性。

如果color（νi）=gray，则说明νi的邻居里面至少有一个1跳的νm，而且2跳的邻居里面还有一个νk。如果IDm＜IDk，则νi广播一个Mesg2（νi，νj，νk），这里要求IDm＜IDk是因为ASCDS算法规定由ID号小的节点决定是否与其ID号大的节点连通，如果νm决定建立连接，则建立了νm→νi→νj→νk的路径。

如果color（νi）=black，且IDi＜IDk，则由νi决定是否与νk连通，如果满足条件，则建立νi→νj→νk的路径。

现在建立了νi通过νj到νk的路径，但是并不知道有没有其他更优的数据收集路径。因此，先把路径［νj，νk］置于列表List1中，如果存在了到νk的路径［νl，νk］（这里νl可以是一个也可以是多个），则比较νl和νj的权值大小，如果Wl＜Wj，则将［νl，νk］删除并增加［νj，νk］，相反，则不增加［νl，νk］。 如果节点νi第一次接收到Mesg1和Mesg2消息，则启动定时器Timer，等待Δ秒，这Δ秒能保证接收到其他邻居节点发来的Mesg1和Mesg2消息。

（3）如果节点 νi接收到一个Mesg2（νn，νj，νk），首先查看自己的 color属性。如果 color（νi）= black，则νi决定是否与2跳之外的νk进行连通。为了实现节点的能量均衡，延长节点生命周期，νi会先把路径νn→νj→νk存入列表List2中。如果存在其他通往νk的路径νr→νs→νk，并且（Wr+Ws）＜（Wn+ Wj），则删除路径 νr→νs→νk，并增加路径 νn→νj→νk。如果节点νi第一次接收到Mesg2消息，则启动定时器Timer，等待Δ秒，这Δ秒能保证接收到其他邻居节点发来的Mesg1和Mesg2消息。

（4）当定时器Timer结束后，节点 νi要根据List1和List2去确定最后的连通路径。

对于表List1中记录的每条路径［νl，νk］，将 νl加入到集合 F中，由于存在路径［νl，νk］，则可以删除表List2中的［νn，νj，νk］。

对于表List2中的每条记录［νn，νj，νk］，将νn，νj加入集合F中。最后将F放入消息connector（F，2）中并广播出去，数字2表示会广播2次，每被转发一次减1，这说明 νi的2跳记录都可以收到此消息。如果νi收到消息connector（F，a），首先a减1，如果νi属于F，并且color（νj）=gray，则color（νj）= black。如果a≥1，则继续广播connector（F，a）。

3 数据融合调度过程

数据融合调度的最终目的是为节点分配时隙，本文主要的调度过程依据服务概率去确定每个时隙中的通信链路集合。在其他研究人员提出的算法中，基本上采用的是每个链路只调度一次的原则［11］，这种方法让权重数高得无法优先调度，但是又不能无限制调度，如何调整通信次数是实现能量均衡和延长生命周期的关键参数。

调度步骤如下：

（1）链路的权重集合为W=｛w1，w2，…，wn｝，调度集为Tree，阈值为δ，初始化SCH=Ø，t=1，标记所有链路未调度。

（2）没有被调度的链路 νi，如果 νi属于连通支配集中的非边沿链路，且权重大于δ，则激活为 t时刻的链路集合［12］。

（3）构造链路的冲突矩阵CM，构造以CM为邻接矩阵的最大独立集。

（4）对于所有不在连通支配集中的激活链路，根据自适应的概率计算器，即节点的权重参数动态调整各节点的服务概率。假设第i个节点的权重 wi，可以与邻居节点形成矩阵并构成近似的最大加权独立集，则根据服务概率把此节点变成调度节点。

（5）如果Tree中尚存在没有被调度的链路，则

t=t+1，转到步骤（2）。

（6）返回融合周期每个时隙的传输链路集合SCHE=｛e1，e2，…，et｝，如图2所示。

图2 不同时隙内链路的选取

此调度方法执行后，有：

（1）所有被采集数据被汇聚到SINK节点；

（2）E（1）∪E（2）∪…∪E（t）=E︵；

（3）对于E（s）（1≤s≤t），若ei，ej∈E（s），则必有ei和ej相互不冲突。

4 仿真结果与性能比较

为了证明ASCDS算法的性能，采用Matlab7.0软件进行仿真。仿真环境如下：在一个100 m×100 m的正方形区域内，SINK位于区域的中心，N个节点随机分布在区域中，如表1所示。通过设置不同个数的节点、不同半径的观察节点的支配连通情况，选择与m r-CDS做比较，实验结果来自于20次仿真结果。

表1 仿真参数设置

4.1 分簇仿真

在节点数为100的平台上分别仿真ASCDS算法和mr-CDS算法，设置节点的通信半径为20 m，观察生成的连通支配集情况，实验结果仿真如图3所示。在图3中，加号代表连通支配集里面的节点，而圆圈代表支配节点，中心的叉号代表基站。

图3 ASCDS算法和mr-CDS算法分簇对比

从图3中可以看出，ASCDS算法的构建覆盖了所有节点连通支配集，集合中支配节点为11个，比mr-CDS产生的包含14个支配节点的连通支配集的规模要小，因为mr-CDS在连通过程中，连接节点是由非支配节点决定的，从而造成了支配节点间可以存在多个连接节点，而ASCDS算法的连接节点是由ID较小的支配节点决定，它会选择能量较大的节点担任连接节点，而非支配节点就可以节省能量做其他工作。

4.2 生成连通支配集时消耗的能量

在100 m×100 m区域内分别设置n=100，200，300和400的节点，计算在生成连通支配集时消耗能量的平均值。其中，节点的通信半径分别为r=20 m和r=30 m，实验结果如图4所示。从图中可以看出，节点增加的同时，2种算法消耗的能量均呈递增趋势，因为随着节点数量的增多，需要接收邻居节点发来的消息也增多，网络规模增大，消耗的能量随之增加。但是也可以从图中看出因为生成的支配集要小，所以ASCDS算法比mr-CDS算法消耗的能量要小，节点的能量可以提供更多轮数据的收集。

图4 生成连通支配集的能耗比

从图4可以看出，节点增加的同时，2种算法消耗的能量均呈递增趋势，因为随着节点数量的增多，需要接收邻居节点发来的消息也增多，网络规模增大，消耗的能量随之增加。但是也可以从图中看出，因为生成的支配集要小，所以ASCDS算法比mr-CDS算法消耗的能量要小，节点的能量可以提供更多轮数据的收集。

4.3 网络生命周期对比

无线传感器网络因为能量有限，所以用尽可能有限的能量完成更多轮数据的收集是WSN网络重要的一部分。

当前阶段有很多算法先将节点构成连通支配集，然后构成融合树，最终把数据送到SINK节点。本文算法数据收集采用的是基于近似最大独立集的自适应数据调度算法，而mr-CDS采用的是距离向量DV算法［13］。

从图5可以看出，不同网络条件下，ASCDS算法比mr-CDS算法的生命周期长，这是因为ASCDS算法在构建网络时考虑了能量和节点度的关系，在数据调度时通过自适应的调度最大加权独立集降低时延，通过调节参数来限制发送次数，实现数据融合和能量消耗的性能平衡。可见，ASCDS能减少能量消耗，能有效延长网络生命周期。然而，ASCDS构造的支配集属于 1-连通、2-支配的支配集，因此ASCDS在可靠性方面的性能仍有待提高。ASCDS与相关算法的性能对比如表2所示。

图5 网络生命周期对比

表2 不同算法的性能对比

5 结束语

本文提出基于连通支配集的自适应数据调度算法，根据节点的能量值和度得出自身权值，该值大于邻居节点时则成为支配节点，在连通时则ID小的支配节点决定担任连接节点。在数据调度时采用基于近似最大独立集的自适应算法。实验分析结果表明，该算法比已有的算法网络形成的规模更小，消耗更少的能量，从而获得较长的网络生命周期。在真实的环境中设计能耗低同时可靠性高的数据调度算法是接下来的研究方向。

［1］ 于广州.WSN中面向数据收集的网络拓扑构造算法［J］.计算机工程，2014，40（4）：64-70.

［2］ 郑 婵，孙世新，黄天云.Ad Hoc网络和无线传感器网络中连通支配集的分布式构造［J］.软件学报，2011，22（5）：1053-1066.

［3］ 赵学锋.基于 GSO算法的最小连通支配集问题求解［J］.计算机工程，2013，39（2）：99-102.

［4］ Kim Donghyun，Wu Yiwei，Li Yingshu，et al. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20（2）：147-157. ［5］ Hussain S，Shafique M H，Yang L T.Constructing a CDS-based Network Backbone for Energy Efficiency in Industrial Wireless Sensor Network［C］//Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications.Washington D.C.，USA：IEEE Press，2010：322-328.

［6］ Wu Yiwei，Li Yingshu.Construction Algorithms for kconnected m-dominating Sets in Wireless Sensor Networks［C］//Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA：ACM Press，2008：83-90.

［7］ 李 辉，刘书吉.基于节点度和距离的WSN分簇路由算法［J］.计算机工程，2014，40（3）：114-119.

［8］ 奎晓燕，杜华坤，梁俊斌.无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法［J］.电子学报，2013，41（8）：1521-1528.

［9］ 郑 婵，尹 令，孙世新.无线传感器网络中2-连通k-支配的容错连通支配集构造［J］.控制与决策，2013，28（5）：650-656.

［10］ 刘文彬，李香宝，付 沙，等.无线传感器网络中的改进数据聚集调度算法［J］.计算机工程，2014，40（1）：93-97.

［11］ 郜 帅，张宏科.时延受限传感器网络移动Sink路径选择方法研究［J］.电子学报，2011，39（4）：742-747.

［12］ 许 建，杨 庚，陈正宇，等.基于二次独立集的数据融合调度算法［J］.通信学报，2014，35（1）：62-71.

［13］ Malhotra R.IP Routing［M］.［S.l.］：O’Reilly Media，Inc.，2002.

编辑 顾逸斐

Adaptive Data Scheduling Algorithm in WSN Based on Connected Dominating Set

KONG Fanfeng1，OU Hongyu1，LONG Linde1，CHEN Xi2
（1.Department of Mobile Communication，Hunan Post and Telecommunication College，Changsha 410115，China；2.School of Computer and Communication Engineering，Changsha University of Science&Technology，Changsha 410114，China）

In Wireless Sensor Network（WSN）constructing connected dominating set based virtual backbone，help to optimize multi-level hierarchical networks，which prevents the node’s death caused by the death of the data link. However，the minimum connected dominating set can not balance the energy consumptions to premature death.This paper presents an adaptive data gathering algorithm in WSN based on connected dominating set.Connected set by selecting the node has high energy and large degree from a dominating set which forms higher energy network backbone.Data through adaptive scheduling along the smaller network backbone seek route until the base station.Simulation results show that the proposed algorithm has a good performance with fault-tolerant in smaller network size，reduces the energy consumption and prolongs the network life cycle.

Wireless Sensor Network（WSN）；virtual backbone；connected dominating set；data scheduling；energy consumption；life cycle

孔凡凤，欧红玉，龙林德，等.基于连通支配集的 WSN自适应数据调度算法［J］.计算机工程，2015，41（10）：94-98，104.

英文引用格式：Kong Fanfeng，Ou Hongyu，Long Linde，et al.Adaptive Data Scheduling Algorithm in WSN Based on Connected Dominating Set［J］.Computer Engineering，2015，41（10）：94-98，104.

1000-3428（2015）10-0094-05

A

TP301.6

国家自然科学基金青年基金资助项目（61303043）。

孔凡凤（1979-），女，硕士，主研方向：无线传感器网络；欧红玉、龙林德，讲师；陈 曦，教授。

2014-09-16

2014-11-11E-m ail：maomaokff@163.com