無線傳感器網絡中一種基于聚合層次聚類的分簇路由算法

摘 要：針對無線傳感器網絡中節點連接以及能量受限不足的問題，為了延長網絡壽命，提出了一種基于AHC的分簇路由算法（HACCRA）。該算法首先運用AHC對網絡節點分簇，接著為簇首選擇、簇形成和路徑構建分別定義了恰當的決策目標函數，運用能量閾值、提出距離閾值、并且路由過程優先考慮簇首節點之間的一對一連接，有效解決了路由算法中分簇和路由不銜接的問題。仿真結果表明，與JCR、ICR以及DCK-LEACH相比，HACCRA能夠更好地實現網絡節點的能耗均衡，保證網絡數據傳輸的連接性，從而延長網絡壽命。

關鍵詞：聚合層次聚類算法； 距離閾值； 一對一連接； 能耗均衡； 分簇路由算法

中圖分類號：TP301.6 文獻標志碼：A

文章編號：1001-3695（2024）09-034-2805-10

doi：10.19734/j.issn.1001-3695.2024.02.0033

Clustering and routing algorithm based on agglomerative

hierarchical clustering for wireless sensor network

Zhang Fang， Gao Cuifang

（School of Science， Jiangnan University， Wuxi Jiangsu 214122， China）

Abstract：Aiming at the shortcomings of node connection and energy limitation in wireless sensor networks， this paper proposed a clustering routing algorithm based on AHC（HACCRA） to prolong the network lifetime. The algorithm firstly applied the aggregated hierarchical clustering to cluster network nodes， and then defined appropriate decision objective functions for cluster head（CH） selection， cluster formation， and path construction respectively， it used the energy threshold， proposed the distance threshold， and taked priority of the one-to-one connection between CHs during the process of nodes’ data transmission， effectively solving the unconnected problem of clustering and routing in algorithms. The simulation results show that compared with JCR， ICR， and DCK-LEACH， HACCRA can better achieve nodes’ balanced energy-consumption， and ensure effective connection of data transmission in the network， so as to prolong the network lifetime.

Key words：agglomerative hierarchical clustering algorithm; distance threshold; one-to-one connection; balanced energy-consumption; clustering routing algorithm

0 引言

無線傳感器網絡具有廣泛的應用前景［1］，研究人員對無線傳感器網絡的研究熱度不斷增長［2］。然而傳感器節點的能量容易很快耗盡，導致網絡數據連接失敗［3］。因此，“如何延長網絡壽命”的問題引起了研究者們的關注［4］。無線傳感器網絡中節點的能量主要消耗在數據傳遞階段［5］，故一些研究者們試圖從路由算法著手旨在最大化網絡壽命，其中分簇路由算法得到了廣泛地研究。

分簇路由算法包括靜態［6，7］、動態以及混合分簇［8］。為了更好地均衡網絡節點的能量消耗，很多研究采用不同的方法構造動態分簇路由算法，例如DEEC［9］、NEECH［10］、運用機器學習方法的PFMUR［11］、運用啟發式算法的CRGT［12］、EBCRP［13］、運用冒泡排序的I-ECHERP［14］、運用AHC的DHAC［15］，構建非均勻結構的EEUCB［16］。動態分簇給網絡帶來了過大的負載，Mosavifard等人［17］提出在網絡中選擇簇首和后向簇首以減少分簇的成本，但網絡的連接性難以得到保證。EEHCHR［18］采用周期性更新簇首的方法，并提出一種層次數據包路由策略，但是它完全將簇首選擇與路由過程分離看待。

在分簇路由算法的簇首選擇階段，為了避免簇首數量過多導致網絡的能量消耗值增加，同時保證網絡的連接性，FL-EEC/D［19］以網絡期望得到的簇數量為依據，得到簇首之間應該滿足的最小距離閾值，但是該算法并沒有考慮節點的通信范圍。IPRA［20］以最小化簇首節點之間的重合節點為目的，提出了簇首之間的距離閾值上下限，并且將基于分簇的思想和基于鏈狀的思想相結合運用于數據傳遞過程，該算法中選擇簇首和路徑構建的完全分離并不適用于大規模網絡。

一些分簇路由算法將聚類算法［21］運用到網絡拓撲結構的構建當中。DCK-LEACH［22］結合canopy優化和K-means算法形成簇，但是數據傳輸階段并沒有完全考慮到網絡的連接，其采用簇首與BS直接進行單跳數據傳輸的舉措忽視了節點通信范圍的限制。GBK［23］將K-means算法運用到網絡簇結構的構造當中，采用肘部法則得到最佳簇首數量，由此建立網格拓撲結構，但是該方法也將分簇與路由看成是完全分離的階段。

