能耗均衡的低功耗自適應集分區路由改進算法

劉 濤， 龐 博

(西安科技大學通信與信息工程學院， 西安 710054)

無線傳感器網絡(wireless sensor networks，WSNs)作為一種自組織網絡，因其成本低廉、節點體積小等特點，被廣泛應用在各種無人到達的復雜惡劣環境中[1-3],如監測山體滑坡、環境監測、泥石流預警等。然而WSNs也存在巨大缺陷，節點自身能量有限，實際情況下無法更換電池，一旦電池能量消耗完畢，節點失效，大量無效節點的出現就會破壞網絡整體連通性，網絡生存周期會縮短。因此，設計能量高效的路由算法成為國內外的熱點研究問題[4]。

WSNs路由算法主要分為平面路由算法和分簇路由算法。其中分簇路由算法將整個網絡劃分為多個簇，每一個簇群由簇首進行管理，具有層次性，便于管理和網絡延伸擴展，已成為當前應用最廣，最受關注的WSNs路由算法[5-6]。Tang[7]提出一種基于非均勻分區的雙簇頭節能路由算法，該算法根據節點距基站距離將WSN劃分為不均勻分區，在每個分區內選舉主簇頭(primary cluster head， PCH)和副簇頭(secondary cluster head， SCH)，簇間采用最小生成樹算法進行數據傳輸，該方法能夠有效延長WSNs壽命，避免熱區現象，但簇間路由多跳傳輸時，只考慮了下一跳的距離因素，未考慮下一跳轉發節點的剩余能量。Anzola等[8]提出了一種基于k-d 樹的分簇路由算法，采用空間分區將節點組織成簇，在簇頭選擇上提出反應式簇頭形成機制，該算法相比LEACH提高了網絡吞吐量和降低了時延，但該算法穩定階段采用單跳方式傳輸數據，導致簇頭節點能量消耗過快，節點間能耗不均衡。戚攀等[9]提出一種智能分層路由FCM-SI(WSN hierarchical routing algorithm based on Fuzzy C-Means clustering and Swarm Intelligence)，利用模糊C-均值(fuzzy C-means， FCM)對WSNs進行分簇，同時通過人工蜂群算法選舉簇群內部最優節點當選簇頭，在數據傳輸時利用蟻群算法建立多跳路由機制，該算法能有效提高節點能量利用率，延長網絡壽命，但由于基站附近簇頭承擔更大轉發負載，相比其他節點耗能加快，容易出現“熱區”現象。Fakhrosadat等[10]提出一種基于模糊聚類的路由算法FSFLA(fuzzy shuffled frog leaping algorithm)，該算法采用蛙跳優化算法對Mamdani模糊規則進行優化，該方法分簇效果比較好，但采用單跳的數據傳輸方式，并不適合大規模WSNs使用。

針對上述研究存在的問題，提出一種基于分區的LEACH改進算法，該算法對閾值函數進行優化，為降低基站附近作為數據轉發的簇頭節點的能耗，避免能量空洞現象的發生，對監測區域進行分區，針對不同的分區，采取不同的數據傳輸方式，并對簇間數據轉發路由進行改進。

1 系統模型

1.1 網絡模型

為防止其他外部因素影響，對監測區域內部署的WSNs做如下假設。

(1)所有節點構造一樣且具有相同初始能量。

(2)網絡初始化之后，所有節點不可移動。

(3)基站唯一，具有無限的處理能力。

(4)所有節點可直接與基站進行通信。

(5)每個節點具有唯一標識，可獲取自身位置信息。

(6)傳感器節點可自動調節發射功率大小。

1.2 能耗模型

采用一階無線電能量模型[11-12]來計算節點能耗，模型如圖1所示。

由圖1的一階無線電能量模型可知，發送端發送傳輸距離為d的l比特數據的能耗為

(1)

接收端接收l比特數據的能耗為

ER(l)=lEelec

(2)

閾值d0計算公式為

(3)

2 LEACH算法

