一种基于DPSO的无线传感器网络QoS路由算法*

何 筱，石为人，王小刚，邓仲芬

(重庆大学自动化学院，重庆400030)

0 引言

随着无线传感器网络的不断快速发展，不同业务对其网络服务质量(QoS)提出了更高的要求［1］，应用时往往会对延时，带宽，丢失率，代价等多个性能参数同时提出要求。

有序分配路由SAR［2］是第一个面向WSNs提供QoS保证的路由算法。能量感知QoS路由EQR［3］，通过评估链路代价、扩展Dijkstra算法为节点找到符合QoS需求的最小代价路径。文献［4］提出一种满足QoS带宽需求的能量最优的无线传感器网络路由方案，文献［5］提出一种保证服务质量的最小能量路由算法。目前提出的QoS路由算法大多仅考察个别性能指标，不能全面反映传感器网络的QoS需求，且需维护路由参数和网络状态信息的开销较大，能量消耗快。所以，相对传统QoS路由算法，设计满足多QoS参数约束的智能算法具有重要意义。

粒子群优化(PSO)算法［6］是一种源于对鸟群捕食行为研究的新型进化计算方法。它通过群体中个体之间的协作和信息共享来寻找最优解，具有结构简单、参数调整少、收敛速度快及易于实现等特点。本文提出的基于离散粒子群优化无线传感器网络QoS路由(DPSO-QR)算法，将不同的QoS参数定义为不同优化目标，对节点间通信的多个参数目标进行优化，从而为具有不同QoS需求的业务提供满足其特有需求的优化路由，同时，降低网络能耗、延长网络寿命、提高网络服务质量。

1 QoS路由问题的网络模型

本文假设WSNs中节点位置固定，通信半径为R，且具有唯一ID号，形成无向连通图G=(V，E)，V 为网络节点集合，E 为网络链路集合，相邻两节点 vi，vj∈V，eij为节点 vi与vj之间的边，每条边包含4种QoS参数度量:带宽B，时延D，丢包率L，传播损耗C。求解满足4个需求约束条件的问题属于多目标优化问题，假设有一条从节点a到节点b的路径Pab，对Pab路径上的目标函数定义如下:

定义1:带宽Bab取路径所有组成边中带宽的最小值;时延Dab为链路时延之和;链路丢包率Lab见式(1);传播损耗Cab的模型见式(2)

其中，ε为路径损耗系数，取值为50 nJ/bit，k为发送数据包长度，kbit。

由于各参数度量数量级和量纲不同，采用参数适应度对各参数进行规范化处理，公式中带下标up，low的参数分别代表参数需求上限和下限。

定义2:参数适应度定义如下，其中，丢包率适应度B'ab与时延适应度D'ab类似

式中 max Cab为路径Pab中节点一跳通信范围R内最大的能量传播损耗，h为路径Pab的跳数。

通过对路径上目标函数及其适应度的定义，将任意一条路径Pab∈E定义为相应的矢量集合，即目标空间fab=(B'ab，D'ab，L'ab，C'ab)，从而将无线传感器网络 QoS 路由优化问题抽象为多目标优化问题。本文采用算法简单、寻优速度快的PSO算法求解多目标问题，以适应WSNs中节点计算能力较弱的特点和对算法速度的要求，并加入扰动操作解决PSO算法寻优过程中易陷入局部最优的问题。

2 基于离散粒子群的多目标优化策略(MDPSO)

2.1 改进的离散粒子群算法

基本PSO在传统的连续域函数优化领域中，用速度和位置更新2个迭代公式来搜索求解。而多QoS参数约束单播路由问题是一个非线性组合优化问题，属于离散问题［7］，因此，本文结合路由算法特点，对PSO算法进行改进，设计了一种基于离散空间的DPSO策略，改进公式如下

其中，X表示粒子，“⊕算子”是加法运算的扩展，Pi(n)为第n次迭代后粒子i的历史Pareto最优解集Pi中的一个随机解，G(n)为第n次迭代后全局Pareto最优解集G中的一个随机解，λ1，λ2为加速因子，值域为［0，1］。

2.2 离散粒子群算法初始化

任意粒子Xi对应一条从源节点s到目标节点t的随机路径(ID序列)。设源节点粒子Xi群规模为m，迭代次数设为N，任意粒子Xi生成一个空的历史Pareto最优解集Pi，全局生成一个空的全局Pareto最优解集G，G未被更新的迭代次数的阈值设为F。

2.3 加算子

