蔡 釗，馬林華，黃紹城，孫康寧，田 雨

(1.空軍工程大學(xué) 航空航天工程學(xué)院，陜西 西安710038;2.95876 部隊(duì)，甘肅 張掖734100)

0 引 言

分簇算法通過構(gòu)建層次化的拓?fù)浣Y(jié)構(gòu)，依靠簇頭融合作用減少數(shù)據(jù)包發(fā)送量和路由維護(hù)信息量，很大程度上提升了網(wǎng)絡(luò)的能量效率，其中，最具代表性的算法有LEACH［1］，DEEC［2］等。但這些算法要求簇頭與基站之間采用直接通信的方式傳輸數(shù)據(jù)，極大地增加了簇外通信能耗?；诖?，很多采用簇外多跳方式傳輸數(shù)據(jù)的分簇算法［3～6］被提出，但也隨之產(chǎn)生了“熱區(qū)”問題［7～9］。此外，在實(shí)時(shí)性較強(qiáng)的傳感器網(wǎng)絡(luò)中，要求部分?jǐn)?shù)據(jù)需在指定跳數(shù)內(nèi)到達(dá)基站。目前，雖有一些基于最小跳數(shù)的分簇路由算法［10，11］被提出，但此類算法并不能保證所有緊急數(shù)據(jù)包的傳輸實(shí)時(shí)性。

針對(duì)上述問題，本文提出一種基于跳數(shù)限制的高能 效 分 簇 路 由(hop－constrained energy－efficient clustering routing，HCECR)算法，其相較于傳統(tǒng)算法有三個(gè)創(chuàng)新點(diǎn):1)根據(jù)網(wǎng)絡(luò)規(guī)定的跳數(shù)限制、簇成員數(shù)量及簇內(nèi)平均通信開銷，構(gòu)建兼顧能量效率并滿足跳數(shù)要求的簇結(jié)構(gòu);2)針對(duì)普通數(shù)據(jù)，在簇間通信中引入了普通節(jié)點(diǎn)的中繼機(jī)制，提高簇頭與普通節(jié)點(diǎn)之間的負(fù)載均衡度，同時(shí)減弱基站附近的“熱區(qū)”效應(yīng);3)在數(shù)據(jù)包傳輸階段，簇頭根據(jù)接收數(shù)據(jù)包剩余跳數(shù)區(qū)分緊急和普通數(shù)據(jù)包，并針對(duì)性采取不同的轉(zhuǎn)發(fā)機(jī)制。

1 系統(tǒng)模型假設(shè)

在場(chǎng)景設(shè)置上，僅考慮一個(gè)基站、n 個(gè)同構(gòu)節(jié)點(diǎn)的情況，全部節(jié)點(diǎn)隨機(jī)布撒且不具有移動(dòng)性。基站無功率限制，傳輸區(qū)域能夠覆蓋整個(gè)區(qū)域。網(wǎng)絡(luò)內(nèi)每個(gè)數(shù)據(jù)包均設(shè)置有最大跳數(shù)，根據(jù)取值不同分為緊急數(shù)據(jù)和普通數(shù)據(jù)。其中，緊急數(shù)據(jù)具有極強(qiáng)的時(shí)效性，需要在指定跳數(shù)(跳數(shù)屬于固定區(qū)間)內(nèi)到達(dá)基站。

傳感器節(jié)點(diǎn)廣播信息時(shí)使用全向天線，通信區(qū)域?yàn)閳A形，并可以利用非對(duì)稱鏈路進(jìn)行通信。節(jié)點(diǎn)具有感知自身位置的能力，且發(fā)射功率可以調(diào)整，共有n 個(gè)離散的發(fā)射功率，即p1，p2，…，pn，其中，pn=pmax。為保證數(shù)據(jù)包的時(shí)效性需求，假定所有簇頭均能與基站直接通信。

2 HCECR 算法

