基于能量和距离的非均匀分簇路由算法

金 彤，曾子维，王 刚

（辽宁科技大学 计算机与软件工程学院，辽宁 鞍山 114051）

无线传感器网络（Wireless sensor network，WSN）是由众多的传感器节点组成的网络［1］，在智能交通、环境检测、工业控制等领域都有很好的发展优势。通常情况下WSN中的节点采用蓄电池供电，但由于网络实际情况复杂，更换节点电池较为困难。因此设计一个高效节能的路由协议尤为重要。

WSN路由协议主要分为平面路由和分簇路由。其中应用最为广泛的就是低能量自适应聚簇分层协议（Low energy adaptive clustering hierarchy，LEACH）［2］，该协议引入“轮”概念，网络在运行中的每一轮都会进行簇头节点的更换，基于概率选举簇头，普通成员节点根据接收到的信号强度来选择加入簇。在选举过程中，如果忽略节点的剩余能量，会导致选举过程中出现网络能耗分布不均匀，部分节点过早死亡等问题。针对此问题有很多改进算法，赵小强等［3］提出一种基于模拟退火算法和改进灰狼优化器的异构WSN路由协议，算法定义适应度函数，利用模拟退火确保网络中最优簇群，均衡网络能耗，但距基站较近的簇能耗过大，产生的“热区”问题并未有效解决。Gachhandar等［4］提出基于K-means的分簇路由算法，但在选举簇头时只考虑节点的能量和距离，依然存在“热区”问题。吉训生等［5］为解决“热区”问题，引入双簇头思想，有效均衡节点能耗。韩广辉等［6］提出基于能量均衡和分簇的LEACH-E节能算法，该算法在初始阶段综合考虑节点的剩余能量和网络平均剩余能量，使剩余能量比网络平均能量高的节点优先选为簇头，改进阈值计算式，使选举阶段的能耗问题得到解决，但没有解决簇头分布不均的问题。

本文针对已有路由算法存在的问题，为提高整体网络的能量效率，延长网络的生存周期，提出一种新的非均匀分簇路由算法，即ONCH-LEACH算法，依靠网络能耗模型确定最佳簇头数目，根据网络的实际情况，改进簇头选择概率，将节点剩余能量、簇内节点覆盖率和地理位置引入簇头选举阈值函数中，解决节点因能量过低提前死亡从而造成网络部分瘫痪的问题。簇头节点选择之后，每个簇头节点根据距离基站的距离以及剩余能量产生自身的成簇规模的动态半径，使越靠近基站的簇，簇的规模越小，整体网络实现非均匀分簇，以解决“热区”问题。在传输数据阶段，提出新的数据分发机制，综合考虑节点的距离和传输数据量以及前簇头节点的剩余能量，根据路径代价函数动态选择最优的中继节点进行数据传输，从而减少传输过程中的能耗。

1 系统模型

1.1 网络模型

假设在一个M×M的区域内，有N个传感器节点随机分布，且该网络具有以下性质：

（1）节点在监测区域中随机分散，每个节点的初始能量由电池提供。

（2）所有传感器节点具有相同的结构，并且每个节点有唯一的标识（ID）［7］，初始能量是相同的，节点和基站的位置在部署后是静止的。

（3）网络中节点之间的通信链路是对称的，节点的通信距离可控，已知对方发射功率，节点可根据RSSI（Received signal strength indicator）信号值计算出发送者到自身的近似距离，同时感知自己的剩余能量。

（4）网络中传感器节点可以控制发送和接收的功率，即节点可根据需要调整自身发射功率。

（5）在节点的通信半径范围内，节点可以相互通信。

1.2 能量消耗模型

本文所选择的能耗模型主要基于LEACH算法［8］。算法根据发送者和接收者之间的距离d选择对应的模式：如果距离小于d0限值，使用自由空间模式计算能量消耗；当距离大于d0，选择多径衰减模式［9］。节点发送l比特数据的能耗为

接收消耗的能量为

阈值d0的定义式为

式中：Eelec表示发送和接收电路每传输1 bit数据的耗能；l为传送数据的长度；εfs为自由空间传播模型能耗；εamp为多路径衰减传播模型的能耗。

2 ONCH-LEACH算法

2.1 最优簇头数目

簇头节点的能量消耗主要来源于接收簇内普通节点收集来的数据信息，融合簇内信息和发送融合后的数据信息给基站。令最优簇头数为COPT，采用多路径衰减模型，每一轮中簇头的能量消耗为

式中：l为传送数据的长度；N为网络的随机分布的节点数；C为网络中的簇头数目；dtoBS为簇头和基站BS的距离；EDA是数据融合率。

