无线传感网络恶意节点识别算法①

周文雄, 林 穗

(广东工业大学 计算机学院, 广州 510006)

引言

无线传感器网络现有大部分路由协议都是以假设网络中的所有节点安全可信为基础的.而在现实情况下, 因传感器节点直接暴露在恶劣或开放的环境中而受到限制, 导致节点易被攻击者俘获, 最后改造成了恶意节点, 从而对路由层产生侵入攻击.现有的对称密钥安全机制在一定程度上只能够对外部的攻击进行抵抗,而对于节点被俘获过程中所带来的内部攻击却无能为力[1].信任的基本评估机制可以对故障节点、恶意节点以及不协作节点进行完整的识别, 从而达到抵抗网络相关攻击的目的, 而且这一评估机制可以在一定程度上提升无线传感器网络的完整性、机密性以及安全性[2].如果将节点信任机制引入到路由协议之中, 那么它就能以一种分配策略的身份将恶意节点从网络中排除出去, 还可以解决内部攻击问题, 保证了重要的数据仅能从可信节点之间传输, 继而建立起安全高效的路由协议[3].

现实社会中, 无线传感器网络面临着多种多样的安全威胁, 例如: 虫洞、女巫攻击、选择性转发、污水池攻击以及虚假路由信息等.针对上述无线网络安全威胁, 近年来已经提出多种算法用以检测识别恶意节点, 达到了抵御外部伪造的路由讯息、Sybil 攻击和Hello flood 攻击的目的.如刘志锋等人建立了一种多层攻击下的、以簇为基础的传感网评估模型, 增强了网络恢复的能力从而达到提升生存力的目的, 而且此模型还能用于区分网络受到何种攻击方式[4]; Awad A 等利用虚拟坐标提高传感器网络的路由性能, 从而隐藏恶意节点的攻击目标[5]; Naser A 等在研究过程中以两跳邻居信息为基础提出了一种新的算法来对选择性的转发攻击来进行检测[6].段正飞等针对虫洞攻击对节点定位过程的影响, 提出了一种距离矢量跳安全定位算法.通过改进冲突集建立方法,选出最合适的信标节点广播睡眠信息, 提高了虫洞检测成功率和定位精度[7].付翔燕等建立了以最优转发为基础的随机路由算法, 利用可信任的邻居节点进行监听, 可对恶意节点做到有效的防御和处理[8].齐全等提出一种基于信誉机制的认知ad hoc 网络分簇协作感知方法, 将权值应用为节点信誉值的基础上实现了数据之间的融合, 然后对融合值和实际值进行了比较分析, 判断数据节点的可疑性, 并利用惩罚系数来降低数据信誉值, 筛选恶意节点[9].与有线网络相比较, 无线传感器网络在开放环境下, 能量、带宽、计算能力、存储空间受到一定限制,这就决定了传统的入侵检测技术难以直接应用到无线传感器网络中.因此, 针对无线传感器网络的特点, 金鑫等提出了针对无线传感器网络的入侵检测模型, 它由邻居节点监听、历史行为记录、数据釆集融合、拓扑和路由追踪等搭建[10].为提升无线网络传感器的安全性和使用时间, 本文在对前人相关研究进行分析和借鉴的基础上, 引入信任以及信誉系统, 针对的节点类型主要有两种, 分别是转发节点和传感节点, 提出了一种以随机并行为基础的簇头选举算法, 该算法以安全数据的融合为基础, 可以均匀地选举节点, 对恶意节点进行识别清除, 加密通信数据, 从而有效地实现无线网络通信的安全.

1 算法设计

1.1 簇头节点的可信选举