算法由很多輪次組成，每個(gè)輪次分為分簇階段和數(shù)據(jù)傳輸階段。其中，分簇階段又可被劃分為三個(gè)步驟:1)分簇信息泛洪;2)簇頭選舉;3)簇成員劃分。

2.1 分簇信息泛洪

分簇信息泛洪階段，各節(jié)點(diǎn)要廣播自身分簇(CL)信息，并依據(jù)收到的分簇信息構(gòu)建鄰居隊(duì)列。其中，分簇信息由六部分組成:源節(jié)點(diǎn)地址S_Add、坐標(biāo)S_Pos(x，y)、上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)地址L_Add、坐標(biāo)L_Pos(x，y)、數(shù)據(jù)包剩余跳數(shù)R_hop、源節(jié)點(diǎn)至當(dāng)前節(jié)點(diǎn)的累計(jì)最小可達(dá)能耗TMRC。當(dāng)節(jié)點(diǎn)i 要發(fā)送初始分簇信息時(shí)，各參數(shù)應(yīng)按照式(1)進(jìn)行設(shè)置

節(jié)點(diǎn)收到鄰居CL 信息后，忽略源節(jié)點(diǎn)地址相同且TMRC取值更大的信息和剩余跳數(shù)為0 的信息，利用剩余信息更新鄰居表。首先計(jì)算自身到上一跳節(jié)點(diǎn)的距離，并利用式(2)得出最小可達(dá)能耗。假設(shè)當(dāng)前節(jié)點(diǎn)為i，上一跳節(jié)點(diǎn)為last(i)，則傳輸長(zhǎng)度為l 數(shù)據(jù)包的最小可達(dá)能耗為

節(jié)點(diǎn)將數(shù)據(jù)包剩余跳數(shù)減一，并將最小可達(dá)能耗與原數(shù)據(jù)包中的TMRC 進(jìn)行累加，得出從源節(jié)點(diǎn)到自身的TMRC

計(jì)算出TMRC(i)和數(shù)據(jù)包剩余跳數(shù)后，節(jié)點(diǎn)要利用處理后的CL 信息更新鄰居隊(duì)列，并將L_Add 和L_Pos(x，y)分別替換為自身地址和坐標(biāo)，再次轉(zhuǎn)發(fā)此CL 信息。

2.2 簇首選舉

經(jīng)過t0時(shí)間后將進(jìn)入簇頭選舉階段，簇首的選取需綜合考慮節(jié)點(diǎn)剩余能量、簇內(nèi)平均通信開銷和成員數(shù)量，簇頭權(quán)值表達(dá)式見式(4)。每個(gè)節(jié)點(diǎn)計(jì)算出自身的簇頭權(quán)值后將進(jìn)行廣播，同時(shí)接收鄰居的簇頭權(quán)值。若節(jié)點(diǎn)的簇頭權(quán)值高于所有鄰居的取值，則向基站推舉自己為潛在簇頭;否則，作為普通節(jié)點(diǎn)?；靖鶕?jù)各潛在簇頭的簇頭權(quán)值和鄰居隊(duì)列確定正式簇頭，并廣播正式簇頭信息

式中 wCH(k)為k 的簇頭權(quán)值，Qs為鄰居隊(duì)列的元素個(gè)數(shù)，ER(k)和E0(K)分別為節(jié)點(diǎn)k 的剩余能量和初始能量。

2.3 簇成員劃分

每個(gè)正式簇頭需向自身鄰居隊(duì)列中的所有成員發(fā)送簇頭聲明(CHS)信息，CHS 信息包含五項(xiàng)內(nèi)容:簇頭地址、目的節(jié)點(diǎn)地址、上一跳節(jié)點(diǎn)地址、上一跳節(jié)點(diǎn)坐標(biāo)和TMRC。其中，目的節(jié)點(diǎn)即為簇成員，上一跳節(jié)點(diǎn)為最近轉(zhuǎn)發(fā)CHS信息的節(jié)點(diǎn)，TMRC 則代表從簇頭至簇成員的累計(jì)最小可達(dá)能耗，此項(xiàng)可由簇頭查找鄰居隊(duì)列得到。普通節(jié)點(diǎn)根據(jù)收到的CHS 信息，判斷自身是否屬于某個(gè)簇頭的成員，若不屬于任何簇，則聲明自身為正式簇頭;若僅屬于一個(gè)簇頭，則成為該簇的成員;若同時(shí)屬于多個(gè)簇頭，則加入TMRC 取值最小的簇，并將自身屬于多個(gè)簇的情況告知這些簇頭。特別地，滿足第三種情況的節(jié)點(diǎn)可以承擔(dān)簇外的中繼任務(wù)，減小簇頭的轉(zhuǎn)發(fā)能耗。

