Energy Balanced and Fault Tolerant Data Gathering Algorithmfor Heterogeneous Wireless Sensor Network*

YANG Mingxia，WANG Wanliang，MA Chenming（1.College of Electrical and Information Engineering，Quzhou University，Quzhou Zhejiang 34000，China；.College of Information，Zhejiang University of Technology，Hangzhou 31003，China）



Energy Balanced and Fault Tolerant Data Gathering Algorithm
for Heterogeneous Wireless Sensor Network*

YANG Mingxia1，2，WANG Wanliang2*，MA Chenming2
（1.College of Electrical and Information Engineering，Quzhou University，Quzhou Zhejiang 324000，China；2.College of Information，Zhejiang University of Technology，Hangzhou 310023，China）

Virtual backbone based on connected dominating setcan prolong the lifetime of wireless sensor network. However，the network also needs to have a certain degree of fault tolerance due to characteristicsof the nodes that are prone to failure.In view of the problem that the fault tolerant methods of k-connected m-dominated set consume too much energy，a distributed data gathering algorithm for energy-saving and fault-tolerance is proposed in the new⁃ly heterogeneous network mode.The algorithm firstly construct connected dominating set，then select better degree of fault tolerance nodes as backup nodes，and finally balance the energy consumption of the dominated nodes in the data gathering process.Theoretical analysisand simulation experimentsconfirm that our algorithm not only can con⁃struct connected dominating set with low time and message overhead，but also ensure the fault tolerance and extend the network lifetime finally.

heterogeneous wireless sensornetwork；connected dominating set；data gathering；fault tolerant；load balance

随着物联网技术的快速发展，数据已经成为社会发展的核心内容。作为末端采集系统，无线传感器网络（Wireless Sensor Networks，WSNs）可以实现物理世界与信息世界的有效融合。资源受限导致传感器网络在部署规模和运行时间等方面存在大量难题和挑战。利用节点的空间冗余性，可利用网络中部分节点工作来节省能耗，这类方法最典型的做法是拓扑控制，通过优化网络的拓扑结构，使得网络中节点的能耗均衡，延长网络生命时间。

其中，基于虚拟骨干的拓扑控制方法［1-4］通过求解一个确保网络连通的连通支配集，覆盖网络中所有其它非骨干节点，目标函数是减少工作节点规模。采用连通支配集作为虚拟骨干可以有效减少活跃节点数和路由开销，同时对于节点的管理和维护也更加容易，是一种有效的节能方法。但是，在实际环境中可能会出现节点死亡和链路错误等问题。

本文主要从节能和容错两个方面对无线传感器网络的能量节省问题进行研究，针对异构网络模型研究分布式容错数据收集算法，通过对活跃节点产生备份集的方法来生成容错拓扑，减少处于工作的支配节点数，从而节省网络能量，维持网络的稳定性。

1　相关研究工作

虚拟骨干网可以利用图论中求解最小连通支配集（Minimum Connected Dominating Set，MCDS）问题的方法来构建。现有算法可以分为减少能耗和保证高可靠性。

EBCDS［5］通过选择能量水平和度均比较大的节点组成连通支配集，支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干。网络中的所有数据沿骨干在较小的寻路空间中转发，能够节省节点能量。但是，EBCDS在连通节点的过程，将三跳邻域中所有的节点均进行了连通且没有考虑剪枝等操作，导致产生的连通支配集规模较大，同时算法的消息复杂度也较高。

以上算法没有考虑节点能耗速率产生的影响，网络的生命由能量最先耗尽的节点决定，它主要受到初始能量和能耗速率的影响。

