李新路 吳志澤 李國斌

(合肥學(xué)院 人工智能與大數(shù)據(jù)學(xué)院， 合肥 230601)

無線傳感器網(wǎng)絡(luò)(WSNs)常見的應(yīng)用是監(jiān)測遠(yuǎn)程環(huán)境中的低頻數(shù)據(jù)趨勢，如習(xí)慣監(jiān)測、健康監(jiān)測、城市環(huán)境監(jiān)測、目標(biāo)跟蹤等。WSNs由大量分布式傳感器節(jié)點(diǎn)組成，它的單個(gè)節(jié)點(diǎn)通常由能量受限且不可替換的電池供電[1]。因此，如何高效地利用有限能量，延長網(wǎng)絡(luò)生命周期，這是在無線傳感器網(wǎng)絡(luò)路由設(shè)計(jì)中需要探索的問題。

1 相關(guān)研究略述

有關(guān)研究表明，分簇路由協(xié)議可以增加網(wǎng)絡(luò)的可擴(kuò)展性和生命周期[1-2]。典型的分簇路由協(xié)議如LEACH[2]、HEED[3]等，是將網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)劃分成簇頭節(jié)點(diǎn)和成員節(jié)點(diǎn)，使用特定的選擇策略挑選簇頭節(jié)點(diǎn)，根據(jù)空間距離等因素來劃分簇，由簇頭節(jié)點(diǎn)負(fù)責(zé)其所在簇中的數(shù)據(jù)收集和融合，并傳輸數(shù)據(jù)到基站。因此簇頭扮演了非常重要的角色，會(huì)消耗更多的能量，容易導(dǎo)致網(wǎng)絡(luò)壽命的縮短，或者帶來網(wǎng)絡(luò)“熱點(diǎn)”問題[4]。

近年來，在簇頭的產(chǎn)生和分簇的形成算法方面已經(jīng)有許多研究成果[5-9]。鑒于簇間單跳通信模型的局限性，對多跳路由算法的研究也在逐漸增加。文獻(xiàn)[10]提出了一種基于蟻群優(yōu)化的分簇路由算法，在簇間通信中利用蟻群的自組織、自適應(yīng)和動(dòng)態(tài)尋優(yōu)能力，進(jìn)行網(wǎng)絡(luò)優(yōu)化路徑的建立與維護(hù)。文獻(xiàn)[11]提出了一種感知蟻群路由算法，通過感知節(jié)點(diǎn)能量、鏈路質(zhì)量和鏈路生存性等網(wǎng)絡(luò)狀況，均衡網(wǎng)絡(luò)能量、提高分組投遞率。文獻(xiàn)[12]提出了一種改進(jìn)的蟻群路由協(xié)議，通過改進(jìn)啟發(fā)函數(shù)，綜合考慮節(jié)點(diǎn)通信的傳輸距離、傳輸方向、剩余能量和距匯聚節(jié)點(diǎn)的距離，引入新的路由更新規(guī)則，使網(wǎng)絡(luò)保持相對較高的平均剩余能量水平。

在分簇算法的研究中，大部分改進(jìn)算法是通過引入節(jié)點(diǎn)剩余能量、位置距離等因素，設(shè)計(jì)簇頭選擇及分簇形成算法，但往往忽略了對網(wǎng)絡(luò)分簇?cái)?shù)量的分析。一些基于蟻群的多跳路由協(xié)議是以滿足最短路徑[10,13]或最小能耗[11-12,14]為目標(biāo)，未能綜合考慮其他能量度量(如平均能耗、最大能耗)。在規(guī)劃的最優(yōu)路徑中一些能量較低的節(jié)點(diǎn)會(huì)過早地耗盡能量，引發(fā)網(wǎng)絡(luò)“熱點(diǎn)”問題。此外，由于無線網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性、網(wǎng)絡(luò)拓?fù)涞淖兓?，在蟻群路由協(xié)議中，鄰居節(jié)點(diǎn)需要頻繁交換剩余能量、信息素及啟發(fā)因子等。采用廣播機(jī)制，信息交換過于頻繁，會(huì)急劇增加網(wǎng)絡(luò)的控制開銷，也容易導(dǎo)致網(wǎng)絡(luò)沖突并帶來額外的能量消耗。

