无线传感器网络中基于相邻节点协作的恶意节点溯源定位算法

张迪

（赤峰学院物理与智能制造工程学院，内蒙古 赤峰 024000）

无线传感器网络是一种由基站（sink）及大量的传感器节点组成的分布式网络，多部署在无人值守的环境中，因此极易受到物理破坏及人为的攻击。与传统网络相比，传感器网络节点结构较为简单且容易被敌方俘获，可以通过被捕获节点发动如泛洪攻击等方式的恶意攻击，使得网络资源快速耗尽。因此，设计一种高效的恶意节点溯源定位算法，成为当前无线传感器网络研究热点之一。

Savage[1]等人最早提出具体的标记算法方案。Ye[2]等人提出了一种基于概率包标记的节点溯源方案(Probabilistic Nested Marking,PNM)，该方案中，传感器网络节点对接收到的数据包作概率性标记，随着被标记的次数增加，致使数据包的首部变大，因此需要占用大量的传感器存储资源。Yang[3]等人提出一种基本标记方法(Basic Probabilistic Packet Marking,BPPM)，该方法是对PNM方法的改进，节点概率性标记数据包包头的标记区域限定为四个，为了能够重构溯源路径，在单个数据包标记信息有限的情况下，只能收集更多的数据包，该方法虽然标记过程简单、复杂度低，但算法收敛性差，溯源定位效率较低。此外，上述方法在网络拓扑发生变化，如因能量均衡改变簇头节点或恶意节点主动更改路由时，则需要重新定位恶意节点并重新收集更多数量的数据包，使得对恶意节点的溯源定位效率大大降低，变得更加困难[4]。

为解决上述问题，本文提出了一种基于相邻节点协作的恶意节点溯源定位算法。本算法基于数据包日志，在通信过程中，收发节点及其相邻节点将建立数据包日志并记录数据包内的特征参数。当恶意节点发动攻击时，sink节点通过收集途中各节点及其相邻节点数据日志中的特征参数重构数据包传输路径，进而定位至攻击节点。与传统的BPPM算法作对比分析，结果表明本算法对恶意节点具有更高的溯源定位效率且能够适应无线传感器网络动态路由变化等特点。

1 基于相邻节点协作的恶意节点溯源定位算法

1.1 系统模型与假设

假设一个传感器网络由基站（sink节点）及若干传感器节点构成，基站与外网相连，安全可靠且资源不受限制[5]。传感器节点随机部署，网络拓扑呈树状结构且可以动态变化，当传感器节点感知到某事件发生时，将通过簇头节点收集感知信息（如事件的位置信息等），簇头节点将周围若干节点发送过来的感知信息进行数据融合处理，再将数据融合后的数据包发送给下一跳节点，经过若干节点转发后，最终达到基站。与目前许多安全问题研究假设相同，假设传感器节点抗俘获能力较弱，攻击者可以通过被捕获传感器节点获取节点内所有的信息。本算法借鉴了与LEAP[6]协议类似的多重密钥机制，以适应节点间、簇间、节点与基站之间多种通信形式的安全需要。

1.2 符号

文中涉及的符号含义如下：

IDA：传感器节点A的标识符，即节点的MAC地址；

KA：个体密钥，节点A的个体密钥，该密钥与基站共享；

KAn：广播认证密钥，节点A的单项秘钥链中用于广播认证的第n个秘钥；

(Data)K：用秘钥K来加密数据Data；

MAC{Data}K：数据Data使用秘钥K计算出来的消息认证码；

NA：节点A的相邻节点列表。

1.3 算法描述

下面将对初始化阶段及恶意节点溯源定位算法进行描述。

（1）网络部署及初始化阶段。本阶段主要完成节点部署、节点发现、建立路由以及秘钥分配等任务，假设在网络部署及初始化阶段内，系统不会受到攻击。在节点部署前，在每一个节点（以节点A为例）内预置一个唯一的节点标识符IDA和一个与基站共享的通信秘钥KA。当节点部署完成后，借鉴μTESLA[7]协议生成应对一跳范围相邻节点广播通信认证的单向秘钥链（KA1,KA2,KA3,……,KAn），然后广播节点标识符IDA、广播通信认证秘钥KA1等信息来发现并建立节点之间的邻居关系，相邻节点P收到节点A的广播信息后将IDA写入其邻居节点列表NP中，随后节点之间完成其他秘钥的分配工作。

（2）感知信息阶段。本阶段传感器节点主要依据基站下达任务感知部署环境相关信息，每一个节点需要在缓冲区内建立数据包日志，用来记录接收到的有关感知信息的数据包的相关参数，数据包格式如图1所示。

图1 感知信息数据包格式

