王出航, 王 雪, 胡黄水, 赵宏伟, 韩由佳

(1. 长春师范大学 计算机科学与技术学院, 长春 130032； 2. 吉林建筑科技学院 计算机科学与工程学院, 长春 130114；3. 吉林大学 计算机科学与技术学院, 长春 130012； 4. 长春工业大学 计算机科学与工程学院, 长春 130012)

无线传感器网络(WSNs)广泛应用于军事、 环境监测和太空探索等领域[1-2]. 为有效延长无线传感器网络的生命周期, 可利用分簇路由组织节点并传输数据至基站[3-5]. 由于无线传感器网络的大规模和动态特性, 路由易受来自网内外各种恶意节点的攻击[6-9], 因此, 安全分簇路由协议设计成为无线传感器网络的研究热点.

目前, 加密和身份认证是一种有效提高分簇路由安全性的方法. 文献[8]采用K-means聚类和蚁群优化分簇, 基于球面网格的多椭圆曲线加密路由算法确定路由, 安全地将数据从源节点发送至基站. 但这类算法计算复杂、 能耗较高且通常只能抵御外部攻击[10]. 而基于信任感知的安全分簇路由能识别恶意节点, 抵抗内部攻击, 提高网络安全性[10-12]. 不同于非分簇安全路由算法[13-15]中所有节点都参与路由计算, 分簇安全路由仅选取网络中信任度高的节点参与最优路径搜索, 保证网络安全的同时提高了能量效率. 文献[10]提出了一种考量多种信任因子结合节点度、 距离的分簇安全路由算法, 其从随机产生的候选簇头集中选出信任度值大的节点作为簇头, 簇头选择最近簇头转发数据或直接发送给基站. 仿真结果表明, 其能有效评估节点信任值, 提高网络路由的安全可靠性, 但该算法在计算信任度时忽略了历史行为影响, 导致计算不准确, 簇头选举时随机选择候选簇头, 并且仅基于距离选择下一跳将导致能量和信任值都较低的节点成为簇头或中继簇头, 从而降低了算法的整体性能. 基于此, 文献[12]提出了一种基于信任与能耗均衡的安全分簇路由协议, 计算节点综合信任值时考虑历史信任, 并采用模糊逻辑计算直接信任值, 根据偏离度对间接信任值进行过滤和权重分配. 路由选择时距离基站近的簇头直接与基站通信, 其他簇头选取剩余能量多、 综合信任度大且相比距离基站近的簇头作为其下一跳. 仿真结果表明, 该协议在提升网络安全和可靠性的同时也提高了网络数据包传输量及能耗均衡性, 但其与文献[10]算法相同, 随机选举簇头可能将能量和信任值都较低的节点选为簇头或中继簇头, 导致某些节点因能量消耗不均而早死. 文献[16]提出了一种基于信任云的分簇无线传感器网络安全路由方法, 选取网络中节点度高、 剩余能量大、 信誉好的节点作为簇头, 并利用粒子群进行优化, 同时为降低簇头的负荷, 选出专门的信任云节点负责簇内节点信誉的计算, 并把结果反馈给簇头, 路由选择时距离自身近且信誉好的簇头成为下一跳或直接发送至基站. 仿真结果表明, 该方法能应对无线传感器网络中的路由安全问题, 且能有效控制节点的能耗, 但现有路由安全算法都通过本地决策选择簇头并选择簇头下一跳, 无法找到最优簇头和路径. 此外, 现有算法在信任值计算、 簇头选举和路由选择时通常不考虑节点负载, 导致网络负载不均衡, 从而降低了网络生命周期. 而遗传算法具有良好的全局搜索能力, 常用于寻找最优簇头或路由[17]. 但基本遗传算法存在收敛速度较慢、 易陷入局部最优等缺点[18-20].

