孫彥清，彭艦，劉唐,2，陳曉海

（1. 四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都 610065；2. 四川師范大學(xué) 基礎(chǔ)教學(xué)學(xué)院，四川 成都 610068）

1 引言

無(wú)線傳感器網(wǎng)絡(luò)是由部署在農(nóng)田、森林、戰(zhàn)場(chǎng)等監(jiān)測(cè)區(qū)域內(nèi)大量廉價(jià)的微型傳感器節(jié)點(diǎn)和一個(gè)信息收集基站（sink）組成，通過(guò)無(wú)線通信的方式形成一個(gè)多跳的自組織分布式網(wǎng)絡(luò)系統(tǒng)。作為一種新的信息獲取方式和處理模式，被廣泛應(yīng)用于軍事國(guó)防、環(huán)境監(jiān)測(cè)、智能家居、醫(yī)療衛(wèi)生等領(lǐng)域[1]。

傳感器節(jié)點(diǎn)一般采用能量十分有限的電池，通常運(yùn)行在惡劣甚至危險(xiǎn)的偏遠(yuǎn)環(huán)境中，一旦部署就不能再充電和電源更換，因此如何設(shè)計(jì)有效的策略控制節(jié)點(diǎn)的能量消耗成為傳感器網(wǎng)絡(luò)研究的核心問(wèn)題[2]。為了達(dá)到節(jié)省能耗的目的，許多基于成簇的層次型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)被提出[3~5]。分簇優(yōu)化了數(shù)據(jù)的傳輸數(shù)量，減少了節(jié)點(diǎn)對(duì)基站的數(shù)據(jù)發(fā)送次數(shù)，能夠有效減少網(wǎng)絡(luò)冗余信息，降低能量消耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

早期的成簇路由算法大多采用單跳通信方式（簇頭節(jié)點(diǎn)收集簇內(nèi)成員節(jié)點(diǎn)的數(shù)據(jù)，進(jìn)行壓縮、融合后直接和基站通信，如LEACH[6]），但存在網(wǎng)絡(luò)部署面積受限、擴(kuò)展性差、離基站越遠(yuǎn)的簇頭能量消耗越快等缺陷。隨著研究的深入，分簇網(wǎng)絡(luò)采取多跳方式來(lái)節(jié)省能量，但也存在嚴(yán)重缺陷：距離基站越近的簇頭需要轉(zhuǎn)發(fā)的數(shù)據(jù)任務(wù)越多，消耗的能量越多，越容易因能量耗盡而過(guò)早失效。如果靠近基站的節(jié)點(diǎn)成塊死亡，則會(huì)導(dǎo)致網(wǎng)絡(luò)中數(shù)據(jù)無(wú)法成功傳輸，網(wǎng)絡(luò)壽命降低。因此，如何均衡簇間能量消耗，達(dá)到網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)載均衡是成簇路由協(xié)議的研究熱點(diǎn)。

LEACH是最早提出的一種均勻分簇路由協(xié)議，通過(guò)周期性地等概率隨機(jī)選擇簇頭來(lái)構(gòu)造出大小相等的簇，在理論上達(dá)到了簇內(nèi)能耗平衡，但這種局部能耗均衡會(huì)造成遠(yuǎn)離基站的簇頭能量先耗盡，從而造成了能量空洞。EEDRCP[7]是對(duì)LEACH改進(jìn)的一種雙輪成簇協(xié)議，在簇頭選取算法中引入剩余能量參數(shù)，形成混合型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

EEUC[8]通過(guò)控制簇頭的競(jìng)爭(zhēng)半徑來(lái)調(diào)節(jié)簇規(guī)模大小，使得靠近基站的簇規(guī)模相對(duì)較小，這樣簇頭因收集簇內(nèi)數(shù)據(jù)而消耗的能量就會(huì)相對(duì)減少，從而簇頭就會(huì)擁有更多的能量來(lái)進(jìn)行路由轉(zhuǎn)發(fā)；同時(shí)在選擇路由節(jié)點(diǎn)時(shí)，不僅考慮候選路由與基站的距離，還參考其剩余能量，這種非均勻成簇路由協(xié)議在一定程度上緩解了簇頭能量消耗不均衡的問(wèn)題。ACOUC[9]在 EEUC 的非均勻分簇協(xié)議的基礎(chǔ)上對(duì)算法進(jìn)行了優(yōu)化，首輪所有節(jié)點(diǎn)參與簇頭競(jìng)選、后續(xù)輪簇內(nèi)調(diào)整，利用基于定向擴(kuò)散的蟻群優(yōu)化(ARAWSN)算法進(jìn)行路徑優(yōu)化和動(dòng)態(tài)路由調(diào)整，以建立從簇首到匯聚點(diǎn)綜合能耗最小的多跳路由。