其中IDstr表示发起数据包的源节点ID；IDlast表示上一跳转发数据包节点的ID；IDend表示数据包目的节点的ID；Seq表示数据包源节点设置的序列号，其值没随节点转发而不断增大；Klast-i表示上一跳转发数据包IDlast节点的单向秘钥链验证秘钥；IDnext表示转发数据包的下一跳节点ID；Data表示感知信息数据；MAC表示数据包经过秘钥计算出来的消息认证码。例如假设在部署区域内发生某一事件，该区域簇头节点在汇聚来自周围节点的感知信息后，通过数据融合处理后生成感知信息数据包M，经过节点A并以广播形式发送给下一跳节点B，数据包M的格式如下：

接收节点在收到感知信息数据包后，先利用单向链秘钥KAi验证数据包的合法性，若验证数据包为合法数据包，则接收节点根据数据包内的相关信息，在缓冲区内建立数据包日志，日志信息将以结构体数组node[i]的形式按照FIFO方式记录并储存，其日志格式如下：

struct LogF{IDstr;Seq;sum;IDlast;IDnext}node[i];

其中Seq和sum分别表示在一个网络拓扑更新周期内节点发送感知信息数据包的序列号及发送数据包的条目数；若数据包核验为非法数据包，则直接丢弃该数据包。

（3）数据包的转发及日志信息的建立与更新。验证数据包M合法后，接收节点需要判断自己是否需要转发该数据包，检查数据包头中的IDnext是否与接收节点ID一致，如果一致则该节点需要将该数据包进行转发并记录数据包日志；若检查数据包头中的IDnext与接收节点ID不一致，则接收节点需要查找其相邻节点列表，检查接收节点是否同时是数据包M中上一跳节点IDlast和下一跳节点IDnext共同邻居节点，如果是共同邻居节点，则需要记录该路径数据包日志，否则丢弃该数据包。算法描述如下：

1）假设节点B收到上一跳节点A发出的感知信息数据包M，若有IDnext==IDB，则执行数据转发过程如下：

步骤1：建立或更新数据包日志。节点B检查缓冲区中的数据包日志。若存在数组元素B[i]满足传输转发路径一致的日志信息：

即节点B的日志信息与数据包M的源节点、序列号、上一跳转发节点ID、接收节点（下一跳节点）ID均一致，则执行B[i].sum=B[i].sum+1，将该记录的sum域的数值增加1后替换保存；否则，将建立新的传输转发路径日志记录B[i]={IDS;Seq;1;IDA;IDB}，保存在数据包日志缓冲区中。

步骤2：转发数据包至下一跳节点。节点B查找路由表，查找下一跳路由节点C的ID，然后替换数据包M中的单向链秘钥Klast-i、上一跳节点IDlast和下一跳节点IDnest， 即Klast-i=KBi；IDlast=IDB；IDnext=IDC；然后将数据包发送给下一跳节点C。

2）假设节点B收到上一跳节点A发出感知信息数据包M，若有M.IDnext==IDC，即该数据包M的下一跳节点为C，则节点B查找其相邻节点列表NB，若有：IDB∉NA∩NC，则丢弃该数据包，若有：IDB∈NA∩NC，即节点B为节点A和C的共同相邻节点，则执行数据监听过程如下：

建立或更新数据包日志。节点B检查缓冲区中的数据包日志。若存在数组元素B[i]满足传输转发路径一致的日志信息：

即节点B的日志信息与数据包M的源节点、序列号、上一跳转发节点ID、接收节点（下一跳节点）ID均一致，则执行B[i].sum=B[i].sum+1，将该记录的sum域的数值增加1后替换保存；否则，将建立新的传输转发路径日志记录B[i]={IDS;Seq;1;IDA;IDB}，保存在数据包日志缓冲区中。

（4）恶意节点的溯源定位。当系统发现不合法数据包或者检测到有恶意节点正在发动攻击时[8,9]，sink节点会启动针对的恶意节点溯源定位程序，具体过程描述如下：

步骤1：当sink节点检测到非法数据包后，sink节点将向上一跳节点H1发送节点溯源请求信息Q，如图2所示。请求信息包含非法数据包中的IDstr和Seq两个域的数据，节点H1收到该请求信息后，将该请求信息Q广播给邻居节点N1、N2……Ni，节点N1收到广播信息Q后，将检查其数据包日志，如果无该传输路径的日志，则无须回复任何信息；如果有日志记录：

图2 利用相邻节点信息溯源恶意节点过程

则N1[i].IDlast节点（假设为IDH2节点）就是节点H1的上一跳节点，则节点N1将生成ACK回答信息发送给节点H1，ACKN1的格式如下：

