WSN中一种新颖的基于预测机制的事件检测容错算法

刘耿耿，郭文忠，洪 伟

1(福州大学 数学与计算机科学学院，福州 350116) 2(福建省网络计算与智能信息处理重点实验室，福州 350116) E-mail ：guowenzhong@fzu.edu.cn

1 引 言

无线传感器网络(Wireless Sensors Network，WSN)是由大量低能耗、具有感知能力的传感器节点组成.节点通互相协作地感知，采集和处理监测区域中感兴趣事件的信息，然后以无线通信的方式把信息发送回基站[1].WSN紧密结合了信息世界与真实的物理世界，实现了信息“无处不在”的模式[2].目前，该技术被广泛应用在众多的实际环境中，如森林火灾检测、化学物质泄漏检测等[3，4].由于传感器节点一般部署在偏远地方，容易受到外界恶劣气候的干扰，而且节点自身资源有限，抗干扰能力差，这些特征往往会引起感知信息过程出现错误，造成误检或者漏检，进而影响网络的性能[5].因此，容错能力对于WSN正常运行而言是至关重要的，不仅提高了数据融合的准确性，还促进了网络的稳定运行.

文献[6]提出一种基于融合树的事件区域检测容错算法，根据已构建的融合树，树节点执行多元线性回归，对单个或者多个事件进行检测，得到相应的估计值.文献[7]利用经验分布和证据理论相结合的方法，提出了一种新颖的事件检测方案.该算法利用Goodness-of-fit(GOF)测试比较节点的采样数据与经验分布情况，依据两者的符合程度来判断事件发生的假设是否成立.以上的算法能够获得较好的检测效果，但是在检测过程中计算复杂度太高，无法满足WSN中的容错实时性要求.文献[8]提出了一种分布式贝叶斯事件检测算法.假设每个传感器出错的概率相同，而且错误是时空间相关的.每个传感器通过与邻居节点的信息交换得到事件发生的概率，进而使用贝叶斯算法进行分析是故障还是事件；文献[9]从数学角度证明了少数服从多数是事件检测中的最优决策模型.利用二进制变量0和1表示传感器的读数，有效地减少了节点间信息的传输能量.并通过实验表明了算法的有效性.但是这类算法忽略了传感器节点的瞬时测量故障，当瞬时故障数量增加的时候，算法的容错性无法得到保证.文献[10]提出了一种新颖的对邻居节点测量数据进行加权的方法，设计了一种衡量测量数据之间差距的方法，利用中值策略检测故障节点，但在节点故障率较高的系统中算法的性能将会显著下降.文献[11]提出一种基于加权平均值的故障检测算法，在不同故障率情况下，传感器节点的永久性故障识别精度高，但在节点故障率较高的系统中算法的性能将会显著下降.文献[12]利用节点的空间相关性提出了一种空间相关的事件容错检测算法.节点通过自身的历史数据计算节点的可信水平，然后算法根据节点的可信度确定邻居节点，并分析节点的测量值与邻居节点的数据之间的关系，综合判断事件是否发生.该算法具有很高的检测精度和较小的误判率，但是节点间互相通信频繁，会占用很多节点的能耗.文献[13]结合时间和空间特性提出了一种分布式邻居节点协作动态事件检测算法.但是该算法只考虑到网络能量的有效性，对容错的能力，事件检测的精确度未有很大的改善.

针对目前在上述方面的不足，本文提出一种基于预测机制的容错事件检测算法.算法主要由改进的事件检测机制和容错机制组成.利用事件发生的具有很强的时空关联性，对事件是否发生还是节点异常进行准确判断.当节点出现异常的时候，利用KNN-PSOELM预测机制进行估计，以排除错误数据对融合结果的影响，从而在节点出现故障的时候仍能保持网络的可行性.

2 网络模型与环境假设

2.1 网络结构

