康 琳，董增壽

（太原科技大學(xué)電子信息工程學(xué)院，太原030024）

無線傳感器網(wǎng)絡(luò)被越來越多地應(yīng)用于森林火災(zāi)監(jiān)控、戰(zhàn)場狀況檢測、動物行為監(jiān)控等領(lǐng)域。在這些應(yīng)用中，采用電池供電的傳感器節(jié)點(diǎn)被隨機(jī)地部署在無人到達(dá)的惡劣環(huán)境中，節(jié)點(diǎn)的再供電幾乎是不可能的，在能量受限的傳感網(wǎng)絡(luò)中，設(shè)計(jì)能量有效的路由策略以延長網(wǎng)絡(luò)的生存時(shí)間成為亟待解決的問題。

傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)之間常形成簇狀的分層拓?fù)?，被選中的簇頭節(jié)點(diǎn)CH（Cluster Head）將成員節(jié)點(diǎn)CM（Cluster Member）收集的數(shù)據(jù)包聚合為單一數(shù)據(jù)，并通過直接通信或CH中繼，將數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)（Sink）［1-2］，CH的數(shù)據(jù)聚合及CH之間的多跳中繼減少了網(wǎng)絡(luò)中冗余數(shù)據(jù)傳輸?shù)哪芎模虼?，網(wǎng)絡(luò)的生存時(shí)間得以延長［3-4］。

但是，在成簇網(wǎng)絡(luò)中，距離sink節(jié)點(diǎn)較近的CH由于承擔(dān)過重的簇間中繼轉(zhuǎn)發(fā)任務(wù)，會過早的耗盡能量而形成“熱點(diǎn)”，引發(fā)網(wǎng)絡(luò)的不連通。文獻(xiàn)［5］設(shè)計(jì)了能量有效的非均勻成簇算法EEUC（Energy Efficient Unequal Clustering），首次提出了競爭半徑的概念，以CH的可變競爭半徑來調(diào)節(jié)簇的大小，使距離sink節(jié)點(diǎn)較近的CH擁有較小的簇，而較遠(yuǎn)的CH形成較大的簇，以均衡CH消耗在簇內(nèi)以及簇間中繼的能量，解決熱點(diǎn)問題，但是，算法的簇頭選舉過程耗能較多。文獻(xiàn)［6］通過優(yōu)化非均勻簇的大小及簇頭輪換均衡了網(wǎng)絡(luò)能耗。特別地，對于節(jié)點(diǎn)分布均勻的傳感器網(wǎng)絡(luò)，文獻(xiàn)［7］設(shè)計(jì)了一種非均勻成簇策略（UCA）來均衡節(jié)點(diǎn)簇內(nèi)及簇間的能耗，延長網(wǎng)絡(luò)生存時(shí)間。文獻(xiàn)［8］將備選CH的剩余能量、與sink節(jié)點(diǎn)的距離以及備選CH的度數(shù)作為模糊量，利用模糊算法選取了最佳CH以及競爭半徑。文獻(xiàn)［9］則基于PSO優(yōu)化算法為非均勻簇選取了最優(yōu)的雙簇頭。文獻(xiàn)［10］利用節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到sink節(jié)點(diǎn)的距離、節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)以及節(jié)點(diǎn)到簇頭的距離來優(yōu)化非均勻簇的簇頭選擇。文獻(xiàn)［11］采用混合蛙跳算法優(yōu)化了簇頭選擇；文獻(xiàn)［12］利用對節(jié)點(diǎn)選票及傳輸距離的加權(quán)，優(yōu)化了非均勻簇的簇頭選取。文獻(xiàn)［13］則利用動態(tài)分簇及基于節(jié)點(diǎn)休眠/喚醒機(jī)制改進(jìn)了非均勻簇的簇間路由。文獻(xiàn)［14］基于網(wǎng)絡(luò)的動態(tài)分區(qū)產(chǎn)生的區(qū)頭以及非均勻簇的簇頭構(gòu)造了最優(yōu)的簇間協(xié)作路由均衡網(wǎng)絡(luò)能耗。