LEACH是一種層次型分簇路由算法[8]。該算法的核心思想采用了“輪”的概念，每輪節點會根據閾值函數重新選舉簇頭，當選過簇頭的節點不再會當選簇頭，保證每個節點都有機會成為簇頭節點。一輪開始時，整個算法過程被分為簇群建立和數據傳輸兩個階段，簇群建立階段根據節點生成的隨機數與閾值進行比較選取出簇頭進而建立簇群，之后的數據傳輸階段簇頭壓縮成員節點采集的數據發送給基站。閾值T(n)定義為

(4)

式(4)中：p表示預期當選簇頭個數占總節點個數比例；r為當前輪次；mod為取模運算符；G表示最后1/p輪還未當選簇頭的節點集合。

3 改進的LEACH算法

LEACH算法在簇頭選舉時，未考慮其他因素對簇頭選取產生的影響，節點當選簇頭完全隨機，存在距離基站較遠低能量節點當選簇頭的可能性，造成節點無線通信能耗急劇增大。一些基于LEACH改進的路由算法，通過單跳和多跳相結合的方式[13]，克服了簇間能耗不均問題，但沒有考慮到基站附近簇頭節點由于承擔距離基站較遠的簇頭節點所轉發的數據信息，節點能量消耗過快，致使基站附近區域出現“能量空洞”問題。為解決以上問題，提出了一種改進算法，根據節點剩余能量、鄰居節點數以及節點距基站距離因素對簇頭選舉產生的影響，該算法對閾值函數進行優化；為避免基站附近出現能量空洞問題，對部署區域進行分區，在不同的分區采取不同的數據傳輸方式，對簇間多跳數據轉發方式進行改進。

3.1 閾值優化

3.1.1 剩余能量因子

隨著WSNs的不斷運行，網絡中的傳感器節點能量不斷下降。能量消耗較大的節點，如果重復多次被選舉為簇頭節點，將會因為能量下降過快，過早死亡。因此，簇頭選舉時節點剩余能量應被考慮在內。文獻[14]對閾值函數T(n)進行優化，引入了剩余能量因子，即

(5)

式(5)中：Ei，cur為節點i的剩余能量；E0為節點初始能量。將式(5)進行改進，定義新的剩余能量因子E為

(6)

式(6)中：Ei，cur是節點i的剩余能量；Emin和Emax分別表示節點剩余能量的最小值和最大值。從式(6)可看出，剩余能量因子在設置上，考慮了節點i的剩余能量在當前輪次下所處的能量等級，不會因為節點i的剩余能量隨著時間運行而減少，導致剩余能量因子權重一直降低，在網絡運行后期，新剩余能量因子有更好的性能表現。式(6)中E能降低低能量節點當選簇頭的可能性。

3.1.2 距離因子

WSNs中傳感器節點之間，通過無線通信的方式進行數據傳輸。根據圖1的無線電能量模型以及式(1)、式(2)可知，發送相同比特的數據信息時，距離越遠，消耗的節點能量越多。因此，距離因素在簇頭選舉時必須被考慮在內。

文獻[15]提出的基于LEACH的分區路由算法中引入距離因子修正簇頭閾值選舉函數，采用的是節點距基站(Sink節點)的距離因子，即

(7)

式(7)中：di代表節點i和基站之間的距離；dmax和dmin分別表示網絡中節點距基站距離的最大值和最小值。

通過圖1和式(1)可知，傳輸相同比特數據，傳輸距離越大，消耗的能量越多，尤其當d≥d0時，傳輸數據消耗的能量由正比傳輸距離平方轉變為正比傳輸距離四次方。根據閾值d0對能耗計算公式產生的影響，對式(7)進行優化改進，重新定義距離因子為

(8)

式(8)中，d0計算方法為式(3)；di代表節點i和基站之間的距離；dmax表示節點距基站距離的最大值。重新定義的距離因子D以閾值d0為分界線，根據傳輸距離d的大小，設置兩種不同的距離因子。當di

3.1.3 鄰居節點數

待選簇頭競爭半徑以內節點數的多少，影響最終形成的簇群大小。因此，節點的鄰居節點數在簇頭選舉時，必須被考慮在內。

根據式(9)計算節點i的競爭半徑[16]，即

(9)

