随着越来越多无线传感器网络(WSN, wireless sensor network)应用的部署，感知节点运行状态监测和异常检测成为保障WSN应用正常工作、提高WSN应用可用性的关键技术之一. WSN具有应用定制的特性，感知节点的状态与行为在不同应用中具有较大的差异，为感知节点运行时的状态监测和异常检测带来了巨大的挑战. Zhou等^[1]提出对节点程序的执行轨迹进行区间划分，并将区间内指令周期数作为程序动态运行时的特征，应用分类支持向量机，对由瞬态错误导致的异常区间进行检测；Zhou等^[2]从节点执行函数调用轨迹中挖掘并建立工作流模型，将程序运行时的行为与已知工作流模型对比检测异常；马峻岩等^[3]提出了一种基于有限状态机模型断言检查的故障检测算法，并借助轻量级有限状态签名算法检测运行时状态异常变化；Khan等^[4]提出了一种改进的关联规则算法实现日志事件序列频繁判别模式挖掘，并基于挖掘模式实现异常检测；Dong等^[5]应用主成份分析和t检验方法对多个时间窗口观测的节点函数调用频数进行统计分析，实现节点的异常检测与诊断；Lu等^[6]以嵌入式系统事件序列与序列事件之间间隔时间为特征，提出了一种硬件辅助的嵌入式异常检测方法.

与现有研究大多从程序函数、事件序列角度出发对感知节点状态进行建模不同，笔者提出的基于任务转移概率的异常检测方法(T2PAD, task transition probability based anomaly detection)从感知节点任务运行的周期性与关联性特征出发，提出了基于节点任务转移概率的运行状态特征描述方法，并基于该特征实现异常检测.

1 感知节点状态模型

感知节点使用的操作系统通常采用事件驱动执行模型和轻量级线程的结构设计，这种设计可以在单栈开销下执行多并发任务.笔者所述任务对应感知节点中操作系统内核调度器的调度实体.以TinyOS为例对异常检测方法进行阐述，但T2PAD同样适用于其他具有类似调度机制的WSN操作系统平台.

1.1 任务转移概率

感知节点所有的任务构成一个任务集合.假设感知节点有u个任务，则其任务集合表示为

$ E=\left\{T_{1}, T_{2}, T_{3}, \cdots, T_{u}\right\} $

(1)

定义1  (任务转移)   从当前任务执行结束，到下一任务开始执行的过程构成一次任务转移.

定义2   (转移频数)   转移频数的形式为

$ M\left\{X(n)=t_{i+n} | X=t_{i}\right\}, t_{i}, t_{i+n} \in E, n \geqslant 1 $

(2)

在指定的统计窗口内，t_i为第i个被执行的任务.节点从处于执行任务t_i状态，经过n次任务转移处于执行任务t_i+n状态的频数称为从t_i到t_i+1的n步转移频数，其中当n=1时称为一步转移频数.

定义3   (转移概率)  转移概率的形式为

$ P\left\{X(n)=t_{i+n} | X=t_{i}\right\}, t_{i}, t_{i+n} \in E, n \geqslant 1 $

(3)

在指定的统计窗口内，节点从处于执行任务t_i状态，经过n次任务转移处于执行任务t_i+n状态的观测概率称为从t_i到t_i+1的n步转移概率，其中当n=1时称为一步转移概率.

1.2 状态模型

为了方便表示，当t_i=T_i, t_i+1=T_j，M_ij表示T_i到T_j的一步转移频数，即由定义2有

$ M_{i j}=M\left\{X(1)=T_{j} | X=T_{i}\right\} $

P_ij表示T_i到T_j的一步转移概率，由定义3有

$ P_{i j}=P\left\{X(1)=T_{j} | X=T_{i}\right\} $

在指定的统计窗口内，感知节点的状态定义为如下一步任务转移概率矩阵：

$ \boldsymbol{S}=\left\{\begin{array}{ccccc}{P_{11}} & {P_{12}} & {P_{13}} & {\cdots} & {P_{1 u}} \\ {P_{21}} & {P_{22}} & {P_{23}} & {\cdots} & {P_{2 u}} \\ {P_{31}} & {P_{32}} & {P_{33}} & {\cdots} & {P_{3 u}} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {P_{u 1}} & {P_{u 2}} & {P_{u 3}} & {\cdots} & {P_{u u}}\end{array}\right\} $

