無線傳感器網絡層次型路由協議研究與仿真

王華兵

（長沙民政職業技術學院，湖南長沙410004）

1.引言

近年來無線通信、微機電系統、低功耗模擬和數字電路、低功耗射頻技術的進步，推動了低成本、低功耗、多功能傳感器的快速發展，使其在微小體積內能夠集成信息采集、數據處理和無線通信等多種功能。大量的這種傳感節點被布置在監測區域中，自組織成無線傳感器網絡，可以完成復雜的監控任務。但是由于受到體積、成本等因素的限制，傳感器節點的計算能力、存儲能力和通信帶寬非常有限，節點只能攜帶有限的電池能量作為能源。為了完成特殊的監控任務，傳感器節點通常被部署在環境惡劣的地區，無法補充或更換能源，因此如何減少能量消耗，盡可能地延長網絡的生命周期是一個關鍵問題。網絡數據傳輸離不開路由協議，設計能量高效的路由協議以盡量延長網絡的生命周期至關重要。

2.無線傳感器網絡簇型模型分析

層次型路由協議也叫分簇路由協議。分簇的基本思想是把網絡中的傳感器節點劃分成若干個簇，如圖1所示。每個簇由一個簇頭(Cluster head)和多個簇成員(Cluster member)組成，簇成員只和自己的簇頭通信，簇頭把成員節點的傳感數據進行聚集和融合，傳送給基站（Sink），簇頭還可以負責簇間數據的轉發和基站控制消息的分發。其中成員節點和簇頭之間通信可以采取直接通信的方式，也可以通過多跳路由；簇頭節點還可以再產生更高一級簇首，以此遞歸，生成多層的分簇結構。

圖1 簇型網絡模型

圖1 給出的是單層的分簇結構。這種分簇結構具有很大的優勢：

把通信局部在簇內，減少了長距離無線通信；

可以采用數據融合機制，簇頭把成員節點的數據進行融合和壓縮；

減少了傳輸的數據量；

具有較好的可擴展性。

所以簇型網絡能有效地減少能量消耗、延長網絡的生命周期。在此網絡模型下主要的層次型路由協議有：LEACH、TEEN、EARSN、PEGASIS等。

3.無線傳感器網絡路由協議設計

3.1 LEACH協議

低功耗自適應集群分層型協議 (Low Energy Adaptive Clustering Hierarchy，LEACH)通過采用下面的策略來節約能量：采用簇型結構，把數據通信局部化在每個簇內，減少了長距離無線通信；運用數據壓縮和融合技術，把多個數據包壓縮成一個較小的數據包，減少了需要傳送的數據量；采用動態分簇技術，使網絡中的所有節點輪換充當簇頭，以均衡網絡中的能量消耗。保證各節點等概率地擔任簇頭，使得網絡中的節點相對均衡地消耗能量，它可以大大延長網絡的生命周期。

簇頭選舉算法：在每一輪開始時，每個節點自主決策自己是否成為本輪的簇頭。首先，每個節點產生一個0～1之間的隨機數，如果這個數小于門限值T(n)，則該節點成為本輪的簇頭。門限值T(n)可表示為：

其中，P是期望的簇頭數量在所有節點中所占的百分比，r是當前輪數，G是在最近前r mod(1/P)輪中未擔當過簇頭的節點的集合。符號mod是求模運算符號。在每輪循環中，如果節點在最近前r mod(1/P)輪中已經當選過簇頭，則把T(n)設置為0，這樣該節點不會再次當選為簇頭。對于在最近前r mod(1/P)輪中未當選過簇頭的節點，則將以T(n)的概率當選。

由公式1，在第0輪的時候(r=0)，每個節點充當簇頭節點的概率都為P。在第0輪充當簇頭節點的節點在后面的1/P輪中不能再次充當簇頭節點。這樣，剩下的節點數目變少了，所以增加剩余節點能夠充當簇頭節點的概率，這樣才能保證每一輪中簇的個數保持均衡。到(1/P)－1輪時，T=1，此時對于任何在過去的(1/P)－1輪中還沒有做過簇頭節點的節點，都可以成為簇頭節點。等過了1/P輪以后，所有的節點就又可以重新充當簇頭節點了。

