一種能耗均衡的WSN分簇路由協議*

李建洲，王海濤，陶 安

(1．解放軍理工大學通信工程學院，南京210007;2．解放軍理工大學信息管理中心，南京210007;3．中國人民解放軍95174部隊，430040)

無線傳感器網絡WSN(Wireless Sensor Network)是由大量具有一定計算和通信能力的傳感器相互協作而形成的網絡。WSN在軍事國防、工農業、環境監測、醫療衛生、智能家居、搶險救災等領域有巨大的實用價值。WSN部署環境常常較特殊，如野外、戰場、科考、救災環境，常常采用節點隨機撒布的方式進行布置。由于很難對節點充電以及受成本和體積的限制，節能是 WSN需要高度重視的問題[1]。科學合理的分簇路由協議，可以減少通信量、通信沖突和傳播時延，提高信道利用率和能量效率，均衡節點能耗以及延長網絡壽命[2]。本文以理想環境為背景，暫不考慮信道干擾、通信沖突和網絡環境變化等因素。

分簇多跳路由協議利用簇結構，進行局部管理和數據處理，減少了通信量和協議復雜性，相對于平面路由算法有更好的適應性[3];與節點直接傳遞數據到Sink(匯聚節點)相比，多跳路由方式更為節能。CBRP協議[4]的分簇機制采用最小ID分簇算法，計算簡單、實現方便、算法收斂較快，但該機制沒有考慮負載平衡。E_LEACH協議[5]選擇中繼節點時考慮了選擇距離最近的節點;基于不均勻分簇的LEACH協議的改進研究方案[6]還考慮了當中繼簇頭與Sink距離較近時，將數據直接傳輸給Sink，但它們都沒有定量考慮傳輸的方向。LBMC算法[7]采用分層機制調節簇頭概率，均衡和減少了中繼負擔，但分層以及預設層寬度不一定符合網絡實際部署情況。基于時間片的低功耗分簇算法[8]采用定期重新分簇的方法來均衡能耗，但沒有對輪轉周期進行仿真研究;該算法還將閾值函數T(n)(見下文)乘以能量比例因子(Ecur為當前節點能量，Einit為節點初始能量)來均衡能耗，這樣可以減小能耗高的節點再次成為簇頭的概率，但網絡在長期運行后，整體簇頭比例會降低[8]，減少了WSN的覆蓋范圍并增加了簇頭間的中繼距離。

EBCRP(Energy Balanced Clustering Routing Protocol)協議對以上問題進行了研究，提出了改進成簇概率、簇間路由和輪轉周期的方法，同時加入了便于數據融合的等待機制，形成了新的路由協議。

1 相關知識

1．1 能耗模型

簇頭節點接收簇內數據的能耗如式(1)所示。

在不考慮中繼數據的融合時，簇頭接受中繼數據的能耗如式(2)所示。

WSN中，通常根據節點發送數據的距離，節點發送數據能耗分別采用自由空間能耗模型(式(3))和多路衰減模型(式(4))[9]。

以上公式中，l表示數據包長度，Eelec表示無線收發電路處理單位數據所消耗能量，用同一個值表示，n表示簇內節點數，Eda表示單位數據融合能耗，efs與 emp分別表示兩種能耗模型的功率放大系數

1．2 LEACH協議的分簇機制

LEACH協議[10]是典型的分簇路由協議，簇內節點采集數據后發送到簇頭，簇頭將其直接轉發到Sink。協議思想是輪轉地以隨機方式選擇簇頭節點，將能量負載近似均勻地分配到每個傳感器節點，從而降低網絡能耗和延長網絡生存時間。LEACH協議中，節點成為簇頭的概率與節點數、簇頭比例和輪數有關，具有一定的隨機性。基于網絡能耗最小的原則考慮，通過數學推導和仿真實驗，一般取簇頭比例為5%[10]。傳感器節點n隨機生成一個(0，1)之間的隨機數，并且與閾值函數T(n):

