基于蚁群_遗传的无线传感器网络路由算法

文章编号:1674-2974(2009)07-0046-06

湖南大学学报(自然科学版)

JournalofHunanUniversity(NaturalSciences)Vol.36,No.7Jul12009

基于蚁群-遗传的无线传感器网络路由算法陈延军­,潘 泉,耶刚强,梁 彦

(西北工业大学自动化学院,陕西西安 710072)

X

摘 要:提出了一种基于蚁群-遗传的无线传感器网络路由算法.通过有限寿命的蚂蚁在源节点与目的节点之间的运动获取多个备选路径,然后把每一个备选路径视为一个基因序列,通过选择、交叉和变异操作获得路径的优化,并适时进行路由维护.仿真结果表明,本算法减少了能耗,延长了网络生存时间,提高了网络的可靠性和自适应性.

关键词:无线传感器网络;路由;蚁群算法;蚁群-遗传算法

中图分类号:TP393 文献标识码:A

AntColony-geneticRoutingAlgorithmforWirelessSensorNetworks

CHENYan-jun,PANQuan,YEGang-qiang,LIANGYan

(CollegeofAutomation,NorthwesternPolytechnicalUniv,XianShanxi 710072,China)

­

Abstract:AnantColony-GeneticRoutingAlgorithm(ACGRA)wasproposedforroutingoptimizationde-sign,inwhichthecommunicationmessagessentbynodesforsearchingtheoptimalrouteweretreatedasantswithlimitedlife-span.Throughtheants.movementbackandforthamongsourcenodesandsinknodes,mu-ltiplecandidateroutingpathscouldbeobtained.Eachcandidatepathwasthenconsideredasagenesequence,andthroughtheselection,crossoverandmutationoperationsonthem,theoptimalroutingpathwasdeterminedatsinknode.Simulationresultshaveshownthatenergycostissavedbyover21%,thelife-spanisincreasedbyaround16%andthereliabilityandadaptationofthenetworkarealsoimproved.

Keywords:wirelesssensornetworks;routing;antcolonyalgorithm;antcolony-geneticalgorithm

无线传感器网络[1]是由大量具有信息感知,数据处理和无线通讯能力的传感器构成的无线自组织网络.降低能耗是无线传感器网络的核心问题,由于数据传输消耗能量较多,因此高效的路由算法对于节省能耗至关重要.文[2]提出了一种以数据为中心的路由协议(DirectedDiffusion,DD),这是一个基于数据的、查询驱动的路由协议,该协议采用多路径数据传输和数据聚和的方法,提高了数据传输的可靠性,减少了通信量.LEACH为一种基于聚类的路由协议,它把整个网络分成多个簇,通过簇首收集和传输信息,并不断地进行簇首选择来降低能耗.文[4]提出了一个提供软实时端到端速率保证、网络

[3]

拥塞控制及负载均衡的QoS路由协议,该协议要求每个节点维护其邻居信息,以便寻找最优路径,从而

确保每个报文分组能以指定速度转发给汇聚节点.

鉴于群体智能算法强大的优化能力,一些学者提出了基于智能的路由算法,它通过个体之间的协作,以分布式计算来完成全局优化,所以适于大规模传感器网络.文[5]提出了一种针对斯坦纳树的蚁群算法,该算法可被移植到WSN路由中.然而,并没有针对WSN的特定需求做出相应改变,而且没有考虑对于WSN性能至关重要的能耗问题;Zhang等人在文[6]中研究了3种不同的基于蚂蚁的WSN算法,但是,作者仅仅关注信息素初始分布的建立,

X收稿日期:2008-12-02

基金项目:国家自然科学基金资助项目(60634030)

作者简介:陈延军(1977-),男,河南焦作人,西北工业大学博士研究生­通讯联系人,E-mail:chenyanjun@mail.nwpu.edu.cn第7期陈延军等:基于蚁群-遗传的无线传感器网络路由算法

47

在系统启动效率方面具有一定的优势.Kassabalidis提出了AntNet[7]算法,通过前向蚂蚁和返回蚂蚁来实现路由优化.前向蚂蚁收集节点信息,返回蚂蚁利用这些信息更新路由表.AntNet算法对网络的变化有较强的适应能力,能快速建立优化路径.但它们都利用了网络延时信息建立更新路由表,而没有考虑节点当前状态,这样会使部分节点能量迅速耗尽,引起网络瘫痪.而且为了优化路径需要较多的蚂蚁协同工作,这将导致大量的广播通信而消耗过多的能量.

