一种分簇无线传感网络的节点自诊断算法

刘亚红，刘 昊

(西安电子科技大学 理学院，陕西 西安710071)

无线传感网络是由部署在监测区域内的大量依靠微型电池供电的传感器节点构成，通过无线通信方式组成的多跳自组织网络系统。其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者［1］。为了提高网络的性能以及延长传感网络的寿命，大多网络都使用分簇协议［2］。然而网络运行中，节点难免会出现各种故障。

无线传感器网络的节点故障类型通常分为两类［3］:硬故障和软故障。所谓硬故障，是指传感器节点的某一模块发生故障，以至不能与其节点通信;所谓软故障，指传感器节点虽然发生故障，但仍可继续工作并与其他节点通信，但节点所感知或传送的数据不正确。

本文主要针对节点软故障的检测且不考虑瞬时故障［4］，假设N个节点随机部署在预设的区域内，并都具有相同的传输距离。定义p为本文的软故障率。

节点信息的空间相似性最早被KrishnamachariB.and lyenga等人在［5－7］中提出，该文献指出了相邻节点之间可以利用信息相似性作比较来进行节点自诊断。文献［8～9］提出节点状态的判断要在给定阈值的基础上，通过多次比较邻居节点的信息来确定自身的状态。文献［10～11］主要研究了给定阈值的大小对整个区域中利用相邻节点之间的感应信息进行诊断的影响。算法仿真结果说明当阈值近似等于区域的节点度时，诊断效果最优，然而当节点度较低时，诊断效果极据下降。文献［12～14］提出了分簇节点自诊断算法，簇头的选择都是建立在各种方法的诊断或众多轮筛选来确定，在保证正确的簇头基础上再分簇进行簇内诊断。然而很多网络最初就是以满足分簇协议来传播信息的，所以故障出现要直接进行诊断。本文算法就是针对簇间诊断设计的，由于簇头之间要进行通信，及形成簇间连通图，利用邻居簇头节点的信息空间相似性进行节点自诊断，再以给定的阈值为判断标准，本文引用［10］中的自诊断方法及阈值结论来诊断簇头的状态，然而在文献［10］中网络空间中可能会出现两层内相邻簇头节点均出现故障的情况以及节点度较低的情况，该种情况通过其诊断算法难以保证诊断效果。所以本文引用诊断之后在对节点状态检验进行二次调整，确保节点的准确性较高。

1 网络故障诊断

1.1 通过邻居节点比较诊断

无线传感网络中，节点的测量值都是空间相关的，即相邻节点之间有着相似的信息值。根据这一性质，将引用到文中的簇头节点诊断中，假设簇头节点形成一个连通网络G，将诊断簇头节点通过相邻簇头节点之间的信息进行比较。本文列出符号定义如表1所示。

表1 相关定义

如表2所述，假设节点v1，v2，…，vj是vi的邻居簇头节点，比较vi与vj，如果满足条件，则表示其两信息相似，记为cij=0，其中cij的情况只有表2所示的4种。则继续比较vi与其他邻居节点的信息。记Ci为簇头节点vi与邻居节点所测的cij=0的个数，假如，则表示簇头节点vi的状态正常，记为Fi=0。

表2 信息比较结果

对所有di≥θ的簇头节点按上述方法诊断出状态，然后判断得出的状态与簇头节点之间的cij值是否吻合。如簇头节点vi的状态根据上述方法诊断出正常，簇头节点vj被诊断出故障，而其的cij=0，则表示实际中信息相似，而状态诊断却不同，因此不吻合。出现这种情况算法中将引用第二步检验，如果节点vi的状态与cij的值不吻合个数大于邻居节点个数的1/2，则将改变节点vi的状态为相反状态。

1.2 算法描述

文献［10］中的算法如表3所示，此算法主要是解决大面积区域且节点部署密集的情况，由于分簇网络中首先要诊断簇头节点确保簇头节点的诊断精度高，簇头连通图中节点个数少，区域的节点度低。故用此算法对于簇头间的诊断效果较低。而本文提出算法诊断簇头节点效果较好。

表3 原算法

文中算法描述如下:

步骤1对每个被检测簇头节点vi，生成该簇头节点的邻簇簇头节点集N(vi)，求出簇头节点di以及簇头节点构成连通图的d，初始化Fi=0，初始化θ。

2 仿真算例

2.1 数值例子

本文通过Matlab随机形成一个分簇网络如图1所示，作为特例来说明本算法。

图1 分簇网络

簇头节点图放大图如图2所示。

图2 簇头连通图

假设实际故障节点为5、16、17、18、20。根据本文算法，首先假设20个节点初步为正常状态，并求出平均节点度3.7，直接令θ=［d］=3，然后根据算法步骤2～步骤3，可初步诊断出节点F1=2，F2=0，F3=0，F4=0，F5=1，F6=1，F8=0，F9=0，F10=0，F11=0，F12=0，F14=0，F15=1，F16=1，F17=0，F18=1，F20=1。

初步诊断得到的节点重新构成新的连通子图如图3所示。

图3 二步诊断图

