劉睿瓊，齊小剛，孫正海

(1.西安電子科技大學研究生院，陜西西安 710071;2.西安電子科技大學理學院，陜西西安 710071;3.西安理工大學高等技術學院，陜西西安 710082;4.空間電子信息技術研究院，陜西西安 710000)

作為一種新的信息獲取方式和處理模式，無線傳感器網絡(Wireless Sensor Network，WSN)目前已成為國內外備受關注的研究熱點。由于工作環(huán)境和自身構造所限，WSN網絡傳感器節(jié)點的計算、通信能力及能量都較為有限，對于節(jié)點的更換和充電也較難實現。因此，盡量減少節(jié)點能耗、延長網絡生存時間，已成為WSN網絡協議及傳輸機制研究的一個主要目標。網絡中的數據傳輸靠路由協議控制管理，無線傳感器網絡具有與傳統(tǒng)網絡不同的特點，傳統(tǒng)路由協議不能有效地用于無線傳感器網絡。人們研究了眾多的路由協議，其中 LEACH(Low—Energy Adaptive Clustering Hierarchy)［1］協議是由美國麻省理工學院的J.Heinzelman等人提出的一種低功耗自適應分層算法，對該算法的分析研究以及改進有著重要的應用價值。

l LEACH協議

LEACH是一種分布式自組織的分簇協議，LEACH協議按輪(Round)運行，每輪分為初始化(Setup)和穩(wěn)定(Steady)兩個階段。在初始化階段，首先以自組織的方式隨機選出部分傳感器節(jié)點作為簇頭。每個節(jié)點產生一個0～1之間的隨機數，若隨機數小于設定的閾值T(n)，則該節(jié)點發(fā)布自己是簇頭的消息。T(n)的計算公式為

其中，p是簇頭占所有節(jié)點的百分比，即節(jié)點當選簇頭的概率;r表示目前進行的輪數;G代表前輪中還沒有當選過簇頭的節(jié)點集合。在簇頭選舉過程中，若節(jié)點已經當選過簇頭，則將T(n)值設置為0，在下一輪選舉中不再參與簇頭節(jié)點選舉，這樣保證網絡中每個節(jié)點都有當選簇頭的機會。當只剩下一個節(jié)點未當選簇頭時，T(n)值為1，表明其一定當選為簇頭節(jié)點。簇頭節(jié)點選定后，選出的簇頭進行廣播，非簇頭節(jié)點根據接收信號的強弱來選擇加入最近的簇，并通知相應簇頭。當簇頭節(jié)點接收完所有節(jié)點的加入信息后，就會形成一個TDMA時隙列表，并向簇內所有節(jié)點通知。

在穩(wěn)定階段，簇內節(jié)點通過TDMA方式與簇頭進行通信，簇內其他節(jié)點將采集的數據傳輸給簇頭節(jié)點，簇頭節(jié)點對簇中所有節(jié)點采集的數據進行進行聚合再發(fā)送給Sink節(jié)點。

LEACH協議中分層的簇型結構降低了節(jié)點能量消耗，但LEACH協議存在以下缺點:(1)簇頭的選擇完全依賴于簇形成階段節(jié)點產生的隨機數，從而導致簇頭的產生具有較大的隨機性;作為簇頭的節(jié)點不一定是最優(yōu)節(jié)點。(2)傳感器節(jié)點分布不均勻，可能會出現個別簇頭相距Sink節(jié)點太遠或部分簇內成員離簇頭太遠的情況，大幅增加了節(jié)點的傳輸能耗，反而不能有效延長網絡生存時間。(3)協議沒有考慮節(jié)點的剩余能量和節(jié)點之間的距離。

2 LEACH－C協議

LEACH—C協議［2］是在LEACH基礎上加以改進的一種集中式路由協議。協議仍然引用“輪”的概念，每輪還是簇建立和數據傳輸兩階段。但在第一階段與LEACH有較大不同。LEACH－C中，每個傳感器要先將自己的位置和能量信息傳輸給基站，基站根據模擬退火算法和簇平衡原理決定簇頭。LEACH是傳感器器節(jié)點和簇首之間根據廣播信號的強度來確定節(jié)點歸屬于哪個簇，而LEACH－C中節(jié)點的位置已確定，基站在確定簇頭后將簇頭的信息廣播給各個節(jié)點，每個節(jié)點根據距離公式算出到各個簇頭的距離來確定該節(jié)點加入哪個簇。在數據穩(wěn)定傳輸階段，如果簇頭沒有收到該簇傳感器的數據，那么要對節(jié)點的能量進行判斷，如果小于閾值那么就認為節(jié)點已經死亡，如果大于閾值就認為節(jié)點已經移動，重新判斷節(jié)點應該屬于哪一簇。

