基于节点相对密度的无线传感器网络成簇算法*

卢建刚，乐红兵

(江南大学物联网工程学院，江苏无锡214122)

无线传感器网络的路由算法从网络逻辑结构角度可以分为平面型和层次型两种。由于平面路由算法中节点需要较多存储空间来维持较大路由信息，同时在数据处理上不能进行有效数据融合，因此该路由算法不适用于大型的传感器网络。层次路由算法又称分簇路由算法，这类算法在一定程度上克服了平面路由算法的不足，其中 LEACH［1］(Low Energy Adaptive Clustering Hierarchy)是最早提出的分簇路由算法，后来的许多分簇路由算法都是在它的基础上发展起来的。

无线传感器网络中分簇路由算法的改进一般都是围绕簇头的选择，成簇的方法以及数据传输的方式来考虑设计的。不少国内外研究人员针对LEACH算法的改进也主要从这三个方面进行。早期改进算法中比较经典的有Ossama Younis等人提出的HEED算法［2］，它在簇头的选择过程中考虑了节点的剩余能量，但因在簇头选择时约束条件过多，故而增加了算法的复杂度。Heinzelman W等人提出的LEACH-C算法［3］采用集中控制，它考虑节点能量和位置信息，但需要通过基站来控制节点如何成簇，这样网络不是完全自组织的，使用范围受到限制。近年来国内外也有不少学者从事这方面的研究，提出一些比较好的改进方法。如文献［4］采取在每个簇内增加副簇头来保证数据传输的稳定性，有效地解决了簇头在数据传送过程中因为能量耗尽而中断传输的问题。文献［5］提出的模糊路由和数据融合算法整体改善了整个网络的能量损耗，但该算法的可操作性比较差。国内的张伟华等人提出的LEACH-B算法［6］在选择簇头时将节点的当前能量和节点充当簇头的次数综合考虑了进来，然而当网络运转时间较长，整个算法优势将会变得不明显。李成岳等人提出的LEACH-T算法［7］采用了时间间隔来选取簇头，保留了分布式产生簇头的优点，避免了每轮产生簇头个数的不确定性，但该算法对传感器的要求较高，不便于广泛的推广应用。

本文在综合研究LEACH及其相关改进算法的基础上，针对LEACH算法存在簇头分布不均和簇间负载不均衡的问题，提出了一种通过考虑节点相对密度来选择簇头和采取选择合理中转簇头完成多跳通信的算法。通过Matlab的仿真表明，该算法有效改善了网络生存时间和簇间负载均衡的问题。

1 问题描述

1．1LEACH算法

LEACH算法是MIT学者A．Chandrakasan等人为无线传感器网络设计的低功耗自适应聚类路由算法。LEACH算法提出了“轮”的概念，每轮分为簇的建立阶段和稳定的数据通信阶段，簇头通过轮换来达到均衡节点能耗的目的。

初始化阶段是簇头的形成阶段。在初始阶段，每一个节点从0～1中选取一个随机数，如果这个随机数小于这一“轮”所设定的门阈值T(n)，那么这个节点就成为簇头。T(n)的计算公式:

式中:p是网络中簇头所占比例;r为当前的轮数;G为在最后的1/p轮中还没有成为过簇头的节点集。节点在当选簇头后，需要发布消息告知其它节点自己是簇头。非簇头的节点根据接受信号的强度来选择它要加入的簇，并通知相应的簇头。最后簇头产生一个TDMA定时消息，并且通知簇内节点。当簇内节点收到TDMA同步消息后，它们将在各自的时间段内发送数据，在时段外是进入睡眠状态。簇形成和TDMA时刻表确定后，就进入了本轮的数据传输阶段。簇头把来自簇内节点的数据进行数据融合和压缩处理后，传给远处的基站。经过一个TDMA时刻表后，新的一轮又开始了，如此循环运行，直到大多数节点的能量耗尽为止。

1．2 LEACH算法存在的问题

(1)在LEACH算法中簇头的选择是通过采用阈值判定方法来选取的，具有极大的随机性。这种随机性可能造成簇头在网络中分布不均匀，导致有些节点密集区域簇头过少甚至没有，而有些节点稀少区域内簇头过多，使得一部分节点无法加入任何簇或者促使其成员节点与较远簇头进行数据传输而消耗自身过多的能量。

(2)在LEACH算法中，由于簇头选举的随机性使得网络中簇头需要负担的节点数不同，在这种情况下可能加重了个别簇头的负担，导致簇间负载不均衡，使得整个网络的负载平衡程度下降。

