基于节点综合故障模型的无线传感器网络容错拓扑控制方法

尹荣荣 刘 彬 刘浩然 郝晓辰

(燕山大学电气工程学院 秦皇岛 066004)

1 引言

无线传感器网络(Wireless Sensor Networks,WSNs)可以随时随地自组成网，特别适合在敌对或恶劣条件下快速组网，形成对特定目标的有效监视[1]。由于传感器节点常部署在面积广大且人迹罕至甚至危险的远程环境中，供电电池不易替换[2]，环境损坏造成的节点失效情况频繁出现[3]，所以综合关注网络节能效率和节点随机故障容忍能力的容错拓扑控制[4]是WSNs的一个重要研究课题。

目前容错拓扑控制的研究，重点集中于探索分布式算法构造具有节能特点的k连通容错网络[5]与无标度容错网络[6]，以保证节点随机失效下的网络正常运行。对于k连通容错算法，文献[7]为冗余机制能自动产生一个具备相似功能的替代方案，使网络在任意k.-1个节点同时失效状态下依然能正常工作，提出了k连通k支配集构造算法；文献[8]认为在连通支配集中节点存在功能差异，配备相同的冗余度并非必要，拓展了基于睡眠/工作调度的k连通m支配集生成算法；文献[9]联合睡眠调度和功率调整技术，给出了簇间k连通容错拓扑控制算法；这些算法均为WSNs建立了k连通最小能耗容错拓扑，但是，网络维持k连通需要耗费大量的能量资源[10]，造成仅能容忍少量随机失效节点的弊端。因此，近来少量学者从无标度网络对节点随机失效的强容错性[11,12]出发，建立适用于WSNs的无标度拓扑结构。如，陈力军等人[13]借助随机行走机制，通过改善拓扑均匀性，生成了具有无标度特征的WSNs簇间拓扑结构；文献[14]将节点剩余能量与无标度网络择优增长机制相结合，建立了具有无标度特征的 WSNs能量均衡拓扑；文献[15]借助适应度拓扑演化模型，将适应度计算与节点能量值直接关联，提出了WSNs无标度拓扑构建算法；他们均使WSNs具有了无标度网络的强容错性。然而，无论是k连通构建算法还是无标度生成算法，皆是在保证网络容错结构基础上进行的能量优化，由于忽视了节点能量耗尽故障对拓扑容错性的影响，导致建立的网络拓扑容错性差，而且存在严重的能效约束。因此，面向节点能量耗尽和随机失效的综合故障优化是探索更加有效的WSNs容错拓扑控制方法的新思路。

基于上述分析，本文提出一种基于节点能量耗尽和随机失效综合故障模型的WSNs容错拓扑控制方法 FTCA(Fault-tolerant Topology Control Approach)，该方法首先根据节点能量耗尽和随机失效信息进行综合故障建模，然后利用不等式放缩法与一元函数极值分析法对故障模型进行节点度量化分析，最后通过调整网络中各节点的节点度趋于其节点度最优值对拓扑结构进行控制，保证了网络生命期和节点能量耗尽及随机失效综合容忍能力的双重需求。

2 节点综合故障建模

由于能量耗尽造成节点故障和环境损坏导致节点随机失效是WSNs故障的主要表现形式，则可将网络中任意节点i的故障概率表示为能量耗尽概率fe(i)和随机失效概率fr(i)的乘积形式。

其中fe(i)[16]取决于节点i的初始能量E0(i)，能量消耗Ec(i)和网络运行时间t，即

采用图 1无线通信能耗模型[17]，相距为d的节点发送lbit数据所消耗的能量Etx为信号发射电路与信号放大电路消耗的能量之和为

节点接收lbit数据消耗能量Erx由式(4)计算得到

那么，节点i的总能耗Ec(i)可用下述形式表示：

假设N个节点均匀散布在 2维有界监测区域G(面积为A)内，则节点落入以通信距离d为半径的圆域D内的概率为

图1 无线通信能耗模型