假设监控区域内具有n个同构的传感器节点，节点的集合可以表示为Si=(S1，S2，S3，…，Sn)，其中Si表示第i个传感器节点.每个节点通过定位设备反馈自己的地理位置.传感器的通信半径为R，当两个节点处于通信范围之内，节点间可以进行通信，否则需要通过多跳的无线连接来保持通信.如图1所示，网络中的节点采用一定的算法进行非均匀的分簇以及簇首的选择.在簇内，通过构建最优融合树的方式，节点把自身的能量信息以及采集的数据发送给簇首，簇首节点承担对簇内节点发送来的信息压缩、融合等数据处理任务以减少数据通信量.在簇间，基站通过派遣移动代理的方式，对每个簇的簇首节点进行信息的收集以此均衡传感器节点能耗.

图1 无线传感器网络结构图Fig.1 Network structure of wireless sensors network

2.2 能量模型

WSN的能量消耗主要体现在传感器节点感知、处理、接受和发送的任务上，节点传输能量主要表现有：

(1)

其中，Eti表示源节点i发送kbits的数据到相距dij的节点j所需要消耗的能量，Eri表示源节点i接收kbits数据消耗的能量，Eelec表示涉及无线电接收和传输数据的一个常量，εamp表示与信号衰减相关的常量，Ecom表示WSN网络无线通信消耗总能量.

对于簇首节点而言，节点不仅仅承担着传输能量消耗，同时还需要对簇内节点发送来的信息进行处理，因此节点的处理信息能量消耗为：

Efusion=S×q(k)

(2)

其中，q表示平均单位融合代价，它的值取决于融合数据类型以及数据相关性.

3 时空相关的事件检测模型

在一定的监测区域内，事件的发生具有很强的时空相关性.一般情况下，对单个节点而言，监测环境的数据在短时间内不会发生太大的改变，监测值是彼此相关的.只有当事件发生的时候，节点的监测值变化率会产生明显的变化.变化率的大小可以作为事件是否发生的依据.但是节点自身的检测无法消除固有错误，检测的结果存在着不可靠性，因此需要利用事件区域内部的节点以及节点的近邻节点感知信息的关联性检测[14].

定义1.瞬时测量值故障：由于传感器受到外界环境的突变等原因，导致节点在某一时刻或者某些时刻产生错误的读数.

定义2.固定测量值故障：由于传感器节点能量耗尽或者设备出现故障等原因，导致节点采样数据与环境无关，多个采样周期内持续采集到异常的数据.

3.1 时间相关性检测

传感器节点以T为时间周期进行均匀采样，为了保证节点在采样周期T内完成数据处理与发送，T值需要满足一定的条件.设传感器在时刻i的读数为Si，传感器在正常区域内读数的期望函数为En(t)，在事件区域中的读数的期望函数Ee(t)，则判定异常的阈值的R(t)=(En(t)+Ee(t))/2.当Si的值大于事件发生的期望值R(t)的时候，说明可能有事件发生或者节点发生故障；否则说明区域正常.

图2 滑动窗口机制Fig.2 Sliding window mechanism

事件特征的变化规律与事件发生的具体时刻无关，而是与距离事件发生时刻之后的一段时间有关.每一个时刻传感器节点采集数据，并对事件进行有效的判断，并把判断的值缓存在本地.为了更有效地检测事件的发生，本文在节点内部采用双重滑动窗口技术，如图2所示.在传感器节点采集到下一时刻的数据的时候，移动窗口，执行事件检测算法，从时间相关性上对事件进行判断.窗口的长度的L，Flag表示节点t时刻的状态.状态的值由公式(3)决定.

(3)

当滑动窗口的长度为1的时候，Flag=1，则表示事件发生，否则事件没发生；当滑动窗口的长度大于1且小于窗口大小的时候，则Flag=1的数量大于Flag=0的数量的时候表示事件发生，否则无事件发生；当窗口的长度与滑动窗口的长度一致的时候，设定阈值C，Flag=1的数量大于C的时候，表示事件发生.

