适于地下管廊的无线传感网络节能分簇算法

商益民，施亦旺，胡力勤，骆 懿

(1.杭州电子科技大学通信工程学院，浙江 杭州 310018；2.中国电信股份有限公司浙江分公司，浙江 杭州 310001；3.浙江建设职业技术学院，浙江 杭州 311231)

0 引 言

随着城市的现代化发展，地下管廊成为城市建设的重要组成。常用的地下管廊监控方式是将通信电缆作为信息传输的载体，但是，地下管廊又长又窄，贯通整个城市，通信电缆架设困难，成本高，不易维护，而无线传感器网络布局简单，架设成本低，同时自组织能力强，能大规模组网，可靠性也高[1]，适宜地下管廊环境。由于无线传感器网络的能量由电池供电，经常在地下管廊中更换电池是不现实的[2]，同时，无线传感器网络能耗不均，地下管廊的长远大于宽，导致能耗更加不均[3]。针对这些技术难题，学者们主要通过在分簇拓扑结构下延长网络的生命周期，例如，刘广聪等[4]提出二分K-means算法，将圆簇进行二分裂，通过合并过小的簇来均衡网络簇结构，但是大小簇合并复杂，随意性大；王丹丹等[5]在地下管廊中随机部署网络结构，改进网络模型，对监测区域分簇，但采用随机部署网络结构使得节点数目过多，增大了网络能耗。本文提出一种基于层次聚类和固定部署网路结构的综合算法，简称HC-CFSFDP，在固定部署网络结构下，通过二分裂思想和快速搜索密度峰值聚类(Clustering by Fast Search and Find of Density Peaksd，CFSFDP)[6]将监测区域进行分簇，从而使网络生命周期得到延长。

图1 管廊的二维平面网络结构模型图

1 网络模型与最优簇数计算

无线传感器网络的能耗不均主要受簇首能耗的影响，簇间通信的能耗与簇首数量成正比，簇内通信所消耗的能量与簇首数量成反比，因此，适合的簇首数能大大均衡网络的能耗。以管廊的二维平面建立数学模型，如图1所示。图1中，部署传感器节点感知范围满足全覆盖，同时节点感知范围的重叠面积也是最小的，此时簇为椭圆簇。监测区域为长方形，椭圆表示簇；部署在管廊上的黑点为传感器节点；虚线圆表示节点的感知范围。长方形区域的长为L，宽为M(L≫M)。因此，监测区域内的网络模型呈现单行线形椭圆形状，以图1所示，长方形监测区域内单行排列k个椭圆簇，因此，假设椭圆簇的长半轴长和短半轴长分别为M/2和R。

椭圆簇与监测区域的关系如下：

(1)

从式(1)中可以得出k与R的关系：

(2)

长方形区域内分布着k个簇，N个传感器节点，簇成员节点服从均匀分布，采用经典无线电模型[7]计算。则关系式为：

(3)

根据式(2)和(3)可以计算得出簇首与簇内节点平方距离的期望值，则该值为：

(4)

由式(4)可知，每一个簇内簇成员节点的平均能耗为：

(5)

每一个簇的簇首节点的平均能耗为：

(6)

式中，dBS为基站与簇首距离，Eelec为发射机或接收机电路发送或接收每bit信息量所消耗的能量，εfs为自由空间模型能耗系数，εmp为多路径放大电路能耗系数，EDA为每bit数据融合的耗能。根据式(5)和式(6)可知，单个簇的平均能量消耗为：

(7)

通过式(7)可以得到整个网络的总能耗为：

(8)

将Etotal对k求导，得出最优簇数kopt为：

(9)

2 基于层次聚类的的节能分簇算法

本文提出的基于层次聚类和固定部署网路结构的综合算法HC-CFSFDP主要是通过自上而下的层次聚类思想[8]进行分簇操作。首先，根据第1节计算k值，作为一轮中分簇过程的结束条件；然后，根据母簇选举因子选举出母簇，用CFSFDP分裂母簇；最后，通过簇首综合指标选举出各自的簇首节点，根据相应的路由传输数据。分簇流程如图2所示。

图2 分簇协议流程图

图2中，J为当前监测区域内簇的个数，Gc为选出需要被分裂的簇的选举因子，k为最优簇数，i为当前被选举出簇首的数量。算出当前每个簇的Gc值，最大值的簇就会成为下一个被分裂的簇，1个簇分裂成2个簇，此时簇数就增加1个，即J增加1。

2.1 截断距离的优化

CFSFDP是通过局部密度和邻近距离来聚类。首先，在数据节点集中找到满足以下条件的点作为汇聚中心点：(1)汇聚中心节点的密度比其周围所有节点的都要高；(2)汇聚中心周围节点与该汇聚中心点距离相比于与其它汇聚中心点的距离来说，是最近的。然后，该汇聚中心与距离其近的节点组成一个簇。邻近距离使2个汇聚中心点更加分散，利于母簇分裂成2个子簇。局部密度使汇聚中心点与大多数邻近点的距离都较近，利于母簇的选举和减少簇的能耗，而局部密度是根据截断距离的大小来确定范围的。通过多次的计算得出，该网络模型中簇内每个节点的平均邻居节点个数与节点总数的比例为3%～5%，此时，能大大优化局部密度，CFSFDP很好地与本文的细胞分裂思想结合起来，每次分裂都均衡了网络的能耗。

