基于跳數限制的高能效分簇路由算法

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

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

0 引 言

分簇算法通過構建層次化的拓撲結構，依靠簇頭融合作用減少數據包發送量和路由維護信息量，很大程度上提升了網絡的能量效率，其中，最具代表性的算法有LEACH［1］，DEEC［2］等。但這些算法要求簇頭與基站之間采用直接通信的方式傳輸數據，極大地增加了簇外通信能耗。基于此，很多采用簇外多跳方式傳輸數據的分簇算法［3～6］被提出，但也隨之產生了“熱區”問題［7～9］。此外，在實時性較強的傳感器網絡中，要求部分數據需在指定跳數內到達基站。目前，雖有一些基于最小跳數的分簇路由算法［10，11］被提出，但此類算法并不能保證所有緊急數據包的傳輸實時性。

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

1 系統模型假設

在場景設置上，僅考慮一個基站、n 個同構節點的情況，全部節點隨機布撒且不具有移動性。基站無功率限制，傳輸區域能夠覆蓋整個區域。網絡內每個數據包均設置有最大跳數，根據取值不同分為緊急數據和普通數據。其中，緊急數據具有極強的時效性，需要在指定跳數(跳數屬于固定區間)內到達基站。

傳感器節點廣播信息時使用全向天線，通信區域為圓形，并可以利用非對稱鏈路進行通信。節點具有感知自身位置的能力，且發射功率可以調整，共有n 個離散的發射功率，即p1，p2，…，pn，其中，pn=pmax。為保證數據包的時效性需求，假定所有簇頭均能與基站直接通信。

2 HCECR 算法

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

2.1 分簇信息泛洪

分簇信息泛洪階段，各節點要廣播自身分簇(CL)信息，并依據收到的分簇信息構建鄰居隊列。其中，分簇信息由六部分組成:源節點地址S_Add、坐標S_Pos(x，y)、上一跳轉發節點地址L_Add、坐標L_Pos(x，y)、數據包剩余跳數R_hop、源節點至當前節點的累計最小可達能耗TMRC。當節點i 要發送初始分簇信息時，各參數應按照式(1)進行設置

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

節點將數據包剩余跳數減一，并將最小可達能耗與原數據包中的TMRC 進行累加，得出從源節點到自身的TMRC

計算出TMRC(i)和數據包剩余跳數后，節點要利用處理后的CL 信息更新鄰居隊列，并將L_Add 和L_Pos(x，y)分別替換為自身地址和坐標，再次轉發此CL 信息。

2.2 簇首選舉

經過t0時間后將進入簇頭選舉階段，簇首的選取需綜合考慮節點剩余能量、簇內平均通信開銷和成員數量，簇頭權值表達式見式(4)。每個節點計算出自身的簇頭權值后將進行廣播，同時接收鄰居的簇頭權值。若節點的簇頭權值高于所有鄰居的取值，則向基站推舉自己為潛在簇頭;否則，作為普通節點?；靖鶕鳚撛诖仡^的簇頭權值和鄰居隊列確定正式簇頭，并廣播正式簇頭信息

式中 wCH(k)為k 的簇頭權值，Qs為鄰居隊列的元素個數，ER(k)和E0(K)分別為節點k 的剩余能量和初始能量。

2.3 簇成員劃分

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

假設節點p，q 分別為簇頭i，j 的成員，k 為兩個簇的共有成員，即j∈B(i，j)。此時，若節點i 向j 傳輸的是普通數據包，則應當采用簇間的多跳中繼，如圖1 虛線所示。若為緊急數據包，則要采用簇間的直接通信(圖1 中直線)或基站的直接通信。

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

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

2.4 節點類型與數據包類型

在數據傳輸階段，網絡內的數據包共分為三類，即感知、融合和中繼數據包。傳感器節點探測環境產生感知數據包，將其發送給對應簇頭，簇頭接收成員感知數據包后進行數據融合得到融合數據包。而中繼數據包是針對普通融合數據包進行簇外多跳通信而設立的，旨在降低轉發能耗。

