無線傳感器網絡自適應動態路由算法仿真

紀辛然

(山西大學商務學院，山西 太原 030031)

1 引言

無線傳感器網絡由多個具有通信、計算能力的傳感器節點以無線方式連接在一起構成[1-2]，同時與實際網絡設備互相連接，共同完成特殊應用及工作。因無線傳感器的節點方位無需提前設定且維護成本更低，與傳統有線傳感器相比無線傳感器更具靈活性。

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

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

2 無線傳感器網絡路由模型

在對平面型路由、等級型路由進行應用及檢測時，其各自的功能與缺陷逐漸表現出來，為此研發了無線傳感器網絡路由框架，如圖1所示，該框架主要由兩大模塊組成，即數據獲取模塊與數據傳輸模塊。

圖1 無線傳感器網絡路由模型

無線傳感器網絡在運行時存在大量多余信息，所以每個節點含有大量冗余信息。若將這些數據全部傳輸至Sink節點，則消耗大量傳輸節點能量。基于此，在數據傳輸前需對節點數目進行高效率采集與融合。利用層簇方法有效地融合數據，由簇首提供制定區域范圍內數據收集與融合的必要條件，從而在數據獲取模塊中采用成簇形式的層次路由。同時，在此模塊中選擇合適的簇首為首要任務，從而提高一定范圍內數據的收集與融合效率，從而大幅度降低傳輸到Sink節點的信息量。若信息在傳輸過程中與某些節點傳輸形成了信息疊加，則信息量的降低能夠大量減少數據節點的承載量，這不僅提高了工作效率，還減少了能量的消耗，實現無線傳感器網絡的節能運行。

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

3 自適應動態路由算法HDAR的實現

根據所改進的無線傳感器網絡路由模型，結合無線傳感器網絡運行特性，提出一種動態自適應路由算法HDAR。HDAR算法主要通過兩種算法完成，一種是動態成簇算法(APSOCH)，另一種是自適應選擇路由算法(ASR)。在數據采集模塊中，采用改進自適用粒子群優化動態成簇算法(APSOCH)[7]。基于此在數據傳輸模塊中，提出了一種由網絡生命階段產生動態轉變的自適應選擇路由算法(ASR)[8]。

3.1 基于ASR算法的路由節能優化

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

當ASR算法選取最優路徑時，距離最接近Sink位置的節點被稱為前期節點，相對于距Sink較遠的節點被稱為后期節點，通過前期節點數據求出所有節點軌跡選取函數F，選取函數最大值當作下一跳。該函數公式如下所示：

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

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

(1)

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

ASR具體算法如下：

Step1：Sink節點發出一個信號，然后網絡節點根據這個信號來確定自身所在相應點位。同時能夠獲得節點的跳數數量。

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

Step3：當節點處在運行后期時，會發出新的信號，待其它節點的指定回復信息。若沒有收到回復信息，則轉換到Step5。

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

Step5：運作一輪回結束后，再返回Step1，不斷重復，建立網絡核心。

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

3.2 動態成簇算法

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

(2)

式中，w代表迭代權重。當權重不夠大時，線性的降低不能夠確保粒子跳出局部最優，基于此，進行非線性自適應權重調整[10]，定義函數如式(3)所示

(3)

(4)

式中，pid代表粒子i當前所在的最優位置，pgd代表在進化過程中全部粒子的最優位置。通過自適應函數定義[11]可知，pid大于pgd。式(3)能夠確保權重隨迭代過程不斷進行而降低，對于權重來說，局部最優與全局最優是相互制約的，可根據權重的轉化進行自適應調節。

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

1)預簇首初始化。利用LEACH來挑選出預簇首，但預簇首不能夠解決能量負載平衡問題。簇內所有非簇首節點把它們的能量由預簇首傳輸到中心節點，初始化節點的局部最優與全局最優。局部最優是指節點所在位置，全局最優是指目前全部粒子的局部最優。為了能夠讓PSO達到此問題空間，提出適應度函數如下所示

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

