分簇路由算法中的多跳跳數(shù)及中繼節(jié)點優(yōu)化

孫 振，王 凱，王亞剛

1(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)2(上海理工大學(xué) 上海出版印刷高等?？茖W(xué)校，上海 200093)

1 引 言

無線傳感器網(wǎng)絡(luò)WSNs(wireless sensor networks)是由隨機(jī)部署的微型傳感器節(jié)點組成，通過無線方式與終端用戶通信，監(jiān)測多種物理參數(shù)和執(zhí)行命令動作的多跳自組織網(wǎng)絡(luò)[1].WSNs被廣泛應(yīng)用于軍事、環(huán)境觀測等領(lǐng)域，但由于大部分應(yīng)用情景中采用能量有限的電池供電，使得網(wǎng)絡(luò)生命周期較大程度受到電池能量的制約[2].節(jié)點網(wǎng)絡(luò)層中的路由協(xié)議是節(jié)能和均衡負(fù)載的關(guān)鍵技術(shù)之一，因此如何設(shè)計能量高效的路由協(xié)議至關(guān)重要[3].

為了節(jié)省能耗，學(xué)者們提出許多利用數(shù)據(jù)融合技術(shù)減少數(shù)據(jù)傳輸量的層次路由協(xié)議，而在層次路由協(xié)議中，分簇路由算法較為活躍、有效[4].LEACH[5]算法是早期經(jīng)典分簇算法之一，LEACH算法按輪循環(huán)，以概率選取簇頭，然后根據(jù)入簇信號的強(qiáng)度入簇，最后簇頭直接將融合后的數(shù)據(jù)發(fā)給基站.LEACH算法的主要缺點是：a)剩余能量低的傳感器節(jié)點也會出任簇頭；b)采用單跳傳輸造成距基站較遠(yuǎn)的節(jié)點過早死亡.為改進(jìn)LEACH算法的單跳不足，EBCRP[6]算法綜合考慮鄰近簇頭的距離和方向來選擇中繼簇頭，實現(xiàn)簇間多跳傳輸，節(jié)省了遠(yuǎn)基站簇頭能量，但沒有考慮中繼簇頭的剩余能量，造成簇頭過早死亡.針對多跳雖能夠節(jié)省能量，但易造成近基站節(jié)點過早死亡的熱區(qū)[7]問題，學(xué)者們提出了EEUC[8]、DEBUC[9]、SNNUC[10]等算法，EEUC通過競爭半徑調(diào)節(jié)簇規(guī)模，近基站簇的簇規(guī)模較小，從而減少了簇內(nèi)能耗，簇頭將有更多能量承擔(dān)路由傳輸任務(wù).DEBUC算法基于EEUC算法的競爭機(jī)制，利用節(jié)點剩余能量調(diào)制等待時間競選簇頭，節(jié)省了節(jié)點信息交換能耗，有效延長網(wǎng)絡(luò)壽命.SNNUC算法基于時間成簇，利用競爭半徑調(diào)節(jié)簇規(guī)模時，將節(jié)點密度、剩余能量考慮在內(nèi)，使簇的大小更加合理.此外，還有一些非均勻分簇算法通過競選區(qū)頭[11]或者副簇頭[12]來分擔(dān)簇頭的能耗，有效的平衡了節(jié)點間的能耗.上述非均勻分簇算法存在待改進(jìn)的地方，如：a)熱區(qū)狀況的評價較為粗糙，大部分算法只整體觀測到越靠近基站的區(qū)域越‘熱’，而且無法對熱區(qū)“熱”的程度進(jìn)行量化；b)多跳傳輸數(shù)據(jù)時，將源節(jié)點到中繼，中繼再到基站兩跳的最低能耗作為選擇中繼的標(biāo)準(zhǔn)，但能耗最低時的跳數(shù)不一定為兩跳.關(guān)于一定距離能耗最低的最優(yōu)跳數(shù)有關(guān)討論中，文獻(xiàn)[13]推導(dǎo)出最優(yōu)跳數(shù)的通項，但此通項推導(dǎo)過程中未對平均跳距處于自由空間模型和多路徑衰減模型各自的最優(yōu)整數(shù)跳數(shù)進(jìn)行比較，而文獻(xiàn)[14]只精確分析了以一跳為最優(yōu)跳數(shù)和以兩跳為最優(yōu)跳數(shù)時節(jié)點距基站的距離，需要再推廣分析.

