基于磷虾群算法的无线传感器网络QoS任播路由算法*

徐 昕，顾云丽，张嫣娟

（1.南京信息工程大学江苏省网络监控中心，南京210044；2.南京信息工程大学计算机与软件学院，南京210044）

基于磷虾群算法的无线传感器网络QoS任播路由算法*

徐 昕1，2*，顾云丽1，2，张嫣娟2

（1.南京信息工程大学江苏省网络监控中心，南京210044；2.南京信息工程大学计算机与软件学院，南京210044）

无线传感器网络多约束QoS任播路由问题是一个NP难题，提出一种基于磷虾群算法的优化策略来解决该路由问题。该算法采用适应度函数和全局最优个体位置更新方法来寻找无线传感器网络中满足多QoS约束的最优任播路由，并加入遗传繁殖机制中的交叉与变异操作以加快优化速度。实验验证了该算法的有效性，实验数据表明相比较粒子群优化算法，该算法在算法效率和可扩展性性能上具有较好的性能；具有较快的收敛速度，从而适用于对路由选择有时延敏感的网络。

无线传感器网络；路由算法；磷虾群算法；任播

磷虾群算法KH（Krill Herd Optimization）是近年来由Gandomi［1］提出的一种新型的元启发式群体智能优化算法。该算法的主要思想是模仿磷虾个体在食物位置和磷虾群密度等因素影响下的移动过程，因此具有在连续空间的非线性优化性能。

磷虾群算法提出后，收到一些学者的极大关注并应用于各个科研领域。Deng［2］采用磷虾群算法优化移动服务共享组合问题；针对损耗和馈线超载等问题，Rostami［3］通过磷虾群算法优化电动汽车充电负荷；Younesi［4］采用磷虾群算法优化永磁同步电机的转速和转矩控制器参数，以尽量减少稳定状态下速度跟踪误差；Sultana［5］研究关于磷虾群算法在配电网电容器中的优化应用。在应用中，有学者还对磷虾群算法进行了改进。如Mukherjee［6］提出一种混沌磷虾群算法，并用来最优化处理无功优化调度电力系统问题；王磊［7］构造一种启发式二次对立搜索算子以提高磷虾群算法的全局探索能力；Fattahi［8］提出一种模糊磷虾群算法，该算法可以动态地调节每一轮探索过程中磷虾的探索范围；Bulatovic［9］对磷虾群算法中交叉因子进行改进从而加快寻优速度，并将其应用在四连杆结构优化设计问题中。

由于磷虾群算法比较新颖，以往的研究主要集中在工程优化领域中。本文尝试将磷虾群算法应用到无线传感器网络WSN（Wireless Sensor Networks）多约束QoS任播路由领域中。

WSN节点能量受限于有限电源（电池），节点传输能力较弱，监控范围较大。因此，为了节能和能耗均衡等目的，在WSN中往往部署多个基站（Sink），节点可以根据路由状况将监测信息任播（Anycast）至任一基站处。WSN往往对路由能耗、传输时延等有服务质量QoS（Quality of Service）约束，这种多约束路由问题是一个NP难题［10］。以往有学者采用遗传算法、蚁群算法、粒子群算法等智能算法解决多约束QoS网络路由问题［11-13］，本文尝试采用磷虾群算法来解决多约束QoS路由问题。

1 问题描述

WSN拓扑结构抽象表示为连通图G（V，E）。其中，V为所有传感器节点的集合，共N个节点，E为节点间有向通信链路的集合。本文标记：A为某任播地址；G（A）为共享A的通信组成员集合（即Sink节点集合）；Ai为G（A）中第i个组员；M为G（A）组员数目。为保证监测数据分组能安全迅速到达任一Sink，本文规定发送节点s需同时向k个Sink进行传输，因此需寻找k条任播路径。

