衛(wèi) 琪

（中北大學 電子與計算機科學技術學院，山西 太原 030051）

0 引言

無線通信技術和電子技術的發(fā)展使得無線傳感器網(wǎng)絡(Wireless Sensor Networks, WSN)方面的研究受到越來越多的重視。WSN可實現(xiàn)數(shù)據(jù)的采集量化、處理融合和傳輸應用，它是信息技術中的一個新的領域，在人們生產(chǎn)、生活的各個領域都有廣闊的應用前景[1-3]。

WSN的一個基本功能就是將監(jiān)測區(qū)域內(nèi)發(fā)生的事件或感知到的數(shù)據(jù)傳送到基站供進一步分析使用，WSN路由協(xié)議對這項功能的實現(xiàn)起著至關重要的作用[4]。通常情況下，傳感器節(jié)點能量有限且無法補充，因此降低能量損耗、延長網(wǎng)絡的生命周期是WSN中設計有效路由算法的核心目標。WSN的路由協(xié)議作為一項關鍵技術已成為目前研究熱點。

本文在對LEACH協(xié)議研究的基礎上，結合其優(yōu)點、針對其不足，提出一種基于剩余能量且負載均衡的無線傳感器網(wǎng)絡能量有效分簇路由協(xié)議(LEACH-improved)，可以更好地均衡網(wǎng)絡負載，延長網(wǎng)絡生存時間。

1 相關工作

LEACH ( Low-Energy Adaptive Clustering Hierachy)[5]低功耗自適應分簇路由協(xié)議，是最早提出的分簇路由算法。它的核心思想是通過周期性的隨機選舉產(chǎn)生簇頭，使網(wǎng)絡能耗平均分配到每個傳感器節(jié)點上，進而延長網(wǎng)絡的生存時間。 LEACH協(xié)議有許多優(yōu)點，通過動態(tài)分簇，使所有節(jié)點平均分擔中繼通信業(yè)務[6]；在簇內(nèi)進行的本地融合技術減少了發(fā)往sink的數(shù)據(jù)量，特別是處理具有高度相關性的數(shù)據(jù)時，冗余數(shù)據(jù)被大量消除[7]；作為一種分布式的分簇路由協(xié)議，節(jié)點既不需要全局的網(wǎng)絡信息[8]，也不需要來自基站的任何控制信息。但是，LEACH在簇頭選擇時僅依靠節(jié)點產(chǎn)生隨機數(shù)，而未考慮參選節(jié)點的能量水平；頻繁的簇重構，且每次網(wǎng)絡的拓撲結構都會較大改變；要求所有簇頭與sink一跳通信，為遠離sink的簇頭帶來很大數(shù)據(jù)傳輸能耗，同時造成簇頭間能量消耗不均衡。

2 系統(tǒng)模型

2.1 網(wǎng)絡模型

LEACH-improved協(xié)議采用如下網(wǎng)絡模型：考慮一個具有N的傳感器節(jié)點的傳感器網(wǎng)絡，節(jié)點周期性的收集數(shù)據(jù)，相應的節(jié)點集合可表示為S= {s1，s2， …，sn} 。假設網(wǎng)絡和傳感器節(jié)點具有以下性質(zhì)：

（1）N個傳感器節(jié)點隨機、均勻地分布在M×M的正方形區(qū)域中，節(jié)點足夠密集，保證一個節(jié)點的有效發(fā)射半徑內(nèi)存在其他節(jié)點。節(jié)點部署之后不再發(fā)生位置變化。

（2）sink節(jié)點位于觀測區(qū)域外的某一固定位置，且沒有能量和發(fā)射功率的限制。

（3）傳感器網(wǎng)絡為同構網(wǎng)絡，即所有傳感器節(jié)點初始能量相等，都有計算能力、信號處理能力和數(shù)據(jù)融合功能，且在網(wǎng)絡中地位平等。每個節(jié)點都有唯一的標識（ID）。

（4）節(jié)點不知道自身的位置信息。

（5）節(jié)點可以感知當前自身的能量。

（6）節(jié)點的無線發(fā)射功率可控，即節(jié)點可以根據(jù)接收者的距離遠近來調(diào)整其發(fā)射功率以節(jié)約能量。

（7）各節(jié)點間的鏈路對稱。若已知對方發(fā)射功率，節(jié)點可以根據(jù)接收信號的強度RSSI計算發(fā)送者到自己的近似距離。

2.2 能量模型

