欢迎光临中国知识产权协同创新网!

     联系我们

中心成果

+MORE IP与军民融合

您的位置 > 首页中心成果期刊论文 > 戚涌,倪铭,张宏,李千目:基于混合PSO的无线传感网安全分簇算法

戚涌,倪铭,张宏,李千目:基于混合PSO的无线传感网安全分簇算法

作者:倪铭,张宏,李千目,戚涌来源:解放军理工大学学报 日期:2019年3月5日 21:25

本文发表在《解放军理工大学学报》2015年05期。

 

摘要:为了合理有效地管理和维护无线传感网络中的节点,提出基于混合粒子群算法的安全无线传感网分簇算法,基于网络的安全性和节点的信任度问题,在分析粒子群优化算法的基础上,引入局部最优解对最优解搜索过程的影响。在适应度函数中,该方法将节点剩余能量、与其他节点的连接性能以及安全信任度作为主要评价指标,把粒子群算法多次迭代得到的适应度值最高的节点作为簇首节点。通过实验对比了该算法与LEACH和MCBMC算法对节点生命周期的影响。结果表明,在不同恶意节点数量和不同节点密度的情况下,该算法能使无线传感网络具有较长的生命周期。

 

关键词:分簇;安全性;粒子群算法;局部最优解;无线传感网

 

  无线传感网已被广泛地应用在国防、信息安全、环境监测、医疗监护等领域,用于监测、感知和采集分布在区域内的对象,并实时反馈信息。由于无线传感网络具 有 节 点 量 多、资 源 有 限、动 态 拓 扑 等 特点,为了实现高效的数据传输和较长的生命周期,需要对网络进行分簇,簇首节点通过融合簇内各普通节点采集的数据并汇聚至上一层节点(如基站),从而减少在网络中传输的数据量[1,2]。簇首可以对簇内成员节点进行管理和控制,实时感知簇内的安全态势,为全网络的安全态势感知提供支撑[3~7]

 

研究人员提出了多种无线传感网络的节点分簇算法。文献[8]提出了一种低功耗的自适应分簇路由协 议(low-energyadaptiveclusteringhierarchy,LEACH),其基本思想是网络以周期循环的方机选择簇首节点,其他普通节点则以就近原则加入相应的簇,普通节点将采集的数据传送到对应的簇首,簇首节点对数据进行融合后转发给汇聚节点。文献[9]在 LEACH 协议的基础上提出集中式随机簇头 生 成 算 法 (LEACH-centralized,LEACH-C),由基站根据全局信息选取簇首节点。其基本思想是基站依据全局节点的能量信息选取候选簇首,根据模拟退火算法选举簇头并构建相应的簇。文献[10]提出一种使用分布式的固定簇半径的分簇协议(ahybrid,energy-efficientdistributedclusteringap-proach,HEED),其基本思想是依据主、次 参 数(即剩余能量、节点邻近度或密度)混合选择簇头节点,其他普通节点根据次参数的平均可达能量(averageminimumreachabilitypower,AMRP)选择 加 入 相应的簇。文献[11]提出一种基于多轮分簇的无线传感 器 网 络 路 由 协 议 (multi-round cluster basedmulti-hopclustering,MCBMC),在簇头自举中引入剩余能量参数,同时,改单轮成簇为多轮成簇,减少了频繁分簇和重复建立多跳路由的次数。

 

由于无线传感器网络的开放性和资源的有限性,安全问题一直是研究人员关注的热点。基于分簇结构的安全问题与平面传感器网络是不同的,那些比普通成员节点承担更多网络通信任务的簇头节点更容易成为恶意攻击的对象。攻击者可以在网络中插入恶意节点来间接控制网络。由于上述分簇算法都没有考虑无线传感网络的安全性问题,一旦恶意节点成为簇首节点,所有加入这个簇的节点都会受这 个 簇 首 节 点 的 控 制。攻 击 者 可 以 发 起 sink-hole,selectiveforwarding等恶意攻击,不仅使整个网络的安全受到威胁,而且节点的资源会很快消耗殆尽,导致网络陷入瘫痪[12~17]。由于粒子群算法收敛速度较快且有较强的适应性,能够较好地应对实时动态变化的网络拓扑结构,因此可以将粒子群算法引入无线传感网络簇首的选举优化中。本文提出一种基于混合粒子群算法的安全分簇算法,研究在复杂网络环境下兼顾节点安全状况和信任度的簇头选择方法,并通过仿真实验证明该算法的有效性。

 

