無線傳感網(wǎng)絡(luò)中能量和距離改良的LEACH分簇算法

鄔厚民

（廣州科技貿(mào)易職業(yè)學院，廣東 廣州 511442）

0 引 言

能耗問題一直是制約無線傳感器網(wǎng)絡(luò)發(fā)展的關(guān)鍵問題。由于傳感器節(jié)點是依靠電池供電的節(jié)點設(shè)備，并且考慮其自身尺寸限制及所部署的惡劣環(huán)境，人工很難通過“二次供電”的方式為其補充能量，導致傳感器節(jié)點因能量耗盡得不到補充，造成網(wǎng)絡(luò)中存在漏測區(qū)域，甚至整個傳感器網(wǎng)絡(luò)的癱瘓；因此，在無線傳感器網(wǎng)絡(luò)正常工作過程中，如何有效減少網(wǎng)絡(luò)中節(jié)點能量消耗，均衡網(wǎng)絡(luò)中傳感器節(jié)點的能量來延長網(wǎng)絡(luò)生命周期成為當前無線傳感器網(wǎng)絡(luò)中研究的重點。

大量實驗研究表明，通過選定合理的簇頭節(jié)點、簇頭數(shù)目及減少簇內(nèi)的簇頭節(jié)點處理簇內(nèi)數(shù)據(jù)的計算量，可以有效地減少整個傳感器網(wǎng)絡(luò)的能量消耗，延長網(wǎng)絡(luò)生命周期。本文采用低功耗自適應(yīng)集簇分層型協(xié)議（low energy adaptive clustering hierachy，LEACH）作為自適應(yīng)分簇拓撲算法對傳感器網(wǎng)絡(luò)進行分簇，在簇的建立階段著重考慮能量因素，從簇頭的選擇和簇內(nèi)通信兩方面對LEACH算法進行了改進。該改進算法能夠克服傳感器網(wǎng)絡(luò)中整體能量消耗過大及因節(jié)點伴隨時間推移而能量耗盡所帶來的漏測區(qū)域的弊端。

1 LEACH算法

LEACH算法是Heinzelman等提出的自適應(yīng)分簇經(jīng)典算法。該算法中引入了“輪”的概念，每一輪分為初始化和穩(wěn)定通信兩個階段。其中，初始化階段又分為簇頭選舉和簇的建立。簇頭選舉過程中，節(jié)點產(chǎn)生0~1之間的隨機數(shù)，若該隨機數(shù)小于規(guī)定的閾值T（n）則自行選舉為簇頭并進行廣播。

式中：p——簇頭數(shù)量所占的百分比；

r——選舉輪數(shù)；

G——這一輪循環(huán)中未當選過簇頭的節(jié)點集合。

在簇的建立階段，接收到簇頭廣播消息的非簇頭節(jié)點根據(jù)“就近原則”加入簇。在穩(wěn)定通信階段，簇頭節(jié)點將接收到的簇內(nèi)成員節(jié)點的數(shù)據(jù)進行融合并發(fā)送給基站。

LEACH算法初步解決了傳感器節(jié)點負載平衡的問題，并且比較容易實現(xiàn)，但是還有很多值得改進的地方。如簇頭選舉階段，節(jié)點隨機決定是否成為簇頭，導致簇頭位置和簇內(nèi)包含的節(jié)點個數(shù)很不均勻，并且也沒有考慮到節(jié)點的剩余能量；在成簇階段，非簇頭節(jié)點采用就近原則，加入離自己最近的簇頭，也沒有考慮到簇頭的剩余能量；選取節(jié)點沒有考慮對區(qū)域的覆蓋情況等。本文在考慮對區(qū)域保證最大覆蓋的前提下，結(jié)合對能量和距離的綜合考慮，對初始化階段簇頭選舉和成簇兩個子階段進行改進，用選出的簇頭保證對區(qū)域的最大覆蓋。

2 最優(yōu)覆蓋下基站“數(shù)據(jù)表”的構(gòu)建

2.1 傳感器網(wǎng)絡(luò)最大覆蓋理想模型

[1]證明，在圖1所示相鄰的節(jié)點拓撲覆蓋中，Wang提出定理：節(jié)點0所覆蓋的區(qū)域是一個正六邊形時，可以取得無縫最大有效覆蓋面積，即

式中：r——圓半徑。

圖1 最大無縫覆蓋示意圖

2.2 基站“數(shù)據(jù)表”的建立

