基于覆蓋率的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議研究及改進*

馬杰良，王 垚，顧蕾蕾

(1.南京信息工程大學(xué)電子與信息工程學(xué)院，南京210044;)

2.南京信息工程大學(xué)信息與控制學(xué)院，南京210044

隨著信息技術(shù)的不斷發(fā)展，人們對移動通信的要求越來越高。移動通信技術(shù)的發(fā)展和普及不僅方便了人們的生活，同時也推動了無線通信技術(shù)的發(fā)展。

無線傳感器網(wǎng)絡(luò)(WSN)是一種新型的網(wǎng)絡(luò)和計算技術(shù)。它能夠?qū)崟r監(jiān)測、感知和采集監(jiān)測對象的信息并對其進行處理，再將信息傳送到用戶。隨著無線傳感器網(wǎng)絡(luò)的日益成熟和普及，人們的生產(chǎn)、生活方式和工作效率也會隨之得到不斷的改善和提高。

路由協(xié)議是無線傳感器網(wǎng)絡(luò)層的核心技術(shù)。目前，WSN路由協(xié)議的種類已有很多，其目的是要節(jié)省系統(tǒng)的能量，延長系統(tǒng)的生命周期，提高系統(tǒng)的性能，主要有平面路由協(xié)議和層次路由協(xié)議兩種［1－2］。

LEACH協(xié)議是第一個在無線傳感器網(wǎng)絡(luò)中提出的分簇式路由協(xié)議，在無線傳感器網(wǎng)絡(luò)路由協(xié)議中占有重要地位，具有分簇協(xié)議的基本特點。近年來，許多文章針對LEACH的分簇算法進行改進。隨著人們對WSN路由協(xié)議的研究深入，以生存節(jié)點的個數(shù)來衡量WSN生命周期長短已無法滿足人們對系統(tǒng)性能的高要求。于是以生存節(jié)點的覆蓋率來衡量WSN生命周期這一新概念順理成章地被現(xiàn)在的大部分學(xué)者所認可了［3－4］。覆蓋率反映了網(wǎng)絡(luò)區(qū)域被監(jiān)測的狀況，它的應(yīng)用，有助于網(wǎng)絡(luò)節(jié)點能量的有效控制、感知服務(wù)質(zhì)量的提高和整體生存時間的延長。

文獻［5］中算法根據(jù)節(jié)點的位置信息來計算節(jié)點與其鄰居節(jié)點的覆蓋關(guān)系，從而選取工作節(jié)點。為了避免產(chǎn)生覆蓋盲區(qū)，采取了后退機制，該算法使網(wǎng)絡(luò)保持完全覆蓋，但算法運行復(fù)雜度較高。文獻［6］中證明了當節(jié)點的通信半徑大于等于兩倍的感知半徑時，若工作節(jié)點能夠覆蓋整個區(qū)域，則工作節(jié)點集合一定是連通的。并提出了OGDC算法，該算法按輪次運行，每輪開始時隨機選擇開始節(jié)點并廣播消息。節(jié)點根據(jù)其鄰居信息，自己的位置，計算是否被鄰居節(jié)點覆蓋。文獻［7］中提出了根據(jù)節(jié)點密度信息來選擇工作節(jié)點的算法SCOM，由節(jié)點周圍鄰居節(jié)點與骨干節(jié)點交互信息來決定節(jié)點是否為工作節(jié)點。文獻［8］中提出了基于覆蓋度的覆蓋控制算法DSP，每個節(jié)點計算本地節(jié)點的覆蓋度，針對應(yīng)用對覆蓋質(zhì)量的精確要求，通過根據(jù)節(jié)點覆蓋度來選擇工作節(jié)點。

本文主要是在LEACH協(xié)議的基礎(chǔ)上，根據(jù)檢測到的鄰居節(jié)點的數(shù)量，提出一種有效的算法，該算法通過對簇頭節(jié)點分布及簇內(nèi)實際覆蓋率的優(yōu)化來提高整個網(wǎng)絡(luò)壽命。

1 LEACH協(xié)的分析

1.1 LEACH協(xié)議算法分析

LEACH協(xié)議是以循環(huán)的方式隨機選擇簇頭節(jié)點，將整個網(wǎng)絡(luò)的能量負載平均分配到每個傳感器節(jié)點中，從而達到降低網(wǎng)絡(luò)能源消耗、提高網(wǎng)絡(luò)整體生存時間的目的。

