基于簇頭協(xié)作的LEACH-C路由策略研究

天津工業(yè)大學(xué)電氣工程與自動(dòng)化學(xué)院 楊振偉 郭利進(jìn)

引言

隨著計(jì)算機(jī)和通信技術(shù)的快速發(fā)展，WSN(無(wú)線傳感器網(wǎng)絡(luò):Wireless Sensor Network)正受到了前所未有的關(guān)注和重視[1]。由若干個(gè)具備感知、計(jì)算和通信能力的節(jié)點(diǎn)構(gòu)成，WSN技術(shù)現(xiàn)在已被廣泛應(yīng)用于氣象監(jiān)測(cè)、環(huán)境監(jiān)測(cè)、深海導(dǎo)航及軍事監(jiān)視等生活的各類領(lǐng)域[2,3]，為確保這些持續(xù)性具體監(jiān)測(cè)和數(shù)據(jù)動(dòng)態(tài)跟蹤，WSN工作時(shí)間必須要在一定程度上盡可能延長(zhǎng)。另一方面，WSN中的成員節(jié)點(diǎn)在數(shù)據(jù)無(wú)線傳輸通信、信息的分析處理、信號(hào)傳輸帶寬、電池電量供給以及存儲(chǔ)空間等方面都受到了限制，傳統(tǒng)路由協(xié)議無(wú)法直接應(yīng)用于當(dāng)前的無(wú)線傳感器網(wǎng)絡(luò)。因此，一個(gè)優(yōu)良的路由協(xié)議應(yīng)當(dāng)涵蓋低能耗的數(shù)據(jù)傳輸路徑，良好的可擴(kuò)展性、強(qiáng)大的魯棒性、良好的容錯(cuò)性、良好的穩(wěn)定性和低延遲性等特征。所以，設(shè)計(jì)一個(gè)高穩(wěn)定性、強(qiáng)魯棒性、低能耗的特定路由協(xié)議對(duì)無(wú)線傳感器網(wǎng)絡(luò)的進(jìn)一步發(fā)展意義相當(dāng)重大[4]。

1 LEACH相關(guān)協(xié)議

LEACH（低能量自適應(yīng)聚類層次:Low Energy Adaptive Clustering Hierarchy）協(xié)議是一種典型的自適應(yīng)聚類路由協(xié)議，其以數(shù)據(jù)為中心利用單層簇路由[5]。LEACH協(xié)議簇頭選舉策略及其單跳數(shù)據(jù)傳輸也存在一定的弊端，這些弊端對(duì)網(wǎng)絡(luò)性能的影響不可小覷。近些年，基于LEACH路由協(xié)議的不斷研究與改進(jìn)，已然然成效顯著。文獻(xiàn)[6]中提到了LEACH路由協(xié)議中簇頭選舉機(jī)制的改進(jìn)，當(dāng)前一輪的簇頭達(dá)到一定條件時(shí)，再重新選舉簇頭，這樣便減少了每輪簇頭選舉所帶來(lái)的能量消耗。文獻(xiàn)[7]中展示了一種多跳式的路由協(xié)議，基本原理是讓距離較遠(yuǎn)的節(jié)點(diǎn)先選擇一個(gè)離自己位置最近的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)，相較于與終端直接通信，距離大大縮短。文獻(xiàn)[8]提出在節(jié)點(diǎn)分完簇后，接下來(lái)在每一個(gè)簇內(nèi)，根據(jù)節(jié)點(diǎn)之間的相互距離和數(shù)據(jù)相似度再次進(jìn)行分組，并在每一個(gè)分組內(nèi)重新選取一個(gè)代表節(jié)點(diǎn)，其任務(wù)是將數(shù)據(jù)發(fā)送給簇頭。文獻(xiàn)[9]根據(jù)能量分布和節(jié)點(diǎn)位置信息，引入了代價(jià)函數(shù)進(jìn)行簇頭的選舉，其中，能量更高和位置更優(yōu)的節(jié)點(diǎn)會(huì)優(yōu)先當(dāng)選為簇頭，這樣，各個(gè)節(jié)點(diǎn)的工作任務(wù)分配會(huì)更加合理。文獻(xiàn)[10]采用了一些綜合性較強(qiáng)的概率公式來(lái)定義閾值函數(shù)，使網(wǎng)絡(luò)負(fù)載更加均衡，有效增加WSN的生命周期。