簇頭向基站傳輸融合數據包分為快速模式和正常模式。快速模式針對緊急的融合數據包，即滿足R_hop∈［hmin，hup］的數據包。當簇頭節點收到數據包的剩余跳數滿足下式時:1 ＜R_hop≤hup，采用簇外多跳路由，將數據傳輸給相鄰簇頭中距離基站最近的一個簇頭。而當數據包剩余跳數為1 時，簇頭將直接把數據傳輸到基站。

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

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

圖2 節點類型與數據包類型對應圖Fig 2 Node type corresponding to data packet type

2.5 能耗模型

根據簇頭鄰居隊列中存儲的累計最小可達能耗和剩余跳數等信息，可知單次簇內通信的平均開銷

在僅考慮簇內數據匯聚能耗、忽略中繼其他簇數據的情況下，普通節點在一個采樣周期內的能量消耗為

式中 DDN為網絡的平均節點度。由于簇內數據融合采用的是樹狀結構，故需要其協助匯聚數據的鄰居數量是DDN－1。結合式(5)和規定的最小跳數，可以計算出簇間通信的平均距離

忽略轉發其他簇頭數據的情況下，簇頭接收、融合簇內成員數據，并向基站傳輸自身融合數據包的總能耗為

式中 αin，αout和αBS分別為簇頭產生融合數據后，選擇簇間多跳傳輸、簇間直接傳輸和基站傳輸的概率，αin+αout+αBS=1。結合這三個概率能得到當前簇(包括簇頭和簇成員)轉發鄰簇融合數據的能量開銷

式中 DDCH為下游相鄰簇頭節點數量。根據式(5)～式(9)可知，單個簇在單個采樣周期內的總能耗為

3 仿真分析

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

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

圖3 最短節點壽命的比較Fig 3 Comparision of the shortest node lifetime

圖4 最長節點壽命的比較Fig 4 Comparision of the longest node lifetime

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

圖5 跳數限制對節點最短壽命的影響Fig 5 Impact of hop limit on the shortest node lifetime

圖6 跳數限制對節點最長壽命的影響Fig 6 Impact of hop limit on the longest node lifetime

結合圖5、圖6 可知，無跳數限制的HCECR—W 算法相比HCECR 算法，具有更長的節點壽命。因為HCECR—W 算法在簇外通信中，更多地采用了簇間多跳通信，減少了簇間直接通信和簇頭與基站直接通信的次數，降低了簇外的轉發總能耗。

最后衡量新算法在數據包實時性方面的提升效果，將三種算法在網絡運行期間內失效數據包占總數的比例作為判斷標準。設場景大小為200 m×200 m，數據包跳數限制設為2，仿真節點數量為50，75，100 的三種情況，如圖7。

圖7 過期數據包比例的比較Fig 7 Comparison of ratio of overdue data packets

由圖7 可知，在網絡運行期間，有跳數限制的HCECR算法無過期數據包。而無跳數限制的HCECR—W 算法則有一定比例的數據包過期，且與HEED 和ECDS 兩種算法相比，其隨著節點數量的增多，過期數據包比例的增長速度最快。這主要是因為HCECR 算法引入了簇間多跳中繼的通信方式，一定程度上增加了轉發總跳數，導致滿足跳數要求的數據包比例下降。

4 結束語

本文提出一種基于跳數限制的分簇路由算法，構建了兼顧數據實時性和能量使用效率的簇結構和路由轉發機制。此外，在簇間利用普通節點中繼數據，降低簇頭的簇外轉發能耗和鏈路總能耗，均衡簇頭與普通節點之間的能量水平。仿真結果表明:HCECR 算法在保證數據包時效性的同時，減小了網絡總體通信能耗，提高了節點間能量均衡度。

［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非均勻分簇路由協議［J］.傳感器與微系統，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］ 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網絡非均勻分簇路由協議［J］.軟件學報，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 最小跳數路由算法研究［J］.小型微型計算機系統，2014，35(8):1775－1779.

［11］王瀟嫻.基于最小跳數的WSNs 分簇路由協議研究與設計［D］.南京:南京郵電大學，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.