基于蟻群算法的搜索區(qū)域受限的WSN 路由協(xié)議

張 波，安 樂，湯一波

（遼寧大學 信息學院，遼寧 沈陽110036）

0 引 言

無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）是由大量具有通信與計算能力的微小傳感器節(jié)點構(gòu)成的自組織網(wǎng)絡(luò)系統(tǒng)，是一種全新的信息獲取和處理技術(shù)，廣泛應(yīng)用于國防軍事，環(huán)境監(jiān)測，反恐救災(zāi)及目標跟蹤等領(lǐng)域［1－3］。

傳感器節(jié)點的能量是無線傳感器網(wǎng)絡(luò)中最寶貴的資源之一，能量控制一直是無線傳感器網(wǎng)絡(luò)研究的焦點。為了有效延長網(wǎng)絡(luò)生存時間，減少路徑建立和數(shù)據(jù)傳輸時的能量消耗，下一跳節(jié)點的選取就成為了路由策略的關(guān)鍵。因此，設(shè)計節(jié)能，高效的路由協(xié)議成為無線傳感器網(wǎng)絡(luò)的研究熱點［4，5］。

1 相關(guān)工作

蟻群算法是由Dorigo等人在1992年提出來的一種性能優(yōu)良的啟發(fā)式隨機優(yōu)化算法，它通過螞蟻之間的信息交流與協(xié)作最終找到最優(yōu)解。蟻群算法最初用于解決TSP 問題，后來用于模擬生物過程，網(wǎng)絡(luò)路由優(yōu)化，生產(chǎn)調(diào)度，車輛路徑規(guī)劃等復雜問題［6－8］。文獻［9］提出一種基于蟻群算法的ARAWSN 算法，該算法采用了自適應(yīng)和自組織的尋優(yōu)機制進行路徑的建立。ARAWSN 算法雖然可以找出網(wǎng)絡(luò)中的最優(yōu)路徑，但是沒有考慮節(jié)點的剩余能量，使得節(jié)點的能量消耗過快從而導致節(jié)點的快速死亡，減少了網(wǎng)絡(luò)的生存時間。考慮到節(jié)點剩余能量帶來的問題，文獻［10］提出了一種多種群蟻群優(yōu)化路由算法MACO。該算法能夠均衡傳輸能量消耗和節(jié)點的剩余能量。但是MACO 算法在選擇下一跳節(jié)點的時候沒有考慮到該節(jié)點周圍節(jié)點能量分布的情況，以至于全局節(jié)點消耗的不均勻，降低了網(wǎng)絡(luò)的生存時間。文獻［11］提出了基于位置意識的無線傳感器網(wǎng)絡(luò)路由算法ELACO，該算法限定了下一條節(jié)點的選擇范圍，有效地加快了最優(yōu)路徑的收斂時間。但是ELACO 算法對下一跳節(jié)點的選擇范圍限定的太小，使得產(chǎn)生的最優(yōu)路徑受到了一定的影響。

針對以上論文的不足，提出了基于蟻群算法的搜索區(qū)域受限的WSN 路由協(xié)議。該算法充分考慮了節(jié)點的周圍能量密度，并對ELACO 算法的候選區(qū)域進行了改進，使得全局網(wǎng)絡(luò)節(jié)點能量更加均衡的消耗，有效地增加了無線傳感器網(wǎng)絡(luò)的生存時間。

2 SACACO 路由算法

2.1 算法思想

隨著傳感器節(jié)點能量的消耗，傳感器節(jié)點之間能量存在差異，使得網(wǎng)絡(luò)中的能量分布情況極其的不均衡，按照傳統(tǒng)的蟻群算法選擇下一跳節(jié)點的時候一般只考慮節(jié)點本身的一些屬性，例如剩余能量，鄰居節(jié)點間距離等，并沒有考慮該節(jié)點周圍的能量分布情況，使得在最后形成的路徑上進行數(shù)據(jù)傳輸?shù)臅r候并沒有使全網(wǎng)中能量消耗的更加均衡。如圖1所示。