在保证网络可靠性方面，文献［6］提出的CDSA算法通过选择中间节点合并（1，1）-CDS中叶子块的个数，最终使所有活跃节点在同一个块中。文献［7］将问题扩展到了任意k，m的取值，但是算法求解比较困难。k-CDS［8］将节点的参数Domi和Total分别初始化为k和所有邻居节点Domi之和。算法通过消息交互获得邻居节点的Total，Total最大的节点成为支配节点并通知邻居节点；邻居节点收到消息后将Domi减1，然后通知其他节点对Total更新；如果节点的Domi等于0成为普通节点。反复执行上述过程，这样形成的节点集是k支配的。然后，利用块-割点图将m-支配集2-连通。

DDA［9］首先构建（1，m）-CDS，然后从指定节点开始构建初始k连通分支。分支上的所有节点广播KC消息，邻居Black节点收到消息后对路径进行确认，如果至少存在k条可行路径，则广播AC消息；否则，发送RC请求k连通路径。当白色节点收到RC时，检查自己是否存在k条连通路径，如果存在回复CS消息给发送者，然后广播KC消息成为Black节点；否则，将ID添加到请求列表中并向邻居节点转发RC请求。算法在最坏情况下需要收集网络中所有节点的消息，时间和消息复杂度分别达到了O（n1.6）和O（n2）。

文献［10］提出了一种生成候选节点的方法来分流工作负载过重的支配节点，尽管这只是针对能耗问题进行研究，但是这种思想仍然值得借鉴。文献［11］采用类似思想，提出了以生成备份节点为主导的算法AFTC。AFTC对节点的容错度进行研究，然后选择容错度高的节点构建网络并生成备份节点集，相比（k，m）-CDS，该方法产生的活跃节点规模更小。但是，算法在实现中需要获得每个节点的位置信息，而节点通常并不配备GPS等具有定位功能的昂贵设备，而且算法构建的消息开销也过大，同时没有对容错算法的连通性的必要条件提供理论证明。

此外，现有拓扑控制方法主要集中在同构网络中，文献［12-13］针对异构网络展开研究。文献［12］在异构网络中提出了分布式拓扑控制算法A3M，拓扑构建基于最小连通支配集构建虚拟骨干树，拓扑维护对网络性能进行评估。而文献［13］基于反向连通支配集树，改进了节点的适应度函数和算法流程，提出了一种低信息复杂度的分布式拓扑构建算法A3GMLM，优化了产生的连通支配集的规模和通信开销。

本文主要在参考文献［11-13］的基础上，考虑数据收集过程节点的能耗速率的影响，提出了一种容错数据收集算法EBFT（Energy Balanced and Fault Tolerant），在节省网络能量基础上保证数据收集质量。

2　算法描述

数据收集过程由连通支配集的构建、数据传输和拓扑维护组成。为了节约能量，普通节点在大部分时间将关闭通信模块，仅仅周期性向支配节点发送采集的数据，而活跃节点负责接收并融合其他节点发送的数据。假设邻域内不同节点产生的数据具有部分相关性，不同节点的数据可以完全汇聚为一个大小固定的数据包，然后通过路由最终到达Sink。当网络出现异常时，恢复、轮换或再生成拓扑。本文所采用的网络模型与数据模型均基于文献［12］。

2.1相关定义

定义1节点的权值

结合节点的异构性，算法优先选择能量多、采集能力强、邻居节点多、通信半径大、距离上层骨干节点距离远和故障少的节点作为支配节点，节点的权值定义如下：

式（1）第1部分表示计时时段内节点被选为支配节点的影响因子，分母为节点单位时间消耗的能量值；第2部分可以在选举支配节点时使用相对邻居节点个数，原因是算法在初始化时需要通过两轮的消息交换获得邻居节点的邻居列表消息；第4项表明了节点的距离覆盖利用效率（距离近的节点不要一起工作）；而式（1）的第5部分ω5p（μ）是当前节点失效的概率，p（μ）代表了正常工作的期望概率。。

定义2节点的容错度

在备份节点的选择中需要对节点的容错属性进行分析，如果当前节点与活跃节点的性能越相似，那么使用当前节点进行替代后就可以覆盖更多节点，定义式（2）表示节点的容错度：

