童孟軍，邱偉偉

(杭州電子科技大學(xué)計算機(jī)學(xué)院，浙江杭州310018)

0 引言

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量較大，在網(wǎng)絡(luò)自組、路由查詢和信息傳輸過程中，都會占用大量的通信資源和處理資源所帶來的能量消耗［1］。因此，對于規(guī)模較大的無線傳感器網(wǎng)絡(luò)來說，分簇技術(shù)是分層路由協(xié)議中一種高效節(jié)能的拓?fù)淇刂品椒?。如何產(chǎn)生選舉簇頭節(jié)點(diǎn)是分簇路由算法最先要考慮問題［2］。本文提出的一種節(jié)能的負(fù)載均衡的分簇路由協(xié)議(Energy Efficient and Load-balanced Clustering Algorithm，EELCA)，該路由協(xié)議是一種復(fù)合型分簇路由協(xié)議。在該協(xié)議中，依據(jù)簇頭個數(shù)，將區(qū)域劃分為數(shù)個子區(qū)域，每個子區(qū)域綜合節(jié)點(diǎn)的剩余能量和隨機(jī)因素選舉簇頭，并且保證簇頭節(jié)點(diǎn)之間的有一定的間距，這樣避免簇頭分布過密和位置過偏，確保了網(wǎng)絡(luò)負(fù)載的均衡性。數(shù)據(jù)傳輸階段實現(xiàn)多跳式傳輸，外層區(qū)域的簇頭節(jié)點(diǎn)向內(nèi)層區(qū)域簇頭發(fā)送數(shù)據(jù)，直到最內(nèi)層區(qū)域簇頭直接發(fā)送給基站，減少了離基站較遠(yuǎn)的簇頭能量的消耗［3］。

1 模型介紹

(1)網(wǎng)絡(luò)模型:1)有節(jié)點(diǎn)完全相同并且都具有有限的初始能量;2)絡(luò)中所有傳感器節(jié)點(diǎn)都靜止;3)線傳感器網(wǎng)絡(luò)中每個節(jié)點(diǎn)有6個屬性字段ID(節(jié)點(diǎn)標(biāo)識)，Cid(聚類標(biāo)識)，C(是否簇頭)，E_mode(節(jié)點(diǎn)剩余能量)，Px，y(節(jié)點(diǎn)位置信息)，AreaID(子域標(biāo)識)。其中，節(jié)點(diǎn)自身的坐標(biāo)值由自帶的GPS獲得。

(2)能量模型:1)網(wǎng)絡(luò)中所有節(jié)點(diǎn)完全相同;2)無線電信號在各個方向上能量消耗相同;3)信道是對稱的，從節(jié)點(diǎn)A發(fā)到節(jié)點(diǎn)B的能量消耗與從節(jié)點(diǎn)B發(fā)到節(jié)點(diǎn)A的能量消耗相同［4］。

傳感器節(jié)點(diǎn)發(fā)送k bit數(shù)據(jù)消耗的能量分為兩部分，一部分是信號發(fā)射電路所消耗的能量，一部分是信號放大電路所消耗的能量，為:

傳感器節(jié)點(diǎn)接收k bit字節(jié)所消耗的能量為:

式中，Eelec是發(fā)送電路和接收電路消耗的能量;d是信號傳輸?shù)木嚯x［5］。

2 EELCA分簇算法思想

2.1 分簇算法準(zhǔn)備

基于網(wǎng)絡(luò)能耗最小的考慮，通過數(shù)學(xué)推導(dǎo)和仿真實驗，一般選取簇頭比例為5%，即簇頭產(chǎn)生概率P=0.05。對于一個節(jié)點(diǎn)數(shù)為100的區(qū)域，最多有簇頭數(shù)為5個。當(dāng)簇頭分布較合理時，簇的范圍應(yīng)盡量均勻覆蓋整個區(qū)域。因此簇頭間的距離必須適中，太近或太遠(yuǎn)都不合適，且在一定間距內(nèi)不能出現(xiàn)其他簇頭。設(shè)傳感器區(qū)域面積為S，節(jié)點(diǎn)數(shù)為N，簇頭產(chǎn)生比例為P，要覆蓋整個節(jié)點(diǎn)區(qū)域，則簇的平均半徑R滿足:

簇頭間距接近2R時，簇頭分布較合理。對于一個邊長為100m的正方形區(qū)域，節(jié)點(diǎn)個數(shù)100，簇頭比例P為0.05，則R≥25.2m。這里采用LEACH協(xié)議運(yùn)行模式，如圖1所示:

圖1 LEACH運(yùn)行過程

假設(shè)第i個簇中成員節(jié)點(diǎn)個數(shù)為Ni，一輪的數(shù)據(jù)傳輸時間為Tdata，每個成員節(jié)點(diǎn)分配的時槽長度是Tslot，則在一輪內(nèi)，簇i中一個成員節(jié)點(diǎn)消耗的能量為:

式中，Ni越大，Ei越小，即簇內(nèi)節(jié)點(diǎn)數(shù)越多，節(jié)點(diǎn)消耗的能量越小;反之，簇內(nèi)節(jié)點(diǎn)數(shù)目越少，節(jié)點(diǎn)消耗的能量越多。

2.2 簇的形成階段

簇的形成在整個協(xié)議中占著舉足輕重的作用，其分布的好壞決定了整個網(wǎng)絡(luò)的壽命。EELCA算法采取:(1)根據(jù)最優(yōu)簇頭概率設(shè)置簇頭個數(shù)為N×p，其中N為區(qū)域中傳感器節(jié)點(diǎn)總數(shù);(2)離基站較遠(yuǎn)的簇，成員節(jié)點(diǎn)可以適當(dāng)多一些，這樣簇內(nèi)能量消耗少;(3)在簇頭的選舉中，引入簇間距，使得每個簇頭的形成必須考慮和其他簇頭的距離。

(1)區(qū)域的劃分。假設(shè)有個100×100m的區(qū)域(L=100)，隨機(jī)分布了N=100個節(jié)點(diǎn)?；疚恢?50，50)。那么最優(yōu)簇頭個數(shù)為k=100×5%=5，根據(jù)前文所說，簇頭覆蓋半徑取R=26m，區(qū)域邊長為100，即簇頭可能最大間距為100，這里規(guī)定的簇頭間距為2R=52m，要想簇頭覆蓋到所有節(jié)點(diǎn)，每個子域的直徑需為2R，因此可以推斷出所要劃分的子域個數(shù)為［L/2R］=［100/52］=2，通過計算得出兩個子域面積之比SI:SII=1:6，現(xiàn)在有5個節(jié)點(diǎn)，子域I(內(nèi)層)分布一個節(jié)點(diǎn)，子域II(外層)分布其余4個節(jié)點(diǎn)。節(jié)點(diǎn)在每個子域的分布個數(shù)根據(jù)實際情況而定，隨著區(qū)域面積的增大，最內(nèi)層子域的個數(shù)增多。

(2)簇首選舉。為了使簇頭在子域內(nèi)分布均勻，選舉時確保各個簇頭的間距在2R=52左右，這里定義下一個簇頭只要在已經(jīng)選出的簇頭所在的［2R，2R(1+α)］鄰域內(nèi)就可以了。α是參數(shù)，在在0～1之間?？紤]到能量的消耗，則在已選為簇頭的鄰域內(nèi)，節(jié)點(diǎn)剩余能量最高的當(dāng)選簇頭。以此類推，直到子域內(nèi)的簇頭全部選舉完畢。

(3)簇的形成。對任意的節(jié)點(diǎn)i，會收到多個簇頭發(fā)來的消息，首先比較信號強(qiáng)度最高的兩個簇頭I和J，假設(shè)I的強(qiáng)度大于J，即SignalI＞SignalJ。NI，NJ為簇I和簇J內(nèi)成員節(jié)點(diǎn)的個數(shù)。dtoBS(I)，dtoBS(J)為簇到基站的距離。依據(jù)均衡原則來選擇加入的簇。

均衡原則是:節(jié)點(diǎn)i不但可以加入所屬區(qū)域的簇，還可以加入和自己不在同一個區(qū)域的簇，條件最優(yōu)者優(yōu)先，具體為:若SignalI/SignalJ≥ε，則節(jié)點(diǎn)i選擇加入簇I;否則，若|NI－NJ|≥λ，則節(jié)點(diǎn)i選擇加入NI，NJ中較小的簇;否則，若dtoBS(I)－dtoBS(J)≥0，則節(jié)點(diǎn)i選擇加入簇I，否則加入簇J，即選擇離基站遠(yuǎn)的簇頭加入。其中ε，λ為參數(shù)，根據(jù)情況自己設(shè)定。

