陳 笑 祁榮賓 錢 鋒 Huaglory Tianfield

(化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點實驗室(華東理工大學(xué))1，上海 200237;

WSNs基于非均勻分區(qū)成簇的多跳路由協(xié)議

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

(化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點實驗室(華東理工大學(xué))1，上海 200237;

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

無線傳感器網(wǎng)絡(luò)(WSN) 低功耗自適應(yīng)集簇分層型(LEACH)協(xié)議 能量消耗 Sink節(jié)點 多跳路由協(xié)議

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

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

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

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

0 引言

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

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

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

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

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

1 LEACH算法簡介

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

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

式中:P為網(wǎng)絡(luò)中簇頭占總節(jié)點的百分比;r為選舉輪數(shù);rmod(1/P)代表這一輪循環(huán)中當(dāng)選簇頭的節(jié)點個數(shù);G為這一輪循環(huán)中未當(dāng)選簇頭的節(jié)點集合。

在穩(wěn)定工作階段，節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)并傳送到簇頭，簇頭對數(shù)據(jù)進(jìn)行必要的融合處理后，發(fā)送到匯聚節(jié)點。為了避免額外的處理開銷，穩(wěn)定工作狀態(tài)一般持續(xù)相對較長的時間。在本輪工作完成之后，網(wǎng)絡(luò)將重新進(jìn)入下一輪的工作周期，完成兩個階段的過程。

基本LEACH協(xié)議存在如下問題。

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

②簇頭選舉由隨機(jī)數(shù)產(chǎn)生，這可能導(dǎo)致簇頭分布不合理和個數(shù)偏離期望值。

③簇頭與匯聚節(jié)點的單跳方式使得節(jié)點通信范圍有限，限制了網(wǎng)絡(luò)覆蓋范圍，不適用于大規(guī)模部署的網(wǎng)絡(luò)。

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

2 UZCMR路由協(xié)議

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

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

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

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

2.1 網(wǎng)絡(luò)模型

本文對無線傳感器網(wǎng)絡(luò)模型作以下假設(shè)。

①假設(shè)N個無線傳感器節(jié)點隨機(jī)均勻部署在二維平面上的一塊方形區(qū)域A內(nèi)，匯聚節(jié)點處于該區(qū)域范圍之外。

②傳感器節(jié)點同質(zhì)，能量有限，部署后無法補(bǔ)充能量，其信號傳輸功率有限，不一定能夠直接將信號發(fā)送至匯聚節(jié)點。

③所有傳感器節(jié)點同構(gòu)，在網(wǎng)絡(luò)中具有相同的重要性。

④網(wǎng)絡(luò)鏈路對稱，無線電發(fā)射功率可控，節(jié)點可以根據(jù)發(fā)送距離選擇無線電信號發(fā)射功率。

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

2.2 能耗模型

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

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

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

數(shù)據(jù)融合1 bit所消耗的能量為EDA。

2.3 網(wǎng)絡(luò)分層

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

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

劉明等人對單個簇的能耗進(jìn)行了分析，最優(yōu)簇半徑推導(dǎo)如下［10］:

式中:A為監(jiān)測區(qū)域的面積;N為區(qū)域內(nèi)節(jié)點數(shù)量;EDA為融合每比特數(shù)據(jù)所消耗的能量;εfs為功率放大所需能量。

本文將最優(yōu)簇半徑公式引入簇頭競爭半徑。

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

上一區(qū)域確定簇頭后，簇頭節(jié)點以半徑Ri廣播相關(guān)信息，包括節(jié)點ID、區(qū)域Zi、與匯聚節(jié)點的通信代價、傳感器網(wǎng)絡(luò)節(jié)點的平均能量(Eavg)。

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

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

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

在下一輪的簇頭競選中將Eavg廣播給傳感器網(wǎng)絡(luò)Z1的網(wǎng)絡(luò)區(qū)域，后面競選成為簇頭的節(jié)點依次廣播至網(wǎng)絡(luò)所有區(qū)域。

2.4 簇的建立

當(dāng)某區(qū)域中節(jié)點產(chǎn)生的0～1之間的隨機(jī)數(shù)小于

2.5 簇間通信

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

在簇頭競選過程中，簇頭Ni通過上一層 Nj向Sink每發(fā)送1 bit數(shù)據(jù)，整個網(wǎng)絡(luò)所消耗的總能量為Ccom，稱為節(jié)點Ni的通信代價。

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

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

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

簇頭Ni選擇通信代價最小的下一跳簇頭發(fā)送加入請求消息，得到確認(rèn)后，在本輪通過該簇頭進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

為了保證通信質(zhì)量，簇頭之間的通信采用載波監(jiān)聽多路訪問(carrier sense multiple access，CSMA)的MAC協(xié)議。這里假設(shè)簇間的數(shù)據(jù)冗余度較低，簇頭只是轉(zhuǎn)發(fā)其他簇的數(shù)據(jù)。

2.6 算法步驟

具體的算法步驟如下。

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

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

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

⑤網(wǎng)絡(luò)拓?fù)溥x擇下一跳節(jié)點:若Zi-1區(qū)域中存在簇頭剩余能量大于Eavg，那么選取該部分簇頭中通信代價最小的簇頭作為Zi中某簇頭的下一跳簇頭節(jié)點;否則，選取剩余能量最大的簇頭作為該簇頭的下一跳簇頭。

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