这里与式（1）不同的主要在第3部分，如果两个节点的邻居节点个数越多那么该节点作为后备节点就可以覆盖尽可能多的其他节点，这样就能更好地维护网络的容错性，减少活跃节点数。

2.2构建连通支配集

本节算法在文献［12］中拓扑构建算法的基础上进行改进，在节点通信半径存在异构的网络环境中进一步优化了消息开销。本文只需要一次信息交换，具体方法如下：在节点上存储通信半径Ru并在Hello消息中依据接受到的信号强度RSSI计算距离信息，当节点u收到了节点v发送的Hello消息时，节点通过RSSI可以获得u，v之间的距离d（u，v），若Ru≥d（u，v）即表示节点之间可以通信。本文在此基础上增加节点容错度、邻居列表信息等参数，在异构网络中每个节点只需要发送两次消息就可以获得容错度计算所需要的参数，在节点通信半径不同的网络环境中进一步优化消息开销。

2.3选择备份节点

备份节点的选择从某一“Black”节点v开始，从邻居节点列表N1（v）中优先在FT属性为true的记录中选择FD（u）最大的“Grey”节点加入到备份节点集Back（v），否则在FT==fasle的记录中查找。在每一次选择后，更新当前节点尚未覆盖的节点集（Cover（v）=Cover（v）CNL（u）），其中Cover（v）被初始化为当前节点的邻居节点集N1（v）∪v。该操作结束后，还需要对当前节点v的其他邻居节点w对应的公共节点列表CNL进行更新（CNL（w）= CNL（w）CNL（u））；如果Cover（u）≠Φ，继续选择FD最大且CNL≠Φ的其他节点加入到Back（v）中直到Cover（u）=Φ。上述过程结束后，Black节点v广播一个Notify（IDv，Back（v），NBlack（v））消息，其中NBlack表示当前节点下层的“Black”节点列表。

当Grey节点u收到Notify消息后，检查IDu是否在Back列表中，如果存在成为Blue节点；如果是下层Black节点u收到该消息，则遍历Back（v）列表，并更新N1（u）列表中对应记录的FT属性为true。完成操作后，按照其在邻居支配节点列表NBlack中的索引位置等待超时结束选择备份节点。

当Black节点u突然失效时，它将广播Active消息唤醒邻域的Blue节点重新进入工作状态，下层的Black节点v收到消息后，将路由的发送对象从节点u调整为距离自身最近的Blue节点，然后继续数据收集过程。

图1给出了备份节点选择的一个算法运行实例，假设S是初始执行节点。如图1（a），节点S对邻居节点的FD进行评估，选择最大节点A加入到Back（s），此时因为A已经能够覆盖节点S需要覆盖的所有节点（C，D，S，E，F），S广播Notify消息。节点A收到消息后变成Blue，而C、F在N1列表中设置A的FT属性等于true，然后C首先开始选择备份节点，它首先从列表N1（C）中选择FT==true的节点A更新Cover（C）（｛B｝），此时得到Cover（C）==Φ，即C将A作为Blue节点。图1（c）中节点G首先被选为F的备份节点，但是此时发现其与节点S不再连通，需要继续将E加入到Back中。图1（d）中显示了节点A、E、G、H最终被标记为Blue。

图1　选择备份节点的实例图

2.4均衡能耗速率

为了均衡支配节点的能量消耗，最终使得所有节点尽可能在同一时刻死亡，需要平衡支配节点数据转发的任务，让能量较高节点承担较重的任务负载。考虑邻居支配节点的个数、剩余能量以及支配节点与被支配节点链路之间的距离，定义了期望分配概率函数DEAP，将普通节点采集的数据以概率发送到支配节点上，这样避免了集中消耗部分中心节点的能量，从而延长了网络的生命时间，对支配节点i的概率计算为：

