基于蜂群算法的无线传感器网络任播路由协议

基于蜂群算法的无线传感器网络任播路由协议

无线传感器网络的节点（无线传感器网络）的工作依赖有限的电源（电池），因此传统的路径协议大多数不适合无线传感器网络。蜂群算法是一种模仿蜜蜂繁殖和采蜜等行为的新兴的群体智能优化技术,近年来受到众多学者的关注。蜂群算法目前主要应用于函数优化、电力系统分析、神经网络训练、图像处理等领域。由于其具有群体智能的特点,近年来也有学者将蜂群算法应用在路由技术中,如Rashedi将蜂群算法应用在光网络的路由和波长分配技术中以减少阻塞概率;Szeto将蜂群算法应用在限量运输路由问题中;Zheng针对多播路由技术中的Steiner树问题,采用蜂群算法进行优化,相比较传统遗传算法和蚁群算法,收敛速度更快,优化结果更佳;Singh通过蜂群算法寻找无向带权图中最小遍历开销。目前,蜂群算法在WSN路由中的应用还较少,如Karaboga将蜂群算法的智能觅食策略应用在WSN路由中的成簇技术中;Fahmy采用2种类型的蜜蜂Agent去寻找源节点至目标节点的可用路径,通过预测机制选择能耗最小的路径作为目标路径。Santhiya提出一种混合蜂群算法和蚁群算法的路由协议(EARRP),该协议以MAC开销、剩余能量和链路失效率作为适应度函数,混合蜂群算法和蚁群算法进行优化从而获得最优路径,EERRP思路较新颖,但实际优化过程中以蚁群算法为主体,蜂群算法的优化作用体现并不明显。受启发于人工蜂群算法ABC(ArtificialBeeColony)中的采蜜机理,本文提出一种基于蜂群算法的WSN任播路由协议,该协议具有控制开销低和能耗效率高等性能优势。1蜂群算法及数据说明在WSN中节省节点能耗是一个重要研究课题,有大量研究成果已成功应用于提高WSN生存期,如在大规模WSN中增加基站数目并引入任播技术能够均衡能耗,提高WSN生存期。任播是IPv6提供的一种新型网络服务,指一个发送者和通信组中的任意一个之间的通信。本文标记:A为某任播地址;G(A)为共享A的任播组员集合(即基站集合),共有M个组员;Ai为G(A)中第i个组员;U为传感器节点集合,共有N个节点。由于任播技术具有均衡数据流和能耗的特点,可以较好地应用在WSN路由中。为减少能耗,本文协议还采用睡眠唤醒机制,每个节点都有自己的唤醒率(单位时间内唤醒状态时间所占比例),本文设置节点的唤醒率与其剩余能量率有关,当节点能量率低于相应阈值时,相应降低其唤醒率。蜂群采食首先由侦查蜂(Scouter)搜索食物,探测信息通过蜜蜂的一种特殊舞蹈(摇摆舞)在蜂群中共享;随后组织采集蜂(Forager)采蜜,其数目取决于食物数量。根据上述原理,学者常以此为启发,以食物源代表各种可能的解,以采蜜过程代表搜索函数最优解的过程。本文将蜂群算法应用在WSN任播路由中,为适应WSN的特性,将蜂群算法做一些改进。首先,各个传感器节点被视为一个个蜂箱,各节点需要向任一基站(任播组员)汇报监测数据分组,各基站被视为食物源;蜂箱至某食物源的路径跳数和中间节点剩余能量情况被视为该食物源的食物充裕程度。蜂群算法中设置3种蜜蜂:蜂后(Queen),侦查蜂和采集蜂。每个蜂箱由蜂后产生侦查蜂和采集蜂分别用来查询路由和传递分组。在WSN中,若节点u∈U监测到移动事件发生需汇报至任一基站,节点u周围区域的节点也有很大几率在此时或随后监测到该目标移动事件并也需汇报至基站。为节省路由查询能耗,节点u寻找基站路由的同时也通知其周围区域节点无需寻找基站路由,当路由寻找完毕后将查询信息通知相应节点。基于以上设计策略,本文将探索蜂分为2种:长途探索蜂LDS(Long-DistanceScouter)和短途探索蜂SDS(Short-DistanceScouter)。LDS和SDS都用来查询路由,但最大跳数设置不同。SDS最大跳数值设置为H,因此SDS所探知的是一个半径为H的区域FZ(ForagingZone);LDS最大跳数值设置为与网络直径相关,即允许其探索整个网络区域。LDS在路由查找过程中需携带其编号,源节点地址,目标地址,本次路由查找编号(PID),路径堆栈,上一跳节点,TTL(TimetoLive),路径跳数D,路径中节点最小能量值E(MinimumEnergy),数据字典和度量值R等信息,其结构如图1所示。每个节点需维护两个本地路由信息表:SDS表和LDS表。SDS表需保存其FZ区域内所有节点的路由信息,其表项有目标单播地址、下一跳地址和跳数等。LDS表需保存至所有基站节点的路由信息,其表项有目标单播地址,目标任播地址,下一跳地址,路径跳数D,E值,度量值R和路径信息栈等。其结构如图2所示。显然,LDS表结构大于SDS表,但由于LDS表只保存至各基站节点的路由信息,而基站数目相对较少,因此所带来的路由维护开销也相对较小。2处理协议的步骤模仿蜜蜂的采蜜过程,协议操作被分成以下6个步骤。(1)相邻邻近节点分析每一个节点需周期性发送刷新报文去探知相邻(一跳)邻居节点情况;当一个节点从睡眠切换至唤醒阶段需及时向相邻邻居节点汇报;当节点收到相邻邻居节点的响应信息后,需保存其路由信息及剩余能量率至本地Cache中,保存或刷新SDS表和LDS表中以该相邻邻居节点为第一跳的相关路径信息;当指定时间Δt内不能收到相邻邻居节点的响应报文,则判定该节点丢失,从Cache、SDS表和LDS表中移除包含该节点的所有路径信息,由于本文采用睡眠唤醒机制,指定时间Δt需大于系统规定最大睡眠时长。(2)访问和维护sds表沿线信息每一个节点还需周期性派遣SDS查询和维护自身FZ区域的路由信息,操作过程与相邻邻居节点路由信息维护相似,在此不赘述。(3)节点s查询或更新基当源节点(蜂巢)侦查到的基站数目不能满足客户需求或者已有基站路径中间节点剩余能量较低(食物不充沛)导致在巢采集蜂数量无法满足监测数据分组流量要求,源节点需(重新)派遣LDS查询或更新基站路由信息。为节省查询能耗,节点u∈U寻找到基站后需将寻找到的路由信息通知其FZ内其他节点,而这些节点无需寻找路由。如图3是一个WSN监测网络,H设置为3,图3中目标移动事件只需由节点n1和n2作为代表节点去查找基站,而无需监测到该移动事件的所有节点(图3中白色节点)去参与路由查询,节省大量路由查询能耗。代表节点基本操作步骤如下:当节点监测到移动事件后,由其充当代表节点并通知其FZ区域内所有节点;已被代表的节点在随后监测到该移动事件不再去查询基站路由信息,等待代表节点转发其寻找到的路由信息。(4)u3000s-n-大力推进网络负荷的计算源节点通过LDS查询基站路由信息,LDS的数量Ψ取决于最近K个时间周期窗口内该节点最大监测数据分组流量F,Ψ计算如下:其中,Fs为预期平均流量;Ψs为预期平均流量下系统所需LDS数量。由式(1)可知,当监测数据流量较大时,Ψ值也随之增大,寻找基站和最优路径的能力也相应增强;另一方面,当监测数据流量剧增时,网络中也不会大量充斥LDS,加重网络负荷。查询过程采用转发机制,步骤如下:Step1中间节点转发LDS至其一个相邻邻居节点处(通过LDS携带的上一跳节点ID信息可以避免按原路转发)。LDS在选择下一站时,需先检查本地Cache,首选未曾接收过源节点相同且PID相同(即同一批次)LDS的节点(通过Cache可以查知),次选能量较高的节点。中间节点在本地Cache保留该LDS信息以及其所选择的下一站。Step2LDS在寻找路由过程中需保存并携带所经过的跳数D,路径堆栈,路途时间t,中间节点最小剩余能量值E,路径度量值R等信息。设LDS所经过的任播路径P=S-n1-n2-…-nk-Ah,其中S是源节点,Ah是基站h,则路径P的E=min{E(n1),E(n2),…,E(nk)}。路径度量值R用来反映路径食物充沛度,计算如下:R=E/D(2)由式(1)可知,中间节点剩余能量较高且路径跳数较小的路径具有较高的度量值。Step3当LDS到达任一基站后需根据路径堆栈原路返回源节点;LDS返回源节点后汇报其查询到的路由信息;源节点从LDS返回的各条路径中选择至各基站的最优路径并计算各基站的度量值。(5)源节点以自身渠道为驱动源节点通过采集蜂携带监测数据分组至基站,监测数据分组必须由采集蜂携带才能传递。蜂后产生的采集蜂总数设为L,根据基站数目将采集蜂划分为M组,至某基站如Ai的检测数分组必须由相对应组别的采集蜂才能携带传递。基站如Ai所对应组别的采集蜂的数量取决于至该基站路径的度量值,至基站Ai的采集蜂数量L(Ai)计算如下所示:L(Ai)=R(Ai)∑i=1MR(Ai)R(Ai)∑i=1ΜR(Ai)L(3)其中,R(Ai)为源节点至基站Ai的路径度量值。由于监测数据分组由采集蜂携带传输,本文协议要求采集蜂还需原路返回源节点,采集蜂吞吐量需满足监测数据分组流量,因此要求L如下:L=max{2F∑i=1Mt(Ai)L(Ai)/Γ−−−−−−−−−−−−−−−−ue001⎷ue000ue0002F∑i=1Μt(Ai)L(Ai)/Γ,Lm}(4)其中,t(Ai)为至基站Ai的路径时间,Lm为系统指定的最小值,Γ为一只采集蜂一次最大携带数据量。结合式(3)和式(4),解得采集蜂数量L如下:L=max⎧⎩⎨⎪⎪⎪⎪2F∑i=1Mt(Ai)R(Ai)Γ∑i=1MR(Ai),Lm⎫⎭⎬⎪⎪⎪⎪(5)L=max{2F∑i=1Μt(Ai)R(Ai)Γ∑i=1ΜR(Ai),Lm}(5)根据目前尚未派遣出去的各组采集蜂数量,源节点按比例随机选择采集蜂并传递至相应基站,该设计可以使得拥有高度量值的基站拥有较高优先权。由于节点睡眠时长取决于节点剩余能量率,若高度量值的路径由于中间节点能耗较快导致睡眠时间增长,尽管至该基站的采集蜂配比数量较多,但多数还停留在路途中,源节点采用该路径的概率降低。因此,本文提出的采集蜂返回机制不仅可以让源节点确认数据分组送达基站,而且相比较以往大多数多路径路由协议(如文献[11-12])需要额外维护一张路由权重表并需时时更新,本文设计可以减少路由表的维护开销。(6)寻找基因组织式(5)中L的设置与最大流量和路径平均时延有关,通常情况下采集蜂吞吐量可以匹配监测数据流量,但由于各基站路径节点能耗较多睡眠时间增长,采集蜂往返时间增加,从而出现无法满足监测数据流量的情况。对此需要重新安排LDS去查找基站路由信息,在寻找过程中或者寻找到新的基站(食物源),或者寻找到至某基站的替代路径(至该基站的原先最优路径由于能耗损失被新的最优路径替代),或者刷新至该基站的时延。由此,采集蜂数量和分配比例将被重新安排,从而改善采集蜂吞吐量问题。3abcarp能耗本节讨论ABCARP的基站路由查询能耗(控制开销)。为方便讨论,假设移动事件经过所有传感器节点的周边,即所有节点都需要汇报该监测事件的数据分组至基站。如前文所述,ABCARP只需要代表节点负责寻找基站路由信息,设网络面积为S,节点密度为ρ,节点数为N,可得S=N/ρ。设节点传输半径为r,则代表节点的数目Θ≈S/(πr2ρH)。如前文所述,每个代表节点的LDS数量Ψ取决于该节点最大监测数据分组流量F,假设LDS寻找到基站所需平均时间为T,则代表节点派遣LDS的平均频率rL=Ψ/(2T)。本文设置TTL(TimeToLive)值为网络直径D,可得D=S√=N/ρ−−−−√D=S=Ν/ρ。假设每个LDS所经过的跳数为最大值TTL,因此,ABCARP单位时间基站路由信息查询能耗EA计算如下(只计算LDS的传递能耗,忽略接收能耗和监听能耗):其中,La为LDS数据大小;{ET×La}为节点传输La比特数据分组至下一站所导致的节点能耗。而传统AODV采用全泛洪机制寻找基站路由,而且监测到移动事件的所有节点都要参与查询基站路由。在全泛洪机制下,中间节点需将从邻居节点接收的RREQ转发给其他邻居节点。记节点平均周围邻居节点数目为w,w=ρπr2-1。一个中间节点共需转发(w-1)w个RREQ。因此AODV中各节点因RREQ的传递总能耗(忽略接收能耗和监听能耗)EV计算如下:其中,Lq是RREQ数据报大小,{ET×La}为节点传输La比特数据分组至下一站所导致的节点能耗,rs为节点寻找基站路由信息的频率,由于AODV为按需驱动路由,节点没有路由表,rs通常即为监测事件发生频率。显然LDS数据报大小(La)要大于RREQ数据报大小(Lq),而且当监测事件发生频率极低时,即rs极小,AODV的控制开销也极少。而ABCARP由于需要经常性地维护路由表,控制开销较大。但由上文可知,ABCARP的控制开销能耗数量级为O(N3/2),低于AODV的O(N2)。因此,当监测事件发生频率较高时,随着网络规模(N)的增大,ABCARP的能耗优势将渐渐体现。而且,AODV要求所有节点都需要查询基站信息,而ABCARP只需要代表节点去查询,从而进一步提高ABCARP的能耗优势。4基于传感器网络带及sds-pct的事件网络设置以下我们以WSN中常用的AODV以及群体智能路由协议的代表Ant-AODV作为对照协议,来评价ABCARP的优劣。仿真模拟一个具有N个(80～180)节点的网络,节点随机分布在180m×180m矩形区域里。网络设置如下:节点传输半径r为30m;指定任播组员(基站)节点,数目设置为4,基站具有无限能量;传感器节点初始能量为50J,剩余能量率为100%(即唤醒率为100%);设置H=2;传输速度为160kbit/s;以矩形左下角为坐标系原点;以参数λ=0.5的泊松分布产生移动事件,该事件监测数据分组大小为1kbit,事件移动速度为30m/s,移动轨迹为直线y=ax+90,其中a为常数,在间随机取值,x∈。不改变区域面积,不断调节节点数目(80～180,即节点密度ρ=0.0025～0.0056),运行20s,检查各协议性能参数。4.1基于防止主体网络地理风险的算法实验观察发送1kbit监测数据分组所需平均路由查询和维护控制开销,结果如图4所示。由图4可知,随着节点数增加,AODV控制开销增加明显;Ant-AODV是针对传统蚁群路由算法时延较长等缺点,在AODV协议泛洪之前加入蚁群算法进行优化处理,从而能够有效降低时延,但由于仍然需要广播泛洪,控制开销并不少于AODV,其次前向蚂蚁在移动过程中需要携带并创建源节点路由信息表,蚂蚁个体体积增大从而增加控制开销,而且,随着节点数增加(密度增加),移动事件所波及的监测节点数增加,网络动态变化较大,蚁群算法不适应于动态性网络的缺点体现更加明显;ABCARP没有采用泛洪查询机制,采用两级探索蜂机制,控制开销较少,而且通过代表节点查询基站,该机制在移动目标监测事件中能够节省大量控制开销。4.2节点密度对ant-aodv定位能耗的影响实验观察发送1kbit监测数据分组所需平均能耗(传递、接收和监听能耗),结果如图5所示。由图5可知,随着节点数增加(节点密度增加),各协议监测数据分组发送能耗都相应增加,原因主要是监听能耗和重传能耗的增加。Ant-AODV控制