無線傳感器網(wǎng)絡(luò)自適應(yīng)動態(tài)路由算法仿真

紀(jì)辛然

(山西大學(xué)商務(wù)學(xué)院，山西 太原 030031)

1 引言

無線傳感器網(wǎng)絡(luò)由多個具有通信、計算能力的傳感器節(jié)點以無線方式連接在一起構(gòu)成[1-2]，同時與實際網(wǎng)絡(luò)設(shè)備互相連接，共同完成特殊應(yīng)用及工作。因無線傳感器的節(jié)點方位無需提前設(shè)定且維護(hù)成本更低，與傳統(tǒng)有線傳感器相比無線傳感器更具靈活性。

在涉及范圍較廣的傳感器網(wǎng)絡(luò)中，利用等級化成簇路由協(xié)議是一種有效的解決方法，目前也出現(xiàn)了較多的研究成果。文獻(xiàn)[3]以潮間帶無線傳感器網(wǎng)絡(luò)(IT-WSN)為例進(jìn)行深入研究，提出期望剩余傳輸次數(shù)(PRTX)算法。 PRTX算法充分考慮網(wǎng)絡(luò)端到端延遲時間、節(jié)點剩余能量、鄰居節(jié)點之間的距離，以及鏈路質(zhì)量，并利用指數(shù)加權(quán)平均算法加強路由選擇的穩(wěn)定性。PRTX路由算法在節(jié)點通信距離變化時具有較好的性能穩(wěn)定性，但運行能耗較高。文獻(xiàn)[4]提出基于改進(jìn)自適應(yīng)離散粒子群算法的異構(gòu)無線傳感器網(wǎng)絡(luò)路由算法，構(gòu)建綜合性目標(biāo)函數(shù)及確定評價指標(biāo)。改進(jìn)算法由于在適值函數(shù)上充分考慮簇頭節(jié)點能耗及簇間負(fù)載均衡因子，使得算法性能得以改良，但該算法節(jié)點存活率較低。文獻(xiàn)[5]提出一種基于虛擬網(wǎng)格的動態(tài)聚簇策略IDCS，考慮數(shù)據(jù)轉(zhuǎn)發(fā)延遲的最大化網(wǎng)絡(luò)生命周期的動態(tài)負(fù)載均衡路由算法DCDLB。IDCS依據(jù)節(jié)點的通信半徑將網(wǎng)絡(luò)劃分成若干虛擬網(wǎng)格，采用考慮節(jié)點能量和位置因素的分布式簇首選舉策略，并引入基于簇首能量水平的動態(tài)簇首輪換機制。DCDLB綜合考慮簇首間能耗均衡和數(shù)據(jù)多跳轉(zhuǎn)發(fā)延遲來構(gòu)建路由，實現(xiàn)網(wǎng)絡(luò)生命周期的最大化，但該方法運行能耗較高。

針對上述傳統(tǒng)方法存在的問題，本次研究提出動態(tài)自適應(yīng)路由HDAR(Hybrid Dynamic Adaptive Routing)算法。建立雙重路由網(wǎng)絡(luò)框架，該框架將平面路由與等級路由相結(jié)合，有效降低路由數(shù)據(jù)傳輸能耗，在數(shù)據(jù)獲取過程中選取等級路由能夠有效匯總數(shù)據(jù)，。實驗證明，采用HDAR計算方法，提高了實際操作效率，改變了路由在選擇上所受的限制，大幅度降低了網(wǎng)絡(luò)平均能耗。

2 無線傳感器網(wǎng)絡(luò)路由模型

在對平面型路由、等級型路由進(jìn)行應(yīng)用及檢測時，其各自的功能與缺陷逐漸表現(xiàn)出來，為此研發(fā)了無線傳感器網(wǎng)絡(luò)路由框架，如圖1所示，該框架主要由兩大模塊組成，即數(shù)據(jù)獲取模塊與數(shù)據(jù)傳輸模塊。

圖1 無線傳感器網(wǎng)絡(luò)路由模型

