基于能量均衡的WSNs固定分區路由算法*

李秋巒， 詹國華， 李志華

(杭州師范大學 信息科學與工程學院,浙江 杭州 311121)

0 引 言

隨著無線傳感器網絡(wireless sensor networks,WSNs)被越發廣泛地應用到軍事、環境監測、醫療救護等領域，作為其關鍵技術之一的路由算法也開始成為人們關注的焦點。

WSNs能量有限，故低能耗與負載均衡是其路由算法設計的首要目標[1]。分簇路由可以提高能量利用率、均衡網絡負載，是一種有效的WSNs拓撲管理方式[2]。其主要思想是選擇部分節點作為簇首，簇內成員將數據發送給簇首，簇首將數據融合后發送給信宿。Heinzelman W等人提出的LEACH協議[3](low energy adaptive clustering hierarchy)是早期的一種專為WSNs設計的經典協議。其中定義了“輪(round)”的概念，并創建了時分多址時刻表以記錄成員節點的數據傳輸時隙。

繼承LEACH協議分簇思想的改進協議有很多。DEEC(distributed energy-efficient clustering)算法對簇間通信算法進行了優化，但未解決簇首數量波動大和分布不均勻的問題[4]。鄧仲芬等人提出的EUCR(energy-efficient uniform tree-clustering routing)協議均勻了簇首分布，但未考慮網絡的控制開銷[5]。李成法等人提出的EEUC(energy-efficient uneven cluster)算法基于地理位置對網絡進行規模不等的分簇[6]，平衡了不同位置節點的能耗，但沒有對相關參數進行優化取值。

本文在LEACH算法的基礎上，提出一種基于能量均衡的固定分區路由算法(fixed partition routing algorithm basedon energy balance,FRAEB)。通過計算最優簇半徑進行非均勻分簇以避免“熱區”[7]問題，采用固定分區策略，限制簇首的范圍與數量，引入簇首能量自檢機制，避免過大的控制開銷，同時充分利用節點剩余能量和位置信息，選取最優節點成為簇首。

1 FRAEB流程

本算法包括模型假設、網絡劃分、分區成簇、簇首輪換、數據傳輸五部分，算法流程如圖1所示。

圖1 FRAEB流程圖

在本算法中，首先對網絡結構作出假設，確定網絡能耗模型。然后計算最優簇半徑以解決“熱區”問題，同時采用固定分區策略，限制簇首的范圍與數量，在簇首輪換階段引入簇首能量自檢機制，并將節點能量與位置對簇首選舉的影響進行量化，得到簇首競爭力計算公式。下面將對各部分逐一詳述。

2 模型假設

2.1 網絡模型

本文對WSNs結構作如下假設：

1)信宿節點計算與存儲能力較強，能量不受限。

2)所有傳感器節點結構相同，具有一定的計算和存儲能力，能量受限且初始能量相同，可以感知自身能量和位置信息，發射功率可調。

3)不考慮環境因素對網絡拓撲結構的影響。

2.2 能耗模型

本文采用常見的一階能耗模型，如圖2所示。

圖2 一階能耗模型

該模型的通信能耗計算公式如下所示

(1)

ERx(k)=Eelec·k.

(2)

其中,ETx(k,d)為向距離dm的節點發送kbit數據的能耗；ERx(k)為節點接收kbit數據的能耗；Eelec為節點發送電路和接收電路處理單位數據的能耗；εfs,εmp分別為自由空間模型和多徑衰落模型中放大單位數據并傳輸單位距離所需的能量，可統一用Eamp表示；dcrossover為距離門限值，若傳輸距離d比距離門限值小，則采用自由空間模型，放大能量消耗與d2呈正比；否則，采用多徑衰落模型，能耗與d4呈正比。此外，融合單位數據的能耗為Eda。

3 網絡劃分

在FRAEB中，首先計算最優簇半徑，對網絡進行非均勻劃分，為之后的分區成簇做準備。

當所有節點都部署完畢后，信宿向監測區域廣播消息收集節點位置信息，并由此創建和維護一個傳感器節點信息表，記錄節點標識、位置信息及活躍狀態。之后信宿計算出監測區域面積，并據此將其分為L層，離信宿最近的為第L層，最遠的為第1層。FRAEB網絡結構圖如圖3所示。

