一种联合区域划分和分簇路由的WRSN能耗优化算法

一种联合区域划分和分簇路由的wrsn能耗优化算法
技术领域
1.本发明涉及无线可充电传感器网络传输技术领域，特别涉及一种联合区域划分和分簇路由的wrsn能耗优化算法。


背景技术：

2.无线可充电传感器网络(wireless rechargeable sensor network,wrsn)是由确定部署的无线充电基站或移动的无线充电设备(wireless charging equipment,wce)通过该无线电能传输技术(wireless power transfer,wpt)为枯竭节点及时补充能量的无线传感器网络(wireless sensor network，wsn)。
3.现有的技术研究主要集中在如何延长无线传感器网络(wsn)的使用寿命。能耗优化传统的wsn分簇路由算法中，分簇后的簇内传感器节点将监测数据通过簇头节点进行中继路由转发到基站，可以有效地均衡并降低wsn中节点能耗，但是仍存在一定的热区效应问题。k-means算法将距离相近的节点划分到同一簇内，可以有效降低簇内通信数据收发能耗，但算法中k个初始簇节点是随机选取的，选取数量和选取节点的位置都会对最终的分簇聚类结果影响较大。同时由于wrsn中传感器节点可以进行快速的能量补充，无线充电设备的充电规划算法在延长网络寿命发挥重要作用，因此设计wrsn的分簇路由算法时应考虑到wce充电移动距离以及能量利用率等因素。在文献《k-chra:aclustering hierarchical routing algorithm for wireless rechargeable sensor networks》中给出的k-chra算法，通过簇头间的中继通信路由确保了簇内和簇间节点的单跳通信，大幅提升网络通信效率，但是最佳簇个数不好确定，容易出现较多外层孤立节点导致wce充电移动距离增加，充电效率降低。
4.因此，有必要提出一种联合区域划分和分簇路由的wrsn能耗优化算法，该算法通过提出一种基于动态簇半径的区域划分方法，使得其能够根据wrsn的网络结构和节点能耗情况，动态调整簇半径，以实现wrsn不同区域中节点能耗均衡，并在k-means算法基础上提出了一种基于极大簇的分簇聚类算法和分簇优化策略，优化并得到更加合理的wrsn簇结构，最后，通过中继路由区间划分与中继路由选择函数，均衡簇间和层间的节点能耗，缓解热区效应问题，同时也优化了wce充电移动路径，从而降低wrsn网络的整体能耗，延长wrsn的网络使用寿命。


技术实现要素：