上述基于LEACH的改進(jìn)算法不同程度上降低了網(wǎng)絡(luò)能耗，但依然存在很多明顯的缺陷，如WSN網(wǎng)絡(luò)中的簇頭分布具有很大的隨機(jī)性；簇成員的加入僅僅考慮成員節(jié)點(diǎn)與簇頭的距離，沒(méi)有考慮該簇頭的能量；另外，一個(gè)簇內(nèi)只有一個(gè)簇頭，簇頭由于需要完成信息處理與路由而需消耗較大的能量。所有這些不足導(dǎo)致WSN能耗消耗不均衡，大大影響網(wǎng)絡(luò)的正常工作時(shí)間。

2 改進(jìn)的算法

2.1 算法描述

本文算法的主要研究思想是研究如何分擔(dān)WSN簇頭的網(wǎng)絡(luò)能耗，均勻網(wǎng)絡(luò)簇頭分布，優(yōu)化網(wǎng)絡(luò)分簇，均衡全局能耗，延長(zhǎng)系統(tǒng)有效工作時(shí)間。為了彌補(bǔ)傳統(tǒng)的LEACH協(xié)議存在WSN中簇頭分布不均勻和節(jié)點(diǎn)能量消耗過(guò)于集中等缺陷，本文采用一種改進(jìn)的LEACH路由算法，即基于主次簇頭協(xié)作的LEACH路由算法LEACH-C(LEACH-Cooperative)。主要在如下幾個(gè)方面進(jìn)行改進(jìn)：

（1）簇頭選取過(guò)程：在LEACH簇頭選取的基礎(chǔ)上，進(jìn)一步根據(jù)距離與能量因素進(jìn)行次簇頭的選擇，也即實(shí)現(xiàn)同一個(gè)簇的雙簇頭選擇（收集處理和發(fā)送分開(kāi)），有效緩解LEACH算法中簇頭分布不均、能量消耗過(guò)快的不足。

（2）簇的創(chuàng)建過(guò)程：在傳統(tǒng)LEACH路由算法中簇成員的確定是以與“準(zhǔn)簇頭”距離的因素來(lái)確定加入規(guī)則，但是這樣容易造成整個(gè)監(jiān)測(cè)區(qū)域簇的分布不均勻，進(jìn)而導(dǎo)致采集信息高度的相關(guān)性和冗余性。在本文提出的LEACH-C路由協(xié)議中，利用成員節(jié)點(diǎn)與主次簇頭（具體為主次簇頭之間的虛擬坐標(biāo)）之間的距離選擇加入不同的簇，能夠有效克服能耗消耗過(guò)于集中的缺陷，為了避免采集信息的冗余性和進(jìn)一步降低系統(tǒng)能耗，采用臨近距離內(nèi)休眠機(jī)制。

（3）特殊節(jié)點(diǎn)處理：無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署的隨機(jī)性，可能造成個(gè)別區(qū)域節(jié)點(diǎn)分布嚴(yán)重不均勻，存在游離節(jié)點(diǎn)即在參考距離內(nèi)沒(méi)有歸屬任何一個(gè)簇，基于此，本文也提出了游離節(jié)點(diǎn)的主次協(xié)作傳輸或選擇加入最近的簇的規(guī)則進(jìn)行信息的采集與路由。