即节点传输距离d与其节点度k之间存在如下关系：

将式(7)代入式(5)可得节点i的能耗值Ec(i)随其节点度k的变化关系，进而代入式(2)得到由节点度k和运行时间t描述的节点能量耗尽概率fe(i)。

考虑到节点随机失效是因环境损坏导致网络稀疏，从而使节点在网络运行环境中发生孤立丧失规定功能的一类故障，其概率与节点度k呈指数变化关系[18]，有

结合式(1)、式(8)和式(9)，可得网络中任意节点i的故障模型如下：

从而，利用节点度k和网络运行时间t，节点能量耗尽和环境损坏造成的综合失效故障具有式(10)的统一模型形式，有必要对k值进行分析，以得到WSNs容错拓扑构建的理论依据。

3 基于故障模型的节点度量化分析

在对k值进行量化分析之前，必须对网络生命期和节点能量耗尽及随机失效综合故障容忍能力的双重需求进行定义：

讨论定义1是针对网络拓扑的节能和容错双重需求而言的，此定义表明，对于一个网络G，为提高其拓扑的能量有效性，网络G须保证一定的生存时间tmin，即t≥tmin；同时为增强其拓扑对随机失效节点的容忍能力，网络G须维持一定的节点度下限kmin，即k≥kmin，而为增强其拓扑对能量耗尽节点的容错性，网络G又须限定其节点度的上限kmax，即k≤kmax。可见，若网络G满足定义 1的条件，则它不仅可以确保网络的生存时间需求，又可以增强容忍能量耗尽和环境损坏导致的综合节点失效现象，也就是说，能够满足网络生命期和综合故障容忍能力要求较高的应用场景。

3.1 满足双重需求的节点故障率分析

基于节点故障模型(式(10))和网络生命期及综合故障容忍能力双重需求(定义1)，给出满足网络生命期和综合故障容忍能力双重需求的节点故障率取值。

证明为确保网络满足定义 1，网络中任意节点i须满足定义1，为此下面采用不等式放缩法对满足定义1的节点故障率f(i)进行讨论。

(1)由t≥tmin可得，节点i的故障率f(i)符合

又根据kmin≤k≤kmax易得

那么由不等式的基本性质可以推出

(2)由kmin≤k≤kmax得

基于不等式的基本性质，由式(10)得到

综合式(14)和式(17)，有

3.2 节点度的定量分析

根据定理 1，网络生命期和综合故障容忍能力的双重需求转化成了节点故障率的要求(式(18))，在此基础上，通过一元函数极值分析法可以对节点度进行定量分析，获取在满足故障率要求下具有最大生存时间的节点度取值，为网络拓扑构建提供依据。

证明令c=a/b，当节点故障率满足f(i) =f0，记网络运行时间t为，根据式(10)有

采用一元函数极值分析法研究节点度取值k与网络生存时间之间的变化关系，对关于k求一阶导数得

进而，根据式(20)可得，在k∈[kmin,+ ∞) 内＞0，那么是增函数，从而，在满足k≤kmax且e-k-f0＞ 0 的条件下，即k=min{kmax,- lnf0}点处，最大。也就是说，存在唯一极值点k0=min{kmax,- lnf0}，使得节点i在满足故障率要求下可实现其生命期的最大化。 证毕

综上，本节获得了满足网络生命期和综合故障容忍能力双重需求的节点度k的最优值k0，为构建可最大限度延长网络生命期，且能够有效提高对节点能量耗尽及随机失效综合故障容忍能力的目标拓扑提供依据。

4 基于节点度调整的FTCA算法

FTCA算法是基于确定的节点度最优值k0提出的一种WSNs容错拓扑控制方法，主要包括以下步骤：

(1)信息交换 各节点以最大发射功率广播包含自身id和位置信息(x,y)的HELLO数据包。任意收到HELLO包的节点建立其邻居列表，以节点i为例，邻居列表nl(i)的表头格式如表1所示。其中，id(j)表示节点i的邻居节点j的id,(xj,yj)表示节点j的地理位置，d(i,j)为i和j之间的距离，由两点间的距离公式计算得到，mark(j)为状态标识，初始记为0。

