一種帶有孤立節點的DEEC改進算法

【摘要】針對無線傳感器網絡能量受限的問題，在DEEC算法的基礎上，提出了一種帶有孤立節點的分簇算法。以DEEC算法確定簇頭后，改進節點加入簇的機制，從而降低節點的能耗，延長網絡的生存時間。仿真實驗結果表明，與LEACH和DEEC分簇算法相比，網絡生存時間延長了約30%，在數據傳輸效率、負載均衡度、網絡能耗等方面具有更好的性能。

【關鍵詞】無線傳感器網絡；分簇算法；孤立節點；DEEC；網絡生存時間

中圖分類號：TP301.6 文獻標識碼：A 文章編號：

An Improved DEEC Algorithm With Isolated Nodes

Zhu Lihua，Jiang Kaifeng

Chi Zhou vocational technical college， chizhou， 247100 ，China

Abstract： Aim at the characteristic of energy heterogeneous for wireless sensor network， a clustering algorithm with isolated nodes based on the DEEC algorithm is proposed. The mechanism of nodes joined in cluster is improved. So the energy consumption is reduced， the network lifetime is prolonged. Simulation results show that the network lifetime is prolonged about 30%， compared with LEACH and DEEC algorithms. There is a better network performance than the LEACH and DEEC algorithms in data transmission efficiency， energy consumption， load balancing degree， etc.

Keywords： wireless sensor network； clustering algorithm； isolated nodes； DEEC； network lifetime

0 引言

無線傳感器網絡（Wireless Sensor Network，WSN）是由一組傳感器節點自組織形成的一個無線網絡。傳感器節點能量受限，而且能量難以補充，決定了傳感器網絡的生存時間是有限的。實驗表明，傳輸一個比特所消耗的能量比運算處理一個比特消耗的能量大[1]，為了延長網絡的生存時間，除了設計低功耗的傳感器節點外，還需要設計能量有效的網絡通信協議。

基于分簇的路由協議是將網絡劃分為不同的簇（cluster）。在簇內選舉出一個簇頭（cluster head），簇內節點直接和簇頭通信，而簇頭之間采用單跳或者多跳技術與sink節點通信，減少通信量，有利于減少節點參與路由計算的數量，降低整個網絡的能量開銷，延長網絡的生存時間，適合大規模網絡[2]。

分布式能量有效成簇算法DEEC（Distributed Energy-Efficient Clustering Algorithm）是一種典型的基于分簇的路由算法。其基本思想是通過所有節點輪流成為簇頭，以達到節點均勻消耗能量、延長網絡生存時間的目的。而選舉簇頭節點的概率與節點當前剩余的能量直接相關，每個節點成為簇頭節點的輪數根據其初始能量和剩余能量的差別而不相同，即簇頭輪轉周期適應節點的能量變化，具有較高初始能量和剩余能量的節點比低能量節點有更多的機會成為簇頭節點[3，4]。

本文在DEEC算法的基礎上，提出了一種帶有孤立節點的改進算法，稱之為DEEC-WIN（DEEC Algorithm With Isolated Nodes）算法。仿真實驗結果表明，DEEC-WIN算法與LEACH和DEEC分簇算法相比，網絡生存時間提高了約30%，在數據傳輸效率、負載均衡度、網絡能耗等方面具有更好的性能。

1 典型分簇算法

在分簇算法中，簇內節點將采集到的信息傳輸給相應的簇頭，由簇頭對收集到的信息進行數據的融合處理，將處理好的數據發送給基站。比較典型的是W.Heinzelma 等人提出的一種低功耗自適應分簇算法LEACH[2]，該算法是讓網絡中的節點自組織地形成簇，簇頭是隨機產生的。它在節約能耗方面，比傳統平面路由協議提高了近8倍，但是由于簇頭選舉的隨機性使得網絡的簇頭需要負擔的節點數不同，加重了個別簇頭節點的負擔，使得網絡的負載平衡程度下降，在簇頭選舉策略中沒有考慮到所有節點的剩余能量問題，也不能優化簇內結構，從而影響整個網絡的能耗。于是，提出了改進算法LEACH-C[5]，該算法由sink節點作出簇頭選擇決定，健壯性較好，解決了LEACH算法中“節點根據隨機數決定是否當選為簇頭” 以及“每輪產生的簇頭沒有確定的數量和位置”等方面的問題，大大提高了簇的生成質量。但由于每個節點都須向基站周期性地報告它們的能量和位置等信息，成簇開銷較大，網絡流量、時間延遲以及信號干擾的概率都會增加。文獻[6]給出了一個LEACH的改進算法LEACH-M，在建立網絡初期，要求每個節點告知基站，自己的地理位置和狀態，這在一定程度上增加了整個網絡的能量消耗，雖然在網絡生存期和數據傳輸量都優于原來的LEACH算法，但是引入了額外的能量開銷，不利于網絡的能量優化。文獻[7]的HEED算法是完全分布式的成簇算法，它隨機選擇簇頭節點，選舉概率與該節點的剩余能量直接相關，通過降低低能量節點成為簇頭的概率來保證網絡內能量負載的平均分布，從而進一步延長網絡生存時間。但HEED在選擇簇頭時，節點需要在一定的迭代次數內與周圍鄰居節點不斷地進行信息交互，因此算法的實現需要額外的通信代價，不適合大型無線傳感器網絡。