無線傳感器網(wǎng)絡(luò)在運行時存在大量多余信息，所以每個節(jié)點含有大量冗余信息。若將這些數(shù)據(jù)全部傳輸至Sink節(jié)點，則消耗大量傳輸節(jié)點能量?；诖耍跀?shù)據(jù)傳輸前需對節(jié)點數(shù)目進(jìn)行高效率采集與融合。利用層簇方法有效地融合數(shù)據(jù)，由簇首提供制定區(qū)域范圍內(nèi)數(shù)據(jù)收集與融合的必要條件，從而在數(shù)據(jù)獲取模塊中采用成簇形式的層次路由。同時，在此模塊中選擇合適的簇首為首要任務(wù)，從而提高一定范圍內(nèi)數(shù)據(jù)的收集與融合效率，從而大幅度降低傳輸?shù)絊ink節(jié)點的信息量。若信息在傳輸過程中與某些節(jié)點傳輸形成了信息疊加，則信息量的降低能夠大量減少數(shù)據(jù)節(jié)點的承載量，這不僅提高了工作效率，還減少了能量的消耗，實現(xiàn)無線傳感器網(wǎng)絡(luò)的節(jié)能運行。

由于所有融合后的數(shù)據(jù)最終都會傳送到Sink節(jié)點，但在傳輸過程中，會消耗大量網(wǎng)絡(luò)節(jié)點的能耗量。為此可通過平面路由來解決此問題，平面路由相對來說更加具有靈活性，能夠篩選出誤差較小、效率較高的方式來傳出數(shù)據(jù)，增加各個節(jié)點能量的均衡使用，同時能夠利用能量感知途徑選取方式實現(xiàn)所有節(jié)點的能量均衡，防止某個節(jié)點產(chǎn)生較高的能量消耗及檢測誤區(qū)[6]。

3 自適應(yīng)動態(tài)路由算法HDAR的實現(xiàn)

根據(jù)所改進(jìn)的無線傳感器網(wǎng)絡(luò)路由模型，結(jié)合無線傳感器網(wǎng)絡(luò)運行特性，提出一種動態(tài)自適應(yīng)路由算法HDAR。HDAR算法主要通過兩種算法完成，一種是動態(tài)成簇算法(APSOCH)，另一種是自適應(yīng)選擇路由算法(ASR)。在數(shù)據(jù)采集模塊中，采用改進(jìn)自適用粒子群優(yōu)化動態(tài)成簇算法(APSOCH)[7]?；诖嗽跀?shù)據(jù)傳輸模塊中，提出了一種由網(wǎng)絡(luò)生命階段產(chǎn)生動態(tài)轉(zhuǎn)變的自適應(yīng)選擇路由算法(ASR)[8]。

3.1 基于ASR算法的路由節(jié)能優(yōu)化

ASR算法通過節(jié)點附近鄰域的能量消耗情況，來決定下一跳節(jié)點的重點研究問題，即能耗與跳數(shù)數(shù)量。

當(dāng)ASR算法選取最優(yōu)路徑時，距離最接近Sink位置的節(jié)點被稱為前期節(jié)點，相對于距Sink較遠(yuǎn)的節(jié)點被稱為后期節(jié)點，通過前期節(jié)點數(shù)據(jù)求出所有節(jié)點軌跡選取函數(shù)F，選取函數(shù)最大值當(dāng)作下一跳。該函數(shù)公式如下所示：

F(E′，Hmin)=a(E′/E)×(1-Hmin/Hmax)

+b(Hmin/Hmax)(1-E′/E)

(1)

其中，Hmin表示節(jié)點i到Sink的極小跳數(shù)，Hmax表示網(wǎng)絡(luò)到Sink最長距離的極小跳數(shù)。a、b表示平衡粒子，根據(jù)傳感器節(jié)點的疏密程度以及能量消耗情況來選擇。

ASR具體算法如下：

Step1：Sink節(jié)點發(fā)出一個信號，然后網(wǎng)絡(luò)節(jié)點根據(jù)這個信號來確定自身所在相應(yīng)點位。同時能夠獲得節(jié)點的跳數(shù)數(shù)量。