CEB-UC[10]是一種基于分區(qū)能耗均衡的非均勻分簇算法，將網(wǎng)絡(luò)合理分區(qū)，使得靠近基站的分區(qū)內(nèi)的簇?cái)?shù)量較多，各簇內(nèi)節(jié)點(diǎn)數(shù)目較少；遠(yuǎn)離基站的分區(qū)內(nèi)的簇?cái)?shù)量較少，各簇內(nèi)的節(jié)點(diǎn)數(shù)目較多，從而保證承擔(dān)數(shù)據(jù)中繼轉(zhuǎn)發(fā)任務(wù)的簇頭節(jié)點(diǎn)能節(jié)約所在簇內(nèi)的通信開(kāi)銷，供簇間數(shù)據(jù)轉(zhuǎn)發(fā)使用，以優(yōu)化網(wǎng)絡(luò)各節(jié)點(diǎn)的能量消耗。DEBUC[10]采用基于時(shí)間的簇頭競(jìng)爭(zhēng)算法，廣播時(shí)間取決于候選簇頭的剩余能量和其鄰居節(jié)點(diǎn)的剩余能量；同時(shí)，通過(guò)控制候選簇頭的競(jìng)爭(zhēng)范圍，使得距離基站較近的簇的幾何尺寸較小，以均衡網(wǎng)絡(luò)中不同位置節(jié)點(diǎn)之間的簇內(nèi)和簇間通信能耗；DEBUC采用簇間多跳路由，運(yùn)用貪婪算法選擇其中繼節(jié)點(diǎn)，有效地延長(zhǎng)了網(wǎng)絡(luò)壽命。

本文提出了一種基于動(dòng)態(tài)分區(qū)負(fù)載均衡的分布式成簇路由算法。首先利用動(dòng)態(tài)非均勻分區(qū)保證網(wǎng)絡(luò)各個(gè)區(qū)域的能耗均衡性，使得距離基站較近的區(qū)具有較小的幾何尺寸；根據(jù)節(jié)點(diǎn)的歷史能耗因子和到基站的距離競(jìng)選區(qū)頭，使得剩余能量較高并且靠近基站的節(jié)點(diǎn)當(dāng)選區(qū)頭。然后綜合考慮節(jié)點(diǎn)的剩余能量因子和“綜合距離因子”進(jìn)行區(qū)內(nèi)成簇，使得剩余能量越多并且越靠近區(qū)頭的節(jié)點(diǎn)出任簇頭的概率越大。采用簇內(nèi)單跳通信、簇頭與區(qū)頭直接通信和區(qū)間多跳的路由策略，簇頭只負(fù)責(zé)收集簇內(nèi)數(shù)據(jù)并進(jìn)行融合，區(qū)頭負(fù)責(zé)收集簇頭數(shù)據(jù)并根據(jù)轉(zhuǎn)發(fā)策略選擇中繼節(jié)點(diǎn)。這種區(qū)頭和簇首共同承擔(dān)數(shù)據(jù)傳輸?shù)耐ㄐ欧绞接行Ч?jié)省了單個(gè)節(jié)點(diǎn)的能量、均衡了網(wǎng)絡(luò)能耗，實(shí)驗(yàn)結(jié)果表明，與LEACH、 EEUC和DEBUC協(xié)議相比，所提協(xié)議能夠顯著延長(zhǎng)網(wǎng)絡(luò)的生存周期。

2 網(wǎng)絡(luò)與能耗模型

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

[11]，本文對(duì)無(wú)線傳感器網(wǎng)絡(luò)作如下假設(shè)：

1) 節(jié)點(diǎn)能量可異構(gòu)，網(wǎng)絡(luò)中初始總能量 Etotal固定，節(jié)點(diǎn)可以獲取自身的當(dāng)前能量Er；

2) 每個(gè)節(jié)點(diǎn)有唯一的 ID，可獲知自己的坐標(biāo)信息。都能擔(dān)任區(qū)頭、簇頭或者普通節(jié)點(diǎn)；

3) 節(jié)點(diǎn)通信功率可以自由調(diào)節(jié)，不同節(jié)點(diǎn)能夠在通信范圍內(nèi)相互通信，通過(guò)接收信號(hào)的強(qiáng)度計(jì)算出通信節(jié)點(diǎn)之間的距離；

4) 每個(gè)節(jié)點(diǎn)獨(dú)立工作，即每個(gè)節(jié)點(diǎn)的工作均不受其他節(jié)點(diǎn)影響；

5) 通過(guò)數(shù)據(jù)融合技術(shù)減少數(shù)據(jù)傳輸任務(wù)；

6) sink節(jié)點(diǎn)具有較強(qiáng)的計(jì)算、存儲(chǔ)能力，且能量無(wú)限制。

2.2 能耗模型

本文采用簡(jiǎn)單能量消耗模型[5]，忽略節(jié)點(diǎn)在計(jì)算、存儲(chǔ)等過(guò)程中的能量消耗，僅計(jì)算通信能耗。在傳輸l bit信息經(jīng)過(guò)距離d的過(guò)程中，發(fā)送端能量消耗為

接收端的能量消耗為

其中，d0為一閾值，本文定義為 87 m。若發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的傳輸距離小于 d0，發(fā)送方發(fā)送數(shù)據(jù)的能量消耗與距離的平方成正比，否則成4次方正比。Eelec是每比特?cái)?shù)據(jù)在發(fā)送電路和接收電路消耗的能量，εfsd2和εmpd4是發(fā)送每比特?cái)?shù)據(jù)放大器的能量消耗。