(3)在无线传感器网络中数据传输的能量消耗主要包括电路能量消耗和功放能量消耗，并且后者是主要的。依据空间信道模型，功放能耗的大小取决于信号的传输距离，因此随着传输距离的增加，传输所消耗的能量将急剧上升。在LEACH算法中，簇头与基站之间的单跳数据传输方式会造成簇头能量消耗过大。

以上所提及LEACH算法所存在的问题，严重地影响了网络的生存时间和簇间的负载平衡。为了有效地解决以上问题，本文提出了一种基于节点相对密度成簇算法—LEACH-D。

2 改进算法及分析

2．1 系统描述

2．1．1 网络模型

所有的传感器节点被随机部署在一个N×N的正方形区域，周期性的采集该区域的信息。同时对建立的无线传感器网络作如下假设:

(1) 传感器网络建立后，节点在网络中的位置将不会发生变化。

(2) 基站部署在该监测区域外的一个固定位置，且基站是唯一的。

(3) 网络中所有传感器节点初始能量相同，且能量是有限。

(4) 节点的无线发射功率可以依据接收者的距离进行调整。

(5) 节点之间连接对称。若已知对方发射功率，则节点可以依据接收信号强度计算出发射者距自己的距离。

2．1．2 能量模型

无线能量模型根据通信节点之间的传输距离d的大小分为自由空间模型和多路径衰减模型，式(3)为发送kbit数据消耗的能量，d0是决定哪种模型的阈值，它的大小由式(2)确定:

接收kbit的数据需要消耗的能量为:

其中，Eelec是收发电路所消耗的能量，εfs、εmp分别为两种模型中功率放大所需的能量。

2．2LEACH-D 算法

2．2．1 相关定义

(1)邻居节点 在网络中每个传感器节点都存在一个通信半径，处于此通信半径范围之内的节点称为其邻居节点。

阳泉市位于山西省中部东侧，全市总面积4 578 km2。地下水开采以娘子关泉域岩溶水为主，娘子关泉域岩溶地下水以水量集中稳定、水质良好成为阳泉市工农业生产及城市供水的重要供水水源。

(2)节点相对密度 在标准通信半径R范围内，节点所在实际网络中的邻居节点数与标准簇内邻居节点数的比值。节点n的相对密度计算公式如下:

其中标准通信半径R的大小为:

式中，Neighbor(n)_alive表示节点n在标准通信半径范围内的邻居节点数;S表示节点所在区域的面积;N为网络区域内的节点数;p表示簇头占网络节点总数的百分比;式(5)中，(1/p)－1是标准簇内的邻居节点数。

2．2．2 簇头的选择

在以往针对LEACH算法的改进中很大一部分是通过对节点自身因素的考虑来决定簇头的选择，却往往忽略了周围其他节点的影响，这样会由于节点分布状况不明而造成簇头在整个网络中的分布不均匀。为了有效地反映每个节点所在区域内节点的分布状况，本文在文献［8］的基础上提出相对节点密度的概念，并通过节点相对密度(如公式(5)所示)的大小来影响簇头在整个网络中的分布。

为了确保簇头在整个网络中合理分布，使得节点密集程度高的区域出现簇头的个数多于节点密集程度低的区域，需采取的方法就是增大处于节点密集区的节点成为簇头的概率;反之，则降低节点密集程度低所在区域的节点成为簇头的概率。为此，本文在簇头的选择问题上将节点相对密度这个因素考虑进来，通过节点相对密度来影响簇头的分布。从而得到改进后的簇头选举阈值T(n)为:

根据公式(7)计算簇头选举时的阈值T(n)可以看出，簇头的选择不再是单个节点的事情，而是要与周围节点数联系起来一起考虑，这样就保证了每轮簇头选举中处于网络密集区的节点有更大概率被选为簇头节点的可能，同时为了避免簇头集中出现在同一密集区造成覆盖区域重叠的状况，在当选簇头的竞争区域内应尽量避免其它候选簇头的出现。

本文在数据传输上采用多跳通信，但是这种通信方式使得靠近基站的簇头除了进行自身簇内信息的收集，还要额外的担负起其他簇头的信息中转，造成这一区域的簇头能量消耗过大，导致产生了新的“热区”问题［9－10］。为了克服这个问题，本文在簇的规模上进行了控制，使得越靠近基站区域节点成簇的规模越小，让处于基站附近的簇头有更多的能量用于其他簇头的信息中转，保持簇间负载均衡。

