WSNs基于非均勻分區成簇的多跳路由協議

陳 笑 祁榮賓 錢 鋒 Huaglory Tianfield

(化工過程先進控制和優化技術教育部重點實驗室(華東理工大學)1，上海 200237;

WSNs基于非均勻分區成簇的多跳路由協議

陳 笑1祁榮賓1錢 鋒1Huaglory Tianfield2

(化工過程先進控制和優化技術教育部重點實驗室(華東理工大學)1，上海 200237;

針對無線傳感器網絡中節點能量有限和能量空洞問題，提出了一種基于優化簇半徑的非均勻分區成簇多跳路由算法(UZCMR)。在分簇時充分考慮節點的能量和地理位置，通過“逐層分區”的方法將整個網絡以Sink為中心劃分成若干個區域。每個區域中的節點通過最優簇半徑進行分簇，同時使用參數使靠近Sink節點的簇的規模小于遠離Sink節點的簇，并采用了最小通信代價的多跳路由。試驗表明，與低功耗自適應集簇分層型(LEACH)協議相比，UZCMR形成的簇首分布均勻，有效均衡了節點能量消耗，緩解了能量空洞問題，顯著延長了網絡生命周期，也擴大了協議的適用規模。

無線傳感器網絡(WSN) 低功耗自適應集簇分層型(LEACH)協議 能量消耗 Sink節點 多跳路由協議

國家自然科學基金資助項目(編號:20876044);

上海市基礎研究重點基金資助項目(編號:10JC1403500);

上海市重點學科建設基金資助項目(編號:B504)。

修改稿收到日期:2012-05-31。

0 引言

無線傳感器網絡的目的是協作地感知、采集和處理網絡覆蓋區域里被監測的對象信息。大規模無線傳感器網絡通常包括三類節點，即傳感器節點(sensor node)、匯聚節點(Sink)和管理器節點［1］。鑒于能量平衡或其他總體網絡性能指標，節點之間并不是全部一對一進行通信，而是通常借助中間節點以多跳路由的方式將源數據傳送至目的節點。

分簇路由是無線傳感器網絡節省能耗的一種重要方法，采用分簇結構可以提高能量利用效率，達到負載平衡的目的。它的主要思想是在無線傳感器網絡中選擇部分節點作為簇頭節點，以此將網絡劃分成簇。簇內成員節點將數據發送給簇頭節點，簇頭節點將數據經數據融合后以多跳方式發送給Sink節點。這種分簇方式雖有利于節省能量，但也使得靠近Sink節點的簇頭承擔了過多的轉發任務而過早死亡。通常把這種問題稱為“熱區”問題［2-3］。

Heinzelman等人提出的低功耗自適應集簇分層型(low energy adaptive clustering hierarchy，LEACH)協議［4］是早期的一種專為無線傳感器網絡設計的經典分布式低功耗自適應分層路由協議。該協議定義了“輪(round)”的概念。許多研究都沿用了LEACH協議的分簇思想。但是LEACH算法沒有考慮節點的能量，采用單跳通信路由造成距離匯聚節點遠的節點能量開銷過大;也不能保證簇頭數目和分布，當簇頭與匯聚節點(Sink)相距較遠時，通信會消耗較多能量，造成網絡能耗不均衡。

繼承LEACH協議成簇思想的改進協議有很多。Lindsey S等人提出的PEGASIS(power-efficient gathering in sensor information system)將網絡中的所有傳感器節點構成鏈(chain)，全網只選擇一個群首節點［5］。Handy M J等人在選擇簇首時考慮了節點的能量因素，使具有較多剩余能量的節點有更多機會成為簇頭，但未考慮節點的位置［6］。李成法等人提出的節能非均勻簇(energyefficient uneven cluster，EEUC)是一種非均勻的分簇路由協議，它基于地理位置不同對網絡進行規模不等的分簇，緩解了“熱區”問題，但并沒有討論如何優化簇半徑［7］。網絡分簇時，簇的規模過大或過小都不利于消減能耗。劉安豐等人提出了一種采用不等簇半徑輪換工作的能量空洞避免策略［8］。Faroop M O等人提出了MR-LEACH多跳路由協議，以Sink節點為圓心將網絡劃分成均勻的圓環區域，圓環內的節點單跳成簇，不同環內的簇頭節點以多跳路由的方式將數據傳送到Sink節點［9］。該方法假設Sink節點可與所有節點通信。

綜合而言路由協議大致可分為兩類，一類為選取固定數量的簇頭節點，另一類為選取固定長度的簇半徑。為此，本文在LEACH算法的基礎上，提出一種新型的基于非均勻分區成簇的多跳路由協議(uneven zoned clustering multi-hop routing，UZCMR)。此方法將網絡逐層劃分區域，解決了大規模網絡中Sink節點并不可能與每一個節點通信的問題。另外，用優化的簇半徑對網絡進行不等規模分層成簇，使靠近Sink節點的簇半徑較小，以便均衡靠近Sink節點的簇頭的能量消耗，為其轉發其他簇頭的數據預留能量，從而緩解“熱區”問題。

1 LEACH算法簡介

LEACH是低功耗自適應分簇路由算法。它的成簇方法簡單，是一種經典的分簇協議，被廣泛使用和改進。LEACH主要考慮簇內節點的能量消耗問題，其將網絡的能量平均到每個傳感器節點中。LEACH定義了“輪”的概念，每一輪包括初始化和穩定工作兩個階段。

在初始化階段，各節點生成一個0～1的隨機數。如果該數小于閾值T(n)，則選擇該節點作為簇首。T(n)計算方法如下［4］:

式中:P為網絡中簇頭占總節點的百分比;r為選舉輪數;rmod(1/P)代表這一輪循環中當選簇頭的節點個數;G為這一輪循環中未當選簇頭的節點集合。

在穩定工作階段，節點持續采集監測數據并傳送到簇頭，簇頭對數據進行必要的融合處理后，發送到匯聚節點。為了避免額外的處理開銷，穩定工作狀態一般持續相對較長的時間。在本輪工作完成之后，網絡將重新進入下一輪的工作周期，完成兩個階段的過程。

基本LEACH協議存在如下問題。

①簇頭與匯聚節點間采用直接通信方式，其能量利用效率較低。

②簇頭選舉由隨機數產生，這可能導致簇頭分布不合理和個數偏離期望值。

③簇頭與匯聚節點的單跳方式使得節點通信范圍有限，限制了網絡覆蓋范圍，不適用于大規模部署的網絡。

針對這些問題，本文從簇頭選舉、簇的建立和簇間路由通信這三方面對LEACH進行了改進。

2 UZCMR路由協議

在UZCMR路由協議設計過程中，主要考慮網絡總能量消耗最小和使各個區域的能量消耗均衡，避免“熱區”問題。UZCMR協議算法也采用了“輪”的概念，每一輪分為初始化階段和穩定數據傳送階段，其中穩定數據傳送階段分為很多“幀”。初始化階段包括簇頭選舉、簇形成以及簇間路由樹構造。在數據傳輸階段，簇成員節點采集數據并發送給簇頭，經過數據融合后發送給Sink節點。

節點部署完成后，每個節點初始化并處于信號監聽狀態，同時收集匯聚節點以及各區域簇頭的廣播信息。簇頭多跳路由示意圖如圖1所示。

圖1 簇頭多跳路由示意圖Fig.1 Schematic of cluster-head multi-hop routing

本文引入“區域”的概念，采用逐層劃分區域的方法，即Sink節點以一定半徑廣播信號，監聽到Sink節點廣播信號的節點組成Z1(Z1=1)，Zi中節點以概率P(Zi)選舉出簇頭后，以一定的半徑廣播信息。首次監聽到信號的傳感器節點若尚未得知層次信息，那么其層次為(Zi+1)，同時以概率P(Zi+1)選舉簇頭并廣播簇頭信息。在數據傳輸階段，(Zi+1)中的簇頭根據監聽到的Zi中簇頭的信息選擇所要加入的下一跳簇頭，并在穩定數據傳輸階段向其發送數據，經過多跳后將數據發送給Sink節點。

2.1 網絡模型

本文對無線傳感器網絡模型作以下假設。

①假設N個無線傳感器節點隨機均勻部署在二維平面上的一塊方形區域A內，匯聚節點處于該區域范圍之外。

②傳感器節點同質，能量有限，部署后無法補充能量，其信號傳輸功率有限，不一定能夠直接將信號發送至匯聚節點。

③所有傳感器節點同構，在網絡中具有相同的重要性。

④網絡鏈路對稱，無線電發射功率可控，節點可以根據發送距離選擇無線電信號發射功率。

⑤傳感器節點的位置未知，且無法采用GPS定位;節點部署后不再移動。

2.2 能耗模型

本文采用的能耗模型如下。定義無線電路發送l bit消息至距離d m消耗的能量為:

式中:Eelec為發射電路能量損耗，由電路本身決定;εfsd2、εmpd4為無線電功率放大損耗。d0由式(3)決定:

而傳感器每通過無線電接收 l bit數據，能耗如下:

數據融合1 bit所消耗的能量為EDA。

2.3 網絡分層

對于本文提出的基于簇半徑優化的非均勻分簇路由協議，采用逐層成簇的方法。該方法中每個傳感器節點不需要通過匯聚節點廣播或者GPRS的方式獲取自身位置信息。

網絡分區時，從Sink節點向外將網絡區域分別編號為Z1，Z2，…，Zn，由Z1開始逐層劃分。匯聚節點廣播分層信號并確定網絡的Z1。設匯聚節點距離傳感器區域距離為d，Z1的區域半徑為r1，那么匯聚節點廣播半徑為R0=d+r1。接收到匯聚節點廣播信號的傳感器節點S(i).Z=1，并開始選舉簇頭，下一區域范圍由上一層簇頭的廣播信號確定。因此，Sink節點無需與網絡范圍內的所有節點通信，更適用于在大規模網絡中的應用。

劉明等人對單個簇的能耗進行了分析，最優簇半徑推導如下［10］:

式中:A為監測區域的面積;N為區域內節點數量;EDA為融合每比特數據所消耗的能量;εfs為功率放大所需能量。

本文將最優簇半徑公式引入簇頭競爭半徑。

式中:α為梯度因子，α≥1。

上一區域確定簇頭后，簇頭節點以半徑Ri廣播相關信息，包括節點ID、區域Zi、與匯聚節點的通信代價、傳感器網絡節點的平均能量(Eavg)。

在簇頭競選階段，為了避免由于Sink附近節點轉發大量數據而產生能量空洞問題，本文采用非均勻分簇的方法，使得距離匯聚節點遠的區域中簇頭密度較小，簇的規模相對較大;距離匯聚節點較近的層中簇頭分布相對密集，簇的規模相對較小，從而平衡簇頭的能量負載。

另外，考慮到節點剩余能量對競選簇頭的影響，使剩余能量較高的節點成為簇頭的概率較高。假設初始成簇概率為P0(0.07)，令:

式中:β為簇頭非均勻程度參數，0＜β≤1，β越小，層與層之間的成簇概率梯度越大;Eresidual為節點的剩余能量;Eavg為整個網絡節點的平均能量。這里由于網絡模型中定義所有傳感器節點同質，因此，當輪數r=1時，Eavg=Emax;當r＞1時，在每一輪的最后一幀里，傳感器節點需要將自身的剩余能量與傳感數據一起發送至匯聚節點，匯聚節點計算節點平均能量:

在下一輪的簇頭競選中將Eavg廣播給傳感器網絡Z1的網絡區域，后面競選成為簇頭的節點依次廣播至網絡所有區域。

2.4 簇的建立

當某區域中節點產生的0～1之間的隨機數小于

2.5 簇間通信

在某一區域成簇以后，該區域中的所有簇頭需要選擇上一層的一個簇頭作為將數據多跳傳送至Sink節點的下一跳節點。為了提高網絡的能量效率和網絡負載平衡，若Zi-1區域中存在簇頭剩余能量大于Eavg，那么選取該部分簇頭中通信代價最小的簇頭作為Zi中某簇頭的下一跳簇頭節點，否則，選取剩余能量最大的簇頭作為該簇頭的下一跳簇頭。將Sink節點也看做一個簇頭，其所在的區域S(i).Z=0，通信代價為0。節點由Z0開始，若確認自己為簇頭，Sink節點則以半徑Ropt發送廣播信息，包括ID、層次、通信代價。未知層次的節點Ni保存所收到的廣播信息，據此計算自己的層次信息，Zi=Zj+1，其中Zi為節點Ni的層，Zj為接收到的簇頭所處的層。若Ni在后續的簇頭競選中能夠當選，Ni可以根據廣播信息選擇下一跳簇頭。

在簇頭競選過程中，簇頭Ni通過上一層 Nj向Sink每發送1 bit數據，整個網絡所消耗的總能量為Ccom，稱為節點Ni的通信代價。

同層或者下一層非簇頭節點可以根據廣播信息選擇加入合適的簇。假設Ni為簇頭，Nj、Nk、Nm為通信范圍內的非簇頭節點，且滿足:

那么Ni根據接收到的Nj、Nk、Nm的廣播信息，計算與匯聚節點通信的通信代價。

若Ccom(Ni-m-link)≤Ccom(Ni-j-link)≤Ccom(Ni-k-link)，則Ccom(Ni-link)=Ccom(Ni-m-link)。

簇頭Ni選擇通信代價最小的下一跳簇頭發送加入請求消息，得到確認后，在本輪通過該簇頭進行數據轉發。

為了保證通信質量，簇頭之間的通信采用載波監聽多路訪問(carrier sense multiple access，CSMA)的MAC協議。這里假設簇間的數據冗余度較低，簇頭只是轉發其他簇的數據。

2.6 算法步驟

具體的算法步驟如下。

①Sink節點以一定半徑廣播信息，收到Sink信息的節點i的S(i).Z=1。

③未確定區域的節點接收到廣播信號后確定自己為下一區域中的節點。

④重復步驟②、③，直至所有節點都確定自己的層次信息。

⑤網絡拓撲選擇下一跳節點:若Zi-1區域中存在簇頭剩余能量大于Eavg，那么選取該部分簇頭中通信代價最小的簇頭作為Zi中某簇頭的下一跳簇頭節點;否則，選取剩余能量最大的簇頭作為該簇頭的下一跳簇頭。

⑥各層中的簇頭節點以半徑Ri=Roptα(Zi-1)廣播信息，本層或下一層中的非簇頭節點根據收到的信息，分別計算通過該簇頭多跳至Sink的通信代價，并選擇通信代價最小的簇頭發送加入請求。

若普通節點均找到了所屬的簇，每個簇頭均找到了下一跳，則簇及多條路由建立階段至此結束，網絡進入數據采集階段。

⑦本輪數據采集結束后，進行重新分區與分簇，循環步驟①～⑦。

本文主要從以下幾個方面改進了LEACH協議。

①LEACH協議要求Sink節點能與所有節點通信。而UZCMR通過逐層劃分區域的方式，由上一區域的簇頭廣播信息來確定下一個區域;匯聚節點無需具有極高的信號發送功率和定位硬件模塊。

②成簇過程中引入了最優簇半徑的概念。在最優簇半徑的基礎上每個區域構建不同規模的簇。距離Sink節點較近的簇規模較小。這不但使每個區域能構建規模合理的簇，并且使靠近Sink節點的簇預留了能量來轉發相鄰簇頭的數據，緩解了能量空洞問題。

③簇頭節點選擇多跳路徑時，不僅考慮了通信代價，同時考慮了下一跳節點的剩余能量，從而均衡了網絡負載。

3 仿真試驗

為了對UZCMR協議的性能進行評估，在此利用Matlab平臺對該協議進行仿真試驗。將UZCMR算法在網絡能量均衡性、能量效率、生命周期等方面的性能表現，與LEACH和EEUC路由協議進行對比。各試驗參數如表1所示。

表1 試驗參數Tab.1 Experimental parameters

UZCMR的其他參數設置為:α=1.2、β =0.9，通過式(5)可得本文的Ropt=20.771 9 m。

UZCMR網絡分區圖如圖2所示，其中“*”代表Z1內的節點，“。”代表Z2內的節點，“+”代表Z3內的節點。

圖2 網絡區域劃分圖Fig.2 Network zones division

圖3給出了在相同參數和試驗條件下，幾種協議中存活節點數目隨時間(輪數)變化的情況。

從圖3可以看出，LEACH協議第一個節點死亡輪數是第254輪，EEUC是第776輪，而UZCMR協議出現第一個死亡節點輪數是1 217輪，比LEACH協議推遲了近1 000輪;而UZCMR協議最后一個節點死亡的輪數是1 710輪，EEUC是第1 092輪，LEACH是在第1 222輪。由此可知UZCMR由于引進優化的簇半徑公式，且采用分區成簇，各節點負載更為均衡，從而延長了網絡生命周期。

圖3 各種協議的網絡存活時間Fig.3 Network survival time of various protocols

每輪中各協議的總網絡剩余能量對比圖如圖4所示。

圖4 各協議的網絡剩余能量Fig.4 Network residual energy of various protocols

由圖4可以看出，由于UZCMR引入了最優簇半徑，使得網絡中的簇半徑大多接近最優化，減少了能量消耗。而LEACH協議由于隨機選擇簇頭節點，簇頭與Sink節點采用單跳方式，其能量消耗最快。EEUC協議的簇半徑不一定是最優，所以其節點能耗也多于UZCMR協議。

UZCMR在不同簇半徑下的網絡生命周期的對比圖如圖5所示。

圖5 簇半徑vs網絡生命周期Fig.5 Cluster radius vs.network life cycle

本文提取所有節點完全死亡時和還存活10個節點時的數據一起做分析比較。從圖5可以看出，在本文的環境下，簇半徑為20 m時網絡生命周期達到最大。當簇半徑過大時，節點由于遠距離通信會造成能量浪費，驗證了本文改進的結果。UZCMR通過優化的簇半徑，節省了網絡能量消耗。

UZCMR各區域中的節點在200和500輪時的平均能量如圖6所示。其中，標號為1的為200輪時的平均能量，標號為2的為500輪時的平均能量。從圖6所示的柱狀圖可以看出，從靠近Sink節點的Z1到遠離Sink節點的Z3，各區域中的平均能量基本持平。這表明本文采用的方法緩解了部分“能量空洞”問題。

圖6 UZCMR各區域在200、500輪時的網絡能量Fig.6 Network energy of UZCMR zones in 200 and 500

4 結束語

本文針對無線傳感器網絡中能量有限和“熱區”問題，提出了一種基于簇半徑優化的非均勻分區路由協議。通過逐層劃分區域的方式從靠近Sink節點的區域開始將網絡分成大小遞增的不等區域;在區域的簇頭競爭半徑中引入了最優簇半徑公式，將各區域進行合理大小的成簇，使能量消耗在各個區域中趨于平衡狀態。

仿真結果表明，通過改進，UZCMR路由協議平衡了網絡負載，緩解了“熱區”問題，延長了網絡生命周期。

［1］ Akyildiz I F，Su W，Sankarasubramanian Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40(8):102-114.

［2］ Soro S，Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥ Proceedings of the 5th International Workshop on Algorithms for Wireless，Mobile，Ad Hoc and Sensor Networks，Denver，CO，2005.

［3］ Gou H，Yoo Y.An energy balancing LEACH algorithm for wireless sensornetworks［C］∥ Seventh InternationalConference on Information Technology，IEEE，2010(12):822-823.

［4］ Heinzelman W R，Chandrakasan A，Balakrishman H.Energy-efficient communication protocol for wireless microsensor networks［C］∥Proceedings of Hawaii International Conference on System Sciences.Hawaii，2000.USA，2000:3005-3014.

［5］ Lindsey S，Raghavendra C.PEGASIS:Power-efficient gathering in sensor information systems［C］∥Proceeding of the IEEE Aerospace Conference on IEEE Aerospace and Electronic Systems Society，Montana，2002:1125-1130.

［6］ Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection［C］∥ 4th International Workshop on Mobile and Wireless Communications Network，Washington.DC，2002:368-372.

［7］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30(1):27-36.

［8］劉安豐，陽國軍，陳志剛.基于不等簇半徑輪換工作的傳感器網絡能量空洞避免研究［J］.通信學報，2010，31(1):2-8.

［9］ Farooq M O，Dogar a b，Shah G A.MR-LEACH:multi-hop routing with low energy adaptive clustering hierarchy［C］∥2010 Fourth International Conference on Sensor Technologies and Applications，2010.

［10］劉明，曹建農，陳貴海，等.EADEEG:能量感知的無線傳感器網絡數據收集協議［J］.軟件學報，2007，18(5):1092-1109.

Multi-hop Routing Protocol Based on Uneven Zoned Clustering for WSNs

Department of Computer，Communications and Interactive Systems，

School of Engineering and Built Environment，Glasgow Caledonian University2，Glasgow Scotland，U.K.G4 OBA)

To solve the problems in wireless sensor network，i.e.，limit node energy and energy hole，the uneven zoned clustering multi-hop routing(UZCMR)algorithm based on optimized cluster radius is proposed.In clustering，energy and geographic location of the node are fully taken into account.Through the method of“hierarchic partition”，the entire network is divided into several zones with Sink as the center.The nodes in each zone are clustered via optimized cluster radius.In addition，through adopting parameter，to make the scale of clusters near the node of Sink smaller than that of the clusters far from the Sink.Furthermore，the multi-hop routing with minimum communication cost is used.The experiments show that comparing with the LEACH protocol，the cluster heads formed by UZCMR are distributed evenly，thus the energy consumption of the nodes is effectively balanced，and the problem of energy hole is eased.The life cycle of network is obviously extended，and the adaptable scale of the protocol is expanded.

Wireless sensor network(WSN)Low energy adaptive clustering hierarchy(LEACH)protocolEnergy consumption Sink node Multi-hop routing protocol

signal strength indicator，RSSI)來選擇它要加入的簇，并告知相應的簇頭。簇頭收到簇內成員發送的信息后，創建時分多址(time division multiple access，TDMA)時刻表，通知每個節點何時開始傳輸數據。

TP273

A

陳笑(1988-)，女，2012年畢業于華東理工大學控制科學與工程專業，獲碩士學位;主要從事無線傳感器網絡路由協議方面的研究工作。

成為簇首的節點向周圍廣播信息，其他非簇頭節點根據收到信號的強度(