假設(shè)節(jié)點(diǎn)p，q 分別為簇頭i，j 的成員，k 為兩個(gè)簇的共有成員，即j∈B(i，j)。此時(shí)，若節(jié)點(diǎn)i 向j 傳輸?shù)氖瞧胀〝?shù)據(jù)包，則應(yīng)當(dāng)采用簇間的多跳中繼，如圖1 虛線所示。若為緊急數(shù)據(jù)包，則要采用簇間的直接通信(圖1 中直線)或基站的直接通信。

圖1 簇外通信示意圖Fig 1 Diagram of outer-cluster communication

在簇劃分結(jié)束后，普通節(jié)點(diǎn)根據(jù)CHS 信息中的上一跳坐標(biāo)和自身坐標(biāo)，計(jì)算兩點(diǎn)間距離并調(diào)整自身傳輸半徑。當(dāng)兩點(diǎn)間距離滿足:rm－1＜d(i，next(i))＜rm時(shí)，將傳輸半徑調(diào)整為rm。雖然節(jié)點(diǎn)調(diào)整發(fā)射功率造成了部分非對(duì)稱鏈路，但這并不影響簇內(nèi)數(shù)據(jù)的匯聚。因?yàn)閿?shù)據(jù)包向簇頭匯聚的路徑是單向的，而當(dāng)簇頭需要向成員傳輸數(shù)據(jù)時(shí)，由于已知其坐標(biāo)可采用直接通信。

2.4 節(jié)點(diǎn)類型與數(shù)據(jù)包類型

在數(shù)據(jù)傳輸階段，網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)包共分為三類，即感知、融合和中繼數(shù)據(jù)包。傳感器節(jié)點(diǎn)探測(cè)環(huán)境產(chǎn)生感知數(shù)據(jù)包，將其發(fā)送給對(duì)應(yīng)簇頭，簇頭接收成員感知數(shù)據(jù)包后進(jìn)行數(shù)據(jù)融合得到融合數(shù)據(jù)包。而中繼數(shù)據(jù)包是針對(duì)普通融合數(shù)據(jù)包進(jìn)行簇外多跳通信而設(shè)立的，旨在降低轉(zhuǎn)發(fā)能耗。

簇頭向基站傳輸融合數(shù)據(jù)包分為快速模式和正常模式?？焖倌Ｊ结槍?duì)緊急的融合數(shù)據(jù)包，即滿足R_hop∈［hmin，hup］的數(shù)據(jù)包。當(dāng)簇頭節(jié)點(diǎn)收到數(shù)據(jù)包的剩余跳數(shù)滿足下式時(shí):1 ＜R_hop≤hup，采用簇外多跳路由，將數(shù)據(jù)傳輸給相鄰簇頭中距離基站最近的一個(gè)簇頭。而當(dāng)數(shù)據(jù)包剩余跳數(shù)為1 時(shí)，簇頭將直接把數(shù)據(jù)傳輸?shù)交尽?/p>

相比之下，正常模式是能量效率更高的傳輸模式，在傳輸普通融合數(shù)據(jù)包時(shí)使用。在簇外多跳通信中，融合數(shù)據(jù)包先由簇頭直接發(fā)送給多簇頭交叉集內(nèi)的邊緣節(jié)點(diǎn)，邊緣節(jié)點(diǎn)將數(shù)據(jù)包類型改為中繼包，并通過簇內(nèi)多跳的方式傳給下一跳簇頭。