假定全网时间同步并且各节点有独一无二的身份标志.网络的簇结构如图1 所示不考虑具体的密钥分布策略, 但假设各节点拥有3 种密钥: 公钥、密钥以及私钥.公钥被网络中的全部节点拥有, 主要作用为收获基站广播.密钥主要作用为簇结构内部的组播或广播,每一个簇结构拥有其内部特有的密钥.因此, 可以通过簇内密钥实现基站和其它簇之间的通讯, 还可以使得邻居节点的簇头内部信息交换相互不影响.私钥一般是被某一个节点存放, 以便于节点间的数据通讯.

图1 无线传感网层次路由的拓扑结构

在路由层级中, 簇头节点扮演着核心的角色, 如数据采集融合、信息转送、密钥转存等.在相对繁杂的网络背景下, 层级路由急需改善的核心问题是如何采取适当的方式来保证簇头的可信任度.在对簇头节点进行可信选举的过程中不应该对太多的因素进行考量,而是应该把其当作一个最优化的选举方式, 仅须对可信度、距离和密度之间的最优化进行考量分析.节点密集度是指在某节点附近的邻居节点密集程度, 可以直接表示为邻居节点的数量; 距离D 指的是簇头节点和成员节点间相隔的距离.对距离和密集程度进行设置的主要目的是为了能够以节点的信任评估为基础来实现路由主干节点选择的均匀性.如果密集度越高, 那么簇头间数据信息的融合率就会越大, 如果距离越近,那么节点间的通讯代价就会越小[11].

若节点p 在等候选择的信任簇节点集s 之中, 那么THSp 命令为表示节点p 的簇头选举函数.如果对概率形式的信任值进行利用, 那么对簇头选举进行无约束优化的问题表达式就如式(1)所示:

式中, OT 表示的是普通成员节点对候选的可信簇头节点p 表现出的总体信任值, α、β、γ 分别代表的是节点处的信任值、密集度以及距离的权重, 且存在α+β+γ=1 的现象, 表示信任值的调整系数.如果使用理论基础上的信任值, 那么基本表达式如式(2)所示:

其中, m(T)指普通成员对可信节点p 总体信任值的信任分量, M(T,-T)指不确定分量.

由式(2)可得出簇头选举函数具有这种特性: 随着可信值和密集度的提高, 函数值增大; 随着距离的增加,函数值减小.此可以表为一个组合优化问题, 若p 要成为可信簇头, 则p*必须为簇头选举函数的一个解, 即:

可得出式(3)的解并不是唯一存在, 是3 个参数α、β、γ 的不同函数; 因此, 须依据实际情境, 拟定3 个参数的值, 最后对其进行迭代优化.通过分析节点发送和接受的消息使每个节点的行为得到监督, 从而自动检测识别恶意节点并清除, 实现对无线网络的保护.

1.2 算法优化

在传统的层次路由之中, 一般会对全网节点的安全可信性进行肯定假设.但是在实际操作和工作环境之中, 层次路由经常会受到威胁.威胁的来源和种类主要分为以下两个方面: (1) 恶意节点有时会充当簇头节点对网络流量产生一定的误导影响, 从而对网络的安全产生一定的威胁; (2) 恶意节点有时会加入到正常的簇结构中, 通过发送某些错误信息而对监测结果产生相应的影响.传统HRBNT 算法主要解决单一网络威胁, 忽略了信任路由自身功能漏洞, 并没有对信任整体进行充分考虑, 如簇结构不稳定导致恶意节点不能及时排除、关键节点防御能力不足等问题[12], 为了实现上述问题的有效解决, 确保簇结构工作过程中的安全可靠, 本文以簇头可信选举和节点信任值为基础, 对无线传感器网络层次路由协议HRBNT 进行优化.改进算法基于节点行为分析, 综合信任度、密集度等参数选举簇头, 根据邻居节点建立高效稳定的簇结构, 与原算法在预防恶意节点方面更加优秀, 保证网络高安全性.算法优化和建立过程主要为:

① HRBNT 之运行过程呈周期性, 其可分为数次循环.如簇头的能量小于一定阈值或该轮运行操作即将结束时, 当前簇头发布重新选择信息, 进入后面的循环运行操作, 并选举新的簇头.