便于理解，在图中用T来表示Ft=0，F来表示Ft=1。根据步骤5可知，节点17与邻居节点经检验共有3个信息不匹配，所以节点17的最终状态由正常变为故障F17=1，同理可得F1=0，F2=0，F3=0，F4=0，F5=1，F8=0，F9=0，F10=0，F11=0，F14=0，F15=0，F16=1，F17=1，F20=1。根据步骤6由于F8=0，且C8，6=0，所以可知F6=0，同理可得F12=0，F18=1;在返回到原图G中，由于C11，13=0，且F11=0，根据步骤7可得F13=1，同理可依次得出F7=0，F19=0。

通过以上数值举例分析可看出，本文算法解决了节点误诊断错误的情况，且可解决当阈值取低节点度时，诊断率依然能够保持较高，比较结果如图4和图5所示。

2.2 仿真结果

2.2.1 簇头节点诊断结果

通过Matlab对上述比例的簇头节点(20个)按诊断算法与故障诊断原算法［14］分别在节点故障率p为0.05，0.10，0.15，0.20，0.25，0.30，0.35下进行20次仿真得到的诊断精确率，如图4和图5所示。如图4在对其故障诊断精确率和原算法的诊断率进行比较时得到故障率为0.35时，新算法仍能保持83.35%的诊断精度，而原算法诊断精度却为75%。

图4 故障诊断率比较结果

图5 故障虚警率比较结果

2.2.2 整个区域节点诊断结果

由于此算法是建立在簇头的连通图上，簇头被准确诊断后，再延伸到簇内，根据簇头节点与簇内节点之间的相似值来诊断簇内节点。通过Matlab对其算法进行仿真，在簇头通信半径为30，簇内通信半径为20的情况下，分别在节点故障率p为0.05，0.10，0.15，0.20，0.25，0.30，0.35下对算法分别执行20次后得到的故障诊断精度和故障虚警率如图6所示。由此可看出此算法延伸到整个区域的准确性较高。

图6 整个网络的故障诊断效果图

3 结束语

对于分簇传感网络来说，簇头节点数目通常较少，而现有研究未能提供一个合理的算法使簇头节点有较高的诊断精度。文中提出了基于分簇节点自诊断无线传感网络故障诊断的算法，此算法能够精确诊断出簇头节点状态。同时，由于簇头节点得到了精确的诊断，簇内诊断的精确率便得到保障。仿真结果显示整个网络的诊断效果良好。但本文仍然存在一些问题，例如簇头节点大面积出现故障的情况下，诊断精度急速下降，这将是今后研究的重点。

［1］ZHU Chunsheng，SHU Lei，TAKAHIRO H，et al.A survey on communication and data management issues in mobile sensor networks［J］.Wireless Cmmunications and Mobile Computing Wiley，2011，21(3):110－114.

［2］ 沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.Journal of Software，2006，17(7):1588－1600.

［3］CHESSA S，SANTI P.Comparison based system level fault di－agnosis in ad hoc networks［C］.New Orleans:Proc.of IEEE 20th Symp.on Reliable Disrributed Systems(SRDS)，2001:257－266.

［4］CAO Donglei，CAO Jiannong，JIN Beihong.A fault tolerrant algorithm for event region detection in wireless sensor networks［J］.Chinese Journal of Computers，2007，30(10):1770－1776.

［5］KRISHNAMACHARI B，LYENGAR S.Distributed bayesian algorithms for fault－tolerant event region detection in wireless sensor networks［J］.IEEE Transsactions on Computers，2004，53(3):241－250.

［6］CHEN Qinggchun，LAM K Y，FAN Pingzhi.Comments on distributed bayesian algorithms for eault－tolerant event region detection in wireless sensor networks［J］.IEEE Transactions on Computers，2005，55(1):58－70.

［7］LUO X，FAN DONG M，HUANG Y.On distributed faulttolerant detection in wireless sensor networks［J］.IEEE Transactions on Computers，2006，55(1):58－70.

［8］CHEN J R，SHUBNA K，ARUN S.Distributed fault detection of wireless sensor networks［C］.Losangeles，CA，USA:In Proceedings of the International Conference on Mobile Computing and Networkings，2006:65－72.

［9］JIANG P.A new method for node fault detection in wireless sensor networks［J］.Sensors，2009，9(2):1282－1294.

［10］MYEONG H L，YOON H C.Fault detection of wireless sensor networks［J］.Computer Communications，2008，31(14):3469－3475.

［11］季赛，袁慎芳，李含光.WSN中故障诊断性能与平均节点度研究［J］.计算机工程，2010，36(7):14－16.

［12］WANG Zhaoxing，WEN Qiaoyan，ZHANG Yisunhua.A fault detection scheme based on self－clustering nodes sets for wireless sensor networks［C］.IEEE 12th International Conference on Computer and Information Technology，2012.

［13］LIU Wenjun，ZHANG Shukui，FAN Jianxi.A diagnosisbased clustering and multipath routing protocol for wireless sensor networks［C］.International Journal of Distributed Sensor Networks Volume，2012.

［14］刘凯，彭力.一种改进分簇式无线传感网器络节点故障诊断算法研究［J］.传感器与微生态，2011(4):37－40.