圖2 描述了不同節(jié)點(diǎn)類型可以發(fā)送、接收、轉(zhuǎn)發(fā)數(shù)據(jù)包的類型。簇頭可以發(fā)送、轉(zhuǎn)發(fā)融合數(shù)據(jù)包，而普通傳感器節(jié)點(diǎn)將忽略融合數(shù)據(jù)包，只發(fā)送、轉(zhuǎn)發(fā)感知數(shù)據(jù)包或中繼數(shù)據(jù)包。特殊地，處于兩個(gè)簇頭交叉集內(nèi)的邊緣節(jié)點(diǎn)可以轉(zhuǎn)發(fā)融合數(shù)據(jù)包。當(dāng)簇頭產(chǎn)生一個(gè)融合數(shù)據(jù)包后，其可以將數(shù)據(jù)包傳給邊緣節(jié)點(diǎn)，再由邊緣節(jié)點(diǎn)通過簇內(nèi)多跳的方式傳給下一個(gè)簇頭，也可以直接傳給下一跳簇頭或基站。需要注意的是，若邊緣節(jié)點(diǎn)需要通過普通節(jié)點(diǎn)進(jìn)行中繼，需先將融合數(shù)據(jù)包轉(zhuǎn)換為中繼數(shù)據(jù)包。

圖2 節(jié)點(diǎn)類型與數(shù)據(jù)包類型對(duì)應(yīng)圖Fig 2 Node type corresponding to data packet type

2.5 能耗模型

根據(jù)簇頭鄰居隊(duì)列中存儲(chǔ)的累計(jì)最小可達(dá)能耗和剩余跳數(shù)等信息，可知單次簇內(nèi)通信的平均開銷

在僅考慮簇內(nèi)數(shù)據(jù)匯聚能耗、忽略中繼其他簇?cái)?shù)據(jù)的情況下，普通節(jié)點(diǎn)在一個(gè)采樣周期內(nèi)的能量消耗為

式中 DDN為網(wǎng)絡(luò)的平均節(jié)點(diǎn)度。由于簇內(nèi)數(shù)據(jù)融合采用的是樹狀結(jié)構(gòu)，故需要其協(xié)助匯聚數(shù)據(jù)的鄰居數(shù)量是DDN－1。結(jié)合式(5)和規(guī)定的最小跳數(shù)，可以計(jì)算出簇間通信的平均距離

忽略轉(zhuǎn)發(fā)其他簇頭數(shù)據(jù)的情況下，簇頭接收、融合簇內(nèi)成員數(shù)據(jù)，并向基站傳輸自身融合數(shù)據(jù)包的總能耗為

式中 αin，αout和αBS分別為簇頭產(chǎn)生融合數(shù)據(jù)后，選擇簇間多跳傳輸、簇間直接傳輸和基站傳輸?shù)母怕?，αin+αout+αBS=1。結(jié)合這三個(gè)概率能得到當(dāng)前簇(包括簇頭和簇成員)轉(zhuǎn)發(fā)鄰簇融合數(shù)據(jù)的能量開銷

式中 DDCH為下游相鄰簇頭節(jié)點(diǎn)數(shù)量。根據(jù)式(5)～式(9)可知，單個(gè)簇在單個(gè)采樣周期內(nèi)的總能耗為

3 仿真分析

本文選用NS2 和Matlab 作為仿真平臺(tái)，將HCECR 算法與HEED［12］和ECDS［13］算法在過期數(shù)據(jù)包比例、節(jié)點(diǎn)死亡時(shí)間等方面進(jìn)行比較。在數(shù)據(jù)流設(shè)置上，感知、融合和中繼數(shù)據(jù)包的長(zhǎng)度均為500 bits，CL 信息和CHS 信息的長(zhǎng)度分別為120，96 bits。在節(jié)點(diǎn)配置方面，初始能量設(shè)為0.5 J，并假定節(jié)點(diǎn)在能量耗盡前不會(huì)失效。此外，規(guī)定緊急數(shù)據(jù)包跳數(shù)的取值區(qū)間為5～15，普通數(shù)據(jù)的初始跳數(shù)為255。