⊕算子用以实现当前解对Pareto最优解的学习。设Pa为当前路径，Pb是相对Pa较好的一条路径，Pa路径的源节点为s，终节点为t。以Pa⊕λPb为例，运算过程如下:

1)根据λ的大小在Pb上随机选取一个路由子片段，长度由λ控制，记为Pb_sub，其源节点为s'，终节点为t'，现将Pb_sub插入Pa路径中;

2)进行插入衔接

左向衔接:若路径Pa中有与Pb_sub源节点s'相同的节点，则将Pa中s～s'的一段截取下来，记为Pa_sub0;若没有与s'相同的节点，则求出一条s'～Pa的一条路径，将此路径的反向路径记为Pnew0，将Pa中s到Pnew0的源节点s″的路径截取下来，记为Pa_sub0;

右向衔接:若路径Pa中有与Pb_sub终节点t'相同的节点，则将Pa中t'～t的一段截取下来，记为Pa_sub1;若没有与t'相同的节点，求出一条t'～Pa的一条路径，将路径记为Pnew1，同样将Pa中Pnew1的终节点t″到t的一段路径截取下来，记为Pa_sub1;

3)将 Pa_sub0，Pnew0，Pb_sub，Pnew1，Pa_sub1连接，删除路径中重复的节点，就得到新路径P'a。

2.4 扰动算子

基本PSO计算过程中容易出现群体陷入局部最优的现象。为保持粒子多样性，提高搜索性能，将采用扰动操作对粒子进行变异。

设任意解的目标向量 U=(U1，U2，U3，U4)，其中，U1，U2，U3，U4分别对应 B，D，L，C 4 种 QoS 参数。当有解 X'要加入全局Pareto最优解集G时，先计算X'与G中解XG∈G之间目标向量的距离。当有‖Uk(X')－Uk(XG)‖＜δk时，δk为根据需求设定的阈值，认为可能陷入局部极小，对该粒子进行一次扰动操作。扰动操作为:放弃粒子当前路径，重新获取一条从源节点s到终节点t的随机路径。

2.5 MDPSO 流程

1)当节点有数据发送需求时，进行算法初始化;

2)利用式(6)、⊕运算，进行迭代计算;

3)每次迭代后，判断各粒子当前解Xi与其历史Pareto最优解集Pi中解XP的支配关系，当有XP＜Xi时，删除XP;当﹁∃XP＞Xi时，将Xi加入Pi中;

4)判断所有当前解 Xi，i∈(1，2…，I)之间的支配关系，保留其中的非支配解X'i，再判断X'i与G中解XG的支配关系，当有 XG＜X'i时，删除XG;当﹁∃XG＞X'i时，计算 X'i与XG的欧几里德距离，判断是否需要扰动，然后将X'i加入G中;

5)当迭代次数达到n或者G未被更新的迭代次数达到F，则输出G;否则，返回步骤(2);

6)根据数据传输的QoS需求，按式(7)计算G中路径适应度fitness，其中，w为数据传输时设定的QoS需求权重。计算完成后取fitness最小的路径转发数据

7)在计算出G后的时间ts内(2 min)，如有新数据发送，返回步骤(6)选择路径;超过ts后，如有新数据发送，返回步骤(1)重新初始化。

3 DPSO-QR整体流程

MDPSO完成了节点需转发数据时路由的选取，但WSN中节点的计算、储存能力都非常有限，若每个节点都使用MDPSO进行全局集中式路由计算，则参数更新将浪费大量的能量，极大限制DPSO-QR算法的扩展性。因此，DPSOQR在MDPSO基础上，设计了局部区域网络参数的获取机制，形成局部集中的计算模式，以实现算法性能与能耗及扩展性之间的折中。

1)Sink节点进行全局网络初始化广播，每隔t's时间都将进行一次全网更新广播;

2)网络节点收到广播后，在自己的通信范围内进行初始化广播，记录H跳范围内(本文H=3)所有路径的适应值矢量集合f，建立局部区域的QoS参数表;

3)节点以自己所在局部区域中剩余能量最大的节点作为自身的局部目标节点，如果Sink在节点的H跳范围内，则以Sink为目标节点;

4)当有数据发送需求时，节点用MDPSO计算出Pareto最优解集G。按待发送的数据对QoS的需求，结合式(7)，选出局部区域最佳路由进行转发。在得到集合G后的时间ts内，将不再重新计算G。ts时间后有数据发送需求时，重新计算G，以适应网络参数的变化;

5)每间隔时间ts，节点将自身和2跳范围内的节点以及路径QoS参数发生变化的部分参数打包，并发送给自己的邻居节点，实现局部区域的QoS参数更新;