現(xiàn)提出一種基于機(jī)會(huì)策略的蟻群分簇路由協(xié)議，以實(shí)現(xiàn)協(xié)議的高能效和良好的能量負(fù)載均衡。在分簇算法中，利用網(wǎng)絡(luò)生命周期的理論值定義平均能耗期望值，并以此為基準(zhǔn)重新定義分簇算法中的簇頭選擇概率，使網(wǎng)絡(luò)分簇?cái)?shù)在理論最優(yōu)值附近波動(dòng)；同時(shí)，綜合考慮能耗及路由跳數(shù)等因素，重新定義啟發(fā)式函數(shù)和信息素更新方式，使用這種改進(jìn)的蟻群路由算法，為網(wǎng)絡(luò)簇間通信建立具有較低能耗水平和較短鏈路長度的最優(yōu)路徑；采用基于能耗的機(jī)會(huì)廣播機(jī)制，減少網(wǎng)絡(luò)路由控制開銷。

2 算法設(shè)計(jì)

假設(shè)：在矩形區(qū)域中隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，基站位于矩形的某一頂點(diǎn)。采用與文獻(xiàn)[2]相同的能量模型。為了降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)壽命，采用基于能量估計(jì)的分簇算法和改進(jìn)的蟻群多跳路由算法。為了避免網(wǎng)絡(luò)泛濫，降低由廣播機(jī)制引起的額外能耗，采用基于機(jī)會(huì)策略的廣播算法。

2.1 基于能量估計(jì)的分簇算法

在分簇路由協(xié)議中，分簇算法通過輪(Round)周期性地選擇簇頭。每一輪選擇中，節(jié)點(diǎn)隨機(jī)選擇0～1之間的數(shù)，如果生成的隨機(jī)數(shù)小于閾值T(s)，則該節(jié)點(diǎn)成為本輪的簇頭。閾值計(jì)算公式如下：

(1)

式中：r是當(dāng)前輪數(shù)；G為包含過去1P輪中未被選為簇頭的節(jié)點(diǎn)集合；P為簇頭占所有節(jié)點(diǎn)的百分比，為先驗(yàn)值，其取值影響分簇的大小及分簇算法性能。

根據(jù)文獻(xiàn)[2]，在給定傳感器節(jié)點(diǎn)分布總數(shù)的情況下，先驗(yàn)概率P存在最優(yōu)值：

Popt=koptN

(2)

式中：Popt和kopt分別表示先驗(yàn)概率P的最優(yōu)值和網(wǎng)絡(luò)最優(yōu)分簇?cái)?shù)。

在分簇算法中，考慮到每個(gè)節(jié)點(diǎn)的能耗因素，直接使用Popt同樣會(huì)導(dǎo)致網(wǎng)絡(luò)“熱點(diǎn)”問題。因此，為每輪簇頭選擇引入一個(gè)能量估算值。

(3)

式中：R表示最大輪數(shù)的理論值，由最優(yōu)簇頭數(shù)量kopt及網(wǎng)絡(luò)的總能量Etotal決定。

(4)

式中：E(i)表示節(jié)點(diǎn)i當(dāng)前的剩余能量。

這樣，可以保證Pi在先驗(yàn)概率最優(yōu)值附近波動(dòng)，同時(shí)確保具有較多剩余能量的節(jié)點(diǎn)有更多的機(jī)會(huì)被選為簇頭。相應(yīng)地，網(wǎng)絡(luò)能耗可在各輪選擇中分布均衡，延長網(wǎng)絡(luò)生命周期。

2.2 蟻群多跳路由算法改進(jìn)

對蟻群路由算法的啟發(fā)式函數(shù)及信息素更新方式進(jìn)行優(yōu)化，然后采用基于蟻群優(yōu)化算法的多跳路由協(xié)議進(jìn)行簇間通信。在蟻群路由算法中，前向螞蟻代理的下一跳路由選擇，由基于信息素和啟發(fā)式函數(shù)的隨機(jī)決策策略控制。

(5)

式中：Pij(t)為t時(shí)刻螞蟻代理從節(jié)點(diǎn)i移動(dòng)到節(jié)點(diǎn)j的狀態(tài)轉(zhuǎn)移概率；τij(t)和ηij(t)分別代表t時(shí)刻鏈路(i,j)上的信息素濃度和啟發(fā)式函數(shù)值；α和β分別表示信息素和啟發(fā)式函數(shù)權(quán)重因子；Ni是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合；Tabu為禁忌表，存儲(chǔ)螞蟻代理已訪問的節(jié)點(diǎn)集合。

