能量異構無線傳感器網絡分簇路由算法研究

張銘悅，陳桂芬，王鶴霏

（長春理工大學 電子信息工程學院，長春 130022）

物聯網技術被譽為當今偉大的技術之一，它的應用主要與三項關鍵技術密不可分。其中一項關鍵技術—無線傳感器網絡相當于“觸手”，針對無處不在的信息流進行感知，并將獲得的信息進行處理。傳感器節點可以分布在森林、會議室、患者身體等特殊區域。可以實現對多種實時動態數據的采集。之后，來自傳感器的數據傳遞給實時接收設備，通過互聯網傳遞給用戶［1］。隨著社會的發展需要，數據產生的途徑也更加多樣化，現今有效的數據收集手段也很有限，傳感器的發展仍然重要。

無線傳感器網絡（WSN）由多個傳感器節點組成，這些節點分布在各個需要收集數據的區域，每個節點的通信方式、計算和感知能力都是相同的［2］。無線傳感器網絡適用于棲息地監測，建筑監測和森林監測等領域，在生物科學、生物醫學等重要領域中扮演著重要的角色［3］。無線傳感器網絡收集的信息量很大，在電池、傳感器以及附近的能量消耗速度較快。能量的不均勻消耗會導致網絡壽命的縮短。分簇算法的出現大大延長了網絡的生命周期，并節約了很多能量［4］。

早期對無線傳感器網絡的研究主要集中在同構網絡上，但現實環境下，同構網絡的作用并不好，相對而言，異構網絡的發展更具有現實意義。異構無線傳感器網絡分為節點能量異構網絡、計算能量異構網絡、鏈路異構網絡、網絡協議異構網絡等［5］。

胡中棟、伍華林等人［6］提出了MEECR算法，該算法優化DEEC算法的方式是將節點位置與剩余能量引入簇頭選舉機制，通過改進選舉閾值公式，優化網絡性能。Raju Pal等人［7］提出的BEECP是將BBO算法（Biogeography-based optimi?zation）引入到異構網絡中，用于找出傳感器節點的最佳組合，達到降低能耗的作用。Jin-Shyan Lee等人［8］提出了一種基于三層結構的半分布式分簇方法，實現了上下層的簇頭選擇，有效提高了網絡死亡生命周期。Saini P等人［9］提出了EDEEC算法，該算法在異構無線傳感器網絡中原有的兩種節點的基礎上，加入了超級節點，增加了網絡的異構性和能量水平。Nematollahi P等人［10］提出了SEDC算法（Simple Energyefficient Data Collecting protocol），該算法是通過設置能量閾值，讓能量不符合要求的節點不參與簇頭的選舉，使得簇頭選舉更加準確快速。Dutt S等人［11］提出了一種簇頭能量受限的算法CREEP，該算法通過修改雙層異構網絡中的簇頭選擇閾值，來克服原算法在簇頭上的限制。Van?in等人［12］提出了一種基于三層異構分簇的分布式節能路由算法TBSDEEC，該算法考慮了能量消耗模型中，閾值平衡采樣的影響，通過設置兩種不同的應用場景，來設置參數。

上述針對異構網絡算法的改進，不僅僅從網絡本身的異構性進行考慮，還有參數和算法的結構。應用場景也是優化異構網絡性能的重要考慮因素。

1 DEEC算法

異構網絡的研究起步晚于同構網絡，為了更好的理解異構網絡，首先，介紹一下同構網絡的研究狀況。

大部分適用于同構網絡的算法均可改進為適用于異構網絡的算法。DEEC算法就是從LEACH算法改進而來的。這種改進同構網絡算法方式，使得其實用價值得到提高。同構網絡與異構網絡的區別主要體現在兩個方面：參數設置的不同和協議的混合應用。參數的設置可以隨著環境的變化而變化，協議的不同，則需要特殊技術，將其融和在一起，共同對網絡發揮作用。

DEEC算法主要目的是將剩余能量更多的節點選做簇頭，節約網絡能量，使其利用率提高。該算法主要應用于二級能量異構無線傳感器網絡。

（1）簇的建立階段

兩種節點的區別直觀體現在初始能量的差異上，普通節點的初始能量為E0，那么高級節點的初始能量是E0（1+α）。α為高級節點多于普通節點的能量倍數。由于存在兩種不同的節點，對兩種節點的概率值Pi的設置也不同，如公式（1）所示：

其中，Popt表示期望簇頭比例；Ei(r)表示節點在r輪剩余的能量值；Pi表示節點在輪中當選為簇頭節點的平均概率節點。

在節點的剩余能量不一致的情況下，剩余能量高的節點將有更大的概率當選簇頭。表示網絡節點在第r輪的平均能量值，如下：

在第r輪，用當前節點的能量與網絡平均能量做比值，可以得到：

由公式（3）可以看出節點當選簇頭的概率是根據能量比值決定的，節點的剩余能量越多，節點當選簇頭的概率越大。