6)局部目标节点收到数据后，转到步骤(3)，继续搜索以其为源节点的局部区域最优路由，直至数据传输至Sink。

4 仿真实验

在100 m×100 m的平面区域中随机布撒100个无线传感器节点，Sink节点位于右上角，节点初始能量为1J，最大无线通信半径为20 m;仿真过程中，节点以一定周期产生长度为128 bytes的数据包向Sink节点发送。设网络QoS路由参数度量需求的取值范围为B∈(0，10)，D∈(0，10)，L∈(0，0.1)，且 Bup=6，Blow=3，Dup=20，Dlow=10，Lup=0.1，Llow=0.05。实验中设置w=(0.15，0.3，0.15，0.4)。通过改变数据包发送速率，从1～10 pkt/s来模拟不同的网络负载。仿真分别对DPSO-QR，SAR和EQR算法进行了10次仿真，网络性能对比图如图1～图4所示。

图1 算法带宽均值对比图Fig 1 Comparison diagram of average bandwidth

从图1可以看出:3种算法的路由带宽均值较为接近。由于EQR有固定的带宽阈值，其带宽略优于DPSO-QR和SAR。而DPSO-QR在一定周期内可对环境状态参数进行实时更新，其带宽性能优于SAR。

图2 算法时延均值对比图Fig 2 Comparison diagram of average delay of the algorithm

图2中随着网络数据包发送速率的增加，时延明显增加。这是因为网络中数据流量较大时，冲突碰撞和重传次数增加。由图可知，SAR与EQR算法的平均端到端时延性能接近，DPSO-QR算法的平均端到端时延比SAR和EQR约减少了26.3%，且随着负载的增加上升较为缓慢。

图3中当数据包发送速率较低时，3种算法的路由丢包率都较为接近。随着发送速率增大，DPSO-QR算法的丢包率明显小于SAR和EQR，比SAR约减少了34.4%，比EQR约减少了51.8%。说明DPSO-QR算法在一定程度上降低了丢包率。

图4为不同网络负载下的网络寿命变化情况。本文将网络寿命定义为网络中第1个节点能量耗尽的时间。随着网络负载的增加，网络寿命不断下降，DPSO-QR算法的网络寿命明显比SAR和EQR长，是SAR的1.17倍，是EQR的1.08倍，且随着负载的增加下降较为缓慢。这是因为DPSO-QR的局部集中计算模式有利于降低网络节点能量消耗，有效避免节点快速死亡，延长了网络寿命。

图3 算法丢包率均值对比图Fig 3 Comparison diagram of average packet loss rate of the algorithm

图4 算法网络生存时间均值对比图Fig 4 Comparison diagram of average nework lifetime of the algorithm

5 结论

本文提出的DPSO-QR算法，以经典PSO算法为基础，结合提出的加算子和扰动算子，设计出面向路由建立的多目标MDPSO，以实现QoS路由优化。DPSO-QR解决了当前大多数路由算法难以根据不同业务对QoS的不同需求提供相应保障的问题。仿真验证表明:与SAR、EQR算法相比，DPSO-QR在可为网络不同业务提供QoS保障的同时，有效减小了网络平均端到端时延，降低了丢包率和网络能量消耗，延长了网络寿命。

［1］文 浩，林 闯，任丰原，等.无线传感器网络的QoS体系结构［J］.计算机学报，2009，32(3):432－440.

［2］Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for self-organization of a wireless sensor network［J］.IEEE Personal Commmunications，2000，7(5):16－27.

［3］Akkaya K，Younis M.An energy-aware QoS routing protocol for wireless sensor networks［C］∥Proceedings of the IEEE Workshop on Mobile and Wireless Networks，Washington DC:IEEE Computer Society，2003:710－715.

［4］Lin C R，Liu J S.QoS routing in Ad Hoc wireless networks［J］.IEEE Journal on Selected Areas in Communications，1999，17(8):1426－1438.

［5］余 荣，孙 智，周海军.保证服务质量的最小能量无线传感器网络路由算法［J］.清华大学学报，2007，47(10):1634－1637.

［6］Kenned Y J，Eberhart R.Particle swarm optimization［C］∥Proceedings of the 1995 IEEE International Conference on Neural Networks，1995:1942－1948.

［7］Kenned Y J，Eberhart R.A discrete binaey version of the particle swarm algorithm［C］∥Proceedings of the 1997 IEEE International Conference on Computational Cybernetics and Simulation，1997:4104－4108.