張文柱,孔維鵬,高 鵬,孫瑞華
(西安建筑科技大學 信息與控制工程學院,西安 710055)
無線傳感網(wǎng)絡(luò)(wireless sensor network,WSN)通常由大量相對較小的節(jié)點組成,每個節(jié)點配備有傳感設(shè)備。大多數(shù)傳感網(wǎng)絡(luò)使用無線通信,節(jié)點通常由電池供電,且不可更換,一旦中斷,將對網(wǎng)絡(luò)的傳輸造成很大影響。WSN由傳感器節(jié)點和匯聚節(jié)點組成。傳感器節(jié)點負責收集和轉(zhuǎn)發(fā)數(shù)據(jù),匯聚節(jié)點在本地分析數(shù)據(jù)并將數(shù)據(jù)轉(zhuǎn)發(fā)到基站(BS)。無線傳感網(wǎng)絡(luò)與有線傳感網(wǎng)絡(luò)的關(guān)鍵區(qū)別在于,無線傳感網(wǎng)絡(luò)中的傳感器節(jié)點僅依賴于自己的電池,因此功率、能耗、計算能力、儲存資源都是有限的[1]。所以如何降低網(wǎng)絡(luò)的能量消耗,延長網(wǎng)絡(luò)生命周期成為該領(lǐng)域的重中之重。
針對上述問題,已經(jīng)有許多專家學者對目前的路由算法進行改進,文獻[2]提出的ARA算法是最早將蟻群算法應(yīng)用到移動自組織網(wǎng)絡(luò)中,該算法減少了數(shù)據(jù)包類型,在節(jié)點信息素低于某個值時自動進入休眠狀態(tài)以減少不必要的能量消耗,但是該方法會產(chǎn)生冗余節(jié)點,增加算法的復(fù)雜度并產(chǎn)生無關(guān)路徑。隨后提出的IARA算法考慮到了鄰域冗余節(jié)點并進行篩選,并用角度和距離來限制節(jié)點間的傳輸,避免了無關(guān)路徑的產(chǎn)生,但是該算法在路徑?jīng)Q策時,增加了算法復(fù)雜度,收斂速度較慢。文獻[3]提出了基于改進蟻群算法的分簇路由協(xié)議LEACH-VA,它利用幾何關(guān)系將螞蟻的數(shù)據(jù)包結(jié)構(gòu)、信息素更新規(guī)則進行改進,并在簇內(nèi)運用多跳的路由傳輸方式,而且前向螞蟻具有收集跳數(shù)和所經(jīng)過路徑對其他路徑的負反饋條件,綜合多因素來調(diào)整路由,得到全局最優(yōu)解。但該算法存在頻繁的動態(tài)分簇導致能量消耗過多。文獻[4]提出一種基于蟻群算法的能量有效路由協(xié)議EEABR,將節(jié)點平均剩余能量和跳數(shù)加入到信息素增量中進行信息素更新。但是在信息素更新過程中,離Sink節(jié)點較近或者一些節(jié)點分布密集的區(qū)域存在頻繁的數(shù)據(jù)傳輸,僅僅靠增量公式的計算更新信息素不夠精確而且會消耗更多的能量。而且由于數(shù)據(jù)包中只有兩條節(jié)點的信息,容易形成環(huán)路,不利于能量的均衡。IEEABR針對EEABR存在的問題進行改進,分別定義前向螞蟻和后向螞蟻的數(shù)據(jù)結(jié)構(gòu);啟發(fā)函數(shù)中加入鄰域節(jié)點的剩余能量,增加了高能量節(jié)點成為下一跳節(jié)點的概率;前向螞蟻和后向螞蟻采用不同的信息素更新,使后續(xù)螞蟻優(yōu)先選擇剩余能量較高的節(jié)點。但是由于信息素的更新是一個正反饋過程,這會導致大量螞蟻聚集在最佳路徑導致節(jié)點能量消耗過高而死亡,而非最優(yōu)路徑上的信息素濃度逐漸降低,出現(xiàn)荒廢路徑且有充足能量。
綜合考慮多種路由算法,本文提出一種新的基于改進蟻群算法的路由算法。在網(wǎng)絡(luò)結(jié)構(gòu)方面,加入網(wǎng)絡(luò)分隔帶和搜索角,并結(jié)合節(jié)點剩余能量,共同限制下一跳節(jié)點的轉(zhuǎn)移概率;同時改進啟發(fā)函數(shù),加入能量影響因子,增強算法尋優(yōu),避免陷入局部最優(yōu);在信息素更新方面,引入閾值機制并設(shè)立最優(yōu)路徑權(quán)重值來尋找最優(yōu)路徑。
為了簡化無線傳感網(wǎng)絡(luò)的節(jié)點,對每個節(jié)點進行以下假設(shè):
假設(shè)監(jiān)測區(qū)域為一個二維平面區(qū)域,N個傳感器節(jié)點隨機分布在該區(qū)域,且只有一個基站。任何一個節(jié)點都能被監(jiān)測到,并且擁有唯一的ID號:1,2,3,4,5,n,同時與Sink節(jié)點構(gòu)成一個集合N={n1,n2,n3…,sink}。每個傳感器節(jié)點的通信半徑、感知半徑、初始能量都是相同的,節(jié)點被部署后,網(wǎng)絡(luò)拓撲結(jié)構(gòu)將不再發(fā)生變化。在信息傳輸過程中,傳感器節(jié)點與Sink節(jié)點將不會有能量補充,且Sink節(jié)點具有無限的能量。用于發(fā)送和接收信息的的無線鏈路是對稱的[5-6]。
無線傳感網(wǎng)絡(luò)可以被看成一個賦權(quán)無向圖,由式(1)表示出:
G=
(1)
其中:V表示無線傳感網(wǎng)絡(luò)的節(jié)點集合,E表示無線傳感網(wǎng)絡(luò)的通信鏈路集合。
V可以具體表示為:
V={v1,v2,…,vn,vsink}
(2)
上式中,表示無線傳感網(wǎng)絡(luò)的Sink節(jié)點,其他節(jié)點用表示。
E可以具體表示為:
E={e1,e2,e3,…,en}
(3)
假設(shè)無線傳感網(wǎng)絡(luò)的節(jié)點有效傳輸距離為,代表傳感器節(jié)點a、b之間的距離,E將進一步表示為:
E={ei|D(va,vb)≤R0,va,vb∈V}
(4)
在無線傳感網(wǎng)絡(luò)中通過以下公式來判斷兩個節(jié)點之間的有效鏈路是否存在,可表示為:
(5)
式(5)中,當i,j之間存在在有效鏈路時表示為1,否則表示為0。
對于能量有限的無線傳感網(wǎng)絡(luò),節(jié)點能耗主要集中在節(jié)點的發(fā)送和接收狀態(tài)下,WSN的路由算法設(shè)計與信道能量損失模型密切相關(guān)[7],因此本文采用的能耗模型如下。
其中,節(jié)點i到節(jié)點j傳輸數(shù)據(jù)過程中消耗能量的具體公式如下:
(6)
其中:d是通信距離,k的單位bit,是節(jié)點發(fā)送數(shù)據(jù)包的長度;Eelec指收發(fā)電路的功耗系數(shù),εfs和εamp分別是自由空間和多徑衰減信道模型功率放大器的能耗系數(shù);d0為閾值,由以下公式表示:
(7)
節(jié)點收發(fā)1 kb數(shù)據(jù)傳感器節(jié)點的能耗為:
Erv(k,d)=k*Eelec
(8)
由以上公式可以看出,數(shù)據(jù)傳輸過程中消耗的能量主要由傳輸距離和經(jīng)過的節(jié)點數(shù)目決定。
蟻群算法(ant colony algorithm,ACA)是通過觀察自然界中螞蟻的覓食行為而啟發(fā)產(chǎn)生的群智能算法[8]。大量的螞蟻會從不同的路徑去尋找食物,尋徑過程中每只螞蟻會釋放信息素來記錄走過路徑的信息,后續(xù)的螞蟻會更傾向于選擇信息素濃度較高的路徑,這樣源節(jié)點和目的節(jié)點之間的較短路徑由于經(jīng)過的螞蟻數(shù)量較多會有更高的信息素濃度,所以經(jīng)過大量的螞蟻尋徑,就會產(chǎn)生一條最優(yōu)路徑。該算法所具有的自組織性、并行性和正反饋性適用于在無線傳感網(wǎng)絡(luò)中尋找最佳路由。
在無線傳感網(wǎng)絡(luò)中,假設(shè)節(jié)點的個數(shù)為n,螞蟻的個數(shù)為m,采用蟻群算法對WSN進行優(yōu)化,主要算法步驟如下。
1)假設(shè)當前尋徑螞蟻為k,此時螞蟻正位于i節(jié)點,它轉(zhuǎn)移到下一節(jié)點j的概率為Pij(t),公式如下:
(9)
(10)
其中:dij表示節(jié)點i和節(jié)點j之間的距離。
2)當螞蟻k完成覓食之后,需要更新它所經(jīng)過路徑的信息素濃度,用公式可以表示為:
τij(t+1)=τij(t)*(1-ρ)+Δτij(t)
(11)
(12)
上式中,ρ表示信息素的蒸發(fā)系數(shù),且ρ∈[0-1],1-ρ則表示信息素持久性系數(shù),信息素的濃度會隨著時間的推移不斷蒸發(fā),從而調(diào)節(jié)路徑上的信息素濃度平衡。其中,信息素濃度更新采用蟻周系統(tǒng)[9](Ant-cycle System),是在螞蟻到達目的后進行信息素濃度的調(diào)整,即
(13)
式中,Q為常數(shù),Lk表示螞蟻k在此次尋徑過程中的路徑總長度。
基礎(chǔ)蟻群算法的局部尋優(yōu)能力較強,但全局搜索能力較差。當算法運行一段時間后,會出現(xiàn)停滯不前,且搜索速度也會相應(yīng)的降低。為了提升最佳路徑的搜尋速度,在其已有優(yōu)勢的基礎(chǔ)上進行改進,來獲得性能更好的蟻群算法。
2.2.1 網(wǎng)絡(luò)分隔帶和搜索角
經(jīng)典蟻群算法里螞蟻的下一跳由轉(zhuǎn)移概率函數(shù)決定,這種概率取決于下一跳節(jié)點對螞蟻的啟發(fā)作用、信息素濃度[10]。信息素會隨著時間的增加而慢慢揮發(fā),為了及時利用這些信息素,降低網(wǎng)絡(luò)延遲造成的轉(zhuǎn)移概率不確定性,在蟻群路由優(yōu)化算法中提出網(wǎng)絡(luò)分隔帶的概念[11],使尋徑螞蟻能夠有目的地尋找下一跳節(jié)點,其原理如圖1所示。
圖1 網(wǎng)絡(luò)分隔帶原理圖
假設(shè)處于n層的節(jié)點i為源節(jié)點,它在選擇下一跳節(jié)點時,只能從當前層n或者鄰近層n+1、n-1內(nèi)的節(jié)點進行選擇。i的鄰近節(jié)點只有A,B,C,D,E,F(xiàn),和j等節(jié)點。按照以上規(guī)則,i的下一跳節(jié)點只能從鄰近層的節(jié)點中選取,如A,B,C,D,E,F(xiàn)和j等而不能選擇G節(jié)點。這樣能夠使尋徑螞蟻盡可能的向Sink節(jié)點靠攏,減少不必要的跳數(shù)和消耗的能量。
然而,只依賴網(wǎng)絡(luò)分隔帶螞蟻無法精確的選擇最優(yōu)路徑,因為在下一跳節(jié)點選取的時候并沒有考慮該節(jié)點是否靠近Sink節(jié)點,所以有可能選擇與Sink節(jié)點相反方向的節(jié)點。所以在網(wǎng)絡(luò)分隔帶的基礎(chǔ)上,提出搜索角的概念。其原理如圖2所示。
圖2 搜索角原理圖
圖2中,采用源節(jié)點i到Sink節(jié)點的連線與源節(jié)點i到下一跳節(jié)點連線的夾角,與距離因子共同限制下一跳的選擇,來選擇最佳路徑方向。夾角通常限制在,角度越小,則尋徑螞蟻從源節(jié)點到目的節(jié)點之間的距離越接近直線,這樣更容易找到最優(yōu)路徑,能量消耗也更少。從圖中可以看出θ1最小,那么j節(jié)點作為下一跳節(jié)點的概率就更大。
2.2.2 改進啟發(fā)函數(shù)
基本蟻群算法早期用來解決旅行商(TSP)問題,僅僅考慮節(jié)點之間的距離因素[12]。但是將該算法應(yīng)用到無線傳感網(wǎng)絡(luò)中,不僅要考慮距離因素,傳輸方向和剩余能量也要考慮到其中,需要綜合以上因素來改進蟻群算法。本文將重新定義新的啟發(fā)函數(shù),如下公式所示:
(14)
其中:R為節(jié)點通信半徑;ei為節(jié)點i的剩余能量;Ei為節(jié)點i的初始能量;ej為節(jié)點j的剩余能量;Ej為節(jié)點j的初始能量;θ是節(jié)點i到Sink節(jié)點的連線與節(jié)點j到Sink節(jié)點的連線的夾角;γ1、γ2、γ3分別代表上式中三項的權(quán)重值。θ角的定義由2.2.1給出,如圖2所示,搜素角越小,下一跳節(jié)點越接近Sink節(jié)點,避免了節(jié)點回旋,產(chǎn)生不必要的路徑。
上式中,改進的啟發(fā)函數(shù)不僅把下一跳節(jié)點的能量考慮進去,同時也考慮了發(fā)送節(jié)點的能量,除此之外,將發(fā)送節(jié)點的剩余能量與節(jié)點之間的傳輸距離相結(jié)合,共同限制下一跳。當節(jié)點i的剩余能量很小的時候,距離節(jié)點i更近的點將會有更高的概率被選中為下一跳節(jié)點,j節(jié)點的剩余能量大小和θ角對啟發(fā)函數(shù)的影響力就會減小。由于γ2和γ3的設(shè)置值不同,當節(jié)點i的剩余能量較多時,j節(jié)點的剩余能量和θ角的大小對啟發(fā)函數(shù)的影響力會更高。在無線傳感網(wǎng)絡(luò)工作的初始階段,各個節(jié)點的初始能量都很充足,能量因素對節(jié)點的選擇影響較小,改進后的啟發(fā)函數(shù)對尋徑螞蟻進行方向限制,減少經(jīng)過的節(jié)點數(shù)目,降低傳輸消耗的能量。
2.2.3 改進能量影響因子
基礎(chǔ)蟻群算法中,尋徑螞蟻在確定下一跳時會考慮信息素濃度和路徑啟發(fā)因子,但是沒有將節(jié)點的能量對路由選取的影響考慮進去,這樣會使部分關(guān)鍵節(jié)點過早消耗完能量,降低網(wǎng)絡(luò)性能,縮短網(wǎng)絡(luò)生命周期[13],因此在基礎(chǔ)蟻群算法中,加入能量影響因子ω,公式如下:
(15)
上式中,ω表示了節(jié)點能量對轉(zhuǎn)移概率的影響,E0、Ej分別代表了節(jié)點的初始能量和當前剩余能量。由公式可知,節(jié)點當前的剩余能量越高,能量影響因子就小,隨著網(wǎng)絡(luò)的運行,節(jié)點能量逐步被消耗,能量影響因子變大,螞蟻下一跳受能量因素影響的概率也逐步變大。
把能量因子引入到轉(zhuǎn)移概率公式中去,如下式所示:
(16)
(17)
以上兩個公式分別是先驗路徑和變異路徑選擇的概率公式,其中,α、β、γ分別代表信息素濃度、啟發(fā)函數(shù)、能量影響因子的權(quán)重系數(shù),系數(shù)越大說明下一跳轉(zhuǎn)移的概率受該項的影響越大。其中,q是尋徑螞蟻在選擇下一跳節(jié)點之前產(chǎn)生的一個隨機數(shù),且q∈(0,1]q0∈[0,1]。當q≤q0時,則選擇[τij(t)]α[ηij(t)]β[ωis(t)]γ中最大的節(jié)點作為下一跳,若q>q0,則按照公式(17)進行下一跳的選擇。對于α、β、γ的取值,應(yīng)該綜合考慮,不能有一個因子為零,否則該算法將無法收斂,太大或太小都會影響算法的收斂速度,而且更容易陷入局部最優(yōu),當前兩項的值較大時,可以酌情降低其系數(shù),將轉(zhuǎn)移重心放在能量因子上,權(quán)衡整個網(wǎng)絡(luò)的每個影響因素。
2.2.4 改進信息素更新規(guī)則
在經(jīng)典蟻群算法中,每個節(jié)點的初始信息素濃度均為零,當前向螞蟻從源節(jié)點到目的節(jié)點完成信息傳輸時,目的節(jié)點也就是Sink節(jié)點會根據(jù)尋徑螞蟻所攜帶的信息計算螞蟻經(jīng)過的不同路徑長度和路徑信息素濃度,把結(jié)果反饋給后向螞蟻,完成信息素的更新。當后向螞蟻回到源節(jié)點時,算法完成一次路徑尋優(yōu),后向螞蟻消失,同時產(chǎn)生新的前向螞蟻進行下一輪的路徑尋優(yōu),如此循環(huán)該過程,直至達到算法設(shè)置的最大迭代次數(shù),找到最優(yōu)路徑[14]。
但是由于經(jīng)典蟻群算法的信息素更新是一個正反饋過程,當前向螞蟻搜索到最短路徑后,那么該條路徑上的信息素濃度會增高,會有更多的螞蟻選擇該路徑,從而造成最佳路徑擁堵,使路徑上的節(jié)點過早消耗完能量而死亡,而非最佳路徑上的信息素濃度逐漸降低,隨著算法的進行,導致路徑荒廢但節(jié)點能量卻很充足[15-18]。此時算法將會陷入局部最優(yōu),導致算法出現(xiàn)過早停滯,為了解決此問題,本文將建立閾值機制來影響信息素濃度的大小,且同時考慮路徑的長度,跳數(shù)和節(jié)點的剩余能量等因素。具體如下所示:
(18)
(19)
參數(shù)τmax表示信息素的閾值,Y代表信息素強度,m是螞蟻的總個數(shù),Lm表示第m只螞蟻走過的路徑,ρ是信息素蒸發(fā)系數(shù),ρ∈[0,1]。每次尋優(yōu)過后,每只尋徑螞蟻各自對應(yīng)著一條走過的路徑,本文將提出一個能夠選擇最佳路徑的權(quán)重公式計算所有尋徑螞蟻走過的路徑,該公式如下:
(20)
本文提出的改進蟻群算法的實現(xiàn)步驟如下。
Step1:初始化各項參數(shù)。在t=0時刻,設(shè)置節(jié)點初始能量為E0,信息素濃度τij,迭代次數(shù)為N=0,運行最大迭代次數(shù)為Nmax。
Step2:把m只螞蟻隨機部署在n個節(jié)點,直至遍歷完這n個節(jié)點,每只螞蟻都有自己的禁忌表tabuk,且每只螞蟻的tabuk里放置不同的初始地點。
Step3:迭代次數(shù)按照N=N+1進行。
Step4:尋徑螞蟻遵循K=K+1進行路徑尋優(yōu)。
Step5:根據(jù)網(wǎng)絡(luò)分隔帶、搜索角和節(jié)點剩余能量等因素,尋找下一跳節(jié)點的最佳路徑范圍。若產(chǎn)生的隨機數(shù)q≤q0,則按照下一跳節(jié)點概率公式(16)進行節(jié)點j轉(zhuǎn)移;否則按照公式(17)轉(zhuǎn)移,其中j∈allowedk。
Step6:更新節(jié)點的禁忌表tabuk。
Step7:如果k Step8:利用公式(20)計算走過路徑對應(yīng)的最優(yōu)路徑度量值。 Step9:繼續(xù)執(zhí)行Step4—Step8,直到m只螞蟻到達Sink節(jié)點。 Step10:每輪迭代結(jié)束后,比較各路徑上的最優(yōu)路徑度量值,將最大返回值所對應(yīng)的路徑當成最優(yōu)路徑,并利用公式(18)、(19)進行信息素更新。 Step11:繼續(xù)執(zhí)行Step2~Step10,直到迭代次數(shù)N Step12:輸出最優(yōu)路徑。 改進蟻群算法實現(xiàn)的流程圖如圖3所示。 圖3 改進蟻群算法流程圖 本文改進的蟻群算法的仿真實驗選擇在Matlab2014b環(huán)境中進行,并與IEEABR算法,和IARA算法進行對比。為了確保仿真結(jié)果的穩(wěn)定性與可靠性,取多次仿真結(jié)果的平均值。分別從路徑的平均跳數(shù)、節(jié)點平均能量消耗、網(wǎng)絡(luò)生命周期等3個方面進行對比分析。仿真參數(shù)如表1所示,仿真環(huán)境設(shè)置為100 m*100 m的區(qū)域,隨機分布150個節(jié)點。 1)路徑平均跳數(shù): 路徑平均跳數(shù)顯示了算法的尋優(yōu)能力,圖4顯示了IARA算法、IEEABR算法和改進的蟻群算法的平均路徑條數(shù)的趨勢對比圖。隨著迭代次數(shù)的增加,平均跳數(shù)漸漸減小并趨于穩(wěn)定,從圖中可以看出,改進蟻群算法的平均跳數(shù)始終低于IARA和IEEABR算法,在迭代初始階段,IEEABR算法和IARA算法的跳數(shù)降低較為明顯,且收斂速度也相對較快,但是最終的收斂跳數(shù)維持在一個較高的水平,這樣對網(wǎng)絡(luò)資源的占用會更高。而本文提出的改進蟻群算法的最終收斂跳數(shù)則明顯低于以上兩種算法,這說明該算法能夠減少丟包率,提高網(wǎng)絡(luò)傳輸效率,減少路徑堵塞。 表1 仿真參數(shù)設(shè)置 圖4 路徑平均跳數(shù)的對比 2)節(jié)點平均能量消耗: 網(wǎng)絡(luò)節(jié)點的平均能量消耗直接影響了整個網(wǎng)絡(luò)的生命周期,節(jié)點能量消耗越小,則網(wǎng)絡(luò)生命周期越長。圖5顯示了3種算法的節(jié)點平均能量消耗隨著仿真時間變化的仿真結(jié)果。從圖中可以看出,本文提出的改進蟻群算法隨著仿真的進行,平均能量消耗始終低于EEIBR和AIRA算法,這得益于本算法考慮到節(jié)點能量對轉(zhuǎn)移概率的影響,將節(jié)點之間的距離與剩余能量相結(jié)合,同時限制了傳輸方向,避免節(jié)點回旋傳輸,產(chǎn)生與最佳路徑偏差較遠的路徑。 圖5 節(jié)點平均能耗隨的對比 3)網(wǎng)絡(luò)生命周期: 仿真實驗將第一個網(wǎng)絡(luò)節(jié)點的死亡時間定義為網(wǎng)絡(luò)周期,通過增加節(jié)點數(shù)量,來對比各算法的網(wǎng)絡(luò)生命周期。如圖6所示,當網(wǎng)絡(luò)節(jié)點數(shù)量相同時,EEABR和IARA算法的第一個節(jié)點死亡時間總是低于本文所提出的算法,這說明改進的蟻群算法能夠有限的延長網(wǎng)絡(luò)生命周期。這是因為該算法中同時考慮節(jié)點剩余能量、路徑長度和跳數(shù),同時建立一個能夠選擇最優(yōu)路徑的權(quán)重公式去更新信息素,避免了冗余節(jié)點的產(chǎn)生,延長了網(wǎng)絡(luò)生命周期。 圖6 網(wǎng)絡(luò)生命周期的對比 本文在經(jīng)典蟻群算法的基礎(chǔ)上,提出改進的蟻群算法來解決無線傳感網(wǎng)絡(luò)的路由能耗問題,從網(wǎng)絡(luò)結(jié)構(gòu)、啟發(fā)函數(shù)、能量因子、信息素更新規(guī)則等方面進行改進,解決蟻群算法在無線傳感網(wǎng)絡(luò)中出現(xiàn)局部最優(yōu)、能量消耗過多、節(jié)點過早死亡等問題。仿真實驗表明,改進后的蟻群算法能夠有效均衡能量消耗,提高節(jié)點存活數(shù)量,延長了網(wǎng)絡(luò)生命周期。3.2 改進蟻群算法流程圖
4 實驗仿真與結(jié)果分析
5 結(jié)束語