基于能量和距离的分区域选择簇首WSNs 路由算法*

刘永超，张月霞，缪 旻

(1.北京信息科技大学 信息与通信工程学院，北京100101;2.北京信息科技大学 北京高动态导航技术重点实验室，北京100101)

0 引 言

无线传感器网络(WSNs)是由很多传感器节点组成，这些节点包含传感器单元、处理器和无线收发器，可以形成一个自组织网络系统。目前WSNs 已应用于很多领域，比如:环境监测、医疗应用、军事等。通常WSNs 中传感器的数量非常大，又由于恶劣环境条件的限制，这些传感器节点都是由电池供电的［1］。因此，WSNs 的设计主要考虑到能量有效和延长网络的生命周期，这也是WSNs 不同于传统的无线网络的主要部分。

根据网络中各个节点的地位和功能的不同，路由算法可以分成平面路由算法和分层次路由算法。分层路由算法是通过将网络分成不同的簇，在簇内有一个簇首负责融合簇内节点的信息，然后将融合信息发送给基站(BS)。相比平面路由算法，它能够更好地节省网络的能量和延长网络的生命周期。LEACH(low-energy adaptive clustering hierarchy)是最早提出的经典的分层路由算法，它采用动态分簇，让节点循环去充当簇头，负责收集簇内其他节点的信息，进行数据融合，然后再将信息发送到基站，从而均衡网络节点的能量消耗［2］。与一般的平面路由算法相比之，LEACH 算法可以将网络生存寿命延长15%左右。但是，LEACH 路由算法本身存在不足之处，如簇首分布不均匀，簇首节点选择的盲目性，远距离传输过多消耗能量等［3］。

针对LEACH 算法存在的不足，本文提出一种基于能量和距离的分区域选择簇首路由算法。根据网络所有节点所处的位置和到基站的距离，将节点进行分区域，然后再在各个区域内进行簇首节点选择;将节点的剩余能量和节点的密集程度引入到簇首节点选择;同时，采用多跳传输模型。实验结果表明:该算法能够平衡网络负载和延长网络生命周期。

1 LEACH 算法原理

LEACH 算法是2000 年麻省理工学院电子工程和计算机科学系的Heinzelman W 等人为WSNs 设计的第一个分层次拓扑路由算法［4］。LEACH 算法引入“轮”的概念，执行过程是周期性的，每轮分为簇的建立阶段和稳定的数据传输阶段，为了减少分簇带来的额外能耗，簇的稳定阶段要远远长于簇的建立阶段。从图1 可以清楚地看出LEACH 算法的运作过程。

图1 LEACH 算法的运作过程Fig 1 Operation process of LEACH algorithm

1.1 建立阶段

在选举簇首时，各个节点产生一个0～1 之间的随机数，将它与它所对应的阈值T(i)进行比较，如果这个随机数小于其阈值，则这个节点将被选为簇首。其中，T(i)可表示为

其中，p 为簇首在所有节点中所占的比例，r 为当前运行的轮数，mod 为求模运算，G 为这一周期中未当选为簇首的节点集合。

一轮簇首选举结束后，某些节点会当选为簇首。簇首节点就向外发送广播信息，其他节点接收到广播消息后，依据接收到广播消息的信号强度确定要加入的簇，同时向该簇发送加入请求。簇首收到请求后将节点加入自己的路由表，并为每个节点设定一个TDMA 时间表，再将该时间表发送给所有簇内节点。普通节点接收到信息后，整个簇的建立完成。

1.2 稳定的传输阶段

在每轮的稳定传输阶段，普通的传感器节点按照TDMA 表在属于自己的时隙内将采集的数据发送给簇首节点。簇首节点再将收集到的数据进行数据融合，然后将融合后的信息发送给基站。簇首工作任务比较繁重，需要收集普通节点的信息，然后完成数据融合，最后与基站通信，能量消耗较大。因此，每一轮结束后要按照上述方法重新选择簇首和簇的划分，以使网络内节点的负载保持均衡。

1.3 LEACH 算法的不足