表1 节点i邻居列表nl( i)的表头格式

(2)邻居排序 节点i依据邻居列表nl(i)中距离的升序排列其邻节点，并广播包含自身id和邻居列表的NOTICE信息。对于收到NOTICE信息的节点，判断自身通信区域内的链路状态，建立区域链路列表，其表头格式见表2。其中，d(j1,j2)为节点i的相互可达邻居节点j1和j2间的距离，id(j1)和id(j2) 分别为j1,j2的id, s ign(j1,j2)为状态标识，初始设定为0。

表2 节点i区域链路列表ll( i)的表头格式

节点i按照通信距离d(j1,j2)对其区域链路列表ll(i)进行升序排列，如果j1和j2之间不存在通信路径，将链路l(j1,j2)的状态标识sign(ji,jj)更新为1，直至与所有邻节点皆建立通信路径为止，删除sign标记为0的链路项信息。

(3)链路选择 基于区域链路列表ll(i)，节点i寻找ll(i)中由自身出发的链路项，将其sign标记为2，删除标记为1的链路项信息，并广播包含自身id和ll(i)信息的CONNECT数据包。根据所接收到的CONNECT数据，以链路双向性原则确定其邻节点，并将其nl列表中的相应标识位mark更新为1，统计其数目记为kmin，计算出k0与kmin的差值。按距离升序依次将个nl列表中标识为0的节点标记为2，广播其id，保留具有双向链路的邻节点，将nl中相应状态标识更新为 1，删除状态不为 1的邻节点信息项。

(4)功率调整 最后，节点i确定的发射功率应保证与其所有邻节点(位于已更新的邻居列表nl中)皆能正常通信，即节点i的发射半径为di=max{d(i,j)|j∈nl(i) } 。

5 实验分析

本文使用仿真工具 Matlab实现k连通算法k-Grid(k=2)[7]、无标度算法 EAEM(m0=2,m=1)[14]以及FTCA算法，并比较所得网络拓扑的节能性和容错能力。实验中参数设置如表3所示，运行仿真实验50次，以下分析数据均为50次实验数据均值。

基于网络生命期和节点能量耗尽故障及随机失效故障综合容忍能力的双重需求，节点度k的量化分析结果如图2所示，该图直观地描述并验证了k的最优值k0的存在性。图3描述了FTCA算法所得目标拓扑中节点平均度＜k＞与其理论最优值k0之间的偏差情况，偏差越小意味FTCA算法的准确率越高。从图2中可以看出，当节点度取值为k=-ln(f0)时其生存时间t达到最大，即最优值k0的存在性在图中得到了很好的体现。从图3中可以看出，当网络节点数目增加时，FTCA算法所得拓扑的节点平均度与理论最优值之间的偏差在减小，且最大偏差小于0.15，也就是说，FTCA算法可以有效保证生成拓扑的准确性。

图 4描述了原始拓扑结构Gs以及k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目标拓扑结构图，该图验证了FTCA算法的相关拓扑性质，如连通性、对称性与鲁棒性。从图4可以看出，k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法均对原始拓扑结构Gs进行了简化，生成的目标拓扑结构都保留了双向链路。另外，由于k-Grid(k=2)算法基于概率进行拓扑构建，依据链路冗余实现拓扑容错，较 EAEM(m0=2,m=1)算法和FTCA算法所得拓扑更为密集，且拓扑的连通性不能很好地保证；而EAEM算法是根据结构的不均匀性实现容错，FTCA算法是以维持各节点的节点度在某一特定值达到容错，两者所得拓扑结构更为稀疏，且有效确保了所得拓扑的全连通。

表3 实验参数设置

图2 节点度最优值k0存在性分析图

图3 FTCA算法准确性分析图

图4 拓扑结构分析图