重新定義局部啟發(fā)式函數(shù)：

(6)

這樣，對于能耗較少、剩余能量多的節(jié)點(diǎn)，局部啟發(fā)因子值較高，即在某簇頭節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中，剩余能量高于或接近網(wǎng)絡(luò)平均能量的節(jié)點(diǎn)，有更大概率成為下一跳節(jié)點(diǎn)。

前向螞蟻代理在搜索路徑過程中，記錄途經(jīng)節(jié)點(diǎn)的能量信息；到達(dá)基站后轉(zhuǎn)變成后向螞蟻代理，并通過單播方式為途經(jīng)的中間節(jié)點(diǎn)更新信息素濃度，估算鏈路成本，更新路由表。在蟻群路由協(xié)議中，全局信息素濃度τij按照式(7)更新。

τij=(1-ρ)·τij+ρ·Δτij

(7)

式中：ρ∈(0，1)，是路徑信息素濃度的揮發(fā)系數(shù)；Δτij表示鏈路(i，j)上的信息素濃度增量，由包含此鏈路的路徑信息素總增量分配。

將信息素總體增量定義為：

(8)

式中：Emin和Eavg分別表示前向螞蟻途經(jīng)路徑的最低剩余能量和平均剩余能量；Fant表示前向螞蟻代理經(jīng)過的路徑長度。

鏈路信息素濃度更新方式為：

(9)

式中：Bant代表后向螞蟻距離基站的路徑長度；ξ是一個(gè)控制系數(shù)，其目的是對Δτij進(jìn)行歸一化處理。

根據(jù)式(7)(8)(9)，信息素濃度的更新取決于路徑的能量水平(Emin、Eavg、E(j))及路徑長度(Fant和Bant)。因此，具有更多剩余能量的鏈路會(huì)分布更高的信息素增量，同時(shí)路徑較短的鏈路也會(huì)獲得較高信息素增量。此外，在信息素更新過程中，剩余能量較多或基站附近的傳感器節(jié)點(diǎn)具有更多的信息素濃度。這樣，可以使得平均能量較高的鏈路承擔(dān)更多數(shù)據(jù)轉(zhuǎn)發(fā)功能，同時(shí)也吸引數(shù)據(jù)流向基站，加快路由協(xié)議的收斂速度。

2.3 機(jī)會(huì)路由策略

廣播機(jī)制是節(jié)點(diǎn)用來交換本地信息的一種快速有效的通信方法?；谙伻核惴ǖ穆酚蓞f(xié)議，通常采用快速廣播機(jī)制交換相鄰節(jié)點(diǎn)的剩余能量等信息，從而增加路由控制開銷，容易引起網(wǎng)絡(luò)擁塞，造成大量額外的能量消耗。在規(guī)模較大或存在較多移動(dòng)節(jié)點(diǎn)的網(wǎng)絡(luò)中，這種情況尤為嚴(yán)重?，F(xiàn)在提出一種簡單機(jī)會(huì)路由策略，通過降低路由控制開銷來降低網(wǎng)絡(luò)能耗。

在改進(jìn)的蟻群多跳路由算法中，當(dāng)傳感器節(jié)點(diǎn)收到廣播信號(hào)后，使用機(jī)會(huì)策略選擇其鄰居節(jié)點(diǎn)集合中的一個(gè)節(jié)點(diǎn)來重新廣播信息。為此，定義一個(gè)評(píng)價(jià)函數(shù)C(i，j)來表示節(jié)點(diǎn)i和其鄰居節(jié)點(diǎn)j之間的鏈路質(zhì)量。

(10)

式中：Emax和Emin分別表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中剩余能量最大值和最小值。

節(jié)點(diǎn)i收到廣播數(shù)據(jù)包時(shí)，將根據(jù)隨機(jī)決策概率b(i，j)選擇一個(gè)鄰居節(jié)點(diǎn)j，并重新廣播該數(shù)據(jù)包。隨機(jī)決策公式如下：

(11)

