基于蜂群算法的無線傳感器網絡任播路由協(xié)議_第1頁
基于蜂群算法的無線傳感器網絡任播路由協(xié)議_第2頁
基于蜂群算法的無線傳感器網絡任播路由協(xié)議_第3頁
基于蜂群算法的無線傳感器網絡任播路由協(xié)議_第4頁
基于蜂群算法的無線傳感器網絡任播路由協(xié)議_第5頁
已閱讀5頁,還剩1頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

基于蜂群算法的無線傳感器網絡任播路由協(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控制

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論