其他普通成员节点的能量消耗为

式中：dtoCH为网络中非簇头节点与簇头节点间的距离。

每个簇在一帧内的能量消耗为

假设在面积为M×M的区域中随机分布N个传感器节点，簇头位于每个簇的中心，由于感知区

在整个区域内WSN的总能耗为

对Etotal求C导数，得出网络中最优簇头数目公式

2.2 改进的簇头选举概率公式

为了最大化利用节点能量，确定最优簇头数COPT后，在簇头选举概率公式中，引入当前参与竞选簇头节点的剩余能量与所有节点的平均剩余能量的比值，从而降低能量较低的节点当选簇头的概率，缓解因簇头能量较低导致的部分网络瘫痪的问题。本文提出的新的簇头选举概率公式为

式中：Eicu-avg为当前节点平均剩余能量；Eicu-resi为当前节点剩余能量。

2.3 剩余能量参数

WSN中各个节点的初始储存能量是相同的。随着网络的循环，符合条件的一部分节点被选为簇头，其余普通节点则选择加入适合的簇群。为了使能量更大的节点当选簇头，本文提出剩余能量参数Ei，综合考虑了节点剩余能量、存活节点的能量平均值以及节点的初始能量之间的比值，Ei值随着循环轮数而变化，使阈值的定义具有实时性。Ei定义式

式中：E0为初始能量。

2.4 间距参数

在WSN中，节点距离基站越远，接收到的信号越弱。在初始阶段，各个节点通过接收基站发送信号的强弱，得到自身的距离d，并返回给基站。距离基站越远的节点，传输过程中能量消耗越大。因此，节点与基站的距离在簇头的选举中有着至关重要的作用。本文提出的节点间距参数定义式

式中：Dicu-avg为网络中节点到基站距离平均值。

2.5 密度覆盖率参数

WSN的节点随机分布在区域内，所以网络中节点的邻居节点数目存在一定差异。簇头的选举应该考虑其周围的节点分布率，选择节点汇聚度较高的节点成为簇头，从而降低能耗。簇头的邻居节点为该簇头最大可覆盖通信范围内所有节点的集合。本文引入密度覆盖率，定义式为

式中：Nρ为密度覆盖率参数；Nneig为节点在其通信半径内的邻居节点的数量。

Nρ值大，说明实际邻居节点更密集，信息处理量大。

2.6 簇头选举阈值公式

将所提出的剩余能量参数、间距参数和密度覆盖率参数融入阈值公式中，同时引入加权因子α，定义为能量距离因子，取值为2或4，取决于节点间距离d。β为密度覆盖率加权因子，γ为节点间距加权因子，两个加权因子取值为0～1之间的常量，取决于实际环境对位置间距和密度的要求。簇头选举阈值定义式

2.7 非均匀成簇机制

选举簇头后，不同簇头节点剩余的能量不同，簇内能容纳的节点数目不同。因此，根据簇头节点的剩余能量和距离，设置动态通信半径

式中：Rmax为初始最大通信距离；Eicu-avg为节点平均剩余能量；Eicu-resi为该节点剩余能量。

随后，节点根据接收到的信息，选择适合的簇加入，成簇规则为

式中：V表示簇头集合；d(i,CH)表示节点i到簇头的距离。

E(i,nj)表示当有nj节点加入某簇后，每个节点分配的能量。计算式为

式中：Ech(i)表示当前簇的节点能量；nj表示当前加入该簇的节点数目；Emin表示节点存活的最小能量。

当节点满足成簇规则时，接收到多个簇头节点发来的信息，节点会选择E(i,nj)值最大的簇加入。若没有满足成簇规则，则选择最近的簇加入。因此，通过剩余能量和距离的引入可以均衡簇内的能耗，使剩余能量较小和距离基站较近的簇头成簇规模较小，实现网络的非均匀分簇，有效缓解网络的“热区”问题。

2.8 数据传输阶段

在WSN节点能耗模型［10］中，通信能耗占主要部分。当簇结构构造完成后，网络进入数据传输阶段。在这个过程中，当簇头节点传输距离较远时，选出适合的簇头节点作为中继节点，将数据逐步转发到基站。以最佳的路径进行数据传输，从而达到提升网络性能的目的。

本文将数据分发规则进行改进，提出一种综合考虑数据量和节点距离以及节点剩余能量的多跳数据分发方式。当簇头有数据转发任务时，查看邻居节点与基站的距离，选择比自身更接近基站的前邻居簇头节点，计算每个节点的路径转发代价函数，选择函数值最低的节点进行下一跳传输。