(5)

(6)

(7)

f3=min{d(ni，BS)}

(8)

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

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

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代表學習因子，φ1和φ2表示隨機數，通常取值在[0，1]之間。要確保節點的傳輸路徑在問題空間中，如果偏離問題空間，需要用人為方式將其控制在空間內邊界上。

3)更新適應度函數，若節點適應度函數小于上代局部最優函數，則更新局部最優函數，若節點中最小局部最優函數小于全局最優函數，則更新全局最優函數。

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

5)由簇首向其它節點傳輸信息，由此建立動態成簇。

在傳感器網絡中，已構建的簇結構也有可能產生動態變化，如圖2(a)所示，網絡運行中又產生了新的節點，則需將它融入到此運行過程中，如圖2(b)所示，融入后的節點向原簇A中傳出信息，若數據傳輸的速度滿足目前情況時，則會向附近節點發出查找信息，隨著事件的不斷發展，節點逐漸擴展到兩個簇結構如圖2(c)。每一輪的簇首任務結束后，則該簇解散，簇內節點又重新恢復到平等關系，并進入抑制狀態。同時節點可根據事件發展情況，重新設定簇首。根據以上步驟完成無線傳感器網絡自適應動態路由算法的優化設計。

圖2 簇動態擴展示意圖

4 實驗結果與分析

實驗設備采用Tiny-OS傳感器網絡的硬件級別仿真軟件power TOSSIM，實驗指標為能量消耗和節點存活率，以傳統的TEEN算法和傳統LEACH算法作為實驗對照組，與研究方法的實驗結果做對比，具體分析如下。

4.1 網絡耗能對比分析

將研究所提的HDAR算法與兩種傳統算法進行對比分析。實驗設置某地區無線傳感器網絡的100個網絡節點作為實驗對象，獲得30分鐘內的平均能量消耗情況，將所提算法與兩種傳統方法進行對比實驗，結果如圖3所示。

圖3 平均耗能對比

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

隨著網絡的不斷運行，這種優勢會變得更加明顯，如圖4所示，描述了在相同網絡范圍內，HDAR、LEACH算法與TEEN的能量消耗情況。當網絡范圍較大時，能量消耗都在不斷增加，由于數據傳輸到Sink節點的過程存活時間變長，導致網絡節點平均能耗加強。當網絡范圍擴大時，TEEN算法和LEACH算法的能量消耗上升速度高于HDAR，這是因為傳統算法下節點的能耗量持續增強，但HDAR中的能量主要用在數據匯總與融合上，所以能耗上升幅度較小，由此可以證明HDAR算法有利于大范圍網絡的實際應用。

圖4 不同網絡規模下的能耗對比

4.2 不同算法下死亡節點分布對比分析

為進一步驗證所提算法的適用性，在相同實驗時長1000s內，設置600m×600m的無線網絡范圍內，對不同算法應用下的無線傳感器網絡節點存活率進行實驗，在實驗結果圖中，圓圈形狀標志代表正常存活節點，星星形狀標志代表死亡節點。具體實驗結果如下：

圖5 死亡節點分布情況對比

由于TEEN算法和LEACH算法是利用在一定時間內簇首輪換的方法來降低耗能量，導致運行過程中消耗了大量能量，尤其在成簇無線傳感器網絡100m×400m范圍內，死亡的節點數量較多。

相比之下，研究算法在整個傳感器網絡范圍內死亡節點數量非常少，

HDAR算法在將數據傳輸到Sink時，通過自適應路由選擇方式，分析節點能耗狀況，利用動態的路由選擇算法，保留含有較少能量的節點，提高了網絡傳感器的實用性，也又減緩了傳感器節點衰敗的速率，一直持續到全部節點消失。通過實驗結果可以說明，HDAR提高了網絡傳感器運轉效率，更加適用于現實生活中。

5 結論

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