基于QoS-PSO 的无线传感器网络路由方法

刘 敏,徐世军,孙思毅,严隽薇

(同济大学 电子与信息工程学院, 上海201804)

无线传感器网络(w ireless sensor network ,WSN)由大量密集部署在监控区域的微型廉价低功耗传感器节点构成, 通过无线通信方式形成一个多跳的无线网络系统[1].无线传感器网络在军事、民用和工业生产等领域具有广阔的应用前景.与传统网络相比,其节点的能量、通信和计算能力较有限, 网络设计需考虑容错性、可扩展性、可靠性和节能等需求[2-3].

随着网络的飞速发展, 一些新的问题也随之而来.最为关键的问题是网络如何满足应用的需求,也就是网络的服务质量(quality of service,QoS)的问题[4] .对那些有带宽、延时、延时抖动等特殊要求的应用来说, 现有的尽力而为的服务无法满足服务质量的需要.由于应用和网络拓扑结构的特点决定了无线传感器网络的QoS 的研究的重要性, 因而有必要在网络路由协议中研究Q oS .

作为一种新的进化计算技术, 微粒群优化(particle sw arm optimization ,PSO)算法是一种很有效的搜索与优化技术.它除了具有简单、通用、鲁棒性强和适于并行处理等优点外, 还具有采用实数编码的优势.粒子群优化算法近些年得到迅速发展,已广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域[5-7].

本文对微粒群算法和无线传感器网络路由进行了研究,提出了综合服务质量(QoS)度量值,以综合Q oS 为微粒群算法的目标函数,实现了对无线传感器网络路由优化的迭代过程, 并与传统算法的结果进行了比较,得到了满意的结果.

1 WSN 的综合QoS 指标

1.1 QoS 路由问题

路由的Q oS 度量值是通过量化的各QoS 指标来计算的.这些度量值可以是一个或多个参数.例如,延时、带宽、抖动等.保证QoS 的路由协议是指在路由建立时, 考虑延时、丢包率、带宽等Q oS 参数,从众多的可行路由中选择一条最适合的QoS 应用要求的路由.

基于QoS 路由的目的就是在网络中寻找最优路径,要求从源节点出发, 到达目的节点, 且满足所有的QoS 约束条件, 达到特定的服务水平, 这里的特定的服务水平不是单指某一个指标而是各QoS指标的一种平衡.

首先建立无线传感器网络的模型.一个无线传感器网络可以定义为无向图G(V,E), 其中V是具备无线连接的传感器节点的集合, 网络中有n+1 个节点,V={v0,v1,v2,v3,…,v n},每一个节点的无线通信半径为r i,通信区域为Avi,边e=(vi,vj)∈E表示一对节点(v i,v j)的双向无线连接.G 中的一条路径P(v1,v n)是边的有序组合序列,P(v1,vn)=((v1,v2), (v2,v3), …, (vi-1,vi),…,(v n-1,vn)).

对任一路径P(v s,vd),其中vs和v d分别代表源节点和目的节点, 可定义综合QoS 指标.本文考虑延时、带宽和包丢失率.路径P(vs,vd)的QoS 可以在每一个节点和每一条链路上得到体现, 对于任一网络节点v∈V,分别为延时函数delay(v), 带宽函数bandw idth(v), 包丢失率函数packet_ loss(v)和能量函数energy(v).相应地对于网络中的任一链路e=(vi,vj)∈E也有对应的QoS 指标,分别为延时函数delay(e)、带宽函数bandwidth(e)、包丢失率函数packet_loss(e)和能量函数energy(e).

通过对节点和链路的QoS 指标的定义, 可以计算的路径的QoS 指标.对于给定的源节点vs∈V,目的节点vd∈V,一条路径P(vs,vd)对应的Q oS 指标存在下列关系:

如果路径P(vs,vd)是一条满足各QoS 指标的路径,必须满足如下条件:

其中D,B和PL是网络的QoS 要求.

1 .2 综合QoS 的应用

在定义了无线传感器网络路由模型的各QoS函数后, 建立应用到每一条路径上的综合QoS 指标.这一指标计算的前提是每一项Q oS 指标都符合其QoS 约束要求, 如果有一项不符合, 则指标对于综合QoS 的贡献大为降低,并产生对于综合QoS 的负面和惩罚性的影响.

如对于延时指标fdelay ,如果Delay(P(vs,vd))＜D,即路径的延时满足约束条件,则

其中取k接近于1 如0 .9,那么fdelay的值将在0 .9 到1 之间.如果Delay(P(v s,vd))＞D,表明路径的延时指标不能满足应用对于延时的约束要求,则

这样fdelay的值将非常小,在0 到0 .1 之间.另两个指标带宽fbandwidth和包丢失率fpacket_loss,进行同样的处理.最后的综合QoS 值即是对3 个QoS 指标函数的综合乘积而得.

综合QoS 的值在0 到1 之间.