2.3 數(shù)據(jù)融合模型

UCDP通過(guò)數(shù)據(jù)融合技術(shù)減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，達(dá)到節(jié)約網(wǎng)絡(luò)能量的目的。由于不同區(qū)域中數(shù)據(jù)有較大的差異，在模擬實(shí)驗(yàn)中不考慮區(qū)域間的數(shù)據(jù)融合。假設(shè)區(qū)內(nèi)的數(shù)據(jù)融合模型為：簇頭接收每個(gè)節(jié)點(diǎn)發(fā)送的l bit數(shù)據(jù)，壓縮為l bit數(shù)據(jù)；區(qū)頭接收每個(gè)簇頭發(fā)送的l bit數(shù)據(jù)，壓縮為l bit數(shù)據(jù)。數(shù)據(jù)融合能耗設(shè)定為DEΛ=5 nJ/bit。

3 基于動(dòng)態(tài)分區(qū)的非均勻成簇（UCDP）路由協(xié)議

UCDP是一個(gè)分布式的并行成簇算法，具有良好的擴(kuò)充性，算法采用輪循環(huán)機(jī)制，每輪分為3個(gè)階段。1）動(dòng)態(tài)分區(qū)階段：首先通過(guò)節(jié)點(diǎn)歷史能耗因子和與距離基站的距離對(duì)網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)非均勻分區(qū)，使得剩余能量較高的節(jié)點(diǎn)當(dāng)選區(qū)頭并且距離基站較近的區(qū)域面積較小。2）區(qū)內(nèi)成簇階段：每個(gè)區(qū)內(nèi)進(jìn)行非均勻成簇，區(qū)內(nèi)節(jié)點(diǎn)綜合考慮自身與區(qū)頭的距離以及自身與基站的距離計(jì)算出“復(fù)合距離因子”，保證節(jié)點(diǎn)的數(shù)據(jù)傳輸距離最優(yōu)；同時(shí)參考節(jié)點(diǎn)的剩余能量因子來(lái)競(jìng)選簇頭；既避免了能量消耗過(guò)低的節(jié)點(diǎn)擔(dān)任簇頭，又最大限度地降低了簇頭的通信傳輸能耗。3）路由轉(zhuǎn)發(fā)階段[12]：分為簇內(nèi)通信、簇首與區(qū)頭通信、區(qū)頭與匯聚點(diǎn)通信三部分，簇內(nèi)通信采用單跳的方式，容易實(shí)施；同一個(gè)區(qū)內(nèi)的所有簇首都采用單跳的方式與所屬區(qū)頭通信，只有和基站距離小于一定范圍的簇首才將數(shù)據(jù)直接發(fā)送給基站；區(qū)頭根據(jù)能量消耗因子建立區(qū)間多跳路由。

下面給出與UCDP算法相關(guān)的一些定義。

定義 1 能量消耗因子。能量消耗因子e _ cos tkr表明在第r-1輪工作周期內(nèi)節(jié)點(diǎn)k所消耗的能量與區(qū)域內(nèi)節(jié)點(diǎn)平均消耗能量的比值，

定義2 剩余能量因子。剩余能量因子 W (Ekr)表明節(jié)點(diǎn)此時(shí)的剩余能量和區(qū)域平均剩余能量的關(guān)系，

定義3 復(fù)合距離因子。復(fù)合距離因子D(v)表明節(jié)點(diǎn)此時(shí)的位置與匯聚點(diǎn)和區(qū)頭的關(guān)系，0≤D(v)≤ 1。

3.1 動(dòng)態(tài)分區(qū)

UCDP算法在每輪數(shù)據(jù)傳輸周期之前首先對(duì)網(wǎng)絡(luò)進(jìn)行合理的動(dòng)態(tài)非均勻分區(qū)，有效均衡網(wǎng)絡(luò)的整體負(fù)載。在UCDP中，區(qū)頭的任務(wù)負(fù)擔(dān)較重，不僅需要管理區(qū)內(nèi)多個(gè)簇頭，還要融合各個(gè)簇頭收集的數(shù)據(jù)，再將處理后的數(shù)據(jù)發(fā)送給基站，因此算法以區(qū)域內(nèi)節(jié)點(diǎn)的歷史能耗因子為主要的競(jìng)選依據(jù)。所有參與區(qū)頭競(jìng)爭(zhēng)的候選區(qū)頭節(jié)點(diǎn)都保存一張鄰居節(jié)點(diǎn)信息表，如表1所示。

表1 候選區(qū)頭鄰居節(jié)點(diǎn)信息

首先，每個(gè)候選區(qū)頭節(jié)點(diǎn)廣播 Area_Vie_Msg報(bào)文，告知其他候選節(jié)點(diǎn)自身的 ID號(hào)、當(dāng)前剩余能量Er和競(jìng)爭(zhēng)范圍Rvie，通過(guò)廣播能夠獲知其他鄰居節(jié)點(diǎn)的信息集合。

