覃科　张亚红

(桂林航天工业学院　计算机科学与工程系, 广西　桂林　541004)



MANET中萤火虫GSO优化的路由协议研究*

覃科**张亚红

(桂林航天工业学院计算机科学与工程系, 广西桂林541004)

针对无线自组网拓扑结构多变、能量受限以及带宽有限的特性，提出一种基于萤火虫GSO优化的路由协议(GSORM)。将节点驻留萤火虫的荧光素值更新规则映射成为节点的移动速度、拥塞程度及剩余能量等统计信息的函数。路由发现、路由选择及路由维护过程由搜索萤火虫、驻留萤火虫及回溯萤火虫协同完成，无须传送大量的控制分组。仿真实验结果表明，与AODV及AntRouting协议相比，GSORM在数据包成功传送率、端到端时延及网络生存时间上均表现出了良好的性能。

GSO; 群智能优化算法;无线自组网;路由协议;网络优化

无线自组网是一种无中心的自组织多跳网络，网络中的节点既是移动终端也是路由器。其随时随地组网的灵活性及抗毁性，使得无线自组网在野外勘测、抢险救灾及军事领域等方面拥有广泛的应用前景。由于节点具有任意移动性，无线自组网的拓扑结构变化频繁，因此高性能的路由协议一直是无线自组网的研究热点。

目前，有许多学者都对无线自组网的路由协议进行了大量的研究，并取得了一定的成果。大多数无线自组网的路由协议都采用单一的标准来作为路由选择的依据。例如DSDV[1]协议和DSR[2]协议选择跳数最少的路由，而AODV[3]协议选择序列号最新的路由。这种单一的路由衡量标准无法满足无线自组网拓扑结构多变、带宽能量受限及无线信道易受干扰的特性。还有一部分路由协议采用了综合的指标来衡量路由。例如MMPEW-DSR协议使用节点剩余能量和传输功率链路状态函数作为路由选择的参数，ABGP协议根据电池剩余量和带宽选择下一跳节点，ARBFAM协议利用名声、可用带宽和最小跳数的多量度指标选择路由[4]。但是多指标的路由选择增加了控制分组的大小和数量，从而增加了网络负担，对整个网络的稳定性和可靠性会带来一定的影响。现有无线自组网路由协议适应能力有限，网络吞吐率较低，稳定性和可靠性都没有得到较好的解决。

群智能优化算法是近年来发展迅速的一种仿生模拟进化算法，具有操作简单、宜于并行处理、收敛速度快且鲁棒性强等特点。其优良的分布式特性和在组合优化问题中的突出表现能够适合无线自组网的特点[5-8]。本文利用群智能优化方法，提出一种基于萤火虫GSO优化的路由选择自适应算法GSORM。该算法将节点的移动速度、节点的拥塞程度、节点的剩余能量以及节点之间的距离等影响网络性能的因素与萤火虫算法中萤火虫的荧光素强度的更新规则相映射，从而对路由的自适应选择进行控制。同时，为了进一步降低通信开销，每个中间节点双向维护多条辅助路径，以提供路径冗余。通过实验发现，本文的算法提高了协议的自适应性和可靠性。在不同移动性及负载的无线自组网中，从数据包成功传送率、端到端时延以及网络生存时间三个指标来看，GSORM的性能均要优于AODV协议和AntRouting协议。

1　萤火虫GSO算法概述

印度学者K.N.Krishnanad和D.Ghose根据仿生学原理，提出了模拟自然界萤火虫求偶和觅食行为的群智能优化方法——萤火虫优化算法(Glowworm Swarm Optimization, GSO)，从而实现在求解空间寻优[9-10]。GSO算法将求解空间中的解模拟为萤火虫个体，每个萤火虫个体都包含各自的荧光素和感知半径。萤火虫个体的荧光素值和其所在的位置即目标函数值相关，目标函数值越优则荧光素值越高[11]。萤火虫个体在感知半径内搜索比自身荧光素值高的个体，按照概率向荧光素值高的个体移动，并更新位置和感知半径。达到一定的迭代次数后，所有的萤火虫个体都将聚集在问题求解空间的最优解位置[12]。

