基于节能的WSN分簇式故障诊断算法

曾庆杰，朱晓娟，王先超

（1.安徽理工大学 计算机科学与工程学院，安徽 淮南 232001；2.阜阳师范大学 计算机与信息工程学院，安徽 阜阳 236037）

无线传感器网络（wireless sensor network，WSN）由于部署灵活且成本较低，目前广泛应用在社会生活的各个领域[1-5]。WSN通常部署在环境比较复杂的区域，且具有自身鲜明的缺陷[6-8]，使得传感器节点出现故障的可能性较大。节点一旦出现故障，将会严重影响网络的监测性能。因此，研究WSN故障诊断技术对维护WSN可持续、稳定运行意义重大。集中式策略和分布式策略是WSN的故障诊断中常用的两种策略[9]。集中式策略适用于小型网络，分布式策略适用于网络规模较大的故障诊断，且比集中式诊断策略有较小的通信开销[10]。杜莹[11]和刘凯[12]等人分别提出了改进的分簇式故障诊断算法。二者通过实验表明，分簇式故障诊断算法比传统分布式[13]算法在诊断过程中不仅提高了故障检测准确率，而且降低了网络能耗。因此，本文提出的故障诊断方法是基于能量优化的分簇式诊断方法。

1 相关理论

1.1 WSN感知数据的时空相关性

无线传感器网络中的节点采集的数据具有时空相关性[14]。对于单个节点在非常短的时间内感知的数据具有一定的连续性，存在时间相关性。例如，在某区域中部署无线传感器网络连续监测区域的温度，则在相邻时间内采集的温度值非常接近。在实际应用中，通常会在监测区域内高密度部署传感器节点，因此网络中节点的冗余度很高，则地理位置相近的传感器节点的感知数据存在空间相关性。

1.2 WSN软故障

本文提出的故障诊断算法主要针对节点的软故障[15]，即节点发生软故障后，仍能够对数据进行发送、接收和处理。软故障主要有如下四种类型：

（ⅰ）偏移故障。偏移故障是指节点采集的数据与同等条件下正常节点采集的数据有固定的偏移量，其值仍会随时间和环境的变化而改变。

（ⅱ）固定值故障。节点连续采集的数据是一个固定的常数，不会因时间和环境的变化而改变。

（ⅲ）间歇性故障。传感器节点的测量值有时在正常值范围内，有时会远大于正常值范围或小于正常值范围。

（ⅳ）瞬时故障。由于瞬时故障只是在节点某一瞬间发生，随后会恢复正常，因此一般将发生瞬时故障的节点作正常节点考虑。

2 模型

2.1 网络模型

本文算法研究的网络为大规模分簇式结构，在网络中所有节点通信半径相同，每个簇内的节点均采用一跳通信机制。每个簇中的簇头与所在的簇内成员节点之间均能进行一跳通信，簇中发生软故障的节点也能进行通信。每个簇中正常节点之间的感知数据满足时空相关性原理。

2.2 能耗模型

在本算法中，我们采用傅菊萍等人[16]给出的WSN节点能耗模型来计算在算法诊断中节点产生的通信能耗，式（1）所示为节点Si发送lb的信息所消耗的能量，式（2）表示节点Sj接收lb的数据所消耗的能量。

其中：d表示源节点与目标节点之间的传输距离，若d小于等于节点的通信半径r时，用表示发射放大器将1 b数据发送到1 m2的能耗，此时节点功率放大损耗采用自由空间模型。若d大于节点的通信半径r时，则节点通信采用多路径衰减模型，那么节点通信开销将大大增加。在网络中所有节点发射功率固定的前提下，目标节点与源节点的近似距离可以通过目标节点接收信号强度(received signal strength indication，RSSI)进行计算。为了节省诊断能耗，本文诊断算法采用单跳通信机制，即两节点之间在诊断过程中的通信行为都在节点通信半径范围内，所以采用d≤r的能量消耗模型。

3 基于节能的分簇式WSN故障诊断算法

3.1 相关研究

