改进的网络路由协议低功耗自适应分簇算法

刘 军，李 岩，齐 华

（1.武警工程学院，陕西 西安 710086；2.西安工业大学电子信息工程学院，陕西 西安 710032）

0 引言

无线传感器网络（Wireless Sensor Network）［1］是数据采集、处理及通信功能于一体的分布式自组织网络，具有分布式式处理带来的高监测精度、高容错性、大覆盖区域、可远程监控等众多的优点，在军事、环境监测、医疗、智能建筑及其他商业领域等方面有着广泛的应用。

无线传感器网络中传感器节点能量有限，不同于传统的有限网络。无线传感器网络的路由协议必须时刻关注降低能耗、延长网络生命周期这一核心问题［2］。设计精良的网络协议就可以降低能耗，延长网络的生命周期。目前，路由协议的主流是层次路由协议，该协议具有代表性的路由算法是低功耗自适应分簇（LEACH）算法［3］。LEACH 算法中，簇首形成高一层的网络，这样簇内成员的功能就变相对简单，大大减少了路由控制信息的数量。但该算法也存在着簇首分布不均匀、簇首与基站之间只能采用单跳路径的问题。针对以上问题，以降低功耗，实现能量均衡、延长网络寿命为目的，对LEACH算法进行改进。

1 LEACH算法的分析

LEACH 算法（Low Energy Adaptive Clustering Hierarchy）是 MIT的Chandrakasan等人为无线传感器网络设计的低功率自适应分簇路由算法。它的基本思想是以循环的方式随机选择簇首节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到提高网络整体生存时间的目的。

1.1 LEACH算法的工作流程

该算法的建立主要包括三个阶段：

1）簇首的建立阶段

簇头节点的选取是LEACH算法中的关键，具体的选择方法是：各节点产生一个［0，1］之间的随机数，若该数小于某一个阈值T（n），则该节点成为簇头。T（n）［4］如公式：

式中，p是网络中簇头数与总节点数的百分比；r是当前的选举轮数；G是最近1／p轮不是簇头的节点集合。

被选为簇首的节点会利用CSMA MAC协议广播ADV消息，宣布自己成为簇首。非簇首节点收到来自各簇首的消息，并根据接收信号的强度选择强度最大的簇首发送加入请求JOIN－REQ，其包含了节点的ID和要求加入簇首的ID信息。

2）时隙表建立阶段

当簇首确定并且簇域划分工作完成，簇头将根据成员节点的数目，产生TDMA时隙表［5］。成员节点通过接收簇首的广播获取该表，并在自己的时隙到达时才开启发送装置向簇首发送数据，其余时间处于休眠状态以节省宝贵能量。

3）稳定阶段

相对于簇的建立阶段，这个阶段是相对较长的一个阶段，该阶段主要是各节点完成数据传输的任务。一旦簇形成，TDMA时刻表确定，则数据传输开始。簇首节点在收到成员节点传来的数据后对数据进行数据融合和压缩，将压缩处理后的信号传输给基站。

1.2 LEACH算法存在的问题

1）寿命不均：簇首的选举策略是随机的，可能造成簇首分布不均，簇成员个数也有较大差异，使得各簇首负载不均衡，造成个别簇首较早死亡。

2）距离受限：LEACH协议只适用于小规模的无线传感器网络。由于基站与簇首之间采用单跳路径选择模式，所以簇首与基站必须布置在通信可达的范围内。

2 LEACH算法的改进

2.1 改进算法的设计思路

针对LEACH算法中存在簇首寿命不均、传输距离受限的问题，并结合无线传感器网络自身的特点，本文从以下几个方面对LEACH算法进行改进。

1）改变簇首产生方式来均衡各各簇首寿命

簇首的产生主要从以下两个方面加以改变：

①基于节点的剩余能量选择簇首。考虑到无线传感器网络的能耗问题，选取能量较多节点作为簇首。将节点的剩余能量作为选择簇首的一个重要衡量标准，保证区域内剩余能量较多的节点被选为簇首。

②基于节点与簇首之间的距离选择簇首。考虑到簇首地理分布平均的问题，每个簇首发射信号，其他节点根据接收到的信号判断离簇首的距离，离簇首距离小于设定值M的节点不再选为簇首。从而保证所有簇首之间距离不小于M。

2）改变簇首与基站之间的通信方式来增加传输距离

LEACH算法中，簇首与基站之间的数据发送过程采用单跳的方式。由于基站距离传感区域很远，所以簇首将数据发送给基站时所消耗的能量很多，基于这一点，在簇首向基站发送数据的时候采用多跳的方式，这样可以使簇首节点能量的消耗相对减少。因此，本论文提出的改进算法将会把簇首组织起来，以多跳的方式向基站发送融合之后的数据。

2.2 改进算法的实现

与传统的LEACH算法相比，改进后的算法在选择簇首之前，传感区域内的所有节点需要将自己的地理位置信息和节点能量发送给基站，基站收集到区域内各个节点的位置信息后，根据这些信息将传感器网络按面积平均划分为k个区域（本论文中设定k＝3，如图1所示，这就意味着需要将整个区域划分为三部分）。