与传统网络的QoS需求略有不同，WSN由于节点受能量限制，其路由的重要指标之一是节省能耗。而且，WSN路由还要尽量保证能耗均衡，这是由于一旦有节点快速耗尽能量，该节点区域将无节点负责监测和转发分组，从而导致网络分割；由于WSN节点传输能力较弱，要求能在低能耗以及不稳定的网络情况下仍能提供安全可靠的数据传输。除此以外，WSN往往用于军事、环境监控，因此还要求数据具有时效性，对网络传输延迟有着严格的要求，超时传送到Sink节点的数据将毫无意义，甚至成为扰乱信息影响整个系统监测。

本文WSN路由QoS衡量体系设定为：节点能耗E，路径剩余能量比C，端对端时延D，分组丢失率L和路径延迟抖动J。讨论如下：

①节点能耗

传输监测数据分组至Sink处导致路径上各节点能耗E计算如下：

式中，E[p(s,Ai)]是路径p(s,Ai)上各节点能耗之和。而

式中，Es是节点t传输监测分组的能耗，Er是节点t接收监测分组的能耗。在此不讨论节点串听和空闲等待能耗（即便没有监听数据分组传输任务，这部分能耗仍然需要消耗）。发送和接收k比特数据的能耗计算如下：

其中，n为衰减指数，本文设定为2；d为发送节点与接收节点之间的距离；节点发送分组时，需要放大讯号发送，其能耗参数记为Eamp；发送或接收分组时在电路运作方面有一定的能耗，记为Eelec。

②路径剩余能量比

在WSN中，有些节点会出现能耗过快的现象，从而使得网络生存期较短（网络生存期定义为到第一个节点失效的时间）。为避免或减轻该现象，本文采用路径剩余能量比指标C来尽量减少对能量较低的节点的使用。

其中，E(t)是节点t当前剩余能量，Einit(t)是节点t的初始能量。本文设置能量比低于阈值C′的节点只参与到自己主动发起的监测数据汇报至Sink的传输任务，但不再参与到其他节点发起的分组转发任务中。

③端对端时延

传输监测数据分组到达Sink的端对端时延D计算如下：

式中，D[p(s,Ai)]是分组在路径p(s,Ai)上各节点的时延。而

式中，Ds(t)是监测分组在节点t的传输时延；Dq(t)是监测分组在节点t的排队等待时延。

④分组丢失率

在WSN中，往往由于无线链路质量问题导致数据传输失败。除此以外还存在隐终端问题（hidden terminal problems）的传递碰撞导致分组传递失败。

传输监测数据分组到达Sink的分组丢失率计算如下：

式中，L[p(s,Ai)]是路径p(s,Ai)上分组丢失率。

式中，L(t)是在节点t的分组丢失率。

⑤延迟抖动

传输监测分组至Sink处延迟抖动J计算如下：

式中，路径p(s,Ai)的延迟抖动J[p(s,Ai)]计算如下：

其中，J（l）是链路l的延迟抖动。

将WSN多约束QoS任播路由问题转化为一个最优化数学问题。优化目标是在满足以约束条件下寻找到能耗最小的优化目标。

将上述多约束优化问题转化为如下无约束优化问题：

其中，

式中，C′，D′，L′和J′分别是路径剩余能量比、端对端时延、分组丢失率和延迟抖动的QoS约束值；ω0，ω1，ω2，ω3，ω4是归一化系数，取值范围在[0,1]。

由于f0，…，f4等值计量单位不一致，数值之间差距较大，为方便给出各自的权值系数，采用最小-最大规范化方法将各自的实验值映射到[0,1]区间，如f0被映射到f0'的计算过程如下：

由此，优化问题转为

Minimize：

2 磷虾群算法优化

磷虾群算法是近年来根据磷虾个体的群集行为提出的一种启发式算法。在磷虾群整体迁移过程中，每个个体磷虾都在一定范围内受到相邻磷虾的吸引或排斥。以磷虾个体的位置为设计变量，给定适应度函数，磷虾群算法从而可以在多维搜索空间寻找食物（优化值）。