LEACH-improved協(xié)議采用LEACH協(xié)議使用的無線通信模型。節(jié)點發(fā)射k bit的數(shù)據(jù)到距離為d的接收方，消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，如公式（1）所示。

其中,Eelec表示發(fā)射電路損耗的能量，與編碼、調(diào)制、濾波等相關；它與mp分別表示自由空間和多徑衰落信道模型下功率放大器的能量消耗常數(shù)。節(jié)點在傳輸數(shù)據(jù)時具體采用哪種信道是由發(fā)送節(jié)點和接收節(jié)點之間的距離d決定的。如果兩者之間的距離小于距離閾值d0，則采用自由空間信道模型；若距離大于d0，則采用多徑衰落信道模型。很明顯，后者消耗的能量比前者大得多。

節(jié)點接收k bit數(shù)據(jù)消耗的能量為：

此外，數(shù)據(jù)融合也會消耗一定能量，用EDA表示融合單位比特數(shù)據(jù)所消耗的能量。

3 LEACH-improved協(xié)議

LEACH-improved協(xié)議的思想是利用分簇和建立簇間多跳路徑，來達到均衡網(wǎng)絡負載、延長網(wǎng)絡壽命的目的。在首輪成簇時，協(xié)議借鑒了LEACH的隨機簇頭選舉機制，簡單、快速地將網(wǎng)絡分簇并選出首輪簇頭節(jié)點。隨著網(wǎng)絡的運行，進入非首輪成簇階段，協(xié)議考慮了每個簇內(nèi)參選節(jié)點的剩余能量，選擇剩余能量較多的節(jié)點擔當下一任簇頭，從而避免了能量已經(jīng)不足的節(jié)點擔當簇頭。

簇形成之后，LEACH-improved協(xié)議借鑒了泛洪算法的思想，各簇頭通過轉(zhuǎn)發(fā)來自sink的包含跳數(shù)信息的廣播包，在簇頭節(jié)點間建立和選擇多跳傳輸路徑，使得遠離sink的簇頭不再使用長距離單跳通信方式傳輸數(shù)據(jù)到sink。

LEACH-improved協(xié)議中，簇頭節(jié)點承擔著數(shù)據(jù)采集、數(shù)據(jù)融合以及數(shù)據(jù)轉(zhuǎn)發(fā)3項任務，能量消耗比普通節(jié)點大。為了平衡節(jié)點能量損耗，延長網(wǎng)絡壽命，本協(xié)議也以“輪”為單位周期性執(zhí)行，每輪循環(huán)分為簇形成階段、簇間多跳路徑建立和選擇階段以及數(shù)據(jù)傳輸階段。其中，簇形成階段根據(jù)實際情況又可分為首輪簇形成階段和非首輪簇形成階段。

3.1 簇形成階段

3.1.1 首輪簇形成階段

本階段協(xié)議借鑒LEACH的簇頭選舉及成簇機制。因為初始狀態(tài)下所有節(jié)點的能量相同，所以首輪成簇時不需要考慮節(jié)點的能量狀況。每個節(jié)點產(chǎn)生一個0～1之間的隨機數(shù)，與相應的閾值T(n)作比較，若產(chǎn)生的隨機數(shù)小于T(n)則此節(jié)點當選為首輪簇頭節(jié)點(FCH)，未當選的節(jié)點處于空閑狀態(tài)。T(n)的計算方法如公式（1）所示。

其中，p為期望的簇頭節(jié)點在所有傳感器節(jié)點中的百分比，r表示當前輪數(shù)，n代表某個節(jié)點，G為第r輪之前尚未成為簇頭的節(jié)點集合。

節(jié)點一旦成為首輪簇頭節(jié)點，則向全網(wǎng)用CSMA(Carrier-Sense Multiple Access)的MAC協(xié)議廣播其當選消息，該廣播消息中包含了自己的ID。非簇頭節(jié)點根據(jù)收到消息的信號強弱，選擇信號最強的消息發(fā)送源節(jié)點作為自己的簇頭，并向該簇頭節(jié)點發(fā)送消息，請求成為該簇成員，消息中包含了自身ID和首輪簇頭ID。首輪簇頭節(jié)點收到成員節(jié)點的加入請求后，將各成員節(jié)點的信息保存在自己的路由表中。當簇頭收到所有加入請求消息后，向各成員節(jié)點發(fā)送確認加入消息，消息中包含了本簇使用的CDMA編碼、TDMA時隙表以及要求進入休眠狀態(tài)的消息。不同的簇內(nèi)部通信采用不同的CDMA編碼，避免了相互之間的通信干擾。TDMA時隙表告知了成員節(jié)點何時可以傳送數(shù)據(jù)到簇頭。收到休眠狀態(tài)消息后，成員節(jié)點即由工作狀態(tài)轉(zhuǎn)換到休眠狀態(tài)，節(jié)省了能量，也利于簇間多跳路徑的建立。

