孫 揚，何建忠

(上海理工大學光電信息與計算機工程學院，上海200093)

0 引言

相比于傳統(tǒng)網(wǎng)絡，無線傳感器網(wǎng)絡 (wireless sensor network，WSN)具有節(jié)點能量受限、動態(tài)性、自組織性、以數(shù)據(jù)為中心等特點，這也就決定了在設計WSN路由協(xié)議時必須將重點放在如何更有效地利用有限的節(jié)點能源上面，同時應充分考慮網(wǎng)絡拓撲的動態(tài)變化，以數(shù)據(jù)為中心，保證網(wǎng)絡的健壯性和實時性。另外，在實際應用背景中，網(wǎng)絡中的傳感器節(jié)點往往是非對等的，也就是節(jié)點在初始能量、計算能力以及通信能力上往往存在著差異，而這往往會對WSN路由協(xié)議的設計產(chǎn)生重要影響。傳統(tǒng)的WSN路由協(xié)議從不同的角度力求均衡網(wǎng)絡中各節(jié)點功耗，同時最大化網(wǎng)絡壽命。但是，在不同應用背景下，這些路由協(xié)議也都存在著各自的缺陷。針對這些問題，本文提出了一種自適應負載均衡集簇分層路由協(xié)議——ALBCH(adaptive load balancing clustering hierarchy)，從多個層面對傳統(tǒng)路由協(xié)議進行了綜合性的改進，并通過引入剩余能量因子等方法使本協(xié)議可以適用于實際應用中非對等節(jié)點構(gòu)成的網(wǎng)絡，實現(xiàn)網(wǎng)絡整體負載均衡和網(wǎng)絡生存周期的延長。

1 LEACH和PEGASIS協(xié)議分析

1.1 LEACH協(xié)議

文獻［1］提出了一種低功耗自適應集簇分層路由協(xié)議——LEACH(low energy adaptive clustering hierarchy)，它的核心思想是:將整個網(wǎng)絡中的節(jié)點劃分為若干個簇，每個簇內(nèi)隨機選舉出一個簇頭節(jié)點，簇內(nèi)節(jié)點都通過簇頭結(jié)點與基站進行通信，以減少直接與基站進行通信的節(jié)點的數(shù)量。該協(xié)議按輪進行通信，每輪分為建立階段和穩(wěn)定階段，在建立階段以自組織的方式進行簇頭的隨機選舉，選舉出的簇頭節(jié)點進行廣播，未被選為簇頭的普通節(jié)點根據(jù)收到的信號強弱選擇加入的簇;穩(wěn)定階段，節(jié)點采集到的數(shù)據(jù)首先發(fā)送到簇頭節(jié)點，簇頭節(jié)點進行數(shù)據(jù)融合后將收集到的信息發(fā)送到基站。由于每輪簇頭是隨機產(chǎn)生的，這樣可以較好得平衡節(jié)點耗能，達到負載平衡的目的。

在LEACH的基礎(chǔ)上，包括該協(xié)議作者在內(nèi)的一些研究者進行了一系列基于集簇分層思想的改進，比如LEACHC［3］提出了中心化的成簇算法以解決簇頭節(jié)點分布不均的問題;還有學者提出簇頭節(jié)點間通過MTE(minimum transmission energy)［4］方式向基站發(fā)送數(shù)據(jù)以節(jié)省能量的策略，如圖1所示。

圖1 LEACH和PEGASIS協(xié)議

1.2 PEGASIS協(xié)議

PEGASIS(power efficient gathering in sensor information systems)是一種基于貪婪算法的路由策略。它本質(zhì)上是LEACH的增強算法，其核心思想與LEACH是一致的，那就是盡量減少直接與基站進行通信的節(jié)點的數(shù)量［5］。它首先使用貪婪算法構(gòu)成一條邊長之和接近最小的鏈。該策略在每輪會選舉一個鏈內(nèi)簇頭節(jié)點，當通信開始的時候，數(shù)據(jù)會從最遠端節(jié)點開始沿鏈向簇首節(jié)點發(fā)送，每經(jīng)過一個節(jié)點都會進行一次數(shù)據(jù)融合，直到到達簇首節(jié)點后由簇首節(jié)點將融合后的數(shù)據(jù)發(fā)送到基站。