圖1 節(jié)點能量分布

在圖1中陰影部分代表區(qū)域能量比較高的地方，如果在選擇路徑時優(yōu)先走這樣的區(qū)域，必定會均衡全網(wǎng)的能量消耗。區(qū)域能量只是SACACO 算法考慮的一個因素，因為在建立路由路徑時過分的突出區(qū)域能量的重要性可能會導致建立的路徑增長，從而在傳輸數(shù)據(jù)時加大了能量的消耗。針對這個情況對蟻群算法進行了改進，節(jié)點的能量密度用單位面積內(nèi)的能量大小作為衡量標準。SACACO 算法在設(shè)計轉(zhuǎn)移概率公式的時候，把節(jié)點的周圍能量密度作為一個重要因素。這樣就可以實現(xiàn)全網(wǎng)能量的相對均衡的消耗。

為了尋找出最優(yōu)路徑，中間節(jié)點在選擇下一跳節(jié)點的時候可能會遍歷所有的鄰居節(jié)點，導致發(fā)送過多的查詢消息，從而消耗過多的節(jié)點能量。如果把節(jié)點的選擇范圍限制在一定的范圍之內(nèi)，那么就會大大減少這種不必要的查詢擴散，從而大大的減少全網(wǎng)的能量消耗。

2.2 問題描述

為了方便描述，假設(shè)隨機部署的無線傳感器網(wǎng)絡(luò)具有以下特點：

（1）網(wǎng)絡(luò)中的節(jié)點隨機部署。

（2）節(jié)點的通訊半徑都是相同的。

（3）節(jié)點自身裝有GPS系統(tǒng)，能夠比較準確的測量自身的地理位置。

（4）無線鏈路是對稱的。

無線傳感器網(wǎng)絡(luò)用G＝（V，E）表示，其中V＝｛v1，v2，…，vn｝表示傳感器節(jié)點的集合，n 為節(jié)點的個數(shù)；E 為無線傳感器網(wǎng)絡(luò)邊的集合。用di，j表示節(jié)點vi和vj之間的距離，R 表示每個節(jié)點的通訊半徑。

2.3 基于蟻群算法的搜索區(qū)域受限的WSN 路由算法（SACACO）

定義1 節(jié)點vi的周圍能量密度

式中：N（vi）（N（vi）＝｛vj｜di，j≤R，vj∈V，i≤n，j≤n｝）為節(jié)點vi的鄰居節(jié)點集合，ei，ej為節(jié)點vi，vj的剩余能量。Si，j為以vi為圓心，R 為半徑的圓和以vj為圓心，R 為半徑的圓相交部分的面積。式（1）的物理意義是節(jié)點vi的R 通訊半徑內(nèi)單位面積所含有的能量值。

定義2 用R（vi，R）表示一個以vi為圓心，R 為半徑的圓。用R（vs，ds，i）表示一個以Sink為圓心，以ds，i為半徑的圓，其中ds，i為節(jié)點vi和Sink之間的距離。記圓R（vi，R）和圓R（vs，ds，i）的相交區(qū)域Qi為節(jié)點vi的前向候選區(qū)域。

定義3 位于節(jié)點vi的前向候選區(qū)域Qi中的節(jié)點稱為節(jié)點vi的前向候選節(jié)點。節(jié)點vi的前向候選節(jié)點集合記為P（vi）。

在進行路由選擇時，下一跳節(jié)點的集合不再是該節(jié)點所有的鄰居節(jié)點，而是前向候選節(jié)點集合。如圖2 所示。這樣就限制了查詢消息的擴散范圍，減少了不必要的能量消耗，同時加快了路由路徑的建立速度。

圖2 節(jié)點的前向候選區(qū)域

這里提出一種新的螞蟻前向選擇概率模型，此模型考慮了節(jié)點的周圍能量密度情況。在SACACO 算法中，螞蟻m 按照下面定義的概率行為規(guī)則在前向候選區(qū)域中選擇下一跳節(jié)點。在節(jié)點vi上的螞蟻k選擇下一跳節(jié)點的概率為