本文提出了一种蚁群-遗传路由算法(ACGRA,AntColony-GeneticBasedWirelessSensorNetworksRoutingAlgorithm),重点研究了在降低能耗的情况下,延长网络寿命,提高网络的可靠性和容错能力,并有效地进行路由维护.

协作来完成.算法步骤如下:

图1 ACGRA算法流程图

Fig.1 TheflowchartofACGRAalgorithm

1 蚁群-遗传路由算法介绍

先利用蚂蚁分布式特点,以少量的蚂蚁产生多条路径并收集网络信息,然后利用遗传算法(GA,GeneticAlgorithm)的快速收敛性能,将每一条成功的路径视为GA的一个个体,在汇聚节点进行进一步的优化,确定最终路由表,并根据节点信息不断进行路由维护.

本文在AntNet算法基础上对蚂蚁特性做出了新的定义,赋予蚂蚁寿命,当蚂蚁走过较长时间时就会死亡,这样蚂蚁就避免在能耗很大的路径上继续寻优而耗费能量.

本文中蚂蚁的主要特性定义如下:

¹蚂蚁分为前向蚂蚁和返回蚂蚁,前向蚂蚁收集节点信息,进行局部更新并把信息带给返回蚂蚁,返回蚂蚁对最优路径进行全局更新;

º前向蚂蚁具有寿命,前向蚂蚁随着时间的增加年龄也不断增加,当L=Lmax(Lmax为蚂蚁最大寿命),蚂蚁就宣布死亡;

»蚂蚁具有记忆能力,可以记住节点的信息.111 算法实现

ACGRA算法设计了合理有效的适应度函数,力求在节省能量的前提下尽量提高路由效率,AC-GRA算法实现参见图1.

首先在步1~步6利用蚂蚁分布式特点快速收集信息,建立遗传算法使用的初始种群,然后在步骤7~12进行遗传算法,完成最终路径的建立.

1)蚁群算法:

蚁群算法是完全分布式算法,通过所有节点的[8]

步1初始化.将m只蚂蚁放置于源节点上.步2计算转移概率.

定义位于第i个节点上的蚂蚁k到节点j的转移概率Pij(i)为:

Sij

Pkij(i)=

j=1

k

k

E

n

kSij

,jINb{i};

(1)

0,否则.

其中:Nb{i}为节点有效通讯半径内的节点集合;n

k

为Nb{i}中元素个数;Sij为节点i到节点j的信息

素,此公式规定蚂蚁以较大的概率选择信息素较多的路径;

步3节点的选择和局部更新.

局部更新公式见式(2):

Sij(t)=max{Smin,min{Smax(1-a)Sij(t-1)+ $Sij(t)}}.

(2)

其中:Smax和Sman分别为极大和极小信息素的值;a为信息素挥发率常数,0$Sij=

(3)

0,其他.

$Sij的设计直接关系到路由的能效比,但在本算法中考虑到优化主要由GA来完成,为了减少计算量和ACO的复杂度,我们只考虑接收的信号强度Rij,以排除一些失效节点;K1为常量,通常K1=1;h1为权值系数,通常h1=1.

根据转移概率选择下一个节点,用式(2)进行局部信息素更新;令前向蚂蚁能够记忆节点和邻居

K1Rij1,蚂蚁走过的路径;

h

48

湖南大学学报(自然科学版)2009年

节点的能量和状态信息.

步4前向蚂蚁随着时间增长年龄不断增加,每经过一个节点,蚂蚁年龄L(i)=L(i)+1,iI[0,m];若前向蚂蚁没有到达sink节点且L步5全局更新规则.

全局更新公式如式(4)所示:S)Sij(t)+ij(t)=max{Smin,min{Smax,(1-Q $Sij}}.确定:

(5)

0,其他.

其中:GI(0,1)为信息素的衰减率;K2为常量,通常K2=1;h2为权值系数,通常h2=1;当蚂蚁年龄L越大时,G越小.所以蚂蚁到达汇聚节点越晚,年龄越大,返回时释放信息素就越少.

2)遗传算法:

遗传算法是在汇聚节点进行最终优化的集中式算法,它根据蚁群算法建立的初始种群和收集到的节点信息形成最终的路由网络.算法步骤如下:

步6初始化群体.

每一个在规定周期内成功到达汇聚节点的蚂蚁,表示一条备选路径,规定为种群P(t)的一个个体,个体的编码采用节点的ID号作为基因代码.当满足规定的种群大小时蚁群算法结束,否则转到第2步.

步7计算个体适应度.