根據(jù)文獻［9］中所述，LEACH協(xié)議在運行過程中不斷的循環(huán)執(zhí)行簇的重構(gòu)過程，每個簇重構(gòu)過程可以用回合的概念來描述。其選取簇頭的原則是:傳感器節(jié)點隨機的生成一個0，1之間的數(shù)，如果小于閾值T(n)，則該節(jié)點當選為簇頭，T(n)按下列式(1)計算:

其中p為每輪節(jié)點成為簇頭的百分比即p=k/N，k為一輪中成為簇頭的個數(shù)，N為總的傳感器個數(shù)，r為當前輪數(shù)，G是在過去的輪內(nèi)未成為簇頭的節(jié)點集合。這個算法可以保證每個節(jié)點在1/p輪內(nèi)僅僅當選成為簇頭一次。

選定簇頭節(jié)點后，其通過廣播告知整個網(wǎng)絡(luò)。網(wǎng)絡(luò)中的其他節(jié)點根據(jù)接收信息的信號強度決定從屬的簇，并通知相應(yīng)的簇頭節(jié)點，完成簇的建立。

進入穩(wěn)定階段后，普通節(jié)點將采集的數(shù)據(jù)傳送至簇頭節(jié)點。簇頭節(jié)點對簇中所有節(jié)點所采集的數(shù)據(jù)進行信息融合后再傳送給匯聚節(jié)點。穩(wěn)定階段持續(xù)一段時間后，網(wǎng)絡(luò)重新進入簇的建立階段，進行下一回合的簇重構(gòu)，不斷循環(huán)，直至整個傳感器網(wǎng)絡(luò)的生命周期結(jié)束。

1.2 LEACH協(xié)議算法不足

LEACH協(xié)議的精華內(nèi)容是分布式的成簇技術(shù)和自適應(yīng)的成簇算法以及簇首位置的輪換算法。其中分布式的成簇技術(shù)保證了大數(shù)目的節(jié)點的自組織行為。自適應(yīng)的成簇算法以及簇首位置的輪換算法保證所有節(jié)點公平地承擔能量消耗的負擔，最終可以延長整個系統(tǒng)的生存時間，但是LEACH協(xié)議還是有很多不足之處:

(1)LEACH協(xié)議的簇頭選舉是隨機的，可能出現(xiàn)簇頭分布不均而造成的信息傳遞時的能量損失。

(2)各節(jié)點擔任簇頭節(jié)點的機會均等，但因剩余能量的不同，可能會因某簇頭能量過低而引起網(wǎng)絡(luò)中斷。

(3)LEACH協(xié)議的選簇及信息傳遞一般只考慮到用生存節(jié)點的個數(shù)來衡量傳感器生命周期的長短及協(xié)議性能的好壞，并未從覆蓋率的角度考慮，造成了重復(fù)的信息采集時的能量損失。

2 LEACH協(xié)議改進—LEACH-C協(xié)議

改進的LEACH—C協(xié)議主要針對LEACH協(xié)議分簇時簇頭在網(wǎng)絡(luò)中的分布不均問題及簇內(nèi)覆蓋冗余問題兩方面進行優(yōu)化。通過對鄰居節(jié)點的測量排除每輪中不必要的工作節(jié)點以保證網(wǎng)絡(luò)覆蓋率并降低整個網(wǎng)絡(luò)的能耗。

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

假設(shè)所有傳感器節(jié)點隨機均勻地部署在一個正方形區(qū)域A中，節(jié)點密度足夠大，若所有節(jié)點都處于工作狀態(tài)，則可以覆蓋整個區(qū)域A，且該網(wǎng)絡(luò)具有以下性質(zhì):

(1)相對于節(jié)點的感知范圍而言，監(jiān)測區(qū)域A足夠大，邊界因素可以忽略;

(2)所有節(jié)點部署后不再移動，且無需人為進行維護;

(4)所有節(jié)點是同構(gòu)的;

(5)每個節(jié)點無需裝備GPS，且不能通過測量或定位方法獲得其具體的物理位置;

(6)能量消耗滿足LEACH協(xié)議的能耗模型

2.2 簇頭節(jié)點的競選