LEACH-C的詳細(xì)流程如圖1所示。基于分簇路由方式的無(wú)線傳感網(wǎng)絡(luò)，簇頭選取和確定在無(wú)線傳統(tǒng)中起著至關(guān)重要的作用。如表1所示，WSN各成員節(jié)點(diǎn)都擁有并維護(hù)一份屬于自身的路由屬性表。路由表中，網(wǎng)絡(luò)節(jié)點(diǎn)被唯一編號(hào)，并用字段ID表示，該字段在網(wǎng)絡(luò)初始化時(shí)被隨機(jī)標(biāo)記；Alive表示網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)是否存活，“0”和“1”分別表示消亡和存活；Sleep表示網(wǎng)絡(luò)節(jié)點(diǎn)是否為休眠狀態(tài)，“0”和“1”分別表示休眠和活躍；Head-1字段代表WSN節(jié)點(diǎn)是否成為主簇頭，其中0(1)代表“否”或“是”，在WSN初始化階段，Head-1字段都默認(rèn)為“0”；同樣，Head-2字段代表WSN節(jié)點(diǎn)是否成為協(xié)作簇頭即次簇頭，其中0(1)代表“否”或“是”，在WSN初始化階段，Head-2字段都默認(rèn)為“0”；表2-1中的Active-1和Active-2字段代表WSN節(jié)點(diǎn)是否參與主簇頭或者次簇頭的選取，“0”代表該成員在本輪簇頭（主簇頭和次簇頭）選舉過(guò)程沒(méi)有當(dāng)選，或沒(méi)有收到簇頭(包括次簇頭)的廣播信息，或收到至少兩個(gè)簇頭(包括對(duì)應(yīng)的次簇頭)的廣播信息，則節(jié)點(diǎn)標(biāo)記為網(wǎng)絡(luò)中的游離節(jié)點(diǎn)。“1”字段表示節(jié)點(diǎn)當(dāng)選為主或次簇頭，或在給定距離范圍內(nèi)僅收到一個(gè)簇頭廣播消息，該字段的初始默認(rèn)值為“0”；字段Cluster表示該WSN成員節(jié)點(diǎn)是否已經(jīng)成功加入網(wǎng)絡(luò)中的某個(gè)簇，取值為“1”（已入簇）或者“0”（未入簇），該字段初始值標(biāo)記為“0”。該改進(jìn)協(xié)議LEACH-C路由屬性表是在WSN剛開(kāi)始初始化時(shí)被植入對(duì)應(yīng)初始值，同時(shí)在WSN的簇創(chuàng)建過(guò)程和穩(wěn)定過(guò)程中被讀取和改寫(xiě)。

圖1 LEACH-C路由協(xié)議流程圖

表1 WSN成員節(jié)點(diǎn)路由屬性表

2.2 協(xié)作簇頭的確定

為避免LEACH能量消耗過(guò)快以及簇頭節(jié)點(diǎn)分布集中,本路由算法兼顧主簇頭和次簇頭剩余能量和相對(duì)距離,相對(duì)位置等因素,基于局部集中法則選取“簇頭對(duì)”,對(duì)于擁有成員個(gè)數(shù)為N的WSN,預(yù)設(shè)“簇頭對(duì)”節(jié)點(diǎn)占整個(gè)WSN網(wǎng)絡(luò)節(jié)點(diǎn)的比例為P，WSN系統(tǒng)初始化后，基站為網(wǎng)絡(luò)中的節(jié)點(diǎn)分配分簇參考距離Rre1