至此，首輪成簇階段結束，網(wǎng)絡運行進入下一階段。

3.1.2 非首輪簇形成階段

如果網(wǎng)絡不是首輪成簇，那么本輪的簇頭節(jié)點由上一輪的簇頭指定。以第二輪簇形成過程為例來說明。

在首輪數(shù)據(jù)傳輸?shù)淖詈笠粠?，各簇的成員節(jié)點會將自身剩余能量（Eresidual）信息連同采集到的數(shù)據(jù)一起發(fā)送給相應簇頭，由簇頭計算出本簇當前平均剩余能量(Eave)。簇頭將計算結果發(fā)送給簇內(nèi)各成員節(jié)點，各節(jié)點比較簇內(nèi)平均剩余能量和自身當前能量的大小，滿足Eresidual >Eave的成員節(jié)點均可參與競爭第二輪本簇的簇頭節(jié)點，并向當前簇頭發(fā)送競選消息。若競選節(jié)點不唯一，那么簇頭節(jié)點指定距離自己最近的競選節(jié)點成為第二輪的簇頭（NCH），這里的距離可以根據(jù)收到競選消息的信號強弱來判斷。

第二輪簇頭選定之后，當前簇頭將成員節(jié)點包括自身的信息轉(zhuǎn)交給第二輪簇頭，并向本簇成員廣播簇頭轉(zhuǎn)變的消息，隨后，當前簇頭狀態(tài)轉(zhuǎn)換為簇成員節(jié)點，第二輪簇頭的狀態(tài)轉(zhuǎn)為簇頭節(jié)點。新當選的簇頭將選定的CDMA碼、TDMA時隙表和進入休眠要求，以消息的形式廣播給本簇成員。依此類推，以后各輪的簇形成過程均與第二輪相同。

3.2 簇間多跳路徑建立和選擇階段

簇形成之后，sink將自己的跳數(shù)置為0，其余簇頭節(jié)點將自身跳數(shù)置為最大值。然后，sink以發(fā)射半徑d0向全網(wǎng)廣播多跳路徑建立消息，消息中包含了sink的跳數(shù)信息。收到消息的簇頭節(jié)點，將sink節(jié)點加入自己的中繼節(jié)點集中，同時將自身的跳數(shù)置為1，并向外轉(zhuǎn)發(fā)來自sink的廣播消息。利用傳感器節(jié)點可以調(diào)節(jié)自身無線發(fā)射功率的特點，調(diào)整簇頭的發(fā)射能量，使簇頭節(jié)點之間的通信距離大于簇內(nèi)通信的范圍[9]。其他未收到過來自sink的廣播消息的簇頭，在收到相鄰簇頭轉(zhuǎn)發(fā)來的消息后，將發(fā)送該消息的簇頭加入到自己的中繼節(jié)點集中，同時將收到的跳數(shù)值加1，更新為自身跳數(shù)信息，然后再進一步轉(zhuǎn)發(fā)sink的廣播消息。若某個簇頭收到多個具有相同跳數(shù)值的簇頭轉(zhuǎn)發(fā)來的消息，則將它們都加入到中繼節(jié)點集中。若簇頭收到跳數(shù)值大于自身跳數(shù)值的消息，則丟棄該消息。依此類推，廣播結束后，每個簇頭節(jié)點都保存了通往sink的中繼節(jié)點集，簇間多跳路徑建立完畢。

簇頭到sink的數(shù)據(jù)傳輸已經(jīng)建立了多條通信路徑，接下來在此基礎上為每個簇頭選擇一條通往sink的最優(yōu)路徑。各簇頭節(jié)點在其中繼節(jié)點集中，選擇距離自己最近的簇頭作為其下一跳轉(zhuǎn)發(fā)節(jié)點。這里的距離可以根據(jù)收到廣播消息的信號強度來衡量。若最優(yōu)轉(zhuǎn)發(fā)節(jié)點失效，則可選擇中繼節(jié)點集中的其他簇頭節(jié)點。

3.3 數(shù)據(jù)傳輸階段