結(jié)合Younis提出的成簇思想[9]，在UCDP算法中對(duì)LEACH算法的T(n)公式做出改進(jìn)

其中，PRH是節(jié)點(diǎn)競(jìng)選區(qū)頭的概率，r是當(dāng)前循環(huán)進(jìn)行的輪數(shù)，G為最近1/Pk輪中未成為區(qū)頭的節(jié)點(diǎn)集合。在 T(n)中加入 e _ costkr作為影響因子，使歷史能耗較低的節(jié)點(diǎn)優(yōu)先當(dāng)選區(qū)頭。新的閾值公式T(n)new有如下特性：1)當(dāng)選過(guò)候選區(qū)頭的節(jié)點(diǎn)在接下來(lái)的 1/Pk輪循環(huán)中將不能成為區(qū)頭；2)未當(dāng)選過(guò)候選區(qū)頭的剩余節(jié)點(diǎn)當(dāng)選為區(qū)頭的概率增大；3)未成為區(qū)頭的其他節(jié)點(diǎn)根據(jù)接收到廣播信號(hào)的強(qiáng)弱來(lái)決定加入合適的分區(qū)。這樣，通過(guò)T(n)new能夠?qū)崿F(xiàn)對(duì)傳感器網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)定向分割的目的。

假設(shè)傳感器網(wǎng)絡(luò)被分隔成M個(gè)區(qū)域，設(shè)在第r-1輪，對(duì)任意分區(qū)的集合中有個(gè)節(jié)點(diǎn)。其中，傳感器節(jié)點(diǎn)在此輪數(shù)據(jù)傳輸開(kāi)始時(shí)的能量為 Ekr-2，在第r -1輪成簇結(jié)束時(shí)能量為 Ekr-1。由定義1給出節(jié)點(diǎn)k的能量消耗因子為

為了有效保證網(wǎng)絡(luò)每輪分割過(guò)程中各個(gè)分區(qū)能耗的均衡性，算法引入了輪轉(zhuǎn)因子的概念：

當(dāng) r ounds(k,r)>0時(shí)，則節(jié)點(diǎn)k提前 r ounds(k,r)輪進(jìn)入集合 G；當(dāng) r ounds(k,r)=0時(shí)，則當(dāng)前輪轉(zhuǎn)狀態(tài)不變；當(dāng) r ounds(k,r)<0時(shí)，則該節(jié)點(diǎn)延遲rounds(k,r)輪進(jìn)入集合G。

由于距離基站越近的區(qū)頭需要承擔(dān)的數(shù)據(jù)傳輸任務(wù)越重，能量耗盡而失效的概率也越大。為了避免這種現(xiàn)象，算法希望讓靠近基站的區(qū)頭的成員較少，減少區(qū)頭因處理區(qū)內(nèi)數(shù)據(jù)而消耗的能量。算法為每個(gè)候選區(qū)頭設(shè)置一個(gè)競(jìng)爭(zhēng)半徑Rvie，隨著候選區(qū)頭到基站距離的減小，Rvie隨之減小。假設(shè)候選區(qū)頭的最大競(jìng)爭(zhēng)半徑為 Ro，則候選區(qū)頭 i的 Rvie為

其中，dmax代表網(wǎng)絡(luò)中節(jié)點(diǎn)到基站的最大距離，dmin代表最小距離，d(I, BS) 是節(jié)點(diǎn)i 到基站的距離，c是0~1之間的用于控制Rvie取值范圍的常數(shù)。

當(dāng)選為區(qū)頭的節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播獲勝消息Area_Msg時(shí)，申明自己成為區(qū)頭，并默認(rèn)區(qū)頭為區(qū)號(hào)，普通節(jié)點(diǎn)選擇接收信號(hào)強(qiáng)度最大的區(qū)頭并發(fā)送Join_Area_Msg請(qǐng)求加入，每輪分區(qū)后區(qū)頭節(jié)點(diǎn)負(fù)責(zé)對(duì)本區(qū)節(jié)點(diǎn)信息的更新管理，網(wǎng)絡(luò)動(dòng)態(tài)分區(qū)結(jié)束。利用輪轉(zhuǎn)因子的概念，通過(guò)引入剩余能量因子改進(jìn) T (n)new閾值，能夠?qū)?jié)點(diǎn)擔(dān)任區(qū)頭的輪轉(zhuǎn)周期進(jìn)行動(dòng)態(tài)調(diào)整，有效地保證了傳感器網(wǎng)絡(luò)每輪分割過(guò)程中各個(gè)分區(qū)能耗的均衡性。

3.2 區(qū)內(nèi)非均勻成簇

區(qū)內(nèi)成簇階段包括簇頭選舉和簇的形成。

1) 簇頭選舉

為實(shí)現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載均衡，要盡可能增加分區(qū)內(nèi)相對(duì)剩余能量較高的節(jié)點(diǎn)出任簇頭的概率。首先，每個(gè)候選簇頭廣播Cluster_Vie_Msg報(bào)文，告知其他候選節(jié)點(diǎn)自身的 ID號(hào)、當(dāng)前剩余能量、節(jié)點(diǎn)與區(qū)頭的距離和節(jié)點(diǎn)與基站的距離。根據(jù)定義2，節(jié)點(diǎn)k在第r輪成簇之前的剩余能量因子 W (Ekr)計(jì)算公式為