表1 当L=3的时候滑动窗口的执行过程Table 1 Execution of the sliding window when L=3

表1描述了L=3的时候，节点内部滑动窗口实现的机制.在节点内部建立两个缓存队列DATAQUEUE和EVENTQUEUE，分别存放节点的采样值xi，以及节点的事件判断值yi.节点每个时刻采集的数据采用先进先出的方式存放在DATAQUEUE.对于节点i而言，首先在DATAQUEUE队列中执行滑动窗口技术，当满足公式(3)，在EVENTQUEUE中记录此时的事件的状态，在EVENTQUEUE队列中执行周期不同的滑动窗口技术，当达到预测的条件时候则判断事件发生，然后执行下一步操作.具体时间相关的算法检测流程描述如下：

时间相关性事件检测算法eventDetection(k,C) intcount=0; if(k==1)/*当窗口内仅有1个数据*/ if(En(t)C/2) status="NE"; else status="NN"; end elseif(k==C)/*当滑动窗口数据满时候*/ forj=1:k if(En(t)=C) status="NE"; else status="NN"; end end

3.2 空间相关性检测

虽然传感器的滑动窗口能够检测到事件的发生，但是，单个节点检测的结果存在着不可靠性，无法将节点的固定测量值故障排除.由于通常事件都会覆盖一定的区域和多数节点，物理位置相近的节点在同一时间段内采集的信息又十分相似，所以可以通过节点之间的空间相关性进行进一步的事件检测.

定义3.节点邻域：无线传感器网络中节点通信范围内所有节点的集合Nb(i)={Sj|distance(i，j)}.

节点的邻域节点在时刻t的采样的数据值分别为{x1，x2，x3，…，xn}.邻域节点的位置分布对事件检测检测准确与否有很大的关系，距离越近的节点相似程度越大，相关性也就越强，在事件检测判断中起的作用越大，反之越小.如图3所示，利用节点间的距离参数反映对其节点i决策的影响的权重wij：

(4)

式中，所有邻居节点的加权和为1.

图3 节点空间相关性模型Fig.3 Spatial correlation model of nodes

节点i的事件检测判断的置信度可以为：

(5)

当节点i自身检测到事件发生的时候，节点i执行空间相关性检测算法，利用邻域节点的信息协同判断.根据邻域节点的不同支持度，计算不同的决策信息.如果邻域节点也检测到异常数据，支持事件发生的概率越大，则节点i判断事件发生的概率也就越大，立即传输信息回基站，否则，判断数据异常来自测量的故障，进行下一步处理.具体空间相关的算法检测流程描述如下所示.

4 基于预测机制的事件检测容错算法

在事件检测过程中，考虑到环境的不确定性以及网络节点本身的不可靠性导致传感器产生错误的读数，从而影响整个网络对事件的检测.为了提高传感器对事件状态决策的可靠性，本文在事件检测算法的基础上，进一步提出一种基于预测机制的容错算法.容错机制是利用基于时间相关的预测算法.

课题组在前期工作中，为了优化移动代理的行程，采用粒子群优化算法(Particle Swarm Optimization，PSO)进行优化，并加入了自适应融合策略以及数据分流策略.鉴于传统SVM模型[15]、反向传播神经网络 (Back Propagation Neural Network，BPNN)[16]、极限学习机(Extreme Learning Machine，ELM)[17]、PSO和BP神经网络方法相结合所提出一种PSO-BPNN预测模型[18]等所存在预测精度不足的问题，课题组考虑传感器节点周期性采集的数据具有时间相关性，利用K-Nearest Neighbor(KNN)与PSO优化的极限学习机网络建立能够反应采集数据中动态依存的数学模型，减少节点中冗余数据的传输，引入流行学习中的局部线性重构的思想，结合改进的极限学习机，提出了KNN- PSOELM数据预测模型[19].优化之后的模型不仅使得原始非线性的传感器数据具有局部线性的特征，而且避免了由异常数据样本引起的病态隐层输出矩阵，使模型具有更高的预测精度与泛化能力.

