适用于智能间隔棒的双集群无线传感网高效节能分簇算法

李良 吴念 王峥 孙海全 武穆清

（1.北京智芯微电子科技有限公司 北京市 100192 2.北京邮电大学 北京市 100876）

随着国家对智能电网项目的重视以及电力系统状态检修等工作的展开，输电线路在线监测的相关技术也得到了迅猛发展。而传感器网络因能通过对输电线路各种运行参数进行在线监测，且集信息采集、传输和处理一体，综合传感器、嵌入式计算、无线通信以及分布式信息处理等技术，已成为智能电网领域一种非常重要的技术手段，被称作是“智能信息感知末梢”。输电线路智能间隔棒是将各类运行参数监测的传感模块、数据传输模块、供电模块与已有间隔棒高度集成的输电线路在线监测产品之一。

在传感电气集成网络中，数据传输通常具有突发性，同时面临传输环境造成的不可靠性，因此要以尽可能高的速率在短时间内完成大量信息的传输，需要在网络协议和软件控制上采取负载均衡机制，提高多径衰落条件下的传输性能和容量。均衡过程包括业务接入过程中的均衡和保持过程中的均衡：业务接入过程主要考虑无线资源管理连接的建立以及无线接入承载指派过程；业务保持过程主要考虑的切换过程的均衡，需要根据传输链路统计分析节点在网络中所处的地位以及在保证网络数据流量的稳定性、可靠性及实时性的情况下，针对网内数据传输具有的非均匀性，设计负载均衡的网络地址转换策略。在无线传感器网络的特定范围内分布有许多传感器节点，由于多跳路由和多对一的数据流量模式，汇聚节点和汇聚节点相邻的节点需要消耗更多的能量进行数据的转发，这样使得它们的能量消耗速度远远超过其他部分的传感器节点[1-4]。

消耗较少的能源得到较多的信息是传感器网络节能的目的。分簇机制不仅能够通过分层的方式有效对传感器节点进行管理，而且能够减少节点传输过程中的能量消耗，具有拓扑管理方便、数据融合简单等优点，是当前传感器网络重点研究的一种路由技术。

文献[5]提出了一种Low Energy Adaptive Clustering Hierarchy（LEACH）算法协议,在LEACH 中，在从节点中选择簇头时未考虑节点剩余电量和到数据接收器的距离，因此节点在向簇头或是数据接收器传送数据时消耗了更多的能量。文献[6]提出了一种LEACH 的扩展版本（EECS），该文基于剩余能源选择一些候选节点用于簇头选择，EECS 将簇头分布在网络中，较之LEACH 算法延长网络生命周期在35%以上，仍不是十分理想。文献[7]介绍了Hybrid Energy-Efficient Distributed（HEED）协议，簇头节点的选择是基于节点的剩余电量及节点到其相邻节点的距离。HEED 算法为了减少节点尤其是簇头节点更高的能量损失增大了集群成员数量，定期触发集群建立过程。但HEED 算法存在一个严重问题：靠近簇头节点的数据接收器会因为通信开销提前耗尽电量。文献[8]提出了基于权重的多跳，集群内通信算法称为基于分布权重的能量效率分层聚类（DWEHC）。其中，节点计算其对残余能量的权重和与到它们相邻节点的距离，邻域中的最大加权节点被选为簇头。DWEHC 在整个网络中极好地分布节点能量消耗，但是节点因为迭代和算法的重新聚类过程也产生了大量的控制消息开销。类似于DWEHC，一个集中的节能路由体系结构（ECRA）具有均匀密度的无线传感器网络分簇算法中在[9]中提出。ECRA 通过使用k-均值聚类算法完成聚类过程，保持理想的聚类分布，网络集群使用K均值聚类法和簇头选择该算法完成了网络的全部数据传输后，会重新构造簇结构。在ECRA 中，节点能量消耗明显减少并在节点之间独立分布。

本文旨在研究适用于输电线路智能间隔棒的无线传感器网络体系结构中网络层的路由技术，对网络能源负载平衡算法进行改进。本文提出了一种针对传感网的双层节能分簇算法，建立两层集群来平衡传感器的能源负载，对主集群使用K-均值集群方法，而对子集群通过角色成员关系建模寻找簇头节点的能源补救措施。仿真结果证明，新提出的两级集群高效节能的分簇算法可以有效地延长网络生命周期。

1 分簇算法

目前在无线传感器网络中典型的分簇算法主要有LEACH（Low2 Energy Adaptive Clustering Hierarchy） 算 法 和HEED(A Hybrid, Energy-Efficient Distributed clustering approach)算法等。

1.1 随机选择簇头的LEACH算法

LEACH 是最典型的无线传感器网络分簇算法之一，由MIT 的学者W.R Heinzelman 等人首次提出，是一种基于簇类结构的分层技术协议。

LEACH 算法簇头选择分为以下两步：

1.1.1 周期进行

