基于蜂群算法的無線傳感器網絡任播路由協(xié)議

基于蜂群算法的無線傳感器網絡任播路由協(xié)議

無線傳感器網絡的節(jié)點（無線傳感器網絡）的工作依賴有限的電源（電池），因此傳統(tǒng)的路徑協(xié)議大多數不適合無線傳感器網絡。蜂群算法是一種模仿蜜蜂繁殖和采蜜等行為的新興的群體智能優(yōu)化技術,近年來受到眾多學者的關注。蜂群算法目前主要應用于函數優(yōu)化、電力系統(tǒng)分析、神經網絡訓練、圖像處理等領域。由于其具有群體智能的特點,近年來也有學者將蜂群算法應用在路由技術中,如Rashedi將蜂群算法應用在光網絡的路由和波長分配技術中以減少阻塞概率;Szeto將蜂群算法應用在限量運輸路由問題中;Zheng針對多播路由技術中的Steiner樹問題,采用蜂群算法進行優(yōu)化,相比較傳統(tǒng)遺傳算法和蟻群算法,收斂速度更快,優(yōu)化結果更佳;Singh通過蜂群算法尋找無向帶權圖中最小遍歷開銷。目前,蜂群算法在WSN路由中的應用還較少,如Karaboga將蜂群算法的智能覓食策略應用在WSN路由中的成簇技術中;Fahmy采用2種類型的蜜蜂Agent去尋找源節(jié)點至目標節(jié)點的可用路徑,通過預測機制選擇能耗最小的路徑作為目標路徑。Santhiya提出一種混合蜂群算法和蟻群算法的路由協(xié)議(EARRP),該協(xié)議以MAC開銷、剩余能量和鏈路失效率作為適應度函數,混合蜂群算法和蟻群算法進行優(yōu)化從而獲得最優(yōu)路徑,EERRP思路較新穎,但實際優(yōu)化過程中以蟻群算法為主體,蜂群算法的優(yōu)化作用體現(xiàn)并不明顯。受啟發(fā)于人工蜂群算法ABC(ArtificialBeeColony)中的采蜜機理,本文提出一種基于蜂群算法的WSN任播路由協(xié)議,該協(xié)議具有控制開銷低和能耗效率高等性能優(yōu)勢。1蜂群算法及數據說明在WSN中節(jié)省節(jié)點能耗是一個重要研究課題,有大量研究成果已成功應用于提高WSN生存期,如在大規(guī)模WSN中增加基站數目并引入任播技術能夠均衡能耗,提高WSN生存期。任播是IPv6提供的一種新型網絡服務,指一個發(fā)送者和通信組中的任意一個之間的通信。本文標記:A為某任播地址;G(A)為共享A的任播組員集合(即基站集合),共有M個組員;Ai為G(A)中第i個組員;U為傳感器節(jié)點集合,共有N個節(jié)點。由于任播技術具有均衡數據流和能耗的特點,可以較好地應用在WSN路由中。為減少能耗,本文協(xié)議還采用睡眠喚醒機制,每個節(jié)點都有自己的喚醒率(單位時間內喚醒狀態(tài)時間所占比例),本文設置節(jié)點的喚醒率與其剩余能量率有關,當節(jié)點能量率低于相應閾值時,相應降低其喚醒率。蜂群采食首先由偵查蜂(Scouter)搜索食物,探測信息通過蜜蜂的一種特殊舞蹈(搖擺舞)在蜂群中共享;隨后組織采集蜂(Forager)采蜜,其數目取決于食物數量。根據上述原理,學者常以此為啟發(fā),以食物源代表各種可能的解,以采蜜過程代表搜索函數最優(yōu)解的過程。本文將蜂群算法應用在WSN任播路由中,為適應WSN的特性,將蜂群算法做一些改進。首先,各個傳感器節(jié)點被視為一個個蜂箱,各節(jié)點需要向任一基站(任播組員)匯報監(jiān)測數據分組,各基站被視為食物源;蜂箱至某食物源的路徑跳數和中間節(jié)點剩余能量情況被視為該食物源的食物充裕程度。蜂群算法中設置3種蜜蜂:蜂后(Queen),偵查蜂和采集蜂。每個蜂箱由蜂后產生偵查蜂和采集蜂分別用來查詢路由和傳遞分組。在WSN中,若節(jié)點u∈U監(jiān)測到移動事件發(fā)生需匯報至任一基站,節(jié)點u周圍區(qū)域的節(jié)點也有很大幾率在此時或隨后監(jiān)測到該目標移動事件并也需匯報至基站。為節(jié)省路由查詢能耗,節(jié)點u尋找基站路由的同時也通知其周圍區(qū)域節(jié)點無需尋找基站路由,當路由尋找完畢后將查詢信息通知相應節(jié)點?；谝陨显O計策略,本文將探索蜂分為2種:長途探索蜂LDS(Long-DistanceScouter)和短途探索蜂SDS(Short-DistanceScouter)。LDS和SDS都用來查詢路由,但最大跳數設置不同。SDS最大跳數值設置為H,因此SDS所探知的是一個半徑為H的區(qū)域FZ(ForagingZone);LDS最大跳數值設置為與網絡直徑相關,即允許其探索整個網絡區(qū)域。LDS在路由查找過程中需攜帶其編號,源節(jié)點地址,目標地址,本次路由查找編號(PID),路徑堆棧,上一跳節(jié)點,TTL(TimetoLive),路徑跳數D,路徑中節(jié)點最小能量值E(MinimumEnergy),數據字典和度量值R等信息,其結構如圖1所示。每個節(jié)點需維護兩個本地路由信息表:SDS表和LDS表。SDS表需保存其FZ區(qū)域內所有節(jié)點的路由信息,其表項有目標單播地址、下一跳地址和跳數等。LDS表需保存至所有基站節(jié)點的路由信息,其表項有目標單播地址,目標任播地址,下一跳地址,路徑跳數D,E值,度量值R和路徑信息棧等。其結構如圖2所示。顯然,LDS表結構大于SDS表,但由于LDS表只保存至各基站節(jié)點的路由信息,而基站數目相對較少,因此所帶來的路由維護開銷也相對較小。2處理協(xié)議的步驟模仿蜜蜂的采蜜過程,協(xié)議操作被分成以下6個步驟。(1)相鄰鄰近節(jié)點分析每一個節(jié)點需周期性發(fā)送刷新報文去探知相鄰(一跳)鄰居節(jié)點情況;當一個節(jié)點從睡眠切換至喚醒階段需及時向相鄰鄰居節(jié)點匯報;當節(jié)點收到相鄰鄰居節(jié)點的響應信息后,需保存其路由信息及剩余能量率至本地Cache中,保存或刷新SDS表和LDS表中以該相鄰鄰居節(jié)點為第一跳的相關路徑信息;當指定時間Δt內不能收到相鄰鄰居節(jié)點的響應報文,則判定該節(jié)點丟失,從Cache、SDS表和LDS表中移除包含該節(jié)點的所有路徑信息,由于本文采用睡眠喚醒機制,指定時間Δt需大于系統(tǒng)規(guī)定最大睡眠時長。(2)訪問和維護sds表沿線信息每一個節(jié)點還需周期性派遣SDS查詢和維護自身FZ區(qū)域的路由信息,操作過程與相鄰鄰居節(jié)點路由信息維護相似,在此不贅述。(3)節(jié)點s查詢或更新基當源節(jié)點(蜂巢)偵查到的基站數目不能滿足客戶需求或者已有基站路徑中間節(jié)點剩余能量較低(食物不充沛)導致在巢采集蜂數量無法滿足監(jiān)測數據分組流量要求,源節(jié)點需(重新)派遣LDS查詢或更新基站路由信息。為節(jié)省查詢能耗,節(jié)點u∈U尋找到基站后需將尋找到的路由信息通知其FZ內其他節(jié)點,而這些節(jié)點無需尋找路由。如圖3是一個WSN監(jiān)測網絡,H設置為3,圖3中目標移動事件只需由節(jié)點n1和n2作為代表節(jié)點去查找基站,而無需監(jiān)測到該移動事件的所有節(jié)點(圖3中白色節(jié)點)去參與路由查詢,節(jié)省大量路由查詢能耗。代表節(jié)點基本操作步驟如下:當節(jié)點監(jiān)測到移動事件后,由其充當代表節(jié)點并通知其FZ區(qū)域內所有節(jié)點;已被代表的節(jié)點在隨后監(jiān)測到該移動事件不再去查詢基站路由信息,等待代表節(jié)點轉發(fā)其尋找到的路由信息。(4)u3000s-n-大力推進網絡負荷的計算源節(jié)點通過LDS查詢基站路由信息,LDS的數量Ψ取決于最近K個時間周期窗口內該節(jié)點最大監(jiān)測數據分組流量F,Ψ計算如下:其中,Fs為預期平均流量;Ψs為預期平均流量下系統(tǒng)所需LDS數量。由式(1)可知,當監(jiān)測數據流量較大時,Ψ值也隨之增大,尋找基站和最優(yōu)路徑的能力也相應增強;另一方面,當監(jiān)測數據流量劇增時,網絡中也不會大量充斥LDS,加重網絡負荷。查詢過程采用轉發(fā)機制,步驟如下:Step1中間節(jié)點轉發(fā)LDS至其一個相鄰鄰居節(jié)點處(通過LDS攜帶的上一跳節(jié)點ID信息可以避免按原路轉發(fā))。LDS在選擇下一站時,需先檢查本地Cache,首選未曾接收過源節(jié)點相同且PID相同(即同一批次)LDS的節(jié)點(通過Cache可以查知),次選能量較高的節(jié)點。中間節(jié)點在本地Cache保留該LDS信息以及其所選擇的下一站。Step2LDS在尋找路由過程中需保存并攜帶所經過的跳數D,路徑堆棧,路途時間t,中間節(jié)點最小剩余能量值E,路徑度量值R等信息。設LDS所經過的任播路徑P=S-n1-n2-…-nk-Ah,其中S是源節(jié)點,Ah是基站h,則路徑P的E=min{E(n1),E(n2),…,E(nk)}。路徑度量值R用來反映路徑食物充沛度,計算如下:R=E/D(2)由式(1)可知,中間節(jié)點剩余能量較高且路徑跳數較小的路徑具有較高的度量值。Step3當LDS到達任一基站后需根據路徑堆棧原路返回源節(jié)點;LDS返回源節(jié)點后匯報其查詢到的路由信息;源節(jié)點從LDS返回的各條路徑中選擇至各基站的最優(yōu)路徑并計算各基站的度量值。(5)源節(jié)點以自身渠道為驅動源節(jié)點通過采集蜂攜帶監(jiān)測數據分組至基站,監(jiān)測數據分組必須由采集蜂攜帶才能傳遞。蜂后產生的采集蜂總數設為L,根據基站數目將采集蜂劃分為M組,至某基站如Ai的檢測數分組必須由相對應組別的采集蜂才能攜帶傳遞?；救鏏i所對應組別的采集蜂的數量取決于至該基站路徑的度量值,至基站Ai的采集蜂數量L(Ai)計算如下所示:L(Ai)=R(Ai)∑i=1MR(Ai)R(Ai)∑i=1ΜR(Ai)L(3)其中,R(Ai)為源節(jié)點至基站Ai的路徑度量值。由于監(jiān)測數據分組由采集蜂攜帶傳輸,本文協(xié)議要求采集蜂還需原路返回源節(jié)點,采集蜂吞吐量需滿足監(jiān)測數據分組流量,因此要求L如下:L=max{2F∑i=1Mt(Ai)L(Ai)/Γ????????????????ue001?ue000ue0002F∑i=1Μt(Ai)L(Ai)/Γ,Lm}(4)其中,t(Ai)為至基站Ai的路徑時間,Lm為系統(tǒng)指定的最小值,Γ為一只采集蜂一次最大攜帶數據量。結合式(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)?！苅=1ΜR(Ai),Lm}(5)根據目前尚未派遣出去的各組采集蜂數量,源節(jié)點按比例隨機選擇采集蜂并傳遞至相應基站,該設計可以使得擁有高度量值的基站擁有較高優(yōu)先權。由于節(jié)點睡眠時長取決于節(jié)點剩余能量率,若高度量值的路徑由于中間節(jié)點能耗較快導致睡眠時間增長,盡管至該基站的采集蜂配比數量較多,但多數還停留在路途中,源節(jié)點采用該路徑的概率降低。因此,本文提出的采集蜂返回機制不僅可以讓源節(jié)點確認數據分組送達基站,而且相比較以往大多數多路徑路由協(xié)議(如文獻[11-12])需要額外維護一張路由權重表并需時時更新,本文設計可以減少路由表的維護開銷。(6)尋找基因組織式(5)中L的設置與最大流量和路徑平均時延有關,通常情況下采集蜂吞吐量可以匹配監(jiān)測數據流量,但由于各基站路徑節(jié)點能耗較多睡眠時間增長,采集蜂往返時間增加,從而出現(xiàn)無法滿足監(jiān)測數據流量的情況。對此需要重新安排LDS去查找基站路由信息,在尋找過程中或者尋找到新的基站(食物源),或者尋找到至某基站的替代路徑(至該基站的原先最優(yōu)路徑由于能耗損失被新的最優(yōu)路徑替代),或者刷新至該基站的時延。由此,采集蜂數量和分配比例將被重新安排,從而改善采集蜂吞吐量問題。3abcarp能耗本節(jié)討論ABCARP的基站路由查詢能耗(控制開銷)。為方便討論,假設移動事件經過所有傳感器節(jié)點的周邊,即所有節(jié)點都需要匯報該監(jiān)測事件的數據分組至基站。如前文所述,ABCARP只需要代表節(jié)點負責尋找基站路由信息,設網絡面積為S,節(jié)點密度為ρ,節(jié)點數為N,可得S=N/ρ。設節(jié)點傳輸半徑為r,則代表節(jié)點的數目Θ≈S/(πr2ρH)。如前文所述,每個代表節(jié)點的LDS數量Ψ取決于該節(jié)點最大監(jiān)測數據分組流量F,假設LDS尋找到基站所需平均時間為T,則代表節(jié)點派遣LDS的平均頻率rL=Ψ/(2T)。本文設置TTL(TimeToLive)值為網絡直徑D,可得D=S√=N/ρ????√D=S=Ν/ρ。假設每個LDS所經過的跳數為最大值TTL,因此,ABCARP單位時間基站路由信息查詢能耗EA計算如下(只計算LDS的傳遞能耗,忽略接收能耗和監(jiān)聽能耗):其中,La為LDS數據大小;{ET×La}為節(jié)點傳輸La比特數據分組至下一站所導致的節(jié)點能耗。而傳統(tǒng)AODV采用全泛洪機制尋找基站路由,而且監(jiān)測到移動事件的所有節(jié)點都要參與查詢基站路由。在全泛洪機制下,中間節(jié)點需將從鄰居節(jié)點接收的RREQ轉發(fā)給其他鄰居節(jié)點。記節(jié)點平均周圍鄰居節(jié)點數目為w,w=ρπr2-1。一個中間節(jié)點共需轉發(fā)(w-1)w個RREQ。因此AODV中各節(jié)點因RREQ的傳遞總能耗(忽略接收能耗和監(jiān)聽能耗)EV計算如下:其中,Lq是RREQ數據報大小,{ET×La}為節(jié)點傳輸La比特數據分組至下一站所導致的節(jié)點能耗,rs為節(jié)點尋找基站路由信息的頻率,由于AODV為按需驅動路由,節(jié)點沒有路由表,rs通常即為監(jiān)測事件發(fā)生頻率。顯然LDS數據報大小(La)要大于RREQ數據報大小(Lq),而且當監(jiān)測事件發(fā)生頻率極低時,即rs極小,AODV的控制開銷也極少。而ABCARP由于需要經常性地維護路由表,控制開銷較大。但由上文可知,ABCARP的控制開銷能耗數量級為O(N3/2),低于AODV的O(N2)。因此,當監(jiān)測事件發(fā)生頻率較高時,隨著網絡規(guī)模(N)的增大,ABCARP的能耗優(yōu)勢將漸漸體現(xiàn)。而且,AODV要求所有節(jié)點都需要查詢基站信息,而ABCARP只需要代表節(jié)點去查詢,從而進一步提高ABCARP的能耗優(yōu)勢。4基于傳感器網絡帶及sds-pct的事件網絡設置以下我們以WSN中常用的AODV以及群體智能路由協(xié)議的代表Ant-AODV作為對照協(xié)議,來評價ABCARP的優(yōu)劣。仿真模擬一個具有N個(80～180)節(jié)點的網絡,節(jié)點隨機分布在180m×180m矩形區(qū)域里。網絡設置如下:節(jié)點傳輸半徑r為30m;指定任播組員(基站)節(jié)點,數目設置為4,基站具有無限能量;傳感器節(jié)點初始能量為50J,剩余能量率為100%(即喚醒率為100%);設置H=2;傳輸速度為160kbit/s;以矩形左下角為坐標系原點;以參數λ=0.5的泊松分布產生移動事件,該事件監(jiān)測數據分組大小為1kbit,事件移動速度為30m/s,移動軌跡為直線y=ax+90,其中a為常數,在間隨機取值,x∈。不改變區(qū)域面積,不斷調節(jié)節(jié)點數目(80～180,即節(jié)點密度ρ=0.0025～0.0056),運行20s,檢查各協(xié)議性能參數。4.1基于防止主體網絡地理風險的算法實驗觀察發(fā)送1kbit監(jiān)測數據分組所需平均路由查詢和維護控制開銷,結果如圖4所示。由圖4可知,隨著節(jié)點數增加,AODV控制開銷增加明顯;Ant-AODV是針對傳統(tǒng)蟻群路由算法時延較長等缺點,在AODV協(xié)議泛洪之前加入蟻群算法進行優(yōu)化處理,從而能夠有效降低時延,但由于仍然需要廣播泛洪,控制開銷并不少于AODV,其次前向螞蟻在移動過程中需要攜帶并創(chuàng)建源節(jié)點路由信息表,螞蟻個體體積增大從而增加控制開銷,而且,隨著節(jié)點數增加(密度增加),移動事件所波及的監(jiān)測節(jié)點數增加,網絡動態(tài)變化較大,蟻群算法不適應于動態(tài)性網絡的缺點體現(xiàn)更加明顯;ABCARP沒有采用泛洪查詢機制,采用兩級探索蜂機制,控制開銷較少,而且通過代表節(jié)點查詢基站,該機制在移動目標監(jiān)測事件中能夠節(jié)省大量控制開銷。4.2節(jié)點密度對ant-aodv定位能耗的影響實驗觀察發(fā)送1kbit監(jiān)測數據分組所需平均能耗(傳遞、接收和監(jiān)聽能耗),結果如圖5所示。由圖5可知,隨著節(jié)點數增加(節(jié)點密度增加),各協(xié)議監(jiān)測數據分組發(fā)送能耗都相應增加,原因主要是監(jiān)聽能耗和重傳能耗的增加。Ant-AODV控制