CFD（cluster-based fault detection）算法[17]是基于WSN分簇的故障诊断算法，该算法的思想是先将无线传感器网络分成多个簇，要求簇内节点采用单跳通信机制且各簇头不互为邻居节点，先利用簇头的邻居节点对簇头进行可靠性验证，保证簇头具有较高的可信度。然后通过正常簇头与簇内成员节点进行数据交换，比较两个节点的某时刻观测值，从而对簇内成员节点状态进行判断。考虑到节点发生瞬时故障，该算法通过为每个传感节点设定了一个可信度值，提高了算法的容错性，降低了算法误诊率。本文算法考虑到节点能耗和环境因素对节点感知数据的影响，在CFD算法上进行了两点改进。

（ⅰ）在对簇头进行可靠性验证时，候选簇头选择能量较充足、通信质量较佳的η个成员节点对其进行故障诊断，不需要所有的成员节点参与对簇头的故障检测。因为这样可以减少成员节点中剩余能量较小的节点的通信次数，从而降低其诊断的能耗，延长网络使用寿命。

（ⅱ）在采集某时刻的候选簇头的观测值时，考虑到环境因素对观测数据的影响，引入了原则[9]，提高了候选簇头的诊断可靠性。

3.2 算法相关定义

邻居节点：节点Si单跳通信范围内的所有节点为Si的邻居节点，即簇内成员节点，记为SjϵNei(Si)={S1,S2,…,SN}。

观测值：传感节点感测到的当前的真实数据值。

测试值：根据两个节点的观测值比较结果产生的一个0/1值。即一个待诊断节点某时刻的观测值为dj与一个正常节点di，如果|di-dj|＜θ（θ为设定的阈值），则比较结果为cij=0，即该节点诊断正常，反之为cij=1，则该节点发生故障。

可信度值：为了防止节点发生瞬时故障出现误判，将每个传感节点设置一个初始可信度值，若节点测试值cij=0时，此节点可信度值不变，若节点测试值cij=1时，则可信度值减1。若节点的可信度值降为0时，则认为该节点是永久故障的。

节点状态：在WSN中正常和故障节点分别用Tj=0和Tj=1表示。

节点故障检测准确率(correct diagnosis rate，CDR):设无线传感器网络中，故障节点的集合为VF，准确诊断出故障的节点集合为VTF，则

Eri：传感节点Si传输一次数据后剩余能量。

Ei：传感节点Si剩余能量。

3.3 算法步骤

基于节能的分簇式WSN故障诊断算法如下：

Step 1 网络分簇。

首先将整个网络分成多个簇，每个簇中簇头节点包含了所有成员节点的信息，如节点剩余能量等，并且簇内节点之间采用单跳通信机制，且各个簇头不互为邻居节点。

Step 2 验证候选簇头的可靠性

在本文改进的分簇式故障诊断算法中，首先选择每个簇内节点剩余电量较大的节点为候选簇头。令某一个簇内的候选簇头为Si，其簇内的成员节点为Sj，SjϵNei(Si)，候选簇头首先获取其簇内成员节点的剩余能量以及节点的历史数据传输成功率等信息，然后对所有成员节点Sj参与本次诊断后剩余能量Erj进行预估，选择Erj最大的η个成员节点Sj参与对候选簇头的诊断。即候选簇头Si先采集簇内成员节点的剩余电量信息Ej和欧式距离dij以及成员节点成功采集传输一次信息需要的平均次数nj，预估成员节点传输一次数据后剩余能量，则选择Erj最大的η个成员节点Sj的观测值发送给候选簇头。