LEACH 的运作以“轮”来实现，每一轮周期由“设置”和“稳定”这两个阶段构成。每一轮的设置阶段都需要随机进行簇头和集群成员簇的构造。

1.1.2 随机选择

簇头的选取，将由对所有的节点产生的由0 到1 的随机数决定。如果数值小于阈值 ，则该节点将当选为当前周期的簇头节点。

阈值的表达式为：

其中P 为节点当选为簇头的概率，r 为当前周期循环的次数，G 为在1/P 轮未成为簇头节点的集合，En_current表示节点的当前能量，En_max表示节点的初始能量，rs表示节点没有成为簇头的连续循环次数。

1.2 主次参数的HEED算法

HEED 算法以剩余能量和簇内的通信耗能这两个参数计算出节点成为簇头的概率[10]。剩余能量为主参数。与此同时，HEED 算法定义了平均最小可达能量（Average Minimum Reachability Power， 简称：AMRP）。AMRP 表达为：

图1：总传输数据流的对比

图2：生存节点与生命周期的对比

图3：节点总能耗和通信数据流量对比图

其中M 为簇内节点的数量，minP 为最小能耗级别。

HEED 算法主要分为三个阶段：初始阶段，循环阶段和最终阶段。

1.2.1 初始阶段

在初始阶段，首先设置节点成为簇头的初始概率，初始概率随着网络运行和节点的剩余能量发生改变，成为节点被选作簇头的最终概率 。

1.2.2 循环阶段

在循环阶段中，在簇内循环寻找最小传输能量通信的节点作为簇头节点。每次循环过程结束之后，将节点的乘以2，在进入下一次循环。依此类推，直到找到簇头节点之后中止循环。

1.2.3 最终阶段

在最终阶段，每个节点决定其最终的状态，选择簇头并加入该簇。若节点为孤立节点，则申明该节点为簇头节点。

1.3 算法分析

LEACH 算法实现了对分层无线传感器网络数据的传输管理，并且在选取簇头时考虑了节点的剩余能量，但该算法在每一周期的开始阶段都需要重新构造簇，簇头能量的开销十分巨大，并且离散式区域算法无法做到最优，位置较远的簇头节点会因长距离传输提前耗尽能力。HEED 算法不仅考虑了节点剩余能量，而且还考虑了簇内的通信消耗，在一定程度上保证了节点的能耗负载平衡。然而同样在每一轮都要消耗能量进行簇头的选择，而且簇内节点相对固定，没有考虑中继节点的剩余能量问题。在这种分层多对一的传输过程中，还是容易形成“能量洞”的问题。

2 模型建立

传感器节点最主要的功能是数据的采集及其向基站进行的转发，但随着传感器数量的增多，监测空间范围的扩大，数据包的路由会更加复杂，直接影响到节点的能耗[11]。而且，无线传感器网络中的高密度节点造成了数据的高冗余度，网络对冗余数据的处理会严重缩短生命周期。对网络进行集群是对及节点进行高效节能和减少数据冗余的有效路由手段。因此，需要设计一种高效节能容错嵌套的集群算法对能源负载进行平衡，这对延长无线传感器网络的生命周期至关重要。

2.1 模型简化

首先对新建立的网络模型提出下列假设：

（1）第n 个能量约束均匀传感器节点被部署在兼容密度为L*L 的二维区域内；

（2）数据接收器或基站位于部署区域的中心，具有无限的电源；

（3）所有节点都配备有独立的电源，且初始电量相同；

（4）节点的传输范围可以根据需要的通信距离进行动态调整。同时，假设节点都可以与数据接收器直接通信；

（5）如果两个节点被告知是邻居节点，则它们一定在彼此的传输范围内；

（6）节点不知道本身的位置信息，但它根据接收信号强度指标可以获知到邻居节点的近似距离；

（7）收集到的数据可以被簇头压缩合并成单一的数据包簇头。

2.2 模型建立

本文使用一阶无线模型。无线电发射机和接收机电路能量损耗为发射放大器在自由空间(εfs)传播模型中的损耗10pJ/bit/m2，双射线(εpm)模型中的为0.013pJ/bit/m4。同时假设在自由传播空间和双射线空间中的路径损耗分别为r2和r4。因此，在距离为d 的链路上传播lbits 数据，消耗的能量为：

接收这些消息，消耗的能量为：

3 算法设计

使用k-均值聚类算法可以将给定的传感器节点划分成固定数量的集群。HEED 算法基于节点的剩余能量和簇间通信代价两个参数的比值来增加节点被选做汇聚节点的概率，从而进行周期性地选择簇头。我们在k-均值聚类算法和改进的基于角色成员关系HEED算法的基础上提出了双层集群节能分簇算法。此算法分为确定主集群和子集群两个阶段。首先应用改进的k-均值聚类算法将网络区域划分为一定数量的主集群。之后应用改进的基于角色成员关系的分簇算法将确定子集群的簇头并将每个主集群划分成一定数量的子集群。子集群中确定的簇头可以收集集群中其他节点的数据。主集群中确定的簇头可以汇总簇头的数据，并将数据传输到基站。