1 引入局部最优解的粒子群算法

 

粒 子 群 算 法 (particle swarm optimization,PSO)是由 Kennedy和 Eberhart提出的一种群智能优化算法。通过对鸟群觅食行为的研究得到启发,将群体中的一个个体看作 是 D 维 搜 索 空 间 的 一 个没有体积和质量的微粒,而鸟群需要寻觅的食物位置就是全局最优解。每个粒子都有一个由目标函数决定的适应值和速度来调整自身的飞行方向以保证向最优解飞行[18]

 

设在D 维空间中,由 N 个粒子组成的种群X =( ) x1,…,xi,…,xN ,粒 子i 的 位 置 表 示 为 Xi =( ) xi1,xi2,…,xiD , 飞 行 速 度 表 示 为 Vi =( ) vi1,vi2,…,viD 。 适应度目标函数评价每个粒子的适应度值fi。 粒子掌握自身当前的位置 Xi 、自身经历过的最佳位 置(个 体 极 值 为pbest )和 群 体 中所有粒子经历过的最佳位置(全局极值为gbest)。

 

求解系统被初始化为一组随机微粒,即随机解,通过迭代优化从而搜索到最优解。粒子在解空间中追随最优粒子进行搜索。每次迭代中,粒子通过跟踪2个极值(即pbest 和gbest )来动态更新,粒子 Xi通过式(1)(2)分别更新速度和位置,利用个体最优pbest 和全局最优gbest 来引导搜索的方向,并逐步达到全局最优解。

vid(k+1)=wvid(k)+c1r1(pid -xid(t))+

c2r2(pgd -xid(t)), (1)

xid(k+1)=xid(k)+vid(k+1)。 (2)

式中,i=1,2,3,…,N,d=1,2,3,…,D,k=1,2,3,… 表示算法迭代的次数;pid 为粒子i历史最优解位置;pgd 为全局最优解位置;w 是惯性权重;c1,c2 是学习因子,c1 是粒子追寻本身历史最优值继续飞行的权重系数,它表示粒子的“自我”认 知,c2 是粒子朝着群体最优值飞行的权重系数,它表示粒子的“社会”认知;r1,r2 是加速 常 数,在[0,1]区 间 内均匀分布。

 

在标准粒子群优化算法中,每个粒子的速度是根据粒子自身历史最优解和种群的全局最优值这2个因素来变化的,称为标准版算法。该算法的优点是收敛速度较快,但是容易陷入局部最优解,导致最终得到的结果可能不是真正的最优解。因此,引入一个混合的 PSO 算法。该算法在更 新 粒 子 的 位 置和速度时引入粒子一定邻域内最优值的影响,将邻域最优和全局最优加以结合,使得算法既能够保持一定的收敛速度,又不会很快陷入局部最优[19,20]

 

该算法中的速度更新策略考虑了粒子对全局最优的认知和对局部最优的认知,式(1)计算了粒子对全局最优的认知,对局部最优的认知公式如下:

vid (k+1)n =wvid(k)+c1r1(pid -xid(t))+

c2r2(pld -xid(t))。 (3)

式中,pid 为邻域最优解的位置。

 

综合式(1)(3),增加权重系数得到该算法的速度更新公式Hid(k+1)=τ×vid(k+1)+ (1-τ)×vid (k+1)n。 (4)

式中:vid (k+1)n 为局部版算法的粒子速度更新;pld 为邻域最优解的位置;Hid(k+1)为混合全局版算法和局部版算法而得到的速度更新;τ 为权重系数。 利用式(4)得到位置更新公式

