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

【關(guān)鍵詞】無線傳感器網(wǎng)絡(luò)；分簇算法；孤立節(jié)點；DEEC；網(wǎng)絡(luò)生存時間

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：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 引言

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

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

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

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

1 典型分簇算法

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

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

2 DEEC-WIN算法

2.1 基本思想

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

2.2 無線通信模型

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

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

（1）

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

2.3 網(wǎng)絡(luò)模型

假設(shè)傳感器網(wǎng)絡(luò)有N個普通節(jié)點和1個sink節(jié)點，傳感器節(jié)點隨機(jī)均勻分布在MM的正方形區(qū)域內(nèi)，sink節(jié)點位于區(qū)域正中，同時，有如下假設(shè)：

（1）傳感器網(wǎng)絡(luò)使用相同的能量受限的節(jié)點，且每個節(jié)點均可以與sink節(jié)點直接通信。

（2）傳感器網(wǎng)絡(luò)為能量異構(gòu)網(wǎng)絡(luò)，即每個節(jié)點的初始能量不同，但都具備數(shù)據(jù)融合功能。

（3）節(jié)點部署后網(wǎng)絡(luò)無需人為維護(hù)，進(jìn)行自組織管理，且假定節(jié)點是微移動或者靜止不動的。

（4）節(jié)點可以自適應(yīng)調(diào)節(jié)發(fā)射功率，即根據(jù)接收方的距離，調(diào)節(jié)到恰好滿足通信距離要求的發(fā)射功率。

2.4 算法實現(xiàn)

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

算法可分為以下4個階段進(jìn)行：

（1）節(jié)點分布階段。在MM的區(qū)域內(nèi)，隨機(jī)分布N個節(jié)點，節(jié)點Si存儲自身的坐標(biāo)信息（Si.x，Si.y）。在（M/2，M/2）坐標(biāo)位置布置sink節(jié)點。

（2）簇頭選舉階段。在DEEC算法中，區(qū)域內(nèi)節(jié)點根據(jù)自身的剩余能量，由簇頭判決門限來選舉簇頭，簇頭的判決門限[3，4]

（2）

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

（3）

其中，Popt表示簇頭優(yōu)化比例，當(dāng)Pi=Popt 時，網(wǎng)絡(luò)達(dá)到最優(yōu)化狀態(tài)。表示網(wǎng)絡(luò)在第r輪的平均能量，Ei（r）表示節(jié)點Si在第r輪的剩余能量。

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

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

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

（4）

其中，EDA為簇頭進(jìn)行數(shù)據(jù)融合的能耗，dtoBS為簇頭到sink節(jié)點的平均距離，dtoCH為簇內(nèi)成員節(jié)點到簇頭的平均距離。假設(shè)節(jié)點均勻分布，可以得到[5，8]：

（5）

（6）

對于DEEC算法，網(wǎng)絡(luò)在一輪中消耗的能量總和為[3，4]

（7）

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

3 仿真實驗結(jié)果與分析

3.1 評價指標(biāo)

根據(jù)算法對于網(wǎng)絡(luò)運(yùn)行性能的影響與影響程度，主要選擇以下3個方面的評價指標(biāo)：

（1）網(wǎng)絡(luò)生存時間。在排除網(wǎng)絡(luò)受外界干擾的情況下，當(dāng)節(jié)點的能量為0時，就認(rèn)定該節(jié)點死亡。從網(wǎng)絡(luò)運(yùn)行到第一個節(jié)點死亡的時間間隔，為網(wǎng)絡(luò)第一生存時間，以及從第一個節(jié)點死亡到10%節(jié)點死亡的時間間隔為第二生存時間，最后到節(jié)點全部死亡，為整個網(wǎng)絡(luò)的生存時間。

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

（8）

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

（3）網(wǎng)絡(luò)能量消耗。在網(wǎng)絡(luò)生存期內(nèi)，網(wǎng)絡(luò)中所有的節(jié)點的能耗總和。

3.2 仿真環(huán)境

為了便于將DEEC-WIN算法與DEEC和LEACH算法進(jìn)行性能比較和分析，本文設(shè)置上述三種分簇算法的仿真條件一致。假設(shè)網(wǎng)絡(luò)節(jié)點數(shù)為N=100，隨機(jī)分布在100m100m的區(qū)域內(nèi)，sink節(jié)點位于區(qū)域的中心，坐標(biāo)為（50， 50）。傳感器網(wǎng)絡(luò)為能量異構(gòu)網(wǎng)絡(luò)，各節(jié)點初始能量為隨機(jī)值E0（1+rand），其中，E0為節(jié)點初始能量的最小值，rand為（0，1）之間的隨機(jī)數(shù)。

本文以MATLAB 7.6作為仿真工具，節(jié)點網(wǎng)絡(luò)參數(shù)設(shè)置見表1。

3.3 結(jié)果與分析

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

Fig.2 Network lifetime comparison chart

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

Fig.4 Load balancing degree comparison chart

Fig.5 Network energy consumption comparison chart

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

4 結(jié)束語

本文基于最低能耗原則，在DEEC分簇算法的基礎(chǔ)上，提出了帶孤立節(jié)點的改進(jìn)算法DEEC–WIN，在分簇過程中，通過改進(jìn)加入簇的機(jī)制，使孤立節(jié)點直接與sink節(jié)點進(jìn)行通信。仿真實驗結(jié)果表明，DEEC-WIN算法在網(wǎng)絡(luò)生存時間、數(shù)據(jù)傳輸量、負(fù)載均衡度、網(wǎng)絡(luò)能量消耗等方面的性能，優(yōu)于DEEC算法和LEACH算法。

參考文獻(xiàn)：

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.卿利， 朱清新， 王明文. 異構(gòu)傳感器網(wǎng)絡(luò)的分布式能量有效成簇算法[J]. 軟件學(xué)報， 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.余靜濤，胡同森，鐘明霞.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)[J].計算機(jī)系統(tǒng)應(yīng)用，2009（2）