首先衡量不同算法的能量使用效率，比較最短節(jié)點(diǎn)壽命和最長(zhǎng)節(jié)點(diǎn)壽命。將場(chǎng)景大小設(shè)為400 m×400 m，基站坐標(biāo)定為(200，200)m，分別仿真節(jié)點(diǎn)數(shù)為200，300，400 的三種情況。最短與最長(zhǎng)節(jié)點(diǎn)壽命比較如圖3，圖4。

圖3 最短節(jié)點(diǎn)壽命的比較Fig 3 Comparision of the shortest node lifetime

圖4 最長(zhǎng)節(jié)點(diǎn)壽命的比較Fig 4 Comparision of the longest node lifetime

網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)死亡將極大地影響數(shù)據(jù)的傳輸路徑，增加傳輸能耗，縮短節(jié)點(diǎn)和簇的生存周期，故網(wǎng)絡(luò)內(nèi)首個(gè)節(jié)點(diǎn)死亡時(shí)間代表整簇性能下降的起始時(shí)刻，最后一個(gè)節(jié)點(diǎn)的死亡時(shí)間表明網(wǎng)絡(luò)完全失效的時(shí)刻。兩個(gè)時(shí)間的整體水平可以反映算法的能量效率，而它們的差值能夠體現(xiàn)節(jié)點(diǎn)間能量均衡程度。由圖3、圖4 可知，在不同的節(jié)點(diǎn)數(shù)量的情況下，HCECR 算法的最短節(jié)點(diǎn)壽命和最長(zhǎng)節(jié)點(diǎn)壽命均長(zhǎng)于HEED 和ECDS 算法，且兩者之差也是三種算法中最小的，故此算法的能量效率和能量均衡性在三只算法中都是最好的?？紤]到HCECR 算法中數(shù)據(jù)包有嚴(yán)格的跳數(shù)限制，在轉(zhuǎn)發(fā)過程更多地采用簇頭與基站的直接通信，降低了能量效率，故在不同節(jié)點(diǎn)數(shù)量情況下，比較數(shù)據(jù)包存在跳數(shù)限制和無跳數(shù)限制(跳數(shù)設(shè)為255，算法記為HCECR—W)時(shí)節(jié)點(diǎn)最短、最長(zhǎng)壽命的變化情況，比較結(jié)果如圖5、圖6。

圖5 跳數(shù)限制對(duì)節(jié)點(diǎn)最短壽命的影響Fig 5 Impact of hop limit on the shortest node lifetime

圖6 跳數(shù)限制對(duì)節(jié)點(diǎn)最長(zhǎng)壽命的影響Fig 6 Impact of hop limit on the longest node lifetime

結(jié)合圖5、圖6 可知，無跳數(shù)限制的HCECR—W 算法相比HCECR 算法，具有更長(zhǎng)的節(jié)點(diǎn)壽命。因?yàn)镠CECR—W 算法在簇外通信中，更多地采用了簇間多跳通信，減少了簇間直接通信和簇頭與基站直接通信的次數(shù)，降低了簇外的轉(zhuǎn)發(fā)總能耗。

最后衡量新算法在數(shù)據(jù)包實(shí)時(shí)性方面的提升效果，將三種算法在網(wǎng)絡(luò)運(yùn)行期間內(nèi)失效數(shù)據(jù)包占總數(shù)的比例作為判斷標(biāo)準(zhǔn)。設(shè)場(chǎng)景大小為200 m×200 m，數(shù)據(jù)包跳數(shù)限制設(shè)為2，仿真節(jié)點(diǎn)數(shù)量為50，75，100 的三種情況，如圖7。

圖7 過期數(shù)據(jù)包比例的比較Fig 7 Comparison of ratio of overdue data packets

