无线传感器网络中一种基于聚合层次聚类的分簇路由算法

摘 要：针对无线传感器网络中节点连接以及能量受限不足的问题，为了延长网络寿命，提出了一种基于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）．