在无线传感器网络中, 每一个节点都充当了一个路由器, 存放着一张路由表,在每一次的路由选择中起着路由路径发现的作用.表1 给出了一个路由表的示例, 表中第一列对应着目标节点,第一行是源节点A的邻居节点.表中的值代表了从节点A经过其邻居节点到达目的节点的路径的综合QoS 的指标,例如从节点A经过邻居节点C到达目标节点Y的综合QoS 指标是0 .43 ,而节点A经过邻节点D到达目标节点Y的综合QoS 指标高达0 .89 .这样,用综合QoS 指标代替了传统路由表中的各个QoS指标或者能量指标, 只用一个指标即完成了对于每个节点路由表的建立.

表1 节点A 的路由表Tab.1 Routing table of node A

2 基于PSO 的WSN 路由优化

将路由的发现优化过程看成是一个最优目标的发现过程,可以看到网络中的最佳路径的发现, 完全类似于微粒群算法中通过种群间个体协作来实现对问题最优解的搜索.

2.1 微粒群算法(PSO)

微粒群算法PSO 是由Kennedy 和Eberhart 等人于1995 年提出的一种基于种群搜索的自适应进化计算技术[7].算法最初受到飞鸟和鱼类集群活动的规律性启发, 用组织社会行为代替了进化算法的自然选择机制, 通过种群间个体协作来实现对问题最优解的搜索.PSO 算法随机产生一个初始种群并赋予每个微粒一个随机速度,在飞行过程中, 微粒的速度通过自身以及同伴的飞行经验来进行动态调整,整个群体有飞向更好搜索区域的能力.由于PSO算法概念简单、实现容易、参数较少、能有效解决复杂优化任务,故在过去几年中获得了飞速发展.采用微粒群优化算法用于无线传感器网络的路由算法应该是一种比较好的选择.

将问题的多个可行解的集合称为一个种群(sw arm),种群中每个元素(可行解)称为一个微粒(Particle),微粒的个数称为种群规模(size).用n维向量x i来表示第i个微粒的位置,vi来表示微粒的速度,微粒在搜索空间飞行过程中, 它自身所经历的最佳位置记为Pbesti,在群体中,所有微粒经历过的最佳位置用Pgbest表示,微粒在每一代中的速度和计算评价函数的位置通过如下两个公式计算:

其中, ω为惯性权重(inertia w eight), η1和η2为两个学习因子, 通常η1=η2=2 .0 .rand()为介于(0,1)之间的随机数.速度公式(4)的第1 部分称为动量部分,表示微粒对当前自身运动状态的信任, 为微粒提供了一个必要动量, 使其依据自身速度进行惯性运动.第2 部分称为认知部分,代表了微粒自身的思考行为, 鼓励微粒飞向自身曾经发现的最佳位置.第3部分称为社会部分, 表示微粒间的信息共享与相互合作, 它引导微粒飞向微粒群中的最佳位置.这3 部分之间的相互平衡和制约决定了算法的主体.

通过上面的分析,清楚地表明PSO 是一种基于迭代的优化算法.系统初始化为一组随机解, 然后通过迭代找到最优解.在搜索过程中, PSO 结合本地及全局信息, 但根据自身的历史信息, 而且综合利用群体中邻居粒子的相关信息来调整当前位置,从而通过迭代搜索求得优化解.在每次迭代过程中, 粒子通过跟踪两个“ 极值” 来更新自己:第一个是粒子本身所找到的最优解,这个解叫做个体极值;另一个是整个种群目前找到的最优解,这个极值是全局极值.另外也可以不用整个种群而只是用其中一部分作为粒子的邻居, 那么在所有邻居中的极值就是局部极值.

2 .2 初始路由路径的确立

基于Agent 的路由为基于PSO 的路由提供了很好的初始路径.网络中每个节点都会为其余所有的节点创建和维护一张路由表, 在源节点s和目的节点d之间会建立多条路由.当一个源节点需要发送一个数据报到目的节点,但在源节点的路由表中没有发现对应路由信息, 源节点就会希望与其目的节点建立路由, 这时, 启动一个基于Agent 的路由发现机制.路由发现机制是由源节点生成一个前向A gent,并写入自己的地址和报文创建时间, 然后以广播方式发送给周围的每一个相邻节点.前向A gent 在路由发现过程中是以广播形式传播前向A gent .

当前向Agent 到达目的节点时, 一条路由路径就得到了, 转换成后向Agent,采用单播的方式将反向Agent 沿着前向Agent 的路径回到源节点, 同时反向Agent 会根据路由网络情况对沿途的节点和节点上的路由表做出调整.这一过程就是基于Agent的路由发现过程.

由于前向Agent 采用的是广播方式, 故到达目的节点的前向A gent 会有多个,同时意味着在源节点和目的节点之将建立了多条路径.而这多条路径就是PSO 对应的初始种群.对比PSO 算法, 得到的多条路径即为多个可行解的集合, 为一个种群(sw arm),每一个路径被认为是一个微粒(particle).

2.3 基于QoS-PSO 的路由

PSO 算法的迭代公式说明当一条路径在算法的驱动下搜索获得新的路径是通过路径的随机微调获得的.然而在实际实现中,路径的改变vi是不可得到的, 因此采用改变路径经过的节点到其附近的节点的方法.