图 5描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目标拓扑的节点平均发射半径。由于较小的发射半径能够降低节点能量消耗，减少通信干扰，增大网络容量，因此节点的发射半径大小一定程度上能体现网络的节能性，是容错拓扑控制算法追求的良好拓扑性质之一。图 6描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法所得目标拓扑的节点平均度。由于节点最小度为k的k连通网络在任意k-1个节点失效后仍能保持连通，具有k-1的容错能力，虽然节点平均度为k不能保证网络是k连通，但是，节点的平均度在一定程度上也能反映网络的容错能力，是容错拓扑控制算法追求的又一良好拓扑性质。从图5可以看出，网络节点数从100至500的变化中，由于FTCA算法所得拓扑无需维持k-Grid(k=2)拓扑的冗余链路，也不存在 EAEM(m0=2,m=1)拓扑的集散(度很大)节点，故其节点平均发射半径始终远小于k-Grid(k=2)和EAEM(m0=2,m=1)拓扑，并且随着节点数的增大，节点平均发射半径逐渐减小，即网络具有更好的节能性。从图6可以看出，由于FTCA算法以节点能量故障和随机故障的协同优化为设计目标，通过各节点维持某一特定节点度实现容错，所得拓扑的节点平均度低于k-Grid(k=2)冗余拓扑，高于 EAEM(m0=2,m=1)非冗余拓扑，即网络对节点随机失效的容忍能力介于k-Grid(k=2)拓扑与EAEM(m0=2,m=1)拓扑之间。

WSNs生命期定义为有效数据采集轮数(采集1轮数据规定为全网中各节点传输数据1次)是评价容错拓扑控制算法性能的重要指标，对于特定的节点数(100个)，分别运行k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA 算法，然后以 Poisson规则随机地失效节点，直到可用节点(位于最大连通分支中)数占网络原有节点数的50%时停止，此时网络生命期也终止。图7给出了上述算法所得目标拓扑在节点能量耗尽与随机失效故障共存下的生命期变化情况。其中，图 7(a)描述了从开始至网络终止整个运行时间段内的节点随机失效现象，图7(b)为该时间段内网络可用节点数的变化情况，图 7(c)为网络出现节点能量耗尽故障的运行时刻，图7(d)为网络出现节点随机失效故障的运行时刻。可见，k-Grid(k=2)算法所得拓扑对随机节点失效有较强的容错能力，在网络终止前仅出现一次因随机失效节点引发的网络分割现象(图 7(d))，但因多节点的能量耗尽故障(图7(c))导致网络较早终止(图7(b))；EAEM(m0=2,m=1)算法所得网络拓扑的容错能力恰与k-Grid(k=2)拓扑相反，在网络终止前没有出现过节点能量耗尽现象(图 7(c))，却因部分随机失效节点发生网络分割(图 7(d))，最终因集散节点的能量耗尽故障而较早终止运行(图 7(b))；FTCA算法由于考虑了节点能量耗尽故障对网络容错性的影响，并以优化节点综合故障为设计目标，所得拓扑结构在最大化网络生命期(图 7(b))和提升网络综合故障容忍能力方面(图 7(c)和图 7(d))均体现出极佳的效果，大大延长了网络的生命期，增强了网络对节点能量耗尽故障和随机失效故障的综合容错性。

图5 节点平均发射半径分析图

图6 节点平均度分析图

图7 节点能量耗尽与随机失效综合故障下网络生命期分析图

6 结束语

本文提出了一种基于节点能量耗尽和随机失效综合故障模型的WSNs容错拓扑控制方法FTCA，使得生成的网络拓扑具有较大生命期和对节点能量耗尽及随机失效强容错的双重性能。另外，通过对节点故障模型的分析得出，当节点度为 min{kmax,- ln (f0)}时可以获得满足节能和容错双重需求的目标拓扑；并对FTCA算法实验数据的分析得出，相对k-Grid(k=2)算法和 EAEM(m0=2,m=1)算法，FTCA算法由于采用了节点能量故障和随机故障综合优化的节点度取值，大大延缓了因节点能量耗尽及随机失效综合故障造成的网络生命期终止时刻，有效地增强了网络对节点能量耗尽及随机失效的综合容错能力。