雖然各類的非均勻成簇算法均通過選擇最佳CH、競爭半徑及簇間路由均衡了傳感器網(wǎng)絡(luò)中的能耗分布，解決了熱點(diǎn)問題。但是，在傳感器網(wǎng)絡(luò)每一輪數(shù)據(jù)傳輸開始時(shí)，即使當(dāng)前CH還有足夠的能量完成數(shù)據(jù)傳輸，CH都會得到輪換，而在新CH的競爭選取過程中，競爭CH的節(jié)點(diǎn)需要向整個(gè)網(wǎng)絡(luò)廣播自身的ID號、剩余能量、感知半徑、到sink節(jié)點(diǎn)的距離，用以形成以自身為CH的新的簇內(nèi)通信以及簇間路由。頻繁的CH輪換會引發(fā)過多的廣播能量開銷，進(jìn)而縮短網(wǎng)絡(luò)的生存時(shí)間。

針對頻繁的簇頭輪換對網(wǎng)絡(luò)生存時(shí)間的影響，本文提出了一種基于簇頭分級的改進(jìn)的非均勻成簇算法 CHCI（CH Classified Improved Unequal Clus?tering），來降低網(wǎng)絡(luò)中過多的廣播能量開銷。在一個(gè)簇內(nèi)，設(shè)置主要簇頭節(jié)點(diǎn)（PrimaryCH）以及次要簇頭節(jié)點(diǎn)（Secondary CH），PCH完成簇內(nèi)數(shù)據(jù)的聚合，SCH承擔(dān)簇間數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，為PCH設(shè)置CH輪換閾值，只有當(dāng)前PCH的剩余能量低于CH重選閾值時(shí)，才會啟動CH輪換過程，并將簇間中繼路由的選擇轉(zhuǎn)化為二次規(guī)劃問題，選擇了能耗最低的簇間通信路由，延長網(wǎng)絡(luò)的生存時(shí)間。

本文第1部分對系統(tǒng)模型及場景進(jìn)行了描述。第2部分具體介紹CHCI算法。第3部分通過仿真對比了本算法與經(jīng)典的LEACH以及經(jīng)典的EEUC算法性能的比較，最后，第4部分總結(jié)全文。

1 系統(tǒng)模型

假設(shè)N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在M×M區(qū)域內(nèi)，Sink節(jié)點(diǎn)處于M×M區(qū)域之外，其他基本假設(shè)如下：①Sink節(jié)點(diǎn)位置信息已知。②所有隨機(jī)分布的節(jié)點(diǎn)皆為靜態(tài)節(jié)點(diǎn)。③每一個(gè)節(jié)點(diǎn)有獨(dú)立的ID號和相同的初始能量Eo。④節(jié)點(diǎn)沒有配置GPS，但是在網(wǎng)絡(luò)初始化階段，節(jié)點(diǎn)可以根據(jù)RSSI值計(jì)算自身與sink節(jié)點(diǎn)的距離。⑤節(jié)點(diǎn)可以根據(jù)自身與Sink節(jié)點(diǎn)的距離調(diào)整傳輸半徑。

節(jié)點(diǎn)無線傳輸?shù)哪芎哪Ｐ筒捎靡浑A無線電模型［15］。將每l比特?cái)?shù)據(jù)傳輸d所需要的能耗表示如下：

接收此l比特?cái)?shù)據(jù)的能耗為：

式中：ETx表示發(fā)射節(jié)點(diǎn)能耗，ERx表示接收節(jié)點(diǎn)能耗，Eelec表示每發(fā)送或接收1比特?cái)?shù)據(jù)電路消耗的能耗。l代表傳輸數(shù)據(jù)的長度。ξfs及ξmp分別表示傳感器節(jié)點(diǎn)中放大器在自由空間以及多徑衰落模型下的能耗系數(shù)。當(dāng)d＜d0時(shí)，選用電波傳輸?shù)淖杂煽臻g模型，當(dāng)d≥d0時(shí)采用多徑衰落模型，閾值d0表示如下：

2 CHCI算法

