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

顧云麗，徐 昕，杜 杰，侯榮濤，錢煥延

(1.南京信息工程大學，江蘇省網絡監控中心，南京210044;2.南京理工大學，計算機科學與技術學院，南京210094)

無線傳感器網絡WSN(Wireless Sensor Networks)節點的工作依賴于有限電源(電池)［1］，因此傳統路由協議大多不適合WSN。蜂群算法是一種模仿蜜蜂繁殖和采蜜等行為的新興的群體智能優化技術，近年來受到眾多學者的關注。蜂群算法目前主要應用于函數優化、電力系統分析、神經網絡訓練、圖像處理等領域［2－3］。由于其具有群體智能的特點，近年來也有學者將蜂群算法應用在路由技術中，如Rashedi［4］將蜂群算法應用在光網絡的路由和波長分配技術中以減少阻塞概率;Szeto［5］將蜂群算法應用在限量運輸路由問題中;Zheng［6］針對多播路由技術中的Steiner樹問題，采用蜂群算法進行優化，相比較傳統遺傳算法和蟻群算法，收斂速度更快，優化結果更佳;Singh［7］通過蜂群算法尋找無向帶權圖中最小遍歷開銷。

目前，蜂群算法在WSN路由中的應用還較少，如Karaboga［8］將蜂群算法的智能覓食策略應用在WSN路由中的成簇技術中;Fahmy［9］采用2種類型的蜜蜂Agent去尋找源節點至目標節點的可用路徑，通過預測機制選擇能耗最小的路徑作為目標路徑。Santhiya［10］提出一種混合蜂群算法和蟻群算法的路由協議(EARRP)，該協議以MAC開銷、剩余能量和鏈路失效率作為適應度函數，混合蜂群算法和蟻群算法進行優化從而獲得最優路徑，EERRP思路較新穎，但實際優化過程中以蟻群算法為主體，蜂群算法的優化作用體現并不明顯。

受啟發于人工蜂群算法ABC(Artificial Bee Colony)中的采蜜機理，本文提出一種基于蜂群算法的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-Distance Scouter)和短途探索蜂SDS(Short-Distance Scouter)。LDS和SDS都用來查詢路由，但最大跳數設置不同。SDS最大跳數值設置為H，因此SDS所探知的是一個半徑為H的區域FZ(Foraging Zone);LDS最大跳數值設置為與網絡直徑相關，即允許其探索整個網絡區域。LDS在路由查找過程中需攜帶其編號，源節點地址，目標地址，本次路由查找編號(PID)，路徑堆棧，上一跳節點，TTL(Time to Live)，路徑跳數D，路徑中節點最小能量值E(Minimum Energy)，數據字典和度量值R等信息，其結構如圖1所示。

圖1 長途探索蜂攜帶信息結構圖

每個節點需維護兩個本地路由信息表:SDS表和LDS表。SDS表需保存其FZ區域內所有節點的路由信息，其表項有目標單播地址、下一跳地址和跳數等。LDS表需保存至所有基站節點的路由信息，其表項有目標單播地址，目標任播地址，下一跳地址，路徑跳數D，E值，度量值R和路徑信息棧等。其結構如圖2所示。

圖2 LDS表結構圖

顯然，LDS表結構大于SDS表，但由于LDS表只保存至各基站節點的路由信息，而基站數目相對較少，因此所帶來的路由維護開銷也相對較小。

2 協議操作步驟

模仿蜜蜂的采蜜過程，協議操作被分成以下6個步驟。

(1)相鄰鄰居節點路由信息維護

每一個節點需周期性發送刷新報文去探知相鄰(一跳)鄰居節點情況;當一個節點從睡眠切換至喚醒階段需及時向相鄰鄰居節點匯報;當節點收到相鄰鄰居節點的響應信息后，需保存其路由信息及剩余能量率至本地Cache中，保存或刷新SDS表和LDS表中以該相鄰鄰居節點為第一跳的相關路徑信息;當指定時間Δt內不能收到相鄰鄰居節點的響應報文，則判定該節點丟失，從Cache、SDS表和 LDS表中移除包含該節點的所有路徑信息，由于本文采用睡眠喚醒機制，指定時間Δt需大于系統規定最大睡眠時長。

(2)SDS表路由信息查詢和維護

