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

引言

隨著計算機和通信技術(shù)的快速發(fā)展，WSN(無線傳感器網(wǎng)絡(luò):Wireless Sensor Network)正受到了前所未有的關(guān)注和重視[1]。由若干個具備感知、計算和通信能力的節(jié)點構(gòu)成，WSN技術(shù)現(xiàn)在已被廣泛應(yīng)用于氣象監(jiān)測、環(huán)境監(jiān)測、深海導(dǎo)航及軍事監(jiān)視等生活的各類領(lǐng)域[2,3]，為確保這些持續(xù)性具體監(jiān)測和數(shù)據(jù)動態(tài)跟蹤，WSN工作時間必須要在一定程度上盡可能延長。另一方面，WSN中的成員節(jié)點在數(shù)據(jù)無線傳輸通信、信息的分析處理、信號傳輸帶寬、電池電量供給以及存儲空間等方面都受到了限制，傳統(tǒng)路由協(xié)議無法直接應(yīng)用于當(dāng)前的無線傳感器網(wǎng)絡(luò)。因此，一個優(yōu)良的路由協(xié)議應(yīng)當(dāng)涵蓋低能耗的數(shù)據(jù)傳輸路徑，良好的可擴展性、強大的魯棒性、良好的容錯性、良好的穩(wěn)定性和低延遲性等特征。所以，設(shè)計一個高穩(wěn)定性、強魯棒性、低能耗的特定路由協(xié)議對無線傳感器網(wǎng)絡(luò)的進一步發(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ù)傳輸也存在一定的弊端，這些弊端對網(wǎng)絡(luò)性能的影響不可小覷。近些年，基于LEACH路由協(xié)議的不斷研究與改進，已然然成效顯著。文獻[6]中提到了LEACH路由協(xié)議中簇頭選舉機制的改進，當(dāng)前一輪的簇頭達到一定條件時，再重新選舉簇頭，這樣便減少了每輪簇頭選舉所帶來的能量消耗。文獻[7]中展示了一種多跳式的路由協(xié)議，基本原理是讓距離較遠的節(jié)點先選擇一個離自己位置最近的節(jié)點進行數(shù)據(jù)的轉(zhuǎn)發(fā)，相較于與終端直接通信，距離大大縮短。文獻[8]提出在節(jié)點分完簇后，接下來在每一個簇內(nèi)，根據(jù)節(jié)點之間的相互距離和數(shù)據(jù)相似度再次進行分組，并在每一個分組內(nèi)重新選取一個代表節(jié)點，其任務(wù)是將數(shù)據(jù)發(fā)送給簇頭。文獻[9]根據(jù)能量分布和節(jié)點位置信息，引入了代價函數(shù)進行簇頭的選舉，其中，能量更高和位置更優(yōu)的節(jié)點會優(yōu)先當(dāng)選為簇頭，這樣，各個節(jié)點的工作任務(wù)分配會更加合理。文獻[10]采用了一些綜合性較強的概率公式來定義閾值函數(shù)，使網(wǎng)絡(luò)負載更加均衡，有效增加WSN的生命周期。

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

2 改進的算法

2.1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 LEACH-C仿真分析

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

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

3.1 WSN的生命周期分析

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

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

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

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

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

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

4 結(jié)語

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