(4)

状态S为节点在时间窗口w内所有任务的一步转移概率.当T_i到T_j之间没有观测到转移时，P_ij=0.

转移概率P_ij的计算是取一定长度的时间窗口w，统计该窗口内每个任务T_i到任务T_j一步转移频数M_ij，由式(5)可计算得到转移概率：

$ P_{i j}=\frac{M_{i j}}{M_{i}}, \quad M_{i}=\sum\limits_{j^{\prime}=0}^{u} M_{i j^{\prime}} $

(5)

其中M_i为所有从任务T_i出发的一步转移频数之和.通常一个感知节点有数个正常的状态，在不同的情况下节点表现出不同的状态，节点工作的状态序列在时间轴上表现为状态流.

定义4   (状态流)  节点在连续时间窗口下得到的状态序列定义为状态流Γ, Γ的形式为

$ \mathit{\Gamma}=\left\langle\boldsymbol{S}_{1}, \boldsymbol{S}_{2}, \boldsymbol{S}_{3}, \boldsymbol{S}_{4}, \cdots \boldsymbol{S}_{i}, \cdots\right\rangle $

(6)

其中S_i表示节点在时间窗口w_i的状态.

1.3 状态相似性判定

T2PAD采用余弦相似度来评估2个状态的相似程度.设状态S₁、S₂矩阵中2个对应的行向量为V_i¹、V_i², 夹角为θ_i，满足如下关系：

$ \cos {\theta _i} = \frac{{\mathit{\boldsymbol{V}}_i^1\mathit{\boldsymbol{V}}_i^2}}{{\left\| {\mathit{\boldsymbol{V}}_i^1} \right\|\left\| {\mathit{\boldsymbol{V}}_i^2} \right\|}} $

(7)

定义集合φ为2个状态S₁、S₂中所有对应行向量夹角的集合，即φ={θ₁, θ₂, θ₃, …, θ_u}.规定对于∀θ_n>Q, θ_n∈φ，则认为S₁≠S₂，即S₁与S₂不相似，其中Q为阈值.即当2个状态中任意一组对应的行向量夹角θ>Q时，T2PAD判定2个状态为不同的状态. Q的取值由具体的检测需求确定，Q的值越小，状态分类的粒度越细，对异常的敏感性也越高.

2 任务特征分析

图 1所示为TinyOS某应用中一个任务的一步转移频数变化情况.可以看出，该任务后会有7个不同的任务可能被执行，且分别与这7个任务的一步转移概率呈现一种稳定的特征.这主要由于WSN应用多为周期性的重复任务，且任务之间具有一定的相关性，比如完成传感器读取任务后，会执行数据发送任务.

为了进一步验证关于感知节点任务转移概率的特征，实验使用9个不同规模的TinyOS官方应用，构建任务执行序列数据集，并对数据集进行分析得到表 1.可以看出，其任务执行具有如下特点：1)少量的任务占据了大部分的任务转移；2)系统长时间运行过程中会出现多个状态，通常代码规模越大状态数越多；3)在不同的负载情况下，通过设定一个合适的状态相似度阈值(实验中阈值Q=15)，可以将由节点任务执行序列导出的状态流合并成规模较小的有限状态.

上述实验结果表明，感知节点任务转移概率可以作为构建节点运行状态模型的一种特征描述方式.同时，借助状态相似度度量公式和相似度判别阈值，可以对节点随时间变化的状态特征进行分析.

3 异常状态检测方法

感知节点工作实质是一系列任务的顺序执行. T2PAD根据指定的时间窗口w将节点任务执行序列划分为若干任务执行子序列.基于任务转移概率，计算出该时间窗口内节点的状态矩阵.从一系列的时间窗口，T2PAD得到节点运行的状态流.

T2PAD通过对节点实际运行状态与正常状态的相似度评估来实现异常状态的检测. 图 2为T2PAD系统结构.通过部署前的测试构建初始状态表，并以表中的状态对异常进行检测，检测步骤如下.

步骤1  获得任务序列

T2PAD通过在系统内核调度器调度任务之前捕获任务ID进而获得任务序列.

步骤2   任务序列转换为状态流