針對以上問題，本文提出了一種基于最優(yōu)跳數(shù)的非均勻分簇路由算法(下文簡稱UCOH算法).主要特點如下：a)利用推導(dǎo)出的路由理想路徑引入支撐量，量化區(qū)域“熱”的程度，以優(yōu)化簇的規(guī)模，進(jìn)一步均衡簇頭節(jié)點的簇內(nèi)和簇外消耗；b)限制成簇區(qū)域以及利用基站廣播公共信息，節(jié)省近基站節(jié)點整體能耗和節(jié)點信息交換能耗；c)數(shù)據(jù)傳輸階段，在本輪的候選簇頭中選擇中繼節(jié)點，以減少簇頭負(fù)載.下一跳中繼節(jié)點的評價考慮了最優(yōu)跳數(shù)的跳距，剩余能量，傳輸方向，期望在保持能耗平衡的同時減小多跳能耗.實驗結(jié)果表明，對于密度較大的網(wǎng)絡(luò)，本算法與DEBUC、UCDP、SNNUC相比，能使以30%節(jié)點死亡為網(wǎng)絡(luò)失效的網(wǎng)絡(luò)生命周期得到不同程度的延長.

2 系統(tǒng)模型

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

在文獻(xiàn)[10]的基礎(chǔ)上，假設(shè)傳感器網(wǎng)絡(luò)模型的屬性為：

a)傳感器節(jié)點是同構(gòu)的，即有相同的初始能量，處理能力等.

b)傳感器節(jié)點具有唯一標(biāo)識ID，且位置靜止，節(jié)點能夠感知基站的方位.

c)傳感器可以獲得自身剩余能量值和通過數(shù)據(jù)包獲知其他節(jié)點剩余能量值.

d)傳感器節(jié)點的發(fā)射功率可調(diào)，各個節(jié)點能夠相互進(jìn)行通信并且每個節(jié)點能與基站直接進(jìn)行通信.

e)基站能量不受限制且處理能力，存儲能力強(qiáng)大，發(fā)射功率可覆蓋所有節(jié)點，能獲得網(wǎng)絡(luò)邊界.

2.2 能耗模型及最優(yōu)跳數(shù)的推導(dǎo)

本文采用與文獻(xiàn)[15]相同的一階無線電模型，重點考慮數(shù)據(jù)傳輸和接收時所消耗的能量，忽略節(jié)點采集數(shù)據(jù)、計算、存儲等過程中消耗的能量.節(jié)點發(fā)送lbit數(shù)據(jù)至相距距離為d的節(jié)點所消耗的能量為：

(1)

節(jié)點接收lbit數(shù)據(jù)的能耗為：

ERx(l)=lEelec

(2)

其中：Eelec=50nJ/bit為射頻能耗系數(shù)；εfs=10pJ/bit/m2，εmp=0.0013pJ/bit/m4分別為自由空間模型和多路徑衰減模型功率放大電路能耗系數(shù)；d0為距離閾值，本文設(shè)為87.7m.

下面推導(dǎo)節(jié)點直線發(fā)送數(shù)據(jù)到基站的最優(yōu)跳數(shù).

定義1.當(dāng)節(jié)點到基站的距離為d，若從節(jié)點經(jīng)n跳直線傳輸數(shù)據(jù)到基站時各節(jié)點所耗能量和最小，則稱n跳為節(jié)點向基站傳輸數(shù)據(jù)的最優(yōu)跳數(shù).

推論1.若節(jié)點將數(shù)據(jù)經(jīng)中繼直線傳輸?shù)交?，?jié)點到基站距離為d，當(dāng)dc(n)

(3)

