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

鄔厚民

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

0 引 言

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

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

1 LEACH算法

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

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

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

G——這一輪循環(huán)中未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)集合。

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

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

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

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

[1]證明，在圖1所示相鄰的節(jié)點(diǎn)拓?fù)涓采w中，Wang提出定理：節(jié)點(diǎn)0所覆蓋的區(qū)域是一個(gè)正六邊形時(shí)，可以取得無(wú)縫最大有效覆蓋面積，即

式中：r——圓半徑。

圖1 最大無(wú)縫覆蓋示意圖

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

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

通過(guò)式（3）可以計(jì)算節(jié)點(diǎn)所在的行數(shù)[2]

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

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

N*的數(shù)值可以通過(guò)Ln的奇偶性來(lái)計(jì)算：

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

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

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

3 改進(jìn)的CDE-LEACH算法

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

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

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

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

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

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

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

3.2 無(wú)線耗能模型

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

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

d0——門(mén)限距離；

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

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

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

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

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

k——簇頭節(jié)點(diǎn)的個(gè)數(shù)；

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

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

3.3 選擇簇頭

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

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

即k0為極值點(diǎn)。

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

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

（1）當(dāng) k0≥N*時(shí)

（2）k0＜N*時(shí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

圖3 節(jié)點(diǎn)分布圖

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

圖4 改進(jìn)算法與原算法性能對(duì)比

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

[2]呂廣輝，崔遜學(xué)，侯戰(zhàn)勝.一種基于遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋模型[J].微型機(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ú)線傳感器網(wǎng)絡(luò)能量有效的分簇優(yōu)化算法研究[D].武漢：華中師范大學(xué)，2008.

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

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

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

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