1.3 兩種協(xié)議的分析與比較

由于兩種協(xié)議基本策略的差異，在實際應用場景中他們具有各自的特點，總結(jié)見表1。

表1 LEACH和PEGASIS優(yōu)缺點對比

通過對比分析我們發(fā)現(xiàn)，LEACH和PEGASIS在很多方面，比如整體耗能均衡、實時性、容錯性等特性上具有一定的可互補性，這就為我們在這兩個協(xié)議的基礎(chǔ)上進行改進提供了必要的可行性。另外，由LEACH和PEGASIS協(xié)議的原始文獻，作者在分析討論前都假設網(wǎng)絡內(nèi)所有節(jié)點是同構(gòu)節(jié)點，也就是初始能量、計算能力、通信能力是一致的，而這是與實際應用中具體的節(jié)點情況不符的;同時PEGASIS中的貪婪算法機制本身也有一定的缺陷。因此，本文提出一種自適應負載均衡集簇分層路由協(xié)議——ALBCH(adaptive load balancing clustering hierarchy)，以解決上述問題。

2 改進算法描述

2.1 網(wǎng)絡模型

本文討論的WSN基于以下假設:

(1)所有N個傳感器節(jié)點位于一個正方形區(qū)域S內(nèi)。(2)所有節(jié)點部署后不再發(fā)生移動且不需人工維護。

(3)基站位于離S較遠的固定位置，且其能量不受限。(4)網(wǎng)絡內(nèi)各節(jié)點初始能量、處理能力不對等。

(5)在每輪通信中各節(jié)點耗能不統(tǒng)一。

其中前3項是一般討論WSN路由協(xié)議時使用的典型配置，后兩項旨在討論本協(xié)議對異構(gòu)網(wǎng)絡節(jié)點的處理能力。

2.2 簇頭選舉

當網(wǎng)絡部署完畢或每次新節(jié)點被播撒加入網(wǎng)絡后，每隔一定時間都要進行簇頭的選舉。在文獻［1］中，采用以下方法確定當前節(jié)點是否當選為簇頭:節(jié)點n每輪產(chǎn)生一個0到1之間的隨機數(shù)，然后該隨機數(shù)與閾值T(n)進行比較，若該隨機數(shù)小于T(n)，則該節(jié)點n當選為本輪通信的一個簇頭。閾值T(n)由以下公式產(chǎn)生

式中:P——簇頭節(jié)點在總節(jié)點中所占的比例 (LEACH中經(jīng)計算選取0.05為最佳)，r——當前輪數(shù)，n——當前還未被選為過簇頭的節(jié)點的集合。

顯然，這種選舉辦法是不適用于非對等節(jié)點構(gòu)成的網(wǎng)絡的。我們這里說的非對等包括了以下3種情形:

(1)節(jié)點本身在初始能量、計算能力、通信能力上有一定的差距;

(2)網(wǎng)絡在運行一段時間后由于其所處環(huán)境的復雜性造成節(jié)點的耗能不均而產(chǎn)生的不對等;

(3)由于節(jié)點不可避免的死亡需要定期向網(wǎng)絡中添加部署新節(jié)點才能保證系統(tǒng)的健壯性，這樣也會產(chǎn)生剩余能量上的非對等現(xiàn)象。

為適應這些情況，對閾值計算公式進行改進

其中En為節(jié)點n剩余能量，ET為設定的剩余能量閾值，具體取值由實際節(jié)點參數(shù)決定。Pe為剩余能量相關(guān)因子，它由當前節(jié)點剩余能量和網(wǎng)絡節(jié)點平均剩余能量的比值決定