當(dāng)給出節(jié)點到基站的距離時可用hop(d)計算最優(yōu)跳數(shù)，其計算公式為：

(4)

「?表示向上取整.

(5)

以n為自變量，假設(shè)n連續(xù)，則上式對n求導(dǎo)為：

(6)

圖1 簡單線性網(wǎng)絡(luò)Fig.1 Simple linear net

(7)

令Δ(d)≥0，據(jù)以上分析，解出式(8).

(8)

于是得出當(dāng)nd00時dc(n)的分布，發(fā)現(xiàn)基本成一直線，對其進(jìn)行線性擬合，抽象出最優(yōu)跳數(shù)的計算公式為式(4)，(4)式也可用于計算本文分區(qū)的區(qū)號.本文將用該最優(yōu)跳數(shù)引入能更詳細(xì)描述熱區(qū)情況的支撐量來平衡負(fù)載，并用最優(yōu)跳數(shù)尋找最大限度節(jié)省多跳傳輸能耗的路由路徑.

采用數(shù)據(jù)融合技術(shù)有利于減少發(fā)送的數(shù)據(jù)量，本文的融合模型為：簇內(nèi)數(shù)據(jù)完全融合，并且認(rèn)為簇間數(shù)據(jù)差異較大而不進(jìn)行融合，融合能耗設(shè)定為EDA=5nJ/bit.

3 UCOH算法描述及分析

總的來說，UCOH算法是一種結(jié)合輪循環(huán)機(jī)制、非均勻時間競爭分簇機(jī)制、數(shù)據(jù)融合以及數(shù)據(jù)多跳傳輸?shù)乃惴?輪循環(huán)機(jī)制是指系統(tǒng)按輪運(yùn)行，每輪分為：a)輪初始化階段，首輪時，各節(jié)點根據(jù)自身到基站的最優(yōu)跳數(shù)確定自己的分區(qū)，并確定成為簇頭時的入簇半徑(用于控制簇的規(guī)模).首輪后，基站在每輪的此階段廣播必要的信息；b)非均勻時間競爭成簇階段，此階段網(wǎng)絡(luò)首先競選候選簇頭，然后根據(jù)剩余能量調(diào)制時間競爭簇頭，最后普通節(jié)點根據(jù)入簇半徑、簇頭剩余能量和路由消耗進(jìn)行入簇；c)數(shù)據(jù)傳輸階段，首先普通節(jié)點將數(shù)據(jù)單跳傳給簇頭，簇頭融合數(shù)據(jù)后將數(shù)據(jù)或者直接發(fā)送給基站，或者選擇剩余能量高并較符合最優(yōu)跳數(shù)跳距的候選節(jié)點多次中繼后發(fā)給基站.

要特別說明的是，在成簇階段，文獻(xiàn)[16]使距基站小于87.7m的節(jié)點不成簇入簇以節(jié)省分簇和簇內(nèi)通信損耗，但未給出理論依據(jù)，本文使距基站小于74m的候選節(jié)點不競選簇頭，普通節(jié)點距基站小于74m時不入簇以防止成簇的節(jié)能效益不如不成簇.依據(jù)如下：如存在節(jié)點Si和簇頭Sj兩節(jié)點距基站距離都小于d0，且兩節(jié)點的距離小于d0，則節(jié)點Si直接發(fā)送lbit數(shù)據(jù)到基站的消耗和經(jīng)簇頭中繼發(fā)送的消耗分別為Edirect，Ec_relay，如式(9)，(10)所示.

Edirect=ETx(l，dis)

(9)

Ec_relay=ETx(l，dij)+ERx(l)+lEDA+ETx((1-pDA)l，djs)

(10)

其中：pDA表示數(shù)據(jù)融合率；dis，djs，dij是兩節(jié)點到基站的距離和兩節(jié)點之間的距離.如果期望入簇會節(jié)省能量需要Edirect>Ec_relay，將其展開如式(11)所示.

(11)