假設每輪的能量消耗Eround是相同的，并且節點能耗均勻，可以估算出網絡的生命周期為：

其中，Etotal為全網節點初始的總能量；Eround為每一輪全網所消耗的總能量。

由于節點能耗均勻，每輪消耗的能量都幾乎相同，于是得到第r輪節點的平均能量------E(r)為：

簇頭選舉閾值函數T(n)的表達式為：

選舉出的簇頭將會向一定范圍內的節點廣播信息，同時普通節點在接收到入簇指令后，通過選擇最近的簇頭，進行入簇。

多級異構網絡由二級異構網絡推廣而來，將其帶入到公式（3）中，得到：

其中，αi為多于E0的能量倍數。

網絡的全部節點數如公式（9）所示，Ii表示節點的基本輪轉周期，節點成為簇頭的周期為：

當Ei(r)＞，則ni＜Ii，通過上述理論分析，節點能量越高，當選簇頭的概率就會越大。

（2）穩定傳輸階段

經過篩選的簇頭將簇內成員收集來的信息進行整理，并將融合的數據以單跳的方式傳輸數據到Sink節點。

2 仿真模型

2.1 系統的能量模型

系統的能量采用無線電模型。該模型的功能的實現取決于d0的設置。發送數據能耗ETx(l,d)表達式為：

接收數據能耗ERx(l)表達式為：

數據融合能耗Em表達式為：

其中，l為數據包長度；Eelec為發射電路的能量；εfs和εmp為功率放大器的能耗；EDA為單位數據融合能耗；N為簇內成員節點數；若d＞d0，則為多徑衰減模型：反之為自由空間模型。

2.2 系統的網絡模型

為了搭建合理的仿真環境，做出如下假設：

（1）在 100×100的矩形區域中，設置 Sink節點在網絡的中心。

（2）所有的節點的標識號都是唯一的且不會中途發生改變。

（3）所有的節點都是固定不動的，相對的，其坐標也是固定的。

（4）所有節點的硬件配置都是相同的，節點具有的各方面能力都是相同的，并且會按照設置好的通信速率發送數據。

（5）普通節點僅僅負責采集和向簇頭發送數據，簇頭的主要功能是存儲、融合、發送數據，并將融合好的數據發送到Sink節點。

（6）通信鏈路的能量消耗是相同的，且不分主動被動。

（7）假設Sink節點不會死亡并且能量消耗為0。

2.3 算法分析

DEEC是一種基于LEACH并適用于多級能量異構網絡的分布式高能效分簇路由算法。DEEC算法并未考慮網絡中簇頭分布不均、簇頭產生數目不穩定等問題。針對上述問題，目前的解決算法多種多樣，主要差別是參數的改進和算法結構的優化。

通過上述理論分析，DEEC算法的簇首選舉考慮了剩余能量，使得簇頭選擇更加合理。由于簇頭與Sink節點是采用單跳通信的，而在實際應用中，網絡的規模都偏大，這種機制使得該算法不適用于大規模網絡，并且DEEC算法的簇頭選舉僅僅考慮了剩余能量，對于其它影響因素，比如節點之間的距離，可能存在簇頭選擇不合理的情況，加快節點死亡。

CREEP算法在簇首選舉中的概率Pi進行改進，主要將節點距離與平均距離的比值引入到Pi上，該算法同DEEC算法，也考慮了能量因素，但CREEP算法在多跳路徑的選擇中，并未設置合理的參數來限制下一跳的選擇，因此會出現路徑選擇不合理的情況。

3 DEEC-BD算法概述

DEEC-BD算法主要包括兩個方面：

（1）針對簇頭選舉概率Pi進行改進，在考慮剩余節點能量的同時，引入節點距離因子。根據距離的不同選擇不同的距離因子，可以靈活的調整簇頭選舉概率。

（2）設置路徑質量Q(r)，通過對比每條路徑的路徑質量參數，選擇合適的下一跳，緩沖簇頭的壓力，適當的延長網絡的生命周期。

3.1 距離因子

距離因子的形式根據距離閾值產生的，本文設置的距離閾值為D0：

式中，davg為全部節點距Sink節點距離的平均值。

當di≥davg時，Pi概率如下：

式中，di為節點到Sink節點的距離；dmax為節點到Sink節點的最大距離。由本式可知，節點距Sink的距離越小，被選為簇頭的概率相對更大，反之，則更小。

當di＜davg時，Pi概率如下：

如上所述，剩余能量較大、距離Sink節點較近的節點，在簇頭選舉機制中，增大了被選為簇頭的概率。距離Sink節點較遠的節點，在數據傳輸過程中，會耗費更多的能量，從而影響網絡的綜合性能。DEEC-BD算法的簇頭選舉機制，通過設置距離閾值，減少分布在區域邊緣節點被選做簇頭的概率，也減少了由于能量消耗過快而快速死亡的簇頭，即在相同輪數內，網絡能耗減少的同時，網絡的可用節點數量能夠顯著增加。