一旦節點確定自己在本輪要充當簇頭，就廣播通告包，通告包中包含自身的節點ID。所有簇頭以相同的功率廣播通告包。其它節點的接收器一直處于工作狀態，用于接收來自簇頭節點的通告消息。每個節點可能會收到多個來自不同簇頭節點的通告消息，節點根據接收到消息的信號強弱，選擇信號最強的通告包的發送源節點作為自己的簇頭節點。

當成員節點確定了自己屬于哪個簇之后，它向自己的簇頭發送加入請求包，通知簇頭節點自己將成為它的成員之一，包中包含自身ID和簇頭節點ID。經過一段時間之后，簇頭會收到所有成員節點的加入請求消息，基于成員節點的數目，簇頭節點會生成一個TDMA（時分多址）時隙表，并通過廣播通知自己的成員節點。采用TDMA機制使得簇的所有成員節點的數據傳輸沒有碰撞和沖突，而且在某一節點向簇頭傳送數據的時候，其它成員節點可以關閉自身的無線裝置，節省能量。至此，建立階段完成，開始穩定的數據傳輸階段。

穩定的數據傳輸階段，每個成員節點在屬于自己的時隙里向簇頭發送傳感數據，在自己的時隙沒有到來的時候，成員節點可以關閉收發器以節約能量。而簇頭節點必須一直讓自己的接收器處于開啟狀態，用于接收來自不同成員節點的數據。為了節省能量消耗，每個成員節點采用功率控制調整自身的發射功率。當一幀的數據傳送完之后，簇頭節點對接收到的數據進行數據融合，把接收到的數據壓縮成一個新的信號，然后發送給基站。

上面的通信過程都是在各個簇的內部進行的，網絡正常工作的時候，是多個簇在同時進行工作。由于無線射頻是一種廣播介質，因此一個簇內的通信難免會影響到其它鄰近簇的工作。為了減少簇間干擾，不同的簇內部通信采用CDMA（碼分多址）機制。如果一個節點擔任了簇頭節點，那么它就從一組擴展碼中選出一個擴展碼作為這個簇的識別碼，然后通知簇中的成員節點。這樣，在簇內通信的時候，其它簇的信號就會被濾除。

3.2.CHMH協議

在LEACH所采用的網絡模型中，由于基站是固定的，并且放置在遠離整個無線傳感器網絡的地方，那么簇首節點與基站的通信能量消耗是影響網絡生存期的首要因素。并且對傳感器節點和網絡，LEACH假設所有的節點都可以和基站直接通信。在大規模布置的無線傳感器網絡中（如戰場監測、野外生態環境監測等），其網絡覆蓋范圍可能達到幾公里甚至幾十公里，所有節點與基站直接通信的假設無法滿足應用的要求。所以，LEACH不適用于大規模布置的無線傳感器網絡。

基于簇首中轉的多層聚簇路由算法(CH-relay-based Multi-hierarchy,CHMH)CHMH是對LEACH的一種改進，采用的網絡模型與之基本一致，唯一不同之處在于：不存在所有節點都能與基站直接通信這一假設。這樣的模型更適用于大規模布置的無線傳感器網絡。

如圖2所示，在CHMH協議中，將無線傳感器網絡劃分為兩個區域：Sink信號覆蓋區域(CA)和Sink未覆蓋區域(UA)。位于CA區域中的節點都能與Sink直接通信，位于UA區域中的節點無法與Sink直接通信。

圖2.CHMH協議網絡模型

所有分簇采用LEACH協議生成，并采用LEACH的簇首選舉機制產生簇首節點。在鄰節點表中加入NA域，用來表明節點所在的區域。初始時NA域為最大值，CA區域的節點的NA域為0。如圖2所示，A、B節點能與Sink直接通信，它們與Sink直接交換數據；位于UA區域中的C、D、E節點無法與Sink直接通信，它們在鄰節點表中尋找位于NA比自己小的節點，從中選擇NA最小的節點，將其作為Sink，并將自己的NA設置為該鄰節點的NA域加1，并向自己的鄰節點廣播更新消息。如果未能找到NA域比自己小的鄰節點，則在一個設定的時間間隔后重新查找。