每一個節點還需周期性派遣SDS查詢和維護自身FZ區域的路由信息，操作過程與相鄰鄰居節點路由信息維護相似，在此不贅述。

(3)選舉代表節點

當源節點(蜂巢)偵查到的基站數目不能滿足客戶需求或者已有基站路徑中間節點剩余能量較低(食物不充沛)導致在巢采集蜂數量無法滿足監測數據分組流量要求，源節點需(重新)派遣LDS查詢或更新基站路由信息。

為節省查詢能耗，節點u∈U尋找到基站后需將尋找到的路由信息通知其FZ內其他節點，而這些節點無需尋找路由。如圖3是一個WSN監測網絡，H設置為3，圖3中目標移動事件只需由節點n1和n2作為代表節點去查找基站，而無需監測到該移動事件的所有節點(圖3中白色節點)去參與路由查詢，節省大量路由查詢能耗。

圖3 WSN移動目標監測示意圖

代表節點基本操作步驟如下:當節點監測到移動事件后，由其充當代表節點并通知其FZ區域內所有節點;已被代表的節點在隨后監測到該移動事件不再去查詢基站路由信息，等待代表節點轉發其尋找到的路由信息。

(4)基站路由信息查詢

源節點通過LDS查詢基站路由信息，LDS的數量Ψ取決于最近K個時間周期窗口內該節點最大監測數據分組流量F，Ψ計算如下:

其中，Fs為預期平均流量;Ψs為預期平均流量下系統所需LDS數量。由式(1)可知，當監測數據流量較大時，Ψ值也隨之增大，尋找基站和最優路徑的能力也相應增強;另一方面，當監測數據流量劇增時，網絡中也不會大量充斥LDS，加重網絡負荷。

查詢過程采用轉發機制，步驟如下:

Step 2 LDS在尋找路由過程中需保存并攜帶所經過的跳數D，路徑堆棧，路途時間t，中間節點最小剩余能量值E，路徑度量值R等信息。設LDS所經過的任播路徑 P=S－n1－n2－…－nk－Ah，其中 S 是源節點，Ah是基站h，則路徑 P的E=min{E(n1)，E(n2)，…，E(nk)}。路徑度量值R用來反映路徑食物充沛度，計算如下:

由式(1)可知，中間節點剩余能量較高且路徑跳數較小的路徑具有較高的度量值。

Step 3 當LDS到達任一基站后需根據路徑堆棧原路返回源節點;LDS返回源節點后匯報其查詢到的路由信息;源節點從LDS返回的各條路徑中選擇至各基站的最優路徑并計算各基站的度量值。

(5)分組傳遞

源節點通過采集蜂攜帶監測數據分組至基站，監測數據分組必須由采集蜂攜帶才能傳遞。蜂后產生的采集蜂總數設為L，根據基站數目將采集蜂劃分為M組，至某基站如Ai的檢測數分組必須由相對應組別的采集蜂才能攜帶傳遞。基站如Ai所對應組別的采集蜂的數量取決于至該基站路徑的度量值，至基站Ai的采集蜂數量L(Ai)計算如下所示:

其中，R(Ai)為源節點至基站Ai的路徑度量值。由于監測數據分組由采集蜂攜帶傳輸，本文協議要求采集蜂還需原路返回源節點，采集蜂吞吐量需滿足監測數據分組流量，因此要求L如下:

其中，t(Ai)為至基站Ai的路徑時間，Lm為系統指定的最小值，Γ為一只采集蜂一次最大攜帶數據量。

安吉每周三下午都會去動物園看望他的朋友小象安琪兒。安吉剛搬到橡樹灣，爸爸工作很忙，媽媽生病了，他在橡樹灣一個朋友也沒有。

結合式(3)和式(4)，解得采集蜂數量L如下:

根據目前尚未派遣出去的各組采集蜂數量，源節點按比例隨機選擇采集蜂并傳遞至相應基站，該設計可以使得擁有高度量值的基站擁有較高優先權。由于節點睡眠時長取決于節點剩余能量率，若高度量值的路徑由于中間節點能耗較快導致睡眠時間增長，盡管至該基站的采集蜂配比數量較多，但多數還停留在路途中，源節點采用該路徑的概率降低。因此，本文提出的采集蜂返回機制不僅可以讓源節點確認數據分組送達基站，而且相比較以往大多數多路徑路由協議(如文獻［11－12］)需要額外維護一張路由權重表并需時時更新，本文設計可以減少路由表的維護開銷。