簇頭為簇內(nèi)成員節(jié)點分配好TDMA時隙，簇間多跳路徑建立并選擇好之后，各簇頭向成員節(jié)點發(fā)送喚醒消息，使它們轉(zhuǎn)換到工作狀態(tài)，開始采集監(jiān)測區(qū)域的數(shù)據(jù)，并在TDMA時隙表為其分配的時間槽內(nèi)直接向簇頭發(fā)送數(shù)據(jù)。簇頭節(jié)點收集到所有成員發(fā)來的數(shù)據(jù)后，與自身采集的數(shù)據(jù)進行融合處理，再沿著已建立好的多跳路徑傳送給sink。

各成員節(jié)點在向簇頭發(fā)送采集數(shù)據(jù)時，將自身的剩余能量“捎帶”發(fā)送給簇頭，以便簇頭節(jié)點計算出下一輪簇頭選舉所需的本簇平均剩余能量。

為了節(jié)省資源開銷，數(shù)據(jù)傳輸階段的持續(xù)時間要比前兩個階段長得多。

4 性能分析

(1)LEACH協(xié)議單純地依靠隨機方式產(chǎn)生簇頭，缺乏對簇頭節(jié)點能量水平的考慮。雖然一個節(jié)點在1/p輪內(nèi)僅有一次當選簇頭的機會，但如果某些剩余能量已經(jīng)很少的節(jié)點被選為簇頭，它們必然會因大量消耗能量而過早失效，那么其所屬簇內(nèi)節(jié)點采集的數(shù)據(jù)就不能進一步傳送到sink節(jié)點，此時網(wǎng)絡的生存周期結束，網(wǎng)絡中遺留大量未被充分利用的能量資源。這種部分節(jié)點因為過早耗盡自身能量導致網(wǎng)絡原有覆蓋區(qū)域缺失或者數(shù)據(jù)無法送達sink節(jié)點的現(xiàn)象叫作“能量空洞”[10]現(xiàn)象。

由于初始狀態(tài)下網(wǎng)絡中所有節(jié)點的能量均充足且相等，LEACH-improved協(xié)議在首輪采用了LEACH的隨機簇頭選舉方式，簡捷、快速的將網(wǎng)絡分簇。之后每輪的簇頭節(jié)點都由本簇內(nèi)剩余能量大于簇內(nèi)平均剩余能量的節(jié)點競爭產(chǎn)生，有效避免了能量較低的節(jié)點當選簇頭，使網(wǎng)絡負載更加均衡，防止了“能量空洞”現(xiàn)象的發(fā)生，繼而延長了網(wǎng)絡壽命。

（2）LEACH協(xié)議每輪都要重新建簇，且每輪簇重構時，網(wǎng)絡的拓撲結構都會發(fā)生較大變化，同時全網(wǎng)所有節(jié)點都要參與此過程，由此帶來的控制和通信開銷是很可觀的。

LEACH-improved協(xié)議每輪在不改變簇結構的基礎上，重新選擇簇頭節(jié)點和成簇。各簇的成員只需參加本簇的簇頭選舉和成簇，不參與網(wǎng)絡中其他簇的重建過程。因此避免了頻繁簇重構帶來的能量開銷。

（3）LEACH協(xié)議要求所有簇頭節(jié)點均與sink直接通信，sink附近的簇頭向sink傳送數(shù)據(jù)基本可以采用自由空間信道模型，距離sink較遠的簇頭很可能因采用多徑衰落信道模型傳輸數(shù)據(jù)消耗大量能量，造成簇頭節(jié)點間能耗的不均衡。

LEACH-improved協(xié)議通過在簇頭間建立多跳傳輸路徑，使得所有簇頭之間的數(shù)據(jù)傳輸都可采用自由空間信道模型，從而大大節(jié)省了距sink較遠的簇頭節(jié)點的通信能耗，同時簇間負載也得到了均衡。

同時，LEACH-improved協(xié)議僅通過發(fā)送查詢廣播數(shù)據(jù)包進行尋路過程，并不進行采集數(shù)據(jù)的傳輸，并且通過調(diào)節(jié)簇頭發(fā)射功率限制了消息的轉(zhuǎn)發(fā)半徑，因而也不存在泛洪算法固有的“內(nèi)爆”和“重疊”問題。

（4）LEACH-improved的多跳傳輸路徑使得簇頭在向sink轉(zhuǎn)發(fā)數(shù)據(jù)時，每一跳都可以充分地進行數(shù)據(jù)融合，從而減少了網(wǎng)絡中的數(shù)據(jù)傳輸量，降低了節(jié)點的通信能耗。

5 仿真實驗和分析