通过群体的初始化,用式(6)计算每个个体的适应度F,将F按照从大到小的循序排列,记下前N个个体(Nn-1

x

在该算法中对个体进行单点交叉运算,交叉点将会在有相同基因的两个个体之间进行选择.若两个个体之间有两对相同的基因,则任意选择一对,否则取消交叉运算.

图2表明,两个个体A1,A2进行交叉运算,得到B1和B2,由于B1内有相同基因,则对B2进行进化算法去掉两个基因间的相同基因,得到个体C.S为源节点;D为汇聚节点;G为个体中的基因.

(4)

其中:Q为信息素挥发率,0GL

K2(Rh,蚂蚁走过的路径;ij2)

$Sij=

图2 交叉运算框架图

Fig.2 Theframechartofcrossoveroperator

步10变异运算.

对个体i进行变异运算.变异基因在集合8中选取,8=Nb{i}{i-1}HNb{i}{i+1},i-1和i+1分别表示节点i的左右邻居,Nb{i}表示能和节点有效通讯的节点集合.若8Iª,则不进行变异运算,否则对该个体进行进化算法以去除相同基因内的基因,以避免陷入死循环.

假设个体A中基因G5变异后为G3,则进行进化算法去掉其之间相同的基因,得到个体B.

步11小生境淘汰运算.

将M个个体和N个个体合并在一起得到一个含有M+N个个体的新群体,这在第6步和第10步中得到,然后对其中适应度较低的个体乘以惩罚因

F(x)=

i=1

EEi+1Ri,i+1/nx.

A

B

K

(6)

子,见式(8):

F(x)=L#Fmin(x).(8)其中:LI(0,1)为惩罚因子,Fmin(x)为个体内适应度较低的个体.

步12判定算法是否结束.定义适应度的变化率N为:N=

i=n-j

Ej+1为节点i+1的剩余能量,i+1为节点选择的下一个节点;Ri,i+1为节点i+1接收到节点的信号强度;x为从源节点到汇聚节点路径;nx为x的跳数;A,B,K为权值常数;此函数的设计主要是为了平衡路由效率和能耗,得到较高的能效比.

步8选择运算.

对群体P(t)进行比例选择运算,并应用式(7)进行选择概率计算.因此一些适应度较大的个体能够以较大的概率保存到下一代.

pi=F/

i=1

.(9)

j

其中:D为适应度的变化率的一个阈值;j为从n到n-j之间的迭代次数;n为当前迭代次数,当N>D时跳转到第7步,否则结束.112 路由维护

网络由于节点失效,损坏或增加新的节点而破E

n

Fi(x)-

i=n-j

EFi(x)/j

n

EFi,i=

M

1,2,3,,,M.(7)

步9交叉运算.第7期陈延军等:基于蚁群-遗传的无线传感器网络路由算法

49

坏网络的拓扑结构,不及时维护,就会造成网络的瘫痪,而遗传算法根据适应度的大小,不但建立了主路径,而且建立了多条备选路径.因此一旦由于一些节点失效无法正常工作,则可利用备选路径来完成任务.当新节点的加入时,通过发出广播,周围收到广播的节点会返回一个信号,并更新路由表.

为了不频繁的重建路由表,节省能量,ACGRA会根据每个节点的剩余能量自动更新路由表,这样就使节点的能耗尽可能地保持平衡.经过一定周期后,节点就会向周围节点广播自己的剩余能量,收到广播的节点并和其有链路关系的节点用公式(10)更新路由表:

Pi

,(10)

1+$Qi

P为选择i节点的概率;$Qi为i节点的概率减少值.

Pi=

$Ei

.(11)E

其中:E为节点总能量;$Ei为节点i的能量变化量;

$Qi=CC为调整参数.

消耗能量,统计整个路由建立时所有节点能量消耗

的总和.见式(15):

E󰀂c=

Eei.

i

N

(15)

其中:ei为节点i接收和发送数据消耗的总能量.

4)网络的生存期.定义所有节点不断轮流作为源节点向汇聚节点发送数据,直到网络可靠性U小于给定阈值时,网络的运行时间.

5)自适应性.网络对低能量节点,失效节点和新增节点的处理能力;定义能正常工作但能量较低的节点为低能节点,不能够正常工作的节点为失效节点.

3 仿真结果

为了验证ACGRA算法的有效性,本文对提出的5个性能指标做出了仿真分析比较,并对仿真中应用的一些关键参数进行了仿真分析.311 仿真环境