如圖2所示，初始時，所有節點的NA域為最大值，分簇形成，簇首節點選定后，A、B與Sink通過信息交換，得知自己位于CA區域，將自己的NA域置0，并向鄰節點表中的簇首節點廣播自己的更新信息。C、D、E節點在自己的鄰節點表中尋找NA域最小的簇首節點，若找到，則將該鄰節點作為Sink節點。如圖2中所示，C在鄰節點表中找到A是符合要求的鄰節點，C向A發出請求信息。A收到請求后，為C分配時隙，并在應答信息中攜帶時隙信息。C收到應答信息后，將自己的NA域設置成A的NA域加1，并向鄰節點表中的簇首節點廣播自己的更新消息。此時，E收到來自C的更新消息，更新自己鄰節點表中關于C的信息。E在鄰節點表中找到滿足條件的C節點，重復C節點的動作。最后，所有的簇首節點都能與Sink通信，算法收斂。

4.算法仿真與分析

本文使用NS2網絡仿真軟件，對原LEACH協議和改進協議CHMH進行仿真測試，設計典型的實驗場景，根據多種性能指標分析比較它們的性能，對改進算法的效果進行驗證。

實驗場景為：100個節點隨機分布在100m×100m大小的區域中，它們的坐標從(x=0,y=0)到(x=100,y=100)，Sink節點的坐標為(50,115)。為了考查改進算法在大規模布置的傳感器網絡中的工作情況，設計另一種大規模布置的場景：100個節點隨機分布在400m*400m大小的區域中，它們的坐標從 (x=0,y=0)到 (x=400,y=400)，Sink節點的坐標為(200,215)。LEACH中各節點均能到達Sink節點，基于簇首中轉的多層聚簇路由算法(CHMH)和基于節點度的多層聚簇路由算法(NDMH)還存在如下的假設：

傳感器節點的覆蓋半徑為30m；

傳感器節點的感知半徑為10m；

節點總有數據向基站發送，數據包的大小為500Bytes，包頭大小為25Bytes；

仿真算法如下：

表1.仿真算法

這里采用傳感器網絡節點的死亡時間〔第一個節點死亡時間(First Node Dies,FND)、半數節點死亡時間(Half of the Nodes Dies,HND)〕作為評價無線傳感器生存期、比較改進算法和原協議的性能的指標。

在圖3中，對比了LEACH與CHMH的FND和?HND指標。從圖中可以看出，FND和HND與LEACH相比，CHMH分別提高了31%和29%，這說明多跳接力的多層聚簇路由能夠明顯節省節點能耗，延長網絡生存期。

圖3.CHMH100×100場景FND和HND指標仿真結果

圖4 展示的是LEACH與CHMH在大規模布置網絡情況下的指標對比。從圖中可以看出，FND和HND與LEACH相比，CHMH分別提高了1.2倍和0.9倍。說明在大規模布置的無線傳感器網絡中，CHMH比LEACH表現得更好，能夠更有效地延長網絡生存期。

圖4.CHMH400×400場景FND和HND指標仿真結果

從圖3和4可以看出，CHMH能夠顯著延長網絡生存期，網絡規模越大，效果越明顯。這得益于多層聚簇和多跳轉發的機制。

5.結論

通過上面的仿真測試，由結果對比可以得出結論：改進之后的CHMH算法由于考慮了簇首節點與Sink節點的距離，采用多層聚簇和多跳轉發的機制，使得簇首與Sink節點通信過程中能耗降低，從而均衡了網絡中的能量分布、進一步延長了網絡的生命周期。

[1]楊明帥.無線傳感器網絡路由算法研究[D].杭州：浙江大學,2005.

[2]馬祖長,孫怡寧,梅濤.無線傳感器網絡綜述[J].通信學報,2004,25(4):114～124.

[3]孫利民,李建中,陳渝等.無線傳感器網絡[M]..清華大學出版社,2005.

[4]梁英,于海斌,曾鵬.無線傳感器路由協議[J].信息與控制,2005,34(3):325～330.

[5]于斌,孫斌,溫暖等.NS2與網絡模擬[M]..北京:人民郵電出版社,2007.

[6]王春.無線傳感器網絡路由協議的設計與仿真[D].成都：.電子科技大學,2005.