根据磷虾的位置移动变化情况，其算法的主要步骤如下：

①趋光性群集运动

在种群中，每只磷虾的移动使得整个磷虾群的位置时时刻刻都在发生变化。磷虾i的移动方向将受到其邻近磷虾、最优个体以及种群排斥效应的影响。磷虾i的移动向量计算如下：

式中，Vmax是磷虾群体最大引导速度；表示磷虾i的上一次位置变化；ωn是权值，取值在［0，1］之间。为邻近磷虾个体对磷虾i的诱导方向向量；为群体最优个体对磷虾i的诱导方向向量，其计算分别如下：

其中，Ni是邻近磷虾个体的数量；fi，fj，fworst和fbest分别是磷虾i，磷虾j，当前最差和最好的目标函数值；Xi和Xj分别是磷虾i和磷虾j的位置；ξ是取值在［0，1］之间的随机值；I和Imax分别是算法当前和最大迭代次数。

②觅食行为

磷虾i的觅食行为描述如下：

式中，Fi为磷虾i觅食导致的位置变化；ωx为权值；Vf为觅食速度；βi为磷虾i觅食方向向量。

③随机游动行为

磷虾i的随机游动行为描述如下：

式中，Dmax为磷虾个体最大扩散速度；δ为随机方向向量。

④位置更新

式中，Zi为磷虾i的位置矢量，Δt为时间间隔。

算法中，对网络中所有节点编码，将从源节点到任播组组员的一条路径序列编码设为一个可行解。设任播组员数目为M，源节点至组员Ai共有j条可行路径，其中第k条路径（解）表示为Pik，该解是一个数字序列。因此，至组员Ai的解为向量Pi=(Pi1,Pi1,…,Pij)。由此可知，算法解集空间是一个M维的向量空间P1,P2,…,PM。如图1中，路径P11=S-n1-n2-n3-n4-n5-A1可以编码表示为0-1-2-3-4-5-11，P12=S-n6-n7-n3-n4-n5-A1可以编码表示为0-6-7-3-4-5-11，向量P1=(P11,P12)，算法解集空间为(P1,P2)。

初始磷虾群（初始解）可通过图的深度优先搜索算法随机产生，即将随机找到的Np条从源节点到任播组员的路径（解）作为磷虾群的初始位置。

图1 交叉和变异示意图

为加快优化速度提高优化能力，磷虾群算法还将遗传繁殖机制应用到优化过程中，主要包括交叉和变异两个操作。

①交叉操作

磷虾个体以一定概率同挑选出的优秀个体进行交叉操作，操作如下：

式中，crossover（）表示交叉操作；Xgood是挑选出的优秀个体。

②变异操作

磷虾个体以一定概率基因变异，操作如下：

以图1为示意图举例说明交叉和变异操作。设已寻找到任播路径P11=S-n1-n2-n3-n4-n5-A1，P21=S-n6-n7-n3-n8-n9-A2，如图中黑线所示，通过交叉可以生成任播路径P22=S-n1-n2-n3-n8-n9-A2，P12=S-n6-n7-n3-n4-n5-A1，如图中红虚线所示。任播路径P21通过变异操作可以生成任播路径P23=S-n6-n7-n10-n8-n9-A2。

算法具体流程如下：

输入：网络结构图G=（V，E）；k值；最大扩散速度Dmax，时间间隔Dt，最大迭代次数Imax；权值ω0,…ω4,ωn和ωx；发送和接k比特数据的能耗分别为ES和Er；种群规模NP。

Step 1 通过图的深度优先搜索算法随机产生的Np条路径，编码生成解集空间；

Step 2 计算每个磷虾的适应度，确定当前最优个体；

Step 3 根据磷虾趋光性群集运动、觅食运动和随机游动等行为（式（25）～式（29）），计算磷虾个体位置变化；