仿真场景如图3,感知区域为(50,50)到(200,200)的矩形区域,随机分布200个节点,节点最大通讯距离为30.节点能量设为1@10个单位,发送和接收一个数据包各消耗5个单位.仿真中定义一个具有高能量,快速数据处理能力的节点为汇聚节点,用/#0表示;源节点是在200个节点中随机产生,用/*0表示;低能节点是以15%的概率随机生成,用/+0表示.

5

2 性能评价指标

无线传感器网络路由协议有较多的评价指标,主要的性能评价指标有路由的可靠性,延时,建立路径的能耗,网络的生存期和路由的自适应性.

1)可靠度.可靠度是考察在当节点失效率为J的情况下,使数据能够可靠传输到汇聚节点的指标;定义可靠度U为:

U=

Ds

i=1

EDi

N.(12)

定义节点失效率J为:

N1

J=.(13)

N

其中:Di为节点i发出去的数据;Ds为汇聚节点收到的数据总量;N为总的节点数;Nc为时效节点总数;

2)延时T󰀂d.延时是从源节点到汇聚节点的平均经过时间,统计延时时间时,选择多个源节点向汇聚节点发送数据,计算所有数据到达汇聚节点时的平均时间.由下式表示:

n

s

x

图3 网络仿真场景

Fig.3 Thescenariosofnetworksimulation

T󰀂d=

Etd/ns.

i

i

仿真中,随机产生一个汇聚节点后,分别用AC-(14)

GRA和AntNet算法建立所有节点的路由表.然后对各个性能指标做出仿真比较,主要有以下几个

方面:

¹为了验证网络的能耗和延时,仿真根据节点收发数据包个数统计消耗的总能量,然后选择一定

其中:ns为原节点个数;tid为汇聚节点收到由源节点i发送数据的时间;

3)路径建立能耗E󰀂c.建立整个网络路由的总能耗.在路径建立阶段,由于蚂蚁的运动,需要不断地50

湖南大学学报(自然科学版)2009年

距离的源节点依据路由表向汇聚节点发送数据,统计数据成功发送到汇聚节点的平均时间.

º验证网络的自适应性.随机令一部分节点为低能节点,观察路径建立是否自适应节点能量的变化,此指标用以评价网络对节点失效,低能等的自适应性.

»可靠性和网络的寿命的验证.随机让一部分节点失效,然后让所有有效工作的源节点向汇聚节点发送数据,这时就会有节点由于能量消耗过多而失效,统计网络的可靠性.当可靠度小于给定阈值时,就为网络的运行时间,此指标体现网络的抗毁性.

以下为针对各仿真目标的仿真结果及分析.312 仿真参数的选取

蚂蚁越多,广播风暴越大、能量消耗就越大,所以蚂蚁个数m要尽可能的小,仿真中m分别取10,15,20和30时,结果显示当m=20时能够快速建立多条路径,并且能耗较低;对Smax的设计主要是为了增强蚂蚁的探索能力,避免陷入局部最优.对Smin的设计主要是为了增大搜索范围,仿真中Smax=240,Smin=5;参数L,Pc,Pm和G的选取见表1.A和Q都取0.2;权值因子A,B,K的取值和网络特性有很大的关系.

表1 GA算法仿真参数选取

惩罚因子L交叉概率Pc种群大小Num变异概率Pm

信息素衰减率G

网络节点总数

图4 AntNet与ACGRA路由建立所需的能量比较

Fig.4 Thecompareofconsumedenergy

betweenAntNetandACGRA

2)延时比较.

图5为选择源节点到汇聚节点距离分别为50,90和120时,经过20次仿真的平均时延.可以看到距离较短时,ACGRA算法和AntNet的延时基本差不多,而随着路径的增长,ACGRA就明显优于AntNet.这就表明路径越长ACGRA建立起的路径就越优.

0.050.6600.060.98

若节点能量高则可以使A取较小的值,若网络有较大的覆盖冗余就可以使取较小的值.仿真中,取A=1.5,B=2,K=1.5;T经过10次仿真,结果表明,当取值为6时可满足种群数.313 仿真结果分析

1)能量消耗比较

每次路径的建立都需要消耗大量的能量,为验证ACGRA算法的低能耗特性,仿真对网络节点数分别为50,100和200时的路由能耗做出统计.统计建立整个路径时,所有节点消耗能量总和.仿真规定所有算法在节点发送和接收一个数据包时都耗能5个单位见图4,这是经过了20次蒙特卡洛仿真的平均能耗.