作比較，其中P為簇頭比例，r為已完成的輪數，Gr為在最近的1/P輪中未當選簇頭的節點集合。如果隨機數小于該閾值，則該節點當選為簇頭。T(n)的設計可以保證每個節點都可以在連續的1/P輪中有一次成為簇頭，從而均衡了能耗。簇頭廣播自身消息，接收到該消息的普通節點與距它最近的簇頭形成簇。該成簇機制具有計算簡單、交互信息少、能耗較均衡的優點。

1．3 簇間路由

WSN中，為了避免相互干擾，簇內的通信頻率與簇間的通信頻率往往不同[10]。數據直接在相鄰簇頭之間中繼轉發而不通過簇間網關的方式存在發送距離較遠，能耗較高的缺點，但簇內節點不需要充當網關，協議較簡單。

在無線環境中，選擇下一跳進行中繼實際上是協調安排合適的鄰居節點進行數據接收、處理和轉發。根據能耗模型，下一跳節點的距離越近越好。但當中繼節點距離過近時，中繼的總能耗可能會大于兩節點直接通信的能耗。不過在現實環境中，WSN中的節點常常采取隨機撒布的方式，兩簇頭距離很近的可能性很小[11]。

1．4 數據融合比例

針對節點能量有限、通信能耗、節點有冗余、數據有相關性、數據包頭開銷大等特點，數據傳輸時宜采用數據聚合、過濾等融合技術[12－13]。簇內的節點距離較近，采集到的數據具有很高的相似性，因此簇頭進行簇內數據融合時融合比例會高些;而對于簇間中繼的數據，因為它們來自相隔較遠的位置，相互差異較大，如果進行融合，融合的比例要小很多，有時甚至只是將幾個數據包合并成一個長的數據包，用一個包頭(和包尾)來減少數據包的長度。但這時如果轉發失敗，重傳的代價較大。

1．5 輪轉周期

LEACH及其改進協議中，網絡運行一定時間后重新進行分簇，該輪轉周期是約定的。實際上，當輪轉周期較短時，WSN的輪轉速度變快，重新分簇的能耗比重增加;而當輪轉周期較長時，WSN很可能在較長時間處于能耗很不均衡的簇結構，造成部分節點過早死亡。輪轉周期對節點能耗和網絡生命有很大影響。

2 EBCRP協議

針對WSN的特點，路由協議應該遵循:區域自治、冗余數據融合、路由時盡量根據局部信息進行選擇、計算復雜度低以及簡單實用等原則。

EBCRP協議的設計兼顧了以上原則。它采用與LEACH協議相同的分簇方法，但是閾值函數T(n)乘以經驗因子使簇頭概率隨節點到基站的距離變化;簇形成后，簇內節點采集數據，直接發送至簇頭;簇頭等待一定時間(與它到基站的距離成反比)后選擇cosa/(r/R)值(參見第2．3節)最大的鄰近簇頭進行轉發，直至數據到達Sink。以下分別予以闡述:

2．1 隨距離變化的簇頭概率

因為承擔中繼任務，越靠近Sink的簇頭的能耗越大。如果越靠近Sink的區域簇頭越多，就可以均衡和減少中繼能耗。因此，簇頭概率應與節點到Sink的距離成反比例關系。但簇頭比例過高會導致平均簇規模減小，削弱了分簇的優勢，特別是降低了簇內數據的融合效率。因此，經驗因子的選取應當適中。

直接推導出較優的簇頭概率與距離的連續變化關系較難，而且也不一定符合實際。EBCRP協議采用經驗公式的方法。EBCRP協議的成簇方法與LEACH協議相同，但對LEACH協議中的閾值函數T(n)乘以經驗因子，通過改變閾值，使簇頭概率隨距離連續變化。

假設整個網絡區域的半徑為R，d是節點與Sink的距離，采用 exp[(R－d)/R]、1－(R－d)/R、a(R－d)/R(a＞1)等各種距離d的反比例函數因子進行不同隨機數種子下的多次仿真實驗，仿真結果表明，當經驗因子為 1．5(R－d)/R，即:

時，在本文的仿真環境中網絡運行情況最佳(參見第3節)。通過式(6)可以看出，距離Sink越遠的節點，簇頭概率變化越小，甚至沒有變化;而距離越近的節點，簇頭概率越高，最高時概率增加了1．5倍。

2．2 便于數據融合的等待策略

根據上文分析，中繼數據的融合有利有弊。中繼數據的融合比例與實際網絡拓撲有關，不宜采用統一的融合比例進行仿真實驗。EBCRP協議中考慮到了中繼信息的融合，設計了等待機制，但中繼數據的融合比例仍設為100%，為協議留下了發展空間;而簇內數據進行融合，融合比例設為70%。

簇頭節點進行數據發送的時刻t設置為與它和Sink的距離成反比，發送時隙到來后將簇內節點采集的數據和其他簇頭轉發來的數據一起發送。距Sink較遠的簇頭等待時間較短，距Sink較近的簇頭等待時間較長，以便中繼簇頭對更多的簇間數據進行融合。代價是靠近Sink的節點采集的數據不能及時傳送到Sink(可以通過為重要信息設置更高的優先級及時進行中繼來解決該問題)以及需要更大的存儲空間來保存中繼信息。本文的仿真環境中，EBCRP協議使用的等待時間T為:

其中d為節點到Sink的距離，時間單位為s。10和100起調節作用，可以取其他值。針對不同的網絡環境以及時延要求，可以設置不同的等待時間。

根據應用環境對時延的要求，等待策略可選擇性地采納。

2．3 綜合考慮距離、角度的路由

在簇內，EBCRP協議采用與LEACH協議相同的節點單跳傳輸數據至簇頭的路由方式。

在簇間，EBCRP協議采用數據包直接在相鄰簇頭間中繼轉發的方式。簇間中繼時，下一跳簇頭的選擇，除了與間距有關，實際上還與方向有關[14]。以圖1為例，簇頭B、C是距簇頭A最近的下一跳簇頭，且A、B的距離與A、C的距離相等，但A到C的方向更接近于A到Sink的方向，方向用A到Sink的連線與A到C的連線的夾角a表示。在WSN中，該角度可以通過定位技術計算出來。顯然選擇C比選擇B理想。選擇角度小的節點作為下一跳，從整個網絡來看，有助于減少中繼跳數和通信沖突。綜上，簇間路由應該選擇距離近且角度小的節點。因此，可以以

的值作為選擇中繼簇頭的度量標準，其中a為上述的夾角，R是整個區域的半徑，d為節點到Sink的距離。夾角a越小，cosa越大，整個值越大;d/R作為分母是為了讓距離的影響與角度的影響的權值相同。選取比值最大的簇頭節點作為下一跳。

為了減少距Sink較近的簇頭節點的中繼負擔，EBCRP協議還將一跳可達Sink的節點都設為單獨簇頭。單獨簇頭沒有簇內節點，只承擔(采集任務和)中繼任務;靠近Sink的較多單獨簇頭均攤了該區域較重的中繼負擔。如圖1中，距離Sink很近的兩個節點都設置成為了單獨簇頭，它們將數據包直接發送給Sink。

圖1 簇間路由與角度

2．4 仿真實驗確定較優的輪轉周期

EBCRP協議中，簇內節點采集并發送一次數據，簇頭就轉發一次數據。現給出新的一輪和輪轉周期的概念:

一輪:網絡中的節點每間隔一段時間采集并發送一次數據，簇頭節點接收到數據后，轉發到合適的中繼簇頭，直到數據到達Sink的這一過程。

輪轉周期:WSN在兩次分簇間運行的輪數。

為了利用輪轉方法來均衡節點能耗，EBCRP協議通過仿真實驗研究了在其他參數不變的情況下，不同輪轉周期對網絡的硬性，從而確定了較優的輪轉周期。不同的網絡環境中，理想的輪轉周期也不同。

3 仿真比較與分析