CHCI算法的數(shù)據(jù)傳輸主要分為：PCH選取，簇內(nèi)通信建立，SCH選擇，簇間中繼選擇4個(gè)階段。以下先說明本算法的簇頭分級模型。

2.1 簇頭分級模型

在網(wǎng)絡(luò)初始化階段，Sink向區(qū)域內(nèi)所有節(jié)點(diǎn)廣播“hello”數(shù)據(jù)包，每一個(gè)節(jié)點(diǎn)根據(jù)RSSI值確定自身距離sink節(jié)點(diǎn)的距離dtosink。而后，為了節(jié)省能量，我們將以隨機(jī)概率μ處于工作狀態(tài)的節(jié)點(diǎn)根據(jù)概率閾值P分為兩類：活躍節(jié)點(diǎn)及睡眠節(jié)點(diǎn)，如表1所示。

表1 節(jié)點(diǎn)工作狀態(tài)區(qū)分

當(dāng)節(jié)點(diǎn)成為活躍節(jié)點(diǎn)后，加入活躍節(jié)點(diǎn)集，并向節(jié)點(diǎn)集中的其余節(jié)點(diǎn)廣播包含自身ID號、剩余能量、當(dāng)前感知半徑信息的HEAD_MSG數(shù)據(jù)包，參與簇頭節(jié)點(diǎn)的競爭。參與競爭節(jié)點(diǎn)的當(dāng)前感知半徑被定義為競爭半徑，用下式表示：

式中，d（i，Sink）表示任意節(jié)點(diǎn)i與 sink之間的距離。dmax及dmin分別表示所有dtosink數(shù)值中的最大以及最小值。c被定義為半徑控制因子，Rini為所有節(jié)點(diǎn)在網(wǎng)絡(luò)初始化時(shí)的半徑。而后，在活躍節(jié)點(diǎn)集中，擁有最高剩余能量的節(jié)點(diǎn)j當(dāng)選為PCH，向其余節(jié)點(diǎn)發(fā)送CONFIRM_CH_MSG數(shù)據(jù)包以確認(rèn)自身的PCH身份，沒有當(dāng)選為PCH的節(jié)點(diǎn)向其周圍的CH節(jié)點(diǎn)發(fā)送JOIN_MSG數(shù)據(jù)包以確認(rèn)自己加入此PCH，成為其成員節(jié)點(diǎn)。對于睡眠節(jié)點(diǎn)，當(dāng)其接收到當(dāng)選PCH廣播的CONFIRM_CH_MSG信息后，變?yōu)榧せ罟?jié)點(diǎn)，向鄰近PCH節(jié)點(diǎn)發(fā)送JOIN_MSG信息，當(dāng)PCH為其分配數(shù)據(jù)傳輸時(shí)隙后，這些節(jié)點(diǎn)會接收到ACK_MSG以確認(rèn)自身已成為該P(yáng)CH的成員節(jié)點(diǎn)。此后，PCH根據(jù)競爭半徑RTH(j)獲得簇的成員數(shù)kin，PCH為kin個(gè)成員節(jié)點(diǎn)分配TDMA時(shí)隙表，來完成簇內(nèi)節(jié)點(diǎn)信息的匯聚，成員節(jié)點(diǎn)只在被分配的時(shí)隙內(nèi)完成數(shù)據(jù)傳輸，在其他節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)則進(jìn)入睡眠狀態(tài)，以減少數(shù)據(jù)包碰撞來減少網(wǎng)絡(luò)的能耗。假定當(dāng)前輪t內(nèi)，每個(gè)成員節(jié)點(diǎn)傳輸l比特?cái)?shù)據(jù)，則簇內(nèi)數(shù)據(jù)收集完成后，PCH的剩余能量為

則當(dāng)前輪t網(wǎng)絡(luò)的平均剩余能量定義為

定義第t輪SCH節(jié)點(diǎn)的選舉因子p(k)為