DEEC算法是由卿利等人提出的分簇路由算法，該算法基于節點剩余能量與網絡節點的平均能量的比例來選舉簇頭節點，適用于異構無線傳感器網絡[3，4]。本文從降低網絡能耗，優化網絡結構對DEEC算法進行改進，以期進一步降低網絡能耗，延長網絡生存時間。

2 DEEC-WIN算法

2.1 基本思想

DEEC-WIN算法保留了DEEC算法中的簇頭選舉機制，但是對節點加入簇的機制進行了優化。首先，據DEEC算法確立簇頭；然后，計算普通節點與sink節點的距離，以及與所有簇頭的距離。如果普通節點與sink節點的距離，比普通節點與任一簇頭的距離都短，則該節點不加入任何簇而成為孤立節點。孤立節點以最短路徑直接和sink節點通信，從而使節點在保證通信的同時把能量消耗降到最低，達到延長網絡生存時間的目的。

2.2 無線通信模型

與LEACH、DEEC等算法一樣，DEEC-WIN算法采用的無線通信模型如圖1所示[2-5]。

節點發射k比特的數據到距離為d的接收端，消耗的能量由發射電路和功率放大器的能耗兩部分組成 [3-5]

（1）

其中，Eelec表示節點電路發送和接收每比特數據的耗能；為距離閾值，當收發節點間的距離小于時，采用自由空間信道模型，當收發節點間的距離大于等于時，采用多徑衰落信道模型；表示放大器在自由空間信道模型下的能耗；表示放大器在多徑衰落信道模型下的能耗。

2.3 網絡模型

假設傳感器網絡有N個普通節點和1個sink節點，傳感器節點隨機均勻分布在MM的正方形區域內，sink節點位于區域正中，同時，有如下假設：

（1）傳感器網絡使用相同的能量受限的節點，且每個節點均可以與sink節點直接通信。

（2）傳感器網絡為能量異構網絡，即每個節點的初始能量不同，但都具備數據融合功能。

（3）節點部署后網絡無需人為維護，進行自組織管理，且假定節點是微移動或者靜止不動的。

（4）節點可以自適應調節發射功率，即根據接收方的距離，調節到恰好滿足通信距離要求的發射功率。

2.4 算法實現

DEEC-WIN算法在運行中不斷進行簇的重構過程，每個簇重構過程用“輪”來描述[2-5]，每一輪分為簇頭選擇、簇生成和數據通信三個階段。選定簇頭之后，剩余節點根據距離判決機制，來決定是否加入該簇。若在一輪周期內，該區域內至少存在一個簇頭到節點的距離小于節點到sink節點的距離，則節點加入距離簇頭最近的簇；若該區域內沒有一個簇頭到節點的距離小于節點到sink節點的距離，則節點不加入任何一個簇，成為孤立節點，直接和sink節點進行通信，以降低自身能量消耗。最后，sink節點收到的信息包含兩部分：各簇頭融合本簇內各節點數據和孤立節點的信息。

算法可分為以下4個階段進行：

（1）節點分布階段。在MM的區域內，隨機分布N個節點，節點Si存儲自身的坐標信息（Si.x，Si.y）。在（M/2，M/2）坐標位置布置sink節點。

（2）簇頭選舉階段。在DEEC算法中，區域內節點根據自身的剩余能量，由簇頭判決門限來選舉簇頭，簇頭的判決門限[3，4]

（2）

其中，r為當前的輪數，G為在最近（r mod （1/Pi））輪中沒有成為簇頭的節點集合，從而每個節點都有機會輪流成為消耗能量較多的簇頭節點。Pi 表示節點Si在第r輪當選簇頭的概率

（3）

其中，Popt表示簇頭優化比例，當Pi=Popt 時，網絡達到最優化狀態。表示網絡在第r輪的平均能量，Ei（r）表示節點Si在第r輪的剩余能量。

式（3）表示當節點的剩余能量比平均能量大時，該節點的平均選舉概率Pi將比Popt增加相應比例的值；當節點的剩余能量比平均能量要小時，節點的平均選舉概率Pi將比Popt減少相應比例的值。

（3）節點選擇簇頭階段。先計算出節點Si與sink節點的通信距離ds，再分別計算出節點Si與區域內各個簇頭的距離dhi。其中，節點Si與簇頭的最短距離為（h為簇頭數）。若dsdhmin，則節點根據最短路徑原則加入該簇。