LEACH－C協議由基站選擇簇頭好處是均衡整個傳感器網絡的能量，并合理安排簇頭的地理位置，使簇頭之間不過于集中，從而延長了網絡壽命。正是由于整個網絡過分依賴基站，若節(jié)點由于某種原因不能向基站正確傳送自身信息時，基站就無法根據網絡情況選出較好的簇頭節(jié)點。另外，增加了成簇的開銷、時間延遲、信號干擾以及網絡流量。文中提出一種基于節(jié)點的地理位置信息和能量的分簇算法(New Geography and Energy Cluster Algorithm，NGECA)。

3 NGECA算法描述

3.1 網絡模型

文中N和傳感器節(jié)點均勻分布在一個正方形區(qū)域內，并且該傳感器網絡具有如下特點:(1)所有節(jié)點部署后不再移動，基站部署在區(qū)域以外的一個固定位置。(2)所有節(jié)點初始能量相同并可以根據距離調整無線發(fā)射功率的大小。(3)若已知對方發(fā)射功率，節(jié)點可以根據接收信號的強度計算出發(fā)射者到自己的近似距離。

3.2 簇頭選擇

LEACH協議簇首節(jié)點分布不均，可能出現節(jié)點密集的地方簇首多，節(jié)點稀疏的地方簇首節(jié)點少，甚至部分節(jié)點可能沒有在任何簇內，造成網絡的不完全連通。另外節(jié)點密集處如果產生了多個簇首，收集到的數據也會產生冗余，造成能量的不合理消耗。因此，算法首先尋找最優(yōu)簇頭的個數。

采用的能量模型是一種簡單的一階無線電能量模型通信模型，與文獻［3］相同，節(jié)點收發(fā)數據的能耗通過式(2)和式(3)計算

(1)發(fā)送階段能量消耗為

(2)接收階段能量消耗

則整個簇在一輪中所需能量Ecluster為簇頭和簇成員所需能量因此整個網絡一輪中所需能量為K個簇所需能量值之和，即

式(8)中參數具體值均可在網絡設置是給定，這樣就直接得到最優(yōu)簇頭數。

隨后根據網絡節(jié)點分布，網絡規(guī)模確定簇首間的最短距離，再結合式(9)中改進閾值T(n)［4］來選擇簇頭

其中，Ecur表示節(jié)點當前能量;E0表示節(jié)點初始能量;rs表示節(jié)點連續(xù)未當選簇頭的輪數，若節(jié)點成為簇頭;rs重置為0。此改進閾值公式不僅考慮能量因素，而且閾值可動態(tài)調整，使在連續(xù)輪中未當過簇頭的節(jié)點成為簇頭概率變大，平衡網絡能量。

3.3 分簇過程

在網絡初始化階段，基站利用較大的發(fā)射功率向所有節(jié)點發(fā)送廣播消息(ADV)，每個節(jié)點收到后根據接收信號計算自己到基站的距離dtoBS，當第i個節(jié)點當選為簇頭時，其簇內節(jié)點成員數目n［5］可按式(10)確定

其中，λ為加權因子，取0.5;dmax和dmin為節(jié)點到基站的最遠和最近距離。這樣保證了靠近基站的簇規(guī)模小、數量多，遠離基站的簇規(guī)模大、數量少，保持簇間負載均衡?？梢缘贸龃爻蓡T的最大數目為

簇頭選好后，向周圍非簇頭節(jié)點發(fā)出簇頭特有信號，非簇頭節(jié)點根據接收信號強弱判斷加入信號最強的簇，簇頭必須控制加入簇的節(jié)點數量和簇的大小。如果簇頭同意節(jié)點加入簇，會向節(jié)點發(fā)送允許加入信息，否則發(fā)送拒絕信息。當普通節(jié)點收到簇頭的拒絕信息時，再嘗試向另一個距離較近的簇首發(fā)出申請，直至接收到允許加入的信息和簇內傳輸數據的TDMA，此時分簇成功。這樣建簇使得每個簇節(jié)點數會比整個網絡節(jié)點數少得多，傳輸數據的距離也相對較小，數據傳輸延遲不會過于明顯［6］。