其中，傳感器節(jié)點(diǎn) k的初始能量為 Ek0，當(dāng)r =1（首輪）時(shí)，節(jié)點(diǎn)k還沒(méi)有任何能量損耗，W (Ekr)為1；當(dāng)r>1時(shí)， W (Ekr)越大，說(shuō)明該節(jié)點(diǎn)在此時(shí)的相對(duì)剩余能量越高。 W (Ekr)還可以適用于初始能量不同的異構(gòu)網(wǎng)絡(luò)，如果此時(shí)有2個(gè)節(jié)點(diǎn)的當(dāng)前剩余能量值相等，則意味著初始能量高的節(jié)點(diǎn)能量消耗更快，那么初始能量高的節(jié)點(diǎn)的剩余能量因子會(huì)較小。

節(jié)點(diǎn)k到區(qū)頭RHi的距離越小，則k作為簇頭后，簇頭與區(qū)頭之間的通信能耗越小，同理若k到基站的距離越小，數(shù)據(jù)傳輸?shù)哪芎囊苍叫?。根?jù)自由空間能量模型可知，距離的平方直接影響能量消耗的大小，根據(jù)定義 3，給出復(fù)合距離因子可以表示為

為了實(shí)現(xiàn)分區(qū)內(nèi)節(jié)點(diǎn)的負(fù)載均衡，要盡可能增加相對(duì)剩余能量大的節(jié)點(diǎn)出任簇頭的概率；同時(shí)加入綜合距離因子使得簇頭盡量靠近區(qū)頭和基站，盡量減少數(shù)據(jù)傳輸消耗的能量。

節(jié)點(diǎn)k成為簇頭的概率由式(9)計(jì)算。

其中，α、β為調(diào)節(jié)剩余能量因子、綜合距離因子在節(jié)點(diǎn)競(jìng)爭(zhēng)簇頭時(shí)所占權(quán)重的概率因子，且α+β=1。

利用式（9），節(jié)點(diǎn) k和它的鄰居節(jié)點(diǎn)分別計(jì)算出自身的簇頭當(dāng)選概率，并通過(guò)一次握手交換出對(duì)方的概率值。鄰居節(jié)點(diǎn)在收到的所有概率值中挑選出擁有最大概率值的節(jié)點(diǎn)成為簇頭，并通知相應(yīng)的節(jié)點(diǎn)（若沒(méi)有得到更大的概率值信息，則該節(jié)點(diǎn)宣告自己成為簇頭）。選舉結(jié)束后，當(dāng)選簇頭向其通信范圍內(nèi)的成員發(fā)送Head_Msg報(bào)文，宣布成為簇頭。

2) 簇的形成

簇頭確定之后，便在所屬分區(qū)內(nèi)廣播 Cluster_Msg報(bào)文，等待其他普通節(jié)點(diǎn)的加入。普通節(jié)點(diǎn)根據(jù)接收消息的信號(hào)強(qiáng)弱判斷發(fā)送方和接收方的距離，優(yōu)先選擇通信代價(jià)最小的簇頭加入，即發(fā)送消息需要經(jīng)過(guò)的距離最短的簇頭。

普通節(jié)點(diǎn)i根據(jù)距離引力[13]F(i，CHi，r)來(lái)確定加入哪個(gè)簇，CHi為簇頭，距離引力表示節(jié)點(diǎn)不僅考慮簇頭的剩余能量大小，同時(shí)還要考慮與簇頭的距離和與區(qū)頭的距離。

從圖1中可以看出，越是靠近基站的區(qū)，其物理面積越??；分區(qū)內(nèi)的簇頭相對(duì)靠近區(qū)頭和基站。簇形成階段之后，算法進(jìn)入數(shù)據(jù)通信階段—路由傳輸。

圖1 UCDP協(xié)議基本原理

3.3 路由傳輸

UCDP采用簇內(nèi)單跳通信、簇頭與區(qū)頭直接通信和區(qū)間多跳通信的數(shù)據(jù)傳輸方式。

簇頭首先收集簇成員的數(shù)據(jù)并進(jìn)行融合，然后進(jìn)行數(shù)據(jù)發(fā)送，比較由簇頭直接發(fā)送到基站的距離和由區(qū)頭轉(zhuǎn)發(fā)到基站的距離，選擇綜合距離較短的方式進(jìn)行發(fā)送。如果簇頭CHi滿足，數(shù)據(jù)由簇頭直接發(fā)送給基站；滿足就由簇頭交給區(qū)頭發(fā)送。其中，d(CHi, BS)表示簇頭CHi與基站的距離，d(RHm, BS)表示區(qū)頭RHm與基站的距離，DTD-MAX為閾值。

