一種基于自適應(yīng)信息素蒸發(fā)系數(shù)的WSN蟻群路由算法

王 恭， 孫銘陽， 孫匯陽， 滕子銘

(1.東北電力大學(xué) 自動化工程學(xué)院，吉林 吉林 132012； 2.北京電子科技學(xué)院 密碼科學(xué)與技術(shù)系，北京 100070； 3.吉林大學(xué) 通信工程學(xué)院，吉林 長春 130012)

0 引言

無線傳感器網(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]。

1 系統(tǒng)模型

1.1 數(shù)學(xué)模型

在WSN中，確定任意兩節(jié)點間是否存在有效鏈路[11]可以用式(1)表示：

(1)

假設(shè)在WSN中只存在唯一匯聚節(jié)點z，z∈V，源節(jié)點表示為w∈ {V- {z}}。

1.2 EEABR路由算法

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)

2 改進路由算法APECARA

在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)確性。

2.1 削弱蟻群環(huán)路效應(yīng)

在無線傳感器網(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ù)包頭中的組合項生效，使接收端節(jié)點感知到已經(jīng)收發(fā)過此數(shù)據(jù)包，因此發(fā)送端節(jié)點會將數(shù)據(jù)優(yōu)先傳輸給未有標(biāo)識項的其他節(jié)點，最終達到削弱網(wǎng)絡(luò)環(huán)路的目的。

鄰居列表通過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)過路徑的平均能量。

2.2 修正信息素更新公式

在蟻群路由算法的一次迭代中，當(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)

3 APECARA路由算法流程

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

4 仿真實驗及算法結(jié)果對比

為驗證APECARA算法改進后的有效性，對改進后的算法進行仿真實驗，并與現(xiàn)有的典型蟻群路由算法EEABR、ARA進行對比，通過實驗得出相應(yīng)的數(shù)據(jù)和曲線，并分析本文算法的性能。

4.1 實驗環(huán)境及相關(guān)參數(shù)

本文實驗環(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 仿真分析

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

5 結(jié)論

本文在深入研究典型蟻群路由算法的基礎(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ò)的性能。