因為讓每個節(jié)點都知道網(wǎng)絡的實時剩余能量是很難實現(xiàn)的，此處我們使用的節(jié)點平均剩余能量采用的是由通信輪數(shù)所計算的估計值，使用該估計值并不會影響算法的性能。本文我們采用文獻［3］所提出的無線電能耗模型，發(fā)送長度為k比特的信息至距離d處所產(chǎn)生的能耗為

接收此信息耗能為

其中Eelec為發(fā)送或接收電路每處理1比特數(shù)據(jù)所消耗的能量，εfsd2和εmpd4分別為放大電路使用無線電自由空間模型和多徑傳播模型時的耗能，采用哪種模型主要取決于到接收器的距離和可允許的比特差錯率。設已知N個節(jié)點的網(wǎng)絡初始節(jié)點總能量為Einit，網(wǎng)絡生存周期為T，則網(wǎng)絡啟動時間t后節(jié)點的平均剩余能量為

由于Einit已知，只需估算出網(wǎng)絡的生存周期T即可計算出平均剩余能量。由上述無線電能耗模型，每輪通信消耗的能量估計值為

式中:Ec——節(jié)點進行數(shù)據(jù)處理的耗能，dBS——簇頭與基站的平均距離，dCH——節(jié)點到簇頭的平均距離。可以推導得到，在邊長M的正方形區(qū)域中，為便于計算，設基站位于區(qū)域正中間，則

在理想情況下，有

整理代入即得平均剩余能量的估計值。

C為節(jié)點計算能力相關(guān)因子，由具體節(jié)點處理資源決定。因為一般設計的傳感器節(jié)點處理能力與其電池容量有一定的約束關(guān)系，所以通常不必考慮兩者不協(xié)調(diào)的情形。加入計算能力相關(guān)因子主要是出于提高網(wǎng)絡整體實時性的考慮，因為在本協(xié)議體系中作為簇頭節(jié)點相比普通節(jié)點有更多的機會參與數(shù)據(jù)融合處理和數(shù)據(jù)轉(zhuǎn)發(fā)，所以簇頭節(jié)點處理能力的快慢勢必會影響到整個網(wǎng)絡的延遲程度，在一些對實時性要求較高的網(wǎng)絡中加入相關(guān)因子是必須的，而處理資源相對均等的網(wǎng)絡時C的值可以直接置1。

由于剩余能量因子的引入，非對等節(jié)點由于作為簇頭所引起的能耗將得到最大程度的均衡，并使得該協(xié)議可以應用于能量異構(gòu)型網(wǎng)絡，增強網(wǎng)絡的可拓展性和可維護性。通過設定剩余能量閾值ET，剩余能量低于該閾值的節(jié)點將不再被選為簇首節(jié)點，大大延后節(jié)點首次死亡時間，延長網(wǎng)絡生存周期。計算能力相關(guān)因子的引入對于網(wǎng)絡整體實時性的增強提供了一定的幫助。

2.3 簇的建立和簇內(nèi)通信

當簇頭選舉完畢后，當選為簇頭的節(jié)點發(fā)送一個廣播信息，附近的普通節(jié)點根據(jù)收到的廣播信號的強弱來決定以哪個簇頭作為簇首，并向簇頭節(jié)點發(fā)送確認消息，并將自己的簇標志位CLUSTER_FLAG(大小寫?)設為簇頭節(jié)點ID。然后，在每個簇內(nèi)指定任意非簇頭節(jié)點開始，使用改進后的貪婪算法進行成鏈運算，將所有CLUSTER_FLAG值相同的節(jié)點 (含簇頭節(jié)點)構(gòu)成一條長鏈。如圖2所示，當有數(shù)據(jù)要發(fā)送時，當開始收集網(wǎng)絡數(shù)據(jù)的時，首先由本輪簇頭節(jié)點c向d節(jié)點發(fā)送一個ACK信令 (非常小，帶來的能量損耗可忽略)，d節(jié)點收到后依次傳送該信令直至右側(cè)端節(jié)點e;當端節(jié)點接收到ACK指令后，就將傳感器模塊收集到的數(shù)據(jù)發(fā)送到節(jié)點d，節(jié)點d收到e節(jié)點的數(shù)據(jù)后，將該數(shù)據(jù)與自身傳感器模塊收集的數(shù)據(jù)進行數(shù)據(jù)融合后發(fā)送到下一節(jié)點，依此操作直到到達簇頭節(jié)點;同時，對鏈的另一端進行類似的處理。

