張 波，安 樂，湯一波

（遼寧大學(xué) 信息學(xué)院，遼寧 沈陽110036）

0 引 言

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

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

1 相關(guān)工作

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

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

2 SACACO 路由算法

2.1 算法思想

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

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

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

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

2.2 問題描述

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

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

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

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

（4）無線鏈路是對(duì)稱的。

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

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

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

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

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

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

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

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

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

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

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

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

圖3 路由空洞解決方法

前向螞蟻k從源節(jié)點(diǎn)出發(fā)，到達(dá)下一個(gè)節(jié)點(diǎn)的時(shí)候按式（4）進(jìn)行局部信息素的更新

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

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

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

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

SACACO 算法的具體步驟如下：

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

圖6 使用不同算法時(shí)的路徑成功率

圖7 使用不同算法時(shí)節(jié)點(diǎn)的效率

4 結(jié)束語

提出了一種新的基于蟻群算法的搜索區(qū)域受限的WSN路由協(xié)議SACACO。SACACO 算法設(shè)定了更加合適的前向候選區(qū)域，使得節(jié)點(diǎn)在選擇下一跳節(jié)點(diǎn)的時(shí)候只能在前向候選節(jié)點(diǎn)集合中進(jìn)行選擇，從而限制了蟻群算法的尋路范圍，減少了尋路過程中的能量消耗；SACACO 算法同時(shí)考慮了網(wǎng)絡(luò)能量的分布情況，在選擇節(jié)點(diǎn)的時(shí)候考慮節(jié)點(diǎn)周圍能量的分布情況，使得最后形成的路徑所經(jīng)過的地方是能量相對(duì)比較密集的地方，從而有效地延長了網(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］.四川大學(xué)學(xué)報(bào) （工程科學(xué)版），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］.東北大學(xué)學(xué)報(bào)：自然科學(xué)版，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ù)測(cè)的無線傳感器網(wǎng)絡(luò)分簇算法 ［J］.電子學(xué)報(bào)，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ù)學(xué)報(bào)，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］.計(jì)算機(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）.［王小明，安小明.具有能量和位置意識(shí)基于ACO的WSN路由算法［J］.電子學(xué)報(bào)，2010，38（8）：1763－1769.］