大多數分簇路由算法沒有全面考慮網絡中節點有限的通信半徑，這很容易導致網絡連接的失敗。而JCR［24］以保證網絡數據傳輸路徑的連接性為出發點，運用了梯度的概念，將簇首選擇和路徑構建過程相結合，得到了一種簡單高效的分簇路由算法。然而，該算法在網絡簇結構形成和路徑構建時沒有全面考慮到網絡節點的能耗均衡性。

ICR［25］在規定了成簇范圍和數據傳輸范圍之后，將網絡劃分為邊長為成簇范圍大小的方形網格，這保證了普通節點與簇首節點之間的連接，并且該算法在選擇簇首時考慮到了當前簇首節點的前向以及同向節點，為簇間數據傳輸路徑的連接打下了基礎，但是其將最短路徑算法運用到簇間路徑構建環節，忽視了簇首節點之間的能耗均衡性。

對上述算法（如表1所示）進行綜合分析，可以看出大多數現有研究（文獻［6～8，10，12～14，16，18，20，22，23］）都將分簇和路由視為兩個完全孤立的問題。有些算法（文獻［6～8，10，12～14，16，18，20，22，24，25］）也不能全面考慮到網絡中節點能耗的均衡性。此外，在動態分簇路由算法中，簇首選擇和簇形成的過程中，信息復雜度是一個關鍵點，而部分算法（文獻［10，13～16，20，24］）缺乏對這方面的考慮。假設可以綜合考慮上述因素，那么當前較先進的路由算法的性能仍然可以得到提高。這正是本文提出新的分簇路由算法HACCRA的動機。本文的研究貢獻如下：

a）HACCRA將簇首選擇、簇形成和路徑發現三階段相結合，保證簇首選擇的合理性和數據傳輸的連接性，以改善上述算法中各個階段孤立考慮的問題。

b）在簇首選擇階段，HACCRA定義了兩類簇首選擇函數表達式，在合適的能量和距離閾值下選擇簇首和前向簇首，以保證能耗的均衡和網絡的連接。并且在動態條件下，只在小范圍內搜尋，可以減少一些不必要的控制包傳輸。

c）在簇形成階段，HACCRA提出了簇形成的目標函數表達式，依據不同簇規模選擇不同數量簇首的策略，以保證普通節點與簇首之間的連接性。

d）在構建數據傳輸路徑時，HACCRA定義了簇間路徑構建的目標函數，除了考慮能量和距離等必要的指標外，優先考慮了簇首之間的一對一連接，這對平衡簇首之間的能量消耗作出了較大的貢獻。

1 預備知識

1.1 網絡模型

本文采用的網絡模型具體如下：

a）網絡中的節點隨機分布在監測區域中，一旦部署，位置就不會改變。

b）節點編號確定且唯一，節點之間同構。

c）節點配備的電池既不能更換也不能充電。

d）節點可以根據從環境中感知到的信號強度判斷與其他1c3fa068d98d640b50556aa6686d7f549680f965a9cb2e32e96c1e7cc45590eb節點的距離。

e）節點發送數據時可自行調整通信功率的大小，節點具有融合數據的能力。

f）網絡部署時考慮在網絡邊界、中心或者角落放置單個靜止BS（BS的位置取決于實際的仿真條件）的三種情況，分別記為環境1（WSN1）、環境2（WSN2）、環境3（WSN3）。

1.2 能量消耗模型

兩個相距為d的節點在傳遞L bit數據時消耗的能量：

4 結果與討論

4.1 關于成簇半徑和通信半徑對ICR算法性能影響的分析

同于JCR，一旦網絡中節點的傳輸距離超過了它的數據傳輸范圍，數據傳輸便不能正常進行。依然運用JCR中提到的成簇范圍（Tr）和簇間數據傳遞范圍（Tx）。

由于ICR中采用的最小通信范圍（Tr）以及通信半徑（Tx）不同于HACCRA，該部分本文單獨考察了當兩者在相同通信范圍時算法的表現，該情況下的ICR算法被命名為ICRIMPROVE。本節以網絡面積為140 m×140 m，280 m×280 m，節點密度為0.01/m2 的情況為例，主要展示兩算法在ECBI和存活節點數量方面的表現情況，具體如圖2、3所示。

圖2、3的算法性能對比表明，HACCRA表現較好，而ICR和ICRIMPROVE不適合大規模網絡：隨著網絡面積的增大，ICR和ICRIMPROVE的性能越來越差。例如，在環境1下，ICR和ICRIMPROVE的網絡壽命分別從33下降到7以及從277下降到101。同時，對比ICR和ICRIMPROVE的表現可以得出，ICR中Tr和Tx的設置是不合理的。

4.2 算法性能分析

本文從以下四種指標考察算法性能：能耗均衡指標、網絡壽命、數據收集情況以及數據包傳遞率。