Step2：所有收到信號的節(jié)點都會發(fā)出指定信息，包含此節(jié)點的基礎(chǔ)信息、ID以及能量消耗情況，表示自己已成為Sink節(jié)點的一個后期節(jié)點。

Step3：當(dāng)節(jié)點處在運行后期時，會發(fā)出新的信號，待其它節(jié)點的指定回復(fù)信息。若沒有收到回復(fù)信息，則轉(zhuǎn)換到Step5。

Step4：節(jié)點收到上游節(jié)點的信號后，在某一時間段內(nèi)若獲得若干個前期運行節(jié)點信號，那么節(jié)點可通過前期節(jié)點信號中的能量狀況和跳數(shù)來求出函數(shù)值，然后選取最大值當(dāng)作自身前一跳節(jié)點，同時發(fā)出信號指定指令。

Step5：運作一輪回結(jié)束后，再返回Step1，不斷重復(fù)，建立網(wǎng)絡(luò)核心。

綜上所述，若節(jié)點間能耗較為接近，那么ASR鄰近極小跳數(shù)，采用極小跳數(shù)來完成數(shù)據(jù)的轉(zhuǎn)運，若能耗差距大，則ASR算法會通過路由選擇函數(shù)，設(shè)定新的跳數(shù)節(jié)點，同時在選取時要分析節(jié)點使用能耗狀況。在不影響節(jié)點所在網(wǎng)絡(luò)中過多的消耗能量，導(dǎo)致網(wǎng)絡(luò)檢測信息缺失的情況下，需要定期重新建立網(wǎng)絡(luò)核心路由，節(jié)省網(wǎng)絡(luò)耗能。

3.2 動態(tài)成簇算法

全局優(yōu)化是算法應(yīng)用的關(guān)鍵性參數(shù)[9]。算法收斂程度會受到迭代權(quán)重的影響，權(quán)重越大越容易跳出局部最優(yōu)，權(quán)重越小越有利于加速運轉(zhuǎn)。所以，權(quán)重會根據(jù)迭代的進(jìn)行而不斷降低，經(jīng)典的線性迭代權(quán)重如式(2)所示

(2)

式中，w代表迭代權(quán)重。當(dāng)權(quán)重不夠大時，線性的降低不能夠確保粒子跳出局部最優(yōu)，基于此，進(jìn)行非線性自適應(yīng)權(quán)重調(diào)整[10]，定義函數(shù)如式(3)所示

(3)

(4)

式中，pid代表粒子i當(dāng)前所在的最優(yōu)位置，pgd代表在進(jìn)化過程中全部粒子的最優(yōu)位置。通過自適應(yīng)函數(shù)定義[11]可知，pid大于pgd。式(3)能夠確保權(quán)重隨迭代過程不斷進(jìn)行而降低，對于權(quán)重來說，局部最優(yōu)與全局最優(yōu)是相互制約的，可根據(jù)權(quán)重的轉(zhuǎn)化進(jìn)行自適應(yīng)調(diào)節(jié)。

為實現(xiàn)均衡能耗，采用與LEACH同樣的操作模式，構(gòu)建階段優(yōu)點，并通過APSO來選取最優(yōu)簇首，這種方式被叫做自適應(yīng)粒子群分簇多層(Adaptive Particle Swarm Optimizational Clustering Hierarchy，APSOCH)協(xié)議建立，步驟如下：

1)預(yù)簇首初始化。利用LEACH來挑選出預(yù)簇首，但預(yù)簇首不能夠解決能量負(fù)載平衡問題。簇內(nèi)所有非簇首節(jié)點把它們的能量由預(yù)簇首傳輸?shù)街行墓?jié)點，初始化節(jié)點的局部最優(yōu)與全局最優(yōu)。局部最優(yōu)是指節(jié)點所在位置，全局最優(yōu)是指目前全部粒子的局部最優(yōu)。為了能夠讓PSO達(dá)到此問題空間，提出適應(yīng)度函數(shù)如下所示

fitness=a×f1+β×f2+γ×f3

(5)

(6)

(7)

f3=min{d(ni，BS)}

(8)