假設(shè)傳感器的感知半徑為R，被監(jiān)測矩形區(qū)域的長為L，寬為W，節(jié)點的行數(shù)為Ln，每行節(jié)點的數(shù)目為Hn，所有節(jié)點的數(shù)目為N*。

通過式（3）可以計算節(jié)點所在的行數(shù)[2]

計算每行節(jié)點的數(shù)量Hn的過程非常復雜，底邊具有不同的長度，因此每行中包含的節(jié)點個數(shù)不相等。為了進一步判斷分析，作輔助線，假設(shè)從左邊開始計算，對應(yīng)每一列節(jié)點的左切線，如圖2所示。從底向上開始計算，在奇數(shù)行中做各個圓的下切線，在偶數(shù)行中做各個圓的上切線。奇數(shù)行與偶數(shù)行之間均為陰影部分。

圖2 無線傳感器網(wǎng)絡(luò)理想最優(yōu)部署模型

N*的數(shù)值可以通過Ln的奇偶性來計算：

（2）若Ln為偶數(shù)，N*計算公式為

由以上易知此模型下保證最優(yōu)覆蓋所需N*個點，并且可得每個點位置的坐標。

記錄這N*個點的坐標（i，xi，yi），i=1，…，N*。形成一個“數(shù)據(jù)表”，存儲在基站中，以備后續(xù)改進CDE-LEACH算法的簇頭選擇過程中應(yīng)用，用簇頭來保證整個部署區(qū)域的全覆蓋[3]。

3 改進的CDE-LEACH算法

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

在大小為M×M的矩形監(jiān)測區(qū)域內(nèi)，隨機部署N個傳感器節(jié)點組成網(wǎng)絡(luò)。對網(wǎng)絡(luò)模型作如下假設(shè)：

（1）網(wǎng)絡(luò)中節(jié)點是靜止的或緩慢移動；

（2）網(wǎng)絡(luò)中的節(jié)點同構(gòu)且節(jié)點初始能量相同，并且有唯一的ID號，節(jié)點的坐標由定位算法可得，并且已知；

（3）基站位置固定，假設(shè)其能量是無限的（不靠電池供電）；

（4）基站中存有保證網(wǎng)絡(luò)最優(yōu)覆蓋條件下存有N*個點位置坐標信息的“數(shù)據(jù)表”；

（5）節(jié)點的發(fā)射功率動態(tài)可調(diào)，節(jié)點間的通信鏈路可靠且雙向連通。

3.2 無線耗能模型

傳感器節(jié)點的能量主要消耗在無線傳輸?shù)倪^程中，而且隨著通信距離的增加，節(jié)點能耗呈指數(shù)增長。發(fā)送和接收l bit數(shù)據(jù)且傳輸距離為d，節(jié)點消耗的能量分別為

式中：Eel——電路發(fā)送或接收功耗；

d0——門限距離；

rd2——傳輸距離小于d0時，采用自由空間信道環(huán)境下的功率放大器功耗；

ηd4——傳輸距離大于等于d0時，對應(yīng)多路徑衰落信道環(huán)境下的功率放大器功耗。

在每一輪簇的重建中消耗的總能量為[4]

式中：dtobs——節(jié)點到匯聚節(jié)點的平均距離；

Ec——簇頭中數(shù)據(jù)融合時的功耗；

k——簇頭節(jié)點的個數(shù)；

Ei——傳感器節(jié)點的最初能量；

Ei（r）——對應(yīng)第r輪選舉簇頭時的剩余能量；

3.3 選擇簇頭

由LEACH協(xié)議可知，簇頭節(jié)點的個數(shù)影響網(wǎng)絡(luò)的壽命。若選擇的簇頭節(jié)點個數(shù)過少，則導致簇的覆蓋區(qū)域過大，簇內(nèi)節(jié)點到簇頭的通信距離比較遠，相應(yīng)傳輸數(shù)據(jù)時需要的能量也多；由于簇頭節(jié)點需要的能量遠大于非簇頭節(jié)點，若選擇的簇頭節(jié)點個數(shù)過多，每一輪工作過程中整個網(wǎng)絡(luò)中所有節(jié)點總的能耗會增大，進而導致數(shù)據(jù)融合[5]效率降低。

網(wǎng)絡(luò)在每一輪的簇重建中消耗能量最小[5-7]，是選舉最優(yōu)簇頭節(jié)點個數(shù)的準則，并且保證對所監(jiān)測區(qū)域的網(wǎng)絡(luò)覆蓋。首先考慮在式（8）中Etotal達到極小值時的k值點。給定網(wǎng)絡(luò)參數(shù)的前提下，當k＞0時Etotal對應(yīng)以k為變量的連續(xù)函數(shù)。