普通节点v周围可能有多个支配节点，v采集到数据后，需要选择一个支配节点发送数据，DEAP（i）表示发给支配节点i的概率。式（3）中，E（i）表示当前节点的邻居支配节点的剩余能量，Black_Num（i），dis（i，v）分别表示节点v的邻居支配节点数和节点v与i之间的距离。所以，分子表明节点i的能量指数加权，可见能量指数越大，将数据发给支配节点i的概率越高；分母表示i的周边支配节点能量指数加权求和；节点i，j的能量指数加权与其到节点v的距离dis（i，v），dis（j，v）成反比，将普通节点的数据优先传给较近节点。

3　性能分析

定理1EBFT连通支配集构建算法最多需要发送5n的消息，算法的时间复杂度为O（n）。

证明连通支配集构建首先要在每个节点建立邻居列表，需要计算节点的容错度以选出备份节点集，亦因此节点需要获得邻居节点的邻居列表信息（见式（2）），在对文献［12］中的邻居发现过程改进后，算法至多只需发送O（n）的消息数。备份节点选择从任一Black节点开始，Black节点依据自身存储的邻居节点列表选择后备节点后，将会广播一个Notify消息通知列表中节点成为备份节点；下层的Black节点等待超时继续向下选择备份节点，所以整个算法至多发送5n的消息。

在选择备份节点集时，Black节点需要选择邻居节点列表中最优的节点，需要O（Δ）的时间，当网络比较密集时Δ趋向于n，算法的时间复杂度为O（n）。

可见，我们连通支配集构建的计算量是可行的，并随着节点数目的增加线性增长。接下来的两个定理，确切的说明了在同构及异构网络的节点维护过程中，因部分失效节点而唤醒的备份节点数目不会过多，不会造成严重的网络浪费。

定理2同构网络任一节点失效时，算法至多添加10个备份节点来保证网络的连通性。

证明如图2所示，假设Black节点u失效，我们需要选择备份节点连通Black节点v和w，同时覆盖节点u邻域的所有Grey节点。因为以u为中心的正六边形将邻域六等份，每一个扇形区域内至多使用2个节点就能与其他区域连通。从节点w开始添加备份节点，最坏情况使用10个节点就能连通网络。同时，这些节点可以完全覆盖节点u的邻域。

图2　同构网络的备份节点分布图

证明如图3所示，假设节点的通信半径R∈［Rmin，Rmax］，我们考虑任意弧度α的情况。假设节点间的距离d（u，w）=d（w，v）=Rmin，根据三角形余弦定理可得d（u，v）=Rmin（2cosα）；又因为d（u，v）= d（v，x），则d（u，x）=Rmin（2cosα）2；如上迭代可得Rmax=Rmin（2cosα）k，k为节点u与最大通信半径之间至多需要的节点个数，解得。由于单位圆可以划分为2π/α个圆弧，考虑连通性，共需要个节点。对该函数进行积分求解最大值，可得当α=π/5时得到极值。类似的，一个弧形区域内至多使用2个节点就能与相邻区域连通，此时总共需要个节点。

图3　异构网络的备份节点分布图

4　仿真实验及分析

4.1实验环境

仿真采用文献［14］提供的平台，随机生成20个拓扑实例，运行20次取平均值。仿真使用的参数见表1。

表1　仿真实验参数设置

4.2结果分析

为了验证算法的有效性，仿真实验选择与EBCDS、DDA、AFTC三个当前较新的算法进行比较，这里选择这三个算法的原因是EBCDS是当前比较新的基于最大独立集的算法，DDA是较新的k连通m-支配容错拓扑构建算法，AFTC采用与EBFT相同的思想构建容错拓扑结构。