5.鉴于以上内容，有必要提供一种联合区域划分和分簇路由的wrsn能耗优化算法，以提高无线可充电传感器网络中移动充电车的充电效率以及延长网络的使用寿命。
6.为达到上述目的，本发明所采用的技术方案是：
7.一种联合区域划分和分簇路由的wrsn能耗优化算法，包括如下步骤：
8.s1、利用动态簇半径的区域划分方法对wrsn监测区域进行层级划分，得到若干子区域并确定各子区域的分簇半径；
9.s2、根据步骤s1所得到的子区域分簇半径和子区域内节点，通过极大簇的分簇聚类算法，对步骤s1所划分的各个子区域进行节点分簇聚类；
10.s3、通过中继路由区间划分方法对步骤s1所得的子区域进行区域整合，形成中继路由区间，其中，上一区间层级中的簇头节点根据区间划分方法选取下一级区间对应层级的簇头节点作为中继节点；之后，根据中继路由选择函数选取中继节点，并通过设置簇头剩余能量阈值进行簇头轮调，更新下一周期的中继节点，以均衡节点负载；
11.s4、在每一个wrsn运行周期内，簇内普通节点会按照分配的时序序号向簇头节点发送自身采集到的监测数据，簇头节点收集融合后，再将数据以单跳、多跳的方式发送到基站节点中完成wrsn一轮运行周期内的工作。
12.优选地，步骤s1中，采用动态簇半径的区域划分方法进行层级划分的具体步骤包括：
13.步骤1：考虑节点部署最远距离为正方形监测区域四个顶点a0、b0、c0、d0，wrsn最大簇半径为r，将各顶点分别与中心基站连接并以距a0、b0、c0、d0各顶点为r的位置为圆心分别做圆，四个圆分别交连接线于a1、b1、c1、d1；先将监测区域a0、b0、c0、d0划分为两部分，分别为正方形区域a1b1c1d1和框形区域a0b0c0d
0-a1b1c1d1；
14.步骤2：正方形区域a1、b1、c1、d1四个顶点继续连接中心基站，并以k
sfi
r为半径做圆，得到新的交点a2、b2、c2、d2，进而划分得到正方形区域a2b2c2d2和框形区域a1b1c1d
1-a2b2c2d2；其中，k
sf
为缩放因子，i为第1次划分，i＝1；
15.步骤3：检测步骤s2区域划分后得到的正方形区域的边长，当该边长不小于时，继续进行区域划分，直至该边长小于时停止区域划分；划分时，以上一次划分得到的正方形区域的顶点为基础，重新与中心基站连线，并以k
sfi
r为半径做圆，得到新的交点，并基于此划分得到新的正方形区域和框形区域，其中，i为第几次划分，i＝2，3
…
，n，n为区域划分次数；停止区域划分后，距离中心基站为r的圆形区域自动划分为第n+1区域。
16.优选地，缩放因子k
sf
通过如下公式计算得到：
[0017][0018]
式中，d
max
和d
min
分别为wrsn监测区域中的所有节点距离中心基站最大值和最小值，d(r,bs)为子区域内圆心到中心基站的距离，c为调节因子，取值范围为c∈[0,1]。
[0019]
优选地，步骤s2中，通过极大簇的分簇聚类算法进行的节点分簇聚类的具体步骤如下：
[0020]
步骤1：获取步骤s1所得的第l个子区域，并得到该子区域的分簇半径和节点，其中，设第l个子区域的分簇半径为r
l
，节点k为该子区域内节点编号，l＝1,2,...,n，n为子区域数；
[0021]
步骤2：对于子区域内每个节点si，i＝1,2，3
…
,k，以节点为圆心，该子区域的分簇半径r
l
为半径作圆，将满足邻节点条件的其余节点sj划分为该节点si的邻居节点neighbor_si并得到邻居节点数m，其中，邻节点条件为：
[0022]
[0023]
式中，(xi,yi)为节点si的二维坐标，(xj,yj)为节点sj的二维坐标，j＝1,2，3
…
,k，但j≠i；m为满足邻节点条件的节点sj的数量；
[0024]
步骤3：将子区域内节点按邻居节点数m进行降序排列，选取邻居节点数最多的节点为簇头并构建簇；该簇建立完成后将簇内节点从子区域节点编号中移除，子区域内剩余节点为待成簇节点；
[0025]
步骤4：当步骤3中所得的子区域内的待成簇节点的数量不为0时，以步骤3中所得的子区域内的待成簇节点为基础，采用步骤2的方法计算待成簇节点的邻居节点数，并采用步骤3构建簇，直到待成簇节点的数量为0时，停止迭代，完成第l个子区域的分簇聚类；
[0026]
步骤5：当步骤4所完成的第l个子区域的分簇聚类的量词l不等于步骤s1中所得的子区域的总数n时，重复步骤1至步骤4以完成第l+1个子区域的分簇聚类；反之进入步骤6；
[0027]
步骤6：输出wrsn整体监测区域的分簇聚类结果。
[0028]
优选地，步骤s2针对每个子区域完成节点的分簇聚类后，均对每一个子区域分簇聚类所得的簇结构采用分簇优化策略进行优化，以减少重叠簇和交叉簇。
[0029]
优选地，采用分簇优化策略进行优化的步骤如下：
[0030]
对子区域每个簇计算簇头与中心基站间的距离，并以该距离作为该簇的簇保留优先级，其中，距离中心基站越近，该簇的簇保留优先级越高；
[0031]
依次使用以下分簇优化策略优化各个子区域内的簇结构，其中，策略1：对于包含有相同簇内节点的不同簇保留优先级的簇，保留簇保留优化级高的簇；策略2：对于不同簇保留优先级的簇中，当簇保留优先级低的簇的簇头和簇内节点被簇保留优先级高的簇的簇心包含时，移除簇保留优先级低的簇；策略3：对于所有簇，当簇内节点同时被多个簇包含时，若簇保留优先级低的簇中所有节点能被其余簇保留优先级高的簇的簇内节点包含时，移除簇保留优先级低的簇。
[0032]
优选地，步骤s3中，中继路由区间划分方法具体体现在如下中继路由区间划分数据传输方案中：
[0033]
首先，假设步骤s1输出得到了n个子区域，将靠近基站且距离半径为r的圆自动化为一个子区域，该子区域内节点数据直接单跳传输到基站节点，除去靠近基站距离半径为r的子区域，将wrsn监测区域的其他子区域划分为n-1个层级，假设为k＝n-1个层级，在层级划分中用m1,m2,...,mk表示；那么，当层级数k为奇数时，有传输方案1；当层级数k为偶数时，有传输方案2-4；
[0034]
其中，
[0035]
传输方案1为：将k个层级划分为(k-1)2个区间，其中l1＝{m1,m2,m3}，l2＝{m4,m5}，li＝{m
2i
,m
2i+1
},i＝2,3,...,(k-1)2；l1区间中的层级随机选取l2区间的层级作为该层的中级路由层，li区间中的m
2i
层级选取l
i+1
区间的m
2(i+1)
层级作为该层的中级路由层，li区间中的m
2i+1
层级选取l
i+1
区间的m
2(i+1)+1
层级作为该层的中级路由层，最终由l
(k-1)/2
中各层级的簇头节点将数据发送到基站节点；
[0036]
传输方案2为：将k个层级划分为2个区间，其中l1＝{m1,m2,...,m
k/2
}，l2＝{m
k/2+1
,m
k/2+2
,...,mk}；l1区间中的mj层级选取l2区间中的m
k/2+j
层级作为该层的中级路由层，最终由l2中各层级的簇头节点将数据发送到基站节点；其中，j＝1,2,3,...,k/2；
[0037]
传输方案3为：若层级数k满足条件(k+1)/3＝n，n为正整数，则将k个层级划分为(k
+1)/3个区间，其中，li＝{m
3i-2
,m
3i-1
,m
3i
}，l
(k+1)/3
＝{m
k-1
,mk}，i＝1,2,...,(k+1)/3-1；li区间中的m
3i-2
层级选取l
i+1
区间中的m
3(i+1)-2
层级作为该层的中级路由层，li区间中的m
3i-1
层级选取l
i+1
区间中的m
3(i+1)-1
层级作为该层的中级路由层，li区间中的m
3i
层级分别选取l
i+1
区间中的m
3(i+1)
层级作为该层的中级路由层，l
(k+1)/3-1
区间中的层级随机选取l
(k+1)/3
区间的层级作为该层的中级路由层，最终由l
(k+1)/3
中各层级的簇头节点将数据发送到基站节点；
[0038]
传输方案4为：将k个层级划分为k/2个区间，其中，li＝{m
2i-1
,m
2i
},i＝1,2,...,k/2；li区间中的m
2i-1
层级选取l
i+1
区间中的m
2(i+1)-1
层级作为该层的中级路由层，li区间中的m
2i
层级分别选取l
i+1
区间中的m
2(i+1)
层级作为该层的中级路由层，最终由l
k/2
中各层级的簇头节点将数据发送到基站节点；
[0039]
上述方案择一形成中继路由区间。
[0040]
优选地，步骤s3中，中继路由选择函数考虑到候选簇头节点的节点剩余能量、候选簇头节点间的距离和候选簇头节点的簇内节点数三个因素，并基于该三个因素，对其归一化后进行加权求和，得到如下的函数关系式：
[0041][0042]
式中，re
max
、dist
max
、clusternumber
max
分别为下一层级中簇头剩余能量最大值、通信范围内两层级间簇头距离最大值和下一层级中簇内节点数最大值，为第l层级的第i个簇头节点，为l层对应下一层级l
′
的第j候选簇头节点，为对应下一层级的第j候选簇头节点的剩余能量，为两簇头的距离，为下一层级的第j候选簇头节点的簇内节点数，a1、a2、a3分别为三种因素的分配权重且|a1|+|a2|+|a3|＝1。
[0043]
优选地，考虑到簇头间距和簇内节点数与选取中继节点之间呈负相关，设置a2＜0、a3＜0。
[0044]
优选地，在步骤s3中，簇头进行轮调时，对每个簇的簇内节点都进行簇头轮调，其中，将簇内剩余能量较高的节点升级为簇头节点来均衡簇内节点能耗；具体的，设置簇头剩余能量阈值h进行簇头轮调，当wrsn经过周期运行后，如果当前周期簇头节点剩余能量低于设定阈值h则选取本簇内剩余能量最高的节点作为下一周期簇头节点；如果当前周期簇内所有节点的剩余能量都低于设定阈值h，则下一周期簇头节点选取按照簇内节点剩余能量依次选取。
[0045]
与现有技术相比，本发明具有以下有益效果：
[0046]
本发明提出了一种联合区域划分和分簇路由的wrsn能耗优化算法,该优化算法首先利用动态簇半径的区域划分方法对wrsn监测区域进行层级划分，同时确定各个子区域的分簇半径，之后基于k-means算法设计了极大簇的分簇聚类算法和分簇优化策略优化生成的簇结构，最后结合区域划分的层次结构提出层间路由算法实现wrsn簇头节点高效节能的
数据中继传输。通过大量的参数优化实验和算法对比实验表明，本发明所提出的算法能够降低wrsn网络的整体能耗和均衡簇间和层间的节点能耗，大幅延长了wrsn的使用寿命，优化wrsn的分簇结构，提升wce的充电效率和能量利用率。
附图说明
[0047]
图1是本发明所提出优化算法的流程图；
[0048]
图2是基于动态簇半径的区域划分方法得到的区域划分效果示意图；
[0049]
图3是三种不同中继路由区间划分方法中继路由层选取示意图(对应传输方案2-4)；
[0050]
图4是不同参数下jrdfcr算法和jrdhcr算法wrsn死亡节点变化趋势图；
[0051]
图5是不同参数下jrdfcr算法和jrdhcr算法wrsn整体能耗变化趋势图；
[0052]
图6是不同参数下jrdfcr算法和jrdhcr算法wrsn网络覆盖率变化趋势图；
[0053]
图7是不同阈值下jrdfcr算法和jrdhcr算法wrsn死亡节点变化趋势图；
[0054]
图8是不同阈值下jrdfcr算法和jrdhcr算法wrsn整体能耗变化趋势图；
[0055]
图9是不同阈值下jrdfcr算法和jrdhcr算法wrsn网络覆盖率变化趋势图；
[0056]
图10是jrdhcr算法中三种中继路由层选取方法的wrsn死亡节点变化趋势图；
[0057]
图11是jrdhcr算法中三种中继路由层选取方法的wrsn整体能耗变化趋势图；
[0058]
图12是jrdhcr算法中三种中继路由层选取方法的wrsn网络覆盖率变化趋势图；
[0059]
图13是对比试验中，四种算法在500节点wrsn死亡节点数变化趋势图；
[0060]
图14是对比试验中，四种算法在500节点wrsn中整体能耗变化趋势图；
[0061]
图15是对比试验中，四种算法在500节点wrsn网络运行中期节点消耗能量分布图，其中，(a)为jrdfcr算法节点能耗分布，(b)为jrdhcr算法节点能耗分布，(c)为k-chra算法节点能耗分布，(d)为k-clp算法节点能耗分布。
[0062]
如下具体实施方式将结合上述附图进一步说明本发明。
具体实施方式
[0063]
请参阅图1，在本发明的一种较佳实施方式中，一种联合区域划分和分簇路由的wrsn能耗优化算法，包括如下步骤：
[0064]
s1、利用动态簇半径的区域划分方法对wrsn监测区域进行层级划分，得到若干子区域并确定各子区域的分簇半径。
[0065]
在该步骤s1中，动态簇半径的区域划分方法是考虑到“在大规模wrsn的多跳分簇路由中，靠近基站的区域无论是设置为直传区域，还是作为中继区域进行数据汇聚传输到基站都无法避免该区域内节点能量会快速耗尽，无法完成监测和数据采集任务”的缺陷情况而提出的。具体的，步骤s1中，采用动态簇半径的区域划分方法进行层级划分的具体步骤包括：
[0066]
步骤1：考虑节点部署最远距离为正方形监测区域四个顶点a0、b0、c0、d0，wrsn最大簇半径为r，将各顶点分别与中心基站连接并以距a0、b0、c0、d0各顶点为r的位置为圆心分别做圆，四个圆分别交连接线于a1、b1、c1、d1；先将监测区域a0、b0、c0、d0划分为两部分，分别为正方形区域a1b1c1d1和框形区域a0b0c0d
0-a1b1c1d1；
[0067]
步骤2：正方形区域a1、b1、c1、d1四个顶点继续连接中心基站，并以k
sfi
r为半径做圆，得到新的交点a2、b2、c2、d2，进而划分得到正方形区域a2b2c2d2和框形区域a1b1c1d
1-a2b2c2d2；其中，k
sf
为缩放因子，i为第1次划分，i＝1；
[0068]
步骤3：检测步骤s2区域划分后得到的正方形区域的边长，当该边长不小于时，继续进行区域划分，直至该边长小于时停止区域划分；划分时，以上一次划分得到的正方形区域的顶点为基础，重新与中心基站连线，并以k
sfi
r为半径做圆，得到新的交点，并基于此划分得到新的正方形区域和框形区域，其中，i为第几次划分，i＝2，3
…
，n，n为区域划分次数；停止区域划分后，距离中心基站为r的圆形区域自动划分为第n+1区域。
[0069]
上述中，缩放因子k
sf
通过如下公式计算得到：
[0070][0071]
式中，d
max
和d
min
分别为wrsn监测区域中的所有节点距离中心基站最大值和最小值，d(r,bs)为子区域内圆心到中心基站的距离，c为调节因子，取值范围为c∈[0,1]。
[0072]
基于上述划分方法所得到的区域划分效果示意图如图2所示。从图中可以看出，划分距离基站最远的子区域的簇半径最大，为wrsn最大簇半径。随着划分子区域距离基站越近，簇半径可根据调节因子进行最大簇半径的缩放，降低簇内节点数量和簇头节点承担数据收集的任务量，降低簇头节点数据采集和接收能耗，使簇头节点具有更多能量承担数据中继转发任务。因此，本发明所提出的区域划分方法能耗均衡靠近基站的簇结构与距离基站较远的簇结构的能量消耗率，能够有效避免能量空洞问题，同时为各区域确定了簇半径，为后续节点的分簇聚类打下基础。
[0073]
s2、根据步骤s1所得到的子区域分簇半径和子区域内节点，通过极大簇的分簇聚类算法，对步骤s1所划分的各个子区域进行节点分簇聚类。
[0074]
即，步骤s2中的极大簇的分簇聚类算法结合了步骤s1中所使用到的动态簇半径的区域划分方法，来对wrsn划分的子区域进行节点分簇聚类。该分簇聚类算法的具体步骤如下：
[0075]
步骤1：获取步骤s1所得的第l个子区域，并得到该子区域的分簇半径和节点，其中，设第l个子区域的分簇半径为r
l
，节点k为该子区域内节点编号，l＝1,2,...,n，n为子区域数；
[0076]
步骤2：对于子区域内每个节点si，1≤i≤k，以节点为圆心，该子区域的分簇半径r
l
为半径作圆，将满足邻节点条件的其余节点sj划分为该节点si的邻居节点neighbor_si并得到邻居节点数m，其中，邻节点条件为：
[0077][0078]
式中，(xi,yi)为节点si的二维坐标，(xj,yj)为节点sj的二维坐标，j＝1,2，3
…
,k，但j≠i；m为满足邻节点条件的节点sj的数量；
[0079]
步骤3：将子区域内节点按邻居节点数m进行降序排列，选取邻居节点数最多的节点为簇头并构建簇；该簇建立完成后将簇内节点从子区域节点编号中移除，子区域内剩余节点为待成簇节点；
[0080]
步骤4：当步骤3中所得的子区域内的待成簇节点的数量不为0时，以步骤3中所得
的子区域内的待成簇节点为基础，采用步骤2的方法计算待成簇节点的邻居节点数，并采用步骤3构建簇，直到待成簇节点的数量为0时，停止迭代，完成第l个子区域的分簇聚类；
[0081]
步骤5：当步骤4所完成的第l个子区域的分簇聚类的量词l不等于步骤s1中所得的子区域的总数n时，重复步骤1至步骤4以完成第l+1个子区域的分簇聚类；反之进入步骤6；
[0082]
步骤6：输出wrsn整体监测区域的分簇聚类结果。
[0083]
考虑到分簇后子区域可能会存在重叠簇和交叉簇的现象，需要使用分簇优化策略进一步优化簇结构，以减少重叠簇和交叉簇，降低簇头的簇间路由能耗。因此，步骤s2针对每个子区域完成节点的分簇聚类后，均对每一个子区域分簇聚类所得的簇结构采用分簇优化策略进行优化，具体步骤如下：
[0084]
对子区域每个簇计算簇头与中心基站间的距离，并以该距离作为该簇的簇保留优先级，其中，距离中心基站越近，该簇的簇保留优先级越高；
[0085]
依次使用以下分簇优化策略优化各个子区域内的簇结构，其中，策略1：对于包含有相同簇内节点的不同簇保留优先级的簇，保留簇保留优化级高的簇；策略2：对于不同簇保留优先级的簇中，当簇保留优先级低的簇的簇头和簇内节点被簇保留优先级高的簇的簇心包含时，移除簇保留优先级低的簇；策略3：对于所有簇，当簇内节点同时被多个簇包含时，若簇保留优先级低的簇中所有节点能被其余簇保留优先级高的簇的簇内节点包含时，移除簇保留优先级低的簇。
[0086]
上述的极大簇的分簇聚类算法，考虑到了，虽然wrsn中k-means分簇算法核心思想就是依据距离信息进行分簇，并且结合wrsn能耗分析，将距离相近的节点划分到同一簇内可以有效降低簇内通信数据收发能耗，并且便于wce充电对其充电覆盖范围内的簇内节点进行一对多的能量补充；但是，现有的k-means算法会存在以下缺陷和不足之处：(1)k-means算法中k个初始簇节点是随机选取的，选取数量和选取节点的位置都会对最终的分簇聚类结果影响较大，(2)k-means算法没有考虑到wrsn的网络结构和节点能耗情况，k-means算法应用在wrsn生成的分簇结构也无法均衡簇间能耗。因此，为了改善现有状态，本发明使用了上述的极大簇的分簇聚类算法。通过本发明所给出的极大簇的分簇聚类算法，能够有效避免k-means算法中初始k值和节点随机性的影响，同时考虑到wrsn的节点能耗与网络拓扑结构，使用簇保留优先级进行分簇优化策略后可以有效降低簇头节点与基站间数据传输距离，降低簇头的簇间路由能耗，因此，本发明所使用的极大簇的分簇聚类算法能够得到更优wrsn分簇结构，并且便于wce完成充电规划任务。
[0087]
s3、通过中继路由区间划分方法对步骤s1所得的子区域进行区域整合，形成中继路由区间，其中，上一区间层级中的簇头节点根据区间划分方法选取下一级区间对应层级的簇头节点作为中继节点；之后，根据中继路由选择函数选取中继节点，并通过设置簇头剩余能量阈值进行簇头轮调，更新下一周期的中继节点，以均衡节点负载。
[0088]
即，当wrsn完成区域划分和分簇聚类后，wrsn内节点会进入数据采集和传输阶段，在该阶段，本发明通过提出的中继路由区间划分方法和中继路由选择函数相结合的方法实现大规模wrsn中多跳路由中中继节点的选取。
[0089]
具体的，中继路由区间划分方法具体体现在如下中继路由区间划分数据传输方案中：
[0090]
首先，假设步骤s1输出得到了n个子区域，将靠近基站且距离半径为r的圆自动化
为一个子区域，该子区域内节点数据直接单跳传输到基站节点，除去靠近基站距离半径为r的子区域，将wrsn监测区域的其他子区域划分为n-1个层级，假设为k＝n-1个层级，在层级划分中用m1,m2,...,mk表示；那么，当层级数k为奇数时，有传输方案1；当层级数k为偶数时，有传输方案2-4；
[0091]
其中，
[0092]
传输方案1为：将k个层级划分为(k-1)/2个区间，其中l1＝{m1,m2,m3}，l2＝{m4,m5}，li＝{m
2i
,m
2i+1
},i＝2,3,...,(k-1)/2；l1区间中的层级随机选取l2区间的层级作为该层的中级路由层，li区间中的m
2i
层级选取l
i+1
区间的m
2(i+1)
层级作为该层的中级路由层，li区间中的m
2i+1
层级选取l
i+1
区间的m
2(i+1)+1
层级作为该层的中级路由层，最终由l
(k-1)/2
中各层级的簇头节点将数据发送到基站节点；
[0093]
传输方案2为：将k个层级划分为2个区间，其中l1＝{m1,m2,...,m
k/2
}，l2＝{m
k/2+1
,m
k/2+2
,...,mk}；l1区间中的mj层级选取l2区间中的m
k/2+j
层级作为该层的中级路由层，最终由l2中各层级的簇头节点将数据发送到基站节点；其中，j＝1,2,3,...,k/2；
[0094]
传输方案3为：若层级数k满足条件(k+1)/3＝n，n为正整数，则将k个层级划分为(k+1)/3个区间，其中，li＝{m
3i-2
,m
3i-1
,m
3i
}，l
(k+1)/3
＝{m
k-1
,mk}，i＝1,2,...,(k+1)/3-1；li区间中的m
3i-2
层级选取l
i+1
区间中的m
3(i+1)-2
层级作为该层的中级路由层，li区间中的m
3i-1
层级选取l
i+1
区间中的m
3(i+1)-1
层级作为该层的中级路由层，li区间中的m
3i
层级分别选取l
i+1
区间中的m
3(i+1)
层级作为该层的中级路由层，l
(k+1)/3-1
区间中的层级随机选取l
(k+1)/3
区间的层级作为该层的中级路由层，最终由l
(k+1)/3
中各层级的簇头节点将数据发送到基站节点；
[0095]
传输方案4为：将k个层级划分为k/2个区间，其中，li＝{m
2i-1
,m
2i
},i＝1,2,...,k/2；li区间中的m
2i-1
层级选取l
i+1
区间中的m
2(i+1)-1
层级作为该层的中级路由层，li区间中的m
2i
层级分别选取l
i+1
区间中的m
2(i+1)
层级作为该层的中级路由层，最终由l
k/2
中各层级的簇头节点将数据发送到基站节点；
[0096]
上述方案择一形成中继路由区间，在最终选择时，可以针对每个方案进行运行，基于运行的结构选择最终的方案作为优化算法最终的中继路由区间划分方法。
[0097]
为了更方便的解释上述的传输方案，特别是传输方案2-4，在此以八层层级作为例子进行解释说明。其中，传输方案2-4分别对应图3中(a)-(c)所示的结构，具体的，传输方案2为图3(a)中表示的外层-内层两层4-4结构，传输方案3为图3(b)中表示的外层-中层-内层三层3-3-2结构，传输方案4为图3(c)中表示四区间分层2-2-2-2结构。
[0098]
对于传输方案2给出的4-4中继路由区间划分方案，外层的前四层级的簇头节点选取内层的后四层级对应的中继路由层的簇头节点作为中继路由簇头节点，最终内层后四层级的簇头节点将数据发送到基站节点。对于传输方案3给出的3-3-2中继路由区间划分方案，第一次中继路由过程为第1、2、3层级的簇头节点分别在第4、5、6层级中对应的层级选取中继路由簇头节点，在第二次中继路由过程中第4、5、6层级动态选取第7和第8层级的簇头节点作为中继路由簇头节点，最终第7和第8层级的簇头节点将数据发送到基站节点。对于传输方案4给出的2-2-2-2中继路由区间划分方案，首先第1和第2层级的簇头节点分别在第3和第4层级中选取中继路由簇头节点，同理第3层级到第6层级均会选取隔层级的簇头节点作为中继路由簇头节点，最终通过四次簇间路由完成数据的中继传输。
[0099]
在本发明中，对应下一层级中继节点的选取考虑到wrsn的能耗均衡性和网络使用
寿命，将可通信范围内的簇头节点加入到候选簇头集合中，本发明的中继路由选择函数考虑了候选簇头节点的节点剩余能量、候选簇头节点间的距离和候选簇头节点的簇内节点数三个因素，并基于该三个因素，对其归一化后进行加权求和，得到如下的函数关系式：
[0100][0101]
式中，re
max
、dist
max
、clusternumber
max
分别为下一层级中簇头剩余能量最大值、通信范围内两层级间簇头距离最大值和下一层级中簇内节点数最大值，为第l层级的第i个簇头节点，为l层对应下一层级l
′
的第j候选簇头节点，为对应下一层级的第j候选簇头节点的剩余能量，为两簇头的距离，为下一层级的第j候选簇头节点的簇内节点数，a1、a2、a3分别为三种因素的分配权重且|a1|+|a2|+|a3|＝1，考虑到簇头间距和簇内节点数与选取中继节点之间呈负相关，设置a2＜0、a3＜0。
[0102]
根据中继路由选取函数计算公式，可以看出在传输距离相同或相近的情况下，簇内节点少或孤立簇节点往往承担较大的中继路由负担，能够有效均衡簇间的能耗。对于wce进行能量补充时，孤立簇节点的能量补充速度相对较快，可以再次因剩余能量较高当选中继节点来承担负载任务。
[0103]
当wrsn经过一定周期运行后，wrsn由内及外层级间的簇头节点由于中继数据转发会使其能量消耗较快，虽然中继路由选取能够一定程度上分散簇头节点的路由负载度，但是簇头节点相比簇内普通节点仍会快速濒临死亡，因此需要簇内节点进行簇头轮调，将簇内剩余能量较高的节点升级为簇头节点来均衡簇内节点能耗。在本发明的步骤s3中，簇头进行轮调时，对每个簇的簇内节点都进行簇头轮调，其中，将簇内剩余能量较高的节点升级为簇头节点来均衡簇内节点能耗；具体的，设置簇头剩余能量阈值h进行簇头轮调，当wrsn经过周期运行后，如果当前周期簇头节点剩余能量低于设定阈值h则选取本簇内剩余能量最高的节点作为下一周期簇头节点；如果当前周期簇内所有节点的剩余能量都低于设定阈值h，则下一周期簇头节点选取按照簇内节点剩余能量依次选取。
[0104]
s4、在每一个wrsn运行周期内，簇内普通节点会按照分配的时序序号向簇头节点发送自身采集到的监测数据，簇头节点收集融合后，再将数据以单跳、多跳的方式发送到基站节点中完成wrsn一轮运行周期内的工作。
[0105]
基于上述可知，本发明的wrsn能耗优化算法包含基于动态簇半径的区域划分方法和基于极大簇的分簇聚类算法及优化算法和wrsn层间路由。联合区域划分和分簇路由方法用于生成wrsn网络簇结构，wrsn层间路由通过中继路由区间划分与根据中继路由选择函数进行层间多跳传输实现簇间数据传输，最终形成联合区域划分和层间分簇路由的wrsn能耗优化算法。
[0106]
实施例
[0107]
为了验证本发明说提出的一种联合区域划分和分簇路由的wrsn能耗优化算法(下文简称jrdhcr算法)的可行性和效果，本发明做了仿真实验，并对结果进行了分析，具体如下：
[0108]
(1)试验环境与参数设置
[0109]
在pycharm2021平台下通过python3.8搭建wrsn网络模型，实验的硬件环境为intel(r)core(tm)i5-11600kf@3.90ghz，16g内存，操作系统为windows11专业版。设置多种不同的仿真环境对本发明提出的jrdhcr算法与使用简单前向路由的联合区域划分和前向分簇路由能耗优化算法(joint region dvision and forward clustering routing，下文简称jrdfcr算法)，和两种分簇路由算法k-clp算法[30]和k-chra算法[18]在wrsn网络死亡节点数、网络节点能耗、网络节点覆盖率和节点能耗均衡程度等指标进行对比分析，比较所提算法的性能和有效性。
[0110]
其中，jrdfcr算法与本发明的jrdhcr算法仅在路由区间划分数据传输方案上存在不同，具体是，jrdfcr算法没有跨层级的数据传输，对于第mi层级的簇头节点接收第m
i-1
层级簇头节点发送过来的数据信息后，与本簇内接收节点数据信息融合后向前转发到第m
i-1
层级的簇头节点，依次将数据向基站传输，形成前向路由数据传输方案。
[0111]
k-clp算法为文献《基于能量预测的分簇可充电无线传感器网络充电调度》(董颖,崔梦瑶,吴昊,等.吉林大学学报(工学版),2018,48(04):1265-1273)提出的一种算法，k-chra算法则为文献《k-chra:aclustering hierarchical routing algorithm for wireless rechargeable sensor networks》(zhenchun wei,fei liu,xu ding,etal.ieee access,2019,volume7,81859-81874.)给出的一种算法。
[0112]
在仿真实验中，部分通用的实验仿真参数参考文献《基于能量预测的分簇可充电无线传感器网络充电调度》(董颖,崔梦瑶,吴昊,等.吉林大学学报(工学版),2018,48(04):1265-1273)和《wsn中遗传和k均值聚类的多跳路由算法》(苗俊先,赵一帆,朱元静,等.现代电子技术,2021,44(17):42-48.)，具体如下表1所示。
[0113]
表1 wrsn网络能耗通用仿真实验参数
[0114][0115]
(2)不同网络参数对于算法性能影响分析
[0116]
1)中继路由选取函数参数分析
[0117]
考虑到中继路由选取函数参数对本发明jrdhcr算法的影响，根据中继路由选择函
数的函数关系式对三种不同因素的重要权值分配选取了三组不同的测试参数，分别为参数1：a1＝0.3,a2＝-0.5,a3＝-0.2、参数2:a1＝0.5,a2＝-0.3,a3＝-0.2和参数3：a1＝0.2,a2＝-0.5,a3＝-0.3，对500节点的wrsn进行wrsn死亡节点数、wrsn整体能耗、wrsn网络覆盖率等指标的对比实验。总共重复进行了50次路由选取函数参数分析实验，并选取50次实验的平均值进行分析。其中各个参数情况下wrsn中首个节点死亡时、30％节点死亡时、50％节点死亡时的wrsn网络运行轮数如下表2所示。
[0118]
表2不同中继路由选取函数参数两种算法相同死亡节点时的运行轮数
[0119][0120]
从表2中可以看出，整体上，参数2对于jrdfcr算法和jrdhcr算法中首个节点死亡轮数有一定的延长效果，而对于30％节点死亡轮数和50％死亡节点轮数三种参数对比相差不大。其中jrdhcr(参数2)相比jrdhcr(参数1)和jrdhcr(参数3)首个节点死亡轮数延长39.7％和39.2％，jrdfcr(参数2)相比jrdfcr(参数1)和jrdfcr(参数3)首个节点死亡轮数延长33.6％和36.1％。参数2中将簇头节点能量因素在三种影响因素中的权重提高，可以避免找到剩余能量较低的簇头节点当作中继节点，可以均衡中继节点间的网络能耗，进一步地提高和延长wrsn的使用寿命。为了进一步验证参数2对wrsn网络性能和能耗的优化，分别对比了三组不同参数两种算法wrsn死亡节点变化趋势、整体能耗变化趋势和网络覆盖率变化趋势如下图4、图5和图6所示。其中，wrsn网络覆盖率的计算公式如下式所示：
[0121][0122]
式中，area(mi)为层级i的覆盖面积，nodenumber1和nodenumber2分别为该层级存活节点个数和所有节点个数，n为层级总数。
[0123]
图4中可以看出，对于jrdhcr算法，三组参数对于第3000轮中wrsn中整体的网络死亡节点数的影响较小。对于jrdfcr算法，从死亡节点变化曲线可以看出，使用参数2的jrdfcr算法在wrsn运行的前2000轮中，网络死亡节点相对其他两组参数差值较小，而在后1000轮中，使用参数2的jrdfcr算法相比其他两组参数的网络死亡节点有所增加。结合图5和图6中对于两种算法，三组参数情况下的wrsn整体网络能耗基本相同、覆盖率变化曲线基本相似。由于参数2能够有效提升wrsn网络所有节点的存活时间，因此，后续对比试验选取参数2作为jrdhcr算法和jrdfcr算法的中继路由参数。
[0124]
2)簇头轮调剩余能量阈值参数分析
[0125]
考虑到簇头轮调剩余能量阈值对本发明的jrdhcr算法的影响，选取三个阈值进行
对比实验，对于500个节点初始节点能量为2j的wrsn网络，选取节点初始能量的40％、30％和20％作为簇头轮调剩余能量阈值即h＝0.8、h＝0.6、h＝0.4进行wrsn死亡节点数、wrsn整体能耗、wrsn网络覆盖率等指标的对比实验。总共重复进行了50次阈值参数分析实验，并选取50次实验的平均值进行分析。其中，jrdhcr算法和jrdfcr算法在不同簇头轮调阈值情况下的wrsn中首个节点死亡时、30％节点死亡时、50％节点死亡时的wrsn网络运行轮数如下表3所示。wrsn死亡节点变化趋势、整体能耗变化趋势和网络覆盖率变化趋势如下图7、图8和图9所示。
[0126]
表3不同簇头轮调阈值两种算法相同死亡节点时的运行轮数
[0127][0128]
由表3可知当簇头轮调阈值为0.8时，jrdfcr算法和jrdhcr算法的首个节点死亡轮数相较其他两个簇头轮调阈值分别提升12.1％、20.5％和7.6％、20.5％。jrdfcr算法和jrdhcr算法的30％节点死亡轮数和50％死亡节点轮数相较其他两个簇头轮调阈值均有所增加。从图7和图8中可以看出，三个不同阈值对于jrdfcr算法和jrdhcr算法中wrsn整体能耗变化影响较小。对于jrdhcr算法，当h＝0.8时从1500轮至2500轮死亡节点数量较h＝0.4有一定减少，与h＝0.6死亡节点数近似持平。同时，根据图9中可以看出选取h＝0.8时，两种算法的wrsn网络覆盖率都有明显提升。
[0129]
由此可知，提高wrsn中簇头节点轮调的剩余能量阈值能够更好均衡簇内节点的能耗，降低簇头节点由于能耗过大提前死亡导致wrsn中存活的节点数量减少以及wrsn网络覆盖率的降低，影响wrsn的监测覆盖面积以及数据收集质量。因此，后续对比试验时，选取h＝0.8作为jrdfcr算法和jrdhcr算法的簇头轮调剩余能量阈值。
[0130]
3)中继路由区间划分中继路由层选取方法分析
[0131]
在中继路由区间划分方法中采用上文所给的传输方案2-4进行中继路由层选取，对jrdhcr算法进行三种中继路由选取方法进行对比测试。总共重复进行了50次选取方法分析实验，并选取50次实验的平均值进行分析。jrdhcr算法中三种中继路由层选取方法的wrsn死亡节点变化趋势、整体能耗变化趋势和网络覆盖率变化趋势如下图10、图11和图12所示。
[0132]
从图10中可以看出，使用传输方案3给出的3-3-2结构的jrdhcr算法的整体wrsn死亡节点数量在1500轮以后都是小于使用传输方案2给出的4-4结构和传输方案4给出的2-2-2-2结构的jrdhcr算法。在3000轮时，传输方案3给出的3-3-2结构的jrdhcr算法的死亡节点数为428个，相比传输方案4给出的2-2-2-2结构的jrdhcr算法的死亡节点数为465个和传输方案2给出的4-4结构的jrdhcr算法的死亡节点数为475个，分别下降了8％和9.9％。同时在
图11和图12中可知，传输方案3给出的3-3-2结构的jrdhcr算法能够降低wrsn网络节点整体能耗并明显提升了网络覆盖率，这主要是因为在wrsn网络运行中期，传输方案2给出的4-4结构中，后四层级作为中继路由层的中继簇头节点获取前四层级转发数据将直接发送到基站，较长的数据发送距离会导致后四层级的中继路由簇头中继负载较高，会导致簇头节点快速死亡；而传输方案4给出的2-2-2-2结构虽然降低了单次簇间中继路由的数据发送距离，但是多次中继路由会提升中继簇头节点接收数据和转发数据能耗。因此，在后续对比分析试验中，选取传输方案3给出的3-3-2结构作为jrdhcr算法的中继路由区间划分中继路由层选取方法。
[0133]
(3)算法性能指标分析
[0134]
基于上述的参数选取和方案选择，将本发明的jrdhcr算法和jrdfcr算法、k-chra算法、k-clp算法进行对比不同规模下wrsn的能耗优化对比分析，分别对四种算法进行不同网络规模的相同节点部署条件下wrsn死亡节点运行轮数和簇结构对比分析，以进一步验证本发明所提出的算法的有效性。其中，3000轮网络运行时的实验结果如下表4和5所示。
[0135]
表4四种算法不同网络规模下相同死亡节点时的运行轮数
[0136][0137][0138]
表5四种算法不同网络规模下wrsn簇结构
[0139][0140]
由表4中可以看出，随着wrsn网络规模增大jrdfcr算法、k-chra算法和k-clp算法的节点死亡轮数呈提前趋势，其中，400节点规模在首个节点死亡轮数存在较大程度提前现象，这主要是由于节点分布随机性的原因。但综合四组数据可知，jrdfcr算法和jrdhcr算法相较其他两种对比算法，均能够延长网络首个节点、30％节点和50％节点的死亡轮数；jrdfcr算法相比k-chra算法和k-clp算法，在500节点规模情况下，首个节点死亡轮数分别延长了944轮和918轮；jrdhcr算法相比k-chra算法和k-clp算法，在500节点规模情况下，30％节点和50％节点的节点死亡轮数分别延长了85.17％、47.7％和45.3％、18.8％；jrdhcr算法相比jrdfcr算法，能够降低wrsn中期的死亡节点数，也就是能够延长wrsn使用寿命，这是由于jrdhcr算法进行的层级间路由传输虽然提前了靠近基站的中继路由节点的死亡轮数，但避免了数据层层传输导致簇头路由中继次数过多，各个层级的簇头节点能耗过大的问题。
[0141]
由表5中可以看出，随着wrsn网络规模增大，四种算法的成簇个数均有所提升，其中jrdfcr算法和jrdhcr算法都是使用基于极大簇的分簇聚类算法和分簇优化方法，因此成簇个数相同。jrdfcr算法和jrdhcr算法相比k-chra算法和k-clp算法成簇个数更少，能够避免出现簇内节点数量较少的现象，对于wrsn而言，可以降低wce充电规划的复杂度。同时在400节点规模和500节点规模的wrsn中，孤立簇节点个数即单个节点成簇现象更少，更少的孤立簇节点数代表分簇优化算法生成的簇节点分布更加均匀，减少wce为单个簇节点的充电的现象，提升wce的充电效率和能量利用率。
[0142]
再者，分别在500节点相同节点部署条件下对四种算法的wrsn死亡节点数、wrsn整体能耗、wrsn网络覆盖率等指标进行对比分析。四种算法的wrsn死亡节点变化趋势、整体能耗变化趋势和网络覆盖率变化趋势如下图13、图14和图15所示。
[0143]
从图13中可以看出，jrdhcr算法总体的死亡节点数在前2500轮左右相比k-chra算法和k-clp算法有明显减少，并且在2500轮之后jrdhcr算法总体的死亡节点数少于jrdfcr算法。同时，jrdhcr算法和jrdfcr算法均存在一定wrsn网络运行周期中死亡节点不再增加的现象，而k-chra算法和k-clp算法的wrsn死亡节点数一直处于缓慢上升的状态。
[0144]
结合图14和图15可知，jrdhcr算法和jrdfcr算法在wrsn网络运行的前中期能够很好的均衡各个簇节点以及簇间中继簇头节点的能耗，延长wrsn网络的使用寿命。在wrsn网
络运行中后期，jrdhcr算法网络总体能耗低于jrdfcr算法，而jrdfcr算法和jrdhcr算法网络总体能耗高于k-chra算法和k-clp算法，这是由于k-chra算法和k-clp算法中部分节点能耗较高，在wrsn网络运行前中期死亡，降低了wrsn的路由数据量，从而降低了wrsn网络整体能耗。
[0145]
另外，从图15中四种算法wrsn节点消耗能量分布情况看到，相比k-chra算法和k-clp算法，jrdhcr算法和jrdfcr算法有效解决了由于靠近基站节点能耗过高导致的热区效应。jrdfcr算法靠近基站的高能耗节点数量小于jrdhcr算法。相比于k-chra算法和k-clp算法，jrdfcr算法和jrdhcr算法整体节点能耗负载较为均衡，而k-clp算法和k-chra算法，由于存在较多的外层孤立簇节点，导致当wce进行充电时，存在较多靠近基站较远的待充电节点，wce的充电行驶距离相比jrdfcr算法和jrdhcr算法有所增加，会降低wce的充电效率。对于wrsn网络运行时前100个死亡节点，其中，jrdhcr算法死亡节点主要集中在靠近基站的三个层级以及最外层级，而jrdfcr算法死亡节点更加均衡分布在八个层级中，因此，当wce从服务站出发后开启充电规划时，jrdhcr算法总体的充电移动路径将小于jrdfcr算法。
[0146]
综上分析可知，本发明提出的jrdhcr算法的性能优于其他三种对比分析算法，jrdhcr算法能够降低wrsn网络的整体能耗和均衡簇间和层间的节点能耗，大幅延长了wrsn的使用寿命，优化wrsn的分簇结构，提升wce的充电效率和能量利用率。
[0147]
上述说明是针对本发明较佳可行实施例的详细说明，但实施例并非用以限定本发明的专利申请范围，凡本发明所提示的技术精神下所完成的同等变化或修饰变更，均应属于本发明所涵盖专利范围。