Step 4 更新磷虾群个体位置（式（30）），计算新的适应度值；

Step 5 分别按照概率α和β，执行交叉和变异操作，评估新产生磷虾个体的适应度值；

Step 6 IfI＜ImaxI=I+1；goto Step 2.

Else 算法结束.

输出：最优磷虾个体对应的路径（最优解）

4 实验设计与分析

以粒子群算法作为对照算法来验证本文所提算法的有效性及其效率。

4.1 对照算法介绍及算法性能比较分析

粒子群优化算法PSO（Particle Swarm Optimization）将每个个体看作是N维搜索空间中的一个没有体积的微粒，该粒子的位置对应于优化问题在搜索空间的一个可行解。粒子在搜索空间中以一定的速度飞行，这个速度根据该粒子本身的飞行经验和同伴的飞行经验来动态调整。其第i个微粒表示为Xi=(xi1,xi2,…xiN)，其经历过的最好位置记为pbest，群体中所有粒子经历过的最好位置为gbest。

粒子群算法的主要思想是：在每一轮迭代中，（a）粒子根据加速因子更新自己的速度和位置；（b）对每个粒子，将它的适应值和它经历过的最好位置pbest作比较，如果前者较好，则将其作为当前的最好位置pbest；（c）对每个粒子，将它的适应值和全局所经历最好位置gbest的作比较，如果前者较好，则重新设置gbest的索引号。

由此可知，粒子群算法主要是通过不断更新粒子的位置来寻优，这与磷虾群算法在优化过程中有很大的相似之处（两者在移动过程中，都以当前个体最优位置和全局最优位置作为其中一个参考对象）。

但粒子群算法对粒子移动的算法设计比较简单，而磷虾群算法的移动规则更加复杂且符合真实世界中磷虾实际移动规律［1］；粒子群算法缺乏磷虾群算法中觅食行为和随机游动等操作；相比较磷虾群算法，传统粒子群算法没有交叉和变异操作，算法比较简单，因此在搜索解空间时，有时会出现粒子在全局最优解附近振荡的现象，从而有时无法找到全局最优解。文献［1］等其他文献给出数十个算例证明磷虾群算法优化效果优于传统粒子群算法。

将粒子群算法应用到多约束QoS路由问题已有较多的研究成果［11-12］，本文仿真实验比较磷虾群算法在多约束QoS路由问题中的算法性能。

4.2 仿真实验和分析

以图1所示的网络拓扑结构进行仿真实验来评价本文算法有效性。

图1中五元组(E,C,D,L,J)分别表示该节点的接收和传输能耗，剩余能量比，接收和传输时延，分组丢失率L和延迟抖动。QoS约束(C′,D′,L′,J′)设置为（3，35，0.4，20）。ω0，ω1，ω2，ω3，ω4设为0.2，初始磷虾群为路径P11，P21和P21。很显然，初始路径都无法满足给定QoS要求。

源节点至任播组员路径的(E,C,D,L,J)值和f[p(s,A)]值如表1所示。

表1 各路径的(E,C,D,L,J)值和f[p(s,A)]值

由表1可知，路径P22的适应度函数值最佳。以初始路径P11，P21和P21为初始磷虾种群，通过磷虾群算法的交叉、变异和移动等操作，不断寻找更佳f[p(s,A)]值，30轮迭代优化后，找到最优解P22=S-n1-n2-n3-n8-n9-A2。该路径具有最佳适应度函数值且满足给定QoS要求。

模拟一个具有N个（N=100）节点的网络，均匀分布在100 m×100 m的矩形区域内；节点传输半径r=30 m；指定Sink（基站、任播组员），设置任播组员（Sink）数目M=6；设定任播时需向k个Sink汇报（k=2）；Eamp=100 pJ/（bit/m2），Eelec=50 nJ/bit；传感器节点以参数λ=0.05的泊松分布汇报监测事件至任意k个Sink，监测数据分组大小为1 kbyte；QoS约束(C′,D′,L′,J′)设置为（10，20，0.3，30）。以基于传统粒子群算法优化的多约束QoS路由算法作为对照算法，来评价本文算法的优化效率。