假定一条由源节点vs到目的节点v d的路径为

如果节点vi是随机选取的路径中的一个节点,如果存在v i的一个邻节点v,与路径P(vs,vd)中的两个节点vm,vn为邻节点,其中m∈{s,…, 1,…,i-1},n∈{i+1,…,n,d}, 则路径P′(v s,vd)=(v s,v1,v2,v3,…,v m,v,v n,…,v d)是路径的一个相邻路径.

建立了源节点v s到目的节点v s路径P(v s,v d)的一个随机相邻路径,为了应用PSO 算法,对照PSO的算法要求和相邻路径的定义, 将无线传感器网络中的元素与PSO 算法作如下的对应.

设源节点v s到目的节点v d路径的集合为

P对应为一个粒子群, 其中每一个粒子是Pi(v s,v d),粒子P i(vs,v d)包含了PSO 算法需要的信息:①P i(v s,vd)=(v s,v1,v2,v3,…,vi-1,v i,v i+1,…,v n,v d)是粒子位置信息;②Ppbesti(v s,v d)表示了粒子P i(v s,v d)的最优的目标值;③Pgbest(v s,v d)表示了粒子群的最优目标值.

基于PSO思想的路由算法有如下步骤:

(1)选取源节点和目的节点, 利用前向Agent 和后向Agent 建立源节点和目的节点之间的路径集(种群swarm).

(2)为每一个路径(微粒)计算综合QoS ,以取得Pbest,选取最好的Pbest为Pgbest.

(3)依据PSO迭代公式得到新的路径.

(4)计算综合QoS .

(5)当每一个路径(微粒)的QoS 好于对应的Pbest,替换Pbest;当最好的Pbest好于Pgbest,替换Pgbest.

(6)如果算法迭代次数达到指定的最大值或QoS 计算达到要求, 结束算法;否则转步骤(3).

(7)确定路径,修改路由表.

3 实验及结果分析

对于优化的算法, 采用NS2 进行模拟仿真, 加入了PSO 的代码.在模拟实验中,网络范围为100 m×100 m ,网络中的节点假定有相同的发射功率, 节点移动速度为0 .05 m ·s-1,性能指标采用上文所述的综合QoS 指标.路由被PSO 算法不断优化, 以综合QoS 为目标函数, 称作Q oS-PSO,把它和传统算法QoS-AODV(无线自组网按平面距离矢量路由协议)在不同节点数量下进行比较.

如图1 所示, 随着网络中节点数量的增加, 引起了综合QoS 指标的降低.这是因为随着网络中节点的增加,端到端的延时也同样增加,也增加了端到端的hop 距离,同时网络中的节点的通信冲突也增加.在模拟实验中,QoS-AODV 随着节点增加, 综合QoS 指标的下降更为显著, 而QoS-PSO 随节点增加的QoS 的降低幅度较小,甚至逐渐稳定于一定水平.

图1 网络中节点数量与综合QoS 指标的关系Fig .1 Relationship between number of node and comprehensive QoS

4 结语

本文提出了无线传感器网络路由的综合QoS指标, 基于PSO 的路由优化能够有效快速地以综合Q oS 指标进行迭代优化,寻找到更好的路由,满足路由的服务质量的要求.通过与传统算法的比较,得知在WSN 中,基于PSO 算法的路由算法可以获得更高的服务质量.

[1] Akyildiz I, Su W, Sankarasubramaniam Y,et al.Wireless sensor networks:a survey[J] .Computer Networks, 2002,38(4):393.

[2] Chong C Y,Kumar S . Sensor networks: evolution,opportunities, and challenge [J] .Proceedings of the IEE E(S0018-9219), 2003, 91(8):1247.

[3] Estrin D,Govindan R, Heidemann J.Next century challenges :scalable coordination in sensor networks[C] ∥Proceedings of the 5th ACM/ IEEE International Conference on Mobile Computing and Networking .Seattle:ACM, 1999:263-270.

[4] C raw ley E,Nair R, Rajagopalan B,et al.A framework for QoSbased routing in the internet[EB/ OL] .[1998-08-28] .http:∥www.ietf .org/ rfc/ rfc.2386.tx t.

[5] 李爱国, 覃征.粒子群优化算法[J] .计算机工程与应用, 2002,38(21):1.LI Aiguo,TAN Zheng .Particle swarm optimization [J] .Computer Engineering and Application, 2002, 38(21):1.

[6] 许福永, 梅中磊.基于现代超启发式搜索方法的计算机通信网中路由选择优化的研究[J] .兰州大学学报, 2001, 37(2):63.XU Fuyong,ME I Zhonglei .Routing optimization in computer com munication network based on modern ultra heuristic searching method[J] .Journal of Lanzhou University,2001, 37(2):63.

[7] Eberhart R C,Shi Y . Comparing inertia weights and constriction factors in particle swarm optimization[C] ∥Proc of the IEEE Int Conf on Neural Networks.Piscataway :IEE E Service C enter,1995:1942-1948.