圖3 FRAEB網絡結構

計算簇半徑是為了平衡不同簇層能耗，所以，簇半徑的計算應從能量消耗角度出發。根據通信能耗計算公式和Eda可計算出各層簇在一輪數據收集過程中消耗的能量Etotal(i)。本文假設簇首將各成員上傳的kbit數據融合成kbit的數據包轉發給中繼簇首，而中繼簇首只負責轉發此數據包，如圖3所示。

若已知各層簇半徑ri，則可得各層簇個數N(i)

(3)

其中,M為監測區域邊長，并由此得各層的成員節點個數Nnon-CH(i)

(4)

式中N為網絡節點總數。各層簇的能耗來自4個方面：成員節點發送數據的能耗Enon-CH(i)，簇首接收并融合簇內數據的能耗ER&D(i)，簇首接收上級簇首的能耗ER-Sup(i)和簇首將數據轉發給內層簇首的能耗ERelay(i)。由通信能耗公式得Enon-CH(i)

(5)

(6)

同樣，根據通信能耗公式，得到ER&D(i)算式

ER&D(i)=k[Eelec(Nnon-CH(i))+Eda(Nnon-CH(i)+

N(i))].

(7)

簇首接收外層數據能耗ER-Sup(i)算式

ER-Sup(i)=kEelecN(i-1),2≤i≤L,

(8)

式中i=1時ER-Sup(i)=0。ERelay(i)的算式如下

ERela(i)=

(9)

式中h為最內層簇首到信宿的距離。文中令兩層簇首間的距離約等于兩層半徑之和，最內層簇首到信宿距離約等于rL與h之和。至此可求出各簇層總能耗Etotal(i)，其值涉及的變量只有各層簇半徑ri。當各層總能耗相等時，各層簇半徑為最佳簇半徑，故可根據各層總能耗之間的關系，以及各層半徑之和與網絡邊長M的關系列出方程組

(10)

解此方程組即可求得各層最佳簇半徑ri。

4 分區成簇

FRAEB采用固定分區策略，其分區成簇的具體過程分為初始簇首選舉和簇的建立2個步驟。

4.1 簇首選舉

計算出各層簇半徑后，信宿將監測區域進行分層，并將各層劃分成大小相等的區塊(允許每層有個別區塊大小不同)。由于各節點初始能量相同，信宿在各分區選擇離中心最近的節點做為初始簇首。

4.2 簇的建立

信宿選出簇首后，為各節點選擇一個最近的簇首加入，并創建一個簇信息表，包含簇標識、簇首信息和成員信息。其中簇首信息包含自身標識、位置及能量；而成員信息還包含自身數據傳輸時隙。

之后信宿將簇信息廣播到監測區域。傳感器節點查詢自身所屬簇并判斷是否為簇首，若是，則需要創建并維護一個成員節點信息表和一個數據傳輸超時定時器；否則，只需要記錄對應的簇首。之后簇首和使用第一時隙的成員節點切換到正常通信狀態，其他成員節點切換到休眠狀態。

5 簇首輪換

不同于周期性簇首選舉，FRAEB中僅當簇首的剩余能量低于閾值ET時重新進行簇首選舉，該過程充分考慮了節點的能量與位置，具體機制如下。

當前簇首感知自身能量信息，若低于閾值ET，則判定自身失效，并選取剩余能量大于ET的節點作為候選簇首集合，若集合為空，則調整ET并重復上述步驟。ET調整機制由公式(11)表示

(11)

式中ET(i)為第i次閾值調整后的能量閾值，ET(0)為能量閾值的初始值。E0為節點初始能量，c0為迭代因子。當前簇首計算出活躍節點的中心位置，并選取距離中心位置較近且剩余能量較多的節點為新簇首。將節點位置和能量2個因素對簇首選舉的影響進行量化，得到簇首競爭力計算公式

(12)

式中P(i)為候選簇首i的競爭力量化值；dmax為候選簇首與簇中心的最遠距離，di為候選簇首i與簇中心的距離；ER(i)為候選簇首i的剩余能量，ERmax和ERmin代表其中的最大值與最小值；c1,c2分別為候選簇首的位置和能量在簇首競爭力計算公式中的權重。要求c1,c2的取值范圍都為[0,1],且求和為1。