(6)基站路由信息維護

式(5)中L的設置與最大流量和路徑平均時延有關，通常情況下采集蜂吞吐量可以匹配監測數據流量，但由于各基站路徑節點能耗較多睡眠時間增長，采集蜂往返時間增加，從而出現無法滿足監測數據流量的情況。對此需要重新安排LDS去查找基站路由信息，在尋找過程中或者尋找到新的基站(食物源)，或者尋找到至某基站的替代路徑(至該基站的原先最優路徑由于能耗損失被新的最優路徑替代)，或者刷新至該基站的時延。由此，采集蜂數量和分配比例將被重新安排，從而改善采集蜂吞吐量問題。

3 基站路由查詢能耗分析

本節討論ABCARP的基站路由查詢能耗(控制開銷)。為方便討論，假設移動事件經過所有傳感器節點的周邊，即所有節點都需要匯報該監測事件的數據分組至基站。如前文所述，ABCARP只需要代表節點負責尋找基站路由信息，設網絡面積為S，節點密度為ρ，節點數為N，可得S=N/ρ。設節點傳輸半徑為r，則代表節點的數目Θ≈S/(πr2ρH)。如前文所述，每個代表節點的LDS數量Ψ取決于該節點最大監測數據分組流量F，假設LDS尋找到基站所需平均時間為T，則代表節點派遣LDS的平均頻率rL=Ψ/(2T)。本文設置TTL(Time To Live)值為網絡直徑D，可得。假設每個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 實驗與分析

以下我們以WSN中常用的AODV以及群體智能路由協議的代表Ant-AODV［13］作為對照協議，來評價ABCARP的優劣。

仿真模擬一個具有N個(80～180)節點的網絡，節點隨機分布在180 m×180 m矩形區域里。網絡設置如下:節點傳輸半徑r為30 m;指定任播組員(基站)節點，數目設置為4，基站具有無限能量;傳感器節點初始能量為50 J，剩余能量率為100%(即喚醒率為100%);設置H=2;傳輸速度為160 kbit/s;以矩形左下角為坐標系原點;以參數λ=0.5的泊松分布產生移動事件，該事件監測數據分組大小為1 kbit，事件移動速度為30 m/s，移動軌跡為直線y=ax+90，其中a為常數，在［－1，1］間隨機取值，x∈［0，180］。不改變區域面積，不斷調節節點數目(80～180，即節點密度 ρ=0.002 5 ～0.005 6)，運行20 s，檢查各協議性能參數。

4.1 控制開銷

實驗觀察發送1 kbit監測數據分組所需平均路由查詢和維護控制開銷，結果如圖4所示。由圖4可知，隨著節點數增加，AODV控制開銷增加明顯;Ant-AODV是針對傳統蟻群路由算法時延較長等缺點，在AODV協議泛洪之前加入蟻群算法進行優化處理，從而能夠有效降低時延，但由于仍然需要廣播泛洪，控制開銷并不少于AODV，其次前向螞蟻在移動過程中需要攜帶并創建源節點路由信息表，螞蟻個體體積增大從而增加控制開銷，而且，隨著節點數增加(密度增加)，移動事件所波及的監測節點數增加，網絡動態變化較大，蟻群算法不適應于動態性網絡的缺點體現更加明顯;ABCARP沒有采用泛洪查詢機制，采用兩級探索蜂機制，控制開銷較少，而且通過代表節點查詢基站，該機制在移動目標監測事件中能夠節省大量控制開銷。

圖4 節點數和控制開銷

4.2 能耗效率

實驗觀察發送1 kbit監測數據分組所需平均能耗(傳遞、接收和監聽能耗)，結果如圖5所示。

圖5 節點數和能耗效率

由圖5可知，隨著節點數增加(節點密度增加)，各協議監測數據分組發送能耗都相應增加，原因主要是監聽能耗和重傳能耗的增加。Ant-AODV控制開銷最高，而且蟻群算法需要較長時間聚合螞蟻，分組成功到達率PDR(Packet Delivery Ratio)較低，重傳能耗較大，因此其能耗效率最低。ABCARP雖然PDR也低于AODV，但由于控制開銷大大低于AODV，因此具有較好的能耗效率。