将任务序列按照时间窗口w划分为子序列，对于每个子序列依据1.2节所述方法将其转换为一个状态.

步骤3   异常状态检测

将状态流中的每个状态与状态表中正常状态依据1.3节所述方法进行相似性判断，判断的阈值为Q.如果与状态表中所有状态的相似性均大于Q，则认为该状态为异常状态，报告异常状态并提交导致相似性大于Q的任务，为寻找异常的原因与异常的定位提供代码级帮助.

步骤4   状态表更新

对于报告为异常的状态经过检查后发现其是一个在状态表中不存在的正常状态，则将其添加至状态表.

T2PAD有2个可调参数：w、Q.其中，w为统计任务转移概率的时间窗口大小；Q为利用余弦相似度评估状态矩阵间差异的阈值. w的值越大，对持续较短时间的异常越不敏感，但其对于长期异常的检测的准确性越高；Q的值的大小与异常检测的灵敏度相关，Q值越大漏报率会升高，误报率会下降，反之漏报率下降，误报率越高.

4 实例分析

感知节点异常检测研究领域目前没有标准的异常测试集，现有研究大多通过实例分析验证其所提方法有效性.实例1来自TinyOS开源代码库，实例2为笔者开展实验过程中遇到的真实问题，实例3来自文献[5].实例1和实例2的异常与软件缺陷有关，实例3的异常则与外部存储器硬件故障有关.在实例2中，发现了TinyOS网络协议中一个新的缺陷，利用T2PAD给出的异常信息找到了异常程序在源码中的位置，并对其进行了改善.

实验使用TinyOS2.1.x嵌入式操作系统和Telosb节点作为程序编译目标平台，使用Cooja仿真器运行网络程序^[7].通过对TinyOS内核调度器代码的修改，实现了任务的记录.通过修改Cooja底层代码，在实例3中模拟硬件故障.

4.1 实例1：分发协议定时器溢出

实例1中TinyOS的Trickle协议定时器代码存在溢出缺陷(该版本在GitHub网站TinyOS主仓库commit号为11ff964)：当分发节点丢失一段时间(约10 min)，与分发节点通信的接收节点会持续执行某一个任务而无法进入低功耗模式.实验使用TinyOS例程TestDissemination对该缺陷进行测试.设置时间窗口参数w=4.5 min，阈值Q=13.

实验包含1个分发节点、3个接收节点，分发节点在135 min后死亡实验中1个接收节点正常状态模型矩阵如下：

$ {\mathit{\boldsymbol{S}}_0} = \left\{ {\begin{array}{*{20}{c}} {0.37}&{0.539}&0&0&0&{0.091} \\ 0&0&0&{0.003}&0&{0.923} \\ 0&0&0&0&{0.074}&0 \\ {0.429}&{0.536}&0&0&0&{0.036} \\ 0&{0.018}&0&{0.428}&0&{0.5} \\ {0.448}&{0.483}&0&0&{0.069}&0 \end{array}} \right\} $

(8)

$ {\mathit{\boldsymbol{S}}_1} = \left\{ {\begin{array}{*{20}{c}} {0.356}&{0.548}&0&{0.006}&0&{0.09} \\ {0.005}&0&0&0&{0.064}&{0.931} \\ 0&0&0&0&0&0 \\ {0.577}&{0.423}&0&0&0&0 \\ 0&{0.021}&0&{0.479}&0&{0.5} \\ {0.455}&{0.483}&0&{0.002}&{0.06}&0 \end{array}} \right\} $

(9)

图 3所示为感知节点的状态流以及对状态的检测结果，图中数值为状态的编号.可以看出，T2PAD准确地检测到了程序的异常行为. 表 2给出了相应的异常任务.该异常原因为TrickleTimerImplP组件的代码缺陷，而由异常任务0x000f可以为定位该代码缺陷的范围提供线索.

进一步研究了T2PAD参数w、Q与误报率的关系.由图 4可知，随着时间窗口的增大，误报率将呈下降趋势，但时间窗口过大，T2PAD对于持续时间较短的异常状态敏感性降低.由图 5可知，随着阈值的增大，误报率呈下降趋势.

4.2 实例2：节点移动导致网络传输异常