寻找满足QoS约束条件的k条任播路径，观察适应度函数f[p(s,A)]的收敛情况。实验结果如图2所示。

图2 适应度函数f[p(s,A)]与迭代次数

从图2中可知，在约第60次迭代后，适应度函数f[p(s,A)]的平均值在连续迭代过程中几乎没有变化，表明算法已经收敛到最优路径。从实验结果看，相比较粒子群算法，本文算法适应度函数f[p(s,A)]值略微占优。这是由于相比较传统粒子群算法，磷虾群算法中磷虾移动规则更加贴近实际磷虾移动规律，磷虾除群集运动以外，还有觅食行为和随机游动行为，因此算法更加复杂。除此以外，磷虾群算法还增加遗传繁殖机制的交叉和变异操作，算法寻优能力较强，不易陷入局部最优。而且算法具有较快的收敛速度，从而在对路由选择有时延敏感的网络中具有更好的表现。

由于WSN往往规模很大，因此其路由算法应该具有较好的可扩展性。本文不断调节网络节点数目N（40-100），网络矩形区域也相应调整。观察不同网络规模下适应度函数的值，结果如图3所示。

由图3可知，随着网络规模增大，两者算法的适应度函数f(p(s,A))的值也随之增长，增长曲线比较平稳。与粒子群算法相比，本文算法在不同网络规模下都有较好的优化值。这是由于相比较传统粒子群算法，磷虾群算法在复杂问题下仍具有较好的全局寻优能力［1］，而传统粒子群算法则较容易在陷入局部最优，从而影响其优化表现。

图3 适应度函数f[p(s,A)]与节点数

以适应度函数f[p(s,A)]值在连续迭代中方差小于0.001为终止条件，本文继续观察不同网络规模下所需优化时间，结果如图4所示。

图4 优化时间与节点数

由图4可知，随着网络规模增大，两者算法的优化时间也随之增长。与传统粒子群算法相比，磷虾群算法在复杂问题环境下，仍具有较强的算法寻优能力和收敛速度［1］。因此，在不同网络规模下，相比较粒子群算法，磷虾群算法优化时间较占优。

5 结语

针对磷虾群算法具有非线性优化的特点，提出一种基于磷虾群算法优化的WSN多约束QoS任播路由算法。该算法采用适应度函数来寻找WSN中满足QoS约束的最优任播路由，并加入遗传繁殖机制中的交叉与变异操作以加快优化速度。实验数据表明，相比较基于传统粒子群算法的多约束QoS路由算法，本文算法在算法效率和可扩展性上占优。而且本文算法具有较快的收敛速度，从而在对路由选择有时延敏感的网络中具有较好的表现，但有时也有必要对其进行改进以避免早熟收敛。

［1］Gandomi A H，Alavi A H.Krill Herd：A New Bio-Inspired Optimization Algorithm［J］.Communications in Nonlinear Science and Numerical Simulation，2012，17（12）：4831-4845.

［2］Deng S，Huang L，Taheri J，et al.Mobility-Aware Service Composition in Mobile Communities［J］.IEEE Transactions on Systems，Man，and Cybernetics：Systems，2016，PP（99）：1-14.

［3］Rostami M A，Kavousi-Fard A，Niknam T.Expected Cost Minimization of Smart Grids With Plug-In Hybrid Electric Vehicles Using Optimal Distribution Feeder Reconfiguration［J］.IEEE Transactions on Industrial Informatics，2015，11（2）：388-397.