式中，f1代表能量消耗，f2表示簇間距離，f3表示節(jié)點到中心節(jié)點的距離，根據(jù)上述定義可知，f1，f2與f3都能夠確保選擇最優(yōu)簇首。S代表一定范圍內(nèi)的簇空間，E表示節(jié)點的能耗情況，E′表示剩余能量，|Cs|代表簇空間節(jié)點數(shù)量。

2)節(jié)點的傳輸速率更新。由于問題空間是二維[12]的，因此要將速率進(jìn)行更新，然后根據(jù)如下迭代公式進(jìn)行計算。

vid(t)=w×vid(t-1)+c1φ1(pid-xid(t-1))

+c2φ2(pgd-xid(t-1))

(9)

xid(t)=xid(t-1)+vid(t)

(10)

式中，vid和xid代表粒子i的速率與位置，c1，c2代表學(xué)習(xí)因子，φ1和φ2表示隨機數(shù)，通常取值在[0，1]之間。要確保節(jié)點的傳輸路徑在問題空間中，如果偏離問題空間，需要用人為方式將其控制在空間內(nèi)邊界上。

3)更新適應(yīng)度函數(shù)，若節(jié)點適應(yīng)度函數(shù)小于上代局部最優(yōu)函數(shù)，則更新局部最優(yōu)函數(shù)，若節(jié)點中最小局部最優(yōu)函數(shù)小于全局最優(yōu)函數(shù)，則更新全局最優(yōu)函數(shù)。

4)循環(huán)檢索，直到找到最初制定的最大迭代值。迭代完成后，把最優(yōu)全局函數(shù)放到適合的鄰域節(jié)點上，然后選取此節(jié)點為簇首。

5)由簇首向其它節(jié)點傳輸信息，由此建立動態(tài)成簇。

在傳感器網(wǎng)絡(luò)中，已構(gòu)建的簇結(jié)構(gòu)也有可能產(chǎn)生動態(tài)變化，如圖2(a)所示，網(wǎng)絡(luò)運行中又產(chǎn)生了新的節(jié)點，則需將它融入到此運行過程中，如圖2(b)所示，融入后的節(jié)點向原簇A中傳出信息，若數(shù)據(jù)傳輸?shù)乃俣葷M足目前情況時，則會向附近節(jié)點發(fā)出查找信息，隨著事件的不斷發(fā)展，節(jié)點逐漸擴展到兩個簇結(jié)構(gòu)如圖2(c)。每一輪的簇首任務(wù)結(jié)束后，則該簇解散，簇內(nèi)節(jié)點又重新恢復(fù)到平等關(guān)系，并進(jìn)入抑制狀態(tài)。同時節(jié)點可根據(jù)事件發(fā)展情況，重新設(shè)定簇首。根據(jù)以上步驟完成無線傳感器網(wǎng)絡(luò)自適應(yīng)動態(tài)路由算法的優(yōu)化設(shè)計。

圖2 簇動態(tài)擴展示意圖

4 實驗結(jié)果與分析

實驗設(shè)備采用Tiny-OS傳感器網(wǎng)絡(luò)的硬件級別仿真軟件power TOSSIM，實驗指標(biāo)為能量消耗和節(jié)點存活率，以傳統(tǒng)的TEEN算法和傳統(tǒng)LEACH算法作為實驗對照組，與研究方法的實驗結(jié)果做對比，具體分析如下。

4.1 網(wǎng)絡(luò)耗能對比分析

將研究所提的HDAR算法與兩種傳統(tǒng)算法進(jìn)行對比分析。實驗設(shè)置某地區(qū)無線傳感器網(wǎng)絡(luò)的100個網(wǎng)絡(luò)節(jié)點作為實驗對象，獲得30分鐘內(nèi)的平均能量消耗情況，將所提算法與兩種傳統(tǒng)方法進(jìn)行對比實驗，結(jié)果如圖3所示。

圖3 平均耗能對比