空间相关性检测算法faultDetection(r) fori=1:N if(dij<=r) weight=calculatetheweightwij; end end fori=1:N if(neighbor'status==NE) NEVALUE=calculate(i,weight); else NNVALUE=calculate(i,weight); end end if(NEVALUE>NNVALUE) status="Event"; Send("EventDetected!"); else status="Fault"; Send("FaultEquipment"); end end

传感器的初始状态为NN，每隔T周期采集一次样本，在采集的过程中同时执行基于事件时间相关性的检测与空间相关性的检测.当某个时刻传感器y读数大于R(t)的时候，即自身检测到事件，将传感器的的状态置为NE.此刻，节点进入空间相关性检测，向邻居广播消息，收集邻域节点的状态，从而确定自身的状态.如果节点的状态与邻域节点的状态一致，说明传感器位于事件区域，需要发送事件发生信息回基站.反之，节点的状态与邻域节点的状态并不同，则认为自身发生了错误，此刻需要执行容错算法KNN-PSOELM.因此，本文的事件检测容错算法的流程图如图4所示.

图4 基于预测机制的事件检测容错算法的流程图Fig.4 Flow chart of the proposed prediction-based fault-tolerant aggregation algorithm

5 仿真实验

5.1 实验基本设置

本节采用Matlab软件进行仿真实验，对WSN事件检测与容错性能进行评估.假设传感器节点随机分布在100m×100m的区域内，感知的数据类型是温度数据.通常情况下，传感器的感知数据在[Tmin，Tmax]内是连续的而且服从正态分布.因此，本文随机产生一组数据，使其服从正态分布φ(i)，其中Tmin=25℃、Tmax=40℃、E(i)=32.5℃、τ=2.5℃.其分布曲线图如5所示.

图5 正态分布的温度数据Fig.5 Temperature data of normal distribution

5.2 仿真实验1

本节探讨节点通信半径，EVENTQUEUE的长度和平均事件检测数的关系，其中节点的密度为100.实验结果如图6所示，随着节点的通信半径的增加，平均事件检测的数量下降，这是因为通信范围的扩大，使得节点的领域节点数量增加，空间的相关性得到提高，使得节点异常数据被判定为事件的几率减少.当通信半径一定的时候，EVENTQUEUE的长度对事件的检测同样产生影响.EVENTQUEUE的长度增加，提高了事件的检测的准确度，排除瞬时值的故障测量引发的错误事件，因此降低了平均事件检测数量.

图6 通信范围、窗口长度和平均事件检测数的关系Fig.6 Relationship among communication range，window length and average event detection

从图7可以看出事件区域的检测数量随着节点的密度增加而逐渐递减.同理，节点总数的增加导致节点的密度增加，使得参与协作决策的成员数量增加，从而，瞬时值故障测量值或者固定值故障测量值被判定为事件的几率减少.

图7 节点密度、通信范围和平均事件检测数的关系Fig.7 Relationship among node density，communication range and average event detection

5.3 仿真实验2

本节实验结合事件检测机制与容错机制，对于出现故障的节点采取了基于预测的KNN-PSOELM容错机制，并将KNN-PSOELM模型分别与BPNN、SVR、ELM和PSOBPNN进行对比[19]，同时将本文的事件检测容错算法与基于加权中值法的事件检测容错算法[10]、基于自适应加权平均法的事件检测容错算法[11]进行比较与分析.

图8 五种数据预测模型预测结果对比Fig.8 Comparison of prediction results of five data forecasting models

一方面本节实验将KNN-PSOELM模型分别与BPNN[16]、SVR[15]、ELM[17]和PSOBPNN[18]进行对比，实验结果如图8所示[19].由图8可以明显看出，本文模型的预测值与真实值十分接近，效果明显优于其他算法.为了更好地说明KNN-PSOELM模型的优越性，下面对预测成功率进行分析.从图9可以看出在不同的预设阈值下不同预测机制预测数据的成功率[19].KNN-PSOELM模型预测的成功率都优于其他几个预测模型，当预设阈值达到0.4的时候，预测的成功率到达100%.此刻传感器节点无需发送数据，节省了能量.

图9 不同阈值下五种数据预测模型的预测成功率Fig.9 Prediction success ratio of five data prediction models under different thresholds

另一方面，将本文的事件检测容错算法与基于加权中值法的事件检测容错算法[10]、基于自适应加权平均法的事件检测容错算法[11]进行比较与分析.其中节点密度为100，通讯半径为20，EVENTQUEUE的长度为4，簇首融合的数据来源于簇内的3个节点.为了更好地可视化传感器读数，本文采用了多项式插值方法对原始的数据进行拟合，并对簇内其中一个节点做产生错误数据处理.

图10 容错之后融合结果对比Fig.10 Comparison of fusion results after fault tolerance

当节点出现故障的时候，节点利用历史的时间序列数据估计当前周期内的数据.由图10可以看出，节点发生故障的时候，节点数据融合的结果容易造成很大的偏差，自适应加权平均法(AdaptiveWeightedAverage)虽然能够有效地降低错误节点的权重，逐渐提高数据融合的精度.但是，权重的调整过程需要耗费一定的时间，容易导致前期的数据失去有效性.同时加权中值法(AggregateMedian)检测在节点故障率较高的系统中算法的性能将会显著下降.本文提出的基于预测的容错算法很好地解决两个对比算法的不足.通过对时间历史数据分析建模，然后预测得到最新的估计值.排除了错误数据的影响，保证数据融合的准确度.如图10所示，运用本文的容错算法，簇首节点融合的结果与实际的真实结果十分相近，证明了本文的容错算法的实用性和高效性.

6 结 论

针对传感器节点自身设备不稳定以及监测环境恶劣等原因造成的错误检测结果，影响数据融合的结果，从而发生错误事件检测判断，本文在已建立的有效的数据预测机制上，提出了无线传感器网络中一种新颖基于预测技术的事件检测容错算法.利用事件的时空关联性对监测区域进行事件检测，有效地提高事件检测的准确度.同时采用基于时间预测的算法进容错的计算，排除错误数据对网络的影响，在网络故障的时候，系统仍能给出正确信息的能力,保证系统的可靠性.仿真实验结果表明了算法的正确性和有效性.

[1] Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey[J].Computer Networks，2008，52(12)：2292-2330.

[2] Ren Feng-yuan，Huang Hai-ning，Lin Chuang.Wireless sensor networks [J].Journal of Software，2003，14(7)：1282-1291.

[3] Zhang Ji-jun，Liu Yun-fei，Zhao Xin.Review of data aggregation system structure in wireless sensor networks[J].Transducer and Microsystem Technologies，2009，28(10)：1-4.

[4] Wang Yao-nan，Li Shu-tao.Multisensor information fusion and its application：a survey [J].Control and Decision，2001，16(5)：518-522.

[5] Singhal S，Gankotiya A K，Agarwal S，et al.An investigation of wireless sensor network：a distributed approach in smart environment[C].Advanced Computing & Communication Technologies (ACCT)，2012 Second International Conference on.IEEE，2012：522-529.

[6] Zhang Shu-kui，Wang Yi-huai，Cui Zhi-ming，et al.Event region fault-tolerant detection algorithm based on aggregation tree [J].Journal on Communications，2010,31(9)：74-87.

[7] Nguyen-Thanh N，Koo I.Empirical distribution-based event detection in wireless sensor networks：an approach based on evidence theory [J].Sensors Journal，IEEE，2012，12(6)：2222-2228.

[8] Krishnamachari B，Iyengar S.Distributed Bayesian algorithms for fault-tolerant event region detection in wireless sensor networks [J].Computers，IEEE Transactions on，2004，53(3)：241-250.

[9] Chen J，Kher S，Somani A.Distributed fault detection of wireless sensor networks[C].Proceedings of the 2006 Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS)，ACM，2006：65-72.