针对上述问题, 本文提出一种采用改进遗传算法同时选择最优簇头和搜索最佳路径的安全路由协议SCRGA(a trust-aware secure clustering routing protocol for wireless sensor networks using an enhanced genetic algorithm). 将簇头选举和路由搜索用同一个染色体编码, 并基于簇头综合信任值最大、 全网能量消耗最小以及负载均衡为目的构建适应度函数, 遗传操作时定义约束条件避免产生非合理个体, 并将上一轮最优染色体加入初始种群, 保持种群多样性以避免局部最优并提高收敛速度. 仿真结果表明, SCRGA协议相比其他算法具有更好的能量效率和负载均衡性, 在保障网路安全的基础上有效延长了其生命周期.

1 确定节点综合信任值

与传统安全路由算法相同, 节点的综合信任值是参与簇头选举和路径搜索的关键[15,17], 综合信任值越大的节点安全性越高, 更有可能被选为簇头和中继节点. SCRGA组合节点的直接和间接信任值确定其综合信任值.

1.1 节点直接信任值

节点根据邻居节点的接收和发送数据包个数, 计算其对每个邻居节点的直接信任值, 节点i对邻居节点j的直接信任值可表示为

(1)

其中: 等式右侧第一项表示历史信任值, 第二项表示当前信任值；γ和1-γ(0<γ<1)分别是历史信任值和当前信任值的权重, 其值大小根据实际的WSN确定, 本文令γ=0.5;Rt和St分别表示发送和接收的数据包数量占总数据包数量的比例, 可表示为

(2)

(3)

此外, 还定义了挥发因子, 目的是快速降低从具有高信任度值的普通节点被捕获成为恶意节点的信任值.挥发因子计算公式为

ω1=e-c1mod(T,τ),

(4)

ω2=e-c2mod(T,τ),

(5)

其中T为网络的当前时间,τ为时间阈值,c1和c2为用于调整信任值变化速度的常数.引入mod(T,τ)是为保证历史信任值不会太小, 并使挥发因子在一定范围内周期性衰减.

1.2 节点的间接信任值

节点i对节点j的间接信任值由其公共邻居节点提供的直接信任值计算得到.公共邻居节点集合可以用Bh={B1,B2,…,Bm}表示, 其中m是公共节点个数.节点i对节点j的间接信任值表示为

(6)

(7)

其中p为节点i的邻居节点个数.

2 确定最优簇头和最佳路径

SCRGA采用改进的遗传算法同时进行簇头选举和路径搜索, 为提高收敛速度, 本文从染色体编码、 选择、 交叉和变异操作以及终止条件方面进行改进, 特别是构造了基于综合信任值、 能量消耗和负载的适应度函数, 使选出的簇头和路径综合信任度较高、 能量消耗较小且负载均衡, 从而有效延长网络生命周期.

2.1 构造适应度函数

设n为网络节点数,H={h1,h2,…,hk}为簇头集合,M={m1,m2,…,mq}为成员集合, 则有k+q=n.为计算方便, 将基站表示为hk+1；dij为节点i和j之间的距离,dmax表示其最大值；