顯然，我們選擇p(k)較高的節(jié)點(diǎn)作為SCH，將接收到的來自PCH的數(shù)據(jù)傳輸至Sink節(jié)點(diǎn)。其余節(jié)點(diǎn)作為成員節(jié)點(diǎn)將數(shù)據(jù)傳輸至PCH。

2.2 SCH-sink的中繼路由選擇

當(dāng)SCHk從PCH接收到聚合的數(shù)據(jù)后，會廣播一個(gè)包含自身ID號、剩余能量、以及dtosink的STATE_MSG信息給其余SCH，而后節(jié)點(diǎn)k根據(jù)表2選取直接單跳通信或借助其余SCH的多跳通信以完成簇間中繼，將信息傳輸至Sink節(jié)點(diǎn)。

表2 中繼選擇方案

TDmax是判定SCHk采用單跳或多跳通信方式的閾值。

圖1 能量有效路由的中繼節(jié)點(diǎn)選擇示意圖

如圖1，當(dāng)SCHk通過鄰近sink的節(jié)點(diǎn)m作為中繼節(jié)點(diǎn)時(shí)，數(shù)據(jù)傳輸時(shí)耗費(fèi)的能量可以表示為：

為了減少能耗，SCHk需選擇一條經(jīng)過中繼節(jié)點(diǎn)m?的能量有效的路由，節(jié)點(diǎn)m?可通過以下方式選擇：

式中，Ω(k)表示SCHk的一跳鄰居節(jié)點(diǎn)集。

2.3 PCH重選因子

在數(shù)據(jù)傳輸階段，當(dāng)?shù)趖（t≥1）輪數(shù)據(jù)傳輸結(jié)束后，引入PCH重選因子T（t+1）來降低PCH輪換的頻率，T（t+1）可表示為：

表3 CHCI算法中的數(shù)據(jù)傳輸

3 仿真與分析

3.1 算法的消息復(fù)雜度

假定傳感器網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，在執(zhí)行CHCI算法網(wǎng)絡(luò)初始化時(shí)，Sink節(jié)點(diǎn)向N個(gè)節(jié)點(diǎn)廣播“hel?lo”數(shù)據(jù)包，N×P個(gè)節(jié)點(diǎn)被選為激活節(jié)點(diǎn)參與簇頭競爭，會廣播N×P條HEAD_MSG信息，若M個(gè)節(jié)點(diǎn)競選PCH成功，會發(fā)送M條CONFIRM_CH_MSG信息，其余N-M個(gè)節(jié)點(diǎn)收到CONFIRM_CH_MSG信息后，向PCH發(fā)送JOIN_MSG信息，M個(gè)PCH發(fā)送NM個(gè)ACK_MSG信息以確認(rèn)加入節(jié)點(diǎn)被分配了時(shí)隙。簇內(nèi)通信的消息復(fù)雜度為O（N）。簇間路由建立時(shí)，M個(gè)SCH在網(wǎng)絡(luò)內(nèi)產(chǎn)生M條STATE_MSG信息，計(jì)算最佳路由時(shí)，消息復(fù)雜度為O（M）。

若T（t+1）=1，PCH不得到更換，則網(wǎng)絡(luò)中不需要重復(fù)簇內(nèi)通信的建立過程，只需要SCH建立簇間路由，此時(shí)算法的消息負(fù)雜度為O（M），若T（t+1）=0，PCH更換，網(wǎng)絡(luò)重新進(jìn)行簇內(nèi)及簇間通信的建立，由于N?M，算法的消息復(fù)雜度為O（N）。

3.2 仿真參數(shù)設(shè)置

假設(shè)400個(gè)節(jié)點(diǎn)隨機(jī)分布200 m×200 m的區(qū)域內(nèi)。主要仿真參數(shù)參考表4。

本部分通過仿真分析了參數(shù)c，Rini，a，TDmax對網(wǎng)絡(luò)性能的影響，然后比較了CHCI協(xié)議與經(jīng)典的LEACH算法以及非均勻成簇的EEUC算法對網(wǎng)絡(luò)生存時(shí)間以及節(jié)點(diǎn)平均剩余能量的影響。

表4 仿真參數(shù)

3.3 仿真結(jié)果及分析

