能耗均衡的無線傳感器網絡兩級路由協議

摘 要:傳感器網絡分簇路由協議研究的一個關鍵問題是如何最優化組簇，既能有效降低簇內節點能耗，又能均衡整個網絡能耗。為此，提出一種能耗均衡的網絡兩級分層分簇路由協議。協議底層應用PSO算法實現網絡節點最優化分簇;上層選擇總簇頭節點負責收集、融合簇頭數據并發送至基站。仿真結果表明，本協議能有效降低節點死亡速度，延長網絡生存周期。

關鍵詞:傳感器網絡;分簇路由協議;粒子群優化算法;網絡生存周期

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1142-03

doi:10.3969/j.issn.1001-3695.2010.03.093

Energy-balanced clustering routing protocol of two-layer hierarchy forwireless sensor networks

JIANG Chang-jiang， SHI Wei-ren， XIANG Min， ZHANG Ying

(College of Automation， Chongqing University， Chongqing 400044， China)

Abstract:The most important problem of the clustering protocol for WSN is how to cluster all nodes with the optimization way， which can not only decrease the energy consumption of the nodes， but also balance the energy dissipation of the entire network. Therefore，this paper proposed a new centralized clustering protocol of two-layer hierarchy， which was compact， energy-aware and energy-consumption-balanced. In the lower layer of the protocol， the optimal cluster of all nodes using PSO algorithm was realized. And in the upper layer， the chief-cluster-head， which was responsible for collecting， aggregating the data of all cluster heads and sending the fused data to the base station， was selected. Simulation results demonstrate that the protocol can efficiently decrease the dead speed of the nodes and prolong the network lifetime.

Key words:wireless sensor network(WSN); clustering routing protocol; PSO algorithm; network lifetime

0 引言

近年來，無線傳感器網絡(WSN)，在環境與軍事監控、地震與氣候預測，以及外層空間探索等許多方面具有廣泛的應用前景，受到越來越多研究者和工程技術人員的關注。由于無線傳感器網絡節點通常采用能量非常有限的微型電池供電，并且在部署后難以二次補充能量，如何降低單個節點能耗和平衡所有節點能耗，避免個別節點因過度消耗能量而過早死亡，以延長網絡生存時間，成為無線傳感器網絡路由協議研究的一個關鍵性問題。

在WSN中，路由協議從網絡拓撲結構的角度可以分為平面路由協議和分簇路由協議。分簇路由協議將網絡分成若干簇，并選擇簇頭節點負責簇內數據的收集、融合并傳送至基站，研究和實驗表明[1，2]，它能高效地管理網絡數據和降低網絡能耗，有效延長網絡生存周期。分簇路由協議實現的關鍵問題是，如何在節點剩余能量隨網絡運行不斷減少時，動態快速有效地尋找一組最佳節點擔任簇首，既能減少簇內節點能耗，又能使簇首均勻地分布在網絡中，整個網絡能量消耗均衡，這是一個NP難問題[3]?；谌褐悄芊椒ǖ腜SO算法，能夠簡單、快速地搜尋最優解，適合于解決這個難題[4]。

國內外學者基于PSO算法提出了多種網絡分簇路由算法和協議。梁英等人[5]提出運用PSO算法優化分簇過程，避免簇內節點過早地出現盲節點現象。但由于是在LEACH算法預分簇的基礎上運用PSO優化簇首選擇，不能有效控制網絡分簇的均勻性和合理性，而且優化過程需要消耗額外的能量。鄒學玉等人[6]提出基于離散粒子群(DPSO)的單跳路由分簇協議(DPSOCA)。該協議應用DPSO優化簇首選擇過程，采用無競爭開銷的方式選舉一組最佳節點擔任簇首，能有效地均衡網絡節點的能量消耗和顯著地延長網絡壽命。但是，該協議假設所有節點初始能量相同，位置信息已知，適用范圍有一定局限性。J. Tillett等人[7]應用粒子群算法解決網絡分簇問題，提出均勻分簇(每個簇的節點數量及候選簇頭數量相等)的思想以最小化節點能耗。但對于節點分布不均勻的網絡，這種分簇方法可能造成各簇數量規模相等，而幾何規模差異較大的情況，從而使得簇間消耗能量不均。Latiff等人[8]提出一種具有能量感知能力的分簇策略，采用PSO算法優化選擇分簇方式，既能最小化簇內距離，又能最優化網絡能耗，與LEACH和LEACH-C比較，該協議能有效延長網絡生存周期。但由于沒有考慮到簇頭節點傳輸信息至基站時的能耗不均，當基站位于目標區域以外時，該協議將導致距離基站較遠的節點成塊死亡，網絡能量消耗不均衡。