为了实现簇的规模控制，本文在文献［11］的基础上采取了一种改进的分簇规模约束机制，即在簇形成阶段设置簇内非簇首节点数目的门限值以控制成簇的规模。其中，每个簇头拥有的门限值的大小根据簇头距离基站的远近自动调整，即距离基站近的簇规模小，远离基站远的簇规模大。如果节点i成功当选簇头，则其簇内节点数目N(i)应控制在M(i)的范围内。当簇内节点数超过其控制的范围，簇头则拒绝接受其他节点入簇要求，并告知这些节点去选择其他较近且簇内成员未满的簇头成簇。同时，如果出现节点到基站的距离小于或等于节点到簇头的距离，则选择节点直接与基站通信。其中M(i)的大小为:

其中:d(CHi，BS)是簇头i到基站的距离;dCHmin是簇头到基站的最近距离;dCHmax是簇头到基站的最远距离;e是修正节点数的加权因子，本文e取2/3。

2．2．4 数据传输

当簇生成后，就需建立簇头与基站之间的通信。本文根据节点成簇的特点，在数据传输中采取了簇头间多跳转发机制。因此，如何合理选择中转簇头成为多跳数据传输中的关键问题。

在构建路由表时，每个簇头为了能找到更合理中转簇头，需要建立一张候选中转簇头集C(i)。为了将邻近簇头纳入到自己的候选中转簇头集中，每个簇头需以更大的通信半径2·R广播一条消息Head-Msg，其中包含簇头的ID、剩余能量及其与基站的距离d。每个簇头需通过以上获取的信息来决定邻近簇头是否存在于自己的候选中转簇头集中。其中候选中转簇头集C(i)定义为:

假设簇头i在C(i)中选取簇头j作为中转簇头，簇头j在C(j)中选取簇头h作为中转簇头，且在通信过程中采用自由空间模型。计算传输kbit数据时消耗i和j两个簇头的能量为:

由上式可知，在数据传输中网络能量的消耗取决于d(i，j)和d(j，h)的大小。然而只考虑中转簇头距离的远近，而忽略其能量的大小，容易使单个中转簇头在转发任务中能量过早耗尽，造成数据传输中断。因此，本文综合考虑了中转簇头的剩余能量和距离，并通过比较候选中转簇头集中簇头T(CHi)的大小来建立更加合理网络路由。

其中 ECHi－current是簇头 i的剩余能量;ECHi－init是簇头 i的初始能量;d(CHi，CHy)是簇头 i到簇头y的距离;dCHmax是簇头到基站的最远距离;v1是加权系数。

路由表的建立从离基站最远的簇头y开始，簇头y通过查询C(y)中簇头T(CHi)的大小来选取拥有最大T(CHi)的簇头作为其父节点。当出现簇头T(CHi)相等的情况时，则根据ID的大小决定其父节点。该父节点继续搜索，并选择它的候选中转簇头中权重最大的作为根节点，依次搜索，直至所有簇头加入到树中，完成簇树路由的构建，并由最后选取的根节点将数据传递给BS，如图1所示。

图1 簇树路由的构建

2．2．5 算法分析

性质 整个算法的控制消息复杂度为O(N)

证明 本算法每轮产生的控制消息包括:(1)在每轮算法开始前，每个节点以半径R广播一条Hello-Msg，用来统计邻居节点数。(2)在簇生成过程中，对于普通成员节点，只要发送一条请求入簇消息Join-Msg，用于加入所选的簇;簇头需要发送一条当选簇头消息CH-Msg，宣布当选簇头。(3)在构建簇树路由的过程中，每个簇头以半径2R广播一条Head-Msg。设簇头比率是P，从而网络中总的控制消息开销为:

因此整个算法的控制消息复杂度是O(N)

3 仿真结果及分析

在仿真实验中，无线传感器网络由100个节点组成，随机分布在100 m×100 m的区域内，基站位于平面坐标(50 m，175 m)，节点当选簇头的概率p取0．05，节点的通信半径 R根据式(6)取25．2 m。本文使用MATLAB对LEACH算法、EERP算法［12］和LEACH-D算法进行了仿真比较，参数的设置如表1所示。

表1 仿真环境主要参数

在数据传输过程中，计算簇头权重的加权系数v1的大小直接影响整个算法的性能。图2显示了v1取不同值时，LEACH-D算法中第一个节点死亡发生的轮数。当v1的取值从0．1逐渐增加到0．2的过程中，中转簇头的选择在考虑数据中转能量消耗的同时，也增加对中转簇头当前能量的考虑，实现了均衡中转簇头能耗的目的，进而延缓第一个节点死亡发生的时间;当v1的取值大于0．2时，过分注重中转簇头当前能量，而逐渐忽略簇头在数据中转时的能量消耗，最终造成中转簇头能量消耗过大，从而加快了第一个节点死亡发生的时间。故从图1可以看出，v1存在一个最优值0．2，此时第一个节点死亡发生的时间最晚。

图2 不同V1取值下的第一个节点死亡发生的轮数