[10] Gao Jian-liang，Xu Yong-jun，Li Xiao-xiong.Weighted-median based distributed fault detection for wireless sensor networks[J].Journal of Software，2007，18(5)：1208-1217.

[11] Ding M，Chen D，Thaeler A，et al.Fault-tolerant target detection in sensor networks [C].Proceedings of 2005 IEEE Wireless Communications and Networking Conference (WCNC) ,IEEE，2005：2362-2368.

[12] Huang Ri-mao，Qiu Xue-song，Gao Zhi-peng，et al.A neighbor-data analysis method for fault detection in wireless sensor networks [J].Journal of Beijing University of Posts and Telecommunications，2011，34(3)：31-34.

[13] Enemark H J，Zhang Y，Dragoni N，et al.Energy-efficient fault-tolerant dynamic event region detection in wireless sensor networks[C].Proceedings of the 81st Vehicular Technology Conference (VTC Spring)，IEEE，2015：1-5.

[14] Xu Xiao-long，Geng Wei-jian，Yang Geng，et al.An efficient fault-tolerant event and event boundary detection algorithm for wireless sensor networks [J].Journal of Computer Research and Development，2015，51(5)：997-1008.

[15] Guo Yi-nan，Cheng Jian，Yang Mei.Selection method for hyper-parameters of support vector regression by chaotic cultural algorithm [J].Control and Decision，2010，25(4)：525-530.