令η个成员节点观测值为Neixsi(t)，设N(t）为候选簇头节点Si的观测值与Neixsi(t)的按升序排列的数集，其中：N(t)={xs1(t),xs2(t),…,xsN(t)}，则

由于节点观测值可能是正常的，也有可能是错误的，且节点观测值服从正态分布。将候选簇头在t时刻的观测值记为xsi(t)，即满足

若节点i为正常节点时，则其标准差很小，发生故障时则很大。根据概率3δ原则[18]，正常节点的观测值分布在中的概率为0.997 4，可以认为正常节点的观测值几乎全部落在该区间中。即当时，则认为该节点为正常节点。

其中med{N(t)-medi}表示N(t)中各个元素与中值medi的差的绝对值的中位数，节点状态判断准则：

具体实现算法如算法1。

算法1候选簇头可靠性算法

输入：WSN分簇网络；候选簇头Si；参与诊断成员节点个数η；节点一次发送的数据量lbit输出：候选簇头为正常节点或故障节点1候选簇头Si采集簇内成员节点SjϵNei(Si)的剩余电量信息Ej和欧式距离dij 2候选簇头Si采集簇内成员节点SjϵNei(Si)的成功采集传输一次信息需要的平均次数nj 3预估成员节点传输一次数据后剩余能量Erj=Ej-nj(lEelec+lεampd2 ij)4选择Erj最大的η个成员节点参与候选簇头的诊断5 for j←1 to Neixsi(t)//遍历Erj最大的η个成员节点t时刻数据6 N(t)=Neixsi(t)⋃xsi(t)7 sortN(t) //升序排列集合N(t)8 计算集合N(t)的中位数medi 9 mad=med{ ||N(t)-medi} //计算中值绝对偏差的中位数10MANDsi=mad 0.675 //计算归一化绝对值偏差xsi(t)-medi MANDsi 12 ifqsi＜3 13 候选簇头正常，则该节点为簇头14 else 15 候选簇头故障，重新选择候选簇头16 end 11 qsi= ||| |||||

Step 3 簇内成员节点故障诊断

Step 2 可以选择正常的簇头，在t+1时刻，簇内成员节点Sj分别将其观测值与正常簇头Si的观测值进行比较，其差值应小于阈值θ，其中θ为同一时刻相邻节点正常观测值的范围跨度，则

虽然在验证簇头无故障的前提下通过其与簇内成员节点的观测值进行比较来判断成员节点是否故障，却不能保证在每次进行观测值比较时，簇头的观测值始终是在正常范围内。一旦簇头发生瞬时故障，就会造成对簇内成员节点的误诊，大大降低了网络的诊断准确度。因此在测试完簇内成员节点状态后，需比较测试结果中cij=0的个数是否大于成员节点个数的一半。如果大于一半，说明簇头没有发生瞬时故障，此次节点测试结果可靠。节点可靠性诊断算法如算法2。

Step 4 验证t+1时刻簇头节点可靠性。具体算法如算法3。

算法2簇内成员节点可靠性诊断算法

输入：簇头Si在t+1时刻的数据xsi(t+1)，Nei(Si))在t+1时刻据Neixsi(t+1)输出：簇内所有成员节点t+1时刻状态测试结果cij=0或cij=1 1 for j←1 to Neixsi(t+1) //遍历t+1时刻成员节点的数据2 for j←1 to dt+1 ij //遍历t+1时刻成员节点与簇头数据的差值3 if dt+1 ij＜θthencij=0 4 else cij=1 5 for j←1 to cij //遍历t+1时刻成员节点与簇头数据的测试结果6 ifNum(∑SjϵNei(si)cij=0)＞ Num(Nei(Si))/2then 7 ifcij=0 then 8 Tj=0 9 else ifcij=1then 10 if节点在可信度范围内11 λj=λj-1 12 Tj=0 13 else成员节点故障14 Tj=1 15 end

算法3t+1时刻簇头节点可靠性验证算法

输入：t+1时刻成员节点与簇头数据的测试结果输出：网络是否重新分簇//遍历t+1时刻成员节点与簇头数据的测试结果1 for j←1 to cij 2 ifNum(∑SjϵNei(si)cij=0)≤ Num(Nei(Si))/2 then 3 if簇头节点在可信度范围内4 λi=λi-1 5 Ti=0 6 else簇头节点不可靠7 Ti=1 8网络重新分簇9 end

网络中所有簇同时进行故障检测，经过第一轮测试结束后进入下一轮测试，若簇头的剩余能量小于节点能量的一半或可信度值减为0时，则重新选择簇头。

4 仿真分析

4.1 仿真参数

本文采用matlabR2012b软件对CFD算法、本文算法进行仿真分析。在100 m×100 m的监测区域内随机部署240个传感节点。假设节点感知某个时刻的温度值，设传感器每次采集数据的时间间隔为T，其中，正常节点的采集数据在[20，30]之间，为了模拟环境因素对采集数据的影响，则在节点感知数据的同一时刻加上10%的噪声数据。设置节点的通信半径为20 m，初始电量6 000 mAh，初始可信度，阈值。由文献[20]中基于邻居协作的故障诊断分析可知，我们选择簇内成员节点中能量最大的个数。

4.2 实验分析

首先模拟网络的平均邻居节点数为7的情况下，两种算法在网络节点故障率分别为时的故障诊断情况。数据分析如图1。