字段Active-1為“0”的節(jié)點(diǎn)首先產(chǎn)生隨機(jī)小數(shù)，當(dāng)小于預(yù)先設(shè)定的閾值（公式2-1）時(shí)，則該節(jié)點(diǎn)當(dāng)選為候選主簇頭；首先當(dāng)選候選主簇頭節(jié)點(diǎn)則為第一個(gè)主簇頭，隨即該節(jié)點(diǎn)廣播消息并且將其Head-1的屬性置為“1”。同時(shí)，“主簇頭”根據(jù)Rre22=，通過(guò)廣播為其周圍網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)放對(duì)應(yīng)次簇頭選擇參考距離Rre2。Active-2字段為“0”的網(wǎng)絡(luò)節(jié)點(diǎn)根據(jù)接收的廣播信息確定是否成為次節(jié)點(diǎn)，當(dāng)“準(zhǔn)次簇頭”接收到主簇頭的廣播信息后加權(quán)自身剩余能量因素啟動(dòng)定時(shí)器，首先定時(shí)完成的節(jié)點(diǎn)廣播消息確定為次簇頭節(jié)點(diǎn)，同時(shí)將自身Head-2屬性值設(shè)置為“1”。進(jìn)一步，基站記錄下網(wǎng)絡(luò)中的已經(jīng)產(chǎn)生的“簇頭對(duì)”數(shù)目，在Rre1內(nèi)的節(jié)點(diǎn)接收到消息后將其Active-1和Active-2字段屬性值設(shè)置為1，該節(jié)點(diǎn)本輪將不再參與主簇頭或者次簇頭的競(jìng)選。依照這樣的過(guò)程，依次產(chǎn)生其他“簇頭對(duì)”，由BS控制WSN網(wǎng)絡(luò)中本輪產(chǎn)生“簇頭對(duì)”個(gè)數(shù)。當(dāng)“簇頭對(duì)”個(gè)數(shù)達(dá)到P*N后，本輪“簇頭對(duì)”選取結(jié)束。

公式（2-1）和公式(2-2)中的各個(gè)參數(shù)具體含義為：S表示監(jiān)測(cè)區(qū)域WSN的面積，N為WSN中節(jié)點(diǎn)數(shù)目，P表示W(wǎng)SN中簇頭節(jié)點(diǎn)的所占百分比，M為分塊距離參考參數(shù)，一般選擇為2-5，具體為當(dāng)主簇頭節(jié)點(diǎn)與基站較遠(yuǎn)的時(shí)候，M選擇較小值，此處考慮是簇與基站較遠(yuǎn)，需要較遠(yuǎn)次簇頭進(jìn)行信息路由。

2.3 LEACH-C簇的形成規(guī)則

在“簇頭對(duì)”的確定過(guò)程中遵循每個(gè)“簇頭對(duì)”節(jié)點(diǎn)的參考（本章采用的是主次節(jié)點(diǎn)中間坐標(biāo)為簇的虛擬中心坐標(biāo)）范圍內(nèi)不再產(chǎn)生其他“簇頭對(duì)”。這樣WSN網(wǎng)絡(luò)中就有可能存在部分非簇頭成員節(jié)點(diǎn)在給定的參考半徑Rre1內(nèi)沒(méi)有“簇頭對(duì)”，或者在參考范圍內(nèi)存在多個(gè)“簇頭對(duì)”，此成員節(jié)點(diǎn)稱為游離節(jié)點(diǎn)，如圖2所示。路由屬性表中字段Active-1和字段Active-2屬性值為1的非簇頭節(jié)點(diǎn)，此時(shí)應(yīng)根據(jù)公式（2-3）計(jì)算參數(shù)最小的d值，參考距離內(nèi)最近的距離“簇頭對(duì)”入簇；而對(duì)于字段Active-x（字段Active-1和字段Active-2）的屬性值為0的非簇頭節(jié)點(diǎn)，在該階段根據(jù)公式(2-3)分別計(jì)算各自入簇閾值Tclu，選擇計(jì)算閾值Tclu最大的主簇頭節(jié)點(diǎn)入簇，即選擇距離較短、剩余能量較高的主簇頭節(jié)點(diǎn)入簇。

圖2 LEACH-C中的節(jié)點(diǎn)入簇示意圖

公式（2-3）中各參數(shù)表示含義分別為：參數(shù)d表示當(dāng)前節(jié)點(diǎn)到“簇頭對(duì)”中間節(jié)點(diǎn)的距離，dmax表示任意兩成員節(jié)點(diǎn)的最大距離，Einit表示網(wǎng)絡(luò)節(jié)點(diǎn)能量初始值，Ecur則表示節(jié)點(diǎn)剩余能量。