[1]Akyildiz I F, Su W, Sankarasubramaniam Y,et al.. Wireless sensor networks: a survey[J].Computer Networks, 2002, 38(4):393-422.

[2]Chen I R, Speer A P, and Eltoweissy M. Adaptive fault-tolerant QoS control algorithm for maximizing system lifetime of query-based wireless sensor networks[J].IEEE Transactions on Dependable and Secure Computing, 2011,8(2): 161-176.

[3]Lee S and Younis M. Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree[J].Journal of Parallel and Distributed Computing, 2010,70(5): 525-536.

[4]Bari A, Jaekel A, Jiang J,et al.. Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirement[J].Computer Communications, 2012, 35(3):320-333.

[5]Zhang W Y, Xue G L, and Misra S. Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms[C]. Proceedings-IEEE INFOCOM, Anchorage,AK, 2007: 1649-1657.

[6]Zhang K, Han D H, and Feng H P. A model of linear expanding in the local-world based on the laws of internal evolution of the wireless sensor networks[C]. Proceedings of the 2010 International Conference on Computer Application and System Modeling, Taiyuan, China, 2010: 357-360.

[7]Dai F and Wu J. On constructing k-connected k-dominating set in wireless Ad hoc and sensor networks[J].Journal of Parallel and Distributed Computing, 2006, 66(7): 947-958.

[8]Zhao Y X, Wu J, Li F,et al.. VBS: maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones[C]. Proceedings-IEEE INFOCOM, San Diego, CA,2010: 1-5.

[9]Forghani A and Rahmani A M. Multi state fault tolerant topology control algorithm for wireless sensor networks[C].Proceedings of the 2008 2nd International Conference on Future Generation Communication and Networking, Hainan Island, China, 2008: 433-436.

[10]王良民, 马建峰, 王超. 无线传感器网络拓扑的容错度与容侵度[J]. 电子学报, 2006, 34(8): 1446-1451.

Wang L M, Ma J F, and Wang C. Degree of fault-tolerance and intrusion-tolerance for topologies of wireless sensor networks[J].Acta Electronic Sinica, 2006, 34(8): 1446-1451.

[11]Barabasi A L and Albert R. Emergence of scaling in random networks[J].Science, 1999, 286(5439): 509-512.

[12]Cohen R, Erez K, Ben A D,et al.. Resilience of the internet to random breakdowns[J].Physical Review Letters, 2000, 85(21):4626-4628.

[13]陈力军, 刘明, 陈道蓄, 等. 基于随机行走的无线传感器网络簇间拓扑演化[J]. 计算机学报, 2009, 32(1): 69-76.

Chen L J, Liu M, Chen D X,et al.. Topology evolution of wireless sensor networks among cluster heads by random walkers[J].Chinese Journal of Computers, 2009, 32(1): 69-76.

[14]Zhu H L, Luo H, Peng H P,et al.. Complex networks-based energy-efficient evolution model for wireless sensor networks[J].Chaos,Solitons and Fractals, 2009, 41(4):1828-1835.

[15]Qi X Q, Ma S Q, and Zheng G Z. Topology evolution of wireless sensor networks based on adaptive free-scale networks[J].Journal of Information and Computational Science, 2011, 8(3): 467-475.

[16]Mizanian K, Yousefi H, and Jahangir A H. Modeling and evaluating reliable real-time degree in multi-hop wireless sensor networks[C]. Proceedings of the 2009 IEEE Sarnoff Symposium, Princeton, NJ, 2009: 1-6.

[17]Heizelman W R, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. Proceedings of the Hawaii International Conference on System Sciences, Maui, USA,2000: 1-10.

[18]Kleinrock L and Silvester J. Optimum transmission radii for packet radio networks or why six is a magic number[C].Proceedings of the National Telecommunications Conference,Birmingham Ala, 1978: 1-5.