王華兵

（長沙民政職業(yè)技術(shù)學院，湖南長沙410004）

1.引言

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

2.無線傳感器網(wǎng)絡(luò)簇型模型分析

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

圖1 簇型網(wǎng)絡(luò)模型

圖1 給出的是單層的分簇結(jié)構(gòu)。這種分簇結(jié)構(gòu)具有很大的優(yōu)勢：

把通信局部在簇內(nèi)，減少了長距離無線通信；

可以采用數(shù)據(jù)融合機制，簇頭把成員節(jié)點的數(shù)據(jù)進行融合和壓縮；

減少了傳輸?shù)臄?shù)據(jù)量；

具有較好的可擴展性。

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

3.無線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計

3.1 LEACH協(xié)議

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

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

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

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

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

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

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

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

3.2.CHMH協(xié)議

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

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

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

圖2.CHMH協(xié)議網(wǎng)絡(luò)模型

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

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

4.算法仿真與分析

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

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

傳感器節(jié)點的覆蓋半徑為30m；

傳感器節(jié)點的感知半徑為10m；

節(jié)點總有數(shù)據(jù)向基站發(fā)送，數(shù)據(jù)包的大小為500Bytes，包頭大小為25Bytes；

仿真算法如下：

表1.仿真算法

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

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

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

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

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

從圖3和4可以看出，CHMH能夠顯著延長網(wǎng)絡(luò)生存期，網(wǎng)絡(luò)規(guī)模越大，效果越明顯。這得益于多層聚簇和多跳轉(zhuǎn)發(fā)的機制。

5.結(jié)論

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

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

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

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

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

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

[6]王春.無線傳感器網(wǎng)絡(luò)路由協(xié)議的設(shè)計與仿真[D].成都：.電子科技大學,2005.