區(qū)頭到基站的距離小于 DTD-MAX，則它可以直接發(fā)送數(shù)據(jù)到基站，否則區(qū)頭只能以多跳通信的方式將數(shù)據(jù)發(fā)送至基站。下面通過(guò)定理1來(lái)討論區(qū)頭的路由轉(zhuǎn)發(fā)策略。

首先給出區(qū)頭RHm的路由候選集合為

定理1 對(duì)剩余能量為Ecur_m的區(qū)頭i，共有Z′個(gè)路由候選區(qū)頭，假設(shè)其中的任意區(qū)頭z的剩余能量為Ecur_z，由z到基站的消息發(fā)送距離dz_o與節(jié)點(diǎn)i的當(dāng)前距離為dm_z可知，如果區(qū)頭z滿足

則區(qū)頭m通過(guò)z轉(zhuǎn)發(fā)數(shù)據(jù)到基站將比區(qū)頭m直接發(fā)送消息到基站更節(jié)省網(wǎng)絡(luò)能量。

證明 設(shè)區(qū)頭m為了傳輸l bit的數(shù)據(jù)，根據(jù)文獻(xiàn)[7]的能量模型，所需要的能量消耗為

設(shè)區(qū)頭m有Z′個(gè)路由候選區(qū)頭，若m通過(guò)其中的候選區(qū)頭z傳輸消息j到基站，則能量消耗分為三部分：兩區(qū)頭發(fā)送消息所消耗的能量、區(qū)頭 z接收消息所消耗的能量以及消息j再?gòu)膠發(fā)送到基站的能量消耗。其中，消息j從m發(fā)送到z的能量消耗為

消息j再?gòu)膮^(qū)頭z發(fā)送到基站的能量消耗為

因此，通過(guò)區(qū)頭z轉(zhuǎn)發(fā)消息j的總能量消耗為

若Em_z(l)占區(qū)頭i和區(qū)頭z剩余能量之和的比例小于ETx_mo(l，di_o)占區(qū)頭m當(dāng)前剩余能量的比例，即滿足式(14)，則消息l通過(guò)轉(zhuǎn)發(fā)的方式傳至基站，更節(jié)省網(wǎng)絡(luò)能量。

結(jié)論得證。

為了簡(jiǎn)化問(wèn)題分析，簡(jiǎn)單假設(shè)能量消耗與距離的平方成正比，則Em_z(l)可以表示為

由分析可知，dm_z2+dz_o2決定了能量消耗的多少，則在選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，優(yōu)先選擇dm_z2+dz_o2最小的區(qū)頭作為下一跳路由節(jié)點(diǎn)。

路由算法偽代碼如圖2所示。

圖2 路由算法偽代碼

動(dòng)態(tài)非均勻分區(qū)保證了網(wǎng)絡(luò)各個(gè)分區(qū)的能耗均衡性；基于綜合距離因子和剩余能量因子的成簇算法保證了簇頭的通信距離最小化，并提高了剩余能量多的節(jié)點(diǎn)出任簇頭的概率，因此，UCDP算法能夠?qū)崿F(xiàn)網(wǎng)絡(luò)負(fù)載均衡性和能量有效性。

4 算法分析

定理2 在UCDP算法中，網(wǎng)絡(luò)中廣播的消息量復(fù)雜度為O(N)。

證明 在UCDP算法中，在區(qū)頭競(jìng)選階段，有NR個(gè)候選區(qū)頭參與競(jìng)選，共廣播NR條Area_Vie_Msg消息，競(jìng)選成功的候選區(qū)頭發(fā)送獲勝消息，假

其中，dm_z為m與z的距離。區(qū)頭z接收消息所消耗的能量為設(shè)共有R個(gè)區(qū)頭，則一共廣播R條Area_Msg消息，而其他的區(qū)成員發(fā)送N-R條Join_Area_Msg消息；有NC個(gè)候選簇頭參與競(jìng)選，共廣播NC條Cluster_Vie_Msg消息，競(jìng)選成功的候選簇頭發(fā)送獲勝消息，假設(shè)共有C個(gè)簇頭，則一共廣播C條Cluster_Msg消息，而其他的簇成員發(fā)送N-C-R條Join_Cluster_Msg消息。因此，網(wǎng)絡(luò)在分區(qū)階段和成簇階段中總的消息開(kāi)銷為

NR+R+N-R+NC+C+N-R-C=(R+C-2)N-R (19)所以，UCDP算法的消息量復(fù)雜度為O(N)。

5 仿真與實(shí)驗(yàn)

為了評(píng)估算法的性能，利用NS-2在相同條件下仿真LEACH、EEUC、DEBUC和本文算法，并進(jìn)行多項(xiàng)性能的比較。

5.1 仿真環(huán)境

本文使用NS-2進(jìn)行仿真模擬，實(shí)驗(yàn)環(huán)境如下：1 600個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布于400 m×400 m的正方形區(qū)域，假設(shè)匯聚節(jié)點(diǎn)（sink）位于區(qū)域中心。表2展示了實(shí)驗(yàn)采用的多種參數(shù)。

表2 網(wǎng)絡(luò)參數(shù)

5.2 簇首特征