3.2 路徑質量

利用單跳的形式將數據傳輸給Sink節點是分簇算法的默認方式，但是單跳傳輸會使得簇頭更快死亡，影響網絡的生命周期，數據的傳輸量也會受到影響，因此，多跳機制可以減輕在數據傳輸過程中簇頭的負擔，并能夠適當的延長網絡的生命周期。

多跳機制中下一跳的選擇是重中之重，本文引入路徑質量參數，使得簇頭向Sink節點傳輸數據的時間延長。

網絡的使用范圍，與算法本身的可擴展性息息相關。根據對上述算法的分析，引入了路徑質量參數Q(r)，該參數考慮了簇頭剩余能量和簇頭到Sink節點距離，根據這個參數選擇最優路徑，在能量消耗較少的情況下，傳輸大量數據。

式中，Di為簇頭到Sink節點的距離；Dmax為簇頭到Sink節點的最大距離。

3.3 DEEC-BD算法流程

（1）部署節點、設置基本參數。

（2）計算距離閾值D0，根據di與D0之間的關系，選擇合適的Pi形式，依據改進的簇頭選舉閾值函數計算出該節點簇頭選舉的閾值，選擇合適的簇頭。

（3）該步驟是成簇的最終階段，其主要將那些并未成為簇頭的節點，根據感知的信號強弱，尋找距離自己最近的節點，然后入簇。然后，把從各個區域收集來的數據，發送到簇頭。

（4）簇頭則將簇內節點收集的數據進行融合，利用改進的多跳機制，根據路徑質量參數，選擇合適路徑，將數據傳輸到Sink節點。

（5）網絡開始新的一輪，重復上述步驟，直到全部節點都死亡。

4 仿真結果分析

在仿真分析中，本文主要針對多級能量異構網絡，在死亡節點數（生命周期）、數據傳輸量和能量消耗三個方面。實驗環境設置見1.2、1.3節。

針對Q(r)中的權值α和β的取值，經過仿真，結果如表1所示。

表1 α、β的取值

圖1 權值取值對比圖

根據圖1所示，可以得到α和β的最優取值，仿真參數如表2所示。

表2 仿真參數

4.1 網絡死亡節點數

網絡的死亡節點數表示全網死亡節點隨網絡運行而變化，是一項重要的指標，能夠直觀的顯示網絡生命周期的長短。

由圖2可以得出DEEC-BD算法的節點死亡速度要比DEEC算法的節點速度慢，DEEC-BD算法節點全部死亡為3 251輪，CREEP算法節點全部死亡為2 364輪，即生命周期延長了37.5%。DEEC算法節點全部死亡為1 794輪，即生命周期延長了79%。

圖2 網絡死亡節點數對比

4.2 網絡數據傳輸量

數據傳輸量的大小，是衡量無線傳感器網絡性能是否優越的重要指標，如今，數據呈“爆炸式”增長，傳輸數據量的大小，決定了數據分析的準確率和應用途徑，能夠使功能的實現更加有效。

圖3 網絡數據傳輸量對比

圖3顯示的是DEEC算法、DECH算法與DEEC-BD算法的數據傳輸量。經計算，DEECBD算法的數據傳輸相較于CREEP算法，多傳輸了41.5%的數據。相較于DEEC算法，多傳輸了4.5倍的數據。

4.3 網絡能量消耗

盡可能的節約能量，對于各個研究都是永恒的目標，無線傳感器網絡的能量由于硬件的限制，節點的能量不可能存在無限大的情況。減少能量的消耗，可以使得網絡的數據傳輸更加持久。

圖4 網絡能量消耗對比

圖4顯示的是DEEC-BD算法、DEEC算法與CREEP算法的能量消耗進行對比，經過計算，本文的提出算法相較于CREEP算法的能量消耗低于16.7%，相較于DEEC算法能量消耗低于52%。

5 結語

本文研究的DEEC-BD算法在原算法的基礎上，引入了距離因子和路徑質量兩個參數。原DEEC算法本身僅僅考慮了剩余能量與網絡節點平均能量的比值，而距離因子的引用可以盡量避免那些距離較遠的節點當選為簇頭，從而影響網絡的性能。簇頭與Sink節點之間的數據傳輸形式是單跳的，這種傳播數據的方式，針對大范圍網絡是行不通的，即網絡的擴展性能將受到極大的影響。CREEP算法雖然數據傳輸是多跳機制，如果僅僅把傳輸方式改成多跳，并不加條件限制，那么路徑的選擇就是任意的，在這種情況下，會出現路徑選擇不合理，加快節點的死亡，引入路徑質量是十分有效的約束條件，可以選擇參數較大的簇頭，作為下一跳。通過改進簇頭選舉機制和數據傳輸機制，DEEC-BD算法的性能要優于DEEC算法和CREEP算法的性能。