式中：τ（i，j）——節(jié)點vi到節(jié)點vj的信息素強度，τ（i，j）＝1／di，j，η（i，j）——能量啟發(fā)函數(shù)，按式（3）計算

在式（2）中β是能量啟發(fā)因子，用于反映在選擇下一跳節(jié)點時剩余能量和周圍能量密度的重要程度。β越大表示螞蟻在選擇下一跳節(jié)點時考慮剩余能量和周圍能量密度的程度越大。

下一跳節(jié)點應(yīng)該在前向候選區(qū)域中進行選擇，這樣每選擇一個節(jié)點就會朝著Sink節(jié)點更進一步，直到Sink節(jié)點為止。在路徑建立過程中，如果前向候選區(qū)域中沒有節(jié)點，則路由無法選擇下一跳節(jié)點，這樣便陷入了路由空洞。如圖3（a）所示，當節(jié)點vi在前向候選區(qū)域中選擇vj作為下一跳節(jié)點時，節(jié)點vj發(fā)現(xiàn)自己的前向候選區(qū)域中沒有節(jié)點，這時便陷入了路由空洞，節(jié)點vj為空洞節(jié)點。為了解決路由空洞問題，這里采用反饋算法，即當前向候選區(qū)域沒有節(jié)點時，那么查詢信息會返回到路由空洞節(jié)點的上一跳節(jié)點。上一跳節(jié)點在它的前向候選區(qū)域中重新選擇下一跳節(jié)點，但這時選擇節(jié)點的時候?qū)⒉辉龠x擇路由空洞節(jié)點進行信息轉(zhuǎn)發(fā)。如圖3（b），路由空洞節(jié)點vj向上一跳節(jié)點vi發(fā)送路由不通消息，vi接收到消息后重新進行路由選擇。當節(jié)點vi選擇下一跳節(jié)點時，它就會從前向候選區(qū)域中選擇節(jié)點vk，不再選擇vj作為下一跳節(jié)點。

圖3 路由空洞解決方法

前向螞蟻k從源節(jié)點出發(fā)，到達下一個節(jié)點的時候按式（4）進行局部信息素的更新

式中：ξ——一個參數(shù)，ξ滿足0＜ξ＜1，τ0——信息素的初始值。

當所有螞蟻到達匯聚節(jié)點后，匯聚節(jié)點將對所有螞蟻所攜帶的路徑信息進行比較，從中選擇最優(yōu)路徑；在最優(yōu)路徑上派出后向螞蟻，并按式（5）進行全局信息素的更新

式中：ρ——信息素的揮發(fā)速率；Lbest（Lbest＝1／L）表示最優(yōu)路徑；L 是最優(yōu)路徑的長度。

在數(shù)據(jù)傳輸?shù)臅r候，路徑上有的節(jié)點可能會由于能量的過多消耗而死亡，這時數(shù)據(jù)傳輸會異常終止，數(shù)據(jù)無法及時到達匯聚節(jié)點。為了解決這個問題，SACACO 算法采用多路徑算法。在源節(jié)點發(fā)現(xiàn)有源數(shù)據(jù)需要傳輸時，它會同時發(fā)出多個種群的螞蟻，每個種群的螞蟻之間互不干擾，這樣最后就形成了多條路徑，增加了路由成功率。

SACACO 算法的具體步驟如下：

步驟1 源節(jié)點派出前向螞蟻。螞蟻中含有源節(jié)點和目標節(jié)點ID 號，目標節(jié)點坐標，所經(jīng)過的中間節(jié)點ID 號，所經(jīng)過的中間節(jié)點之間的距離。

步驟2 根據(jù)當前節(jié)點的通訊半徑和當前節(jié)點和Sink節(jié)點之間的距離，計算出當前節(jié)點的前向候選區(qū)域。

步驟3 在前向候選區(qū)域中根據(jù)式（2）計算出下一跳轉(zhuǎn)發(fā)節(jié)點。如果本節(jié)點前向候選區(qū)域中沒有節(jié)點，則執(zhí)行步驟4；否則執(zhí)行步驟5。