根據以上分析，本文提出能耗均衡的兩級分層體系結構的分簇路由協議，以降低單個節點能耗，平衡網絡能耗，從而延長網絡生存時間。協議底層應用文獻[8]提出的方法實現網絡節點優化分簇。第二層設置總簇頭節點負責收集、融合簇頭節點數據并發送至基站，以平衡各簇頭節點發送信息至基站的能耗。

1 系統模型

1.1 無線傳感器網絡模型

本文假設無線傳感器網絡具有如下性質，與文獻[1]相似:所有節點固定并且能量有限;節點通信功率可調;所有節點都能夠充當簇頭節點或普通節點;采用數據融合技術減少傳輸的數據量;每個節點周期執行數據采集任務，并始終有數據傳送至基站;基站位置固定且位于監測區域外，基站能量無限。

1.2 無線通信能耗模型

本文采用與文獻[1]相同的無線通信能耗模型，即一階無線通信模型(the first order radio model)。在該模型中，無線通信模塊具有功率控制能力，能夠使用最小的能量將數據發送給希望的接收者。在保證合理信噪比(SNR)條件下，節點發送數據能耗為

ETx(k，d)=Eelec×k+Eamp×k×d2

(1)

其中:k為發送的二進制位數;d為發送距離;Eelec(nJ/bit)為射頻能耗系數;Eamp(pJ/bit/m2)為電路中放大器能耗系數。

節點接收數據能耗為

ERx(k)=Eelec×k(2)

本文仿真中，無線通信能耗模型參數設置為:Eelec=50 nJ/bit，Eamp=10 pJ/bit/m2。數據融合模型假設為:簇頭接收每個節點發送的k bit數據，無論簇內節點數目多少，均壓縮為k bit數據;總簇頭節點接收K個簇頭節點發送的K×k bit數據，壓縮為(K/2)×k bit數據。數據融合的能耗設定為ED=5 nJ/bit。

2 分簇路由協議描述

2.1 粒子群算法

粒子群優化(PSO)算法由Kennedy和Eberhart[4]共同提出，其思想源于鳥群和魚群群體運動行為的研究，是一種基于群智能方法的演化計算技術，是演化計算領域中的一個新的分支。

假設在D維搜索空間中，有m個粒子組成一群體，第i個粒子在D維空間中的位置表示為xi=(xi1，xi2，…，xiD)，第i個粒子經歷過的最好位置(有最好適應度)記為Pi=(pi1，pi2，…，piD)，每個粒子的飛行速度為Vi=(vi1，vi2，…，viD)，i=1，2，…，m。在整個群體中，所有粒子經歷過的最好位置為Pg=(pg1，pg2，…，pgD)，每一代粒子根據下式更新自己的速度和位置[4]:

vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid)(3)

xid=xid+vid(4)

其中:w為慣性權重;c1和c2為學習因子;r1和r2是[0，1]之間的隨機數。公式由三部分組成:a)粒子先前的速度，說明了粒子目前的狀態;b)認知部分，是從當前點指向此粒子自身最好點的一個矢量，表示粒子的動作來源于自身經驗的部分;c)社會部分，是一個從當前點指向種群最好點的一個矢量，反映了粒子間的協同合作和知識的共享。

2.2 協議描述

協議采用與文獻[1]相似的輪回機制，每一輪包括兩個階段，即簇的建立和穩態階段。簇的建立采用集中式控制策略，在基站完成，包括四個步驟:收集節點信息、執行分簇算法進行網絡分簇、確定總簇頭節點、發布分簇信息。

2.2.1 簇的建立