设G=(V,E)为包含n个节点的全连接无向图，V是无向图顶点集合且n=|V|，E是边的集合。每条边的权值等于其两端节点vi、vj之间的欧式距离dij,且dij=dji。萤火虫优化方法被用来搜索图G中源节点vi到目的节点vd的最优路径。为了利用萤火虫优化算法来进行路由选择，无线自组网中每个节点vi都有一个驻留萤火虫Fi，Fi携带该节点的荧光素值Li(t)。节点vi存储并维护当前t时刻邻居节点信息表以及用来记录路由信息的路由表。邻居节点信息表包括如下表项：

•邻居节点vj

•时间T

•vj驻留萤火虫Fj荧光素值Lj(t)

若超过时间T，vi未收到邻居节点vj的Hello消息，则vj不再是vi的邻居节点。

路由表中的表项包括：

•目的节点vd

•下一跳节点vj

•当前节点vi通过节点vj到达vd的荧光素概率值Pij(t)

为了减轻网络负担，路由表按需构建。当需要进行路由发现时，源节点会根据需要创建搜索萤火虫Fs。节点vi上的Fs会根据邻居节点上Fj的荧光素值以及dij来计算节点vj作为下一跳的概率。设Ni(t)为节点vi在t时刻所有一跳邻居节点构成的集合，则当搜索萤火虫Fs位于vi时，它将按照公式(1)来计算vj作为下一跳节点的概率：

(1)

公式(1)中m,n∈N。通过调节m和n的值，可以调整荧光素差值和节点间的距离对搜索萤火虫选择下一跳的影响程度。搜索萤火虫移动到下一跳节点vj后，更新当前位置及邻域半径，邻域集合更新为节点vj的一跳邻居节点集合Nj(t)。

每个节点Fi的荧光素值都按照下式进行迭代更新：

Li(t+1)=(1-ρ)×Li(t)+γ×J(xi(t+1))

(2)

公式(2)中Li(t+1)为t+1时刻节点vi上Fi的荧光素值，Li(t)为t时刻Fi的荧光素值。ρ表示荧光素值的挥发系数，ρ∈[0,1]，γ表示荧光素值增强系数，J(xi(t+1))表示t+1时刻节点vi的适应度函数值大小。

2　基于萤火虫GSO优化的路由协议

2.1协议中的网络环境参数

(1)节点能量λie。无线自组网中的节点大多数都采用电池供电，无法使用固定电源。选择路由时应该尽量选择剩余能量高的节点，从而延长网络的生存时间。Ei表示节点vi的电池最大能量，E’i(t)表示节点vi当前的剩余能量，则参数λie=E’i(t)/Ei用于衡量该节点的能量性能。该参数值越大，则说明该节点的适应度函数值越大，对荧光素值增量的贡献越大。

(2)节点拥塞程度λic。每个节点监视MAC层接口队列，Ci表示节点vi的MAC层接口队列缓存容量，Ci’(t)表示节点vi当前的MAC层接口队列缓存分组数，则参数λic=C’i(t)/Ci反应了当前节点的拥塞程度。若节点vi的λic值超出阈值，则节点vi数据处理能力会大大下降，直至陷入拥塞状态，对后续的数据包采取丢包操作。该参数值越大，说明该节点的适应度函数值越小，对荧光素值增量的贡献越小。

(3)节点的移动速度si。在无线自组网中，节点的移动速度越快，则网络的拓扑结构变化越快，路由的更新越快，从而导致源节点发起路由发现过程的频率增加。因此，节点移动速度越大，说明该节点的适应度函数值越小，对荧光素值增量的贡献越小。

2.2路由发现过程

当源节点vs需要向目的节点vd发送数据时，vs先查看本地路由表，若路由表中没有到达vd的路由，则vs发起路由发现过程。vs向每个邻居节点vj都发送探索萤火虫Fs。每个Fs都有分组编号seq，并将其所经过的节点信息Vn存储到自身数据栈data中。