CHmi={hj|∀hj∈H∧0

为成员mi的候选簇头集,Hmi为mi的簇头;

nxCHhi={hj|∀hj∈(H∪hk+1)∧dhihk+1>dhjhk+1∧dhihj≤dmax}

为簇头hi的下一跳候选簇头集, 且nxHhi为hi的下一跳簇头,nHhi表示簇头hi作为中继的次数.用Ld表示节点负载；Einitial表示节点的初始能量,Eresiduali表示节点i的剩余能量.

采用文献[7,13]的能量消耗模型, 即节点i发送l位数据到节点j, 其消耗的能量为

(8)

ERij=l×Eelec,

(9)

融合l位数据消耗的能量为

EDA=l×EpDb,

(10)

其中EpDb是融合l位数据的能耗.

由式(8)～(10)计算得到每个簇头节点和成员节点消耗的能量分别为

于是, 可求出整个网络的能量消耗为

(13)

SCRGA的目标之一是最小化Etotal, 由式(13)可见, 其能均匀分布簇, 因为它既考虑了簇间也考虑了簇内能量最小. 分簇网络中成员节点的负载均相同, 因此网络负载均衡仅考虑簇头, 表示为

(14)

为加速算法收敛, 考虑只有当节点自身剩余能量和综合信任值大于网络平均剩余能量和网络平均综合信任值时才参与簇头选举, 即对任意的hi, 满足

(15)

此外, 为找到可信度高的路由路径, 考虑整个簇头的平均综合信任值, 表示为

(16)

SCRGA的第三个目标是保障簇头和路由的安全, 因此, 构建如下适应度函数：

(17)

通过该函数找到安全可靠、 能量效率高和负载均衡的最优簇头和最佳路径.

2.2 遗传操作

SCRGA采用实数编码表示染色体, 且簇头选择和路由搜索用一个染色体表示, 不增加染色体长度的同时提高算法效率, 即染色体的前部分表示路由搜索, 后部分表示簇头选择, 如图1所示.

图1 簇头选择和路由搜索的染色体表示Fig.1 Chromosome representation for cluster heads selection and routing search

首先, 由图1可见, 从100个节点中根据式(15)任意选出k个(k=6)簇头9,23,48,69,81,95, 根据变量定义可得到每个成员节点的候选簇头集和每个簇头的下一跳候选簇头集. 根据

∀gj|{(gi∈nxCHhi,i∈[1-k])||(gi∈CHmi-k,i∈[k+1,n])}

(18)

计算染色体中各基因, 分别得到每个成员节点的簇头, 成员1的簇头为9, 成员2的簇头为48,…, 成员100的簇头为48. 同理, 可分别得到每个簇头到基站的路由路径, 9→81→23→BS, 23→BS, 48→95→BS, 69→48→95→101, 81→23→BS, 95→BS. 由于对染色体的基因进行了约束, 既保证了染色体的合理性又提高了算法收敛性. 依此可得到初始种群.

其次, 对初始种群中的每个染色体根据式(17)分别计算其适应度值, 并按从小到大排列. 采用精英选择策略选取15%的精英个体直接遗传到下一代种群, 其他的执行交叉操作. 由于染色体由两部分构成, 所以采用两点交叉生成子染色体, 即在父染色体的路由搜索和簇头选举部分各随机确定一个交叉点, 对交叉点之间的基因进行交换, 如图2所示.

图2 染色体两点交叉Fig.2 Two-point crossover of chromosome

由图2可见, 生成的子染色体同样为合理染色体, 对生成的两个子染色体根据式(17)分别计算其适应度值, 并与相应的父染色体适应度值进行比较, 适应度小的用于变异操作. 然后采用位变异对各染色体进行变异操作, 即随机选取某个位置基因修改为新基因, 新基因利用式(18)生成, 以保证新染色体的合理性. 生成的新染色体采用式(17)计算其适应度值并与父染色体进行比较, 适应度值小的遗传至下一代. 于是, 所有变异操作后保留的染色体结合精英染色体形成新一代种群. 如果迭代次数达到预设的值或满足

(19)

则算法终止, 其中ω为种群大小,ε为一个任意较小的正数, 用于表明种群个体差异, 与文献[15]相同取10-5. 一旦算法终止, 种群中适应度值最小的个体即为最优解, 并将该最优解加入下一轮初始种群中加快算法收敛. 算法流程如图3所示.

图3 改进的遗传算法流程Fig.3 Flow chart of improved geneic algorithm

3 仿真分析

为验证SCRGA的性能, 在MATLAB环境下对其进行仿真测试, 并与TC-SRA[13]及文献[7]提出的改进遗传算法(简称SRBNT)进行比较分析. 网络中100个节点随机分布在100 m×100 m的目标区域, 基站位于中心(50 m,50 m), 同时将10个恶意节点分布在网络中, 仿真参数设置如下： 节点初始能量为1 J,Eelec=50 nJ/bit,εfs=10(pJ·bit-1)/m2,εmp=0.0013(pJ·bit-1)/m4,EpDb=5 nJ/bit, 数据包大小为4 000 bit, 控制包大小为200 bit, 节点的最大通信范围dmax=50 m, 交叉率为0.85, 变异率为0.04, 种群数为200.

丢包率是评价网路安全的重要指标之一. 图4为3种不同算法在不同恶意节点数目下的丢包率对比结果. 由图4可见, 随着恶意节点数的增加, 3种算法的丢包率都呈上升趋势, 但SCRGA的丢包率低于TC-SRA, 平均减少了15.98%的丢包率. 这主要是因为SCRGA考虑了历史信任对现在的影响, 引入了挥发因子降低历史信任值对节点的综合信任值作用, 提高了检测恶意节点的速度. 与SRBNT相比, SCRGA的丢包率平均降低了19.44%. 这是因为SRBNT的时间因子是预先设定值, 随着网络的运行, 时间因子可能不再适用网络的信任评价功能. 因此, SCRGA总体优于TC-SRA和SRBNT的安全性能.

当网络存在恶意节点时, 其数量越多, 存在网络中时间越长, 则基站收到的数据包数量就越少. 图5为基站收到的数据量随恶意节点数量增加而降低时3种算法的对比结果. 由图5可见, 当网络存在2,4,6,8,10个恶意节点时, SCRGA基站收到的数据总量分别为30 747 KB,29 565 KB,28 357 KB,27 155 KB,25 917 KB； 比TC-SRA分别提升了1.69%,2.16%,3.03%,2.95%,3.41%； 比SRBNT分别提升了3.40%,6.03%,7.32%,7.64%,8.72%.

图4 3种算法在不同恶意节点下的网络丢包率对比Fig.4 Comparison of packet loss rate of three algorithms in different malicioius nodes

图5 3种算法在不同恶意节点下基站收到的数据量对比Fig.5 Comparison of data received by BS of three algorithms in different malicioius nodes

对于资源受限的无线传感器网络, 网络的剩余能量是评价网络性能的重要指标之一. 图6为3种算法的网络能量对比结果. 由图6可见, 随着网络的运行, 网络的剩余能量逐渐下降. SRBNT和TC-SRA的曲线斜率更大, 说明网络的能量消耗较快. 而SCRGA网络的剩余能量多于SRBNT和TC-SRA, 这是因为SCRGA设计遗传算法的适应度函数时, 除考虑节点的综合信任值外还考虑了簇头节点承担的负载和网络能量消耗两个指标, 合理地规划了每个簇头节点应承担的负载大小, 从而提高了网络的能量效率.

图7为3种算法的网络存活节点数对比结果. 通常网络存活节点数越多, 基站收到的相关数据就越多, 网络的性能也越好. 由图7可见, SCRGA通过遗传算法均匀选举簇头, 网络的能量消耗较均衡, SCRGA比SRBNT和TC-SRA的网络生命周期长. 而SRBNT比TC-SRA的网络生命周期短, 是因为SRBNT需要采集和计算众多因子, 从而增加了节点间信息的交互次数, 消耗了更多能量.

图6 3种算法的网络剩余能量对比Fig.6 Comparison of network residual energy of three algorithms

图7 3种算法的网络剩余节点数对比Fig.7 Comparison of number of surviving nodes of three algorithms

综上所述, 为提高信任感知无线传感器网络分簇路由的安全可靠性以及能量效率和负载均衡, 本文提出了一种基于改进遗传算法的新协议SCRGA. 以最大化平均综合信任值、 最小化网络能耗和均衡网络负载为目标, 采用改进遗传算法搜索全局最优解, 得到全网最优簇头集和最佳路由路径. 仿真结果表明, 无论是在能耗、 丢包率还是网络延迟方面, SCRGA均优于TC-SRA和SRBNT的性能, 而且对黑洞攻击、 选择性转发攻击、 Hello洪泛攻击、 虫洞攻击和槽洞攻击有良好的防御作用.