仿真1将100个节点部署到网络中，观察节点的通信半径对产生的支配节点的影响。如图4所示，EBFT在不同通信半径下产生的支配节点数均要少于其他算法，当半径为20时EBFT只需要21.8个节点作为支配节点，而EBCDS、AFTC、DDA分别需要24.5、26.2和41.3个节点。通信半径加大时，各个算法所需要支配节点数都逐渐减少，当半径为45时，EBFT、EBCDS、AFTC、DDA四个算法分别产生6.0、6.9、7.3和10.2个活跃节点。此时，算法之间的差距变小，其中DDA下降最快，这说明当通信半径增大时构建（2，2）-CDS更加容易。

图4　实验1节点通信半径变化时的活跃节点数

EBFT-Back和AFTC-Back是EBFT和AFTC产生的备份节点数。当半径较少时，更多节点需要作为备份节点保证网络连通，当通信半径为20时，EBFT和AFTC产生的后备节点数分别为28.8和35.2，相比产生的活跃节点分别增加了7.0和9.1，这一差距随着通信半径的增加而减少，但是EBFT需要的后备节点数还是少于AFTC，这是因为AFTC算法在选择备份节点时，多个Black节点可能同时开始选择，造成冗余节点被选入的问题。

仿真2将通信半径设为30，通过改变节点数量观察活跃节点的变化。如图5所示，各个算法的活跃节点数一直在某个值附近波动，这是因为当区域节点数达到一定密度时，当前活跃节点已经可以支配整个网络，继续增加节点数并不需要增加新的活跃节点数。图中还发现DDA产生的活跃节点数要多于其他算法，而EBCDS的性能要优于AFTC。

图5　实验2节点数量变化时的活跃节点数

网络生命是衡量算法的最终指标，实验3将100个节点部署在网络中，将通信半径设为25，观察各算法的最终的生命时间。如图6所示，EBFT在将近800轮时才出现第一个节点的死亡，EBCDS、AFTC、DDA这一数据分别为681.6、590.7和477.5。显然，EBFT能够有效延长网络的生命时间，这是因为EBFT不但可以生成规模较小的活跃节点集，而且算法的构建能耗较小。此外，EBFT还增加了支配节点的负载均衡，其网络寿命相比EBCDS可提高17.1%。相反，DDA算法不但具有较高的支配节点规模和构建能耗，所以它的网络生命时间较短也是可以理解的。

图6　实验3理想环境时的生命周期

为了能够更加真实模拟网络的实际环境，需要考虑节点出错的可能性，在每一轮中使用随机数模拟节点是否出现故障。相比理想环境，图7显示各个算法的生命时间均有所下降，EBFT、AFTC和DDA出现第一个死亡节点的时刻为783.1、567.2和448.5，同比分别提前了14.4、23.5和29.0个轮次。这里需要注意的是EBCDS在节点失效环境中的生命时间不如AFTC，它的第一个节点出现死亡的时间为581.8，相比理想环境超过了100轮，这是因为每次出现节点失效时都需要重新运行拓扑维护，使得网络重构的次数增多，减少了能量的利用率。

5　总结

本文对异构无线传感器网络模型进行了扩展，在异构网络模型中研究分布式容错数据收集算法。算法针对k-连通m-支配集规模过大的问题，转换了容错拓扑构建的思想，在不需要节点位置信息的情况下，通过对活跃节点产生备份集的方法来生成容错拓扑，这样可以减少处于工作的支配节点数。此外，还考虑了节点能耗速率对网络生命的影响，对数据收集过程进行了优化。理论分析对算法在同构和异构两种网络环境中需要增加的节点数情况进行了分析，保证了算法产生的后备节点的连通性。仿真实验进一步证明EBFT在能效性、扩展性、可靠性上都具有较好的优越性。

［1］Lee S，Mohamed Y.Recovery from Multiple Simultaneous Fail⁃ures inWireless Sensor Networks Using Minimum Steiner Tree［J］.Parallel and Distributed Computing，2010，70（5）：525-536.