LEACH 路由算法本身存在簇首的选举是随机选择的，经常会导致簇首分布不均匀，会增加整个网路的能量消耗;在簇首节点选择时没有考虑节点当前的能量情况，如果能量很低的节点当选为簇头节点，则将会加速该节点的死亡，影响整个网络的生命周期;簇首节点到基站的通信采用单跳通信，WSNs 中很多节点距离基站较远，根据多径衰减模型，簇首节点发送数据到基站所消耗的通信能量会随着距离的增大而急剧增长，从而增加整个网络的能量消耗。

2 A-LEACH 算法

综合以上LEACH 算法的不足，本文提出了以下的改进方案:首先根据节点到基站的距离将簇首节点分为由近到远的三个区域［5］，然后在三个区域进行簇首选择。簇首选择时综合考虑到节点的剩余能量［6］和周围的邻居节点［7］，选择剩余能量高且周围邻居节点较多的节点为簇首。在簇首节点收集完信息后进行由远区域到近区域的逐次多跳传输，从而减少过远传输带来的巨大能量的消耗。图2 为ALEACH 路由算法的网络结构图。

图2 A-LEACH 算法的网络结构图Fig 2 Network structure of A-LEACH algorithm

2.1 分区域阶段

节点随机地分布在固定的检测区域，节点一旦部署，其位置不可变动。

1)首先确定所有存活节点到基站距离。基站可以将消息传递给最远的节点，将自己的位置等信息传递给所有节点，从而计算出节点到簇首节点的距离，然后再将信息传递给簇首节点。

2)所有节点确定到基站的距离，并将距离保存下来。通过所有节点到簇首之间的距离，将所有节点分为A，B，C三个区域［8］。将所有节点到基站的距离由近到远进行排序，距离最近的前20%的节点划分为A 区域，排序中到基站的距离在20%～60%的节点为B 区域，而60%以上节点划分为C 区域，A，B，C 区域的节点个数由Num-A，Num-B，Num-C 表示。

3)在分区之后，在各个区域中，计算出每个节点的密集程度，也就是节点附近节点的个数，取节点周围D 距离范围内的节点个数Nneigh(i)，D 为网络区域范围长度x 的20%。

2.2 簇的建立阶段

1)首先是簇首选择:在分区域阶段，已经获知了节点的密集程度，通过节点的剩余能量和节点的密集程度来计算各个节点当选簇首的概率值，该概率值为

其中，c1，c2为比例系数，E(i)为当前节点的能量值，Eave为所有节点能量的平均值，Nneigh(i)为当期节点的密集程度，nalive为当前网络的存活节点个数。通过概率值来选择簇首，让优秀的节点成为簇首节点［9］。

2)在得到了所有节点的概率值之后，然后分别在A，B，C 区域选择簇首节点。在前人研究的基础上，得知将簇首个数控制在整个网络节点的5%时，可使网络的能量消耗最低［2，10］。所以在选择簇首时，A，B 和C 区域选出Num-A×5%，Num-B×5%，Num-C×5%个簇首节点。同时在选择簇首时，为避免两个簇首节点离得太近而增加簇首的能耗，要求两个簇首节点的距离不能小于网络区域范围长度x的20%。

3)在选择出簇首节点以后，簇首向自己所在的区域进行广播，普通节点接收到此区域的簇首广播信息以后选择合适的簇首加入，向簇首发送加入信息，同时簇首接收普通节点发过来的加入信息。

4)在分簇完成以后，簇首为其簇内的普通节点制定TDMA 时间表，普通节点在自己所在时隙里将数据传递给簇首。簇的建立阶段完成。

2.3 信息传输阶段

在信息传输过程中，节点传输k bit 数据到距离为d 时所消耗的能量为

其中，ETx－elec为节点信号发送数据消耗的能量，ETx－amp为发送电路所消耗的能量，εfs和εamp为放大器的系数，d0为临界距离接收端接收k bit 数据消耗的能量为

通过以上公式可知，节点传输距离大于临界距离d0时，所消耗的能量会急剧增加。所以，本文提出采用多跳的传递模式。每个簇接收簇内普通节点的信息后，将信息融合，然后C 区域的簇首将信息传递给B 区域距离近的簇首节点，然后B 区域的簇首节点再将信息传递给A 区域的簇首节点，最后再传递给基站。

3 仿真与结果分析