傳統(tǒng)的LEACH路由協(xié)議中，由于簇頭直接路由信息至基站，這樣就會(huì)導(dǎo)致遠(yuǎn)離基站的簇在信息路由階段消耗大量的能量，進(jìn)而導(dǎo)致WSN網(wǎng)絡(luò)的能量消耗過(guò)快，且網(wǎng)絡(luò)能量消耗不均衡，導(dǎo)致WSN的有效監(jiān)測(cè)時(shí)間較短。基于此，在此改進(jìn)的LEACH-C協(xié)議中，主簇頭負(fù)責(zé)與簇內(nèi)普通成員節(jié)點(diǎn)進(jìn)行通信，即搜集普通成員節(jié)點(diǎn)采集的信息：降低節(jié)點(diǎn)信息的冗余度同時(shí)節(jié)省節(jié)點(diǎn)能量，LEACH-C路由協(xié)議在簇內(nèi)部讓低能量節(jié)點(diǎn)輪流進(jìn)入休眠，進(jìn)而有效延長(zhǎng)網(wǎng)絡(luò)有效工作時(shí)間。在此改進(jìn)的LEACH-C協(xié)議中，WSN中的次簇頭節(jié)點(diǎn)主要負(fù)責(zé)與主簇頭節(jié)點(diǎn)以及WSN網(wǎng)絡(luò)中的基站節(jié)點(diǎn)進(jìn)行通信，當(dāng)主簇頭離基站較遠(yuǎn)時(shí)，為了有效提高系統(tǒng)的能量均衡和網(wǎng)絡(luò)生存周期，次簇頭的參考距離中的M參數(shù)一般取較小值，也即確保次簇頭與主簇頭之間距離較大以期與基站距離較近，這樣可有效彌補(bǔ)由于該簇與基站距離遠(yuǎn)傳輸信息消耗的能量大的缺陷。

3 LEACH-C仿真分析

針對(duì)WSN仿真平臺(tái)Atos-SensorSim進(jìn)行實(shí)驗(yàn)分析提出的LEACH-C路由協(xié)議，將本章提出的LEACH-C路由協(xié)議與傳統(tǒng)的LEACH路由協(xié)議進(jìn)行仿真分析。參數(shù)具體設(shè)置如：在500m*200m監(jiān)測(cè)范圍中隨機(jī)分布200個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。基站坐標(biāo)位于網(wǎng)絡(luò)中心，即（250,100）位置的WSN，本實(shí)驗(yàn)參數(shù)如表2

表2 LEACH-C參數(shù)的配置表

3.1 WSN的生命周期分析

首先分析WSN中存活節(jié)點(diǎn)數(shù)目與分簇輪數(shù)之間的關(guān)系，為比較本章所提的協(xié)作簇頭路由算法，即LEACH-C協(xié)議的性能特征，圖3中畫(huà)出了傳統(tǒng)的LEACH路由協(xié)議所對(duì)應(yīng)的曲線。

圖3 網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)與輪數(shù)之間關(guān)系

根據(jù)圖3可得出如下的結(jié)論：（1）所提的LEACH-C協(xié)作簇頭路由算法顯著提高了WSN中節(jié)點(diǎn)的存活率，即在本參數(shù)設(shè)置條件下，傳統(tǒng)的LEACH路由協(xié)議在第22輪左右時(shí)，WSN系統(tǒng)開(kāi)始出現(xiàn)消亡節(jié)點(diǎn)，但改進(jìn)的算法LEACH-C出現(xiàn)消亡節(jié)點(diǎn)大約在82輪；（2）分簇輪數(shù)為300之前，傳統(tǒng)的LEACH路由算法的節(jié)點(diǎn)存活率大約在50%，也即網(wǎng)絡(luò)有一半左右節(jié)點(diǎn)開(kāi)始不能正常工作，而本文所提出改進(jìn)的協(xié)作簇頭路由協(xié)議LEACH-C路由協(xié)議節(jié)點(diǎn)存活率高于60%，整體網(wǎng)絡(luò)中正常工作的節(jié)點(diǎn)存活率平均提高了10%以上。基于以上分析，可看出當(dāng)基站位于隨機(jī)分布WSN網(wǎng)絡(luò)中心處，所提的改進(jìn)算法，LEACH-C路由協(xié)議能大大提高了WSN網(wǎng)絡(luò)節(jié)點(diǎn)存活率，有效延長(zhǎng)了網(wǎng)絡(luò)有效工作時(shí)間。