圖2 ALBCH基本成鏈機制

2.4 簇頭與基站的通信

與LEACH不同的是，本協(xié)議不再采用簡單的多跳路由的方式來進行簇頭與基站間的通信，這主要是因為如果采用多跳路由的方式，靠近基站的簇頭節(jié)點必然會過多地參與數(shù)據(jù)的轉(zhuǎn)發(fā)，相應的其能耗就會過大，造成近基站節(jié)點早死的問題。

當所有簇內(nèi)的節(jié)點數(shù)據(jù)經(jīng)融合收集并到達簇頭節(jié)點后，采用與前述簇內(nèi)通信類似的機制將所有簇頭節(jié)點構(gòu)成一條長鏈，然后這些簇頭節(jié)點經(jīng)過二次選舉再選出一個簇頭來，所有簇頭通過這個更高級的簇頭與基站進行通信。需要注意的是，本協(xié)議的二次選舉區(qū)別于PEGASIS成鏈策略的是:PEGASIS中是采用鏈上節(jié)點輪流作為簇頭節(jié)點的方式，而本協(xié)議繼續(xù)使用式 (2)中與剩余能量和計算能力的關(guān)聯(lián)，進一步均衡網(wǎng)絡負載和減少延遲。

2.5 改良后的貪婪算法

2.5.1 長鏈問題

PEGASIS中的貪婪成鏈算法存在長鏈問題，如圖3所示。由于傳統(tǒng)的貪婪算法總是取局部最優(yōu)解，當由節(jié)點1發(fā)起成鏈過程后，始終是選擇最短路徑作為下一跳，這就導致節(jié)點8即使與鏈路前端節(jié)點距離較近，但仍然會被插入到鏈路的遠端，從而大大增加了通信耗能，這就是所謂的長鏈問題［6］。

圖3 長鏈問題

2.5.2 距離閾值法解決長鏈問題

為解決長鏈問題，在貪婪算法成鏈過程中加入距離閾值機制，設當前跳數(shù)為N的鏈中包含的節(jié)點集為S={s1，s2，s3，…sN}，成鏈過程由 s1發(fā)起，且已對 s1～sk-1完成成鏈，那么在對當前局部最優(yōu)解節(jié)點sk進行如下入鏈處理:設定一個距離閾值L，鏈上節(jié)點集S中各節(jié)點的距離為Dis(si，sj)(i N，j N，i≠ j)，令 L= αMax［Dis(si，sj)］，α取值由具體網(wǎng)絡情況決定。

(1)若Dis(sk，sk－1) L，說明該鏈接非長鏈，則節(jié)點sk即為下一跳節(jié)點，并繼續(xù)成鏈過程;

(2)否則，若 Dis(sk，sk－1)＞ L ，將 Dis(sk，sk－1)與鏈上各節(jié)點到節(jié)點sk的距離逐一對比:

1)若對 i＜k，有

則說明此長鏈不可避免，節(jié)點sk仍作為下一跳節(jié)點，并繼續(xù)成鏈過程;

2)若式 (10)不成立，設對 i＜k，有

