王 恭, 孫銘陽, 孫匯陽, 滕子銘
(1.東北電力大學(xué) 自動化工程學(xué)院,吉林 吉林 132012; 2.北京電子科技學(xué)院 密碼科學(xué)與技術(shù)系,北京 100070; 3.吉林大學(xué) 通信工程學(xué)院,吉林 長春 130012)
無線傳感器網(wǎng)絡(luò)(wireless sensor network,WSN)是由一系列具有感知、計算和無線通信能力的節(jié)點組成的無線網(wǎng)絡(luò),可以使用戶對特定的環(huán)境和場合進行數(shù)據(jù)采集、處理和傳輸。在實際的應(yīng)用當(dāng)中,無線傳感器網(wǎng)絡(luò)受到其中各節(jié)點的計算能力、無線通訊能力、儲存能力和能量供給能力等諸多限制,這就要求各個節(jié)點在傳輸信息時,要充分合理地利用有限的能量,提高能量的使用效率,從而延長無線傳感器網(wǎng)絡(luò)的生存時間。綜上所述,選取合適的路由算法來提高節(jié)點在信息傳輸?shù)哪芰渴褂眯?,成為近年來無線傳感器網(wǎng)絡(luò)的重要研究內(nèi)容。
蟻群算法是由Dorigo等[1]提出的仿生尋優(yōu)算法,該算法具有正反饋和較強的魯棒性等特點,在解決路徑規(guī)劃問題時效果較好?;谙伻核惴ǖ穆酚蓞f(xié)議被提出后,引起了各方學(xué)者的廣泛關(guān)注。
Gravett等[2]提出的DAR被動路由算法,限制前向螞蟻包只使用信息素濃度作為選擇下一跳節(jié)點的概率,后向螞蟻在回到源節(jié)點的過程中釋放信息素濃度為常量,從而節(jié)省在傳輸中損耗的能量,達到較小網(wǎng)絡(luò)開銷的目的,但因為后向螞蟻更新的信息素為非真實值,導(dǎo)致選擇下一跳概率不準(zhǔn)確。Bean等[3]提出了一種ARA路由算法,將各節(jié)點中的信息素濃度儲存在路由表中,通過多次迭代不斷更新在各節(jié)點中的信息素濃度,從而影響螞蟻包在選擇下一跳節(jié)點的概率。在該路由算法中,除匯聚節(jié)點以外,其余節(jié)點自身攜帶能量是有限的,當(dāng)數(shù)據(jù)包多次經(jīng)過某一節(jié)點時,節(jié)點因能量損耗會過早進入休眠狀態(tài),下一代螞蟻無法再次經(jīng)過該節(jié)點,因為其在選擇節(jié)點時收斂過于迅速,從全局的角度來看容易使得網(wǎng)絡(luò)陷入局部最優(yōu)。李憲強等[4]提出一種精英蟻群算法,將每一次算法迭代中最優(yōu)個體的信息素保留到下一代中以提高搜索效率,但是如果算法初期留存的信息素不夠具有代表性,會導(dǎo)致算法尋優(yōu)精度較差。
Maheshwari等[5]提出的LEACH低功耗自適應(yīng)集簇分層型路由算法,與傳統(tǒng)的通用多條協(xié)議相比,適用于低能耗網(wǎng)絡(luò),但該算法在一定程度上增加了算法復(fù)雜度,導(dǎo)致收斂速度較慢。Camilo等[6]提出的EEABR偽隨機路由算法采用偽隨機的方式來發(fā)現(xiàn)目標(biāo)路徑,通過預(yù)估下一跳節(jié)點剩余能量,來影響下一跳節(jié)點概率,可加快算法的收斂,并減小網(wǎng)絡(luò)開銷,但過快的收斂速度很容易使搜尋路徑陷入局部最優(yōu),從而影響了算法的準(zhǔn)確性。Sun等[7]提出的EEABR路由算法解決了原有蟻群算法在傳輸數(shù)據(jù)時對節(jié)點能量的過量損耗等問題,但沒有考慮因縮短螞蟻包存放的路徑信息,導(dǎo)致螞蟻包在傳輸過程中易生成蟻群環(huán)路的現(xiàn)象,從而導(dǎo)致節(jié)點多余的能量損耗。
為避免數(shù)據(jù)在節(jié)點間反復(fù)回傳,發(fā)生蟻群環(huán)路和信息素增量計算不準(zhǔn)確,導(dǎo)致節(jié)點能量開銷增大、影響網(wǎng)絡(luò)生命周期等問題,本文在EEABR算法的基礎(chǔ)上,提出了一種基于自適應(yīng)信息素蒸發(fā)系數(shù)的改進蟻群路由算法APECARA(adaptive pheromone evaporation coefficient based ant colony routing algorithm)。該算法在前向螞蟻數(shù)據(jù)包中添加生存時間、前向螞蟻數(shù)據(jù)包源地址和序列號,避免數(shù)據(jù)包回傳問題,有效削弱蟻群環(huán)路現(xiàn)象,同時改進原有算法的信息素公式,提高信息素公式準(zhǔn)確性,從而在延長網(wǎng)絡(luò)生命周期的同時,達到有效均衡無線傳感器網(wǎng)絡(luò)中各節(jié)點能量的目的[8-9]。
在WSN中,確定任意兩節(jié)點間是否存在有效鏈路[11]可以用式(1)表示:
(1)
假設(shè)在WSN中只存在唯一匯聚節(jié)點z,z∈V,源節(jié)點表示為w∈ {V- {z}}。
EEABR算法[6]將優(yōu)化的重點放在如何降低節(jié)點能量消耗,通過減少節(jié)點存儲ID數(shù)量[12-13],降低節(jié)點能耗開銷,提升網(wǎng)絡(luò)壽命,以取得全局最優(yōu)解。
在無線傳感器網(wǎng)絡(luò)中,每間隔一段時間在各個節(jié)點發(fā)出一個數(shù)據(jù)包,即前向螞蟻數(shù)據(jù)包k,其訪問過的節(jié)點都會以節(jié)點標(biāo)識的形式儲存在鄰居列表中。前向螞蟻數(shù)據(jù)包k從源節(jié)點出發(fā),更新沿途經(jīng)過路徑和節(jié)點的信息素濃度,最終到達匯聚節(jié)點。匯聚節(jié)點接收到數(shù)據(jù)包后,利用信息素公式并把計算后的信息素通過儲存在后向螞蟻數(shù)據(jù)包中的方式,將數(shù)據(jù)傳送回源節(jié)點。通過一次完整的螞蟻包收發(fā)過程,標(biāo)志著源節(jié)點到匯聚節(jié)點的信息素濃度更新完成。
前向螞蟻選擇下一跳節(jié)點的概率為
(2)
式中:Pk(r,s)為前向螞蟻數(shù)據(jù)包k在r節(jié)點時選擇s節(jié)點作為下一跳節(jié)點的概率;T(r,s)為儲存在節(jié)點r和節(jié)點s路徑上的信息素濃度,被儲存在鄰居列表中;Mk為螞蟻數(shù)據(jù)包k當(dāng)前經(jīng)過所有節(jié)點的集合;E(u)為節(jié)點u的可見性函數(shù);E(s)為節(jié)點s的可見性函數(shù),即
(3)
式中:Eini為節(jié)點初始能量值;es為節(jié)點實際能量值,當(dāng)節(jié)點s損耗的能量越大,節(jié)點s作為下一跳節(jié)點的概率越低。
當(dāng)匯聚節(jié)點接收到前向螞蟻數(shù)據(jù)包后,隨即生成后向螞蟻數(shù)據(jù)包,節(jié)點間的路徑信息素濃度Tk(r,s)按式(4)進行更新:
Tk+1(r,s)=(1-ρ)Tk(r,s)+ΔTk(r,s)。
(4)
式中:ρ為螞蟻包走過路徑上的信息素蒸發(fā)系數(shù);Tk(r,s)為螞蟻數(shù)據(jù)包k從節(jié)點r到節(jié)點s途徑路徑上的信息素濃度;ΔTk(r,s)為信息素增量。
EEABR路由算法計算信息素增量ΔTk(r,s)如式(5)所示:
(5)
在EEABR路由算法中,將螞蟻包分別定義為螞蟻數(shù)據(jù)包和Hello數(shù)據(jù)包。WSN中各個節(jié)點通過廣播Hello數(shù)據(jù)包建立和維護與之對應(yīng)的鄰居列表,利用螞蟻數(shù)據(jù)包傳輸數(shù)據(jù)和進行路徑優(yōu)化。本文提出的APECARA算法將在螞蟻數(shù)據(jù)包和節(jié)點鄰居列表中添加TTL(螞蟻數(shù)據(jù)包生存時間)、pkt_src(前向螞蟻數(shù)據(jù)包源地址)和seq(前向螞蟻數(shù)據(jù)包序列號),增加前向螞蟻數(shù)據(jù)包的序列號和源地址,可有效減少在傳輸數(shù)據(jù)時產(chǎn)生的蟻群環(huán)路效應(yīng);改進原有信息素蒸發(fā)系數(shù)和信息素增量公式,解決中繼節(jié)點因能量消耗,過早進入休眠的問題,提高網(wǎng)絡(luò)節(jié)點能量均衡性和路徑尋優(yōu)準(zhǔn)確性。
在無線傳感器網(wǎng)絡(luò)中,相鄰的幾個節(jié)點在傳輸螞蟻數(shù)據(jù)包時,同一數(shù)據(jù)在相同幾個節(jié)點傳輸多次,形成蟻群環(huán)路效應(yīng),嚴(yán)重影響了能量傳輸效率,造成不必要節(jié)點能量損耗。
圖1分別為兩種環(huán)路網(wǎng)絡(luò),節(jié)點A、D生成的數(shù)據(jù)包發(fā)生數(shù)據(jù)回傳現(xiàn)象,將被鎖定在局部網(wǎng)絡(luò)中,二者的剩余能量將遠低于WSN中其余節(jié)點平均能量,致使陷入環(huán)路的節(jié)點過早進入休眠狀態(tài),從而造成不必要的能量浪費,最終影響尋優(yōu)結(jié)果。
圖1 網(wǎng)絡(luò)環(huán)路Figure 1 Network loop
針對在WSN中出現(xiàn)的蟻群環(huán)路效應(yīng),本文通過對蟻群環(huán)路效應(yīng)的分析,重構(gòu)了前向螞蟻數(shù)據(jù)包包頭結(jié)構(gòu)和后向螞蟻數(shù)據(jù)包包頭結(jié)構(gòu)。添加前向螞蟻數(shù)據(jù)包序列號seq和前向螞蟻數(shù)據(jù)包源地址pkt_src并對螞蟻數(shù)據(jù)包生存時間TTL進行約束。
前向螞蟻數(shù)據(jù)包包頭結(jié)構(gòu)由pkt_src、seq、E_s、E_m、Fd、Fromsrc_len和TTL等組成。其中pkt_src和seq分別為前向螞蟻數(shù)據(jù)包源地址和序列號,E_s為該數(shù)據(jù)包途徑中繼節(jié)點消耗的全部能量,E_m為該數(shù)據(jù)包經(jīng)過的所有中繼節(jié)點中損耗能量最低值,F(xiàn)d為該數(shù)據(jù)包經(jīng)過的節(jié)點數(shù),F(xiàn)romsrc_len[14-15]為該數(shù)據(jù)包走過路徑長度,TTL表示為該數(shù)據(jù)包的生存時間。TTL限制前向螞蟻數(shù)據(jù)包生存時間,每經(jīng)過一個節(jié)點TTL值減小1,當(dāng)TTL=0時,前向螞蟻數(shù)據(jù)包被放棄。通過添加pkt_src和seq到前向螞蟻數(shù)據(jù)包,可以有效避免數(shù)據(jù)在臨近節(jié)點反復(fù)回傳:在發(fā)生或?qū)⒁l(fā)生回傳現(xiàn)象時,螞蟻數(shù)據(jù)包頭中
鄰居列表通過Hello包維護和更新,用于記錄鄰居節(jié)點的信息,該表結(jié)構(gòu)由Neigh_addr、pheromone、Neigh_eng和hops組成。其中Neigh_addr為鄰居節(jié)點地址,pheromone為鄰居節(jié)點與當(dāng)前節(jié)點路徑上的信息素濃度,Neigh_eng為當(dāng)前鄰居節(jié)點所具有的能量,hops為前向螞蟻數(shù)據(jù)包途徑中繼節(jié)點的個數(shù)。
后向螞蟻數(shù)據(jù)包包頭結(jié)構(gòu)由pkt_src、E_i、E_a、pheromone、Next_haddr和TTL組成。其中E_i為節(jié)點初始能量,E_a為經(jīng)過路徑的平均能量。
在蟻群路由算法的一次迭代中,當(dāng)多個螞蟻數(shù)據(jù)包經(jīng)過同一節(jié)點時,該節(jié)點的路由數(shù)增加,伴隨著節(jié)點能量損耗加快,該節(jié)點會過早地進入休眠狀態(tài),同時加快了蟻群路由算法的收斂速度,最終影響到尋優(yōu)路線的準(zhǔn)確性,更容易獲得局部最優(yōu)解。
為使網(wǎng)絡(luò)中節(jié)點能量更加均衡,本文在式(4)的基礎(chǔ)上,改進了信息素蒸發(fā)系數(shù)ρ,將其重新定義為自適應(yīng)信息素蒸發(fā)系數(shù),并得到全新的信息素更新公式:
δ=ρ(1+lgn);
(6)
Tk+1(r,s)=(1-δ)Tk(r,s)+ΔTk(r,s)。
(7)
式中:δ為自適應(yīng)信息素蒸發(fā)系數(shù);n為節(jié)點路由數(shù),當(dāng)n增加時,自適應(yīng)信息素蒸發(fā)系數(shù)值δ增加,信息素持久函數(shù)(1-δ)減小,節(jié)點r到節(jié)點s的信息素濃度Tk(r,s)減小,從全局的角度來看,降低了下一次螞蟻數(shù)據(jù)包選擇該節(jié)點的概率,從而平衡WSN中節(jié)點能量,獲取更理想的全局最優(yōu)路徑。
在計算信息素增量ΔTk(r,s)時,現(xiàn)有的EEABR路由協(xié)議與基本的蟻群路由協(xié)議的區(qū)別在于傳統(tǒng)的路由算法在設(shè)計時,疏忽對各節(jié)點能量損耗的考量而更傾向于對路徑的尋優(yōu)。這樣設(shè)計的好處在于各節(jié)點剩余能量充沛時,往往可以得到最佳的路徑。但是在實際數(shù)據(jù)傳輸過程中使同一節(jié)點多次傳輸數(shù)據(jù)可能導(dǎo)致該節(jié)點能量過度損耗,會過早進入休眠狀態(tài),從而影響最終路徑的優(yōu)化。
(8)
(9)
Step1廣播Hello數(shù)據(jù)包。在APECARA路由算法運行的初期,各節(jié)點廣播Hello數(shù)據(jù)包來搭建臨近節(jié)點的相互關(guān)系,將每條相鄰路徑上的信息素濃度設(shè)置為1,為計算下一跳概率做好準(zhǔn)備。
Step2發(fā)送前向螞蟻數(shù)據(jù)包。由源節(jié)點向下一跳節(jié)點發(fā)送前向螞蟻數(shù)據(jù)包,該數(shù)據(jù)包每經(jīng)過一個中繼節(jié)點時都按式(2)計算下一跳中繼節(jié)點概率,同時把訪問過的中繼節(jié)點儲存在鄰居列表中,前向螞蟻數(shù)據(jù)包發(fā)送流程如圖2所示。
圖2 前向螞蟻數(shù)據(jù)包發(fā)送流程Figure 2 Flow chat of forward ant package transmit
Step3匯聚節(jié)點向源節(jié)點發(fā)送后向螞蟻數(shù)據(jù)包。如圖3所示,前向螞蟻數(shù)據(jù)包到達匯聚節(jié)點后,該節(jié)點隨即生成后向螞蟻數(shù)據(jù)包,該數(shù)據(jù)包中的信息素濃度按照式(7)進行更新,完成信息素更新后的后向螞蟻數(shù)據(jù)包返回到源節(jié)點時,該數(shù)據(jù)包隨即死亡,標(biāo)志著一次螞蟻數(shù)據(jù)包的收發(fā)完成。
圖3 后向螞蟻數(shù)據(jù)包發(fā)送流程Figure 3 Flowchat of backward ant package transmit
為驗證APECARA算法改進后的有效性,對改進后的算法進行仿真實驗,并與現(xiàn)有的典型蟻群路由算法EEABR、ARA進行對比,通過實驗得出相應(yīng)的數(shù)據(jù)和曲線,并分析本文算法的性能。
本文實驗環(huán)境采用MATLAB R2016a搭建仿真平臺,仿真環(huán)境設(shè)置為10 m×10 m的封閉、無干擾的正方形區(qū)域內(nèi)部署100個節(jié)點。無線傳感器網(wǎng)絡(luò)為同構(gòu)靜態(tài)網(wǎng)絡(luò),拓?fù)浣Y(jié)構(gòu)采用平面網(wǎng)狀結(jié)構(gòu),其他仿真參數(shù)如表1所示。部署結(jié)果如圖4所示,其中正方形節(jié)點為源節(jié)點,圓形節(jié)點為中繼節(jié)點,五角星形節(jié)點為匯聚節(jié)點,細實線代表各節(jié)點間的鏈路,粗實線代表改進算法收斂后的最短路徑。
表1 仿真實驗參數(shù)設(shè)置Table 1 Parameters settings of simulation experiment
圖4 節(jié)點分布圖Figure 4 Distributed node graph
4.2.1 網(wǎng)絡(luò)能量消耗
圖5 節(jié)點消耗能量Figure 5 Energy consumption of the node
從圖6可以看出,本文提出的改進算法,在迭代初期對于節(jié)點平均剩余能量的大小并未有明顯優(yōu)勢,這是因為改進的算法為了削弱路徑中出現(xiàn)螞蟻環(huán)路效應(yīng),在前向螞蟻數(shù)據(jù)包中添加了生存時間、源地址和序列號3種標(biāo)識,增加了節(jié)點發(fā)送數(shù)據(jù)的開銷。隨著仿真實驗的進行,改進算法的節(jié)點平均剩余能量明顯低于EEABR和ARA算法的節(jié)點平均剩余能量,這是由于本文改進算法考慮了路徑上節(jié)點的路由數(shù)和前向螞蟻數(shù)據(jù)包途徑節(jié)點損耗能量,提高了下一跳概率的準(zhǔn)確性,避免了網(wǎng)絡(luò)中生成冗余節(jié)點,降低了節(jié)點傳輸數(shù)據(jù)開銷的同時延長了網(wǎng)絡(luò)壽命。
圖6 節(jié)點平均剩余能量Figure 6 Average remaining energy of the node
4.2.2 路徑曲線收斂速度
路徑收斂速度表明了各算法的尋優(yōu)能力。在圖7中,本文提出的改進算法的最短路徑與ARA相比縮短了5.7%。在初始迭代時改進算法的收斂速度與EEABR和ARA算法相比較慢,這是因為本文改進的算法中提出了自適應(yīng)信息素蒸發(fā)系數(shù)這一概念。從全局的角度來看,這是為了防止網(wǎng)絡(luò)中同一節(jié)點的路由數(shù)過多,造成單一節(jié)點能量損耗過大,使節(jié)點過早陷入休眠狀態(tài),但同時也會提高數(shù)據(jù)包選擇更遠的節(jié)點作為下一跳節(jié)點的概率,故在算法計算初期,收斂速度較慢。隨著算法迭代次數(shù)的增加,引入的自適應(yīng)信息素蒸發(fā)函數(shù)提高了下一跳概率的準(zhǔn)確性,使網(wǎng)絡(luò)中節(jié)點能量更加均衡,達到了獲取全局最優(yōu)的目的。
圖7 路徑收斂曲線Figure 7 Convergence curve of the path
4.2.3 網(wǎng)絡(luò)生存周期
仿真實驗將網(wǎng)絡(luò)中剩余節(jié)點數(shù)和節(jié)點死亡數(shù)作為評判網(wǎng)絡(luò)生命周期優(yōu)劣的重要考量參數(shù)。
因上述仿真實驗中,3種算法均在100次迭代內(nèi)各自完成收斂,故圖8分別對比了3種算法在各自完成第100次迭代時的節(jié)點死亡數(shù)目,從圖8中可以看出,在網(wǎng)絡(luò)中ARA算法和EEABR算法的節(jié)點死亡數(shù)均高于本文提出的改進算法,其中ARA算法收斂迅速,造成死亡節(jié)點的自身路由數(shù)目較多,單一節(jié)點能量過度損耗,導(dǎo)致網(wǎng)絡(luò)中死亡節(jié)點數(shù)較多,網(wǎng)絡(luò)生存周期較短。
圖8 節(jié)點死亡數(shù)目Figure 8 Number of node deaths
為了進一步驗證本文提出的改進算法的網(wǎng)絡(luò)生命性能,仿真實驗對比各算法不同迭代次數(shù)對應(yīng)的死亡節(jié)點數(shù),如圖9所示,在ARA算法和EEABR算法中,節(jié)點首次死亡分別出現(xiàn)在第28次迭代和第41迭代時,而改進算法節(jié)點首次死亡出現(xiàn)在第58次迭代。由實驗可知,兩種對比算法的首次節(jié)點死亡時間均早于本文的改進算法。隨著算法迭代的終止,APECARA算法的剩余節(jié)點數(shù)均高于EEABR和ARA算法。這說明APECARA算法延長了網(wǎng)絡(luò)生存周期。
圖9 剩余節(jié)點數(shù)目Figure 9 Number of survived nodes
本文在深入研究典型蟻群路由算法的基礎(chǔ)上,對EEABR路由算法進行了研究與分析,提出了改進蟻群路由算法(APECARA)來解決無線傳感器網(wǎng)絡(luò)中的蟻群環(huán)路效應(yīng)、能量分布不均和網(wǎng)絡(luò)生命周期較短等問題。通過在前向螞蟻數(shù)據(jù)包中添加生存時間、源地址和序列號,同時改進了信息素更新公式,引入節(jié)點路由數(shù)和數(shù)據(jù)包途徑節(jié)點損耗能量,平衡了網(wǎng)絡(luò)中節(jié)點能量分布。通過仿真實驗的對比與分析可知,改進算法的尋優(yōu)最短路徑較對比算法縮短了5.7%,算法終止迭代時,剩余節(jié)點數(shù)均高于對比算法。證明改進后的蟻群路由算法可以有效削弱蟻群環(huán)路效應(yīng),在兼顧網(wǎng)絡(luò)中節(jié)點能量均衡性的同時延長了網(wǎng)絡(luò)生命周期。未來的主要工作將側(cè)重研究啟發(fā)因子α和期望啟發(fā)因子β對信息素及下一跳概率函數(shù)的影響,以提出自適應(yīng)的啟發(fā)因子和期望啟發(fā)因子,從而進一步提升整個網(wǎng)絡(luò)的性能。