xid(k+1)=xid(k)+Hid(k+1)。 (5)

 

2 基于混合粒子群优化算法的安全分簇算法

 

2.1 相关定义

 

2.1.1 信任值

 

每个节点维护有一个信任表,主要记录一段时间内该节点对簇内其他节点的信任值。为了便于描述,作如下假设:

 

(1)无线传感网络节点具有自定位功能,采用文献[21]的定位算法进行定位,能够实时感知自己的位置、速度等信息;

 

(2)每个节 点 有 一 个 唯 一 的 标 识ID,且 剩 余 能量可以实时感知;

 

(3)节点有效发射距离相等,若2个节点处在彼此的发射范围内,则这2个节点为邻居节点,存在一条链路相连。

 

2.1.2 粒子与传感器节点的映射

 

由于传感器节点在工作区域的分布是随机的,因此粒子的搜索空间是离散的。然而在粒子群算法中,粒子在状态更新后不可能正好落在传感器节点的位置上,所以需要将搜索粒子映射到传感器节点上,定义映射函数[22]:

D(Xid)={Xnd |min( )  ) ‖Xnd -Xid ‖ ,

1≤n ≤ N}。 (6)

式中:Xnd 是 传 感 器 节 点 的 位 置;Xid 是 粒 子 的 位置;‖Xnd -Xid ‖ 为欧氏距离;d 是解空间的维度(本文讨论的是平面空间,因此d=2)

 

2.2 分簇算法

 

2.2.1 初始阶段及簇首候选

 

在初 始 阶 段,采 用 LEACH 协 议 的 思 想,每 个节点随机产生1个随机数,若结果大于阈值,则该节点当选为临时簇首,并广播消息;其他节点根据接收信息的强弱来决定加入某一个簇,并向相应的临时簇首节点发送加入消息,成为簇成员。加入消息除了包含节点ID等必要信息外,还包含节点的能量值和对其他节点的信任表。

 

临时簇首根据接收到的各节点的信任表采用平均法综合计算各节点的信任值。随后,临时簇首根据各节点的能量值和信任值对各节点进行初步的能力评估。设评估 阈 值 为 Pλ,当 节 点 的 评 估 值 大 于Pλ,该节点成为候选簇首,并且只有候选簇首才有可能成为本轮的簇首节点。节点评估值 Pi 和阈值Pλ 为

Pi =tEi + (1-t)Ri,

Pλ =tEλ + (1-t)Rλ,

其中, Eλ =∑Ni=1Ei/N,Rλ =∑Ni=1Ri/N。

式中:N 表示簇中节点的数目;Ei 表示节点i的当前剩余能量;Ri 表示节点i的综合信任值;N 表示当前簇的节点数目;t为权重系数。

 

2.2.2 基于混合粒子群优化的簇首选举算法

 

(1)适应度函数

 

适应度函数用于衡量一个粒子的质量,在本算法中表示其作为簇首节点进行工作的能力。根据无线传感网络的特点,本算法的目标在于通过减少能量消耗来提高网络的工作效率,通过减少簇首节点的频繁更替以提高资源利用率,同时兼顾网络安全性,把网络风险降至最低。因此在建立适应度函数时需要考虑下列因素:① 节点的剩余能量。簇首节点除正常的数据采集外承担了额外的数据融合和转发任务,将消耗更多的能量,因此簇首节点的剩余能量越高,簇的整体工作能力就越高,簇的稳定性就越好。② 簇首节点与其他保持通信的能力,即持续通信时间。③ 节 点 信 任 值。簇首节点在簇内不仅要承担路由转发等工作,同时还要负责感知和维护簇内的安全风险状况,因此簇首节点需要较高的安全能力,否则将会导致整个簇的安全性降低,影响整个网络的安全运行。

 

基于以上因素,适应度函数定义为

f=α1f1 +α2f2 +α3f3,

f1 =Ei/E0,f2 =∑Nj=1

Ci,j/N,f3 =Ri。