3．1 仿真環境

本文使用的仿真工具是OMNet++4．0，仿真參數配置如表1所示。根據服務質量與節點數的關系[15]，并考慮邊緣效應來設置一定區域內布置的節點數。節點在區域中隨機均勻分布，以便區域的每一部分都有工作節點。

表1 仿真參數

3．2 比較指標

生命期:從WSN開始運行到有一半節點能量耗盡的時間。這種定義方法比較普遍，判斷簡單而且便于協議間進行比較。

仿真實驗中每60 s采集、發送并轉發一次數據到Sink，每輪的時間為60 s。網絡的輪轉次數等于網絡的生命期與60 s的比值。需要說明的是，EBCRP協議執行過程中，節點隨時可能死亡。因此，仿真過程中只要有節點死亡，就會對存活節點數進行判斷。

WSN中，能量消耗快的節點會先死亡，進而對網絡拓撲造成影響。節點間能耗越均衡，越有利于延長網絡的生命期和采集與發送更多的數據包。、現給出拐點的定義:

拐點:WSN中存活節點數隨時間變化的仿真曲線上，節點死亡速度突然加快的時間點。

有些協議執行過程中，節點能耗的時間差別大，沒有明顯的拐點。有拐點存在，說明協議具有更好的能耗均衡性能。對于有拐點存在的協議，拐點出現越晚，反映了協議具有更好的均衡能耗能力。

拐點是一個參考指標，不需要嚴格確定其位置。一般可以通過觀察仿真曲線確定:拐點前仿真曲線下降較平緩、而拐點后仿真曲線下降很快。

下面給出拐點的數學定義。WSN中，時刻t處存活節點數隨時間變化的一階導數的右極限f't→T+(t)反映了存活節點數在t時刻變化的快慢。假設認為平均K s死亡一個節點為比較快的節點死亡速率，拐點為滿足下列公式的時刻T:

綜上，協議間采用的比較標準包括第一個節點死亡時間、網絡生命期及經歷輪次、存活節點數隨時間變化的曲線的平緩程度、有無拐點以及拐點出現時間等。

3．3 仿真比較和分析

圖2 不同簇間路由策略時存活節點數隨時間變化情況

圖2顯示了簇間轉發數據時只考慮距離與綜合考慮角度和距離的分簇路由協議的仿真結果對比，具體數據比較如表2中第1、2行所示。仿真表明，生命期和輪次都增加了約150%;前者網絡中存活節點數變化較快，后者變化較緩;前者沒有明顯拐點，后者拐點出現在第31 258 s左右，即第520次發送數據前能耗都比較均衡。簇間路由時綜合考慮角度和距離后，減少了數據包的平均傳輸跳數，能耗更少。

表2 仿真實驗數值

在綜合考慮角度與距離的路由協議基礎上閾值函數乘上經驗因子可以增加了靠近基站的簇頭比例，均衡和減少了節點的能耗。但如2．1節討論，經驗因子的選取應當適中。圖3顯示了經驗因子取不同值(圖中只顯示了部分)時WSN的仿真情況，其中R為整個網絡區域的半徑，本實驗仿真環境中取550，d是節點與Sink的距離。

圖3 不同經驗因子時存活節點數隨時間變化情況

通過多次仿真實驗發現，在本文的仿真環境中經驗因子是較優的經驗因子。

圖4中，仿真曲線EBCRP顯示的是在綜合考慮角度與距離的路由協議基礎上加入較優的經驗因子1．5(R－d)/R后的仿真情況，具體數據比較如表2中第2、3列所示。加入經驗因子后，生命期和輪次都增加了約10%;拐點出現時間推遲到第42 478 s左右，即第707次發送數據后死亡才變快。可見，經驗因子的作用明顯。

圖4 加入較優經驗因子時存活節點數隨時間變化情況