4.3 端對端時延

實驗觀察各監測數據分組到達基站的平均時間，結果如圖6所示。

由圖6可知，AODV受網絡規模影響小，由于無需等待，也不維持Cache，時延最小;Ant-AODV由于需要蟻群算法進行優化，時延相對較長，受網絡規模影響相對較大;ABCARP時延最大，這是由于相比較泛洪，兩級探索蜂機制尋找基站的時延相對較長，其次各節點需要等待代表節點轉發的基站路由信息，還有ABCARP采用任播機制，有一定概率將監測數據分組發往較遠的基站。另外，在實驗設置中，沒有討論ABCARP中節點睡眠喚醒機制所帶來的時延問題，當系統運行一段時間后，節點喚醒率降低，ABCARP端對端時延還會增加，因此ABCARP不適合應用在時延受限系統中。

圖6 節點數和端對端時延

5 結語

針對蜂群算法的群體智能適用于路由查詢的特點，提出一種基于蜂群算法的WSN任播路由協議(ABCARP)。ABCARP采用兩級偵查蜂機制，由短途偵查蜂查詢節點周邊區域(FZ區域)，由代表節點的長途偵查蜂查詢基站路由并通知其FZ區域內其他節點，由各節點的采集蜂攜帶監測數據分組傳輸至基站。在移動目標監測事件中，仿真實驗數據表明，相比較AODV和Ant-AODV協議，ABCARP在控制開銷和能耗效率上具有更好的性能優勢，但端對端時延性能較差，不適合應用于時延受限系統中。

［1］ 田賢忠，朱金鳳，陳群，等.無線網絡中基于編碼感知的能量優化路由算法［J］.傳感技術學報，2012，25(9):1304－1311

［2］ Dereli T，Das G S.A Hybrid“Bee(s)Algorithm”for Solving Container Loading Problems［J］.Applied Soft Computing，2011，11(2):2854－2862.

［3］ 劉勇，馬良.函數優化的蜂群算法［J］.控制與決策，2012，27(6):886－890.

［4］ Rashedi A，Kavian Y S，Ansari-Asl K，et al.Dynamic Routing and Wavelength Assignment:Artificial Bee Colony Optimization［C］//Proceedings of ICTON’11.2011(1):1－4.

［5］ Szeto W Y，Wu Y Z，Ho S C.An Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem［J］.European Journal of Operational Research，2011，215(1):126－135.

［6］ Zheng Z H，Wang H，Yao L.An Artificial Bee Colony Optimization Algorithm for Multicast Routing［C］//Proceedings of ICACT’12.2012，168－172.

［7］ Singh A，Sundar S.An Artificial Bee Colony Algorithm for the Minimum Routing Cost Spanning Tree Problem ［J］.Soft Computing，2011，15(12):2489－2499.

［8］ Karaboga D，Okdem S，Ozturk C.Cluster Based Wireless Sensor Network Routing Using Artificial Bee Colony Algorithm［J］.Wireless Networks，2012，18(7):847－860.

［9］ Fahmy I M A，Hefny H A，Nassef L.PEEBR:Predictive Energy Efficient Bee Routing Algorithm for Ad-Hoc Wireless Mobile Networks［C］//Proceedings of 8th International Conference on Informatics and Systems，2012，18－24.

［10］ Santhiya K G，Arumugam N.Energy Aware Reliable Routing Protocol(EARRP)for Mobile Ad Hoc Networks Using Bee Foraging Behavior and Ant Colony Optimization［J］.International Journal of Computer Science Issues，2012，9(2):171－175.

［11］王汝傳，李映，徐小龍，等.基于移動代理的動態路由算法的研究［J］.計算機學報，2005，28(3):420－426.

［12］金仁成，秦紀云，高騰，等.一種適用于無線多媒體傳感器網絡的節點不相交多路徑路由協議［J］.傳感技術學報，2010，23(7):1000－1005.

［13］ Abdel-Moniem A M，Mohamed M H，Hedar A R，et al.An Ant Colony Optimization Algorithm for the Mobile Ad Hoc Network Routing Problem Based on AODV Protocol［C］//Proceedings of ISDA’10.2010，1332－1337.