3.2 LEACH-C網(wǎng)絡(luò)能耗分析

圖4進(jìn)一步分析WSN網(wǎng)絡(luò)總能量消耗與分簇輪數(shù)之間的關(guān)系，為便于比較分析，在此也畫(huà)出了傳統(tǒng)的LEACH路由協(xié)議對(duì)應(yīng)的關(guān)系圖。

從圖4顯示結(jié)果可以看出，所提的新算法LEACH-C在網(wǎng)絡(luò)能耗的統(tǒng)計(jì)上低于傳統(tǒng)的LEACH路由算法。在設(shè)置的具體仿真環(huán)境場(chǎng)景中，傳統(tǒng)的LEACH路由協(xié)議在輪數(shù)18輪左右時(shí)，網(wǎng)絡(luò)能耗大約是2000J，而此時(shí)的LEACH-C的網(wǎng)絡(luò)能耗只有800左右。進(jìn)一步分析可以發(fā)現(xiàn)，隨著運(yùn)行輪數(shù)的增加，所提的LEACH-C路由算法性能優(yōu)勢(shì)更加明顯，也即隨著輪數(shù)增加(持續(xù)到80輪左右)LEACH-C的能量消耗優(yōu)相對(duì)于傳統(tǒng)的LEACH差距更加擴(kuò)大，進(jìn)一步說(shuō)明所提算法的優(yōu)越性。在輪數(shù)250以后，相較于LEACH算法，改進(jìn)的LEACH-C算法相對(duì)傳統(tǒng)的LEACH路由算法，網(wǎng)絡(luò)能量消耗大約節(jié)省920J。根據(jù)以上分析可知，所提基于簇頭協(xié)作的路由算法LEACH-C協(xié)議通過(guò)分?jǐn)偩W(wǎng)絡(luò)簇頭負(fù)載，有效均衡網(wǎng)絡(luò)簇頭節(jié)點(diǎn)的負(fù)載分配，進(jìn)一步降低了WSN網(wǎng)絡(luò)總能量消耗。

4 結(jié)語(yǔ)

本文首先詳細(xì)分析和討論經(jīng)典的WSN分簇路由協(xié)議——LEACH路由協(xié)議。總結(jié)LEACH路由協(xié)議的不足：網(wǎng)絡(luò)中的能量消耗不均衡、網(wǎng)絡(luò)中的節(jié)點(diǎn)局部負(fù)載過(guò)大、網(wǎng)絡(luò)中釆集的數(shù)據(jù)具有很高的冗余度和相關(guān)度、簇頭選擇方式不合理、特殊節(jié)點(diǎn)沒(méi)有充分考慮等等。在此基礎(chǔ)上提出了一種改進(jìn)的分層路由算法：基于協(xié)作簇頭的LEACH-C路由協(xié)議。在主簇頭選定的情況下根據(jù)相對(duì)距離與剩余能量進(jìn)行次簇頭的選擇，系統(tǒng)中每個(gè)節(jié)點(diǎn)維護(hù)自身路由屬性表，WSN中的節(jié)點(diǎn)根據(jù)距離和能量?jī)蓚€(gè)因素選擇入簇；在信息傳輸階段，采用休眠機(jī)制和遠(yuǎn)距離簇頭路由方式進(jìn)一步降低系統(tǒng)能耗；最后通過(guò)仿真分析得到LEACH-C相對(duì)于傳統(tǒng)的LEACH協(xié)議能夠有效延長(zhǎng)網(wǎng)絡(luò)工作時(shí)間，均衡網(wǎng)絡(luò)負(fù)載。