将这三种算法置于同等条件下，分别进行相关性能指标的测试。图3显示的是在三种不同算法作用下剩余节点数量的对照图。从曲线的差别可以看出:(1)LEACH-D算法中第一个死亡节点出现时间滞后于LEACH算法和EERP算法;(2)随着时间的推移，LEACH-D算法中节点减少的速度比在LEACH算法和EERP算法明显放缓。通过比较三种算法作用下的曲线可以更加直观说明改进后的算法更好地平衡了网络负载，实现了延长网络生命周期的目的。

能耗是衡量改进后算法性能的关键指标。从图4节点剩余能量曲线的走势可以看出:在整个网络生命周期中，改进后的LEACH-D算法剩余能量曲线的下降速度要慢于其他两种算法曲线。大约在r=400的时候，改进后的算法在能量消耗上比LEACH、EERP要少得多。可见，LEACH-D算法通过均衡节点能耗，促使节点总能耗的降低。

图3 剩余节点曲线图

图4 总能耗曲线图

网络生存时间能够比较直观的反映改进后算法的优劣性。本文分别采用网络中1%、10%、50%、70%节点死亡发生轮数对三种算法进行了对比评价。仿真结果如图5所示，EERP算法在LEACH算法的基础上优化了数据的传输路径，提高了整个网络生存周期。其中，1%、10%、50%和70%的死亡节点发生的轮数分别较前者提高了3．7%、5．7%、5．9%和4．4%。而本文路由算法在均衡网络能量消耗方面比EERP算法有了进一步的改善。其中，1%、10%、50%和70%的死亡节点发生的轮数分别比EERP算法提高了5%、3．6%、6%和4．4%。故就网络的整体性能指标来看，本文的路由方案在均衡网络能量消耗方面比以上两种方案有了改进。

图5 不同方案下存活时间

4 总结

针对实际网络中可能出现传感器节点分布不均匀以及LEACH算法的不足，本文提出了一种基于节点相对密度来选择簇头，并根据数据多跳传输的特点，采取构建簇树路由的方法来解决网络中簇间负载不均衡的问题。MATLAB仿真实验表明，LEACH-D算法相对LEACH算法、EERP算法而言，能促进簇头的均匀分布，有效均衡整个网络的节点能耗，从而提高网络的生命周期。

［1］ HeinzelmanW ，Chandrakasan A，Balakrishnan H．An Application-Specific Protocol Architecture for Wireless Microsensor Networks［C］//IEEE Transactions on Wirelesss Communications，2002，1(4):660－670．

［2］ Younis O，Fahmy S．A Hybrid，Energy Efficient，Distributed Clustering Approach for Ad-Hoc Sensor Networks［J］．IEEE Trans．on Mobile Computing，2004，3(4):660 －669．

［3］ Heinzelman W．Application-Specific Protocol Architectures for Wireless Networks［D］．Boston:Massachusetts Institute of Technology，2000．

［4］ Yassein M Bani，Al-zou’bi A，Khamayseh Y，et al．Improvement on LEACH Protocol of Wireless Sensor Network(VLEACH)［J］．Journal of Digital Content Technology and its Applications(JDCTA)，2009，3(2)．

［5］ Hamzeh M，Arab S，Fakhraie S M，et al．An Improvement on LEACH Algorithm with a Fuzzy Processor［C］//Proceedings of the 14th Asia-Pacific Conference on Communications(APCC)．IEEE Communications Society，2008:1 －5．

［6］ 张伟华，李腊元，张留敏，王选政．无线传感器网络LEACH协议能耗均衡改进［J］．传感技术学报，2008，21(11):1918 －1922．

［7］ 李成岳，申铉京，陈海鹏，孙恩岩．无线传感器网络中LEACH路由算法的研究与改进［J］．传感技术学报，2010，23(8):1163－1167．

［8］ 乔俊峰，刘三阳，曹祥宇．无线传感器网络中基于节点密度的簇算法［J］．计算机科学，2009，36(12):46 －49．

［9］ 李成法，陈贵海，叶懋，吴杰．一种基于非均匀分簇的无线传感器网络路由协议［J］．计算机学报，2007，30(1):27 －36．

［10］ 刘明，黄小燕，刘锐．一种区域间能量均衡的无线传感器网络分簇算法［J］．传感技术学报，2009，22(4):548 －551．

［11］ 张秋余，彭铎，刘洪国．基于能量的无线传感器网络分簇路由算法［J］，计算机应用研究，2009，26(2):674 －676．

［12］ 王微，冯远静，俞立．一种高能效的无线传感器网络路由协议设计［J］．传感技术学报，2008，21(12):2061 －2066．