② 每一次运行过程中, 各个节点会依据本身的运行状态考虑是否成为候选簇头: 每一个节点会生成一个[0, 1]间的随机数, 假设阈值T(n)大于随机数, 那么此节点可选作候选簇头, 然后邻居节点会收到它选作候选节点的广播.在每一次循环过程中, 若节点曾经被选取为簇头, 则需要设置T(n)为0, 如此当选过簇头的节点就不会再一次成为簇头, 从而实现提高其他节点当选概率的目标; 在当选过簇头的节点个数逐渐增多时, 其他节点当选为簇头的阈值T(n)也会增长, 节点生成比T(n)小的随机数的概率随之提高, 因此其他节点当选的概率就会增大.T(n)的基本计算式(4)如下:

其中, P 指簇头在全部节点中所占的比值, r 指循环次数, G 指还没当选过簇头的节点的集合, er 代表节点当前能量, ei 代表节点初始化能量.

③ 若节点生成的随机数大于T(n)或者其已被选作簇头, 那么可作为成员节点, 等候接收候选簇头的广播讯息.如果此节点接收到了若干候选簇头节点的广播讯息, 那么就查找本地相关的纪录, 对拥有较低信任值的节点进行排除, 收集信任值较高的节点.成员节点在选择加入某簇结构之后会发送相应的请求包, 告知该候选簇头.候选簇头的选举过程如图2 所示, 其中的1、2 和3 号节点为候选簇头节点, 4 号节点为成员节点, 虚线表示成员节点的通信半径.4 号节点排除信任值较低的2 号节点, 计算1 号节点和3 号节点的簇头选举函数, 并向选举值最大的1 号节点发送请求包, 请求加入该簇.

图2 实际网络联机情形

④ 候选簇头发送广播消息后, 等候接收其他节点的请求包.在簇头接收到来源于全部节点发出的加入申请之后, 它就会对本地的信任纪录加以运用, 对具有恶意节点的请求进行排除, 从而确保簇的全部成员是安全可信的.同时, 经过等待接收簇头的考察, 仅行为良好的节点才能和簇头节点连接, 预防恶意节点频繁的加入簇导致过多消耗簇头能量.簇结构的形成过程如图3 所示, 其中4、5 和6 号节点为成员节点, 都向1 号候选簇头发送请求包, 虚线圆表示簇头节点的通信半径.由于6 号节点信任值较低, 所以只接受4 和5 号节点的请求, 且信任值最大的5 号为影子簇头节点[13].

图3 簇结构的形成过程

⑤ 簇头首先利用TDMA 时分复用给其余节点提供方案, 通过广播把方案信息转发给簇结构中的全部节点, 以告诉节点什么时隙可以发送数据, 杜绝节点间互相共谋或者互相影响.簇组员收到TDMA 信息时,立刻为对应的时隙转发消息.全部簇节点的信息传送完成之后, 数据信息会被融合转化为其它信号, 再次发给其它簇头和基站.节点间的数据通信可选用最短路径、泛洪广播和列分层级等不同协议, 实现形式须依据现实情况、网络功能和规格等确定, 在此不做深入讨论[14,15].

1.3 阈值的确定

假设网络中簇头节点的数目是特定的, 所有节点的初始能量相同.由于簇头节点比成员节点耗费的能量更多, 为了避免某些簇头节点比其它成员节点先耗尽能量, 造成网络生命周期的缩短, 需要每个节点轮流充当簇头节点以平均分配能量负载.

假设某个节点i 在第r+1 轮循环中自主决定它以T(n)的概率当选为簇头节点.阈值T(n)的确定应该使得当前轮数期望的簇头节点数目为k.因此, 如果整个网络中共有N 个节点, 则有:

为确保全部节点在相同的时间段内成为簇头的几率同等, 则需要每一个节点平均在 N/k轮中作为簇头节点一次.用指示函数 Ci(t)表示节点i 在最近的r*mod(N/k)轮是否成为簇头节点, 如果节点i 已经当选过一次簇头节点或者一次以上, 则 Ci( t)=0, 否则Ci(t)=1.于是每个节点在r+1 轮应当以T(n)的概率当选为簇头节点, 则:

由此可保证通过每个 N/k环循环后, 全部节点的能量近似相等.得出每一轮循环期望的簇头数目是:

式中, 全部节点都自主决定其以T(n)的概率当选为簇头节点, 但是某些节点由于本身能量较低, 作为簇头节点或会造成其过早的死亡.为延长网络生命周期, 可根据节点能量情况, 对T(n)的算法进行调整:

其中, er 为节点当前能量, ei 为节点初始化能量.

但是, 对于经过长时间运行的网络来说, 其全部节点的现有能量较之前都会有所降低, 阈值T(n)也自然会变小, 而这些节点成为簇头的基本概率也会有所降低, 从而使每一轮循环被选为簇头的节点个数有所减少, 最终甚至会影响网络能量消耗的均衡性, 缩短网络的生命周期.因此, 进一步改进后的T(n)的计算方法如下:

其中, rs 指节点连续没有被选为簇头的选举次数.如果节点被选为簇头, 则将rs 重置为0.上式对节点能量、阈值在选择簇头时的影响方面进行了综合考量, 改进算法更具公平性.

2 算法实验与结果分析

使用Matlab 进行仿真实验, 我们把节点信任值的计算参数设为α=β=γ=1/3.实验范围是参照节点i 和i 通讯区间的全部节点, i 的坐标定为(50, 50).试验范围内全部簇头节点会将选举信息进行广播, 节点i 在收到相应的广播之后会对两者之间的相互距离进行计算,并且对历史记录信任过的节点以及候选簇头节点的密集程度进行查找, 最后以最优原则为依据对可信簇头进行选择.

具体结果如表1 所示, 依据可信任簇头选取方法,对等候选举的节点可信数值、数据采集融合率、信息传输耗损和簇结构的负载均衡进行综合考量.由于18 号节点选举值最大, 则让参照节点选取其为簇头节点, 然后朝簇头节点发出入列申请.

表1 参照点i 的信任节点选举数据

实验对HRBNT 算法和改进算法路由层级的建立采取了仿真模拟, 模拟结果如图4 和图5 所示.在原算法中, 无线网的全部节点会以收到广播的次数和频率为标准来对较近的簇进行选择; 但在改进算法中, 成员节点通常会选择选举函数值最大的簇, 并且会向簇头发出加入请求, 候选的簇头在收到请求之后会对本地的信任记录进行查询, 然后根据成员节点信任值的高低来决定允许或拒绝其加入.

据仿真结果数据得到, 原算法不能对恶意节点进行及时地识别和排除, 有时还会将一部分恶意节点误认为是网络流量, 从而导致破坏网络正常结构的后果;而改进算法则可对恶意簇头与节点进行有效的清除,并且还可在最大程度上对簇结构的布局进行优化整合.这其中的原因主要在于, 建立路由层级时, 原算法在一定程度上缺乏恰当的信任机制, 但改进算法对可信度、密集度进行了充分考量并利用节点之间的协同合作检测恶意节点, 使网络更加安全可信.

图4 HRBNT 算法在网络攻击下的簇结构

图5 改进算法在网络攻击下的簇结构

3 结语

本研究提出了一种基于节点信任值的无线传感网路由算法, 其以节点信任评估为基础, 对节点距离与密集度进行分析考量, 并使用局部最优化和分布式策略,经过对路由节点的可信选举, 预防恶意节点参与数据通信, 保证了层次路由的安全性和可信性, 可对无线传感网节点失效和被俘获所导致的路由安全问题进行有效的解决.