廖福保,张文梅
(1.广东农工商职业技术学院 计算机系,广州 510507; 2.广东农工商职业技术学院 机电系,广州 510507)
改进的基于蚁群算法的非均匀分簇路由协议
廖福保1,张文梅2
(1.广东农工商职业技术学院 计算机系,广州 510507; 2.广东农工商职业技术学院 机电系,广州 510507)
针对无线传感器网络中传感器节点随机分布造成能耗不均和“热区”等问题,提出了一种改进的基于蚁群算法的非均匀分簇路由协议;该协议也采用“轮”方式运行,每轮簇首选举开始阶段,根据节点剩余能量、节点密度,结合节点到Sink节点的距离来构造不均匀的竞选半径,每个节点根据竞选半径范围内邻居节点计算剩余能量比及距离偏差平均值,从而计算出其簇首竞争等待时间,采用时间等候簇首竞选机制来选举出簇首,平衡簇内的通信能耗;数据传输阶段,考虑剩余能量、通信能耗、链路质量、传输时延等因素,采用改进的蚁群算法构造最优传输路径,数据传输的同时更新信息素,从而达到自适应、动态优化地建立和维护传输路径;仿真结果表明,该路由协议能有效节约能量和均衡能耗,延长网络生命周期,改善链路质量,减少传输时延。
无线传感器网络;非均匀分簇;蚁群算法;路由协议
无线传感器网络是由部署在监测区域内的大量微型传感器节点以自组织方式组成,通常包含大量的传感器节点和一个Sink节点,这些传感器节点用于采集监控区域内的数据,并以无线通信的方式将数据上传给Sink节点,无线传感器网络已被广泛用于军事、环境、医疗健康等领域[1-3]。
传感器节点通常采用人工布置、飞机布撒等方式大量部署于监控区域,且这些传感器节点大多采用电池供电。由于监控区域的复杂和任意,节点的电池难以补充和更换,因此设计节省能量消耗、延长生命周期的路由算法是目前无线传感器网络的研究热点之一[4]。
目前,学者们提出了多种路由算法和协议,包括平面路由协议和分簇路由协议[5],其中分簇路由协议比平面路由具有更好的可扩展性和能量均衡性,因此更适合无线传感器网络[6]。
在分簇路由协议中,无线传感器网络被划分为多个不同的簇,每个簇由一个簇首和众多的簇内节点组成,簇内节点负责采集监控区域中的数据;簇首节点负责管理簇内节点、接收簇内节点采集的数据并将其融合后转发至Sink节点[7]。分簇路由协议能将整个网络的能量负载平均分配到每个节点,从而降低网络能量的消耗,但在均匀分簇的无线传感器网络中,簇头与Sink节点的通信无论采用单跳或多跳方式,都会存在“热区”问题。
针对分簇路由协议中可能出现的“热区”问题,本文在LEACH协议[8]、EEUC协议[9]等路由协议的基础上提出了改进的基于蚁群算法的非均匀分簇路由协议。
1.1 相关算法
LEACH协议是最有典型的分簇路由协议,采用“轮”的概念周期性选择簇首。每一“轮”每个节点都生成一个0-1之间的随机数,当该随机数大于阈值T(n),则该节点选为簇首。阈值T(n)采用公式(1)计算。
(1)
图1 LEACH分簇拓扑示意
分簇完成后,簇首以单跳的方式将数据传输到Sink节点。
LEACH协议主要考虑的是簇内成员节点的能耗,而没有考虑簇首间的能耗问题。已有研究[9]表明簇首与Sink节点间采用多跳方式通信更有利于节约能量,但由于越靠近Sink节点的簇首需要转发越多的数据,这样越靠近Sink节点的簇首会越早耗尽能量而失效,形成“热区”。
文献[10-11]提出了EEUC、DEBUC算法,将整个网络分为非均匀的簇,靠近Sink节点的簇小,可节省簇内通信消耗,节省能量用于簇间数据转发。
EEUC算法在簇的形成过程,利用公式(2)计算候选簇首的竞选半径,靠近Sink节点的竞选半径小,使得靠近Sink节点的簇的成员数量较少,从而为转发数据节省能量,达到均衡能量的目的。
(2)
簇首竞选完成后,簇首广播竞选获胜消息,普通节点根据接收到的信号强度加入到簇中成为该簇的成员节点。分簇完成后,簇首以多跳的方式将数据传输到Sink节点。
1.2 存在的问题分析
在LEACH、EEUC协议及其众多分簇路由协议中,成员节点都不直接与Sink节点通信,而必须通过簇首与Sink节点通信,没有考虑有些成员节点直接与Sink节点通信的能耗小于通过成员节点与簇首通信的能耗。如图1所示,成员节点A、B离Sink节点近,离簇首节点远,造成成员节点A、B通过簇首与Sink节点通信比A、B与Sink节点直接通信所耗能量更多。
另外,由于节点在监控区域的随机性,会造成某些区域簇首过多或过少,或者某些簇中的成员节点过多或过少,这些都会造成某些簇首过早耗尽能量而死亡。文献[12]提出EBUCA算法利用节点剩余能量和节点密度来进行簇首选举,达到均衡节点能耗的目的,但没有给出邻居节点数量的获取方式。文献[13]根据节点到Sink节点的距离计算簇首竞争时间,但在多跳路由中簇首的下一跳并不一定是Sink节点,并不利于能量均衡。
文献[14]在非均匀分簇的基础上,簇间通信采用蚁群算法进行优化(ACOUC),引入链路可靠性和实时性参数,但并没有考虑通信能耗。文献[15-16]在簇间路由选举中,采用优化的对蚁群算法进行路径搜索,均没有考虑链路质量等问题。文献[9]说明了链路质量好的路由能有效减少节点能耗,提高网络能量利用率。目前无线传感网络的路由协议极少考虑到链路质量的问题,并不能很好地投入到实践应用中。
本文综合以上问题,提出了一种改进的基于蚁群算法的非均匀分簇协议,在成簇阶段,节点根据区域节点密度、节点剩余能量和节点到Sink节点的距离来决定簇半径的大小,在节点密度大的区域及剩余能量小的节点减少竞争半径,达到能量均衡的目的。节点竞选簇首时根据节点剩余能量、邻居节点分布均匀度计算簇首竞争等待时间,采用时间等候机制增大剩余能量高、邻居节点分布均匀的节点成为簇首的机会,减少簇内数据传输的能耗。在簇间数据传输阶段,采用蚁群算法多跳方式建立簇首到Sink节点的最优路径,考虑剩余能量、传输延时、链路质量等因素,能减少簇首能量消耗,延长网络生命周期。
2.1 网络模型
本文算法对无线传感器的网络模型作如下假设:1)节点随机部署于M×M的正方形区域内,Sink节点位于中央且位置固定,能量不受限;2)除Sink节点外的其它所有节点的初始能量相等且有限,节点可感知自身的剩余能量;3)每个节点部署后位置固定,节点间能相互通信,且都具有唯一的ID号;4)节点可以根据需要自由调整发射功率;5)节点能根据接收到的信号强度RSSI来计算发出者到自身的近似距离。
2.2 通信模型
已有研究[17]表明,无线传感器网络中节点间数据传输所耗的能量远大于其它能耗。本文采用与文献[8]一样的无线通信模型,节点发送k比特数据所消耗的能量如下:
(3)
节点接收k比特数据所消耗的能量如下:
ERx(k)=k×Eelec
(4)
本算法类似于LEACH协议,采用“轮”方式运行。每“轮”利用簇首竞争等待时间机制进行簇首选举,簇内数据利用TDMA方式传输,簇首采用改进的蚁群算法多跳方式将数据传输到Sink节点。
3.1 概念描述
为便于描述,对本文所涉及的概念说明如下:
1)竞选半径。节点竞选簇头时的半径,本文根据公式(5)计算竞选半径。
(5)
(6)
(7)
其中:Qi为节点si节点密度、Pi为可工作剩余能量比,Neighbor(i)为节点si的邻居节点个数,N为网络中所有节点个数,einit为节点初始能量,ei为节点当前能量,emin为节点最低工作能量,c、α、β为0~1之间的值且c+α+β=1,用于控制取值范围的参数。
由式(5)可知,当节点密度相同、可工作剩余能量比相同时,簇首到Sink节点的距离越近,竞选半径越小,簇首可节省能量用于簇间转发数据;当簇首到Sink节点的距离相同、可工作剩余能量比相同时,节点密度越大,竞选半径越小,该区域的簇首数目相应增多;当簇首到Sink节点的距离相同、节点密度相同时,剩余能量越大,竞选半径越大,其它簇中成员节点越小,可节省其它簇首的能量,从而达到各簇的能耗均衡。
2)邻居节点。节点sj为si的邻居节点需同时满足式(8)和式(9)两个条件。
d(sj,si) (8) d(sj,si) (9) 式中,d(sj,si)节点sj和节点si之间的距离。从式(9)可以看出,当节点sj与si的距离大于与Sink节点的距离时,节点sj也不是节点si的邻居节点,sj将不属于任何簇,而直接将数据传输至Sink节点。 3)节点度dui。节点si的邻居节点总数目。 4)邻居表。每个节点保存一个邻居节点表以存储邻居节点的相关信息,如表1所示。 表1 节点的邻居表内容 5)剩余能量比PEi。PEi表示节点si的所有邻居节点剩余能量的平均值与节点si的剩余能量的比值,如公式(10)所示,PEi的值越小,则节点si相对于其邻居节点的剩余能量越大。 (10) 6)距离偏差平均值ddi。如公式(11)、(12)所示,dij为节点sj到节点si的距离,dai为si各邻居节点到si的平均距离,ddi表示si各邻居节点到si的距离与dai之间偏差的平均值,平均值越小,代表节点si与邻居节点的距离分布越均匀,就越能均衡簇内的能量消耗。 (11) (12) 7)簇首竞争等待时间ti。从节点收到Sink节点通知簇首竞争到本节点发出簇首竞争消息的等待时间,如公式(13)所示。 (13) 式中:α为[0.9,1]之间的随机数,T为规定的簇首竞争持续时间,β为邻居节点分布均匀度调节因子。从式中可以看出,簇首竞争等待时间tcomp_i由节点剩余能量比、邻居节点分布的均匀度分布决定,剩余能量越高、邻居节点分布越平均,tcomp_i的取值就越小,簇首竞争等待时间越短,节点竞选成为簇首的机会越大。 3.2 簇首选举及簇建立 在无线传感器网络分簇协议中,簇首对整个网络能耗的均衡占用重要的位置;采用簇间多跳路由时,簇首除了要管理本簇的数据收发外,还需要中继转发其他簇的数据,任务较重;靠近Sink节点的由于需要转发的数据量更大,任务更重。多个文献[10-13]均证明了非均匀分簇能有效均衡能耗,能缓解能量空洞。本文在对无线传感器网络进行非均匀分簇的基础上,建立了本文的簇首选举算法,见算法1。每“轮”开始时网络中所有节点都参与簇首竞争,采用时序的方式选择簇首。 算法1:簇首选择算法步骤 2)Sink节点向全网发出Par_CLU分簇信号,各个节点根据接收到的信号强度RSSIi计算其到Sink节点的距离d(si,DS),并根据公式(5)确定其竞选半径Ri。节点清空邻居节点表,为下一步做准备。 3)每个节点在其竞选半径Ri范围内广播竞选消息Sel_CLU,该消息包括节点的ID、当前剩余能量ei。 5)各节点根据邻居节点表中的信息,计算节点度dui,再按照公式(10)计算出剩余能量比PEi,根据公式(11)(12)计算出距离偏差平均值ddi。 6)各节点再根据公式(13)计算出自身的簇头竞争时间tcomp_i。 7)Sink节点发出同步信号Tim_MSG,以同步各节点的时间。 8)节点si收到Tim_MSG信息后,si开始计时ti,同时监听其他节点的信息。 9)对于节点si有: 10)if(ti 11)if收到节点sj的簇首失败消息Fai_CLU 12)ifsj为si的邻居节点 13)更新邻居表 14)endif 15)endif 16)if收到节点sj的簇首成功消息Suc_CLU 17)ifsj为si的邻居节点 18)si广播竞选失败的信息Fai_CLU 19)更新邻居表 20)endif 21)else 22)继续监听并计时 23)endif 24)endif 25)if(ti==tcomp_i) 26)发出本节点的簇首竞选成功的消息Suc_CLU 27)清空邻居表 28)endif 29)选举结束后,簇首竞选失败的节点选择加入到邻居表中与其距离最近的簇首所在的簇中。如果邻居节点中不存在簇首,则加入到最近的邻居节点所在的簇,成为该簇成员节点。 30)分簇结束后,各个簇首向全网广播竞选成功的消息CLU_MSG,其它簇首节点收到该信息,如果没有处理过且距离Sink节点更近,转发CLU_MSG,Sink节点CLU_MSG信息后记录簇首的id。最后Sink节点将记录下所有的簇首id。 下面对算法1进行具体的解释。 第1行,各节点广播Nei_MSG消息,从而计算出节点密度和可工作剩余能量比。第2行,各节点接收Sink节点发出的Par_CLU分簇信号,并根据RSSIi值、节点密度和可工作剩余能量比计算出竞选半径。第3-5行,各节点广播Sel_CLU消息,计算出节点间距离dj、节点度dui,再计算出距离偏差平均值ddi和剩余能量比PEi。第6行,各节点根据距离偏差平均值ddi和剩余能量比PEi计算其竞争等待时间tcomp_i,邻居节点分布越均衡、剩余能量越大,其竞争等待时间越短,竞争获得簇首的机会越大。第10-24行为节点si的竞争等待时间没有到达时的处理情况;第11-15行为在此期间si收到其它邻居节点的Fai_CLU消息,则更新邻居表;第16-23行为在此期间si如果收到其它邻居节点的Suc_CLU消息,si发出失败的信息并更新邻居表,否则si继续计时并监听网络中的信息。第25-28行为节点si没有收到其它邻居节点的竞选成功的Suc_CLU消息,且本节点的竞争等待时间已经到达时,则发出簇首竞选成功的消息Suc_CLU。第29行为簇首竞选失败的节点选择加入到邻居表中与其距离最近的簇首所在的簇中;如果邻居节点中不存在簇首,则加入到最近的邻居节点所在的簇,成为该簇成员节点;离簇首越近,可以节省簇内通信的能量。第30行为各个簇首向全网广播竞选成功的消息CLU_MSG,同时收集其它簇首广播的消息,为后续路由做准备。CLU_MSG信息包括簇首ID、剩余能量、到Sink节点的距离d(si,DS)。 算法中将整个网络划分为大小不等的簇,靠近Sink节点的簇半径小,同时簇首竞争等待时间考虑了剩余能量、节点分布均匀性等因素,能够保证选举的簇首综合性能最优,有利于均衡能耗。 3.3 路径搜索 成簇完成后,从Sink节点释放蚂蚁开始搜索,每个簇首都维护一个簇首节点的路由表(见表2)。 表2 簇首节点路由表 算法2:路径搜索算法步骤 2)whilesjID!=soID 3)ifsj的蚂蚁Ao到达簇首si 4)ifd(si,so) 5)ifd(si,DS) 6)增加si路由表记录 7)更新蚂蚁Ao携带的信息 8)转发Ao 9)endif 10)endif 11)endif 12)endwhile 13)蚂蚁都释放完毕后,各簇首si根据路由表计算其到邻居簇首sj(sj∈Ci,Ci为si路由表中的簇首集)的初始信息素浓度(见公式14)。 (14) 14)再根据公式(15)计算si将sj作为下一跳的概率pij (15) (16) 下面对算法2进行具体的解释。 3.4 数据传输 数据传输分为簇内传输和簇间传输, 簇内传输由簇内成员按时分多路复用(TDMA)方式把数据传送给簇首, 簇首经过数据处理后再通过簇间多跳路由将数据传输到Sink节点。 在簇间传输中, 簇首si依照概率pij最大的簇首sj作为下一跳。在数据传输过程中, 统计发送和接收数据包数量、转发延时等信息。传输成功后, 按公式(17)对对应路由的信息素进行更新。为了节省能耗, 只在链路每成功发送一定数量的数据包后才对信息素进行更新。 τij=(1-ρ)·τij+ρ·Δτij (17) (18) 式(17~18)中,ρ为信息素挥发参数,ω为调节因子,均为0~1之间的值。ni为节点si在t时间内发送的数据包数量,mj为节点sj在t时间内接收到的数据包数量(mj≤ni),mj/ni即为链路质量[19]。tij为从节点si传输数据到节点sj的时延,tmax为单跳最大时延。从公式(17)~(18)中可以看出,当相邻簇首间链路质量越高、时延越短,在该路径上的信息素浓度就越大,被选中作为下一跳的概率越大。 本文采用OPNET仿真软件对本文算法与EEUC、ACOUC算法进行比较实验。 4.1 仿真环境与参数设置 本文无线传感网络的仿真区域为100m×100m,100个节点在该区域中随机部署,Sink节点位于区域中心。实验中,数据传输模型采用一阶无线电能量模型,实验仿真参数如表3所示。 表3 实验仿真参数表 4.2 仿真结果分析 簇首选择完成后,网络节点分布如图2所示。由于本文算法根据邻居节点密度、邻居节点分布均匀度等因素选择簇首,从图中可以看出,在节点密度大的区域簇首多,节点密度小的区域簇首少,簇首根据周围节点的密度分布于无线传感器网络中。 图2 节点分布图 由图3所示,比较3种算法的生命周期,EEUC和ACOUC算法未考虑节点密度、节点分布均匀度、链路质量对网络的影响,生命周期较短。而本文算法簇首选举考虑了节点密度、节点分布均匀度等的影响,在簇间路由中选择链路质量较好、延时短、能耗低的路径进行数据转发,因此从首节点失效到最后一个节点失效的时间都比EEUC和ACOUC算法滞后,能更好的均衡网络能耗,延长网络生命周期。 图4对比了3种算法在每轮网络剩余总能量的变化情况,可以看出本文算法的能量消耗较EEUC、ACOUC算法更为缓慢,生存时间更长。表明本文算法簇间路由采用改进的蚁群算法,考虑簇首剩余能量、传输时延、链路质量等因素更能有效地节约能量。 图4 剩余总能量对比 图5对比了3种算法在每轮网络数据传输时平均时延的变化情况,本文算法采用蚁群算法,收敛速度快,传输路径更为优化,在选择下一跳时考虑了时延的影响,因此本文算法的平均时延较EEUC、ACOUC算法更短,数据传输更为及时。 图5 平均时延对比 实验中以丢包率来衡量通信可靠性,图6对比了3种算法前100轮每轮中的丢包率变化情况。本文算法采用改进的蚁群算法,蚂蚁信息素更新时考虑链路质量而动态调整,簇首数据转发时选择链路质量更高的路径。结果表明,本文算法比EEUC、ACOUC算法的可靠性更高。 图6 丢包率对比 本文借鉴非均匀分簇的思想,根据节点剩余能量、邻居节点分布均匀度计算簇首竞争等待时间,使节点的簇首竞争等待时间不同,通过时序方式选择簇首,剩余能量高、邻居节点分布均匀的节点成为簇首的机会更大。在簇间路由阶段,采用改进的蚁群算法多跳方式传输数据到Sink节点,考虑剩余能量、传输延时、链路质量等因素,选择一条最优的传输路径。通过对本文算法、EEUC和ACOUC算法进行比较实验,结果表明本文算法更能有效均衡网络能耗,时延更短,丢包率更低,有效延长网络生命周期。 另外,本文算法中的各个参数会影响效率和性能,且各个参数存在关联性,如何确定各参数值及其最佳组合需要进一步的实验和研究。 [1]YickJ,MukherjeeB,GhosalD.Wirelesssensornetworksurvey[J] .ComputerNetworks, 2008,52(12):2292-2330. [2] 苏金树,郭文忠,余朝龙,等.负载均衡感知的无线传感器网络容错分簇算法[J].计算机学报,2014,37(2):445-456. [3] 董 颖,苏真真,周占颖,等.一种基于节点剩余能量和位置的LEACH改进算法[J].四川大学学报(工程科学版),2015,47(2):136-141. [4]BhattacharyaI,GhoshS,KunduS.MaximizinglifetimeofWirelessSensorNetworkthroughextendedLEACHAlgorithm[M].AdvancesinComputerScienceandInformationTechnology.ComputerScienceandInformationTechnology.BerlinHeidelberg:Springer,2012:377-386. [5]LiuY,ChenX,LongC,etal.Improvementofhierarchicalroutingalgorithmforheterogeneouswirelesssensornetworks[J].JournalofComputationalInformationSystems, 2012,8(10):4143-4150. [6] 任非原,黄海宁,林 闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291. [7] 刘 群,白全炜,曾宪华,等.能量感知的WSN节点分类控制路由算法[J].传感技术学报,2011,24(7):1053-1059. [8]HeinzelmanW.ChandrakasanA.BalakrishnamH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[A].Procofthe33rdConfonSystemSciences[C].Piscataway.NJ:IEEE. 2000:3005-3014. [9]MhatreV,RosenbergC.Designguidelinesforwirelesssensornetworks:Communication,clusteringandaggregation[J].AdHocNetworks, 2004, 2(1): 45-63. [10] 李成法,陈贵海,叶 懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(1):27-36. [11] 蒋畅江,石为人,唐贤伦,等.能量均衡的无线传感器网络非均匀分簇路由协议[J].软件学报,2012,23(5):1222-1232. [12] 卢先顺,王莹莹,王洪斌,等.无线传感器网络能量均衡的非均匀分簇算法[J].计算机科学,2013,40(5):78-81. [13] 皇苏斌,王忠群,汪千松. 能量均衡的无线传感器网络节点非均匀分布路由协议[J].计算机应用,2011, 31(11):2887-2890. [14] 张荣博,曹建福.利用蚁群优化的非均匀分簇无线传感器网络路由算法[J].西安交通大学学报,2010,44(6):33-38. [15] 侯彦军,谭国真.一种WSN分簇路由协议研究和实现[J].计算机科学,2015,42(5):160-187. [16] 王开通,熊庆宇 等.无线传感器网络LEACH路由协议研究与改进[J].计算机工程与应用,2015,51(10):103-107. [17]CaoQ,HeT,andFangL,etal.Efficiencycentriccommunicationmodelforwirelesssensornetworks[A].Proc.oftheIEEEINFOCOM[C].Barcelona:IEEEComputerSocietyPress,2006: 1-12. [18]EstrinD.WirelesssensornetworkstutorialpartIV:Sensornetworkprotocols[A].ProcoftheACMMobilComputingandNetworking[C].NewYork:ACM, 2002. 1-5. [19] 郭书城,卢 昱,许定根. 基于分簇无线传感器网络的路由算法研究[J].通信学报,2010,31(8A):63-69. [20] 毛莺池,王久龙 等.基于链路质量的层次型路由协议研究[J].计算机科学,2015,42(3):74-80. UnevenClusteringRoutingProtocolforWirelessSensorNetworksBasedonImprovedAntColonyAlgorithm Liao Fubao1,Zhang Wenmei2 (1.Department of Computer, Guangdong AIB Polytechnic College, Guangzhou 510507, China;2.Department of Mechanics and Electronics, Guangdong AIB Polytechnic College, Guangzhou 510507, China) Aiming at the energy consumption unbalance and “hotspot” energy hole for sensor nodes random distribution in Wireless Sensor Networks(WSNs), an uneven clustering routing protocol for WSNs based on improved ant colony algorithm is proposed. The protocol adopts round operation mode, in the beginning phase of each round cluster-head selection, it forms the uneven competition radius of nodes by the density of the nodes, residual energy and the distance to sink. The rate of residual energy and the average of distance deviation of nodes are calculated by the competition radius, and then the nodes’ wait times of cluster-head selection are calculated. In the cluster-head selection phase, the protocol adopts wait time of cluster-head selection to select the cluster head and balances the energy consumption in the cluster. In the data transmission phase, concerning the residual energy, energy consumption, link quality and transmission delay, the protocol adopts improved ant colony algorithm to construct optimal transmission path. The pheromones are updated at the time of data transmission, and the transmission path are established and maintained more self-adaptive and dynamic. The simulation shows that the routing protocol can efficiently reduce and balance the energy consumption, prolong the wireless sensor network survival period, improve the link quality and reduce transmission delay. wireless sensor networks; unequal clustering; ant colony algorithm; routing protocol 2016-10-07; 2016-11-22。 科技部国家星火计划项目(2013GA780003)。 廖福保(1976-),男,江西宁都人,硕士,副教授,主要从事计算机应用、无线传感器网络与路由方向的研究 1671-4598(2017)04-0147-06DOI:10.16526/j.cnki.11-4762/tp TP A4 仿真实验
5 结语