步驟4 根據(jù)路由反饋策略，向上一跳節(jié)點發(fā)送路由不通消息。上一跳節(jié)點在接收到消息后，在它的前向候選區(qū)域中選擇次優(yōu)節(jié)點進行路由信息轉(zhuǎn)發(fā)。

步驟5 根據(jù)式（4）更新所走路徑的局部信息素。

步驟6 所有的螞蟻到達Sink節(jié)點后，在螞蟻的最優(yōu)路徑上派出反向螞蟻并根據(jù)式（5）更新全局信息素。反向螞蟻到達源節(jié)點后，一次路由選擇結(jié)束。

步驟7 重復執(zhí)行步驟1～步驟6，直至達到最大循環(huán)次數(shù)或者90%以上的螞蟻會選擇同一條路徑時，路由選擇結(jié)束。

3 仿真實驗與分析

實驗將SACACO 算法與文獻［6］的ARAWSN 算法，文獻［7］的MACO 算法以及文獻［8］的ELACO 算法在NS2仿真環(huán)境下進行了比較。進行五次獨立實驗，每次實驗獨立實驗五次。實驗的具體仿真環(huán)境是：在100×100m2的正方形區(qū)域內(nèi)，五次實驗部署的節(jié)點數(shù)分別是：100，120，140，160，180；每個節(jié)點的初始能量設(shè)為2J，通訊半徑為30m。Sink節(jié)點的能量足夠大。每個中間節(jié)點需要轉(zhuǎn)發(fā)的數(shù)據(jù)包大小為500Byte。使用不同算法發(fā)送50 個數(shù)據(jù)報。設(shè)α為1，β為2。節(jié)點發(fā)送大小為k比特的信息給相距為d的目標節(jié)點時的能量消耗如下式所示

式中：E1——發(fā)送或接收的功耗，設(shè)為50nJ／bit；a，b 為這兩種情況下單位功率放大所需能量，設(shè)為100pJ／bit／m2。天線類型為全向。

圖4是在100×100m2區(qū)域中分布120個節(jié)點重復實驗五次的時候所取得的平均結(jié)果。從中可以看出存活節(jié)點數(shù)隨時間變化的關(guān)系，在算法ARAWSN，MACO，ELACO，SACACO 下，節(jié)點隨著時間的增長逐漸減少；并可以看出執(zhí)行算法ARAWSN 時，網(wǎng)絡(luò)節(jié)點消亡的最快，SACACO算法消亡的最慢，從而可以得知SACACO 算法有著更長的網(wǎng)絡(luò)生存時間。

圖4 存活節(jié)點數(shù)隨時間的變化

圖5是區(qū)域中分布120個節(jié)點的時候執(zhí)行各種算法所得到的結(jié)果，從圖中可以看出SACACO 和ELACO 算法建立路徑所消耗的能量差距不大，MACO 算法消耗的能量最大。這里可以說明SACACO 算法不僅可以增加網(wǎng)絡(luò)的生存時間，而且在路徑生成消耗上也有比較好的性能。

圖5 不同算法生成路徑所消耗能量

圖6可以看出算法SACACO 算法有著較高的路徑生成效率。這樣可以提高網(wǎng)絡(luò)對事件的反應(yīng)速度，從而滿足一定的對時間有一定要求的需求。

圖7是使用不同算法成功發(fā)送50個數(shù)據(jù)包時節(jié)點的能量效率仿真結(jié)果。從中可以看出，使用ARAWSN，MACO，ELACO，SACACO 算法時節(jié)點能量效率總趨勢依次增大。

綜上所述，SACACO 算法綜合考慮了傳感器節(jié)點的周圍能量密度情況，設(shè)置了比較合理的前向候選區(qū)域。使用蟻群算法能夠更加智能的搜索和優(yōu)化路由路徑，有效的均衡了全網(wǎng)的能量消耗，增加了網(wǎng)絡(luò)的生存時間。

圖6 使用不同算法時的路徑成功率

圖7 使用不同算法時節(jié)點的效率

4 結(jié)束語