1)收集節點信息 分簇算法要實現網絡優化分簇，需要知道所有節點的位置和能量信息。具有任意初始能量的節點隨機部署以后，在首次簇的建立階段，節點首先發送位置和初始能量信息至基站，基站接收信息以后保存。則在以后各輪中，基站可以通過每輪分簇信息估算節點能耗，得到每輪節點的能量信息，并且節點位置固定，故節點不需要再發送位置和能量信息到基站。

2)分簇算法 協議底層分簇算法采用文獻[8]提出的算法。首先，基于所有節點的能量信息，基站計算節點的平均能量，節點能量大于或等于平均能量的節點為候選簇頭節點，簇頭在候選簇頭節點中產生。設定候選簇頭節點縮小簇頭選擇范圍，并保證最終選出的簇頭節點具有較大的能量，更有能力擔當簇頭的角色。

假設網絡包含N個節點，預先定義分為K個簇，候選簇頭節點數為M(一般情況M>>K)，則可能的分簇方式有CKM種，在其中確定最佳的分簇方式，是一個最優化問題。應用PSO算法解決這個問題，使每一個粒子代表一種可能的分簇方式，用目標函數評價其性能，設置m個粒子組成群體在CKM種可能的簇頭組合方式中尋找最優解，使目標函數取得最小值。該目標函數定義如下[8]:

cost=βf1+(1-β)f2(5)

f1=maxk=1，2，…，K{ni∈Cp，kd(ni，CHp，k)/|Cp，k|}(6)

f2=Ni=1E(ni)/Kk=1E(CHp，k)(7)

其中:f1為分簇緊湊性評價因子，等于節點至對應簇頭的最大平均歐氏距離;|Cp，k|是粒子p中簇Ck的節點數目;f2為簇頭能量評價因子，等于網絡中所有節點ni(i=1，2，…，N)當前能量之和除以簇頭節點當前能量之和;β為各評價因子的權重系數。根據目標函數的定義，最小的適應值表明對應的分簇方式同時滿足:a)節點至對應簇頭的平均歐氏距離較小，即簇的幾何大小緊湊，由f1量化;b)簇頭能量之和較大，由f2量化。這樣的網絡分簇能最小化簇內能耗，均衡網絡能耗，以最大限度延長節點和網絡生存時間。

3)確定總簇頭節點 由于簇頭節點既要負責收集、融合簇內所有節點數據，又要發送信息至基站，其能耗遠遠高于普通節點，網絡節點能量消耗不均衡。而且，由于基站遠離監測區域，不同簇頭節點發送信息至基站能耗差異較大，造成簇頭節點間能量消耗不均衡，距離基站更遠的節點死亡速度較快。為此，設置總簇頭節點負責收集、融合簇頭節點數據，并發送數據至基站。這樣可以均衡簇頭節點和普通節點及各簇頭節點間能耗，并且通過數據融合減小發送信息至基站的總能耗。

總簇頭節點的選擇綜合考慮節點能量、與各簇頭節點距離和與基站距離三個方面的因素。首先，在每個簇中選擇能量最大的節點(不包括簇頭節點)為候選總簇頭節點;然后， 計算每個候選總簇頭節點的評價函數，具有最小評價函數值的候選總簇頭節點成為總簇頭節點。評價函數定義如下:

cos (HCHi)=αf1+ηf2+λf3(8)

f1=maxk=1，2，…，K{E(HCHk)}/E(HCHi)(9)

f2=Kj=1d(HCHi，CHj)/

maxk=1，2，…，K{Kj=1d(HCHk，CHj)}(10)

f3=d(HCHi，BS)/maxk=1，2，…，K{d(HCHk，BS)}(11)

其中: f1為候選總簇頭節點能量評價因子，等于最大候選總簇頭節點能量除以候選總簇頭節點能量; f2為候選總簇頭節點至所有簇頭節點距離評價因子，等于候選總簇頭節點至所有簇頭節點距離之和除以其最大值; f3為候選總簇頭節點至基站距離評價因子，等于候選總簇頭節點至基站距離除以其最大值;α、η、λ為各評價因子權重系數。最小的評價函數值表明對應的候選總簇頭節點具有較大的能量，與各簇頭節點距離之和較小，與基站距離較近。該節點成為總簇頭節點能平衡簇頭節點發送數據至總簇頭節點能耗和總簇頭節點發送數據至基站能耗，以減小單個節點能耗，均衡所有網絡節點能耗。