技术特征：
1.一种联合区域划分和分簇路由的wrsn能耗优化算法，其特征在于，包括如下步骤：s1、利用动态簇半径的区域划分方法对wrsn监测区域进行层级划分，得到若干子区域并确定各子区域的分簇半径；s2、根据步骤s1所得到的子区域分簇半径和子区域内节点，通过极大簇的分簇聚类算法，对步骤s1所划分的各个子区域进行节点分簇聚类；s3、通过中继路由区间划分方法对步骤s1所得的子区域进行区域整合，形成中继路由区间，其中，上一区间层级中的簇头节点根据区间划分方法选取下一级区间对应层级的簇头节点作为中继节点；之后，根据中继路由选择函数选取中继节点，并通过设置簇头剩余能量阈值进行簇头轮调，更新下一周期的中继节点，以均衡节点负载；s4、在每一个wrsn运行周期内，簇内普通节点会按照分配的时序序号向簇头节点发送自身采集到的监测数据，簇头节点收集融合后，再将数据以单跳、多跳的方式发送到基站节点中完成wrsn一轮运行周期内的工作。2.如权利要求1所述的wrsn能耗优化算法，其特征在于，步骤s1中，采用动态簇半径的区域划分方法进行层级划分的具体步骤包括：步骤1：考虑节点部署最远距离为正方形监测区域四个顶点a0、b0、c0、d0，wrsn最大簇半径为r，将各顶点分别与中心基站连接并以距a0、b0、c0、d0各顶点为r的位置为圆心分别做圆，四个圆分别交连接线于a1、b1、c1、d1；先将监测区域a0、b0、c0、d0划分为两部分，分别为正方形区域a1b1c1d1和框形区域a0b0c0d
0-a1b1c1d1；步骤2：正方形区域a1、b1、c1、d1四个顶点继续连接中心基站，并以k
sfi
r为半径做圆，得到新的交点a2、b2、c2、d2，进而划分得到正方形区域a2b2c2d2和框形区域a1b1c1d
1-a2b2c2d2；其中，k
sf
为缩放因子，i为第1次划分，i＝1；步骤3：检测步骤s2区域划分后得到的正方形区域的边长，当该边长不小于时，继续进行区域划分，直至该边长小于时停止区域划分；划分时，以上一次划分得到的正方形区域的顶点为基础，重新与中心基站连线，并以k
sfi
r为半径做圆，得到新的交点，并基于此划分得到新的正方形区域和框形区域，其中，i为第几次划分，i＝2，3
…
，n，n为区域划分次数；停止区域划分后，距离中心基站为r的圆形区域自动划分为第n+1区域。3.如权利要求2所述的wrsn能耗优化算法，其特征在于，缩放因子k
sf
通过如下公式计算得到：式中，d
max
和d
min
分别为wrsn监测区域中的所有节点距离中心基站最大值和最小值，d(r,bs)为子区域内圆心到中心基站的距离，c为调节因子，取值范围为c∈[0,1]。4.如权利要求1所述的wrsn能耗优化算法，其特征在于，步骤s2中，通过极大簇的分簇聚类算法进行的节点分簇聚类的具体步骤如下：步骤1：获取步骤s1所得的第l个子区域，并得到该子区域的分簇半径和节点，其中，设第l个子区域的分簇半径为r
l
，节点k为该子区域内节点编号，l＝1,2,...,n，n为子区域数；步骤2：对于子区域内每个节点s
i
，i＝1,2，3
…
,k,以节点为圆心，该子区域的分簇半径
r
l
为半径作圆，将满足邻节点条件的其余节点s
j
划分为该节点s
i
的邻居节点neighbor_s
i
并得到邻居节点数m，其中，邻节点条件为：式中，(x
i
,y
i
)为节点s
i
的二维坐标，(x
j
,y
j
)为节点s
j
的二维坐标，j＝1,2，3
…
,k，但j≠i；m为满足邻节点条件的节点s
j
的数量；步骤3：将子区域内节点按邻居节点数m进行降序排列，选取邻居节点数最多的节点为簇头并构建簇；该簇建立完成后将簇内节点从子区域节点编号中移除，子区域内剩余节点为待成簇节点；步骤4：当步骤3中所得的子区域内的待成簇节点的数量不为0时，以步骤3中所得的子区域内的待成簇节点为基础，采用步骤2的方法计算待成簇节点的邻居节点数，并采用步骤3构建簇，直到待成簇节点的数量为0时，停止迭代，完成第l个子区域的分簇聚类；步骤5：当步骤4所完成的第l个子区域的分簇聚类的量词l不等于步骤s1中所得的子区域的总数时，重复步骤1至步骤4以完成第l+1个子区域的分簇聚类；反之进入步骤6；步骤6：输出wrsn整体监测区域的分簇聚类结果。5.如权利要求1所述的wrsn能耗优化算法，其特征在于，步骤s2针对每个子区域完成节点的分簇聚类后，均对每一个子区域分簇聚类所得的簇结构采用分簇优化策略进行优化。6.如权利要求5所述的wrsn能耗优化算法，其特征在于，采用分簇优化策略进行优化的步骤如下：对子区域每个簇计算簇头与中心基站间的距离，并以该距离作为该簇的簇保留优先级，其中，距离中心基站越近，该簇的簇保留优先级越高；依次使用以下分簇优化策略优化各个子区域内的簇结构，其中，策略1：对于包含有相同簇内节点的不同簇保留优先级的簇，保留簇保留优化级高的簇；策略2：对于不同簇保留优先级的簇中，当簇保留优先级低的簇的簇头和簇内节点被簇保留优先级高的簇的簇心包含时，移除簇保留优先级低的簇；策略3：对于所有簇，当簇内节点同时被多个簇包含时，若簇保留优先级低的簇中所有节点能被其余簇保留优先级高的簇的簇内节点包含时，移除簇保留优先级低的簇。7.如权利要求1所述的wrsn能耗优化算法，其特征在于，步骤s3中，中继路由区间划分方法具体体现在如下中继路由区间划分数据传输方案中：首先，假设步骤s1输出得到了n个子区域，将靠近基站且距离半径为r的圆自动化为一个子区域，该子区域内节点数据直接单跳传输到基站节点，除去靠近基站距离半径为r的子区域，将wrsn监测区域的其他子区域划分为n-1个层级，假设为k＝n-1个层级，在层级划分中用m1,m2,...,m
k
表示；那么，当层级数k为奇数时，有传输方案1；当层级数k为偶数时，有传输方案2-4；其中，传输方案1为：将k个层级划分为(k-1)/2个区间，其中l1＝{m1,m2,m3}，l2＝{m4,m5}，l
i
＝{m
2i
,m
2i+1
},i＝2,3,...,(k-1)/2；l1区间中的层级随机选取l2区间的层级作为该层的中级路由层，l
i
区间中的m
2i
层级选取l
i+1
区间的m
2(i+1)
层级作为该层的中级路由层，l
i
区间中的m
2i+1
层级选取l
i+1
区间的m
2(i+1)+1
层级作为该层的中级路由层，最终由l
(k-1)2
中各层级的簇头
节点将数据发送到基站节点；传输方案2为：将k个层级划分为2个区间，其中l1＝{m1,m2,...,m
k/2
}，l2＝{m
k/2+1
,m
k/2+2
,...,m
k
}；l1区间中的m
j
层级选取l2区间中的m
k/2+j
层级作为该层的中级路由层，最终由l2中各层级的簇头节点将数据发送到基站节点；其中，j＝1,2,3,...,k/2；传输方案3为：若层级数k满足条件(k+1)/3＝n，n为正整数，则将k个层级划分为(k+1)/3个区间，其中，l
i
＝{m
3i-2
,m
3i-1
,m
3i
}，l
(k+1)/3
＝{m
k-1
,m
k
}，i＝1,2,...,(k+1)/3-1；l
i
区间中的m
3i-2
层级选取l
i+1
区间中的m
3(i+1)-2
层级作为该层的中级路由层，l
i
区间中的m
3i-1
层级选取l
i+1
区间中的m
3(i+1)-1
层级作为该层的中级路由层，l
i
区间中的m
3i
层级分别选取l
i+1
区间中的m
3(i+1)
层级作为该层的中级路由层，l
(k+1)/3-1
区间中的层级随机选取l
(k+1)/3
区间的层级作为该层的中级路由层，最终由l
(k+1)/3
中各层级的簇头节点将数据发送到基站节点；传输方案4为：将k个层级划分为k/2个区间，其中，l
i
＝{m
2i-1
,m
2i
},i＝1,2,...,k/2；l
i
区间中的m
2i-1
层级选取l
i+1
区间中的m
2(i+1)-1
层级作为该层的中级路由层，l
i
区间中的m
2i
层级分别选取l
i+1
区间中的m
2(i+1)
层级作为该层的中级路由层，最终由l
k/2
中各层级的簇头节点将数据发送到基站节点；上述方案择一形成中继路由区间。8.如权利要求1所述的wrsn能耗优化算法，其特征在于，步骤s3中，中继路由选择函数考虑到候选簇头节点的节点剩余能量、候选簇头节点间的距离和候选簇头节点的簇内节点数三个因素，并基于该三个因素，对其归一化后进行加权求和，得到如下的函数关系式：式中，re
max
、dist
max
、clusternumber
max
分别为下一层级中簇头剩余能量最大值、通信范围内两层级间簇头距离最大值和下一层级中簇内节点数最大值，为第l层级的第i个簇头节点，为l层对应下一层级l
′
的第j候选簇头节点，为对应下一层级的第j候选簇头节点的剩余能量，为两簇头的距离，为下一层级的第j候选簇头节点的簇内节点数，a1、a2、a3分别为三种因素的分配权重且|a1|+|a2|+|a3|＝1。9.如权利要求8所述的wrsn能耗优化算法，其特征在于，考虑到簇头间距和簇内节点数与选取中继节点之间呈负相关，设置a2＜0、a3＜0。10.如权利要求1所述的wrsn能耗优化算法，其特征在于，在步骤s3中，簇头进行轮调时，对每个簇的簇内节点都进行簇头轮调，其中，将簇内剩余能量较高的节点升级为簇头节点来均衡簇内节点能耗；具体的，设置簇头剩余能量阈值h进行簇头轮调，当wrsn经过周期运行后，如果当前周期簇头节点剩余能量低于设定阈值h则选取本簇内剩余能量最高的节点作为下一周期簇头节点；如果当前周期簇内所有节点的剩余能量都低于设定阈值h，则下一周期簇头节点选取按照簇内节点剩余能量依次选取。

技术总结
本发明提出一种联合区域划分和分簇路由的WRSN能耗优化算法，该优化算法通过提出一种基于动态簇半径的区域划分方法，使得其能够根据WRSN的网络结构和节点能耗情况，动态调整簇半径，以实现WRSN不同区域中节点能耗均衡，并在K-means算法基础上提出了一种基于极大簇的分簇聚类算法和分簇优化策略，优化并得到更加合理的WRSN簇结构，最后，通过中继路由区间划分与中继路由选择函数，均衡簇间和层间的节点能耗，缓解热区效应问题，同时也优化了WCE充电移动路径，从而降低WRSN网络的整体能耗，延长WRSN的网络使用寿命。WRSN的网络使用寿命。WRSN的网络使用寿命。


技术研发人员：张烈平 陈泓源 李智浩 黄自晨 尹亚梦
受保护的技术使用者：桂林理工大学
技术研发日：2023.06.20
技术公布日：2023/10/7