圖2顯示了參數(shù)c對于首個(gè)死亡節(jié)點(diǎn)出現(xiàn)輪數(shù)的影響，對于一個(gè)確定的初始競爭半徑Rini，c增大時(shí)，競爭簇頭的節(jié)點(diǎn)的競爭半徑減小，網(wǎng)絡(luò)中會出現(xiàn)更多的簇，消耗在簇間中繼通信上的能量增大，相應(yīng)地會縮短網(wǎng)絡(luò)生存時(shí)間，從圖2中可以看到，當(dāng)c=0.6時(shí)，網(wǎng)絡(luò)中的簇的數(shù)量可以均衡簇內(nèi)及簇間能耗，從而延遲首個(gè)死亡節(jié)點(diǎn)出現(xiàn)的輪數(shù)。

圖3顯示了Rini對首個(gè)死亡節(jié)點(diǎn)出現(xiàn)輪數(shù)的影響，當(dāng)Rini增大時(shí)，網(wǎng)絡(luò)中簇的尺寸增大，引起PCH用于簇內(nèi)匯聚的能耗增大，當(dāng)Rini=30 m時(shí)，簇內(nèi)及簇間中繼通信的能耗得到均衡，首個(gè)死亡節(jié)點(diǎn)出現(xiàn)的輪數(shù)出現(xiàn)在850輪，延長了網(wǎng)絡(luò)生存時(shí)間。

圖2 參數(shù)c對網(wǎng)絡(luò)性能的影響

圖3 參數(shù)Rini對網(wǎng)絡(luò)性能的影響

圖4顯示了參數(shù)a對網(wǎng)絡(luò)死亡節(jié)點(diǎn)的影響，當(dāng)進(jìn)行了600輪數(shù)據(jù)傳輸后，若a=0，即沒有選取SCH時(shí)，大概60個(gè)節(jié)點(diǎn)死亡，當(dāng)a=0.4時(shí)，由于SCH分擔(dān)了PCH用于簇間中繼的能耗，降低了PCH的能量損耗，從而降低了PCH輪換的頻率，死亡節(jié)點(diǎn)的數(shù)量達(dá)到最少，SCH的引入降低了網(wǎng)絡(luò)中死亡節(jié)點(diǎn)的數(shù)量，改善了網(wǎng)絡(luò)的性能。

圖5顯示了TDmax對網(wǎng)絡(luò)生存時(shí)間的影響，從表2可知，若TDmax較小簇間通信主要采用中繼通信，若TDmax變大，簇間通信主要采用直接通信，當(dāng)TDmax=140 m時(shí)，網(wǎng)絡(luò)中有更多的節(jié)點(diǎn)存活。

圖4 參數(shù)a對網(wǎng)絡(luò)死亡節(jié)點(diǎn)的影響（r=600）

圖5 參數(shù)TDmax對網(wǎng)絡(luò)性能的影響

圖6、圖7分別比較了LEACH，EEUC，CHCI算法執(zhí)行1200輪后，節(jié)點(diǎn)的平均剩余能量以及存活節(jié)點(diǎn)的數(shù)量，這里將一半節(jié)點(diǎn)死亡定義為網(wǎng)絡(luò)生存時(shí)間的結(jié)束。LEACH算法在執(zhí)行700輪后，一半節(jié)點(diǎn)死亡，采用了非均勻成簇的EEUC算法執(zhí)行750輪后，一半節(jié)點(diǎn)死亡，網(wǎng)絡(luò)不再連通。采用CHCI算法后，由于SCH的存在，節(jié)省了節(jié)點(diǎn)的能耗，增加了節(jié)點(diǎn)的平均剩余能量，從而降低了PCH輪換的頻率，此外，簇間中繼最佳路由的確定也降低了SCH的能耗，網(wǎng)絡(luò)的總體能耗得到降低，生存時(shí)間被延長至900輪。生存時(shí)間比EEUC算法提高了20%。

圖6 節(jié)點(diǎn)平均剩余能量比較

圖7 存活節(jié)點(diǎn)比較

