基于粗集的WSN节点故障诊断算法研究

摘要：本文运用粗糙集及其数据约简理论设计一种改进的启发式WSN节点故障诊断算法来消除冗余，精简节点故障诊断决策表。结果表明，改进后的算法能够实现更准确和更高效的WSN节点的故障检测。

关键词：无线传感器网络；故障诊断；粗糙集；属性约简

中图分类号：TP393.04文献标识码：A文章编号：1007-9599 (2011) 03-0000-02

WSN Node Fault Diagnosis Algorithm Research Based on Rough Set

Cheng Pu1,Du Ying2

(puter Center,Henan University,KaiFeng475004,China;2.College of Computer and Information Engineering,Henan University,KaiFeng475004,China)

Abstract:The improved heuristic fault diagnosis reduction algorithm for the nodes was designed on rough set to reduce the redundancy of the decision-making table.The results show that a more accurate and effective fault diagnosis based on rough set realized.

Keywords:Wireless sensor network;Fault diagnosis;Rough set;Attribute reduction

一、引言

无线传感器网络（WSN，Wireless Sensor Network）是近年来的新技术研究热点之一。受应用环境，制作工艺和其他未知因素影响，WSN节点容易出现各种故障，这会降低或失去WSN预定功能，甚至会造成严重的损失或网络瘫痪。对WSN节点的故障检测能够有效诊断节点异常，预防或消除故障，保证网络正常运行。针对于此国内外已经开展了相关研究[1-4]。但这些研究或算法复杂，消耗资源过多，或诊断准确性不足。本文将在改进基于粗糙集及其数据约简理论的设计算法基础上，进一步简化决策过程，以适应资源有限的WSN的节点故障诊断。

二、基于粗集的属性约简算法

粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。利用粗集理论的属性简约算法能够去除WSN节点故障征兆的冗余信息，减少故障诊断决策所需的征兆属性，从而达到提高故障诊断准确性和降低能耗的目的。

算法设计如下，设WSN节点故障诊断决策系统为 ， 是论域，对应被诊断节点对象集；C={c[k]，k=1，2，…，m}和 分别为条件属性集和决策属性集，分别对应节点故障征兆属性集和节点故障类型属性集；且 为被诊断子节点 在故障征兆属性c[k]上的取值。

定义可辨识矩阵为 ，并且令 ，式中 （i，j=1，2，…，n）为可辨识矩阵中第i行与第j列交点处的元素；n为被诊断子节点数； 。

由于求取信息系统的全部约简是NP复杂问题，复杂度太大也没有必要，因此可利用条件属性的重要性[4]，设计启发式约简算法，只求取全部约简中的某一个或某一些。

文[5]提出了两种重要的启发式思想：

（1）属性在可辨识矩阵中出现的次数越多，该属性的重要性越大；

（2）在可辨识矩阵中属性项越短，属性的重要性越大；

根据思想（1）和（2）可知：条件属性重要性与属性频率有关。据此提出一种新的计算条件属性重要性的方法：

（1）条件属性c[k]的重要性为其在可辨识矩阵内出现的加权频率 ，式中 表示属性c[k]在可辨识矩阵中出现的次数；counts（c[k]）表示可辨识矩阵中含有c[k]的项中的所有属性总个数。这体现出属性在可辨识矩阵中出现频率越大，该属性重要性越大。

（2）决策属性D对属性c[k]的依赖度 ，式中 为U中所有根据条件属性c[k]的分类可以准确划分到决策属性D的等价类中去的对象集合。当条件属性频率相同时，利用K判断条件属性的重要性。此时，K越大的条件属性越重要。

根据上面定义的条件属性重要性判断方法，本文设计了一个启发式的故障检测约简算法，算法描述如下：

（1）求S相应的可辨识矩阵M，初始化 ，令P（c[k]）=0；

（2）找出M中只含有单个条件属性 的元素，令 ，令 ；

（3）构造矩阵 ，其元素取值为 ，令M=M-N，若M=0则结束；否则，B=C-R；

（4）对 ，计算 在 中的加权频率，选择加权频率最大的 ；若存在最大的加权频率相同的多个属性，则选择条件D对其依赖度K最大的 （可能有多个）；令 ；

（5）转第（3）步。

三、算例和结果

采用文[3]中使用的WSN节点故障信息，并得到故障样本决策表（见表1）。其中c[1]-c[8]表示故障征兆，d1-d5表示故障类型，U表示采样节点。

调用上述启发式的WSN节点故障诊断约简算法，步骤如下：

（1）根据表1求出对应的可辨识矩阵M为

式中子矩阵为：

其中，矩阵元素项中分别以1-8代表c[1]-c[8]。

（2）由可辨识矩阵可知，c[3]和c[5]为核属性。

（3）去掉可辨识矩阵M中包含核属性的项后，得到可辨识矩阵N；计算N中条件属性的加权频率，其中P（c[1]）=1.333，P（c[2]）=P（c[4]）=P（c[7]）=2.167，P（c[8]）=3.111。则取加权频率最大的属性c[8]。

（4）去掉包含属性c[8]的项后，得到新的可辨识矩阵N；计算新的N中条件属性的加权频率，P（c[2]）=P（c[4]）=1.5。由于加权频率相同，分别计算决策属性D对c[2]和c[4]的依赖度。可得，决策属性D对c[2]的依赖度为0.25，对c[4]的依赖度为0。所以选择c[2]。

（5）去掉包含属性c[2]的项后，可辨识矩阵变为0，算法结束。

故得到条件属性的约简结果为 ，则得到表2所示的WSN节点故障诊断决策表。

由表2可见，在不影响决策分类的情况下，简化了结果。在对相同的决策表执行属性约简过程中，文[3]中算法的约简结果为3个，再根据实际情况人工选择最适合约简结果；而改进后的约简算法能够直接找到最适合约简结果，因此改进后的约简算法能够更准确地找到约简结果，效率更高。

四、结束语

本文在改进基于粗糙集的数据约简算法的基础上，提出一种启发式的WSN节点故障诊断方法，在能量有限的情况下能够有效准确地进行故障检测，算例结果证明了该方法的有效性。

参考文献：

[1]Khilar PM,Mahapatra S.Intermittent fault diagnosis in wireless sensor networks[C].Proceedings of 10th International Conference on Information Technology.[Sl].IEEE CS Press,2007:145-147

[2]杨建宁,成立,张荣标.多传感器多模型相互作用的数据关联方法[J].江苏大学学报:自然科学版,2005,26,5:444-447

[3]雷霖,代传龙,王厚军.基于Rough set理论的无线传感器网络节点故障诊断[J].北京邮电大学学报,2007,30,4:69-73

[4]沈敏,张荣标,冯友兵.基于粗糙集的温室无线传感网络节点故障诊断[J].江苏大学学报:自然科学版,2009,30,5:510-522

[5]胡可云.基于概念格和粗糙集的数据挖掘方法研究[D].北京:清华大学,2001

[作者简介]

程普（1981-），男，助教，硕士，研究方向：无线传感器网络。

杜莹（1981-），女，讲师，硕士，研究方向：自然语言理解。