由图1可看出，两种算法的故障检测准确率在节点故障率较低时都比较高，随着节点故障率不断增大，两种算法的故障检测准确率都随之下降，因为随着节点故障率增大，正常节点越来越少，两种算法的检测准确率很容易受到故障节点的错误数据的影响。本文算法的诊断准确率较高于CFD算法，这是因为本文算法在验证候选簇头的过程中，首先在采集节点观测值时考虑到环境因素对观测值的影响，引入了原则，提前预估了个能量较高、通信质量较好的簇头的邻居节点参与诊断，并用归一化中值绝对偏差代替，很大程度上提高了候选簇头的检测准确度。而CFD算法在采集邻居节点观测值时并没有考虑到噪声对数据的影响，从而在噪声环境下，本文算法的故障诊断准确率高于CFD算法。

图1 不同节点故障率下的故障检测准确率

然后设置网络节点的故障率为0.25，簇内成员节点的平均邻居节点数k=5，10，15，20情况下，比较两种算法的故障节点检测准确率。由图2可知，当平均邻居节点数为5时，本文算法的检测准确率较高于CFD算法，而随着网络中平均邻居节点度的不断增加，由于本文算法在诊断候选簇头时选择的簇头中能量较大的6个邻居节点参与诊断，本文算法的检测准确率基本保持不变，而CFD算法的检测准确率不断接近于本文算法的检测准确率，当邻居节点数大于25后，CFD算法检测准确率高于本文算法检测准确率。但是本文算法仍能在邻居节点数量较少，即网络较稀疏的情况下，保持较高的故障检测准确率。

最后，分别对本文算法和CFD算法在诊断时的节点能量消耗情况进行了实验数据对比分析。与节点通信产生的能耗相比，节点在数据处理等方面所消耗的能量可以忽略。因此，主要考虑两种算法在诊断时节点通信产生的能耗。假设无线传感器网络被分成个簇，每个簇的节点数为n，在CFD算法中，Si选为候选簇头时，会向簇内所有成员节点广播自己的身份，则簇内所有成员节点参与对候选簇头Si的诊断，所有成员节点向待诊断簇头Si发送lb数据，所以节点进行簇头诊断时数据传输所消耗的能量可表示为

在本算法中当Si选为候选簇头时，会在簇内估算出最佳的η个邻居节点，然后向簇内广播这一消息，然后这η个邻居节点Sj向待诊断簇头Si发送lbit数据，所以本文算法在对候选簇头可靠性诊断时，数据传输所消耗的能量可表示为

其中：dij表示节点Si和其邻居节点Sj的通信距离；η表示诊断算法规定的参与诊断的邻居节点个数。对网络a个簇的故障同时进行诊断，在诊断过程中，对候选簇头进行了b次可靠性验证。本文算法比CFD算法节省能量为

图2 不同平均邻居节点数下的节点故障检测准确率

图3表示了2种诊断方式在60次诊断后网络中节点平均剩余电量与平均邻居节点数的关系。可以看出，当平均邻居节点数为5时，小于本文算法设定的，则2种算法的能耗相接近。随着平均邻居节点数不断增大，本文算法的平均节点剩余电量较高，而CFD算法的节点剩余电量则比较少。当平均邻居节点数越多时，本文算法在节点能耗节省方面更有优势。以上仿真分析可以验证本文提出的故障诊断算法不仅具有很好的诊断性能，而且在诊断过程中更有利于节省网络能耗。

图3 节点平均剩余电量与平均邻居节点数

5 小结

针对传感器节点发生软故障的情况，提出了一种基于节能的WSN分簇式故障诊断算法。与传统的分簇式故障诊断方式不同的是，在本文提出的分簇式故障诊断算法中，主要对候选簇头可靠性验证进行了改进，在验证候选簇头过程中，通过选择每个簇内剩余节点能量高的个节点参加候选簇头的诊断，避免簇内能量较低的成员节点参与诊断，对参加候选簇头可靠性验证的成员节点的观测值的采集考虑了环境因素的影响，通过引入原则，增强了候选簇头节点验证的可靠性。通过仿真实验表明，本文算法在一定噪音环境下，在网络平均邻居节点度较大的情况下进行诊断仍具有较高的故障检测准确率，并且比已有算法在节能方面更有优势。