式中:E0 表 示 每 个 节 点 的 初 始 能 量;α1,α2,α3 ∈[0,1]分别表示3个因素对适应度函数的权重,且α1+α2 +α3 =1;Ci,j 表示节点i与节点j的持续通信时间[23]。设节点i 的速度为vi,位置坐标为(xi ,yi ),移动方向为θi(0≤θi ≤2π),节点的信号传播距离为r,节点i与节点j的持续通信时间为

 

 

式中:a =vicosθi -vjcosθj;b =xi -xj;c =visinθi -vjsinθj;d =yi -yj。 粒子的适应度越大,表明该粒子有较大的能力作为簇首节点。因此优化的目标是在候选簇首中寻找出适应度最大的节点作为本轮的簇首。

 

(2)算法描述

 

基于混合PSO算法的分簇算法的算法流程如下:

 

① 将候选簇首中的节点作为初始粒子,初始化各粒子的参数,包括速度Vi 和 位 置 Xi 等;将pbest标记为粒子当前所在位置,同时计算每个粒子的适应度;将lbest 标记为当前节点邻域中适应度最好的粒子位置;将gbest 标记为全局中适应度最佳的粒子位置。

 

② 根据式(6)将 当 前 粒 子 映 射 到 相 应 的 节 点,并计算对应的适应度fi。

 

③ 对每个 粒 子,将 其 当 前 适 应 度 与 自 身 历 史最佳位置pbest 的适 应 度 作 比 较,若 好 于pbest 的 适应度,则重新设置pbest 的索引号为当前位置;将 其适应度和 全 局 最 好 位 置gbest 的 适 应 度 作 比 较,若好于gbest 的适应 度,则 重 新 设 置gbest 的 索 引 号 为当前粒子的当前 位 置;同 理,与lbest 的 适 应 度 作 比较,若较好,则重新 设 置lbest 的索引号为当前粒子的当前位置。

 

④ 根据式(5)更新粒子的速度和位置。

 

⑤ 如没有达到预设最大迭代次数,则继续执行②~⑤,否则 迭 代 完 毕,并将适应度最大的粒子即gbest 所对应的节点作为簇首节点。

 

3 实验与仿真

 

本文使用仿真工具 Matlab对算法进 行 仿 真 实验,与 经 典 LEACH 算 法、MCBMC 算 法 在 不 同 数量恶意节点、不同区域尺寸和不同节点密度下对网络的生命周期进行比较。

 

实验采用文献[9]中的能量消耗模型来计算网络的能量消耗。式(7)表示节点将l 比特数据发送到距离为d 的节点所需要消耗的能量:

ET(l,d)=ET-elec(l,d)+ET-amp(l,d)=

Eelec ×l+Eelec ×εfs ×d2, d ≤d0;

Eelec ×l+Eelec ×εmp ×d4, d >d0。 (7)

式中:Eelec 表示发射或接收装置发送或接收1b数据的能量消耗;εfs 和εmp 表示发射放大器将1b数据发射单位平方所需要消耗的能量;d0 是传输距离的阈值,d0 =槡εfs/εmp ,若传输距离大于d0,功率放大消耗采用多路径衰减模型,反之,则采用自由空间模型。

 

传感器节点接收lb数据的能量消耗为 ER (l)=ER-elec(l)=Eelec ×l。

 

3.1 不同恶意节点数量下的网络生命周期

 

100个传感器节 点 随 机 分 布 在100 m×100 m的监测区域内,每个节点各自以随机速度运动,节点发送数据包的 长 度 为 4kb。恶意节点数量分别取为20,50,得到 GLPSO 算法和LEACH 算法网络生命周期的对比曲线,如图1所示。

 

 

图1 网络生命周期对比

Fig.1 Comparisonoflifespan

 

从图 1(a)可 以 看 出,与 LEACH 算 法 相 比,GLPSO 算法从网 络 运 行 开 始,第 1 个 节 点 死 亡 所经过的轮数较多,即网络的生命周期更长。同时从第1个节 点 死 亡 到 所 有 节 点 全 部 死 亡,GLPSO 算法经历约1500轮,而 LEACH 算法仅有1000轮。

 