此時將 Dis(sk，sj－1)與 Dis(sk，sj+1)進行比較，若 Dis(sk，sj－1)較小，則將節(jié)點sk插入到sj-1和sj之間，從節(jié)點sk-1繼續(xù)成鏈過程;若式 (11)不能滿足，則說明此長鏈不可避免，節(jié)點sk仍作為下一跳節(jié)點，從節(jié)點sk繼續(xù)成鏈過程。

3 仿真結(jié)果及分析

本文使用Matlab軟件平臺對ALBCH協(xié)議進行仿真。搭建虛擬網(wǎng)絡環(huán)境基本參數(shù)如表2所示。

另外，取ACK信令長度為25bit，根據(jù)所搭建的網(wǎng)絡環(huán)境參數(shù)，計算能力因子C取1，多次仿真后確定距離閾值參數(shù)α較理想取值為1.4。

ALBCH協(xié)議相比LEACH和PEGASIS可以進一步均衡網(wǎng)絡負載，同時延長首次節(jié)點死亡出現(xiàn)的時間。由于簇頭分布、成鏈過程等的隨機性較大，我們采取每種協(xié)議循環(huán)仿真50次后取平均值的方法對所得的節(jié)點存活個數(shù)進行統(tǒng)計。首先將節(jié)點初始能量均設為1J，已驗證ALBCH在處理同構(gòu)網(wǎng)絡時的能量性能。圖4為所得仿真結(jié)果。

表2 仿真參數(shù)表

圖4 三種協(xié)議在同構(gòu)網(wǎng)絡環(huán)境下能耗仿真結(jié)果

由仿真結(jié)果我們可以看到，在應用于節(jié)點完全對等的網(wǎng)絡時，LEACH協(xié)議的首次節(jié)點死亡時間和節(jié)點全部死亡時間分別出現(xiàn)在第570輪和第1210輪;PEGASIS協(xié)議的首次節(jié)點死亡時間個節(jié)點全部死亡時間分別出現(xiàn)在第760輪和第1480輪;而ALBCH協(xié)議的首次節(jié)點死亡時間和節(jié)點全部死亡時間則分別出現(xiàn)在第850輪和第1590輪。ALBCH協(xié)議在處理同構(gòu)網(wǎng)絡時較LEACH和PEGASIS分別延長了網(wǎng)絡生存周期達49%和12%。

ALBCH在處理異構(gòu)網(wǎng)絡時對網(wǎng)絡生存周期的改善就更加明顯。我們將100個節(jié)點分別按1:1:1:1的比例分別取初始能量為0.5J、1J、1.5J、2J，重新進行仿真，所得結(jié)果如圖5所示。

由仿真結(jié)果，在所給定的異構(gòu)網(wǎng)絡環(huán)境下，ALBCH相比LEACH和PEGASIS分別將生存周期延長了185%和72%。剩余能量因子的引入使得能量非對等節(jié)點網(wǎng)絡各節(jié)點的負載得以均衡，大大延后了節(jié)點死亡時間。同時對貪婪算法的改進也使得網(wǎng)絡生存周期進一步延長，整個協(xié)議取得較高的能量效率。

ALBCH協(xié)議還大大減輕了PEGASIS在采用貪婪算法鏈狀機制時的時延問題，從而可以應用在一些對實時性要求較高的網(wǎng)絡中。圖6為三種協(xié)議在同構(gòu)網(wǎng)絡中進行通信時數(shù)據(jù)的端到端時延的仿真統(tǒng)計。

圖5 三種協(xié)議在異構(gòu)網(wǎng)絡環(huán)境下能耗仿真結(jié)果

圖6 三種協(xié)議端到端時延仿真結(jié)果

節(jié)點數(shù)為20、50、100時，ALBCH的平均端到端時延分別比LEACH減少了20%、22%、31%，比PEGASIS減少了200%、260%、300%(約略值)。由于采用了更完善的分簇機制，ALBCH使鏈狀機制所帶來的時延大大減少，提高了網(wǎng)絡的實時性。