即k0為極值點。

經(jīng)過計算得到k0為最小值。k0由匯聚節(jié)點計算，并且每隔預(yù)先設(shè)定的若干個周期重新計算一次，因為網(wǎng)絡(luò)中存在因能量耗盡而死亡的節(jié)點。

此時計算的k0值滿足簇重建過程中所需能量最小，但是并不能保證區(qū)域網(wǎng)絡(luò)的覆蓋，為此在此區(qū)域下結(jié)合利用式（4）或（5），從k0個節(jié)點中在前述條件下計算出保證網(wǎng)絡(luò)最優(yōu)覆蓋的節(jié)點個數(shù)N*，從而挑選出滿足所需條件最優(yōu)的k0個節(jié)點。考慮2種情況：

（1）當 k0≥N*時

（2）k0＜N*時

在簇頭選舉時綜合考慮覆蓋、能量和距離兩個因素，首先在能量和距離因素下，為每個節(jié)點分配表示其適合充當簇頭的概率權(quán)值。定義某個節(jié)點i在第r輪簇頭選舉中的競選概率權(quán)值為

Ei（r）——對應(yīng)節(jié)點i第r輪剩余能量；

E（r）——節(jié)點的最初能量；

μ——區(qū)間[1/2，1]內(nèi)遞增；

dmax——節(jié)點到匯聚節(jié)點的最遠距離；——節(jié)點i到匯聚節(jié)點的距離；

前述可知，在CDE-LEACH算法中，對簇頭的選舉需要知道當前網(wǎng)絡(luò)中的平均剩余能量，方法：每輪過后，簇內(nèi)節(jié)點在最后要發(fā)送的數(shù)據(jù)分組中裝載有自身的剩余能量信息，傳輸給簇頭；簇頭對這些信息進行收集融合，將融合后的數(shù)據(jù)信息發(fā)送給基站；在基站中完成對整個網(wǎng)絡(luò)中的平均剩余能量的計算，并將結(jié)果裝載到下一輪的重新選簇命令中，廣播給網(wǎng)絡(luò)內(nèi)所有的傳感器節(jié)點。由此，完成了對網(wǎng)絡(luò)平均剩余能量的計算。

初始化階段，基站首先廣播簇頭開始競選消息，這個消息中包含當前網(wǎng)絡(luò)平均剩余能量信息。當節(jié)點收到這個消息后，首先將自身剩余能量與當前網(wǎng)絡(luò)的平均剩余能量進行對比，若自身剩余能量比當前網(wǎng)絡(luò)的平均剩余能量小，則直接放棄競選，并隨后加入某一簇；若自身剩余能量比當前網(wǎng)絡(luò)的平均剩余能量大，則向基站發(fā)送消息，消息中包括節(jié)點的ID和剩余能量等信息，即競選簇頭消息。基站收到所有參加競選節(jié)點發(fā)送的競選簇頭消息后，根據(jù)式（11）確定的競選權(quán)值按前述方法選擇出的k0′個節(jié)點作為簇頭，并全網(wǎng)廣播該k0′個節(jié)點作為簇頭的消息，消息中包括選出的k0′個簇頭節(jié)點的ID。網(wǎng)絡(luò)中節(jié)點接收到此消息后如果發(fā)現(xiàn)任命的簇頭中有自身，就當選為簇頭。

3.4 選擇簇內(nèi)成員

在非簇內(nèi)節(jié)點成員選擇加入簇頭時，同樣考慮距離和能量兩個因素，通過選舉出的簇頭節(jié)點來保證整個區(qū)域的最優(yōu)覆蓋，前面簇頭選擇過程中選擇出的簇頭已經(jīng)保證了簇頭對整個區(qū)域網(wǎng)絡(luò)的覆蓋；因此，這里選擇簇內(nèi)成員時不再考慮最優(yōu)覆蓋的問題。

可以假設(shè)非簇頭節(jié)點接收到來自m個簇頭節(jié)點的廣播消息，廣播消息中包含簇頭ID和自身剩余能量。此處定義非簇頭節(jié)點選擇加入簇頭時的概率權(quán)值為

式中：μ——加權(quán)系數(shù)，可根據(jù)實際情況改變；

Ei（r）——節(jié)點i第r輪剩余能量；

E（r）——節(jié)點的初始能量；