2.2 母簇的选取

无线传感器节点部署在长方形监测区域内，该区域就是本文初始的母簇，初始母簇直接一分为二，从分裂出的若干簇中选出接下来要分裂的簇，依次选取簇，对簇进行下一步分裂，直到满足簇数为k，才结束分裂。当一个簇的相对面积更大，同时母簇中各节点与汇聚中心的距离方差更大时，这样的簇才是此次要被选取分裂的簇。母簇中的节点数目与母簇的面积成正比，基于此，构造1个目标函数用于在许多簇中选取出合适的簇作为要被分裂的簇：

(10)

2.3 簇首选举

根据HC-CFSFDP协议和网络模型。当簇内节点的局部密度越大，节点与基站距离越短，同时节点的剩余能量更充足，此时该节点成为簇首节点的可能性更大。本文构造1个目标函数用于在簇中选举出合适的节点作为簇首：

(11)

3 仿真分析

表1 仿真参数值

仿真实验中，节点分别分布于的300×20和600×20的长方形区域中，其基站坐标分别为(150,10)和(300,10)，无线传感器网络都是同构网络，初始能量为0.5 J。分别采用低功耗自适应分簇算法(Low Energy Adaptive Clustering Hierarchy，LEACH)、分布式节能分簇算法(Distribute Energy-Efficient Clustering，DEEC)、低功耗自适应的比例能量分簇算法(LEACH Proportion Energy Algorithm，LPEA)和HC-CFSFDP进行100次仿真实验，以平均值作为最后实验结果。在2种网络规模下，从网络生命周期、网络能耗和网络吞吐量方面进行比较。实验相关参数如表1所示。

3.1 网络生命周期

表2 不同算法在不同网络规模下的节点死亡轮数

第1个节点和最后1个节点死亡轮数均能反映网络生命周期的情况。不同算法的无线传感器网络在不同网络规模下的节点死亡轮数如表2所示。

由表2可知，在网络运行过程中，LPEA的网络存活节点超过LEACH，因为LPEA的节点死亡较慢，使得LPEA的网络生命周期要比LEACH长；DEEC在每轮簇首选举时考虑了节点剩余能量和网络的平均能量，延长了网络的生命周期，在2种网络规模中，与LEACH相比，DEEC将网络生命周期分别延长了4.4%，10.1%；HC-CFSFDP的簇首选举考虑了节点能量，簇首与基站间的距离和簇内节点距离，两个距离的综合使得长方形区域对整个网络性能的影响进一步降低，最终延长了网络的生命周期，在2种网络规模中，与LEACH相比，HC-CFSFDP将网络的生命周期分别延长了22.9%，15.2%。

3.2 网络能耗

不同算法的网络剩余能量在不同网络规模和轮数的比较如表3所示。

表3 不同算法在不同轮数和网络规模下的网络剩余能量 单位：J

由表3可知，网络能耗速度与网络的部署区域长度成正比，其原因在于节点通信距离随着区域变长而变长，这样增加了节点通信能量的消耗。由表3可知，HC-CFSFDP在最优簇首数的计算、簇的形成和簇首选举方面都均衡了整个网络的能耗，使得其能耗速度明显要比LEACH,LPEA,DEEC慢。

3.3 网络吞吐量

表4 不同算法在不同网络规模下的网络吞吐量 单位：bit·s-1

不同算法在不同网络规模下的网络吞吐量之间的比较。比较情况如表4所示。

由表4可知，LPEA在数据吞吐总量上比LEACH的稍微多一点。DEEC的传输总量超过LEACH和LPEA，DEEC在簇首选举时考虑了网络的平均能量，保证了网络更长的通信能力，从而增大了网络的数据吞吐量。HC-CFSFDP的吞吐量始终高于其他算法，在2种网络规模下，其数据吞吐总量分别是DEEC的152.3%和120.2%，是LPEA协议的176.6%和245.8%，因此，HC-CFSFDP的网络生命周期更长，使得网络能长久稳定地传输更多数据。

4 结束语

针对二分K-means算法和随机网络部署网络结构在地下管廊中应用的不足，本文提出一种基于层次聚类和固定部署网路结构的HC-CFSFDP算法。算法结合二分K-means算法的分簇思想和新网络结构，在大小簇的处理和节点的部署方面都有很大的改善，提高了网络的性能。本文算法是在二维网络模型下完成的，但是，现实应用中都是空间三维结构，下一步将进行三维网络模型实验，使无线传感器网络的应用更符合实际。