[16] Takayama K，Fujikawa M，Nagai T.Artificial neural network as a novel method to optimize pharmaceutical formulations[J].Pharmaceutical Research，1999，16(1)：1-6.

[17] Huang G B，Zhou H，Ding X，et al.Extreme learning machine for regression and multiclass classification[J].Systems，Man，and Cybernetics，Part B：Cybernetics，IEEE Transactions on，2012，42(2)：513-529.

[18] Lin J，Guo W Z，Chen G L，et al.A PSO-BPNN-based model for energy saving in wireless sensor networks[C].International Conference on Machine Learning and Cybernetics (ICMLC)，IEEE，2009，2：948-952.

[19] Hong Wei，Guo Kun，Guo Wen-zhong.Prediction model in wireless sensor network based on optimized extreme learning machine regression [J].Journal of Chinese Computer Systems，2016，37(11)：2478-2482.

附中文参考文献：

[2] 任丰原，黄海宁，林 闯.无线传感器网络[J].软件学报，2003，14(7)：1282-1291.

[3] 赵继军，刘云飞，赵 欣.无线传感器网络数据融合体系结构综述[J].传感器与微系统，2009，28(10)：1-4.

[4] 王耀南，李树涛.多传感器信息融合及其应用综述[J].控制与决策，2001，16(5)：518-522.

[6] 张书奎，王宜怀，崔志明，等.基于融合树的事件区域检测容错算法[J].通信学报，2010，31(9)：74-87.

[10] 高建良，徐勇军，李晓雄.基于加权中值的分布式传感器网络故障检测[J].软件学报，2007，18(5)：1208-1217.

[12] 黄日茂，邱雪松，高志鹏，等.无线传感器网络中邻居数据分析的故障检测方法[J].北京邮电大学学报，2011，34(3)：31-34.

[14] 徐小龙，耿卫建，杨 庚，等.高效容错的无线传感网事件及其边界检测算法[J].计算机研究与发展，2015，51(5)：997-1008.

[15] 郭一楠，程 健，杨 梅.支持向量回归超参数的混沌文化优化选择方法[J].控制与决策，2010，25(4)：525-530.

[19] 洪 伟，郭 昆，郭文忠.无线传感器网络中极限学习机回归优化预测模型[J].小型微型计算机系统，2016，37(11)：2478-2482.