4)發布分簇信息 基站發布分簇信息至每個節點，網絡分簇完成，進入穩態階段。

2.2.2 穩態階段

穩態階段簇頭節點首先完成簇內數據收集、融合的任務，采取與文獻[1]相似的方法。根據簇內節點數量，簇頭節點創建TDMA進度表，確定每個節點傳送數據的時間，并廣播簇內節點，數據傳輸開始。非簇頭節點的無線通信模塊關閉，直到分配的傳輸數據時間到來，這樣可以節約節點能量。簇頭節點完成所有成員節點數據收集后進行數據融合，并發送融合數據至總簇頭節點?？偞仡^節點接收所有簇頭節點信息后，進行數據融合，并發送至基站。

3 協議仿真及分析

為了驗證本文提出的分簇路由協議的有效性，利用MATLAB進行仿真，并與LEACH協議和文獻[8]提出的PSO-C協議相應性能進行比較。將100個傳感器節點隨機部署在500 m×500 m的范圍內;數據包長度為2 000 bit，數據包頭長度為50 bit;簇的數量設定為節點總數的5%，則K=5;基站坐標(250，1 000)，位于網絡外部。PSO算法參數設置為:種群規模Q=30，c1=c2=2，慣性權重隨時間變化w=0.9至w=0.4;評價因子權重系數β=0.5，α=0.3，η=0.1，λ=0.6。節點初始能量分兩種情況設定:所有節點初始能量等于0.5 J;節點初始能量不相等，20%為0.4 J，80%為0.8 J。

本文定義網絡生存時間為30%節點死亡的時間。圖1顯示了節點初始能量相同時，三種協議的網絡生存時間對比，本文協議為78輪，較PSO-C(57輪)和LEACH(43輪)分別延長了36.8%和81.4%。圖2顯示了節點初始能量不同時的對比曲線，本文協議(122輪)較PSO-C(84輪)和LEACH(56輪)分別延長了45.2%和117.9%。說明本文協議能更好地均衡網絡中所有節點的能耗，避免個別節點因過度消耗能量而快速死亡，延長了網絡生存時間。節點初始能量不同時，網絡初始能量分布不均衡，本文協議更能發揮其作用。

圖3和4分別顯示了節點初始能量相同和不相同時，三種協議死亡節點的分布情況。LEACH和PSO-C協議的死亡節點集中在距離基站較遠的區域，出現節點成塊死亡的情況;而本文協議的死亡節點在網絡中分布較均勻，整個網絡能量消耗均衡。

4 結束語

本文基于PSO算法提出兩級分層的無線傳感器網絡分簇路由協議。仿真實驗證明，比較LEACH和PSO-C協議，能有效均衡網絡能耗，降低節點死亡速度，延長網絡生存周期。后續的研究工作可能包括網絡分簇個數與路由協議的相互關系、總簇頭節點的選擇算法優化，以及PSO算法的參數優化等。

參考文獻:

[1]

HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Annual Hawaii International Conference on System Sciences.Washington DC:IEEE:Computer Society，2000:8020-8029.

[2]HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1(4):660-670.

[3]BOLLOBAS B.Random graphs[M].[S.l.]:Academic Press，1985.

[4]KENNEDY J，EBERHART R C.Particle swarm optimization[C]//Proc ofIEEE International Conference on Neural Networks.1995:1942-1948.

[5]梁英，于海斌，曾鵬.應用PSO優化基于分簇的無線傳感器網絡路由協議[J].控制與決策， 2006，21(4):453-456.

[6]鄒學玉，曹陽，劉徐迅，等.基于離散粒子群的WSN分簇路由算法[J]. 武漢大學學報:理學版，2008，54(1):99-102.

[7]TILLETT J， RAO R，SAHIN F.Cluster-head identification in Ad hoc sensor networks using particle swarm optimization[C]//Proc ofIEEE International Conference on Personal Wireless Communications.2002:201-205.

[8]LATIFF N M A，TSIMENIDIS C C，SHARIF B S.Energy-aware clustering for wireless sensor networks using particle swarm optimization[C]//Proc of the 18th International Symposium on Personal， Indoor and Mobile Radio Communications.2007:1-5.