在選舉結束后，若當前簇首當選，則該簇開始工作；否則，當前簇首廣播新簇首消息，并與新簇首完成角色交換，之后該簇開始工作。

6 數據傳輸

6.1 簇內通信

在簇內通信階段，FRAEB除了采用LEACH協議的休眠機制外，還令成員節點根據與簇首的距離來降低發射功率；成員節點將能量信息加在發送數據中，使簇首更新成員節點信息；引入數據傳輸超時定時器，供簇首判定成員節點是否死亡。

6.2 簇間通信

FRAEB在簇間通信階段采用了多跳思想，并結合自身特點加以改善：分簇階段，節點根據所屬簇標識計算下一跳簇層；簇首輪換階段，新簇首調整發射功率以覆蓋將自身作為下一跳簇首的所有簇，這些簇的簇首收到新簇首消息后查看新簇首所屬簇是否屬于下一跳簇集合，若是,則更改該集合相應項，并重新計算最短距離，選擇下一跳簇首。

7 算法仿真

本文采用Matlab對FRAEB算法進行仿真，并與LEACH和DEEC做比較。500個節點均勻部署在250 m×250 m的正方形區域內，信宿節點坐標為(125,300)m?？刂瓢L度和DATA包長度分別為25 bytes和500 bytes。網絡環境仿真參數如表1所示。

表1 仿真環境參數表

首先分析網絡的整體能耗，3種協議下的網絡整體能耗曲線如圖4所示。

圖4 各協議的網絡整體能量消耗

從圖中可見，使用FRAEB的網絡其能耗曲線位于最下方，即經歷相同輪數的情況下能耗最小。接下來分析簇首能耗方差，以判斷簇首能耗是否均衡。取簇首節點能耗的最大值和最小值，按照方差公式進行計算。連續隨機抽取10輪樣本,得出3種協議的簇首能耗方差曲線如圖5所示。

圖5 各協議的簇首能耗方差

圖5顯示了使用FRAEB的網絡中簇首能耗方差最小，且沒有明顯的波動，表明該算法可以較好地均衡網絡中不同區域的能量消耗。節點能耗均衡是延長網絡生命周期最主要的因素，各協議生命周期曲線如圖6所示。

圖6 各協議的網絡生命周期

圖6表明：相比使用其他兩種的網絡，使用FRAEB的網絡所經歷的輪數最多，表明其生命周期最長。很大程度上，這得益于FRAEB基于能耗均衡而設計的特點。

8 結束語

本文在詳細分析以往分簇路由協議的基礎上，創新地將固定分區思想與非均勻分簇思想進行融合，并結合以往協議的優點，提出了一種FRAEB。仿真結果表明：FRAEB有效降低了網絡總體能耗，同時均衡了網絡節點負載，使網絡生命周期得到了較好的延長。

參考文獻:

[1] Olutayo B,Hanh L,Audrey M.A survey on clustering algorithm for wireless sensor networks[C]∥Proceedings of the 13th International Conference on Network-based Information System,IEEE Computer Society,2010:358-364.

[2] 李洪兵,熊慶宇,石為人.無線傳感器網絡非均勻等級分簇拓撲結構研究[J].計算機科學,2013,40(2):49-52,77.

[3] Heinzelman W,Chandrakasan A,Balakrishman H.Energy-efficient communication protocol for wireless sensor networks[C]∥Proceedings of Hawaii International Conference on System Science,Hawaii,USA,2000: 3005-3014.

[4] 魏春娟,楊俊杰,張志美.一種分布式能量有效的無線傳感器網絡分簇路由協議[J].傳感技術學報,2013,26(7):1014-1019.

[5] 鄧仲芬,石為人,黃 河,等.一種基于樹均勻分簇的WSNs節能路由協議[J].傳感器與微系統,2011,30(5):47-50.

[6] 李成法,陳貴海,葉 懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,2007,30(1):27-36.

[7] Soro S,Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering[C]∥Proceedings of the 5th International Workshop on Algorithms for Wireless,Mobile,Ad Hoc and Sensor Networks,Denver,Co,USA,2005.

[8] Heinzelman W,Chandrakasan A P,Balakrishnan H.An application specific protocol architecture for wireless micro-sensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):1536-1276.