定义前向邻居节点

定义前向簇头邻居节点

本文提出的中继节点路径转发代价函数

式中：dis(i,BS)是备选的中继节点i与基站之间的距离；Eicu-resi(i)是节点i的当前剩余能量；χ为加权参数，经过反复实验，设置为0.4。

本文提出的路由代价函数，可以动态选择下一跳簇头，减缓单个簇头节点承担转发数据量过大的问题，也分担了整体网络的能量消耗。

3 算法设计与实现

本文提出的ONCH-LEACH算法分为两个阶段。在分簇阶段，首先利用网络模型确定最优簇头数目，网络区域中所有节点通过rand（0，1）函数产生一个［0，1］间的随机数。其次将节点的剩余能量、间距以及节点密度覆盖率引入阈值公式中，当自身产生的随机数小于阈值公式时，该节点就当选为簇头节点。随后，竞选成功的簇头在通信范围内广播竞选成功的消息。其余节点若同时收到多个簇头竞选成功的消息，则对比接收到的信号强弱，选择信号较强、距离较近且被簇头平均分配的能量较大的簇申请加入。若普通节点未收到簇头发来的消息，则自己当选簇头。当节点全部入簇成功后，进入数据传输阶段。当簇头有数据转发任务时，簇头选择代价函数较低的节点进行下一跳的数据传输。本文算法流程图如图1所示。

图1 算法流程图Fig.1 Flow chart of algorithm

4 仿真实验分析

4.1 仿真环境及参数

采用MATLAB进行仿真实验，在100 m×100 m的监控区域内，随机部署400个节点，分别在区域内和区域外部署基站，区域外基站的位置设为（50，150），区域内基站设置为（50，50）。具体参数：节点初始能量0.5 J，发送和接受数据的能耗Eelec=50 nJ/bit，自由空间模型参数εfs=10 pJ/（bit·m2），多路径衰落空间模型参数εamp=0.001 3 pJ/（bit·m4），EDA=50 nJ/bit，d0=87 m，数据信息包4 000 bit，循环次数2 500轮，β=0.3，γ=0.7，Rmax=15，Emin=0.001 J。

4.2 仿真结果分析

节点随机抛洒在网络区域内，分别考虑基站在节点区域内和区域外两种情况进行分析，整体网络分布如图2所示。

图2 网络节点分布图Fig.2 Distribution of network nodes

将本文的ONCH-LEACH算法与LEACH算法、LEACH-E算法分别在存活节点数、网络能耗方面进行对比。

（1）存活节点个数对比。存活节点数的仿真结果如图3所示。在循环2 500轮时，无论基站部署在区域内还是区域外，本文提出的ONCHLEACH算法存活节点个数明显增多。基站在区域内部署时，ONCH-LEACH算法到1 990轮网络中的节点全部死亡，LEACH和LEACH-E分别在1 351轮和1 642轮全部死亡。基站在区域外部署时，ONCH-LEACH算法到2 189轮网络中的节点全部死亡，LEACH和LEACH-E分别在1 654轮和1 861轮全部死亡。这说明本文算法能极大地延缓节点死亡时间，使网络中的存活节点数明显增多，延长了网络的生存周期。

图3 存活节点数目与循环轮数对比图Fig.3 Comparison between number of surviving nodes and number of loop rounds

（2）网络消耗总能量对比。网络总能量仿真结果如图4所示。相比其他两种协议，ONCHLEACH系统总能量最高，即能耗最低。因为ONCH-LEACH算法充分考虑节点的地理位置，减少普通节点到簇首的网络消耗，减少簇中和簇间网络能耗，均衡全局节点的能耗。

图4 系统总能量与循环轮数对比图Fig.4 Comparison between total system energy and number of loop rounds

5 结论

本文提出ONCH-LEACH分簇算法，引入最优簇头数目，改进簇头选择概率，综合考虑节点的能耗以及生存周期问题，将剩余能量、间距、密度覆盖率三个参数加入阈值计算式中，从而得出新的阈值选举计算方法。在分簇阶段，综合考虑簇头与节点之间的双向选择，将簇头的剩余能量和簇头节点距基站的距离引入其中，使剩余能量较低和距离基站较近的簇头成簇规模较小，从而实现非均匀分簇，均衡网络的能耗。在数据传输阶段，综合考虑节点的数据量以及节点间距离，提出新的多跳数据传输方式，根据代价函数动态选择中继节点进行数据传输。仿真对比发现，无论基站部署在区域内还是区域外，本文提出的算法能够降低网络总能耗，提高节点存活率，延长网络的生存时间。