分簇路由算法中的多跳跳數(shù)及中繼節(jié)點(diǎn)優(yōu)化
2019-06-06 06:17:02王亞剛
小型微型計(jì)算機(jī)系統(tǒng) 2019年6期
孫 振，王 凱，王亞剛
1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)2(上海理工大學(xué) 上海出版印刷高等專科學(xué)校，上海 200093)
1 引 言
無線傳感器網(wǎng)絡(luò)WSNs(wireless sensor networks)是由隨機(jī)部署的微型傳感器節(jié)點(diǎn)組成，通過無線方式與終端用戶通信，監(jiān)測(cè)多種物理參數(shù)和執(zhí)行命令動(dòng)作的多跳自組織網(wǎng)絡(luò)[1].WSNs被廣泛應(yīng)用于軍事、環(huán)境觀測(cè)等領(lǐng)域，但由于大部分應(yīng)用情景中采用能量有限的電池供電，使得網(wǎng)絡(luò)生命周期較大程度受到電池能量的制約[2].節(jié)點(diǎn)網(wǎng)絡(luò)層中的路由協(xié)議是節(jié)能和均衡負(fù)載的關(guān)鍵技術(shù)之一，因此如何設(shè)計(jì)能量高效的路由協(xié)議至關(guān)重要[3].
為了節(jié)省能耗，學(xué)者們提出許多利用數(shù)據(jù)融合技術(shù)減少數(shù)據(jù)傳輸量的層次路由協(xié)議，而在層次路由協(xié)議中，分簇路由算法較為活躍、有效[4].LEACH[5]算法是早期經(jīng)典分簇算法之一，LEACH算法按輪循環(huán)，以概率選取簇頭，然后根據(jù)入簇信號(hào)的強(qiáng)度入簇，最后簇頭直接將融合后的數(shù)據(jù)發(fā)給基站.LEACH算法的主要缺點(diǎn)是：a)剩余能量低的傳感器節(jié)點(diǎn)也會(huì)出任簇頭；b)采用單跳傳輸造成距基站較遠(yuǎn)的節(jié)點(diǎn)過早死亡.為改進(jìn)LEACH算法的單跳不足，EBCRP[6]算法綜合考慮鄰近簇頭的距離和方向來選擇中繼簇頭，實(shí)現(xiàn)簇間多跳傳輸，節(jié)省了遠(yuǎn)基站簇頭能量，但沒有考慮中繼簇頭的剩余能量，造成簇頭過早死亡.針對(duì)多跳雖能夠節(jié)省能量，但易造成近基站節(jié)點(diǎn)過早死亡的熱區(qū)[7]問題，學(xué)者們提出了EEUC[8]、DEBUC[9]、SNNUC[10]等算法，EEUC通過競(jìng)爭(zhēng)半徑調(diào)節(jié)簇規(guī)模，近基站簇的簇規(guī)模較小，從而減少了簇內(nèi)能耗，簇頭將有更多能量承擔(dān)路由傳輸任務(wù).DEBUC算法基于EEUC算法的競(jìng)爭(zhēng)機(jī)制，利用節(jié)點(diǎn)剩余能量調(diào)制等待時(shí)間競(jìng)選簇頭，節(jié)省了節(jié)點(diǎn)信息交換能耗，有效延長網(wǎng)絡(luò)壽命.SNNUC算法基于時(shí)間成簇，利用競(jìng)爭(zhēng)半徑調(diào)節(jié)簇規(guī)模時(shí)，將節(jié)點(diǎn)密度、剩余能量考慮在內(nèi)，使簇的大小更加合理.此外，還有一些非均勻分簇算法通過競(jìng)選區(qū)頭[11]或者副簇頭[12]來分擔(dān)簇頭的能耗，有效的平衡了節(jié)點(diǎn)間的能耗.上述非均勻分簇算法存在待改進(jìn)的地方，如：a)熱區(qū)狀況的評(píng)價(jià)較為粗糙，大部分算法只整體觀測(cè)到越靠近基站的區(qū)域越‘熱’，而且無法對(duì)熱區(qū)“熱”的程度進(jìn)行量化；b)多跳傳輸數(shù)據(jù)時(shí)，將源節(jié)點(diǎn)到中繼，中繼再到基站兩跳的最低能耗作為選擇中繼的標(biāo)準(zhǔn)，但能耗最低時(shí)的跳數(shù)不一定為兩跳.關(guān)于一定距離能耗最低的最優(yōu)跳數(shù)有關(guān)討論中，文獻(xiàn)[13]推導(dǎo)出最優(yōu)跳數(shù)的通項(xiàng)，但此通項(xiàng)推導(dǎo)過程中未對(duì)平均跳距處于自由空間模型和多路徑衰減模型各自的最優(yōu)整數(shù)跳數(shù)進(jìn)行比較，而文獻(xiàn)[14]只精確分析了以一跳為最優(yōu)跳數(shù)和以兩跳為最優(yōu)跳數(shù)時(shí)節(jié)點(diǎn)距基站的距離，需要再推廣分析.
針對(duì)以上問題，本文提出了一種基于最優(yōu)跳數(shù)的非均勻分簇路由算法(下文簡稱UCOH算法).主要特點(diǎn)如下：a)利用推導(dǎo)出的路由理想路徑引入支撐量，量化區(qū)域“熱”的程度，以優(yōu)化簇的規(guī)模，進(jìn)一步均衡簇頭節(jié)點(diǎn)的簇內(nèi)和簇外消耗；b)限制成簇區(qū)域以及利用基站廣播公共信息，節(jié)省近基站節(jié)點(diǎn)整體能耗和節(jié)點(diǎn)信息交換能耗；c)數(shù)據(jù)傳輸階段，在本輪的候選簇頭中選擇中繼節(jié)點(diǎn)，以減少簇頭負(fù)載.下一跳中繼節(jié)點(diǎn)的評(píng)價(jià)考慮了最優(yōu)跳數(shù)的跳距，剩余能量，傳輸方向，期望在保持能耗平衡的同時(shí)減小多跳能耗.實(shí)驗(yàn)結(jié)果表明，對(duì)于密度較大的網(wǎng)絡(luò)，本算法與DEBUC、UCDP、SNNUC相比，能使以30%節(jié)點(diǎn)死亡為網(wǎng)絡(luò)失效的網(wǎng)絡(luò)生命周期得到不同程度的延長.
2 系統(tǒng)模型
2.1 網(wǎng)絡(luò)模型
在文獻(xiàn)[10]的基礎(chǔ)上，假設(shè)傳感器網(wǎng)絡(luò)模型的屬性為：
a)傳感器節(jié)點(diǎn)是同構(gòu)的，即有相同的初始能量，處理能力等.
b)傳感器節(jié)點(diǎn)具有唯一標(biāo)識(shí)ID，且位置靜止，節(jié)點(diǎn)能夠感知基站的方位.
c)傳感器可以獲得自身剩余能量值和通過數(shù)據(jù)包獲知其他節(jié)點(diǎn)剩余能量值.
d)傳感器節(jié)點(diǎn)的發(fā)射功率可調(diào)，各個(gè)節(jié)點(diǎn)能夠相互進(jìn)行通信并且每個(gè)節(jié)點(diǎn)能與基站直接進(jìn)行通信.
e)基站能量不受限制且處理能力，存儲(chǔ)能力強(qiáng)大，發(fā)射功率可覆蓋所有節(jié)點(diǎn)，能獲得網(wǎng)絡(luò)邊界.
2.2 能耗模型及最優(yōu)跳數(shù)的推導(dǎo)
本文采用與文獻(xiàn)[15]相同的一階無線電模型，重點(diǎn)考慮數(shù)據(jù)傳輸和接收時(shí)所消耗的能量，忽略節(jié)點(diǎn)采集數(shù)據(jù)、計(jì)算、存儲(chǔ)等過程中消耗的能量.節(jié)點(diǎn)發(fā)送lbit數(shù)據(jù)至相距距離為d的節(jié)點(diǎn)所消耗的能量為：
(1)
節(jié)點(diǎn)接收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é)點(diǎn)直線發(fā)送數(shù)據(jù)到基站的最優(yōu)跳數(shù).
定義1.當(dāng)節(jié)點(diǎn)到基站的距離為d，若從節(jié)點(diǎn)經(jīng)n跳直線傳輸數(shù)據(jù)到基站時(shí)各節(jié)點(diǎn)所耗能量和最小，則稱n跳為節(jié)點(diǎn)向基站傳輸數(shù)據(jù)的最優(yōu)跳數(shù).
推論1.若節(jié)點(diǎn)將數(shù)據(jù)經(jīng)中繼直線傳輸?shù)交荆?jié)點(diǎn)到基站距離為d，當(dāng)dc(n) (3) 當(dāng)給出節(jié)點(diǎn)到基站的距離時(shí)可用hop(d)計(jì)算最優(yōu)跳數(shù)，其計(jì)算公式為： (4) 「?表示向上取整. (5) 以n為自變量，假設(shè)n連續(xù)，則上式對(duì)n求導(dǎo)為： (6) 圖1 簡單線性網(wǎng)絡(luò)Fig.1 Simple linear net (7) 令Δ(d)≥0，據(jù)以上分析，解出式(8). (8) 于是得出當(dāng)nd0 采用數(shù)據(jù)融合技術(shù)有利于減少發(fā)送的數(shù)據(jù)量，本文的融合模型為：簇內(nèi)數(shù)據(jù)完全融合，并且認(rèn)為簇間數(shù)據(jù)差異較大而不進(jìn)行融合，融合能耗設(shè)定為EDA=5nJ/bit. 總的來說，UCOH算法是一種結(jié)合輪循環(huán)機(jī)制、非均勻時(shí)間競(jìng)爭(zhēng)分簇機(jī)制、數(shù)據(jù)融合以及數(shù)據(jù)多跳傳輸?shù)乃惴?輪循環(huán)機(jī)制是指系統(tǒng)按輪運(yùn)行，每輪分為：a)輪初始化階段，首輪時(shí)，各節(jié)點(diǎn)根據(jù)自身到基站的最優(yōu)跳數(shù)確定自己的分區(qū)，并確定成為簇頭時(shí)的入簇半徑(用于控制簇的規(guī)模).首輪后，基站在每輪的此階段廣播必要的信息；b)非均勻時(shí)間競(jìng)爭(zhēng)成簇階段，此階段網(wǎng)絡(luò)首先競(jìng)選候選簇頭，然后根據(jù)剩余能量調(diào)制時(shí)間競(jìng)爭(zhēng)簇頭，最后普通節(jié)點(diǎn)根據(jù)入簇半徑、簇頭剩余能量和路由消耗進(jìn)行入簇；c)數(shù)據(jù)傳輸階段，首先普通節(jié)點(diǎn)將數(shù)據(jù)單跳傳給簇頭，簇頭融合數(shù)據(jù)后將數(shù)據(jù)或者直接發(fā)送給基站，或者選擇剩余能量高并較符合最優(yōu)跳數(shù)跳距的候選節(jié)點(diǎn)多次中繼后發(fā)給基站. 要特別說明的是，在成簇階段，文獻(xiàn)[16]使距基站小于87.7m的節(jié)點(diǎn)不成簇入簇以節(jié)省分簇和簇內(nèi)通信損耗，但未給出理論依據(jù)，本文使距基站小于74m的候選節(jié)點(diǎn)不競(jìng)選簇頭，普通節(jié)點(diǎn)距基站小于74m時(shí)不入簇以防止成簇的節(jié)能效益不如不成簇.依據(jù)如下：如存在節(jié)點(diǎn)Si和簇頭Sj兩節(jié)點(diǎn)距基站距離都小于d0，且兩節(jié)點(diǎn)的距離小于d0，則節(jié)點(diǎn)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é)點(diǎn)到基站的距離和兩節(jié)點(diǎn)之間的距離.如果期望入簇會(huì)節(jié)省能量需要Edirect>Ec_relay，將其展開如式(11)所示. (11) 為簡單起見，假設(shè)數(shù)據(jù)完全融合則pDA=1，而dij≥0，經(jīng)計(jì)算得dis至少在74m以上時(shí)，上式才有可能成立.對(duì)于其他位置的節(jié)點(diǎn)，按照經(jīng)典正常成簇入簇，因此本文以74m為成簇分界線. 下面給出其他相關(guān)定義. 定義 2.支撐量 假設(shè)節(jié)點(diǎn)均勻分布，每個(gè)節(jié)點(diǎn)都有符合最優(yōu)跳數(shù)的中繼，則支撐量src(dtoBS，dtoBS-max)表示以最優(yōu)跳數(shù)的路徑傳輸數(shù)據(jù)時(shí)，基站某方向射線上距基站dtoBS的位置所承擔(dān)的最大消耗(實(shí)際節(jié)點(diǎn)密度可能不這么高)，用于表示多跳傳輸時(shí)某位置‘熱’的程度.其公式如式(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ù)傳輸時(shí)，在mr(mr=1，2，3，…，ms)區(qū)(最優(yōu)跳數(shù)形成的路徑會(huì)經(jīng)過朝向基站的每一個(gè)區(qū))距基站dtoBS的節(jié)點(diǎn)收發(fā)數(shù)據(jù)所耗的能量；dtoBS-max為從基站發(fā)射的沿某方向的射線與網(wǎng)絡(luò)邊界交點(diǎn)到基站的距離，也既該射線方向dtoBS的最大值.rc(ms，mr，dtoBS，dtoBS-max)公式如(13)所示.假設(shè)dtoBS-max=300，則以dtoBS為自變量src(dtoBS，dtoBS-max)的曲線為圖2所示，從圖中可以看出簇外能耗情況類似波浪并非線性地與節(jié)點(diǎn)距基站的距離相關(guān). 圖2 dtoBS-max=300支撐量分布情況Fig.2 Distribution of src when dtoBS-max=300 定義3.最優(yōu)前向路由消耗frc(dtoBS) 用來表示距基站dtoBS的節(jié)點(diǎn)，以最優(yōu)跳數(shù)發(fā)送1bit數(shù)據(jù)所耗能量，公式如式(14)所示. (14) 下面將按輪循環(huán)機(jī)制詳細(xì)介紹本算法. 首輪時(shí)，在節(jié)點(diǎn)部署完畢后，基站會(huì)發(fā)送一個(gè)“hello”消息至網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，節(jié)點(diǎn)Si根據(jù)接收到的信號(hào)強(qiáng)度大小估算自身到基站的距離dis，確定自己所屬分區(qū)，區(qū)號(hào)等于hop(dis)，以表征各節(jié)點(diǎn)最優(yōu)跳數(shù)特征. 為競(jìng)選出均勻分布的簇頭，距基站小于74m的節(jié)點(diǎn)不競(jìng)選簇頭，競(jìng)爭(zhēng)半徑為0，距基站大于74m的節(jié)點(diǎn)賦予相同的競(jìng)爭(zhēng)半徑Rcmp.為避免熱區(qū)內(nèi)的節(jié)點(diǎn)因簇外數(shù)據(jù)傳輸任務(wù)過重而能量耗盡，為每一個(gè)節(jié)點(diǎn)設(shè)置一個(gè)入簇半徑，以調(diào)節(jié)節(jié)點(diǎn)出任簇頭時(shí)所在簇的規(guī)模.簇頭節(jié)點(diǎn)Si的簇內(nèi)能耗主要為接收簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)消耗，簇外能耗主要體現(xiàn)在支撐量上(兩者為估計(jì)值，后面節(jié)點(diǎn)要根據(jù)實(shí)際能耗情況入簇)，假設(shè)節(jié)點(diǎn)均勻分布，若要通過減少簇內(nèi)能耗供中繼使用有： (15) 其中：NS為節(jié)點(diǎn)數(shù)量；S為網(wǎng)絡(luò)面積，則等式左邊為預(yù)計(jì)縮小入簇半徑時(shí)預(yù)留給中繼使用的能量，其在一定程度上反映了節(jié)點(diǎn)密度信息；Ri為簇頭Si的入簇半徑；dborder-i為基站沿節(jié)點(diǎn)Si方向的射線與邊界的交點(diǎn)到基站的距離(本文假設(shè)基站在網(wǎng)絡(luò)中央)，將Ri解出有： (16) 通常而言發(fā)揮入簇優(yōu)勢(shì)時(shí)，簇內(nèi)耗能會(huì)比簇外耗能要大，則上式衡有解，且上式表明，較熱區(qū)域內(nèi)的節(jié)點(diǎn)會(huì)被分配較小的入簇半徑，以平衡節(jié)點(diǎn)成為簇頭后的簇內(nèi)簇外路由能耗.該式綜合了簇內(nèi)簇外的具體能耗，與同類算法比例化距基站距離等因素來調(diào)節(jié)簇規(guī)模相比要精確些. 首輪后，基站在這一階段會(huì)廣播CYCLE_START報(bào)文給所有節(jié)點(diǎn)，報(bào)文包括上一輪到基站距離大于74m的存活節(jié)點(diǎn)的平均剩余能量和存活節(jié)點(diǎn)數(shù)，這些數(shù)據(jù)由節(jié)點(diǎn)發(fā)送到基站的數(shù)據(jù)包中解析而來. 非均勻成簇的過程包括：選舉候選簇頭、簇頭選舉、普通節(jié)點(diǎn)入簇三個(gè)階段.在前兩個(gè)階段中，考慮到一些應(yīng)用基本信息大小與數(shù)據(jù)包大小之比較大或節(jié)點(diǎn)密度較大時(shí)，若節(jié)點(diǎn)相互交換基本信息總耗能會(huì)過大，故UCOH算法用基站廣播最重要的公共能量信息成簇，而不考慮其他因素. 3.2.1 選舉候選簇頭 選舉候選簇頭時(shí)，首先各個(gè)節(jié)點(diǎn)依隨機(jī)數(shù)(0-1)與閾值比較，若小于閾值則出任候選簇頭，非候選簇頭節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)到簇頭選舉結(jié)束.所用的閾值公式改進(jìn)自LEACH算法，對(duì)于節(jié)點(diǎn)Si來說其閾值函數(shù)如式(17)所示. (17) 3.2.2 簇頭選舉 UCOH算法在此階段采用計(jì)時(shí)廣播機(jī)制代替UCDP[11]算法協(xié)商機(jī)制來競(jìng)選簇頭，以節(jié)省基本信息交換能耗. 對(duì)于距基站大于74m的候選簇頭，計(jì)時(shí)廣播機(jī)制讓等待時(shí)間較短的候選簇頭先廣播獲勝消息，鄰居節(jié)點(diǎn)收到獲勝信息則退出競(jìng)選.節(jié)點(diǎn)Si的鄰居節(jié)點(diǎn)定義如式(18)所示. Di={Sj|Sj是候選簇首，且dij (18) 候選節(jié)點(diǎn)Si的等待時(shí)間ti改進(jìn)自DEBUC算法，其公式如式(19)所示. (19) 簇頭競(jìng)選完成后，各簇頭以2倍d0為半徑廣播入簇報(bào)文CH_ADV_MSG，喚醒處于休眠狀態(tài)的普通節(jié)點(diǎn)，該報(bào)文包括簇頭的ID、入簇半徑、距基站的距離和剩余能量，供普通節(jié)點(diǎn)判斷加入哪一個(gè)簇更優(yōu). 3.2.3 普通節(jié)點(diǎn)入簇 為使簇內(nèi)節(jié)點(diǎn)規(guī)模符合熱區(qū)和平衡能耗，入簇方法如下：如果節(jié)點(diǎn)位于某些簇頭的入簇半徑內(nèi)，則節(jié)點(diǎn)在那些入簇半徑包含該節(jié)點(diǎn)的簇頭中選擇距離引力最大的簇入簇，如果節(jié)點(diǎn)不在任何簇頭的入簇半徑內(nèi)，則節(jié)點(diǎn)在收到的入簇信息中選擇信號(hào)強(qiáng)度最強(qiáng)的簇入簇，在網(wǎng)絡(luò)生命周期后期，如果沒有入簇信息，則將數(shù)據(jù)直接發(fā)送到基站.改進(jìn)的距離引力具體化了UCDP算法中的距離因素，考慮了簇頭的剩余能量、節(jié)點(diǎn)發(fā)送數(shù)據(jù)能耗和簇頭最優(yōu)前向路由消耗，公式如式(20)所示. (20) 其中：Si表示普通節(jié)點(diǎn)；CHj表示簇頭；E(CHj)表示簇頭的剩余能量；di-CHj表示節(jié)點(diǎn)Si和簇頭CHj的距離.上式說明，普通節(jié)點(diǎn)會(huì)選擇剩余能量較大，距離較近，并且前向數(shù)據(jù)傳輸消耗小的簇頭，以均衡負(fù)載和降低能耗.選擇好簇頭后，節(jié)點(diǎn)發(fā)送JOIN_CLUSTER_MSG報(bào)文通知相應(yīng)簇頭.簇形成后，簇頭會(huì)在簇內(nèi)廣播TDMA時(shí)隙，各節(jié)點(diǎn)按時(shí)隙通信.當(dāng)簇頭收集簇內(nèi)數(shù)據(jù)并融合完畢后，進(jìn)入數(shù)據(jù)傳輸階段. 本算法采用簇內(nèi)單跳和簇外多跳中繼的數(shù)據(jù)傳輸方式，中繼節(jié)點(diǎn)在候選簇頭中選擇.利用候選簇頭作中繼不會(huì)在競(jìng)選副簇頭、區(qū)頭上耗能，并防止如文獻(xiàn)[17]收集源節(jié)點(diǎn)廣播半徑內(nèi)所有節(jié)點(diǎn)的基本信息，導(dǎo)致信息收集耗能過多，節(jié)能效益反而降低的情形.下文將簇頭或中繼節(jié)點(diǎn)特定廣播范圍內(nèi)的候選簇頭稱作該廣播范圍的鄰居候選簇頭(不包括本輪出任簇頭的節(jié)點(diǎn)).傳輸策略總結(jié)如下： a)距基站74m以內(nèi)的普通節(jié)點(diǎn)或中繼將數(shù)據(jù)直接發(fā)送到基站； b)從圖2可以看出距基站大于74m小于dc(1)的節(jié)點(diǎn)所處區(qū)域較熱，應(yīng)首要考慮能量平衡，所以將考慮是否繼續(xù)中繼，在該范圍內(nèi)的簇頭或中繼節(jié)點(diǎn)，以距基站的距離廣播探測(cè)信息，在廣播范圍內(nèi)的鄰居候選簇頭判斷自己是否距基站更近并距基站小于74m，若是則將自己的基本信息發(fā)回簇頭或中繼節(jié)點(diǎn)(為使基本信息交換能耗不至過大，將在第4節(jié)整定候選簇頭出任概率)，簇頭或中繼節(jié)點(diǎn)Si構(gòu)建每個(gè)鄰居候選簇頭Sj的信息表，如表1所示，用以尋找中繼. 表1 節(jié)點(diǎn)Sj信息表Table 1 Information of node Sj 設(shè)Si鄰居候選簇頭集為Dn-i，則在節(jié)點(diǎn)集合 c)距基站大于dc(1)的簇頭或中繼節(jié)點(diǎn)Si以dc(1)為廣播半徑，以和上文類似的方式維護(hù)一個(gè)鄰居候選簇頭集合，首先，若鄰居候選簇頭Sj的剩余能量與Si探測(cè)到的所有鄰居候選簇頭平均剩余能量的比值小于一定比值，則不通過Sj中繼，以保障能耗平衡，Sj比值公式Vj如式(21). (21) (22) g(dij)= (23) (24) (25) 以上公式中f(x1，x2)表示多跳比單跳所節(jié)省的能量差的比率0 算法 1.整體算法流程 Step1.如果是首輪，基站先廣播“hello”報(bào)文，各節(jié)點(diǎn)根據(jù)式(4)、(16)計(jì)算區(qū)號(hào)和入簇半徑.之后基站廣播CYCLE_START報(bào)文. Step2.各節(jié)點(diǎn)根據(jù)式(17)出任候選簇頭，并根據(jù)式(19)競(jìng)爭(zhēng)簇頭，普通節(jié)點(diǎn)根據(jù)3.2小節(jié)入簇策略入簇. Step3.距基站74m以內(nèi)的普通節(jié)點(diǎn)(或之后中繼)直接將數(shù)據(jù)發(fā)送到基站.簇頭收集簇內(nèi)數(shù)據(jù)并融合. Step4.對(duì)于距基站74m以外的每個(gè)簇頭和中繼候選簇頭Si，Si發(fā)出探測(cè)信息獲得Dn-i，若Dn-i為空，則將數(shù)據(jù)直接發(fā)往基站，否則：若Si到基站距離處于74到dc(1)之間，則從Droute中選取使dij最小的Sj做下一跳； 若Si到基站距離大于dc(1)，選擇Dn-i中能量梯度最大的且符合式(21)的節(jié)點(diǎn)做下一跳，沒有符合條件的節(jié)點(diǎn)則將數(shù)據(jù)直接發(fā)送到基站.所有節(jié)點(diǎn)傳輸完畢，進(jìn)入下一輪，轉(zhuǎn)Step 1. 為了驗(yàn)證所提算法的性能，本文基于MATLAB 平臺(tái)對(duì)DEBUC、UCDP、SNNUC、UCOH算法進(jìn)行仿真，對(duì)比多項(xiàng)指標(biāo).假設(shè)傳感器網(wǎng)絡(luò)覆蓋邊長為L的正方形區(qū)域，基站位于區(qū)域中央，無線通信能耗模型的相關(guān)參數(shù)詳見第2節(jié)，其他實(shí)驗(yàn)環(huán)境參數(shù)如表2所示. 表2 實(shí)驗(yàn)參數(shù)Table 2 Experimental parameters 候選簇頭出任概率p的值在一定程度上影響著算法的性能，p過小不能發(fā)揮成簇的優(yōu)勢(shì)，p增大時(shí)雖然有更大概率找到符合最優(yōu)跳數(shù)的中繼候選簇頭，但會(huì)在成簇階段和路由階段產(chǎn)生較大的信息交換能耗，本文通過實(shí)驗(yàn)分析確定本算法的最優(yōu)p值.以L=400，NS=1600為例，調(diào)整p值(0.03-0.21)觀測(cè)網(wǎng)絡(luò)第一個(gè)節(jié)點(diǎn)、10%節(jié)點(diǎn)、30%節(jié)點(diǎn)死亡時(shí)網(wǎng)絡(luò)運(yùn)行輪數(shù)變化情況，得到如圖3數(shù)據(jù). 圖3 節(jié)點(diǎn)死亡輪數(shù)變化曲線Fig.3 Variation curve of cycle of nodes death 從圖3中可以看出：a)當(dāng)p較小時(shí)，簇頭數(shù)目較少，負(fù)載大，且一小部分節(jié)點(diǎn)入簇耗費(fèi)能量較大，第一個(gè)節(jié)點(diǎn)死亡時(shí)間較早；b)當(dāng)p再次增大時(shí)，節(jié)點(diǎn)入簇能耗和路由階段節(jié)點(diǎn)構(gòu)建路由表能耗增加，導(dǎo)致30%節(jié)點(diǎn)死亡的輪數(shù)提前；c)10%節(jié)點(diǎn)死亡后，其余節(jié)點(diǎn)成批迅速死亡，其原因一是本文的一些平衡策略起作用(如入簇半徑)，且節(jié)點(diǎn)剩余能量都較小，原因二是死亡節(jié)點(diǎn)通常是熱區(qū)中路由消耗較小的節(jié)點(diǎn)，一旦它們死亡，路由消耗會(huì)成倍增加.本文取三個(gè)時(shí)間點(diǎn)的運(yùn)行輪數(shù)都較高的概率為最優(yōu)的候選簇頭概率，本例的最優(yōu)概率為0.11，其他規(guī)模網(wǎng)絡(luò)所取概率見4.3節(jié). 本文將網(wǎng)絡(luò)死亡節(jié)點(diǎn)數(shù)達(dá)到30%視為網(wǎng)絡(luò)失效[9].為觀測(cè)UCOH算法在不同場(chǎng)景的性能，分別固定網(wǎng)絡(luò)范圍和固定節(jié)點(diǎn)數(shù)觀測(cè)比較4種算法首節(jié)點(diǎn)死亡和30%節(jié)點(diǎn)死亡時(shí)網(wǎng)絡(luò)運(yùn)行輪數(shù).圖4為固定網(wǎng)絡(luò)范圍L=400，NS∈NA時(shí)4種算法對(duì)比，UCOH算法候選簇頭概率隨節(jié)點(diǎn)數(shù)目增大依次取0.12，0.11，0.11，0.1，0.09，Rcmp取45，45，45，40，40. 圖4 網(wǎng)絡(luò)范圍固定時(shí)的網(wǎng)絡(luò)壽命對(duì)比Fig.4 Comparation of network lifetime with fixed network range 從圖4中可以看出隨著節(jié)點(diǎn)數(shù)目的增大，各算法兩個(gè)時(shí)間點(diǎn)的相應(yīng)輪數(shù)基本上均有增加.當(dāng)節(jié)點(diǎn)數(shù)較少時(shí)，節(jié)點(diǎn)信息交換能耗較少，SNNUC和UCDP算法競(jìng)選簇頭時(shí)考慮的因素更周全，使得二者性能高于UCOH算法.當(dāng)節(jié)點(diǎn)數(shù)目較多時(shí)，UCDP算法成簇協(xié)商能耗較大，節(jié)點(diǎn)數(shù)為2000時(shí)的運(yùn)行輪數(shù)有所降低，性能差于SNNUC算法，而SNNUC與UCOH算法相比而言，UCOH算法的近基站節(jié)點(diǎn)能耗和成簇階段信息交換能耗較少，并且多跳路徑更優(yōu)降低了路由能耗，故UCOH算法在兩個(gè)時(shí)間點(diǎn)的運(yùn)行輪數(shù)最高. 圖5為固定節(jié)點(diǎn)數(shù)目NS=1600，L∈LA時(shí)運(yùn)行輪數(shù)對(duì)比，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ò)范圍增大時(shí)，節(jié)點(diǎn)距基站的平均距離更遠(yuǎn)，各算法兩個(gè)時(shí)間點(diǎn)的運(yùn)行輪數(shù)有降低趨勢(shì).規(guī)模較大時(shí)，密度較低，UCOH算法的熱區(qū)評(píng)估準(zhǔn)確性降低，但多跳跳數(shù)更優(yōu)，性能相比之下有所下降，但不為最差.當(dāng)規(guī)模較小時(shí)，UCDP算法即使在近基站成簇收益不能補(bǔ)償成簇能耗的情況下也會(huì)頻繁競(jìng)選區(qū)頭和簇頭，并且它與DEBUC算法的競(jìng)爭(zhēng)半徑未考慮節(jié)點(diǎn)密度，節(jié)點(diǎn)能耗均衡性不佳，造成兩者運(yùn)行輪數(shù)較低.UCOH算法熱區(qū)量化較為精確，節(jié)點(diǎn)入簇更合理，加之采用相應(yīng)策略防止了近基站能耗和信息交換能耗過大，故性能最好.綜合圖4圖5及其分析說明UCOH算法更適用于密度較大的網(wǎng)絡(luò). 圖5 節(jié)點(diǎn)數(shù)固定時(shí)的網(wǎng)絡(luò)壽命對(duì)比Fig.5 Comparation of network lifetime with fixed number of nodes 圖6為L=400，NS=2000和L=200，NS=1600時(shí)網(wǎng)絡(luò)失效前的全局剩余能量曲線.可以看出密度較大時(shí)UCOH算法的能耗速率低于其他三種算法，例如在L=400，NS=2000的場(chǎng)景下，網(wǎng)絡(luò)運(yùn)行到450輪時(shí)，DEBUC、UCDP、SNNUC、UCOH網(wǎng)絡(luò)剩余能量分別為：76.4J，98.2J，116.9J，159.8J，說明UCOH算法在平衡與節(jié)約能耗方面是有效的.而其中原因在于UCOH算法利用基站廣播公共信息，限制近基站成簇，優(yōu)化了跳數(shù)和中繼節(jié)點(diǎn)，從而減緩了能耗速率.因此，與另外三種算法相比，UCOH算法更適用于密度較大的網(wǎng)絡(luò). 圖6 全局剩余能量變化曲線Fig.6 Variation curve of the global residual energy of nodes 基于大密度的WSNs應(yīng)用，本文在研究多跳網(wǎng)絡(luò)最優(yōu)跳數(shù)的基礎(chǔ)上提出了一種非均勻時(shí)間競(jìng)爭(zhēng)分簇算法，核心思想是：利用最優(yōu)跳數(shù)指導(dǎo)簇規(guī)模的調(diào)整和下一跳路由的選取，緩解多跳路由中的“熱區(qū)”和節(jié)省能量；通過限定成簇區(qū)域，減少近基站節(jié)點(diǎn)能耗；利用時(shí)間競(jìng)爭(zhēng)簇頭，節(jié)省節(jié)點(diǎn)信息交換的能耗；利用候選簇頭中繼，平衡節(jié)點(diǎn)負(fù)載.最終實(shí)驗(yàn)結(jié)果表明，對(duì)于密度較大的網(wǎng)絡(luò)，本算法能有效節(jié)省網(wǎng)絡(luò)能量，均衡能耗，延長特定生命周期特征的網(wǎng)絡(luò)壽命. 本算法在仿真實(shí)驗(yàn)中有較好的性能，但還不適用于節(jié)點(diǎn)異構(gòu)和節(jié)點(diǎn)可移動(dòng)的網(wǎng)絡(luò)，下一步將探索研究該類網(wǎng)絡(luò)的路由算法.
3 UCOH算法描述及分析
3.1 輪初始化
3.2 非均勻成簇
3.3 數(shù)據(jù)傳輸階段
4 仿真與性能分析
4.1 仿真環(huán)境
4.2 候選簇頭概率的確定
4.3 生存周期
4.4 能量效率
5 結(jié)束語