提出了一種新的基于蟻群算法的搜索區(qū)域受限的WSN路由協(xié)議SACACO。SACACO 算法設(shè)定了更加合適的前向候選區(qū)域，使得節(jié)點在選擇下一跳節(jié)點的時候只能在前向候選節(jié)點集合中進行選擇，從而限制了蟻群算法的尋路范圍，減少了尋路過程中的能量消耗；SACACO 算法同時考慮了網(wǎng)絡(luò)能量的分布情況，在選擇節(jié)點的時候考慮節(jié)點周圍能量的分布情況，使得最后形成的路徑所經(jīng)過的地方是能量相對比較密集的地方，從而有效地延長了網(wǎng)絡(luò)的使用壽命。

［1］ZHAO Yonghui，SHI Haoshan.An energy－balanced routing algorithm in wireless sensor networks［J］.（Engineering Sciences），2011，43 （2）：103－108 （in Chinese）. ［趙永輝，史浩山.一種無線傳感器網(wǎng)絡(luò)能量均衡路由算法 ［J］.四川大學學報 （工程科學版），2011，43 （2）：103－108.］

［2］Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey ［J］.Computer Networks，2008，52 （12）：2292－2330.

［3］WU Chengdong，CHEN Fei.A LEACH－based routing protocol for wireless sensor network to optimize QoS ［J］.Northeastern University：Natural Science Edition，2009，30 （8）：1091－1094 （in Chinese）.［吳成東，陳飛.優(yōu)化Qos的基于LEACH的無線傳感器網(wǎng)絡(luò)路由協(xié)議 ［J］.東北大學學報：自然科學版，2009，30 （8）：1091－1094.］

［4］Conti M，F(xiàn)rancesco M D，Passarella A，et al.Energy conservation in wireless sensor networks：A survey ［J］.Ad Hoc Networks，2009，7 （3）：537－568.

［5］LIN Kai，ZHAO Hai，YIN Zhenyu，et al.A clustering Hierarchy arithmetic based on Energy prediction for wireless sensor network ［J］.Acta Electronica Sinica，2008，36 （4）：824－828 （in Chinese）.［林凱，趙海，尹震宇，等.一種基于能量預(yù)測的無線傳感器網(wǎng)絡(luò)分簇算法 ［J］.電子學報，2008，36 （4）：824－828.］

［6］Dorigo M，Birattari M.Ant colony optimization ［M］／／Encyclopedia of Machine Learning.Springer US，2010：36－39.

［7］Donati A V，Montemanni R，Casagrande N，et al.Time dependent vehicle routing problem with a multi ant colony system［J］.European Journal of Operational Research，2008，185（3）：1174－1191.

［8］Wang W，Wang Y，Li X Y，et al.Efficient interference－aware TDMA link scheduling for static wireless networks［C］／／Proceedings of the 12th Annual International Conference on Mobile Computing and Networking.ACM，2006：262－273.

［9］LIANG Huawei，CHEN Wanming，LI Shuai，et al.ACObased routing algorithm for wireless sensor networks［J］.Sensor Technology，2007，20 （11）：2450－2455 （in Chinese）.［梁華為，陳萬名，李帥，等.一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算 法 ［J］.傳感器技術(shù)學報，2007，20 （11）：2450－2455.］

［10］LI Jianbing，ZHENG Wei.New multiple ant optimization routing algorithm for wireless sensor network ［J］.Computer Applications，2009，26 （7）：2686－2687 （in Chinese）.［黎劍兵，鄭巍.無線傳感器網(wǎng)絡(luò)多種群蟻群優(yōu)化路由算法 ［J］.計算機應(yīng)用研究，2009，26 （7）：2686－2687.］

［11］WANG Xiaoming，AN Xiaoming.An energy and location aware ACO based routing algorithm for wireless sensor networks［J］.Acta Electronica Sinica，2010，38 （8）：1763－1769 （in Chinese）.［王小明，安小明.具有能量和位置意識基于ACO的WSN路由算法［J］.電子學報，2010，38（8）：1763－1769.］