从图4中可以看出,随着网络规模的增大,AC-GRA算法在能量损耗上越少与AntNet算法.AC-GRA算法能耗低的主要原因是采用了较少的蚂蚁而使广播能耗大量减少.

源节点到BS的距离/m

图5 AntNet与ACGRA之间的路由时延比较

Fig.5 ThecompareoftimedelaybetweenAntNetandACGRA

从图5中可以看出ACGRA优于AntNet,主要原因是ACGRA算法在汇聚节点进行了GA优化算法,得到的优化路径综合性能要优于AntNet算法得到的.

3)自适应性比较.

仿真选择了源节点到汇聚节点距离为100时的场景,场景中有部分能量较低但可以工作的节点,现在比较不同算法下建立的路径.见图6,路经A为ACGRA算法建立的,路径B为AntNet算法建立的.

图6表明路径A,B的长度和跳数是相同的,但是路径B没有考虑低能节点,因为它们经由-+.到第7期陈延军等:基于蚁群-遗传的无线传感器网络路由算法

51

达目的节点.显然在ACGRA算法中,路径选择充分考虑了节点状态,使网络的整体性能得到优化.

节点失效率

x

图8 AntNet与ACGRA可靠性对比Fig.8 Thecompareofreliabilitybetween

AntNetandACGRA

图6 AntNet与ACGRA自适应性比较Fig.6 ThecompareofadaptivenessbetweenAntNetandACGRA

4 结 语

研究了无线传感器网络中的路由问题.提出了ACGRA算法.本文以ACO的分布式特点收集节点信息并产生初始种群,然后用GA算法的快速收敛特点产生路径,建立路由表,并在网络运行中根据节点的状态不断更新路由表.仿真结果表明了本算法的有效性.

4)网络寿命比较.

网络的寿命的验证是让所有的节点轮流向汇聚节点传输数据,直到网络的可靠度<60%时,统计网络运行的周期(定义所有有效节点向汇聚节点发送一次数据为一个周期).不同网络大小下的仿真统计结果见图7.

参考文献

[1] AKYILDIZIF,WEILIANSU,CAYIRCIY.Asurveyonsen-sornetworks[J].CommunicationsMagazine,2002,40(8):102-114.

[2] HEINZELMANW,KULIKJ,BALAKRISHNANH.Adaptive

protocolsforinformationdisseminationinwirelesssensornetworks

[C]//5thACM/IEEEMobicomConferenceSeattlec,WA:1999:174-185.

[3] HEINZELMANW,CHANDRAKASANA,BALAKRISHNAN

H.Energy-efficientcommunicationprotocolforwirelessm-i

crosensornetworks[C]//Proceedingsofthe33rdHawaiiInterna-tionalConferenceonSystemSciences,2000,2:908-918.[4] HET.SPEED:astatelessprotocolforrea-ltimecommunicationinsensornetworks[C]//ProceedingsofInternationalConferenceonDistributedComputingSystemsProvidence,2003:46-55.

[5] SINGHG,DASS,GOSAVISV,etal.Antcolonyalgorithms

forsteinertrees:anapplicationtoroutinginsensornetworks

[C]//RecentDevelopmentsinBiologicallyInspiredComputing,2003:183-206.

[6] YINGZhang,LUKASDK,MARKUSPJ.Fromherzimprove-mentsonantroutingforsensornetworks[C]//WorkshoponAnt

ColonyOptimizationandSwarmIntelligence,Berlin:2004:154-165.

[7] KASSABALIDISI,EI-SharkawiMA,MARKSRJ.Swarmin-telligenceforroutingincommunicationnetworks[J].Global

TelecommunicationsConference,2001,6(6):3613-3617.[8] SARENIB,KRAHENBUHLL,NICOLASA.Nichinggenetic

algorithmforoptimizationinelectromagnetics[J].Transactions

onMagnetics,1998,34(5):2984-2987.

网络大小

图7 网络运行寿命比较

Fig.7 Thecompareofnetworklifetime

betweenAntNetandACGRA

图7中表明ACGRA要优于AntNet算法,这主要是因为:ACGRA算法建立了较优的路径,没有频繁的重建路径,而且充分考虑了低能量节点,尽量平衡网络节点的能耗,降低部分节点快速失效的概率.从图7中看到,随着网络的增大,网络的运行周期在减小.这主要是因为网络越大,数据传输的路径越长,能耗越大所导致的.

为了验证ACGRA算法的可靠性,分别使网络节点的失效率为1%,10%,30%,50%,70%,90%,和100%时,统计数据传输的可靠度(见图8).