| 主权项 |
基于数据快照图的异常检测方法，其特征在于：包括如下步骤：(1)对无线传感器网络当前监测区域内的检测数据进行采集和预处理，确定事件相关区域；(2)获取与当前事件相关的数据集，用图模型抽象概括事件数据集，将事件数据集转换成事件数据快照图；(3)采用基于结构关联度的图相似查询算法，在事件模式图数据库中进行查询，查找与当前事件的事件数据快照图相似的事件模式图，判断当前事件的类型；所述事件模式图数据库为事件模式图的集合，所述事件模式图为事件数据快照图，是对事件类型的抽象描述；所述事件模式图通过领域专家知识获取或基于数据分析获取，是一种基于数据快照的事件图；所述数据快照为事件发生时刻传感器网络中各个节点的数据集，基于该数据集建立的事件图为事件时刻的快照图，也是该事件的事件模式图；所述基于结构关联度的图相似查询算法具体为，从图数据中抽取基本结构，以基本结构之间的关联度转化图数据为基本结构序列，将图相似查询问题转化为序列相似性查询问题；所述步骤(1)中，基于传感器节点的物理相关性与数据相关性建立节点关联图，根据节点关联图确定事件区域，所述节点关联图包括全局节点关联图和全局节点关联图的子图，节点关联图的建立方式如下：t时刻的节点关联图形式化表示为：G<sub>t</sub>＝<V,E,ID,f<sub>v</sub>>其中：V为图的顶点集合，包含所有事件相关顶点；E为图的边集合；ID为顶点的编号集合；f<sub>v</sub>:V→ID是顶点的标号函数，图顶点与传感器节点一一对应；无线传感器网络的每一个节点都构成节点关联图上的一个顶点；设d(v<sub>i</sub>)<sub>t</sub>为顶点v在t时刻的监测数据，图的边集合E构造原则如下：对于任意两个顶点v<sub>1</sub>,v<sub>2</sub>∈V，若v<sub>1</sub>与v<sub>2</sub>相对应的传感器节点为单跳通信邻居，或v<sub>1</sub>与v<sub>2</sub>相对应的传感器节点为k跳内通信邻居且存在函数f<sub>1</sub>与f<sub>2</sub>使得f<sub>1</sub>(d(v<sub>1</sub>)<sub>t</sub>)＝f<sub>2</sub>(d(v<sub>2</sub>)<sub>t</sub>)，则存在边(v<sub>1</sub>,v<sub>2</sub>)∈E；所述事件相关区域确定方法为：在事件检测的时刻t，对于任意顶点v<sub>i</sub>∈V，若|d(v<sub>i</sub>)<sub>t‑1</sub>‑d(v<sub>i</sub>)<sub>t</sub>|/|d(v<sub>i</sub>)<sub>t‑1</sub>+d(v<sub>i</sub>)<sub>t</sub>|≤e，则顶点v<sub>i</sub>为事件相关顶点，t时刻所有事件相关顶点所在的区域为事件相关区域；其中常数e为预设值；确定了事件边界后的节点关联图是全局节点关联图的子图，全局节点关联图的子图定义如下：Ge<sub>t</sub>＝<V,E,ID,f<sub>v</sub>>其中：V为图的顶点集合，包含所有事件相关顶点，<img file="FDA0000899971990000021.GIF" wi="371" he="79" />E为图的边集合，<img file="FDA0000899971990000022.GIF" wi="373" he="80" />ID为顶点的编号集合，<img file="FDA0000899971990000023.GIF" wi="420" he="75" />f<sub>v</sub>:V→ID是顶点的标号函数，图顶点与传感器节点一一对应；所述步骤(2)中，用图模型抽象概括事件数据集，将事件数据集转换成事件数据快照图，所述数据快照与事件数据快照图如下：21)无线传感网数据快照S定义如下：对于具有k个节点的无线传感网N，其包含节点为{n<sub>1</sub>,n<sub>2</sub>,…,n<sub>k</sub>}，N在时刻t的数据快照为集合{d(n<sub>1</sub>)<sub>t</sub>,d(n<sub>2</sub>)<sub>t</sub>,…,d(n<sub>k</sub>)<sub>t</sub>}；22)t时刻的事件数据快照图Gs<sub>t</sub>由t时刻的节点关联图Ge<sub>t</sub>根据节点数据相关性计算得到，其形式化表示为：Gs<sub>t</sub>＝<V,E,ID,DV,f<sub>v</sub>,g<sub>v</sub>>其中：DV＝{d(v<sub>i</sub>)<sub>t</sub>}是事件区域内所有传感器节点在t时刻的监测值；g<sub>v</sub>:V→DV是顶点的数据映射函数；t时刻的事件数据快照图Gs<sub>t</sub>的顶点集与t时刻的节点关联图Ge<sub>t</sub>的顶点集相同，包含事件区域内的所有传感器节点；t时刻的事件数据快照图Gs<sub>t</sub>的边集E(Gs<sub>t</sub>)构造如下：a)对于任意边(v<sub>1</sub>,v<sub>2</sub>)∈E(Ge<sub>t</sub>)，若(d(v<sub>1</sub>)<sub>t</sub>‑d(v<sub>2</sub>)<sub>t</sub>)/(d(v<sub>1</sub>)<sub>t</sub>+d(v<sub>2</sub>)<sub>t</sub>)>e，则存在有向边<v<sub>2</sub>,v<sub>1</sub>>∈E(Gs<sub>t</sub>)；b)对于任意边(v<sub>1</sub>,v<sub>2</sub>)∈E(Ge<sub>t</sub>)，若(d(v<sub>2</sub>)<sub>t</sub>‑d(v<sub>1</sub>)<sub>t</sub>)/(d(v<sub>1</sub>)<sub>t</sub>+d(v<sub>2</sub>)<sub>t</sub>)>e，则存在有向边<v<sub>1</sub>,v<sub>2</sub>>∈E(Gs<sub>t</sub>)；c)对于任意边(v<sub>1</sub>,v<sub>2</sub>)∈E(Ge<sub>t</sub>)，若|(d(v<sub>1</sub>)<sub>t</sub>‑d(v<sub>2</sub>)<sub>t</sub>)|/(d(v<sub>1</sub>)<sub>t</sub>+d(v<sub>2</sub>)<sub>t</sub>)<e，则存在有向边<v<sub>2</sub>,v<sub>1</sub>>∈E(Gs<sub>t</sub>)，且存在有向边<v<sub>1</sub>,v<sub>2</sub>>∈E(Gs<sub>t</sub>)；其中常数e为预设值；所述事件数据快照图是有向图，用于描述无线传感器网络事件区域中各个节点的数据状态以及数据状态之间的联系；23)对事件数据快照图进行简化，所述简化方式为将传感器节点进行合并，节点合并的规则为：a)合并节点的数据必须近似相等：即对v<sub>2</sub>,v<sub>1</sub>∈V(Gs<sub>t</sub>)，若<v<sub>1</sub>,v<sub>2</sub>>∈E(Gs<sub>t</sub>)且|(d(v<sub>1</sub>)<sub>t</sub>‑d(v<sub>2</sub>)<sub>t</sub>)|/(d(v<sub>1</sub>)<sub>t</sub>+d(v<sub>2</sub>)<sub>t</sub>)<e，则合并v<sub>2</sub>,v<sub>1</sub>为一个新的节点；b)当近似相等的两个以上节点合并为一个新的节点时，将与这些节点相关联的边都关联到新节点上；所述步骤(3)中，基于结构关联度的图相似算法具体为，首先基于结构关联度提取图数据的结构特征序列，将图数据相似查询转化为结构特征序列相似查询，然后在事件模式图数据库中查找与事件数据快照图相似的事件模式图，判断当前事件的类型；具体过程包括入下步骤：31)定义图数据的基本结构为环型结构、星型结构和线型结构，三种图数据的基本结构定义如下：环型结构：图中一系列的点集合形成一个封闭环，且该封闭环上的边数大于等于3，记环形结构为cycle(s)，s＝{v|v∈V∧v节点构成一个环}，其中该封闭环不能嵌套其他环，即该封闭环为简单环；星型结构：图中某一核心顶点v<sub>0</sub>连接其它若干个顶点，且其它任意两个顶点之间都不连通，满足degress(v<sub>0</sub>)≥3，记星型结构为star(v<sub>0</sub>,s)，s＝{v|v<sub>0</sub>,v∈V∧v是v<sub>0</sub>的邻节点}，degress(v<sub>0</sub>)表示节点v<sub>0</sub>的度；线型结构：由一串顶点端到端相连的结构，记线型结构为line(s)，s＝{v|v∈V∧degress(v)≤2}，degress(v)表示节点v的度；32)基本结构提取步骤如下：①用深度遍历方法和回溯思想先找出图中所有的环型结构；②比较其中任意两个环型结构A,B，若A是B的子集，即环型结构B包含环型结构A，则删除环型结构B；③循环执行步骤②直到没有包含其他环型结构的环型结构，得到所有简单环的环形结构；④计算图中每个顶点的度数，度数大于等于3的作为一个星型结构；⑤计算图中每个顶点的度数，如果某个顶点度数等于1并且其邻接点的度数小于或等于2，则继续遍历邻接点，直到某个顶点的度数大于2为止，由此形成一个线型结构；33)基于结构关联度的图数据结构特征序列提取方法如下：根据每个结构的重要程度不同，对基本结构的序列进行重要程度的排序，将图结构数据转换成基本结构的序列，用结构之间的关联度衡量每个结构的重要程度：关联：一个图中的任意两个基本结构s<sub>i</sub>和s<sub>j</sub>：如果满足cvNum(s<sub>i</sub>,s<sub>j</sub>)≥1，则结构s<sub>i</sub>和结构s<sub>j</sub>是关联的，记为incident(s<sub>i</sub>,s<sub>j</sub>)＝1；如果cvNum(s<sub>i</sub>,s<sub>j</sub>)＝0，则incident(s<sub>i</sub>,s<sub>j</sub>)＝0，说明结构s<sub>i</sub>和结构s<sub>j</sub>不关联；将关联形式化定义为：<maths num="0001" id="cmaths0001"><math><![CDATA[<mrow><mi>i</mi><mi>n</mi><mi>c</mi><mi>i</mi><mi>d</mi><mi>e</mi><mi>n</mi><mi>t</mi><mrow><mo>(</mo><msub><mi>s</mi><mi>i</mi></msub><mo>,</mo><msub><mi>s</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>=</mo><mfenced open = "{" close = ""><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mrow><mi>i</mi><mi>f</mi></mrow></mtd><mtd><mrow><mi>c</mi><mi>v</mi><mi>N</mi><mi>u</mi><mi>m</mi><mrow><mo>(</mo><msub><mi>s</mi><mi>i</mi></msub><mo>,</mo><msub><mi>s</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>≥</mo><mn>1</mn></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><mi>i</mi><mi>f</mi></mrow></mtd><mtd><mrow><mi>c</mi><mi>v</mi><mi>N</mi><mi>u</mi><mi>m</mi><mrow><mo>(</mo><msub><mi>s</mi><mi>i</mi></msub><mo>,</mo><msub><mi>s</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>=</mo><mn>0</mn></mrow></mtd></mtr></mtable></mfenced></mrow>]]></math><img file="FDA0000899971990000041.GIF" wi="853" he="166" /></maths>其中cvNum(s<sub>i</sub>,s<sub>j</sub>)表示结构s<sub>i</sub>和结构s<sub>j</sub>的公共顶点个数，且i≠j；基于关联结构数量的关联度：给定一个图g，假设含有N个基本结构，则第i个基本结构s<sub>i</sub>的关联度为：<img file="FDA0000899971990000042.GIF" wi="838" he="132" />其中：1≤i≤N，sNum_CD(s<sub>i</sub>)≤(N‑1)；如果一个基本结构s与k个基本结构关联，则这个基本结构s的关联度sNum_CD(s)＝k；根据上述定义，将事件数据快照图转化为基于关联度的基本结构序列；34)图数据的结构特征序列相似性查询算法，具体步骤如下：通过编辑距离计算源字符串S与目标字符串T的相似度；所述编辑距离是指由S变化到T所需要的最小编辑操作的数量或代价，其中所提出的编辑操作是指对字符串的某一个位置的字符进行删除、插入、替换的操作，每一个转换操作都有一个相关的代价，一个给定的转换操作序列的代价等于序列中单个操作的代价之和；在事件数据快照图基本结构序列中，层次越是靠前的结构关联度越大，即重要性越大，则此结构代表图的主特征的概率就越大；结构序列中第一个结构在图中的重要性最大，编辑此结构所需的代价应该也是最大的，由此定义一种单调递减的指数函数f(x)＝a<sup>‑x</sup>作为每次变更一个字符操作的代价函数；序列编辑距离相似性：给定序列数据库Set＝{s<sub>1</sub>,s<sub>2</sub>,…,s<sub>n</sub>}，一个查询序列qStr和一个编辑距离阈值τ，序列相似性查询结果为返回序列数据库Set中所有满足SED(qStr,s<sub>i</sub>)<τ的序列s<sub>i</sub>；SED表示字符串编辑距离算法；给定一个查询序列，字符串编辑距离计算序列数据库中的序列与查询图序列之间的编辑距离，则结果返回序列数据库中所有与查询序列编辑距离小于给定代价阈值τ的序列数据。 |