为了分析改进算法有效性，本文对改进算法A-LEACH和LEACH 进行了仿真和分析。WSNs 面积分别为100 m×100 m 基站位置分别为(125，50)m 场景。假定信息感知、空闲和休眠三种功耗均为0，仿真环境的各个参数如表1 所示。

表1 仿真参数Tab 1 Simulation parameters

本文中从网络的生存时间、存活节点数和网络总体剩余能量方面评估改进后的性能。A-LEACH 路由算法首先是对网络进行分区域。图3 为节点的划分区域分布图，根据节点到基站距离的远近将其分为三个部分。

图3 节点的分布图Fig 3 Distribution of nodes

图4 表示仿真中每一轮的簇首个数。通过图4 可知，LEACH 路由算法中的每一轮的簇首节点个数的变化范围很大。簇首个数过多或者过小都会增加网络能量的开销。而A-LEACH 路由算法严格地将簇首节点的个数控制在存活节点个数的5%。同时A-LEACH 采用的是分区选择簇首，簇首节点的分布比较均匀。

图5 为LEACH 和A-LEACH 算法的存活节点个数与轮数的关系。从图中可知，LEACH 出现第一个死亡节点在763 轮，而A-LEACH 算法第一个死亡节点出现在1023 轮。从整体网络的生命周期看，A-LEACH 算法将网络的生命周期延长了近20%。同时通过节点死亡的趋势可以看出，LEACH 算法中，网络节点的能量分布不均匀，能量相差的比例较大，所以，出现了有些节点过早死亡而有些节点存活很长时间的情况。而在A-LEACH 路由算法中，网络中的节点几乎在同一时间能量耗尽，表明此算法能够很好地均衡网络的能量分布。

图4 每一轮的簇首个数Fig 4 Number of cluster heads in each round

图5 存活节点数的比较Fig 5 Comparison of number of nodes alive

图6 为整个网络的剩余能量总和，通过仿真结果可以看出:A-LEACH 算法每轮消耗的能量要比LEACH 少，节省整个网络的能量，这也是延长网络生命周期的一个原因。

图6 整个网络的剩余能量Fig 6 Residual energy of entire network

4 结 论

WSNs 是物联网工程的重要组成部分，而路由算法是WSNs 的核心技术之一。本文通过对WSNs 的经典路由算法LEACH 进行分析研究，提出了一种分区域分簇的路由改进算法A-LEACH。改进算法首先根据节点到基站的距离对节点进行区域划分，然后在特定区域用新的阈值来选择优秀的节点作为簇首，最后采用多跳的方式进行信息传输。通过仿真证明:A-LEACH 改进算法能够更有效延长网络的生命周期，均衡网络能量的分布和减少网络的能耗。

［1］ 李桂香.基于传感器网络能量均衡分簇算法仿真研究［J］.计算机仿真，2012，29(4):161－164.

［2］ 李芳芳，王 靖.一种基于LEACH 协议的无线传感器网络路由算法［J］.传感技术学报，2012，25(10):1445－1451.

［3］ 陈晓娟，王 卓，吴 洁.一种基于LEACH 的改进WSNs 路由算法［J］.传感技术学报，2013，26(1):116－121.

［4］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless sensor networks［C］∥Proceedings of 33th IEEE Annual Hawaii International Conference on System Sciences，2000:10.

［5］ Gautam Navin，Pyun Jae-Young.Distance aware intelligent clustering protocol for wireless sensor networks［J］.Journal of Communications and Networks，2010，12(2):122－129.

［6］ 王 进，邵玉斌，龙 华，等.基于能量和距离加权的WSNs 簇头选择算法［J］.传感器与微系统，2014，33(5):132－134.

［7］ 路成杰，蒋海峰.一种基于节点密度的无线传感器网络路由协议［J］.传感器与微系统，2014，33(9):114－116.

［8］ Liu Y，Xiong N，Zhao Y，et al.Multi-layer clustering routing algorithm for wireless vehicular sensor networks［J］.IET Trans on Communications，2010，4(7):810－816.

［9］ 吕 涛，朱清新，张路桥.一种基于LEACH 协议的改进算法［J］.电子学报，2011，39(6):1405－1409.

［10］Heinzelman W B，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communication，2002，1(4):600－670.