［2］马晨明，王万良，洪榛，等.带有能量补给的异构无线传感器网络拓扑控制算法研究［J］.电信科学，2015，31（8）：2015181.

［3］马晨明，王万良，洪榛.无线传感器网络中一种改进的能效数据收集协议［J］.计算机科学，2015，42（2）：65-69.

［4］He J，Ji S L，Fan P Z，et al.Constructing a Load-Balanced Virtual Backbone in Wireless Sensor Networks［C］//Procof2012 Interna⁃tional Conference on Computing Networking and Communications（ICNC），Maui，Hawaii，USA，2012：959-963.

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

［6］Wang F，Thai MT，Du D Z.On the Construction of 2-Connected Virtual Backbone in Wireless Networks［J］.IEEE Transactions on Wireless Communications，2009，8（3）：1230-1237.

［7］Thai M T，Zhang N，Tiwari R，et al.OnApproximation Algorithms of k-Connectedm-Dominating Sets in Disk Graphs［J］.Theoretical Computer Science，2007，385：49-59.

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

［9］Li Y S，Wu Y W，Ai C Y，et al.On the Construction ofk-Connect⁃edm-Dominating Sets in Wireless Networks［J］.Combinatorial Op⁃timization，2012，1（23）：118-139.

［10］付永生，李善平，周波.无线传感网络中能量均衡的连通支配集算法［J］.传感技术学报，2010，23（8）：1142-1145.

［11］Yin R R，Liu B，Li Y Q，et al.Adaptively Fault-Tolerant Topology Control Algorithm for Wireless Sensor Networks［J］.The Journal of China Universities of Posts and Telecommunications，2012，19（ZK2）：13-38.

［12］马晨明，王万良，洪榛.异构无线传感器网络中基于CDS树的拓扑控制方法［J］.传感技术学报，2014，27（6）：814-820.

［13］杨明霞，王万良，马晨明.一种基于反向CDS树的异构WSNs拓扑控制方法［J］.传感技术学报，2016，29（2）：248-255.

［14］Wightman P M，Labrador M A.Atarraya：A Simulation Tool to Teach and Research Topology Control Algorithms for Wireless Sensor Networks［C］//Proc of 2nd International Conference on Simulation Tools and Techniques，Rome，Italy，2009：26-35.

杨明霞（1979-），女，浙江衢州人，衢州学院讲师。浙江工业大学在读博士，研究方向为计算机自动化、无线传感器网络；

王万良（1957-），男，江苏高邮人，博士生导师。国家级教学名师、享受国务院特殊政府津贴、浙江工业大学计算机科学与技术学院院长，研究方向为计算机网络化控制、无线网络。

EEACC：723010.3969/j.issn.1004-1699.2016.06.024

面向节能和容错的异构WSNs数据收集算法*

杨明霞1，2，王万良2*，马晨明2
（1.衢州学院电气与信息工程学院，浙江衢州324000；2.浙江工业大学计算机学院，杭州310023）

采用连通支配集作为虚拟骨干可以延长无线传感器网络的生命时间，但是考虑节点容易失效的特性，网络还需要具有一定的容错性。针对k-连通m-支配集的容错方法能耗过大的问题，提出了一种面向节能和容错的分布式数据收集算法。算法首先构建连通支配集，然后选择容错度大的节点作为备份节点，最后在数据收集过程对支配节点的能耗进行均衡。理论分析和仿真实验证实算法不仅以较小的时间和消息开销构建规模较优的连通支配集，而且还保证了容错性并最终延长了网络的生命时间。

异构无线传感器网络；连通支配集；数据收集；容错；负载均衡

TP393

A

1004-1699（2016）06-0934-07

2016-01-06修改日期：2016-03-24

项目来源：国家自然科学基金项目（61379123）；浙江省自然科学基金项目（LY15F020041，LY15F030014）；衢州学院师资队伍建设基金项目（XNZQN201308）；宁波市社会发展基金项目（2014C50006）