LEACH-C協(xié)議中，為保證簇頭節(jié)點分布均勻并防止簇頭節(jié)點處于監(jiān)測區(qū)域A的邊緣地段，根據(jù)仿真經(jīng)驗，首先規(guī)定兩個簇頭節(jié)點之間的距離不得小于2倍的Rs，且當某節(jié)點的剩余能量低于Emin時，該節(jié)點將失去簇頭的競選權(quán)以保證被選簇頭有足夠能量完成一輪的信息融合及傳輸工作，Emin按下列式(2)計算:

其中，Nact是簇內(nèi)工作節(jié)點的平均個數(shù)，l為傳輸數(shù)據(jù)包長度，Eelec表示無線收發(fā)電路所消耗的能量，EDA表示數(shù)據(jù)融合所消耗的能量，εfs和εamp分別表示自由空間模型和多路衰減模型的放大器消耗的能量，d是簇頭到Sink節(jié)點的距離，d0為常數(shù)，取決于傳感器網(wǎng)絡(luò)應(yīng)用的環(huán)境。

在整個生命周期的初始階段，以Rs為半徑對外廣播并接收周邊節(jié)點的信息以確定自己的鄰居節(jié)點個數(shù)nn，當nn小于1時默認取1。并以優(yōu)先級pc1選出第1個簇頭從而確保整個網(wǎng)絡(luò)分布的相對密集區(qū)域附近有簇頭節(jié)點存在。pc1按下列式(3)計算:

2.3.1 上消化道出血發(fā)生率 3項研究[3，5，19]報道了上消化道出血發(fā)生率，各研究間無統(tǒng)計學(xué)異質(zhì)性（P＝0.62，I2＝0），采用固定效應(yīng)模型進行分析，詳見圖2。Meta分析結(jié)果顯示，試驗組患者上消化道出血發(fā)生率顯著低于對照組，差異有統(tǒng)計學(xué)意義[RR＝0.16，95%CI（0.07，0.34），P＜0.01]。

其中，nn為該節(jié)點的鄰居節(jié)點個數(shù)，Ecurrent為該節(jié)點當前能量，E為節(jié)點初始能量，N為監(jiān)測區(qū)域節(jié)點總數(shù)。

其余節(jié)點若與當前簇頭的距離大于2倍Rs且其剩余能量不低于Emin，則其成為簇頭的概率pcc按下列式(4)計算，成為簇頭的概率與節(jié)點自身的剩余能量有關(guān):

2.3 簇內(nèi)工作節(jié)點的競選

簇頭選舉結(jié)束后，在該輪成功當選的簇頭節(jié)點以廣播的方式告知整個網(wǎng)絡(luò)，普通節(jié)點收到廣播后，根據(jù)到各簇頭的距離及各簇頭當前能量為條件選擇適當簇頭入簇，其優(yōu)先級pntoc按下列式(5)計算:

其中，dtoc為普通節(jié)點到簇頭的距離，Ec為各簇頭當前能量。

當普通節(jié)點入簇結(jié)束后，將廣播告知簇頭節(jié)點自己已加入該簇。簇頭節(jié)點接收通知并計算出該簇當前簇內(nèi)成員總個數(shù)，若簇內(nèi)成員個數(shù)大于Nact個，則根據(jù)優(yōu)先級pwork選擇本輪簇內(nèi)的工作節(jié)點。

根據(jù)文獻［10］提出，假設(shè)工作節(jié)點密度為ρ，定義為一個單位區(qū)域內(nèi)工作節(jié)點的數(shù)量。由于節(jié)點是隨機均勻分布的，故可推得傳感器網(wǎng)絡(luò)中，平均工作節(jié)點密度ρ公式如下式(6):

即，實際情況下，若要使整個簇內(nèi)區(qū)域被完全覆蓋則平均需要的工作節(jié)點個數(shù)Nact可按下式(7)計算，其中A為整個檢測區(qū)域面積:

由文獻［11］可知，鄰居節(jié)點的個數(shù)與該節(jié)點的被完全覆蓋率及覆蓋面積成正比，即一個節(jié)點的鄰居節(jié)點個數(shù)越多，其感知區(qū)域被完全覆蓋的概率及多余面積的百分比就越高，鄰居節(jié)點個數(shù)與節(jié)點的覆蓋關(guān)系如表1所示。

表1 鄰居節(jié)點個數(shù)與節(jié)點覆蓋關(guān)系