根據(jù)前面的分析可知，算法的分區(qū)個(gè)數(shù)由參數(shù) Ro和c共同決定。圖2顯示了當(dāng)c取2個(gè)不同vie的值時(shí)，區(qū)頭數(shù)目和 Rovie之間的關(guān)系。從圖 3可以看出，c=0.5時(shí)的區(qū)頭數(shù)目要多于c=0時(shí)的區(qū)頭數(shù)目，同時(shí)隨著區(qū)頭競(jìng)爭(zhēng)半徑的減小，分區(qū)數(shù)目不斷增多。

圖3 區(qū)頭數(shù)目和最大競(jìng)爭(zhēng)半徑關(guān)系

圖4 說(shuō)明了算法的穩(wěn)定性，在網(wǎng)絡(luò)拓?fù)涔潭ǖ那闆r下，衡量一個(gè)分簇協(xié)議是否穩(wěn)定的標(biāo)準(zhǔn)是看生成的簇首數(shù)目是否一致。分別從 LEACH算法、DEBUC算法和UCDP算法的模擬過(guò)程中隨機(jī)選出100輪，統(tǒng)計(jì)每個(gè)協(xié)議簇首個(gè)數(shù)的分布情況，由圖4可知，LEACH算法的簇首數(shù)目變化最大，這是因?yàn)長(zhǎng)EACH算法只采用了隨機(jī)數(shù)和閾值的機(jī)制競(jìng)選簇首，因此簇首數(shù)目的波動(dòng)范圍最大。由于DEBUC算法和本文算法都采用了局部競(jìng)爭(zhēng)的方法，因此DEBUC算法的簇首數(shù)目相對(duì)集中，本文算法的區(qū)頭數(shù)目和簇首數(shù)目也相對(duì)集中。值得注意的是，本文算法生成的簇首數(shù)目明顯較多，這是因?yàn)閁CDP算法通過(guò)動(dòng)態(tài)劃分大小非均勻的區(qū)，使得靠近基站的地方產(chǎn)生更多幾何尺寸較小的區(qū)，再通過(guò)區(qū)內(nèi)成簇，簇首個(gè)數(shù)就相對(duì)增多?？傊?，UCDP算法生成了數(shù)目穩(wěn)定的分區(qū)和簇首，具有良好的可靠性。

5.3 生存周期

UCDP算法的核心思想是通過(guò)動(dòng)態(tài)分區(qū)來(lái)均衡網(wǎng)絡(luò)能耗，現(xiàn)在通過(guò)比較4種協(xié)議的網(wǎng)絡(luò)生存時(shí)間來(lái)驗(yàn)證本文算法的有效性。文獻(xiàn)[14]定義網(wǎng)絡(luò)節(jié)點(diǎn)死亡 10%以上時(shí)為網(wǎng)絡(luò)失效，從圖 5可以看出，UCDP算法相對(duì)于其他3種算法有較長(zhǎng)的網(wǎng)絡(luò)生存時(shí)間，由于本文算法采用區(qū)頭與簇首共同協(xié)作的通信方式，減緩了每個(gè)節(jié)點(diǎn)的任務(wù)負(fù)擔(dān)，均衡了網(wǎng)絡(luò)的整體能耗，因此，UCDP算法的第一個(gè)節(jié)點(diǎn)死亡時(shí)間和網(wǎng)絡(luò)失效時(shí)間都明顯晚于其他3種協(xié)議。

5.4 能量效率

圖6對(duì)比了4種協(xié)議的網(wǎng)絡(luò)總能耗隨時(shí)間變化的情況。從圖中可以看出，UCDP算法的能量消耗速度明顯小于其他3種協(xié)議，當(dāng)DEBUC算法中網(wǎng)絡(luò)失效時(shí)，此時(shí)網(wǎng)絡(luò)能量為61 J，而UCDP算法網(wǎng)絡(luò)失效時(shí)，網(wǎng)絡(luò)剩余能量?jī)H為17 J。說(shuō)明UCDP算法有更長(zhǎng)的網(wǎng)絡(luò)存活時(shí)間，能夠有效平衡節(jié)點(diǎn)間的能耗，具有更好的網(wǎng)絡(luò)監(jiān)控質(zhì)量。

圖4 簇頭數(shù)量分布

圖5 存活節(jié)點(diǎn)與生存周期關(guān)系

圖6 網(wǎng)絡(luò)剩余能量與生存周期關(guān)系

圖7 顯示了4種協(xié)議的網(wǎng)絡(luò)節(jié)點(diǎn)平均能量值隨時(shí)間變化的情況，UCDP算法的網(wǎng)絡(luò)節(jié)點(diǎn)能量均值一直都比其他3種協(xié)議的高，說(shuō)明UCDP算法在能量均衡方面有較好的性能。

圖7 節(jié)點(diǎn)平均剩余能量與生存周期關(guān)系

6 結(jié)束語(yǔ)