由圖7 可知，在網(wǎng)絡(luò)運(yùn)行期間，有跳數(shù)限制的HCECR算法無過期數(shù)據(jù)包。而無跳數(shù)限制的HCECR—W 算法則有一定比例的數(shù)據(jù)包過期，且與HEED 和ECDS 兩種算法相比，其隨著節(jié)點(diǎn)數(shù)量的增多，過期數(shù)據(jù)包比例的增長(zhǎng)速度最快。這主要是因?yàn)镠CECR 算法引入了簇間多跳中繼的通信方式，一定程度上增加了轉(zhuǎn)發(fā)總跳數(shù)，導(dǎo)致滿足跳數(shù)要求的數(shù)據(jù)包比例下降。

4 結(jié)束語

本文提出一種基于跳數(shù)限制的分簇路由算法，構(gòu)建了兼顧數(shù)據(jù)實(shí)時(shí)性和能量使用效率的簇結(jié)構(gòu)和路由轉(zhuǎn)發(fā)機(jī)制。此外，在簇間利用普通節(jié)點(diǎn)中繼數(shù)據(jù)，降低簇頭的簇外轉(zhuǎn)發(fā)能耗和鏈路總能耗，均衡簇頭與普通節(jié)點(diǎn)之間的能量水平。仿真結(jié)果表明:HCECR 算法在保證數(shù)據(jù)包時(shí)效性的同時(shí)，減小了網(wǎng)絡(luò)總體通信能耗，提高了節(jié)點(diǎn)間能量均衡度。

［1］ Afsar M M，Tayarani M H.Clustering in sensor networks:A literature survey［J］.Journal of Network and Computer Applications，2014，46:198－226.

［2］ Qing L，Zhu Q X，Wang M W.Design of a distributed energy－efficient clustering algorithm for heterogeneous wireless sensor networks［J］.Computer Communications，2006，29:2230－2237.

［3］ Tanwar S，Kumar N，Niu Jainwei.EEMHR:Energy－efficient multilevel hetrogeneous routing protocol for wireless sensor networks［J］.International Journal of Communication Systems，2014，27(9):1289－1318.

［4］ Akkari W，Bouhdid B，Belghith A.LEATCH:Low energy adaptive tier clustering hierarchy［J］.Procedia Computer Science，2015，52:365－372.

［5］ Tiwari T，Roy N R.Heirarchical clustering in heterogeneous wireless sensor networks:A survey［C］∥International Conference on Computing，Communication＆Automation，ICCCA 2015，Noida，Piscataway，NJ，USA:IEEE，2015:1385－1390.

［6］ 曾華圣，熊慶宇，杜 敏，等.一種分布式能量高效的WSNs非均勻分簇路由協(xié)議［J］.傳感器與微系統(tǒng)，2014，33(3):146－149.

［7］ Hari U，Ramachandran B，Johnson Chris.An unequally clustered multihop routing protocol for wireless sensor networks［C］∥International Conference on Advances in Computing，Communications and Informatics，ICACCI 2013，2015:1007－1011.

［8］ 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2012，23(5):1222－1232.

［9］ Malathi L，Gnanamurthy R K，Chandrasekaran K.Energy efficient data collection through hybrid unequal clustering for wireless sensor networks［C］∥Computers and Electrical Engineering，2015:1－13.

［10］范書平，馬寶英，高晨光，等.一種分簇WSNs 最小跳數(shù)路由算法研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2014，35(8):1775－1779.

［11］王瀟嫻.基于最小跳數(shù)的WSNs 分簇路由協(xié)議研究與設(shè)計(jì)［D］.南京:南京郵電大學(xué)，2011.

［12］Younis O，Sonia F.HEED:A hybrid，energy－efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Trans on Mobile Comput，2004，3(4):366－379.

［13］Albath J，Mayur T，Sanjay M.Energy constraint clustering algorithms for wireless sensor networks［J］.Ad Hoc Netw，2013，11(8):2512－2525.