［4］Sultana S，Roy P K.Oppositional Krill Herd Algorithm for Optimal Location of Capacitor with Reconfiguration in Radial Distribution System［J］.International Journal of Electrical Power and Energy Systems，2016，74（2016）：78-90.

［5］Mukherjee A，Mukherjee V.Solution of Optimal Reactive Power Dispatch by chaotic Krill Herd Algorithm［J］.IET Generation，Transmission&Distribution，2015，9（15）：2351-2362.

［6］王磊，张汉鹏，张东宁.基于对立搜索和混沌变异的磷虾觅食优化算法［J］.控制与决策，2015，30（9）：1617-1622.

［7］Fattahi E，Bidar M，Kanan H R.Fuzzy Krill Herd（FKH）：An Improved Optimization Algorithm［J］.Intelligent Data Analysis，2016，20（1）：153-165.

［8］Bulatovic R R，Miodragovic G，Boskovic M S.Modified Krill Herd（MKH）Algorithm and Its Application in Dimensional Synthesis of a Four-Bar Linkage［J］.Mechanism and Machine Theory，2016，95（2016）：1-21.

［9］EkbataniFard G H，Monsefi R，Akbarzadeh-T M R.A Multi-Objective Genetic Algorithm Based Approach for Energy Efficient QoS-Routing in Two-Tiered Wireless Sensor Networks［C］//Proc of the 5th IEEE International Symposium on Wireless Pervasive Computing，2010：80-85.

［10］Cheng L，Niu J，Cao J，et al.QoS Aware Geographic Opportunistic Routing in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2013，25（7）：1864-1875.

［11］Sun J，Fang W，Wu X，et al.QoS Multicast Routing Using a Quantum-Behaved Particle Swarm Optimization Algorithm［J］.Engineering Application of Artificial Intelligence，2011，24（1）：123-131.

［12］解志斌，于谦，沈斌，等.一种新的基于粒子群优化的双簇头分簇路由算法［J］.传感技术学报，2013，26（8）：1135-1139.

［13］王镇，刘学军.WSN中基于蚁群算法的QoS路由协议［J］.传感技术学报，2011，24（11）：1625-1631.

徐 昕（1975-），男，江苏省南京市人，博士，南京信息工程大学计算机与软件学院副教授，主要研究方向为无线传感器网络路由技术，xuxin@nuist.edu.cn；

顾云丽（1978-），女，江苏省连云港人，博士，南京信息工程大学计算机与软件学院讲师，主要研究方向为无线传感器网络路由技术，guyunli@nuist.edu.cn。

A QoS Anycast Routing Algorithm for Wireless Sensor Networks Based on Krill Herd Optimization*

XU Xin1，2*，GU Yunli1，2，ZHANG Yanjuan2
（1.Jiangsu Engineering Center of Network Monitoring，Nanjing University of Information Science and Technology，Nanjing210044，China；2.College of Computer and Software，Nanjing University of Information Science and Technology，Nanjing210044，China）

Since the multiple constrained QoS anycast routing algorithm for wireless sensor networks（WSN）is a NP-complete problem，a routing algorithm based on krill herd optimization is proposed for this problem.By using the fitness function and updating the global best position in WSN，the proposed algorithm finds the optimal anycast routes which meet QoS constraints.Moreover，crossover and mutation operators in genetic reproduction mechanisms are adopted for accelerating optimization speed.Experimental results show that the algorithm is effective.In comparison with the optimization scheme based on particle swarm optimization，simulation experiments results show that the performances of efficiency and scalability of the proposed algorithm is better；the proposed algorithm has a faster convergence speed，thus it is especially applicable to the network which is delay-sensitive to route selection.

wireless sensor networks；routing algorithm；krill herd optimization；anycast

TP393

A

1004-1699（2016）12-1893-06

��6150P

10.3969/j.issn.1004-1699.2016.12.019

项目来源：南京信息工程大学大学生科技创新项目（201610300212）

2016-04-20修改日期：2016-07-28