為簡單起見，假設(shè)數(shù)據(jù)完全融合則pDA=1，而dij≥0，經(jīng)計算得dis至少在74m以上時，上式才有可能成立.對于其他位置的節(jié)點，按照經(jīng)典正常成簇入簇，因此本文以74m為成簇分界線.

下面給出其他相關(guān)定義.

定義 2.支撐量 假設(shè)節(jié)點均勻分布，每個節(jié)點都有符合最優(yōu)跳數(shù)的中繼，則支撐量src(dtoBS，dtoBS-max)表示以最優(yōu)跳數(shù)的路徑傳輸數(shù)據(jù)時，基站某方向射線上距基站dtoBS的位置所承擔(dān)的最大消耗(實際節(jié)點密度可能不這么高)，用于表示多跳傳輸時某位置‘熱’的程度.其公式如式(12)所示.

rc(ms，mr，dtoBS，dtoBS-max)

(12)

rc(ms，mr，dtoBS，dtoBS-max)=

(13)

其中：rc(ms，mr，dtoBS，dtoBS-max)表示數(shù)據(jù)源自所處ms區(qū)，當(dāng)以最優(yōu)跳數(shù)傳輸時，在mr(mr=1，2，3，…，ms)區(qū)(最優(yōu)跳數(shù)形成的路徑會經(jīng)過朝向基站的每一個區(qū))距基站dtoBS的節(jié)點收發(fā)數(shù)據(jù)所耗的能量；dtoBS-max為從基站發(fā)射的沿某方向的射線與網(wǎng)絡(luò)邊界交點到基站的距離，也既該射線方向dtoBS的最大值.rc(ms，mr，dtoBS，dtoBS-max)公式如(13)所示.假設(shè)dtoBS-max=300，則以dtoBS為自變量src(dtoBS，dtoBS-max)的曲線為圖2所示，從圖中可以看出簇外能耗情況類似波浪并非線性地與節(jié)點距基站的距離相關(guān).

圖2 dtoBS-max=300支撐量分布情況Fig.2 Distribution of src when dtoBS-max=300

定義3.最優(yōu)前向路由消耗frc(dtoBS) 用來表示距基站dtoBS的節(jié)點，以最優(yōu)跳數(shù)發(fā)送1bit數(shù)據(jù)所耗能量，公式如式(14)所示.

(14)

下面將按輪循環(huán)機(jī)制詳細(xì)介紹本算法.

3.1 輪初始化

首輪時，在節(jié)點部署完畢后，基站會發(fā)送一個“hello”消息至網(wǎng)絡(luò)中的所有節(jié)點，節(jié)點Si根據(jù)接收到的信號強(qiáng)度大小估算自身到基站的距離dis，確定自己所屬分區(qū)，區(qū)號等于hop(dis)，以表征各節(jié)點最優(yōu)跳數(shù)特征.

為競選出均勻分布的簇頭，距基站小于74m的節(jié)點不競選簇頭，競爭半徑為0，距基站大于74m的節(jié)點賦予相同的競爭半徑Rcmp.為避免熱區(qū)內(nèi)的節(jié)點因簇外數(shù)據(jù)傳輸任務(wù)過重而能量耗盡，為每一個節(jié)點設(shè)置一個入簇半徑，以調(diào)節(jié)節(jié)點出任簇頭時所在簇的規(guī)模.簇頭節(jié)點Si的簇內(nèi)能耗主要為接收簇內(nèi)節(jié)點數(shù)據(jù)消耗，簇外能耗主要體現(xiàn)在支撐量上(兩者為估計值，后面節(jié)點要根據(jù)實際能耗情況入簇)，假設(shè)節(jié)點均勻分布，若要通過減少簇內(nèi)能耗供中繼使用有：

(15)

其中：NS為節(jié)點數(shù)量；S為網(wǎng)絡(luò)面積，則等式左邊為預(yù)計縮小入簇半徑時預(yù)留給中繼使用的能量，其在一定程度上反映了節(jié)點密度信息；Ri為簇頭Si的入簇半徑；dborder-i為基站沿節(jié)點Si方向的射線與邊界的交點到基站的距離(本文假設(shè)基站在網(wǎng)絡(luò)中央)，將Ri解出有：

