无线传感器网络（WSN）[1]是集数据采集、处理及通信功能于一体的分布式自组织网络，其特点是能量、计算能力和存储空间有限。无线传感器网络中的路由协议必须时刻关注降低能耗、延长网络生命周期这一核心问题。设计精良的网络协议就可以降低能耗，延长网络的生命周期。通常无线传感器网络的路由协议[2]可以分为平面路由协议和层次路由协议两种。目前，路由协议的主流是层次路由协议，该协议具有代表性的路由算法是低功耗自适应分簇（LEACH）算法[3]。LEACH协议中，簇首形成高一层的网络，这样簇内成员的功能就变相地简单，大大减少了路由控制信息的数量。但该协议也存在耗能大、能量不均衡的问题。针对以上问题，本文通过对经典的分簇路由协议LEACH的分析，并且以降低功耗、实现能量均衡、延长网络寿命为主要目的，对LEACH协议进行改进。
1 LEACH算法分析
LEACH算法（Low Energy Adaptive Clustering Hierarchy）是MIT的Chandrakasan等人为无线传感器网络设计的低功率自适应分簇路由算法。它的基本思想是：以循环的方式随机选择簇首节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到提高网络整体生存时间的目的。LEACH在运行过程中不断地循环执行簇的重构过程，每个簇重构过程可以用“轮（round）”来描述，每一轮包含簇的建立和稳定运行两个阶段。其中稳定阶段持续时间要比簇建立阶段持续的时间长得多。
1.1 LEACH算法的工作流程
该算法的建立主要包括三个阶段：
（1）簇首的建立
簇头节点的选取是LEACH算法中的关键，具体的选择方法是：各节点产生一个[0，1]之间的随机数，若该数小于某一个阈值T(n)[4]，则该节点成为簇头。
式中，p是网络中簇头数与总节点数的百分比，r是当前的选举轮数，G是最近1/p轮而不是簇头的节点集合。
被选为簇首的节点会利用CSMA MAC协议广播ADV消息，宣布自己成为簇首。非簇首节点收到来自各簇首的消息，并根据接收信号的强度选择强度最大的簇首发送加入请求JOIN-REQ（其包含了节点的ID和要求加入簇首的ID信息）。
（2）时隙表建立
当簇首确定并且簇域划分工作完成后，簇头将根据成员节点的数目，产生TDMA时隙表。成员节点通过接收簇首的广播获取该表，并在自己的时隙到达时才开启发送装置向簇首发送数据，其余时间处于休眠状态以节省能量。
（3）稳定
相对于簇的建立阶段，稳定阶段是相对较长的一个阶段，该阶段主要是各节点完成数据传输的任务。一旦簇形成，TDMA时刻表确定，则数据传输开始。簇首节点在收到成员节点传来的数据后对数据进行数据融合和压缩，将压缩处理后的信号传输给基站。
1.2 LEACH算法存在的问题
（1）寿命不均：簇首的选举策略是随机的，可能造成簇首分布不均，簇成员个数也有较大差异，使得各簇首负载不均衡，造成个别簇首较早死亡。
（2）距离受限：LEACH协议只适用于小规模的无线传感器网络。由于基站与簇首之间采用单跳路径选择模式，所以簇首与基站必须布置在通信可达的范围内。
2 LEACH算法的改进
2.1 改进算法的设计思路
针对LEACH算法中存在的问题，结合无线传感器网络的特点，本文从以下几个方面对LEACH协议进行改进。
（1）改变簇首产生方式
主要从以下两个方面改变簇首的产生：
①基于节点的剩余能量选择簇首。考虑到无线传感器网络的能耗问题，选取能量较多的节点作为簇首。将节点的剩余能量作为选择簇首的一个重要衡量标准，以保证区域内剩余能量较多的节点被选为簇首。
②基于节点与簇首之间的距离选择簇首。考虑到簇首地理分布平均的问题，每个簇首发射信号，其他节点则根据接收到的信号判断离簇首的距离，离簇首距离小于设定值M的节点不再选为簇首，从而保证所有簇首之间距离不小于M。
（2）改变簇首与基站之间的通信方式
LEACH算法中，簇首与基站（BS）之间的数据发送过程采用单跳的方式。由于基站距离传感区域很远，所以簇首将数据发送给基站时所消耗的能量很多。基于这一点，在簇首向基站发送数据的时候采用多跳的方式，这样可以使簇首节点能量的消耗相对减少。本文提出的改进算法是把簇首组织起来，以多跳的方式向基站发送融合后的数据。
2.2 改进算法的实现
在第一轮开始时，传感区域内的所有节点需要将自己的地理位置信息和节点能量发送给基站,基站收集到区域内各个节点的位置信息后，根据这些信息将传感器网络按面积平均划分为k个区域（本文设定k=3），即需要将整个区域划分为如图1所示的三部分。
区域划分完成以后，每个节点随机地产生一个0~1之间的随机数，如果小于阈值T(n)，则该节点当选为候补簇首(T(n)的计算与LEACH中相同)；然后把选出的候补簇首按能量的大小递减排列成一个队列，从队列中第一个节点开始，取消以节点为圆心、半径为M的圆内的其他候补簇首成为簇首的资格，并将其从列队中删除。
最优簇头数(kopt)个节点完全无缝覆盖检测区域需要满足的条件[5]是：
依次遍历其他节点，重复上述操作。最后剩下的候补簇首即成为最终的簇首。
当选为簇首的节点会将自己的ID添加到该簇域的全局变量ch_list_中去，最终得到的ch_list_就是该簇域内所有簇首节点ID的列表。通过簇域的ch_list_即可以得到下游（下游指的是指向BS方向的下一个簇域）簇域内的所有节点的ID列表。有了该列表，就相当于得到了下一跳的候选列表。如图2所示，簇首只需从这些候选节点中随机选出一个节点作为自己的下一跳节点，这样就将各个簇首的多跳路径建立起来了。
3 算法的仿真及分析
3.1 仿真环境
本文采用NS2[6]对LEACH及改进后的LEACH算法进行仿真。仿真环境设定如下：
(1)传感器节点和虚拟聚类区域具有全局唯一的ID标识；
(2)网络内所有传感器节点均相同，具有相同的初始能量2J，且信号均可到达基站。
(3)各个传感器节点具备GPS功能，即节点能定位其位置。
3.2 仿真结果与分析
(1)在仿真过程中，节点的能量会随着时间的推移逐渐减少，直至能量耗尽而死，所以在各个时段传感区域内仍未耗尽能量的节点个数是不同的。图3是LEACH和改进后的LEACH两种算法在不同时段仍然存活的节点个数比较。
从图3中可以得出以下结论：
①LEACH算法在365 s时出现节点死亡，而改进后的算法在375 s时开始有节点出现死亡。从节点开始死亡的时间上说明，改进后的算法相对于LEACH算法提高了2.73%。
②LEACH算法在500 s左右时结束了网络生命，而改进后的算法在580 s左右时才结束网络生命。从网络存活时间比较说明，改进后的算法比LEACH算法存活时间延长了16%。
(2)不同时段网络内存活节点数目的比较很直观地说明了两种算法下网络生命周期的不同。下面从能量消耗的角度来进一步对两种算法进行比较。
图4为两种算法下在不同时段网络消耗总能量的值，由图4可以看出，LEACH算法在500 s结束网络生命时的总能耗为450 J左右，而改进后的算法在580 s时结束生命周期时总能耗是350 J。对比结果进一步印证了本文算法较LEACH算法延长了网络生命周期。
（3）两种协议的性能比较如表1所示。
从表1可以看出，改进-LEACH协议和LEACH协议相比，如果以节点开始死亡的时间为标准，改进-LEACH协议相比LEACH协议可有2.73%的提高；若以网络生命周期为标准，则有16%的提高；如果以网络总能耗为标准，相比LEACH协议，改进-LEACH协议其性能提高了21%。
本文针对无线传感器网络，在理论分析的基础上提出了一种改进的LEACH协议。该协议在选择簇首方面，充分考虑了网络中节点的位置和剩余能量，进而使簇的大小更为合理；在簇首与基站之间的路径选择方面，采取了多跳传输的方式。通过NS2的仿真实验表明，将改进后的算法应用于传感器网络中，能更有效地降低与均衡网络的能量消耗，从而较大幅度地延长了传感器网络的生命周期。
参考文献
[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005：124-151.
[2] 余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的 改进算法[J].电子学报，2008，36(7)：1309-1313.
[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(12)：11.
[5] 王盛.基于NS2的无线传感器网络LEACH协议的改进仿真研究[D].武汉：武汉理工大学，2010.
[6] 徐雷鸣.NS与网络模拟[M].北京：人民邮电出版，2003.