仿真結(jié)果證明，ALBCH比LEACH和PEGASIS具有更好的均衡負載能力、低能耗特性和實時性能，并且克服了后兩者在異構(gòu)網(wǎng)絡中的局限性，在應用于能量非對等節(jié)點網(wǎng)絡中具有非常大的優(yōu)勢。

4 結(jié)束語

本文在綜合考慮LEACH和PEGASIS優(yōu)缺點的基礎(chǔ)上，結(jié)合實際應用中節(jié)點的不對等性，提出了一種自適應負載均衡集簇分層路由協(xié)議。該協(xié)議分別將改進過的貪婪算法成鏈機制引入分簇網(wǎng)絡的雙層結(jié)構(gòu)，并在簇頭選舉時充分考慮節(jié)點剩余能量，使其在處理異構(gòu)網(wǎng)絡時具有更好的性能。該協(xié)議相比LEACH和PEGASIS在網(wǎng)絡能耗、負載均衡、網(wǎng)路實時性和健壯性等方面都有顯著提高。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless microsensor networks［J］.IEEE Computer society，2007:3005-3014.

［2］Lindsey S，Raghavenda CS.PEGASIS:Power efficient gathering in sensor information systems［C］//Philadelphia:Proceeding of the IEEE Aero space Conference，IEEE Press，2009:1125-1130.

［3］Heinzelman W，Chandrakasan A，Hari Balakrishnan.An application specific protocol architecture for wireless microsensor networks［J］.IEEE Trans on Wireless Communications，2009，1(4):660-670.

［4］LIU Ming，GONG Haigang，MAO Yingchi.A distributed energy efficient data gathering and aggregation protocol for wireless sensor networks［J］.Journal of Software，2005，16(12):1000-9825(in Chinese).［劉明，龔海剛，毛鶯池.高效節(jié)能的傳感器網(wǎng)絡數(shù)據(jù)收集和聚合協(xié)議 ［J］.軟件學報，2005，16(12):1000-9825.］

［5］JUNG Sungmin，HAN Youngju，CHUNG Taimyoung.The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS［C］//Seoul:IEEE The 9th International Conference on Advanced Communication Technology，2007，3(1):260-265.

［6］Cortez R Andres，F(xiàn)ierro Rafae，Wood John.Heterogeneous sensor network for prioritized sensing［C］//New York:IEEE 2011 IEEE/RSJInternational Conference on Intelligent Robots and Systems，2011:2333-2339.

［7］Akshay N Kumar，Harish M P，Dhanorkar S B.An efficient approach for sensor deployments in wireless sensor network［C］//Detroit:IEEE Technologies Internati-onal Conference on Digital Object Identifier，2010:350-355.

［8］Kee-Young Shin，Junkeun Song，JinWon Kim，et al.REAR:Reliable energy aware routing protocol for wireless sensor networks［C］//Seoul:IEEE The 9th International Conference on Advanced Communication Technology，2007，3(1):525-530.

［9］Euisin Lee，Soochang Park，F(xiàn)ucai Yu，et al.Communication model and protocol based on multiple static sinks for supporting mobile users in wireless sensor networks ［J］.IEEE Transactions on Consumer Electronics，2010，56(3):1652-1660.

［10］LI Xin，ZHOU Chan，F(xiàn)EI Minrui.Wired/Wirless heterogeneous network performance comprehensive evaluation［C］//Shanghai:WRI Global Congress on Intelligent Systems，2009:399-403.

［11］Yonis O.HEED:A hybrid，energy-efficient，distributed clustering approach for ad-hoc sensor networks［J］.IEEE Trans on Mobile Computing，2006，3(4):366-379.

［12］Manjeshwar A，Agrawal D P.TEEN:A routing protocol for enhanced efficiency in wireless sensor networks［C］//Memphis:Internatonal Proceeding of 15th Parallel and Distributed Processing Symposium，2006:23-27.