(16)

通常而言發(fā)揮入簇優(yōu)勢時，簇內(nèi)耗能會比簇外耗能要大，則上式衡有解，且上式表明，較熱區(qū)域內(nèi)的節(jié)點會被分配較小的入簇半徑，以平衡節(jié)點成為簇頭后的簇內(nèi)簇外路由能耗.該式綜合了簇內(nèi)簇外的具體能耗，與同類算法比例化距基站距離等因素來調(diào)節(jié)簇規(guī)模相比要精確些.

首輪后，基站在這一階段會廣播CYCLE_START報文給所有節(jié)點，報文包括上一輪到基站距離大于74m的存活節(jié)點的平均剩余能量和存活節(jié)點數(shù)，這些數(shù)據(jù)由節(jié)點發(fā)送到基站的數(shù)據(jù)包中解析而來.

3.2 非均勻成簇

非均勻成簇的過程包括：選舉候選簇頭、簇頭選舉、普通節(jié)點入簇三個階段.在前兩個階段中，考慮到一些應(yīng)用基本信息大小與數(shù)據(jù)包大小之比較大或節(jié)點密度較大時，若節(jié)點相互交換基本信息總耗能會過大，故UCOH算法用基站廣播最重要的公共能量信息成簇，而不考慮其他因素.

3.2.1 選舉候選簇頭

選舉候選簇頭時，首先各個節(jié)點依隨機(jī)數(shù)(0-1)與閾值比較，若小于閾值則出任候選簇頭，非候選簇頭節(jié)點進(jìn)入睡眠狀態(tài)到簇頭選舉結(jié)束.所用的閾值公式改進(jìn)自LEACH算法，對于節(jié)點Si來說其閾值函數(shù)如式(17)所示.

(17)

3.2.2 簇頭選舉

UCOH算法在此階段采用計時廣播機(jī)制代替UCDP[11]算法協(xié)商機(jī)制來競選簇頭，以節(jié)省基本信息交換能耗.

對于距基站大于74m的候選簇頭，計時廣播機(jī)制讓等待時間較短的候選簇頭先廣播獲勝消息，鄰居節(jié)點收到獲勝信息則退出競選.節(jié)點Si的鄰居節(jié)點定義如式(18)所示.

Di={Sj|Sj是候選簇首，且dij

(18)

候選節(jié)點Si的等待時間ti改進(jìn)自DEBUC算法，其公式如式(19)所示.

(19)

簇頭競選完成后，各簇頭以2倍d0為半徑廣播入簇報文CH_ADV_MSG，喚醒處于休眠狀態(tài)的普通節(jié)點，該報文包括簇頭的ID、入簇半徑、距基站的距離和剩余能量，供普通節(jié)點判斷加入哪一個簇更優(yōu).

3.2.3 普通節(jié)點入簇

為使簇內(nèi)節(jié)點規(guī)模符合熱區(qū)和平衡能耗，入簇方法如下：如果節(jié)點位于某些簇頭的入簇半徑內(nèi)，則節(jié)點在那些入簇半徑包含該節(jié)點的簇頭中選擇距離引力最大的簇入簇，如果節(jié)點不在任何簇頭的入簇半徑內(nèi)，則節(jié)點在收到的入簇信息中選擇信號強(qiáng)度最強(qiáng)的簇入簇，在網(wǎng)絡(luò)生命周期后期，如果沒有入簇信息，則將數(shù)據(jù)直接發(fā)送到基站.改進(jìn)的距離引力具體化了UCDP算法中的距離因素，考慮了簇頭的剩余能量、節(jié)點發(fā)送數(shù)據(jù)能耗和簇頭最優(yōu)前向路由消耗，公式如式(20)所示.

(20)

其中：Si表示普通節(jié)點；CHj表示簇頭；E(CHj)表示簇頭的剩余能量；di-CHj表示節(jié)點Si和簇頭CHj的距離.上式說明，普通節(jié)點會選擇剩余能量較大，距離較近，并且前向數(shù)據(jù)傳輸消耗小的簇頭，以均衡負(fù)載和降低能耗.選擇好簇頭后，節(jié)點發(fā)送JOIN_CLUSTER_MSG報文通知相應(yīng)簇頭.簇形成后，簇頭會在簇內(nèi)廣播TDMA時隙，各節(jié)點按時隙通信.當(dāng)簇頭收集簇內(nèi)數(shù)據(jù)并融合完畢后，進(jìn)入數(shù)據(jù)傳輸階段.

3.3 數(shù)據(jù)傳輸階段

本算法采用簇內(nèi)單跳和簇外多跳中繼的數(shù)據(jù)傳輸方式，中繼節(jié)點在候選簇頭中選擇.利用候選簇頭作中繼不會在競選副簇頭、區(qū)頭上耗能，并防止如文獻(xiàn)[17]收集源節(jié)點廣播半徑內(nèi)所有節(jié)點的基本信息，導(dǎo)致信息收集耗能過多，節(jié)能效益反而降低的情形.下文將簇頭或中繼節(jié)點特定廣播范圍內(nèi)的候選簇頭稱作該廣播范圍的鄰居候選簇頭(不包括本輪出任簇頭的節(jié)點).傳輸策略總結(jié)如下：

a)距基站74m以內(nèi)的普通節(jié)點或中繼將數(shù)據(jù)直接發(fā)送到基站；