本文在TinyOS操作系統(tǒng)的TOSSIM仿真平臺下對LEACH-improved協(xié)議進行仿真實驗，演示新協(xié)議的工作過程。通過對比LEACH協(xié)議來驗證它的有效性。

在100m×100m的正方形區(qū)域內(nèi)隨機部署100個節(jié)點，每個節(jié)點的初始能量為2J，其余參數(shù)設置為：Eelec=50nJ/b，EDA=5 nJ/b，d0=87，fs=10pj/bit/m2，mp=0.0013pJ/bit/m，數(shù)據(jù)包的大小是2000b，報頭和廣播包的大小是20b。

本文通過第一個節(jié)點的死亡時間（FND）和最后一個節(jié)點的死亡時間（LND），來衡量兩種協(xié)議下網(wǎng)絡的生命周期。仿真實驗分別采用LEACH協(xié)議和LEACH-improved協(xié)議進行傳感器網(wǎng)絡的運行，得到了兩種協(xié)議下網(wǎng)絡運行輪數(shù)隨死亡節(jié)點個數(shù)的變化關系，如圖1所示。

由圖1可見，LEACH-improved協(xié)議下FND比LEACH協(xié)議的延遲了近32% ，LND比LEACH協(xié)議的延遲了近24%。這是因為LEACH-improved協(xié)議在簇頭選擇時考慮了節(jié)點的能量狀況，在簇頭節(jié)點間通過構造中繼節(jié)點集并選擇最佳路徑進行數(shù)據(jù)發(fā)送，使網(wǎng)絡中節(jié)點能量能耗更加均衡，網(wǎng)絡壽命得到了延長。

圖1 LEACH-improved與LEACH的網(wǎng)絡生命周期比較圖

5 結論

本文通過對LEACH協(xié)議的分析，針對其在簇頭選擇、成簇及數(shù)據(jù)傳輸方面存在的不足，提出了一種基于能量且負載均衡的路由協(xié)議LEACH-improved，用節(jié)點剩余能量來約束簇頭的選舉，在簇頭和sink間建立并選擇多跳傳輸路徑，保證距離較遠的簇頭采用多跳方式發(fā)送數(shù)據(jù)到sink。仿真結果表明，與LEACH協(xié)議相比，LEACH-improved協(xié)議平衡了簇間負載，節(jié)約了網(wǎng)絡能量，網(wǎng)絡壽命得到了延長。但LEACH-improved協(xié)議仍存在不足之處，比如，沒有考慮到簇頭在網(wǎng)絡中是否均勻分布，各簇的大小是否合理等。這兩點對于網(wǎng)絡生命周期的延長都有很大影響，今后還需做進一步的研究和完善。

[1]楊文國，郭田德，趙彤.基于動態(tài)規(guī)劃的無線傳感器網(wǎng)絡的路由算法[J].計算機研究與發(fā)展，2007,44(5):890-897.

[2]李建中，高宏.無線傳感器網(wǎng)絡的研究進展[J].計算機研究與發(fā)展，2008,45(1):1-15.

[3]陳力軍，毛鶯池，陳道蓄，等.平均度約束的無線傳感器網(wǎng)絡拓撲控制[J].計算機學報，2007,30(9):1544-1549.

[4]OK CS, LEE S, MITRA P, et al.Distributed energy balanced routing for wireless sensor networks[J].Computers & Industrial Engineering, 2009, 57(1):125-135.

[5]HEINJZELMAN W，CHANDRAKSAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transcations on Wireless Communications, 2002,1(4):660-670.

[6]劉昕，王全玉，金旭亮.基于能量感知的數(shù)據(jù)匯聚和路由協(xié)議[J].計算機研究與發(fā)展，2008，45(1):83-89.

[7]GAUTAM N, LEE WI, PYUN JY.Dynamic clustring and distance aware routing protocol for wireless sensor networks[C]//Proceedings of the 6th ACM symposium on Performance evaluation of wireless ad hoc, sensor,and ubiquitous networks.Tenerife,Canary Islands,Spain:ACM Press, 2009:9-14.

[8]徐建波，李仁發(fā).無線傳感器網(wǎng)絡中一種新型的混合型數(shù)據(jù)收集協(xié)議[J].計算機研究與發(fā)展，2008，45(2):254-260.

[9]樂世成，王培康.無線傳感器網(wǎng)絡中的節(jié)能路由算法[J].計算機工程，2008，34(7)：113-117.

[10]吳小兵，陳貴海.無線傳感器網(wǎng)絡中節(jié)點非均勻分布的能量空洞問題[J].計算機學報，2008,31(2):253-261.