3.4 簇間路由

簇內發(fā)送數據采用單跳傳輸，而簇頭將信息融合后以多跳方式傳到基站。將Dijkstra算法應用到簇頭間路由，其主要思想是用最短路徑算法的選路方法，這樣做可以使各簇頭節(jié)點以最快的速度找到距離 Sink的最短路徑。當簇頭準備將數據傳輸到Sink時，簇頭先對簇成員的數據進行聚合，消除數據冗余，減小數據包的傳輸量，提高網絡的能量利用率。文中假設數據可以進行完全聚合，然后各簇頭用 Dijkstra算法找到距離Sink的最短路徑將數據以多跳通信的方式發(fā)送至Sink。這樣，有效降低了距離Sink較遠的簇頭給Sink傳送數據的能耗。

4 算法仿真

借助Matlab仿真工具，通過編寫VC++及Matlab程序，實現對LEACH，LEACH－C，NGECA仿真比較。仿真流程如下:(1)按LEACH算法和本文算法的原理編寫VC++程序(leach.cpp、leach－c.cpp和 ngeca.cpp)，在此實現變量初始化、簇頭選擇、分簇、簇內數據收發(fā)以及簇頭向Sink數據發(fā)送。(2)將以上兩個VC++程序運行后的數據保存保存為兩個文件表(outputl.txt、outputlc.txt和outputn.txt)，保存每輪運行結束后所有節(jié)點總能量和簇內剩余節(jié)點數目。(3)用MatlabR 2007a編寫繪圖程序，將輸出在txt文件中的數據繪圖并進行比較。

網絡在100 m×100 m的區(qū)域內，隨機部署100個傳感器節(jié)點，基站坐標(50，175)。設定節(jié)點初始能量E0為 2 J，為 50 nJ/bit，εfs為 10 pJ/bit·m－2，εmp為0.001 3 pJ/bit·m－4，EDA為 5 nJ/bit signal，數據包長度為4 800 bit，廣播包長度為200 bit，節(jié)點能量低于Eth=0.000 1 J時，認為其死亡，假設數據融合率為100%，且在轉發(fā)過程中無數據包丟失情況，沒有誤碼率。

從圖1和圖2可以看出，GECA算法在網絡存活節(jié)點數以及網絡運行過程中的剩余總能量都明顯優(yōu)于LEACH和LEACH－C算法，有效延長網絡的生命周期，解決了LEACH算法簇頭個數不確定，簇頭位置最優(yōu)化不完全等問題。與LEACH－C相比，NGECA算法有效解決了LEACH－C中對基站過高的依賴性。

5 結束語

對無線傳感器網絡分簇算法LEACH協議和LEACH協議進行重點分析，針對LEACH協議簇頭數目不選取的隨機性導致分均勻分簇造成的能量損耗問題，以及LEACH－C協議過分依賴簇頭所造成的分簇開銷、時間延遲和信號干擾的增大，設計了一種基于節(jié)點的地理位置和能量的分簇算法NGECA。通過仿真實驗比較，說明NGECA算法在節(jié)點存活個數和網絡剩余總能量上都明顯優(yōu)于LEACH和LEACH－C協議，有效延長了網絡的生存周期。但延遲方面還需進一步改進，并且也沒有考慮安全因素，下一步將對能量高效的路由協議安全性作進一步討論。

［1］WENDI R H，ANANTHA C，HARI B.Energy—efficient communication protocol for wireless microsensor network ［C］.Washington:IEEE Proceedings of the Hawaii International Conference on System Science，2000:3005 －3014.

［2］何延杰，李臘元，邢明彥.WSN中一種能量均衡的分簇路由協議的設計［J］.傳感技術學報，2009，22(10):1510－1514.

［3］HEINZELMAN WB，CHANDRAKASAN A P，BALAKRISHNAN H.An application specific protocol architecture for wireless microsensor networks ［J］.IEEE Transaction on Wireless Communications，2002，1(4):660 －670.

［4］沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議［J］.軟件學報，2006，17(7):1588－1600.

［5］韓萬強，劉云.WSN中基于分簇的改進路由協議［J］.計算機工程，2012，38(5):105 －107.

［6］潘雪峰，李臘元，何延杰.低能耗無線傳感器網絡路由協議研究［J］.計算機工程與設計，2012，33(4):1347－1351.