本文提出了一種新穎的基于動(dòng)態(tài)分區(qū)的傳感器網(wǎng)絡(luò)成簇路由協(xié)議，核心思想是利用一個(gè)能量均衡的非均勻分區(qū)算法將網(wǎng)絡(luò)合理分區(qū)，以緩解多跳路由中的“熱區(qū)”現(xiàn)象；協(xié)議利用區(qū)頭與簇頭共同協(xié)作的通信方式，以均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗；通過(guò)簇內(nèi)通信、區(qū)內(nèi)通信和區(qū)間轉(zhuǎn)發(fā)的有機(jī)結(jié)合，建立了一個(gè)能耗最優(yōu)的路由傳輸協(xié)議。實(shí)驗(yàn)結(jié)果表明，所提算法具有較好的穩(wěn)定性，能夠有效節(jié)省單個(gè)節(jié)點(diǎn)的能量、均衡網(wǎng)絡(luò)能耗，顯著延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間。

雖然本文算法在實(shí)驗(yàn)中表現(xiàn)了良好的性能優(yōu)勢(shì)，但實(shí)際環(huán)境中移動(dòng)節(jié)點(diǎn)、異構(gòu)網(wǎng)絡(luò)和機(jī)會(huì)網(wǎng)絡(luò)的應(yīng)用越來(lái)越廣泛，為了更好地適應(yīng)傳感器網(wǎng)絡(luò)的發(fā)展，下一步的工作是根據(jù)算法在不同的網(wǎng)絡(luò)環(huán)境下的需要做出改進(jìn)，使其更適應(yīng)于實(shí)際場(chǎng)合。

參考文獻(xiàn)：

[1] 張曉玲, 梁煒, 于海斌等. 無(wú)線傳感器網(wǎng)絡(luò)傳輸調(diào)度方法綜述[J].通信學(xué)報(bào),2012,33(5): 143-157.ZHANG X L, LIANG W, YU H B, et al. Survey of transmission scheduling methods in wireless sensor networks[J]. Journal on Communications, 2012, 33(5): 143-157.

[2] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[3] ABBASI A A, YOUNIS M. A survey on clustering algorithms for wireless sensor networks[J]. Computer Communications, 2007, 30(14-15):2826-2841.

[4] HUANG W W, PENG Y K, WEN J, et al. Energy-efficient mhop hier ar chical routing protocol for wireless sensor netwoks[J]. IEEE Computer Society, 2009, 35( 2): 469- 472.

[5] LI B, WANG W J, YIN Q Y, et al. An energy-efficient geographic routing based on cooperative transmission in wireless sensor networks[J]. Sci China Inf Sci, 2013, 56: 4757-4762.

[6] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications,2002,1(4): 660-670.

[7] 陳慶章, 趙小敏, 陳曉瑩. 提高無(wú)線傳感器網(wǎng)絡(luò)能效的雙輪成簇協(xié)議設(shè)計(jì)[J]. 軟件學(xué)報(bào),2010, 21(11): 2933-2943.CHEN Q Z, ZHAO X M, CHEN X Y. Design of double rounds clustering protocol for improving energy efficient in wireless[J]. Journal of Software, 2010, 21(11):2933-2943.

[8] LI C F, YE M, CHEN G H, et al. An energy-efficient unequal clustering mechanism for wireless sensor networks[A]. Proc of the IEEE Int’l Conf on Mobile Ad Hoc and Sensor Systems[C].Washington, DC, USA, 2005. 597-604.

[9] ZHANG R B, CAO J F. Uneven clustering routing algorithm for wireless sensor networks based on ant colony optimization[J]. Journal of Xi’an Jiaotong University, 2010, 44(6):33-38.

[10] WANG Y, ZHANG D Y, LIANG T T. Cell energy balanced uneven clustering hierarchy scheme for wireless sensor networks[J]. Journal of Xi’an Jiaotong University, 2008, 42(4):389-394.

[11] 蔣暢江, 石為人, 唐賢倫等. 能量均衡的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 軟件學(xué)報(bào), 2012, 23(5):190-200.JIANG C J, SHI W R, TANG X L, et al. Energy-balanced unequal clustering routing protocol for wireless sensor networks[J]. Journal of Software,2012,23(5):190-200.

[12] 劉唐, 彭艦, 楊進(jìn). 異構(gòu)延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸[J]. 軟件學(xué)報(bào), 2013, 24(2):215-229.LIU T, PENG J, YANG J. Data delivery for heterogeneous delay tolerant mobile sensor networks based on forwarding probability[J].Journal of Software, 2013, 24(2):215-229.

[13] 洪榛, 俞立, 張貴軍. 多級(jí)異構(gòu)無(wú)線傳感器網(wǎng)高效動(dòng)態(tài)聚簇策略研究[J].自動(dòng)化學(xué)報(bào), 2013, 39(4):454-460.HONG Z, YU L, ZHANG G J. Efficient and dynamic clustering scheme for heterogeneous multi-level wireless sensor networks[J].Acta Automatica Sinica,2013,39(4):454-460.

[14] 卿利, 朱清新, 王明文. 異構(gòu)傳感器網(wǎng)絡(luò)的分布式能量有效成簇算法[J]. 軟件學(xué)報(bào),2006,17(3): 481-489.QING L, ZHU Q X, WANG M W. A distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Journal of Software, 2006, 17(3): 481-489.