算法如 Algorithm 1。

首先使用改进的k-均值聚类算法根据节点的剩余能量将网络区域划分成Km个集群。主集群Km的数量通过下式确定：

其中M 是部署区域的面积，R 是节点的传输距离，X 是两个簇头之间的最大距离。分母是通过改进算法得到的各个集群的覆盖面积。算法聚类处理之后，一组节点被选作簇头，用于主集群的通信。之后将每个主集群划分成一定数量的子集群。群划分成一定数量的子集群。

之后应用改进的基于角色成员关系的分簇算法将每个主集群划分为一定数量的子集群，以节点的剩余能量和通信代价两个参数作为依据，确定子集群中节点的角色关系和成员关系。

节点的初始化概率根据下面的公式确定：

Cprob是成为汇聚点的初始概率，CHprob是通过能源消耗的比例和通信代价这两个参数得到该点成为汇聚点的最终概率。

定义两个参数the_role 和is_belong。the_role 为传感器的角色关系信息，is_belong 是节点的成员关系信息，在算法开始运行之前将所有节点看成非成员关系。根据传感器节点的邻节点关系形成集合Snbr，Sgroup 将传输范围radius 内的Snbr 构成一个初始的成员组。然后通过CHprob循环寻找组内合适的汇聚节点和中继节点。确定汇聚节点后，通过is_sink_msg（Node ID，final_sink，cost）消息将信息发送给所有的成员节点，同时确定其角色为汇聚点。而汇聚点的邻节点可以作为备用汇聚节点，同时汇聚节点的邻节点又扮演着中继点的角色。源节点可以收到一个或者多个汇聚节点发送的信息，节点可以根据关系程度rational_sink（Ssink-radius）来选择合适的汇聚节点，并加入该汇聚点的成员组，通过汇聚节点的is_sink_msg（Node ID, final_sink，cost）和源节点回应的is_member_msg（Node ID, final_sink, cost）确定其成员关系。如果该节点已经是某个成员组的源节点，当汇聚点发生变化时，可以通过join_group（Node ID, final_sink, cost）选择合适的成员关系。

4 仿真结果

本文利用MATLAB 软件进行仿真，仿真环境为1000*1000 的网络大小，其中节点个数为1000 个。仿真起始时各节点处于相同的基础能量，仿真过程中各节点遵循相同的消耗的能量损耗模型。算法的性能将从仿真结果的运行生命周期和通信数据流量进行分析，并与现有的LEACH 算法和HEED 算法进行对比。

图1 是相同起始能量下，不同算法间总数据流量的对比图。从图中可见，随着仿真次数的增加，本文的双层集群节能分簇算法传输的总数据流量保持相对的稳定；与LEACH 和HEED 两种算法相比较，双层集群节能分簇算法在能量相等的前提下，具有更高的数据流量。

图2 是相同起始能量下，生存节点数量随时间变化图，其反映了整个传感网络的寿命。对比其余两种算法，可见在相同生命周期时，双层集群节能分簇算法生存节点数量较多；节点能量全部耗尽时，双层集群节能分簇算法生存周期最长，即整体网络寿命最长，表明本文的算法均衡各节点间能量提升了节点能量使用效率。

图3 反映了节点总能耗与通信数据流量间的关系。由图可见，在相同的通信数据流量下，双层集群节能分簇算法节点总能耗明显小于其他两种算法，整体节能效果明显。

从仿真结果可以获知，LEACH 算法由于只考虑了簇头节点的能源消耗，并未考虑到簇内节点消耗的不均匀。而HEED 算法是通过相邻节点去分担簇头节点的负载，但是负载总量还是相对集中，能量消耗并不均匀。双层集群节能分簇算法通过分布式的双层数据聚合的方式，减小节点的传输范围，从而使节点间的能耗负载均匀分布于各节点，最终提升传感网络的整体寿命。

5 结语

本文深入研究了无线传感网在智能电网中的应用特点，针对数据传输的突发性，传输环境的不可靠性，和整个无线传感网络的能耗问题，提出了双层集群节能分簇算法（DCES）。该分簇算法结合k-均值聚类的思想和基于角色成员关系的思想，以节点的剩余能量和簇间通信代价两个参数作为依据进行传感器节点的聚类和簇头的选择。最后，通过MATLAB 仿真平台对该算法进行仿真。仿真结果表明，相较于其他分簇算法，本文提出的双层集群节能分簇算法对传感网络构建双层集群，减小了节点的传输范围，实现了节点之间的负载均衡，延长了网络的寿命。后续的研究中我们将扩大该算法的适用范围，提升此算法在大规模网络中的性能，将其应用于更复杂的场景，并在实际场景中进行测试。