实例2由10个运行MultihopOscilloscope应用的节点组成，该应用使用TinyOS汇聚树协议进行网络通信.实验测试了节点移动性对网络的影响，并使用T2PAD对这种影响进行监测.实验包含10个节点，其中1号节点为根节点，2号节点和3号节点与1号节点1跳相连，4号节点在实验开始时仅能通过3号节点路由到根节点.实验仿真时间2 h后，4号节点由于位置移动，离开了3号节点的通信范围，进入了2号节点的通信范围，仅能通过2号节点路由到根节点，整个实验过程持续4 h.设置T2PAD的时间窗口参数w=4.5 min，阈值Q=13. T2PAD检测到2号节点、3号节点、4号节点发生异常，其状态流图分别如图 6、图 7和图 8所示.图中数值为状态的编号，深色为检测出的异常状态.

2号节点异常状态1出现的原因是任务0x0011(CC2420ReceiveP_receiveDone_task)的转移概率发生变化.从任务0x0011到0x0011的转移概率由原来的0.5变为0.96.此异常表明2号节点频繁处理接收事件，这是由于4号节点在此时频繁向2号节点发送数据包. 2号节点异常状态2是4号节点与2号节点建立连接时出现的状态，出现的原因是任务0x0021(UARTDebugSenderP_sendTask)的转移概率发生变化，这是因为建立连接时节点频繁发送Debug调试信息. 2节点异常状态3主要是由一些与发送和接收有关的任务导致，通过分析可知状态3是网络结构重新达到稳定后的正常状态，因此将状态3添加至正常状态表.

3号节点出现异常状态1~5的异常任务主要是与发送和接收数据包相关的任务，由于网络经历了从突然改变结构到新的网络结构逐步稳定的动态变化过程，所以与发送和接收相关的任务也会经历一个动态的变化过程，其从异常状态1逐步达到异常状态5并最终达到稳定.因此需要将状态5添加至正常状态表.

4号节点出现的异常任务与发送数据、更新路由0x0016(CtpRoutingEngineP_0_updateRouteTask)相关. 4号节点断开与3号节点的连接导致4号节点丢失父节点，4号节点需要重新评估链路质量并更新自己的路由表.实际上，4号节点从丢失父节点并进入2号节点通信范围内到其与2号节点建立路由经历了20 min，远大于一般情况下路由建立的期望时间. 4号节点丢失父节点之后任务0x0016出现异常，而2号节点的0x0016任务未出现异常，进一步分析CtpRoutingEngineP组件代码分析发现：Router定时器BeaconTimer在网络稳定之后，广播Beacon数据包的周期上限为512 000 ms，较长的广播周期导致了4号节点不能及时获取到新的邻居信息，进一步导致4号节点建立新的路由时间较长.这一异常将使得网络在节点位置发生变化之后不能很快建立新的最佳链路，网络性能变差.将Beacon广播周期上限设置为1 000 ms后，TinyOS汇聚树协议程序很好地满足了项目在节点具有移动性的情况下快速建立路由的需求.

4.3 实例3：外部存储器失效

Telosb节点使用STM25P作为外部存储器，当外部存储器件失效而无法响应读写请求时程序执行会出现异常.通过修改Cooja底层STM25P相关的模块的代码，使其忽略TinyOS节点发出的任何读写操作，可以在Cooja中重现这一故障.

利用T2PAD可以准确地检测到该故障导致的异常.节点内所有运行的任务如表 3所示. T2PAD检测到任务0x0007现异常：在正常状态下任务0x0007到任务0x0000的一步转移概率为0.035，异常状态下该任务的一步转移概率变为0.411.根据T2PAD给出的异常信息，开发人员可以确定该故障与TinyOS资源仲裁器代码相关.对0x0007任务的进一步分析可以发现：STM25P相关驱动代码没有对STM25P是否正常工作进行检查，进而导致后续异常.

5 结束语

提出了一种新的感知节点状态描述方法.该方法利用观测窗口内节点执行任务一步转移概率矩阵分析节点运行状态特征，通过矩阵向量的相似性建立节点运行状态序列模型，进而实现对节点异常状态的检测. 9个典型应用测试表明，任务转移概率可以较好地表征节点运行状态；3个代表性实例分析，验证了T2PAD异常检测方法的有效性.