實驗開始階段，三種方法的能耗非常接近。隨著各節(jié)點的傳輸，傳統(tǒng)TEEN算法和傳統(tǒng)LEACH算法消耗的能量明顯增加，主要是由于兩種傳統(tǒng)算法的全部節(jié)點都要在一定時間內(nèi)重新選定簇首，但在HDNA算法中，當(dāng)節(jié)點在傳輸過程中含有數(shù)據(jù)時，簇首由運行數(shù)據(jù)來完成，當(dāng)節(jié)點在傳輸中沒有攜帶數(shù)據(jù)時則無需參與成簇的任務(wù)，從而節(jié)省了能量，同時HDAR算法中運用了動態(tài)成簇的方法，使融合的效率有所提高，降低了傳輸?shù)絊INK節(jié)點的數(shù)據(jù)量，所以傳統(tǒng)算法的能量消耗要高于HDAD。

隨著網(wǎng)絡(luò)的不斷運行，這種優(yōu)勢會變得更加明顯，如圖4所示，描述了在相同網(wǎng)絡(luò)范圍內(nèi)，HDAR、LEACH算法與TEEN的能量消耗情況。當(dāng)網(wǎng)絡(luò)范圍較大時，能量消耗都在不斷增加，由于數(shù)據(jù)傳輸?shù)絊ink節(jié)點的過程存活時間變長，導(dǎo)致網(wǎng)絡(luò)節(jié)點平均能耗加強。當(dāng)網(wǎng)絡(luò)范圍擴大時，TEEN算法和LEACH算法的能量消耗上升速度高于HDAR，這是因為傳統(tǒng)算法下節(jié)點的能耗量持續(xù)增強，但HDAR中的能量主要用在數(shù)據(jù)匯總與融合上，所以能耗上升幅度較小，由此可以證明HDAR算法有利于大范圍網(wǎng)絡(luò)的實際應(yīng)用。

圖4 不同網(wǎng)絡(luò)規(guī)模下的能耗對比

4.2 不同算法下死亡節(jié)點分布對比分析

為進(jìn)一步驗證所提算法的適用性，在相同實驗時長1000s內(nèi)，設(shè)置600m×600m的無線網(wǎng)絡(luò)范圍內(nèi)，對不同算法應(yīng)用下的無線傳感器網(wǎng)絡(luò)節(jié)點存活率進(jìn)行實驗，在實驗結(jié)果圖中，圓圈形狀標(biāo)志代表正常存活節(jié)點，星星形狀標(biāo)志代表死亡節(jié)點。具體實驗結(jié)果如下：

圖5 死亡節(jié)點分布情況對比

由于TEEN算法和LEACH算法是利用在一定時間內(nèi)簇首輪換的方法來降低耗能量，導(dǎo)致運行過程中消耗了大量能量，尤其在成簇?zé)o線傳感器網(wǎng)絡(luò)100m×400m范圍內(nèi)，死亡的節(jié)點數(shù)量較多。

相比之下，研究算法在整個傳感器網(wǎng)絡(luò)范圍內(nèi)死亡節(jié)點數(shù)量非常少，

HDAR算法在將數(shù)據(jù)傳輸?shù)絊ink時，通過自適應(yīng)路由選擇方式，分析節(jié)點能耗狀況，利用動態(tài)的路由選擇算法，保留含有較少能量的節(jié)點，提高了網(wǎng)絡(luò)傳感器的實用性，也又減緩了傳感器節(jié)點衰敗的速率，一直持續(xù)到全部節(jié)點消失。通過實驗結(jié)果可以說明，HDAR提高了網(wǎng)絡(luò)傳感器運轉(zhuǎn)效率，更加適用于現(xiàn)實生活中。

5 結(jié)論

此次研究建立了兩種路由互相合作的無線傳感器網(wǎng)絡(luò)路由框架，分別為層次路由和平面路由，同時結(jié)合了動態(tài)成簇自適應(yīng)路由算法HDAR。該算法包含運行數(shù)據(jù)動態(tài)成簇算法和能量自適應(yīng)路由選擇算法。實驗分析證明HDAR算法具有較高的適用性，利于大范圍的網(wǎng)絡(luò)操作，能夠降低網(wǎng)絡(luò)節(jié)點的能量消耗，并有效提升網(wǎng)絡(luò)的運行時長。