a）能耗均衡指標

圖4～6反映了四種算法對于配備有100～900節點數量的網絡于環境1～3下的ECBI情況。

當能耗平衡指數穩定維持在較高值時，表明算法在能量消耗均衡性方面表現良好。從某一時刻開始，JCR算法的ECBI值出現上升趨勢，表明此時網絡中出現了死亡節點，意味著第一梯度節點的能耗與其他梯度節點的能耗差別較大。同樣，當網絡中的數據無法傳輸到BS時，ICR算法的ECBI值變為零。此外，DCK-LEACH的ECBI值波動較大。與此不同的是，HACCRA的ECBI穩定維持在較高值，故HACCRA能更好地保證節點能耗的均衡性。

b）網絡壽命

圖7～9為四種算法對于配備有100～900節點數量的網絡于環境1～3下的存活節點情況。在ICR和DCK-LEACH算法下，網絡較早出現死亡節點，這說明ICR算法中節點能量消耗不均衡。此外，JCR和HACCRA的曲線下降趨勢相似，但JCR比HACCRA更早出現死亡節點，這主要是因為JCR在簇形成時沒有考慮節點的連接，而HACCRA運用多種策略于簇首選擇以及路由階段，由此更好地平衡節點能耗。表4通過總結提煉圖7～9表明HACCRA在網絡壽命方面優于其他算法。

圖10直觀地展示出HACCRA的網絡壽命要遠遠長于JCR、ICR和DCK-LEACH算法。

d）數據包傳遞率（PDR）

圖14～16顯示了不同網絡面積下成功傳輸到BS的數據包傳遞率。HACCRA保證了高效的數據收集情況。總的來說，這五個度量指標之間是環環相扣的。不同算法下形成的網絡拓撲結構反映了節點能耗的均衡性。而能耗越均衡，網絡壽命越長，這使得網絡中的數據能夠源源不斷地傳輸到BS。從圖14、16來看，在這四個指標下，HACCRA的性能都優于JCR、ICR以及DCK-LEACH算法。

5 結束語

以保證網絡節點之間的連接性和節點能量消耗的均衡性為出發點，以延長網絡節點的壽命為目的，提出了一種新的分簇路由算法。算法首先考慮了簇首的選擇、簇的形成和數據傳輸路徑的發現這三個階段應該是相輔相成的，于是在AHC的基礎上，將此三階段進行有效的結合，具體體現在：簇首選擇過程中對于前向節點集合的考慮保證了后續簇間路徑的有效連接，同時根據不同簇規模選擇出不同數量簇首的舉措也輔助保證了普通節點與簇首節點之間的覆蓋連接。其次能量閾值的運用和距離閾值的提出進一步考慮簇首選擇的合理性，并且簇間路徑構建環節優先考慮簇首節點之間的一對一連接在很大程度上保證了簇首節點之間的能量消耗均衡性。

實驗結果表明，相較于JCR、 ICR以及DCK-LEACH算法，本文提出的算法在網絡拓撲結構、能量消耗平衡指數、網絡壽命、數據收集以及數據包傳遞率五個方面都表現得更好。

HACCRA仍然存在一些不足。首先，雖然簇首和前向簇首的動態選擇發生在特定的范圍內，只考慮小范圍內的節點可以減少一些不必要的控制包傳輸，但同樣會導致控制消息較多。因此，在以后的工作中可以考慮設置一個簇首更新機制，以達到降低簇首更新頻率的目的。

參考文獻：

［1］Suresh K M， Sathish K G A. Efficient hybrid energy optimization method in location aware unmanned WSN［J］. Intelligent Automation & Soft Computing， 2023，35（1）： 705-725.

［2］Ahmed R A， Ahmed Z A， Abd-Elnaby M， et al. Energy-efficient routing protocol based on adaptive soft hresholding for wireless sensor networks［J］. Wireless Personal Communications， 2022， 124（3）： 2661-2676.

［3］Anastasi G， Conti M， Di Francesco M， et al. Energy conservation in wireless sensor networks： a survey［J］. Ad Hoc Networks， 2009， 7（3）： 537-568.

［4］Xu Kaida， Zhao Zhidong， Luo Yi， et al. An energy-efficient clustering routing protocol based on a high-QoS node deployment with an inter-cluster routing mechanism in WSNs［J］. Sensors， 2019， 19（12）： 2752.

［5］Bangotra D K， Singh Y， Selwal A， et al. An intelligent opportunistic routing algorithm for wireless sensor networks and its application towards e-healthcare［J］. Sensors， 2020， 20（14）： 3887.

［6］Abaskele-Turgut I， Altan G. A fully distributed energy-aware multi-level clustering and routing for WSN-based IoT［J］. Trans on Emerging Telecommunications Technologies， 2021， 32（12）： e4355.