中间节点vi收到来自邻居节点的Fs后，根据Fs数据栈的节点信息判断是否出现环路，同时根据seq判断该Fs是否为来自不同路径的重复分组。若Fs数据栈的节点信息包含当前节点vi，则出现环路，丢弃该Fs。若该Fs为重复分组，也进行丢弃处理。对于没有出现环路的非重复Fs，节点vi对其进行转发。若节点vi的路由表中有到vd的路由表项，则Fs根据路由表项的荧光素概率值Pij(t)来选择vi到达vd的优化路径。在选择下一跳时，为了加快算法的收敛速度，避免陷入局部最优解，Fs按照公式(3)选择下一跳节点vj：

(3)

(4)

公式(3)中，Ψ为随机数且Ψ∈[0,1]，Ψ0为系统定义的常数且Ψ0∈[0,1]，Ψ与Ψ0之间满足概率p(Ψ≤Ψ0)≫p(Ψ>Ψ0)。这样，在大多数情况下Fs会向荧光素值高的Fj移动，个别情况下Fs随机选择下一跳节点，从而避免陷入局部最优解。若vi的路由表中没有到vd的路由表项，则vi广播Fs。为了避免广播数据包过多占用网络资源，Fs最多被广播3次，若无法到达vd，则该Fs被丢弃。

在公式(2)中，J(xi(t+1))为节点vi的适应度函数值大小，亦可以看做节点vi在t+1时刻荧光素值的增量。有

J(xi(t+1))=f(λie,λic,vi)ΔL

(5)

公式(5)中, ΔL为荧光素增量常量。令

(6)

公式(6)中，βe+βc=1，α、ω和σ均为大于或等于1的调整参数，通过调整参数的值，可以改变节点能量、节点拥塞程度以及节点的移动速度对路由选择的影响程度，从而发现优化的路由。根据公式(2)、(5)、(6)，可得

(7)

Fs移动到vj后，对Fs的数据栈data中所有节点驻留萤火虫的荧光素值按照公式(7)更新，对vj的其他邻居节点驻留萤火虫的荧光素值按照公式(8)更新：

Li(t+1)=(1-ρ)×Li(t)

(8)

同时对vj的路由表进行更新。假设Fs由vi移动到vj后，data中的路径节点为data.node={v1,v2,……,vn,vi}，则更新vj的路由表中通过vi到达v1、v2、……、vn节点的路由表项中的pij(t)，j∈data.node-{vi}。

当Fs到达目的节点vd后消亡，并在vd创建回溯萤火虫Fb。Fb根据Fs中data.node的反方向返回到源节点vs。当Fb通过vj移动到vi后，同样按照公式(7)和公式(8)对vi邻居节点驻留萤火虫荧光素值进行更新，并对vi的路由表信息进行更新。假设Fb到达vi后经过的路径Fb.node={vj,……,vn,v2,v1}，则更新vi的路由表中通过vj到达vi,……,vn,v2,v1节点的路由表项中的pji(t)，i∈Fs.node-{vj}。

Fb到达源节点vs后消亡，vs到vd的路由创建。

2.3路由维护

无线自组网节点vi上的驻留萤火虫Fi以T为时间周期向邻居节点发送Hello数据包来维护本地的连通性。若Fj超过时间T仍未收到Fi发送的Hello信息，则Fj认为vi已经不是vj的邻居节点，将vi节点的信息从vj的邻居节点信息表中删除并更新路由表，将vj路由表中下一跳节点为vi的相关路由表项删除。若Fj收到新的邻居节点Hello信息，则将该节点的信息添加到Fj邻居节点信息表及路由表中。

在vs向vd传送数据包的过程中，若中间结点vi上的Fi发现由于节点的移动导致网络拓扑结构发生变化而出现断链，无法按照原有的路由转发数据包，则Fi会向原有路由的上游节点发送路由错误信息RERR。当vj上的Fj收到Fi发送的RERR包时，删除vj节点中vi节点所对应的邻居节点表项目和路由表项目，并在vj的路由表中查找是否有到目的节点的冗余路由。若vj存在到vd的冗余路由，则按公式(3)选择下一跳节点并按照公式(7)、公式(8)对vj的路由表进行更新。若vj不存在到vd的冗余路由，则vj上的Fj继续向vj的上游节点发送RERR信息，直到找到可用路由。若vs上的Fs收到RERR信息，则重新进行路由发现，寻找新的路由。

3　仿真结果及分析