b)從圖2可以看出距基站大于74m小于dc(1)的節(jié)點所處區(qū)域較熱，應(yīng)首要考慮能量平衡，所以將考慮是否繼續(xù)中繼，在該范圍內(nèi)的簇頭或中繼節(jié)點，以距基站的距離廣播探測信息，在廣播范圍內(nèi)的鄰居候選簇頭判斷自己是否距基站更近并距基站小于74m，若是則將自己的基本信息發(fā)回簇頭或中繼節(jié)點(為使基本信息交換能耗不至過大，將在第4節(jié)整定候選簇頭出任概率)，簇頭或中繼節(jié)點Si構(gòu)建每個鄰居候選簇頭Sj的信息表，如表1所示，用以尋找中繼.

表1 節(jié)點Sj信息表Table 1 Information of node Sj

設(shè)Si鄰居候選簇頭集為Dn-i，則在節(jié)點集合

c)距基站大于dc(1)的簇頭或中繼節(jié)點Si以dc(1)為廣播半徑，以和上文類似的方式維護(hù)一個鄰居候選簇頭集合，首先，若鄰居候選簇頭Sj的剩余能量與Si探測到的所有鄰居候選簇頭平均剩余能量的比值小于一定比值，則不通過Sj中繼，以保障能耗平衡，Sj比值公式Vj如式(21).

(21)

(22)

g(dij)=

(23)

(24)

(25)

以上公式中f(x1，x2)表示多跳比單跳所節(jié)省的能量差的比率0

算法 1.整體算法流程

Step1.如果是首輪，基站先廣播“hello”報文，各節(jié)點根據(jù)式(4)、(16)計算區(qū)號和入簇半徑.之后基站廣播CYCLE_START報文.

Step2.各節(jié)點根據(jù)式(17)出任候選簇頭，并根據(jù)式(19)競爭簇頭，普通節(jié)點根據(jù)3.2小節(jié)入簇策略入簇.

Step3.距基站74m以內(nèi)的普通節(jié)點(或之后中繼)直接將數(shù)據(jù)發(fā)送到基站.簇頭收集簇內(nèi)數(shù)據(jù)并融合.

Step4.對于距基站74m以外的每個簇頭和中繼候選簇頭Si，Si發(fā)出探測信息獲得Dn-i，若Dn-i為空，則將數(shù)據(jù)直接發(fā)往基站，否則：若Si到基站距離處于74到dc(1)之間，則從Droute中選取使dij最小的Sj做下一跳； 若Si到基站距離大于dc(1)，選擇Dn-i中能量梯度最大的且符合式(21)的節(jié)點做下一跳，沒有符合條件的節(jié)點則將數(shù)據(jù)直接發(fā)送到基站.所有節(jié)點傳輸完畢，進(jìn)入下一輪，轉(zhuǎn)Step 1.