通過這種方式，機(jī)會(huì)路由策略取代簡單廣播，每次選擇不同的節(jié)點(diǎn)，重新廣播控制消息。同時(shí)，由于在鏈路質(zhì)量評(píng)價(jià)函數(shù)中使用能量因子，具有更多剩余能量的鄰居節(jié)點(diǎn)即高鏈路質(zhì)量的節(jié)點(diǎn)，具有更多的轉(zhuǎn)發(fā)數(shù)據(jù)的機(jī)會(huì)，相應(yīng)地在減少網(wǎng)絡(luò)開銷的同時(shí)也平衡了能量消耗。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為便于描述，將上述基于機(jī)會(huì)策略的蟻群分簇路由協(xié)議簡稱為“OACR”。在NS2網(wǎng)絡(luò)仿真環(huán)境下，對LEACH協(xié)議[2]、EEABR協(xié)議[13]、UCACO協(xié)議[15]與OACR協(xié)議的性能進(jìn)行對比分析。

仿真實(shí)驗(yàn)參數(shù)：網(wǎng)絡(luò)區(qū)域1 000 m2；節(jié)點(diǎn)100個(gè)，均勻分布；基站位置為(0，1 000)；能耗(發(fā)射接受)為50×10-7JB，初始能量為1 000 J。

由于蟻群優(yōu)化算法中的權(quán)重因子α和β與信息素?fù)]發(fā)系數(shù)ρ對算法性能有較大的影響，根據(jù)文獻(xiàn)[16]中得出的經(jīng)驗(yàn)值，確定α、β、ρ的取值分別為1、5、0.5；式(9)中的歸一化系數(shù)ξ取值為0.9。使用仿真參數(shù)，對每個(gè)路由協(xié)議分別運(yùn)行30次，每次模擬時(shí)長600 s，取其平均值。主要從網(wǎng)絡(luò)成簇?cái)?shù)、平均能耗、路由控制開銷、生命周期等4個(gè)方面對比各類路由算法的性能。

3.1 網(wǎng)絡(luò)成簇?cái)?shù)

網(wǎng)絡(luò)成簇?cái)?shù)是衡量分簇算法性能的一個(gè)重要指標(biāo)。分簇路由協(xié)議中存在分簇?cái)?shù)最優(yōu)值，網(wǎng)絡(luò)分簇?cái)?shù)等于或接近此最優(yōu)值，則意味著網(wǎng)絡(luò)分簇狀態(tài)穩(wěn)定，且各分簇能耗較為均衡。模擬結(jié)果如圖1所示。

圖1 網(wǎng)絡(luò)成簇?cái)?shù)對比

由圖1可知，模擬的分簇算法成簇?cái)?shù)都圍繞最優(yōu)值(kopt)波動(dòng)。根據(jù)公式(2)，在設(shè)定的模擬環(huán)境下，kopt=10。其中，OACR的成簇?cái)?shù)在kopt附近波動(dòng)，振幅較小，波動(dòng)曲線較為平滑。這是由于在OACR中引入了能量估計(jì)值、節(jié)點(diǎn)剩余能量，并與最優(yōu)分簇概率(Popt)結(jié)合，為每個(gè)節(jié)點(diǎn)定義了獨(dú)立的簇頭選擇概率(Pi)，使得分簇?cái)?shù)能接近最優(yōu)值。UCACO的分簇算法中，雖然考慮了能量因素，但只會(huì)讓高剩余能量節(jié)點(diǎn)有較大概率被選中，采用的是與LEACH分簇算法同樣的完全隨機(jī)方式，因此它們的成簇?cái)?shù)雖然也是圍繞最優(yōu)值波動(dòng)，但其振幅較大。因EEABR是平面路由協(xié)議，這里未分析其成簇性能。

3.2 網(wǎng)絡(luò)平均能耗

網(wǎng)絡(luò)的平均能耗與網(wǎng)絡(luò)壽命成正比。模擬結(jié)果，不同仿真時(shí)間下的網(wǎng)絡(luò)平均能耗如圖2所示。由此可見，COAR的性能優(yōu)于EEABR、UCACO和LEACH。EEABR在平均能耗性能上表現(xiàn)最差，主要由于它是采用平面路由，而不是分簇路由。在LEACH、UCACO和OACR這3種分簇路由協(xié)議中，在分簇策略中考慮到能量因素的UCACO和OACR的性能表現(xiàn)都優(yōu)于LEACH。OACR使用機(jī)會(huì)廣播而不是泛洪，大大減少了控制消息的額外能耗，從而也降低了總能耗。

圖2 網(wǎng)絡(luò)平均能量消耗對比