［7］Abaskele-Turgut I. Multihop routing with static and distributed clustering in WSNs［J］. Wireless Networks， 2021， 27（6）： 3797-3809.

［8］Abaskele-Turgut I. DiCDU： distributed clustering with decreased uncovered nodes for WSNs［J］. IET Communications， 2020， 14（6）： 974-981.

［9］Singh S， Malik A， Kumar R. Energy efficient heterogeneous DEEC protocol for enhancing lifetime in WSNs［J］. Engineering Science and Technology： an International Journal， 2017， 20（1）： 345-353.

［10］Baradaran A A， Rabieefar F. NEECH： new energy-efficient algorithm based on the best cluster head in wireless sensor networks［J］. Ira-nian Journal of Science and Technology： Trans of Electrical Engineering， 2023， 47（3）： 1129-1144.

［11］Nithya R， Alroobaea R， Binmahfoudh A， et al. Distributed multi-hop clustering approach with low energy consumption in WSN［J］. Computer Systems Science and Engineering， 2023， 45（1）： 903-924.

［12］Yu Xiuwu， Li Ying， Liu Yong， et al. WSN clustering routing algorithm based on hybrid genetic tabu search［J］. Wireless Personal Communications， 2022， 124（4）： 3485-3506.

［13］Han Yamin， Byun H， Zhang Liangliang. Energy-balanced cluster-routing protocol based on particle swarm optimization with five mutation operators for wireless sensor networks［J］. Sensors， 2020， 20（24）： 7217.

［14］Ali M S， Alqahtani A， Shah A M， et al. Improved-equalized cluster head election routing protocolkVX77Zr2MzaaiwC6462xVw== for wireless sensor networks［J］. Computer Systems Science and Engineering， 2023， 44（1）： 845-858.

［15］Lung C H， Zhou Chenjuan. Using hierarchical agglomerative clustering in wireless sensor networks： an energy-efficient and flexible approach［J］. Ad Hoc Networks， 2010， 8（3）： 328-344.

［16］Jasim A A， Idris M Y I， Saaidal Bin Azzuhri S， et al. Energy-efficient wireless sensor network with an unequal clustering protocol based on a balanced energy method （EEUCB）［J］. Sensors， 2021， 21（3）： 784.

［17］Mosavifard A， Barati H. An energy-aware clustering and two-level routing method in wireless sensor network［J］. Computing， 2020， 102（7）： 1653-1671.

［18］Panchal A， Singh R K. EEHCHR： energy efficient hybrid clustering and hierarchical routing for wireless sensor networks［J］. Ad Hoc Networks， 2021， 123（1）： 102692.

［19］Hamzah A， Shurman M， Al-Jarrah O， et al. Energy-efficient fuzzy-logic-based clustering technique for hierarchical routing protocols in wireless sensor networks［J］. Sensors， 2019， 19（3）： 561.

［20］Sajwan M， Sharma A K， Verma K. IPRA： iterative parent-based routing algorithm for wireless sensor networks［J］. Wireless Personal Communications， 2022， 124（4）： 3321-3353.

［21］李雪， 南建國. 基于IK-means聚類的分簇路由算法［J］. 計算機應用研究， 2021， 38（4）： 1149-1153，1164. （Li Xue， Nan Jianguo. Clustering routing algorithm based on IK-means clustering［J］. Application Research of Computers， 2021， 38（4）： 1149-1153，1164.）

［22］Wu Mei， Li Zhengliang， Chen Jing， et al. A dual cluster-head energy-efficient routing algorithm based on canopy optimization and K-means for WSN［J］. Sensors， 2022， 22（24）： 9731.

［23］Gouissem B B， Gantassi R， Hasnaoui S. Energy efficient grid-based K-means clustering algorithm for large scale wireless sensor networks［J］. International Journal of Communication Systems， 2022， 35： e5255.

［24］Xu Zhezhuang， Chen Liquan， Chen Cailian， et al. Joint clustering and routing design for reliable and efficient data collection in large-scale wireless sensor networks［J］. IEEE Internet of Things Journal， 2016， 3（4）： 520-532.

［25］Alharbi M A， Kolberg M， Zeeshan M. Towards improved clustering and routing protocol for wireless sensor networks［J］. EURASIP Journal on Wireless Communications and Networking， 2021， 2021（1）： 1-31.

收稿日期：2024-02-18；修回日期：2024-04-03 基金項目：國家自然科學基金資助項目（11801222）

作者簡介：張芳（1998—），女，安徽六安人，碩士，主要研究方向為無線傳感器網絡路由算法；高翠芳（1974—），女（通信作者），河北石家莊人，副教授，碩導，博士，主要研究方向為模式識別、計算智能（cuifang_gao@163.com）．