由上表可知，鄰居節(jié)點多的節(jié)點，其感知區(qū)域同時被其他節(jié)點覆蓋的幾率越高，其收集到的信息冗余率也就越高。

故，成為簇內(nèi)工作節(jié)點的優(yōu)先級pwork可根據(jù)該節(jié)點的鄰居個數(shù)及剩余能量得出，按下式(8)計算，競選出Nact個工作節(jié)點:

工作節(jié)點競選結(jié)束后，該輪未被選出的節(jié)點將進入休眠狀態(tài)，不進行數(shù)據(jù)采集工作，而選出的工作節(jié)點將廣播告知簇頭，開始收集信息并傳送給簇頭節(jié)點，簇頭節(jié)點對接受到的信息進行簇內(nèi)融合后傳遞給Sink節(jié)點，該回合結(jié)束。

由上所述，簇內(nèi)工作節(jié)點競選算法偽碼如下:

2.4 節(jié)點低能耗處理

當網(wǎng)絡(luò)中，某節(jié)點的剩余能量低于Edead時，認為該節(jié)點死亡，死亡節(jié)點將向半徑為Rs內(nèi)的節(jié)點廣播告知其死亡消息，收到廣播的節(jié)點將自己的鄰居

3 改進后的性能仿真及分析

3.1 模擬實驗環(huán)境設(shè)置和參數(shù)

節(jié)點數(shù)nn減1(nn小于1時默認取1)。Edead按下列式(9)計算，其中cm為廣播數(shù)據(jù)包長度:

我們用Matlab作為仿真實驗平臺，并使用與文獻［12］中相同的能量模型。發(fā)送數(shù)據(jù)和接收數(shù)據(jù)的無線通信模型分別為:

其中，Eelec表示無線收發(fā)電路所消耗的能量;εfs和εamp分別表示自由空間模型和多路衰減模型的放大器消耗的能量;d0是常數(shù)，取決于傳感器網(wǎng)絡(luò)應(yīng)用的環(huán)境。各項實驗參數(shù)如表2所示。

表2 仿真參數(shù)

3.2 簇頭分布分析

為了驗證LEACH-C協(xié)議選出的簇頭分布良好，在100 m×100 m區(qū)域中，隨機部署100個節(jié)點，并隨機取樣驗證LEACH協(xié)議簇頭與LEACH-C協(xié)議簇頭的分布情況，其對比圖如圖1所示。

由上圖可以看出，因LEACH協(xié)議對簇頭的選舉并未考慮簇的平均分布，故LEACH協(xié)議選出的簇頭易在一小部分區(qū)域內(nèi)密集分布，導(dǎo)致傳輸信息時不必要的能量消耗。而LEACH-C協(xié)議的首簇頭選舉被要求為鄰居節(jié)點較多的節(jié)點，這樣就保證了在節(jié)點分布相對密集的區(qū)域附近必有簇頭，并使得在兩倍的Rs半徑內(nèi)不再有其他簇頭分布，從而達到使網(wǎng)絡(luò)中的簇分布較為均勻的效果。

3.3 仿真結(jié)果分析

圖2是基站位置為(50，180)，監(jiān)測區(qū)域A大小為100 m×100 m，節(jié)點數(shù)量為100時生存節(jié)點數(shù)與網(wǎng)絡(luò)工作時間(輪數(shù))之間的關(guān)系圖.可以看到，圖2

圖1 LEACH協(xié)議與LEACH-C協(xié)議簇頭分布對比圖

中表示LEACH協(xié)議的曲線在第700輪開始出現(xiàn)節(jié)點死亡，最后一個節(jié)點的死亡時間為1 800輪。而LEACH-C協(xié)議的第一個死亡節(jié)點出現(xiàn)在第1 300輪，到2 500輪后節(jié)點的全部死亡。由此可知，從以生存節(jié)點數(shù)為網(wǎng)絡(luò)壽命的定義出發(fā)，相比LEACH協(xié)議，LEACH-C協(xié)議使得網(wǎng)絡(luò)壽命提高了24%(第1個節(jié)點死亡)。

圖2 生存節(jié)點數(shù)與輪數(shù)關(guān)系圖

圖3 網(wǎng)絡(luò)覆蓋率與輪數(shù)關(guān)系圖