若普通節(jié)點均找到了所屬的簇，每個簇頭均找到了下一跳，則簇及多條路由建立階段至此結(jié)束，網(wǎng)絡(luò)進(jìn)入數(shù)據(jù)采集階段。

⑦本輪數(shù)據(jù)采集結(jié)束后，進(jìn)行重新分區(qū)與分簇，循環(huán)步驟①～⑦。

本文主要從以下幾個方面改進(jìn)了LEACH協(xié)議。

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

②成簇過程中引入了最優(yōu)簇半徑的概念。在最優(yōu)簇半徑的基礎(chǔ)上每個區(qū)域構(gòu)建不同規(guī)模的簇。距離Sink節(jié)點較近的簇規(guī)模較小。這不但使每個區(qū)域能構(gòu)建規(guī)模合理的簇，并且使靠近Sink節(jié)點的簇預(yù)留了能量來轉(zhuǎn)發(fā)相鄰簇頭的數(shù)據(jù)，緩解了能量空洞問題。

③簇頭節(jié)點選擇多跳路徑時，不僅考慮了通信代價，同時考慮了下一跳節(jié)點的剩余能量，從而均衡了網(wǎng)絡(luò)負(fù)載。

3 仿真試驗

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

表1 試驗參數(shù)Tab.1 Experimental parameters

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

UZCMR網(wǎng)絡(luò)分區(qū)圖如圖2所示，其中“*”代表Z1內(nèi)的節(jié)點，“。”代表Z2內(nèi)的節(jié)點，“+”代表Z3內(nèi)的節(jié)點。

圖2 網(wǎng)絡(luò)區(qū)域劃分圖Fig.2 Network zones division

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

從圖3可以看出，LEACH協(xié)議第一個節(jié)點死亡輪數(shù)是第254輪，EEUC是第776輪，而UZCMR協(xié)議出現(xiàn)第一個死亡節(jié)點輪數(shù)是1 217輪，比LEACH協(xié)議推遲了近1 000輪;而UZCMR協(xié)議最后一個節(jié)點死亡的輪數(shù)是1 710輪，EEUC是第1 092輪，LEACH是在第1 222輪。由此可知UZCMR由于引進(jìn)優(yōu)化的簇半徑公式，且采用分區(qū)成簇，各節(jié)點負(fù)載更為均衡，從而延長了網(wǎng)絡(luò)生命周期。

圖3 各種協(xié)議的網(wǎng)絡(luò)存活時間Fig.3 Network survival time of various protocols

每輪中各協(xié)議的總網(wǎng)絡(luò)剩余能量對比圖如圖4所示。

圖4 各協(xié)議的網(wǎng)絡(luò)剩余能量Fig.4 Network residual energy of various protocols

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

UZCMR在不同簇半徑下的網(wǎng)絡(luò)生命周期的對比圖如圖5所示。

圖5 簇半徑vs網(wǎng)絡(luò)生命周期Fig.5 Cluster radius vs.network life cycle

本文提取所有節(jié)點完全死亡時和還存活10個節(jié)點時的數(shù)據(jù)一起做分析比較。從圖5可以看出，在本文的環(huán)境下，簇半徑為20 m時網(wǎng)絡(luò)生命周期達(dá)到最大。當(dāng)簇半徑過大時，節(jié)點由于遠(yuǎn)距離通信會造成能量浪費，驗證了本文改進(jìn)的結(jié)果。UZCMR通過優(yōu)化的簇半徑，節(jié)省了網(wǎng)絡(luò)能量消耗。

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

圖6 UZCMR各區(qū)域在200、500輪時的網(wǎng)絡(luò)能量Fig.6 Network energy of UZCMR zones in 200 and 500

4 結(jié)束語

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

仿真結(jié)果表明，通過改進(jìn)，UZCMR路由協(xié)議平衡了網(wǎng)絡(luò)負(fù)載，緩解了“熱區(qū)”問題，延長了網(wǎng)絡(luò)生命周期。

［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］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機(jī)學(xué)報，2007，30(1):27-36.

［8］劉安豐，陽國軍，陳志剛.基于不等簇半徑輪換工作的傳感器網(wǎng)絡(luò)能量空洞避免研究［J］.通信學(xué)報，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］劉明，曹建農(nóng)，陳貴海，等.EADEEG:能量感知的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議［J］.軟件學(xué)報，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)來選擇它要加入的簇，并告知相應(yīng)的簇頭。簇頭收到簇內(nèi)成員發(fā)送的信息后，創(chuàng)建時分多址(time division multiple access，TDMA)時刻表，通知每個節(jié)點何時開始傳輸數(shù)據(jù)。

TP273

A

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

成為簇首的節(jié)點向周圍廣播信息，其他非簇頭節(jié)點根據(jù)收到信號的強(qiáng)度(