所有子域內(nèi)的簇頭全部選擇好后，簇頭發(fā)送廣播通知域內(nèi)其他節(jié)點(diǎn)自己成為簇頭的消息，其余節(jié)點(diǎn)根據(jù)均衡原則決定加入的簇，并向簇首發(fā)送申請消息。當(dāng)某個子域的簇形成后，若其他子域還未完成簇的形成，那么已經(jīng)完成的子域中所有節(jié)點(diǎn)將進(jìn)入休眠狀態(tài)，等待其他子域簇的形成。根據(jù)區(qū)域劃分的特點(diǎn)，可以推斷出，最內(nèi)層的子域最先完成簇的形成，最外面的子域則最后完成。當(dāng)最后一個完成后，將其他子域內(nèi)的節(jié)點(diǎn)喚醒，進(jìn)入簇的穩(wěn)定階段。經(jīng)過一定時間后，進(jìn)入下一輪簇首選擇。

2.3 簇的穩(wěn)定階段

每個傳感器節(jié)點(diǎn)都在探測周圍信息，有信息接收時，開始判斷:1)如果接收信息的是基站，則接收完成;2)如果接收信息的是簇頭，那么該節(jié)點(diǎn)將信息傳給比自己AreaID小1的且信號最強(qiáng)的簇頭。不斷循環(huán)該步驟，直到信息傳遞到AreaID=1的簇頭，然后直接傳給基站;3)如果普通節(jié)點(diǎn)接收到信息，那么將信息傳遞給所在簇的簇頭，轉(zhuǎn)入步驟2。

3 仿真結(jié)果分析與比較

本文中采用的仿真工具為Matlab 6.5，在100×100m的區(qū)域(L=100)，隨機(jī)分布了N=100個傳感器節(jié)點(diǎn)，基站坐標(biāo)為(50，50)。

實驗參數(shù)設(shè)置:節(jié)點(diǎn)初始能量為0.001J(為了縮短程序運(yùn)行時間，減少輪轉(zhuǎn)次數(shù)少)，每個數(shù)據(jù)包含50bit，Eelec=50nJ/bit。簇頭產(chǎn)生概率為0.05。在均衡原則中，兩個簇頭的信號強(qiáng)度比ε=1.5，兩個簇頭中的成員數(shù)之差λ=5。

在傳感器網(wǎng)絡(luò)中，分簇算法的好壞主要根據(jù)網(wǎng)絡(luò)生存時間、能耗、覆蓋率等來衡量。其中網(wǎng)絡(luò)生存時間和能耗是兩個比較重要的參數(shù)。

該文將分簇協(xié)議中最為經(jīng)典的LEACH協(xié)議拿來和EELCA算法最仿真比較。仿真結(jié)果如下:1)首先在簇的分布上，當(dāng)程序運(yùn)行到第200輪時，EELCA算法簇的分布比LEACH協(xié)議的更為合理，而且簇中的成員數(shù)也較為均勻;2)其次是網(wǎng)絡(luò)生存時間，程序運(yùn)行的輪數(shù)越大，EELCA比LEACH節(jié)點(diǎn)存活數(shù)越多;3)最后是能量消耗，程序運(yùn)行到最后，EELCA節(jié)點(diǎn)的平均剩余能量明顯高于LEACH協(xié)議。

4 結(jié)束語

綜上所述，從簇的分布，網(wǎng)絡(luò)生存時間以及能量消耗這幾個方面來看，EELCA算法明顯優(yōu)于LEACH協(xié)議，說明此算法設(shè)計的較為合理，在一定程度上減少了能量的消耗，做到了能量均衡的效果。該文在說明EELCA算法時，對區(qū)域的劃分和每個子域簇頭個數(shù)的分配，針對較具體的網(wǎng)絡(luò)環(huán)境給出具體方法，沒有明確給出一個普遍適用的計算方法，只是提出了思想。在今后的工作中可進(jìn)一步總結(jié)并給出在其他應(yīng)用場景下的計算方法。

［1］ Cullar D，Estrin D，Strvastava M.Overview of sensor network［J］.Computer，2004，37(8):41 －49.

［2］ 孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:13－15.

［3］ Raghunatha，Schurgers V，Sung Park C.Energy － aware wireless microsensor networks［J］.IEEE，Signal Processing Magazine，2002，19(2):40 －50.

［4］ Heinzelman W.Application－Specific protocol architectures for wireless networks［D］.Boston:Massachusetts Institute of Technology，2000.

［5］ Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for self－ organization of a wireless sensor network［J］.IEEE Personal Communications，2000，7(5):16 －27.