圖3是基站位置為(50，180)，監(jiān)測區(qū)域A大小為100 m×100 m，節(jié)點數(shù)量為100時生存節(jié)點網(wǎng)絡(luò)覆蓋率與網(wǎng)絡(luò)工作時間(輪數(shù))之間的關(guān)系圖。因為LEACH中所有節(jié)點都處于工作狀態(tài)，能量消耗較快，又由于選取簇頭時沒有考慮節(jié)點能量大小，導(dǎo)致節(jié)點快速死亡，網(wǎng)絡(luò)覆蓋率迅速下降。而LEACH-C協(xié)議由于每輪簇頭分布相對均勻且按優(yōu)先級選取工作節(jié)點，并非每輪中每個節(jié)點都在工作，故在網(wǎng)絡(luò)壽命初期，網(wǎng)絡(luò)覆蓋率并沒LEACH協(xié)議高，但網(wǎng)絡(luò)壽命后期LEACH-C協(xié)議覆蓋率明顯處于平穩(wěn)下降狀態(tài)。從以網(wǎng)絡(luò)覆蓋率為網(wǎng)絡(luò)壽命的定義出發(fā)，與LEACH協(xié)議相比，LEACH-C協(xié)議使整個網(wǎng)絡(luò)壽命提高了28%(網(wǎng)絡(luò)覆蓋率為0)。

4 結(jié)論

本文提出了一個基于LEACH協(xié)議的無線傳感器網(wǎng)絡(luò)覆蓋率算法－－－LEACH-C協(xié)議。在LEACHC算法中，節(jié)點通過與鄰居節(jié)點交換信息，根據(jù)鄰居節(jié)點的個數(shù)及剩余能量選擇簇頭節(jié)點及工作節(jié)點。仿真實驗結(jié)果表明:在不需要節(jié)點的位置信息的前提下，LEACH-C算法不僅可以提供良好的覆蓋性能，而且在減少整體能量消耗，網(wǎng)絡(luò)能量均衡方面也具有良好的性能。

［1］李夢娥，張登銀.無線傳感器網(wǎng)絡(luò)簇類路由協(xié)議的研究［J］.電子工程師，2008(4):60－63.

［2］吳臻，金心宇.無線傳感器網(wǎng)絡(luò)的LEACH算法的改進［J］.傳感技術(shù)學(xué)報，2006，19(1):34－36.

［3］王偉，林鋒，周激流.無線傳感器網(wǎng)絡(luò)覆蓋問題的研究進展［J］.計算機應(yīng)用研究，2010，27(1):32－35.

［4］王燕莉，安世全.無線傳感器網(wǎng)絡(luò)的覆蓋問題研究［J］.傳感技術(shù)學(xué)報，2005，18(2):401－406.

［5］Tian D，Georganas N.A Coverage Preserved Node Scheduling Scheme for Large Wireless Network［J］.Proc.of First International Workshop on Wireless Sensor Network and Applications(WSNA’02)，Atlanta USA，2002，September，32－41.

［6］Zhang H，Hou J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］.International Journal of Ad Hoc and Sensor Wireless Networks，2005，1(1):89－124.

［7］Lu Jun，Wang Jin-su，Tatsuya Suda.Scalable Coverage in Maintenance for Dense Wireless Sensor Networks［J］.IEEE 2006，651－660.

［8］Luo Han-mei，Wang Huan-zhao.A Precise Coverager Control Protocol with Limited Communication in Wireless Sensor Networks［C］//IEEE International Symposium on Embedded Computing，2008，149－154.

［9］單曉娜，李力.LEACH路由協(xié)議技術(shù)的分析及改進［J］.計算機與現(xiàn)代化，2009(9):81－83.

［10］毛鶯池，劉明，陳力軍，等.DELIC一種高效節(jié)能的與節(jié)點位置無關(guān)的傳感器網(wǎng)絡(luò)覆蓋協(xié)議［J］.計算機研究與發(fā)展，2006，43(2):187－195.

［9］任秀麗，教傳亮，薛建生，等.與節(jié)點位置無關(guān)的無線傳感器網(wǎng)絡(luò)覆蓋控制算法［J］.小型微型計算機系統(tǒng)，2011，32(1):121－125.

［10］劉明，龔海剛，毛鶯池，等.高效節(jié)能的傳感器網(wǎng)絡(luò)數(shù)據(jù)收集和聚合協(xié)議［J］.軟件學(xué)報，2005，16(12):2106－2116.