式(9)中：dmax和dmin分別表示節點與基站之間距離的最大和最小值；di_Sink表示節點i與基站之間的距離；c是用來控制取值范圍；Rmax為節點競爭半徑最大取值。這里取Rmax=d0限制節點競爭半徑最大不得超過d0。

節點i的鄰居節點數定義為

M={NUM|di,j≤Ri,Nodei≠Nodej}

(10)

式(10)中：di,j為節點Nodei和Nodej之間的距離；Ri為Nodei節點的競爭半徑。

3.2 分區

簇間采用多跳數據轉發方式時，基站附近簇頭將會承擔更重的轉發壓力，能耗耗盡大片簇頭節點死亡導致發生“能量空洞”現象。為減輕基站附近簇頭節點的壓力，改善能量空洞問題，對WSNs部署區域進行分區。如圖2所示，以基站節點為圓中心，分別以距離R、距離d0為圓半徑進行分區(0

圖2 部署區域分區模型

區域I作為距離基站最近的區域，區域內的傳感器節點只有兩種工作任務：①獲取節點自身周圍環境的感知數據信息；②對來自區域II和區域III的簇頭節點的數據信息，進行融合處理并轉發給基站節點。區域I內的節點主要作用就是為了減輕基站附近簇頭節點轉發數據的工作量，避免能量空洞問題。區域I面積大小占部署區域的比重定義為

(11)

式(11)中：R為區域I圓形面積的半徑；AreaM為正方形部署區域的邊長。

區域II和區域III內的節點進行簇頭選舉，成簇操作。采取簇內直接通信，簇間簇頭節點間多跳傳輸的通信方式。根據一階無線電能量模型可知，區域II和區域III兩個區域內簇頭節點采用不同的能耗計算公式，對簇頭閾值函數選取進行優化，即

(12)

(13)

式(13)中：T(n)為LEACH算法的閾值函數；α、β、γ分別為剩余能量因子、距離因子、鄰居節點數的權重系數，取值均在0～1，三者系數之和為1；N為網絡中節點總個數。

3.3 數據傳輸階段

針對LEACH算法采用直接通信的方式傳輸數據給基站存在簇頭節點能量消耗過快的缺點，目前常采用簇間單跳和多跳相結合的傳輸方式，有效減少簇頭節點轉發能耗。但此方法選擇的轉發路徑并非最優，在選擇下一跳轉發節點時未考慮簇頭節點與基站之間的方向性問題，為此考慮到簇頭節點數據轉發的方向性問題以及下一跳轉發節點的剩余能量對多跳的數據傳輸方式進行改進，選擇最優下一跳轉發數據節點的選擇函數計算公式為

f(i,j)=

(14)

Node(j)∈Area1

(15)

式(15)中：d[Ci,Node(j)]和d[Node(j),Sink]分別表示簇頭節點i距區域I內節點j之間的距離和區域I內節點j與基站之間的距離。

3.4 改進算法流程圖

改進LEACH算法流程如圖3所示。

圖3 算法流程圖

4 實驗仿真與分析

本實驗在Windows平臺下，使用MATLAB R2012a軟件對改進算法進行代碼仿真，并跟LEACH、LEACH-EDP[17]算法進行性能比較。具體實驗參數如表1所示。

表1 仿真實驗參數

4.1 確定權重系數

為確定權重系數對WSNs造成的影響，進而選出最佳的權重系數比，通過實驗仿真測試多組不同權重系數下WSNs總能量的消耗情況，如圖4所示。從圖4中可以看出在相同輪次下，a=0.6，b=0.1，c=0.3所對應的曲線，在所有曲線中消耗的總能量最少，這表明此曲線對應的WSNs節點能量利用率最高，由此確定最優的權重系數為α=0.6，β=0.3，γ=0.1(這里a代表α，b代表γ，c代表β)。

圖4 不同權重系數下網絡消耗的總能量

4.2 區域I大小設置

區域I內節點主要作用是為了減輕基站附近簇頭節點數據轉發的負載壓力，降低能量空洞現象的發生。區域I設置越大，網絡中直接與基站進行數據通信的節點數目增多，分簇結果不明顯，WSNs的穩定性會受到影響；若區域I設置的比較小，區域I則無法起到緩解基站附近簇頭節點的轉發負載壓力的作用。為了確定區域I的大小對能量空洞問題產生的影響，進而選出最優的區域I，本文中通過比較區域II內節點數先后輪次的變化情況，作為衡量區域I對能量空洞的抑制能力。根據式(11)，針對區域I面積占部署區域比重R取值進行多次實驗，結果如表2所示。

表2 區域II內節點數的變化情況

第一死亡節點時間(first node dead,FND)是衡量傳感器網絡穩定性的重要性能評價指標，是首要考慮的因素，第一死亡節點時間越靠后，代表網絡穩定性越好。區域II內節點數前后變化越緩慢，表示區域I內節點對簇頭節點的數據轉發負載壓力分擔效果越好，能夠很好抑制能量空洞現象的發生。從表2可知，當區域I面積大小占部署區域的比重R=10%時WSNs的穩定性最好，區域II內節點數最終清零處在1 046輪次，在所有數據中最靠后，同時該比重下網絡生命周期也有不錯的表現。這說明在此情況下，區域I內的節點能夠最大程度降低基站附近簇頭節點的數據轉發負載，均衡簇頭節點間能耗。

4.3 節點存活數

圖5為網絡存活節點個數圖。從圖5可知，在729輪時LEACH第一個死亡節點出現，在759輪LEACH-EDP算法第一死亡節點出現。直到899輪本文提出的改進算法第一死亡節點才出現，對比于LEACH、LEACH-EDP算法時間分別推遲了23.32%和18.44%。LEACH算法全部節點死亡在1 094輪，LEACH-EDP算法全部節點死亡在1 191輪，而本文算法全部節點死亡時間出現在1 447輪，比LEACH、LEACH-EDP網絡壽命分別延長了32.27%、21.49%。以上分析可得出，改進算法在網絡整體穩定性、延長網絡壽命方面要優于LEACH、LEACH-EDP算法。這是因為本文算法考慮了節點剩余能量、鄰居節點數以及距基站距離因素，對于不同分區采取不同閾值選舉函數，選擇綜合能力優秀的節點作為簇頭，降低節點能耗，延緩節點死亡時間。

圖5 網絡存活節點個數

4.4 網絡剩余能量

圖6是網絡剩余能量變化圖。從圖6可知，相同輪次下本文算法WSNs中剩余能量是最多的。大約在1 200輪，LEACH和LEACH-EDP算法網絡中已經沒有剩余能量情況下，本文算法網絡中大約還有1 J的剩余能量，在網絡節點能量利用率方面要優于LEACH和LEACH-EDP算法。這主要是因為改進算法的簇頭選取方式更加合理，有效降低節點通信能量損失。

圖6 網絡剩余能量

4.5 剩余能量方差

圖7是剩余能量方差變化圖。由圖7可知，LEACH算法的節點剩余能量方差最大。本文算法節點剩余能量方差要遠小于LEACH和LEACH-EDP算法，說明本文算法中傳感器節點的剩余能量與所有節點剩余能量的平均值差值的平方是最小的，WSNs的節點能耗更加平均。這是因為部署區域分區使得基站附近簇頭節點能耗降低，同時改進的簇間多跳傳輸方式降低了轉發節點的能耗。

圖7 節點剩余能量方差的變化趨勢

5 結論

本文提出的改進算法，通過分析三種不同因素對簇頭選舉產生的影響，優化簇頭閾值選舉函數；對部署區域進行分區操作，不同區域采用不同的數據傳輸方式，減緩基站附近簇頭節點的數據轉發工作量，避免基站附近“能量空洞”，并對簇間多跳轉發方式進行改進。通過與LEACH、LEACH-EDP算法進行實驗對比得到以下結論。

(1)本文提出的改進算法相比于LEACH、LEACH-EDP算法第一死亡節點出現輪次分別推遲了23.32%、18.44%，全部節點死亡出現輪次分別延長了32.27%、21.49%，可知該算法能夠有效提高WSNs的穩定性，提高網絡壽命。

(2)本文提出的改進算法在剩余能量方差方面表現要優于LEACH、LEACH-EDP算法，可知該算法能夠有效均衡所有節點間的能耗，降低節點間的能量差異。