从图 1(b)可 以 看 出,当 恶 意 节 点 增 多 后,LEACH 算法的网络生命周期明显缩短,并且从第1节点死亡后,后续节点死亡的速度很快。而 GLPSO算法基本能够保持与图1(a)相同的生命周期和网络性能。

 

3.2 不同节点密度下的网络生命周期

 

监测区 域 大 小 为200 m×200 m,其 他 参 数 同§3.1。分别取节点数量为100和200,得到 GLPSO算法、LEACH 算法和 MCBMC算法[11]网络生命周期的对比曲线,如图2所示。

 

 

图2 网络生命周期对比

Fig.2 Comparisonoflifespan

 

对比图2与图1可以发现,图2的实验因为节点密度变小,簇内 成 员 到 簇 首 的 平 均 距 离 增 大,导致能量 消 耗 变 高,因 此 网 络 的 生 命 周 期 缩 短。但是相比而言,GLPSO 算 法 的 网 络 比 其 他2种 算 法的生命周 期 更 长,而 且 所 有 节 点 死 亡 所 经 历 的 轮数也较大。

 

4 结语

 

本文提出基于混合粒子群优化算法的兼顾安全的无线传感网分簇算法,在分析标准粒子群算法的基础上,引入局部最优解对粒子的影响,将全局最优和局部最优进行加权,共同影响粒子速度与位置的更新。在建立适应度目标函数时,综合节点的剩余能量、与其他节点的连接性能、安全信任值等因素,合理的评价节点作为簇首节点的能力。实验结果证明,该算法能够提高网络的生命周期,有效减少恶意节点对网络性能的影响。

 

参考文献:

[1] MATROUK K,LANDFELDTB.RETT-gen:aglob-allyefficientroutingprotocolforwirelesssensornet-worksbyequalisingsensorenergyandavoidingenergyholes[J].AdHocNetworks,2009,7(3):514-536.

 

[2] LIQianmu,ZHANG Hong.Information security risk assessmenttechnologyofcyberspace:Areview[J].Information-an InternationalInterdisciplinary Journal,2012,15(11A):4677-4684.

 

[3] 曹建玲,任智.无线传感器网络路由协议综述[J].微计算机信息,2010,28(19):3-5.CAOJianling,REN Zhi.Asurveyonroutingprotocolsforwirelesssensornetworks[J].Microcomputer Information,2010,28(19):3-5.(inChinese).

 

[4] 李建中,李金宝,石胜 飞.传感器网络及其数据管理的概念、问题与进 展[J].软 件 学 报,2003,14(10):1717-1728.LIJianzhong,LIJinbao,SHIShengfei.Concepts,is-suesandadvanceofsensornetworksanddatamanagementofsensornetworks[J].JournalofSoftware,2003,14(10):1717-1728.(inChinese).

 

[5] 李建中,高宏.无线传感器网络的研究进展[J].计 算机研究与发展,2008,45(1):1-15.LIJianzhong,GAO Hong.Surveyonsensornetwork research[J].JournalofComputerResearchandDevelopment,2008,45(1):1-15.(inChinese).

 

[6] 于海滨,曾鹏,王忠锋,等.分布式 WSN 通信协议研究[J].通信学报,2004,25(10):102-110.YU Haibin,ZENG Peng,WANG Zhongfeng,etal.Studyofcommunicationprotocolofdistributedsensor networks[J].JournalofChinaInstituteofCommuni-cations,2004,25(10):102-110.(inChinese).

 

[7] 任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1290.REN Fengyuan, HUANG Haining, LINChuang.Wirelesssensornetworks[J].JournalofSoftware,2003,14(7):1282-1290.(inChinese).

 

[8] HEINZELMAN W R,CHANDRAKASAN A,BAL-AKRISHNAN H. Energy-efficient communication

protocolforwirelessmicrosensornetworks[C]//Pro-ceedingsofthe33rd HawaiiInternationalConference onSystemSciences.Hawaii:ACM,2000:1-8.

 