4 結(jié)論

本文設(shè)計(jì)了基于簇頭分級的新的非均勻成簇算法CHCI。在主要簇頭PCH當(dāng)選后，每一個(gè)簇內(nèi)會選出一個(gè)次要簇頭節(jié)點(diǎn)SCH來承擔(dān)簇間中繼轉(zhuǎn)發(fā)任務(wù)，以此降低PCH的能耗。PCH重選因子T（t+1）在每一輪數(shù)據(jù)傳輸結(jié)束時(shí)得到更新，只有在當(dāng)前簇頭的剩余能量低于PCH輪換閾值時(shí)，啟動PCH的輪換，來降低網(wǎng)絡(luò)中由于EEUC算法中CH頻繁更換引起的額外的廣播開銷，延長網(wǎng)絡(luò)的生存時(shí)間，并將SCH傳輸?shù)闹欣^選擇問題通過二次規(guī)劃問題得出能量有效的路由。仿真結(jié)果表明，與LEACH以及非均勻成簇的EEUC算法相比，CHCI算法延長了網(wǎng)絡(luò)生存時(shí)間。

［1］Tian Q，Coyle E J.Optimal Distributed Detection in Clustered Wireless Sensor Networks：The Weighted Median［C］//INFO?COM，2006.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Effi?cient Communication Protocol for Wireless Microsensor Networks.In：Proc of the 33rd Hawaii Int’l Conf on System Science（HICSS 2000），2000：3005-3014.

［3］Engels D W，Sarma S E.The Reader Collision Problem.In：Proc of IEEE International Conference on Systems，Man and Cybernet?ics.SMC，2002.

［4］AbdelSalam H S，Olariu S.Bees：Bioinspired Backbone Selection in Wireless Sensor Networks［J］.Parallel and Distributed Sys?tems，IEEE Transactions on，2012，23（1）：44-51.

［5］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（1）：27-36.

［6］Xiang M，Shi W R，Jiang C J，et al.Energy Efficient Clustering Al?gorithm for Maximizing Lifetime of Wireless Sensor Networks［J］.AEU—Int’l Journal of Electronic and Communication，2010，64（4）：289-298.

［7］Yuan Huiyong，Liu Yongyi，Yu Jiaping.A New Energy-Efficient Unequal Clustering Algorithm for Wireless Sensor Networks［C］//IEEE Conference Proceedings，2011：431-434.

［8］Mao S，Zhao C，Zhou Z，et al.An Improved Fuzzy Unequal Clus?tering Algorithm for Wireless Sensor Network［J］.Mobile Net?works and Applications，2013，18（2）：206-214.

［9］門順治，孫順遠(yuǎn)，徐保國.基于PSO的無線傳感器網(wǎng)絡(luò)非均勻分簇雙簇頭路由算法［J］.傳感技術(shù)學(xué)報(bào)，2014，27（9）：1281-1286.

［10］張文梅，廖福保.改進(jìn)的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法［J］.傳感技術(shù)學(xué)報(bào)，2015，5：21.

［11］劉洲洲，王福豹，張克旺.基于混合蛙跳算法的非均勻分簇WSNs路由協(xié)議［J］.計(jì)算機(jī)應(yīng)用研究，2013，30（7）：2173-2176.

［12］張瑞華，賈智平，程合友.基于非均勻分簇和最小能耗的無線傳感網(wǎng)絡(luò)路由算法［J］.上海交通大學(xué)學(xué)報(bào)，2012，46（11）：1774-1778.

［13］彭鐸，黎鎖平，楊喜娟.一種能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2014，27（12）：1687-1691.

［14］孫彥清，彭艦，劉唐，等.基于動態(tài)分區(qū)的無線傳感器網(wǎng)絡(luò)非均勻成簇路由協(xié)議［J］.通信學(xué)報(bào)，2014，35（1）：198-206.

［15］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Effi?cient Communication Protocol for Wireless Microsensor Networks［C］//System Sciences，2000.Proceedings of the 33rd Annual Ha?waii International Conference on.IEEE，2000，（2）：10.