通過對簇頭密度、簇間路由的優化，WSN在傳輸數據時具有較好的數據傳輸性能。在WSN運行一段時間后，需重新分簇。改變輪轉周期N的大小，如 10、11、12、…、24、25、…等。仿真發現，當 N=20時網絡拐點出現時間最晚而且生命期最長。圖5顯示了輪轉周期N分別為15、20、25時網絡中存活節點數變化情況。因此，在本文的仿真環境中，理想的輪轉周期為20輪。

圖5 不同輪轉周期時存活節點數隨時間變化情況

綜上，圖6和表2中第1、3行表示了原E_LEACH協議與改進后的協議EBCRP的仿真比較。EBCRP協議比E_LEACH協議能耗均衡很多，第一個節點死亡時間由第295 s變為第5 457 s，生命期和輪次都增加了約180%，有拐點存在且出現很晚(第42 478 s左右)，在拐點前存活節點數變化較小，網絡的能耗更加均衡。總之，EBCRP協議的能耗均衡，網絡生命期增長明顯。

圖6 路由協議改進前后存活節點數隨時間變化情況

4 總結

本文提出了一種能耗均衡的分簇路由協議EBCRP。該協議在簇頭概率、中繼簇頭選擇、數據融合和輪轉周期方面做了改進或設計，計算比較簡單。仿真結果表明，EBCRP協議的能耗性能良好，具有一定的理論和應用價值。能耗均衡的分簇路由協議是保證WSN服務質量的前提之一。簇間中繼數據的融合比例與數據的相似度有關，而相似度又與數據來自的節點的拓撲分布相關，可據此對該協議進行仿真研究，但計算復雜度不宜過高。

[1]王海濤．無線傳感網絡中的分簇協議綜述[J]．傳感器世界，2011，4:6－10．

[2]鄭國強，李健東，周志立．無線傳感器網絡MAC協議研究進展[J]．自動化學報，2008，34(3):305－316．

[3]Yi S，Heo J，Cho Y，et al．PEACH:Power-Efficient and Adaptive Clustering Hierarchy Protocol for Wireless Sensor Networks[J]．Computer Communications，2007，(30):2842－2852．

[4]金鑫，郭虹，劉洛琨．移動Ad hoc網絡中CBRP路由協議仿真分析[J]．通信技術，2007，12(40):145－147．

[5]顧明霞．無線傳感器網絡的LEACH算法改進與仿真研究[J]．計算機仿真，2010，27(9):139－141．

[6]王愛美，王喆．基于不均勻分簇的LEACH協議的改進研究方案[J]．數據通信，2012，3:41－44．

[7]周冬鑫，金文光，容志能．基于分層的無線傳感網絡多跳分簇路由算法[J]．傳感技術學報，2011，24(1):73－78．

[8]王良明，廖聞劍．無線傳感器網絡可生存理論與技術研究[M]．人民郵電出版社，2011:49－52．

[9]Heinzelman W，Chandrakasan A，Balakrishnan H．Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences．Hawaii，USA，2000．3005－3014．

[10]Heinzelman W，Chandrakasan A，Balakrishnan H，et al．An Application-Specific Protocol Archtecture for Wireless Micro-Sensor Network[J]．IEEE Trans on Wireless Communication，2002，1(4):660－670．

[11]杜向黨，李亦洋，石秀華．無線傳感器網絡基于類的簇頭選擇算法改進[J]．傳感技術學報，2008，21(7):1202－1206．

[12]李任發，羅娟，肖玲，等．無線傳感器網絡與 OMNet++實現[M]．湖南大學出版社，2011．

[13]Liu M，Gong H G，Mao Y C．A Distributed Energy-Efficient Data Gathering and Aggregation Protocol for Wireless Sensor Networks[J]．Journal of Software，2005，16(12):2106－2116．

[14]謝志恒，張向利，何龍，等．基于距離和角度的無線傳感器網絡路由方案[J]．計算機工程與應用，2010，46(31):109－110．

[15]鄧曙光，沈連豐，陳新輝，等．大規模無線傳感網中基于能耗均衡的按需 QoS協議[J]．電路與系統學報，2010，15(4):75－81．