[9] HEINZELMAN W R, CHANDRAKASAN A P,BALAKRISHNAN H.Anapplication-specificprotocol architecturefor wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

 

[10]YOUNISO,FAHMYS.Heed:ahybrid,energy-efficient,distributedclusteringapproachforadhocsensornetworks[J].IEEE Transactionson MobileCompu-ting,2004,3(4):366-379.

 

[11] CAO Jianling,CHEN Yongchao,REN Zhi,etal.Multi-roundclusterbasedmulti-hopclusteringroutingprotocolforwirelesssensornetworks[J].ComputerScience,2013,40(7):67-70.

 

[12]LIQianmu,HOUJun,QIYong,etal.Theruleengineermodelonthehigh-speedprocessingofdisaster warninginformation[J].DisasterAdvances,2012,5(4):432-437.

 

[13]LIQianmu,LIJia.Roughoutlierdetectionbasedsecurityriskanalysis methodology[J].China Communications,2012,9(7):14-21.

 

[14]JENNIFER Y,BISWANATH M,DIPAK G.Wireless sensor network survey [J].Computer Networks,2008,52(12):2292-2330.

 

[15]尚志军,曾 鹏,于 海 斌.无线传感器网络节点定位问题[J].计算机科学,2004,31(10):35-38.SHANG Zhijun,ZENG Peng,YU Haibin.Nodelocalizationproblem in wirelesssensornetworks[J].ComputerScience,2004,31(10):35-38.(inChinese).

 

[16]宓小土,高峰,章白瑜,等.无线传感器网 络 安 全 性 问题[J].解 放 军 理 工 大 学 学 报:自 然 科 学 版,2011,12(1):42-47.MIXiaotu,GAOFeng,ZHANGBaiyu,etal.Securi-tyinwirelesssensornetworks[J].JournalofPLA U-niversityofScienceandTechnology(NationalScience Edition),2011,12(1):42-47.(inChinese).

 

[17]赵小敏,毛科技,王正莉,等.基于能量和 距 离 的 分 簇式 WSN 路由协议 设 计[J].解放军理工大学学报:自然科学版,2012,13:393-397.ZHAO Xiaomin,MAO Keji,WANG Zhengli,etal.Designofenergy-distancebasedclusterroutingproto-colinWSN[J].JournalofPLA UniversityofScience andTechnology(NationalScienceEdition),2012,13(4):393-397.(inChinese).

 

[18]KENNEDYJ,EBERHART R.Particleswarm opti-mization[C]//ProceedingsofIEEEInternationalCon-ferenceonNeuralNetworks.Perth:IEEE,1995:1942-1948.

 

[19]CLERC M,JAMESK.Theparticleswarm-explosion,stability,andconvergenceinamultidimensionalcom-plexspace[J].IEEE Transactionson EvolutionaryComputer,2002,6(1):58-73.

 

[20]HAMDAN S A.Hybridparticleswarm optimizeru-singmulti-neighborhoodtopologies[J].InfocompJour-nalofComputerScience,2008,7(1):36-44.

 

[21]MOLINAG,ALBAE.Locationdiscoveryinwirelesssensornetworksusingmetaheuristics[J].AppliedSoftComputing,2011,11(1):1223-1240.

 

[22]ZOU Xueyu,CAO Yang.EffectsofinertiaweightonDPSO-basedsingle-hoproutingprotocolforwireless sensornetworks[C]//Proceedingsofthe7th World Congress on Intelligent Control and Automation,Chongqing:IEEE,2008:6707-6710.

 

[23]BAESH,LEESJ,SU W,etal.Thedesign,implementationand performanceevaluationoftheon-de-mandmulticastroutingprotocolin multihop wirelessnetworks[J].IEEENetwork,2000,14(l):70-77.

 

本站系非营利性学术网站,所有文章均为学术研究用途,如有任何权利问题,请直接与我们联系。

 

(编辑:肖哲媛)

所属类别: 期刊论文

该资讯的关键词为:分簇;安全性;粒子群算法;局部最优解;无线传感网