dmax——節(jié)點到基站的最遠距離；

di——非簇頭節(jié)點到第i個簇頭間的距離。

由式（12）知非簇頭節(jié)點選擇加入簇頭時，首先會選擇當前簇頭節(jié)點剩余能量多且距離近的簇頭加入，因為距離近，傳輸數(shù)據(jù)信息時消耗的能量就少，也就相對節(jié)省了能量，這樣，非簇頭節(jié)點選擇加入簇頭時的概率權(quán)值最大。然后非簇頭節(jié)點向該簇頭節(jié)點發(fā)送加入請求消息，請求消息中包括本節(jié)點的ID和所加入簇頭的節(jié)點ID。簇頭節(jié)點收到各成員節(jié)點的請求信息后，采用TDMA策略為簇內(nèi)成員分配通道，完成簇階段的建立過程并開始進入穩(wěn)定階段，各簇內(nèi)成員節(jié)點在自己分配的通道內(nèi)向簇頭發(fā)送數(shù)據(jù)，簇頭節(jié)點融合各成員節(jié)點的數(shù)據(jù)后發(fā)送到基站。

4 仿真實驗

在100m×100m的監(jiān)測區(qū)域內(nèi)，隨機部署100個傳感器節(jié)點，如圖3所示。節(jié)點半徑為15，初始能量為 0.5J，匯集節(jié)點位于（150，50）處，最大運行輪數(shù)為5000。控制不同情況下的傳輸數(shù)據(jù)觀察節(jié)點的死亡情況即網(wǎng)絡(luò)的運行生命周期[8]。

圖3 節(jié)點分布圖

在上述條件下運行LEACH協(xié)議和本文提出的CDE-LEACH算法，采用Matlab 7.0仿真平臺對改進前后的LEACH算法對能量的消耗情況進行對比，對比結(jié)果如圖4所示。

圖4 改進算法與原算法性能對比

圖4中LEACH1、LEACH2分別代表未采用最優(yōu)覆蓋的LEACH算法與采用最優(yōu)覆蓋的LEACH算法，CDE-LEACH1、CDE-LEACH2分別代表未采用最優(yōu)覆蓋與采用最優(yōu)覆蓋的CDE-LEACH算法。

由圖4可知，改進后的LEACH算法協(xié)議CDELEACH算法在相同運行周期時死亡節(jié)點數(shù)相對于LEACH算法明顯減少，這說明改進后的算法有效地延長了網(wǎng)絡(luò)的生命周期。

5 結(jié)束語

本文在已有的成熟并廣泛應(yīng)用的LEACH算法協(xié)議前提下，提出CDE-LEACH算法，它是一種能保證在網(wǎng)絡(luò)有效最大覆蓋前提下，最大限度地采集網(wǎng)絡(luò)中的有效數(shù)據(jù)并降低網(wǎng)絡(luò)的能量消耗算法。通過Matlab 7.0實驗平臺驗證，改進后的LEACH算法能夠有效地減少網(wǎng)絡(luò)中的傳感器節(jié)點能量消耗，延長網(wǎng)絡(luò)的生命周期。

參考文獻

[1]Warneke B，LastM，Liebowitz B.Smart dust:communicating with acubic-millimeter computer[J].IEEE Computer Magazine，2001，34（1）：44-51.

[2]呂廣輝，崔遜學，侯戰(zhàn)勝.一種基于遺傳算法的無線傳感器網(wǎng)絡(luò)覆蓋模型[J].微型機與應(yīng)用，2010，29（15）：59-62.

[3]Huang C H，Tseng Y C.The coverage problem in three-dimensional wireless sensor network[J].Journal of Interconnection Networks，2007，8（3）：209-227.

[4]蘇瑩.無線傳感器網(wǎng)絡(luò)能量有效的分簇優(yōu)化算法研究[D].武漢：華中師范大學，2008.

[5]陳浩，劉廣鐘.基于能量和距離的無線傳感器網(wǎng)絡(luò)分簇算法[J].微型機與應(yīng)用，2009，28（11）：31-33.

[6]胡剛，謝冬梅，吳元忠.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進[J].傳感技術(shù)學報，2007，20（6）：1391-1396.

[7]陳潔，趙全明.基于冗余節(jié)點的LEACH協(xié)議的改進[J].電子設(shè)計工程，2011，19（22）：42-44.

[8]畢艷忠，孫利民.傳感器網(wǎng)絡(luò)中的數(shù)據(jù)融合[J].計算機科學，2004，31（7）：101-103.