节点H1收到相邻节点N1发送过来的ACK回答信息后，通过节点N1的单向链密钥KN1i验证ACK的合法性，若通过验证，则保存该ACK，否则丢弃。当节点H1收到其他相邻节点Ni发送回来的ACK消息后，检查这些ACK消息中节点H1的上一跳节点是否相同，结合自身相邻节点列表，选取上一跳节点结果相同的ACK，回复给sink节点，回复sink节点的数据包格式如下：

步骤2：节点N1将sink节点的溯源请求信息Q继续发送给上一跳节点N2，N2收到信息Q之后重复步骤1中节点N1的过程。这样按照上述步骤逐跳节点溯源后，sink节点将会收到上游节点发送回来的ACK信息，然后利用与节点的共享密钥验证其是否合法并提取上两跳节点的ID值，当从sink收到自源节点IDstr至sink节点路径的所有节点的ACK回复信息后，由于溯源路径上的每个节点均包含两跳节点的ID信息，所有sink节点可通过这些ACK信息中构造出来的路径信息，溯源到恶意节点。

2 安全性及效率分析

2.1 安全分析

当恶意节点发动虚假数据注入攻击时，本算法采用相邻节点协作的形式，由sink节点发起恶意节点溯源，通过逐跳查询的方式，查找上游节点的数据日志，由于途中转发节点及相邻节点已经将数据包的参数记录在数据包日志中，所以，无论网络路由是否发生变化，均可以实现路由重构和对恶意节点的溯源定位。

对于单独的恶意节点发起的虚假数据注入攻击，sink节点可以依据上游节点的ACK信息重构路径，进而溯源到恶意节点。恶意节点也不能随意丢弃溯源请求信息或拒绝回复sink节点的溯源请求信息，这种情况恶意节点将直接被sink节点视为非法节点。

对于途中节点或邻居节点配合远程恶意节点发起攻击。当途中节点或相邻节点中被敌人捕获，配合远端的恶意节点发动攻击时，如果某途中节点为恶意节点，由于难以提供多个相邻节点ACK信息，因此很难伪造出合法的干扰信息来回复sink节点，一旦无法核验，恶意行为将被检出；另一种情况是某节点的相邻节点中恶意节点的数量可能超过合法节点的数量，这样将伪造虚假的ACK消息，但是在路径重构过程中，很难伪造连续的多个合法的ACK来干扰sink节点重构路径，因此这种情况下很容易识别到远程的恶意节点。

2.2 通信开销

假设自源节点到sink节点之间的节点数目为x，每一跳节点之间的共同相邻节点平均数量为y。在溯源定位过程中，路径中的每个节点需要广播溯源请求信息Q至上一跳节点和相邻节点，相邻节点发送一个查询数据包日志并反馈ACK信息。这样途中节点的通信开销x+x*y+x=(y+2)*x；接着途中节点再将反馈的ACK信息汇总后逐跳转发反馈给sink节点，其通信开销为1+2+…+x=0.5*x*(1+x)。以BPPM算法为例，该算法在跳数<10、概率标记0.1、节点转发次数20的时候能够获得最高的溯源定位效率，sink节点大约需要接受400-600个数据包。本算法假设跳数为x=10，通信节点之间的平均相邻节点数量为y=5个，则sink节点需要接收0.5*10*(1+10)=55个数据包，所有节点发送的总的数据包个数为10*（5+2）=70，效率明显优于BPPM算法。

2.3 适用性分析

这里需要讨论两个通信节点距离与其共同相邻节点个数之间的关系，显然通信节点的间隔越近，两节点天线覆盖范围重叠面积越大，当节点间通信距离增长至最大通信距离时，两节点天线覆盖范围的重叠区域将减少到最小，总的重叠面积约为节点通信总面积的39%。假设节点均匀分布，当两节点天线覆盖范围重叠面积最小时，其共同的相邻节点也应最少。因此，如果一跳节点相邻节点的平均个数为15时，其公共邻居节点的平均数量最少为6个。因此，与BPPM算法相比，本算法不受网络的规模限制，更适用于稠密、大型的传感器网络以及远距离恶意节点的溯源定位。

3 结论

本文提出了一种基于相邻节点协作的无线传感器网络恶意节点溯源定位算法。本算法通过收集上游各节点及其相邻节点数据日志中的特征参数重构数据包传输路径，实现对恶意节点的溯源定位。与传统的BPPM算法作对比分析，结果表明，本算法可以在面对单个或多个恶意节点协同攻击时实现对恶意节点的溯源定位，可适应大型且节点稠密的无线传感器网络以及路由动态变化的特点，溯源过程中可大幅度地减少数据包的传输数量，进一步降低了节点频繁的信息交换所带来的通信开销。