区域划分完成以后，每个节点随机产生一个0～1之间的随机数，如果小于阈值T（n），则该节点当选为候补簇首，T（n）的计算与LEACH算法中相同，然后把选出的候补簇首按能量的大小递减排列成一个队列，从队列中第一个节点开始，取消以节点为圆心，半径为M的圆内的其它候补簇首成为簇首的资格，并将其从列队中删除。依次遍历其他节点，重复上述操作，最后剩下的候补簇首成为最终簇首。

图1 传感区域的划分Fig.1 The regional division

当选为簇首的节点会将自己的ID添加到该簇域的全局变量ch＿list＿中去，最终得到的ch＿list＿就是该簇域内所有簇首节点ID的列表。通过簇域的ch＿list＿即可以得到下游簇域内的所有节点的ID列表，所谓下游指的是指向BS方向的下一个簇域，有了该列表，就相当于得到了下一跳的候选列表，如图2所示，簇首只需从这些候选节点中随机选出一个节点作为自己的下一跳节点，这样就将各个簇首的多跳路径建立起来了。

簇首确定、簇域划分完成后，各簇域将建立各自的时隙表，时隙表建立后，进入到稳定传输阶段。

图2 簇首多跳路径示意图Fig.2 Multi－ hop path

3 算法的仿真及分析

3.1 仿真平台的构建

本文 采 用 NS2［6］对 LEACH 及 改 进 后 的LEACH算法进行了仿真。NS2（Network Simulator）是一种内核源代码开放的，针对网络研究的离散事件大型可视化仿真器。它能够建立目前几乎所有网络对象的基本模型之间的互连，并且使复杂的网络交通和拓扑结构得到高度切合实际的模拟和仿真。仿真环境设定如下：

1）传感器节点和虚拟聚类区域具有全局唯一的ID标识；

2）网络内所有传感器节点均相同，具有相同的初始能量2J，且到BS均可达；

3）各个传感器节点具备GPS功能，即节点能定位其位置。

3.2 仿真结果与分析

1）图3对两种算法在不同时段仍然存活的节点个数做出了比较。

图3 网络中存活节点数量的仿真Fig.3 Simulation of alive node number

从图3可以得出以下结论：

①LEACH算法在365s的时候出现节点死亡，而改进后的算法在375s的时候开始有节点出现死亡。从节点开始死亡的时间上来说，改进后的算法相对于LEACH算法提高了2.73%。

②LEACH算法在500s左右的时候结束了网络生命，而改进后的算法在580s左右的时候才结束网络生命，从网络存活时间比较来说，改进后的算法比LEACH算法延长了16%。

2）不同时段网络内存活节点数目的比较很直观地说明了两种算法下网络生命周期的不同，下面从能量消耗的角度来进一步对两种算法进行比较。

图4比较了两种算法下在不同时段网络消耗总能量的值，可以看出LEACH算法在500s结束网络生命时的总能耗是450J左右，而改进后的算法在580s结束生命周期时总能耗是350J。更进一步印证了算法较LEACH算法延长了网络生命周期。

图4 网络总能量消耗的仿真Fig.4 Simulation of energy consumption

3）两种算法的性能比较

New－LEACH算法和LEACH算法相比，性能有所提高。从表1可以看出，如果以节点开始死亡的时间为标准，New－LEACH算法相比LEACH算法能有2.73%的提高；若以网络生命周期为标准，则有16%的提高；如果以网络总能耗为标准，相比LEACH算法，New－LEACH算法获得了21%的性能提高。

表1 不同路由协议下网络生命周期的比较Tab.1 The comparison of life－cycle under different network routing prorocols

4 结论

本文针对无线传感器网络，在理论分析的基础上提出了一种改进的LEACH算法。该算法在选择簇首方面，充分地考虑了网络中节点的位置和剩余能量，进而使簇的大小更为合理；在簇首与基站之间的路径选择方面，采取了多跳传输的方式。通过NS2的仿真实验表明：与传统的LEACH算法相比较，网络的能量消耗率降低了将近21%。因此，改进后的算法能更有效地降低与均衡网络的能量消耗，从而较大幅度的延长了传感器网络的生命周期。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京：清华大学出版社，2005.

［2］余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法［J］.电子学报，2008，36（7）：1 309－1 313.YU Yongchang，WEI Gang.An improved pegasis algorithm in wireless sensor network［J］.Acta Electronica Sinica，2008，36（7）：1 309－1 313.

［3］Shah R C，Rabaey J.Energy Aware Routing for Low Energy Ad hoc Sensor Networks［C］／／Orlando：IEEE Wireless Communications and Networking Conferenee（WCNC），2002：350－355.

［4］陶东.基于无线传感器网络LEACH协议的仿真分析研究［J］.现代电子技术，2011：24－26.TAO Dong.Analysis and simulation of leach routing protocol in wireless sensor networks［J］.Modern Electronics Technique，2011（11）：24－26.

［5］王盛.基于NS2的无线传感器网络LEACH协议的改进仿真研究［D］.武汉：武汉理工大学毕业论文，2010.

［6］徐雷鸣.NS与网络模拟［M］.北京：人民邮电出版，2003.