能耗標(biāo)準(zhǔn)差是網(wǎng)絡(luò)中所有節(jié)點(diǎn)能量消耗的平均方差，描述網(wǎng)絡(luò)的能耗分布。較低的標(biāo)準(zhǔn)差表示數(shù)據(jù)點(diǎn)趨于接近集合的預(yù)期值，而高標(biāo)準(zhǔn)差表示數(shù)據(jù)點(diǎn)分布在更寬的范圍內(nèi)。高能效的路由協(xié)議應(yīng)使節(jié)點(diǎn)的平均能量消耗水平較小，同時(shí)能耗標(biāo)準(zhǔn)差較小，使得能耗均衡，如此便可以延長網(wǎng)絡(luò)壽命。就能耗標(biāo)準(zhǔn)差而言，與UCACO、LEACH、EEABR相比，OACR的表現(xiàn)更好一些(見圖3)。

OACR的良好表現(xiàn)得益于改進(jìn)的信息素濃度更新方式和啟發(fā)因子的重新定義，不僅考慮到了能量因子，同時(shí)也考慮了前向和后向距離，使得匯聚后的數(shù)據(jù)能流向平均能量較高且路徑長度較短的鏈路，這有助于平衡網(wǎng)絡(luò)中的能量消耗，避免最佳路徑的快速惡化。而在UCACO及EEABR協(xié)議中，只是將能耗作為數(shù)據(jù)轉(zhuǎn)發(fā)的主要依據(jù)。

圖3 網(wǎng)絡(luò)平均能量消耗標(biāo)準(zhǔn)差

3.3 路由控制開銷

網(wǎng)絡(luò)路由控制開銷等于控制消息的數(shù)量除以已傳輸?shù)南⒖倲?shù)。這里的控制數(shù)據(jù)，包括分簇算法中的簇頭廣播及加入簇的申請消息，還有簇間多跳路由協(xié)議中的螞蟻代理數(shù)據(jù)?？刂崎_銷可能導(dǎo)致網(wǎng)絡(luò)擁塞和額外的能量消耗。模擬結(jié)果如圖4所示。

圖4 網(wǎng)絡(luò)路由控制開銷對比

與其他協(xié)議相比，OACR的路由開銷比率更低一些。在COAR中，每個(gè)節(jié)點(diǎn)都根據(jù)其鏈路評(píng)價(jià)函數(shù)重新廣播控制消息，消息轉(zhuǎn)發(fā)的總量大大減少。LEACH協(xié)議不需要使用蟻群路由算法，其控制開銷低于UCACO和EEABR；而在UCACO和EEABR中，沒有使用機(jī)會(huì)路由策略，它倆的路由控制開銷基本持平。

3.4 網(wǎng)絡(luò)生命周期

網(wǎng)絡(luò)生命周期預(yù)測值是初始能量、平均能耗和能耗標(biāo)準(zhǔn)差的函數(shù)。根據(jù)模擬結(jié)果，在幾種路由協(xié)議中，OACR的網(wǎng)絡(luò)生命周期預(yù)期值最高(見圖5)，可以提供更長的網(wǎng)絡(luò)壽命，這與它的網(wǎng)絡(luò)能耗(見圖2)及其標(biāo)準(zhǔn)差(見圖3)也是相符合的。

圖5 網(wǎng)絡(luò)生命周期預(yù)測結(jié)果

4 結(jié) 語

本次研究，在分析網(wǎng)絡(luò)分簇算法及簇間通信協(xié)議的基礎(chǔ)上，以設(shè)計(jì)高能效路由協(xié)議為目標(biāo)，通過引入能量估算值、重新定義簇頭選擇概率，優(yōu)化了網(wǎng)絡(luò)分簇；在基于蟻群的簇間通信協(xié)議中，優(yōu)化啟發(fā)因子和信息素濃度更新策略；同時(shí)，為了降低網(wǎng)絡(luò)控制開銷帶來的額外能耗，提出了一種機(jī)會(huì)路由策略。仿真實(shí)驗(yàn)結(jié)果表明，這種改進(jìn)后的基于機(jī)會(huì)策略的蟻群分簇路由協(xié)議，可在很大程度上提高網(wǎng)絡(luò)使用效率、平衡節(jié)點(diǎn)能量消耗，從而能夠延長網(wǎng)絡(luò)的生命周期。