4 仿真與性能分析

4.1 仿真環(huán)境

為了驗證所提算法的性能，本文基于MATLAB 平臺對DEBUC、UCDP、SNNUC、UCOH算法進(jìn)行仿真，對比多項指標(biāo).假設(shè)傳感器網(wǎng)絡(luò)覆蓋邊長為L的正方形區(qū)域，基站位于區(qū)域中央，無線通信能耗模型的相關(guān)參數(shù)詳見第2節(jié)，其他實驗環(huán)境參數(shù)如表2所示.

表2 實驗參數(shù)Table 2 Experimental parameters

4.2 候選簇頭概率的確定

候選簇頭出任概率p的值在一定程度上影響著算法的性能，p過小不能發(fā)揮成簇的優(yōu)勢，p增大時雖然有更大概率找到符合最優(yōu)跳數(shù)的中繼候選簇頭，但會在成簇階段和路由階段產(chǎn)生較大的信息交換能耗，本文通過實驗分析確定本算法的最優(yōu)p值.以L=400，NS=1600為例，調(diào)整p值(0.03-0.21)觀測網(wǎng)絡(luò)第一個節(jié)點、10%節(jié)點、30%節(jié)點死亡時網(wǎng)絡(luò)運(yùn)行輪數(shù)變化情況，得到如圖3數(shù)據(jù).

圖3 節(jié)點死亡輪數(shù)變化曲線Fig.3 Variation curve of cycle of nodes death

從圖3中可以看出：a)當(dāng)p較小時，簇頭數(shù)目較少，負(fù)載大，且一小部分節(jié)點入簇耗費能量較大，第一個節(jié)點死亡時間較早；b)當(dāng)p再次增大時，節(jié)點入簇能耗和路由階段節(jié)點構(gòu)建路由表能耗增加，導(dǎo)致30%節(jié)點死亡的輪數(shù)提前；c)10%節(jié)點死亡后，其余節(jié)點成批迅速死亡，其原因一是本文的一些平衡策略起作用(如入簇半徑)，且節(jié)點剩余能量都較小，原因二是死亡節(jié)點通常是熱區(qū)中路由消耗較小的節(jié)點，一旦它們死亡，路由消耗會成倍增加.本文取三個時間點的運(yùn)行輪數(shù)都較高的概率為最優(yōu)的候選簇頭概率，本例的最優(yōu)概率為0.11，其他規(guī)模網(wǎng)絡(luò)所取概率見4.3節(jié).

4.3 生存周期

本文將網(wǎng)絡(luò)死亡節(jié)點數(shù)達(dá)到30%視為網(wǎng)絡(luò)失效[9].為觀測UCOH算法在不同場景的性能，分別固定網(wǎng)絡(luò)范圍和固定節(jié)點數(shù)觀測比較4種算法首節(jié)點死亡和30%節(jié)點死亡時網(wǎng)絡(luò)運(yùn)行輪數(shù).圖4為固定網(wǎng)絡(luò)范圍L=400，NS∈NA時4種算法對比，UCOH算法候選簇頭概率隨節(jié)點數(shù)目增大依次取0.12，0.11，0.11，0.1，0.09，Rcmp取45，45，45，40，40.

圖4 網(wǎng)絡(luò)范圍固定時的網(wǎng)絡(luò)壽命對比Fig.4 Comparation of network lifetime with fixed network range

從圖4中可以看出隨著節(jié)點數(shù)目的增大，各算法兩個時間點的相應(yīng)輪數(shù)基本上均有增加.當(dāng)節(jié)點數(shù)較少時，節(jié)點信息交換能耗較少，SNNUC和UCDP算法競選簇頭時考慮的因素更周全，使得二者性能高于UCOH算法.當(dāng)節(jié)點數(shù)目較多時，UCDP算法成簇協(xié)商能耗較大，節(jié)點數(shù)為2000時的運(yùn)行輪數(shù)有所降低，性能差于SNNUC算法，而SNNUC與UCOH算法相比而言，UCOH算法的近基站節(jié)點能耗和成簇階段信息交換能耗較少，并且多跳路徑更優(yōu)降低了路由能耗，故UCOH算法在兩個時間點的運(yùn)行輪數(shù)最高.