（4）數據通信階段。在網絡的一輪周期內，假設孤立節點有n個，到sink節點的距離為dsi（i=1，2，…，n），簇內成員節點向簇頭節點發送k比特的信息，孤立節點也向sink節點也發送k比特的信息，于是網絡在一輪中總消耗的能量為：N-n個簇內節點分別與h個簇頭通信能耗、h個簇頭與sink通信能耗和n個孤立節點直接與sink通信能耗，具體計算公式如下：

（4）

其中，EDA為簇頭進行數據融合的能耗，dtoBS為簇頭到sink節點的平均距離，dtoCH為簇內成員節點到簇頭的平均距離。假設節點均勻分布，可以得到[5，8]：

（5）

（6）

對于DEEC算法，網絡在一輪中消耗的能量總和為[3，4]

（7）

因為di（i=1，2，…，n）

3 仿真實驗結果與分析

3.1 評價指標

根據算法對于網絡運行性能的影響與影響程度，主要選擇以下3個方面的評價指標：

（1）網絡生存時間。在排除網絡受外界干擾的情況下，當節點的能量為0時，就認定該節點死亡。從網絡運行到第一個節點死亡的時間間隔，為網絡第一生存時間，以及從第一個節點死亡到10%節點死亡的時間間隔為第二生存時間，最后到節點全部死亡，為整個網絡的生存時間。

（2）負載均衡度。每輪中簇覆蓋節點的平均程度也會影響網絡的生存時間，只有將網絡負載平均分布到每一個節點，避免少數節點過早的死亡，才能提高網絡性能。負載均衡度以負載平衡因子LBF（Load Balance Factor）表征

（8）

其中，h為簇頭數，Xi是第i個簇頭的簇內節點數，=（N -h）/h 表示每個簇頭的平均簇內節點數。顯然，LBF越大，負載均衡度越好。理想情況下，LBF為無窮大。

（3）網絡能量消耗。在網絡生存期內，網絡中所有的節點的能耗總和。

3.2 仿真環境

為了便于將DEEC-WIN算法與DEEC和LEACH算法進行性能比較和分析，本文設置上述三種分簇算法的仿真條件一致。假設網絡節點數為N=100，隨機分布在100m100m的區域內，sink節點位于區域的中心，坐標為（50， 50）。傳感器網絡為能量異構網絡，各節點初始能量為隨機值E0（1+rand），其中，E0為節點初始能量的最小值，rand為（0，1）之間的隨機數。

本文以MATLAB 7.6作為仿真工具，節點網絡參數設置見表1。

3.3 結果與分析

（1）網絡生存時間比較。圖2是LEACH、DEEC和DEEC-WIN三種算法的生存時間實驗結果對比，可以看出，DEEC-WIN算法的節點死亡速率明顯比DEEC低，其網絡生存時間比DEEC和LEACH算法大約多750輪，延長了約30%。

Fig.2 Network lifetime comparison chart

（2）負載均衡度比較。圖4是三種算法負載均衡度實驗結果對比，為避免LBF為無窮大時作圖困難，圖中以LBF-1作為縱坐標。可以看出，DEEC-WIN算法在網絡的有效生存期內的曲線比DEEC和LEACH算法數值小且曲線變化幅度小，說明DEEC-WIN算法在負載均衡度上比DEEC有了明顯的改善。

Fig.4 Load balancing degree comparison chart

Fig.5 Network energy consumption comparison chart

（4）網絡能量消耗比較。圖5是三種算法網絡能量消耗的實驗結果對比，可以看出，采用DEEC -WIN算法，網絡的能量消耗速度要慢于采用LEACH和DEEC算法的能量消耗。

4 結束語

本文基于最低能耗原則，在DEEC分簇算法的基礎上，提出了帶孤立節點的改進算法DEEC–WIN，在分簇過程中，通過改進加入簇的機制，使孤立節點直接與sink節點進行通信。仿真實驗結果表明，DEEC-WIN算法在網絡生存時間、數據傳輸量、負載均衡度、網絡能量消耗等方面的性能，優于DEEC算法和LEACH算法。

參考文獻：

1.Pottie G J， Kaiser W J. Wireless integrated network sensors[J]. Communications of the ACM，2000， 43（5）： 51-58.

2.Wendi Rabiner Heinzelman， Anantha Chandrakasan， and Hari Balakrishnan. Energy-Efficient Communica -tion Protocol for Wireless Microsensor Networks[C]. 33rd Hawaii International Conference on System Sciences. Maui， 4-7 January 2000， Volume 8， pp. 8020

3.Li Qing， Qingxin Zhu， Mingwen Wang. Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J]. Computer Communications， 2006， 29： 2230-2237

4.卿利， 朱清新， 王明文. 異構傳感器網絡的分布式能量有效成簇算法[J]. 軟件學報， 2006， 17（3）： 491-489

5.Wendi B. Heinzelman， Anantha P. Chandrakasan， Hari Balakrishnan. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications， 2002， 1（4） ：660-670.

6.余靜濤，胡同森，鐘明霞.無線傳感器網絡路由協議LEACH的研究與改進[J].計算機系統應用，2009（2）