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

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

中圖分類號：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 引言

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

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

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

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

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

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

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

a）HACCRA將簇首選擇、簇形成和路徑發(fā)現(xiàn)三階段相結(jié)合，保證簇首選擇的合理性和數(shù)據(jù)傳輸?shù)倪B接性，以改善上述算法中各個階段孤立考慮的問題。

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

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

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

1 預(yù)備知識

1.1 網(wǎng)絡(luò)模型

本文采用的網(wǎng)絡(luò)模型具體如下：

a）網(wǎng)絡(luò)中的節(jié)點隨機分布在監(jiān)測區(qū)域中，一旦部署，位置就不會改變。

b）節(jié)點編號確定且唯一，節(jié)點之間同構(gòu)。

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

d）節(jié)點可以根據(jù)從環(huán)境中感知到的信號強度判斷與其他1c3fa068d98d640b50556aa6686d7f549680f965a9cb2e32e96c1e7cc45590eb節(jié)點的距離。

e）節(jié)點發(fā)送數(shù)據(jù)時可自行調(diào)整通信功率的大小，節(jié)點具有融合數(shù)據(jù)的能力。

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

1.2 能量消耗模型

兩個相距為d的節(jié)點在傳遞L bit數(shù)據(jù)時消耗的能量：

4 結(jié)果與討論

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

同于JCR，一旦網(wǎng)絡(luò)中節(jié)點的傳輸距離超過了它的數(shù)據(jù)傳輸范圍，數(shù)據(jù)傳輸便不能正常進行。依然運用JCR中提到的成簇范圍（Tr）和簇間數(shù)據(jù)傳遞范圍（Tx）。

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

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

4.2 算法性能分析

本文從以下四種指標考察算法性能：能耗均衡指標、網(wǎng)絡(luò)壽命、數(shù)據(jù)收集情況以及數(shù)據(jù)包傳遞率。

a）能耗均衡指標

圖4～6反映了四種算法對于配備有100～900節(jié)點數(shù)量的網(wǎng)絡(luò)于環(huán)境1～3下的ECBI情況。

當能耗平衡指數(shù)穩(wěn)定維持在較高值時，表明算法在能量消耗均衡性方面表現(xiàn)良好。從某一時刻開始，JCR算法的ECBI值出現(xiàn)上升趨勢，表明此時網(wǎng)絡(luò)中出現(xiàn)了死亡節(jié)點，意味著第一梯度節(jié)點的能耗與其他梯度節(jié)點的能耗差別較大。同樣，當網(wǎng)絡(luò)中的數(shù)據(jù)無法傳輸?shù)紹S時，ICR算法的ECBI值變?yōu)榱?。此外，DCK-LEACH的ECBI值波動較大。與此不同的是，HACCRA的ECBI穩(wěn)定維持在較高值，故HACCRA能更好地保證節(jié)點能耗的均衡性。

b）網(wǎng)絡(luò)壽命

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

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

d）數(shù)據(jù)包傳遞率（PDR）

圖14～16顯示了不同網(wǎng)絡(luò)面積下成功傳輸?shù)紹S的數(shù)據(jù)包傳遞率。HACCRA保證了高效的數(shù)據(jù)收集情況。總的來說，這五個度量指標之間是環(huán)環(huán)相扣的。不同算法下形成的網(wǎng)絡(luò)拓撲結(jié)構(gòu)反映了節(jié)點能耗的均衡性。而能耗越均衡，網(wǎng)絡(luò)壽命越長，這使得網(wǎng)絡(luò)中的數(shù)據(jù)能夠源源不斷地傳輸?shù)紹S。從圖14、16來看，在這四個指標下，HACCRA的性能都優(yōu)于JCR、ICR以及DCK-LEACH算法。

5 結(jié)束語

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

實驗結(jié)果表明，相較于JCR、 ICR以及DCK-LEACH算法，本文提出的算法在網(wǎng)絡(luò)拓撲結(jié)構(gòu)、能量消耗平衡指數(shù)、網(wǎng)絡(luò)壽命、數(shù)據(jù)收集以及數(shù)據(jù)包傳遞率五個方面都表現(xiàn)得更好。

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

參考文獻：

［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］. 計算機應(yīng)用研究， 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—），女，安徽六安人，碩士，主要研究方向為無線傳感器網(wǎng)絡(luò)路由算法；高翠芳（1974—），女（通信作者），河北石家莊人，副教授，碩導，博士，主要研究方向為模式識別、計算智能（cuifang_gao@163.com）．