圖5為固定節(jié)點數(shù)目NS=1600，L∈LA時運(yùn)行輪數(shù)對比，UCOH算法候選簇頭概率隨網(wǎng)絡(luò)規(guī)模增大依次取0.06，0.08，0.11，0.14，0.18，Rcmp取35，40，45，60，80.當(dāng)網(wǎng)絡(luò)范圍增大時，節(jié)點距基站的平均距離更遠(yuǎn)，各算法兩個時間點的運(yùn)行輪數(shù)有降低趨勢.規(guī)模較大時，密度較低，UCOH算法的熱區(qū)評估準(zhǔn)確性降低，但多跳跳數(shù)更優(yōu)，性能相比之下有所下降，但不為最差.當(dāng)規(guī)模較小時，UCDP算法即使在近基站成簇收益不能補(bǔ)償成簇能耗的情況下也會頻繁競選區(qū)頭和簇頭，并且它與DEBUC算法的競爭半徑未考慮節(jié)點密度，節(jié)點能耗均衡性不佳，造成兩者運(yùn)行輪數(shù)較低.UCOH算法熱區(qū)量化較為精確，節(jié)點入簇更合理，加之采用相應(yīng)策略防止了近基站能耗和信息交換能耗過大，故性能最好.綜合圖4圖5及其分析說明UCOH算法更適用于密度較大的網(wǎng)絡(luò).

圖5 節(jié)點數(shù)固定時的網(wǎng)絡(luò)壽命對比Fig.5 Comparation of network lifetime with fixed number of nodes

4.4 能量效率

圖6為L=400，NS=2000和L=200，NS=1600時網(wǎng)絡(luò)失效前的全局剩余能量曲線.可以看出密度較大時UCOH算法的能耗速率低于其他三種算法，例如在L=400，NS=2000的場景下，網(wǎng)絡(luò)運(yùn)行到450輪時，DEBUC、UCDP、SNNUC、UCOH網(wǎng)絡(luò)剩余能量分別為：76.4J，98.2J，116.9J，159.8J，說明UCOH算法在平衡與節(jié)約能耗方面是有效的.而其中原因在于UCOH算法利用基站廣播公共信息，限制近基站成簇，優(yōu)化了跳數(shù)和中繼節(jié)點，從而減緩了能耗速率.因此，與另外三種算法相比，UCOH算法更適用于密度較大的網(wǎng)絡(luò).

圖6 全局剩余能量變化曲線Fig.6 Variation curve of the global residual energy of nodes

5 結(jié)束語

基于大密度的WSNs應(yīng)用，本文在研究多跳網(wǎng)絡(luò)最優(yōu)跳數(shù)的基礎(chǔ)上提出了一種非均勻時間競爭分簇算法，核心思想是：利用最優(yōu)跳數(shù)指導(dǎo)簇規(guī)模的調(diào)整和下一跳路由的選取，緩解多跳路由中的“熱區(qū)”和節(jié)省能量；通過限定成簇區(qū)域，減少近基站節(jié)點能耗；利用時間競爭簇頭，節(jié)省節(jié)點信息交換的能耗；利用候選簇頭中繼，平衡節(jié)點負(fù)載.最終實驗結(jié)果表明，對于密度較大的網(wǎng)絡(luò)，本算法能有效節(jié)省網(wǎng)絡(luò)能量，均衡能耗，延長特定生命周期特征的網(wǎng)絡(luò)壽命.

本算法在仿真實驗中有較好的性能，但還不適用于節(jié)點異構(gòu)和節(jié)點可移動的網(wǎng)絡(luò)，下一步將探索研究該類網(wǎng)絡(luò)的路由算法.