AODV协议采取按需路由的方式，通过跳数来进行路由选择，能够及时响应网络拓扑结构的变化,是MANET中一种较为成熟、典型的路由协议。AntRouting协议是一种基于蚁群优化的仿生路由算法，通过探索蚂蚁寻找路由，探索蚂蚁在寻找路径的同时会把信息素放置到经过的路径上，每个节点的路由表用信息素浓度值来替代，搜索蚂蚁通过信息素浓度值的大小来选择下一跳节点[13]。为验证本文提出的基于萤火虫GSO优化无线自组网路由协议GSORM性能，将GSORM协议与MANET中典型的AODV协议及同为群智能算法的AntRouting协议在NS2模拟平台上进行仿真，从数据包成功传送率、端到端时延及网络生存时间三个方面评价GSORM协议的性能。

仿真场景1使用随机分布在1 000 m×1 000 m区域内的50个移动节点，节点采用Random Waypoint移动模型，节点的移动速度在0—30 m/s间均匀分布，通过改变节点的停顿时间来模拟不同的网络移动性。节点传输半径为250 m，物理层选用Two-ray ground reflection无线传输模型，MAC层采用IEEE802.11协议DCF模式，链路带宽为2M bps。仿真通信采用512byte的定长数据包，随机选择 20 个CBR信源，每个CBR信源发包速率为1 packet/s，仿真时间为400 s。仿真场景2通过改变信源发送数据包的速率来模拟不同的网络负载，节点的停顿时间为50 s，其他参数与仿真场景1一致。

设置节点的电池能量最大值为100 J。仅考虑节点发送和接收数据包的能量消耗，根据Feeney等人对IEEE802.11b接口功耗的研究，节点的发送能量为1.350 W，接收能量为0.900 W。网络生存时间设置为网络中有20%的节点因能量耗尽而消亡的时间。

各参数取值如下：m=1，n=2，ρ=0.5，r=0.3，Ψ0=0.8，ΔL=10，α=3，βe=0.4，βc=0.6，ω=1，σ=1。

(a)　端到端时延对比

(b)数据包成功传送率对比

(c)网络生存时间对比图1　场景1中三种路由协议的性能比较

图1是在场景1中AODV、AntRouting、GSORM三种路由协议的数据包成功传送率、端到端时延以及网络生存时间的比较。节点停顿时间由0 s逐渐增加到400 s。当节点的停顿时间为0 s时，节点移动性最强。当节点的停顿时间为400 s时，可以认为节点处于静止状态。随着节点停顿时间的增加，节点移动性降低，网络拓扑变化减缓，路由错误、路由重建和分组重传的次数减少，因而三种协议的数据包成功传送率随节点移动性的降低而上升，端到端时延随着节点移动性的降低而减少，网络生存时间随节点移动性的降低而增加。从图1中可以看到，当节点移动性发生变化时，GSORM协议具有比AntRouting协议及AODV协议更好的性能指标。GSORM协议和AntRouting协议的节点路由表维护多条路径信息，因此当某条路径失效时，可以选择其他的替代路径，因此避免了频繁的路由发现过程，两者的网络性能均高于AODV协议。但是GSORM协议考虑到节点的移动速度、拥塞程度、能量对于荧光素变化的影响，使得搜索萤火虫Fs总是向移动速度较慢、拥塞程度较低、能量较高及距离较近的最优节点移动，因此，GSORM协议受到网络拓扑变化的影响最小，能够更好的适应动态网络，体现出比AntRouting协议更好的性能。

(a)端到端时延对比

(b)数据包成功传送率对比

(c)网络生存时间对比图2　场景2中三种路由协议性能比较

图2是在场景2中AODV、AntRouting、GSORM三种路由协议的数据包成功传送率、端到端时间以及网络生存时间的比较。CBR信源发包速率从1 packets/s增加到5 packets/s。随着发包速率的增加，网络负载随之增大，因而三种协议的数据包成功传送率随发包速率的增加而下降，端到端时延随发包速率的增加而增加，网络生存时间随发包速率的增加而减少。从图2中可以看到，在网络负载增大的情况下，GSORM协议获得了比AntRouting协议及AODV协议更好的性能。GSORM协议及AntRouting协议由于都采取了主动路由维护机制，即在路由发现阶段，目的节点会向源节点发送信息以对路由信息进行确认及维护，因此可以保证节点所存储的路由表能够更及时的得到更新，因而两者的网络性能在网络负载增大的情况下均优于AODV协议。而GSORM协议在路由发现及维护阶段，总是寻求移动速度慢、拥塞程度低、能量较高、距离较近的路由，因此GSORM协议性能稳定，更能够适应负载较大的网络，体现出比AntRouting协议更好的灵活性。

4　结束语

本文提出了无线自组网中一种基于萤火虫GSO优化的路由协议GSORM，协议将节点的移动速度、节点的拥塞程度、节点的剩余能量以及节点之间的距离结合起来与路由选择规则相关联，通过驻留萤火虫、搜索萤火虫及回溯萤火虫进行按需路由的优化选择，无须额外传送大量的控制分组。每个节点维护多条双向冗余路径，提高了协议的自适应性及可靠性。仿真实验结果表明，在不同移动性及负载的无线自组网中，从数据包成功传送率、端到端时间以及网络生存时间三个指标来看，GSORM的性能均要优于AODV协议及AntRouting协议。下一步需要对ρ、r、α、βe、βc、ω及σ等参数的取值进行仿真和理论研究，确定参数因子对于GSORM协议性能的影响程度，以体现GSORM协议在不同环境中的特性。

[1]Nikam, Samiksha. Delay Analysis of DSDV Protocol using NS2.34[J]. International Journal of Computer Applications, 2016, 2(134):13-16.

[2]MB Yassein, AY AI-Dubai. Novel Broadcast Schemes in DSR for Mobile Ad Hoc Networks[J]. International Journal of Advanced Computer Science and Application, 2016, 4(7):1-7．

[3]A Aggarwal,S Gandhi,N Chaubey.Performance Analysis of AODV,DSDV and DSR in MANETs[J]. International Journal of Distributed&Parallel Systems, 2014, 2(6):153-162．

[4]蔺绍良,龙海南.Ad Hoc网络路由协议综述[J].电子设计工程,2013,21(9):141-144．

[5]Yang X,Hosseini S,Gandomi A. Firefly Algorithm for Solving Non-convex Economic Dispatch Problems with Value Loading Effect[J].Applied Soft Computing,2012,12(3):1180-1186．

[6]刘长平,叶春明.一种新颖的仿生群智能优化算法：萤火虫算法[J].计算机应用研究,2011,28(9):3295-3297.

[7]任敬安,涂亚庆,张敏,等.基于蚁群优化的Ad Hoc网络生存时间和其他网络性能平衡路由协议[J].计算机工程与科学,2011,33(10):15-24.

[8]周少琼,徐祎,姜丽,等.蚁群优化算法在Ad Hoc网络路由中的应用[J].计算机应用,2011,31(2):159-165.

[9]Krishnanand K N, Ghose D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]//Swarm Intelligence Symposium,2005. SIS 2005. Proceedings 2005 IEEE.IEEE,2005:84-91.

[10]WH Liao,Y Kao,YS Li. A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks[J].Expert Systems with Applications,2011,38(10):12180-12188．

[11]Krishnanand K N, Ghose D.Glowworm Swarm Optimization for Multimodal Search Spaces[M]. Handbook of Swarm Intelligence.Springer Berlin Heidelberg,2010:451-467.

[12]李咏梅,周永权,韦军.用于函数优化的层次结构萤火虫群算法[J].应用科学学报,2012,30(4):391-396.

[13]王合义,丁建立,唐万生.基于蚁群优化的路由算法[J].计算机应用,2008,28(1):11-13.

(责任编辑陈葵晞)

桂林市科学研究与技术开发计划资助项目《机器人焊接的物联网监测系统研究与实践》(2013-0102-6)；广西高校科研项目《基于跨层协作的无线自组网能量控制研究》(201204LX522)；桂林航天工业学院科研基金资助项目《VANET中基于位置的安全路由协议研究》(Y12Z030)。

TN929.5

A

2095-4859(2016)02-0149-06

**作者简介：覃科，女，湖北松滋人。硕士，讲师。研究方向：无线自组网技术，网络优化及仿真技术。