基于低能耗的无线传感器网络路由协议的研究

童孟军，邱伟伟

(杭州电子科技大学计算机学院，浙江杭州310018)

0 引言

无线传感器网络节点的数量较大，在网络自组、路由查询和信息传输过程中，都会占用大量的通信资源和处理资源所带来的能量消耗［1］。因此，对于规模较大的无线传感器网络来说，分簇技术是分层路由协议中一种高效节能的拓扑控制方法。如何产生选举簇头节点是分簇路由算法最先要考虑问题［2］。本文提出的一种节能的负载均衡的分簇路由协议(Energy Efficient and Load-balanced Clustering Algorithm，EELCA)，该路由协议是一种复合型分簇路由协议。在该协议中，依据簇头个数，将区域划分为数个子区域，每个子区域综合节点的剩余能量和随机因素选举簇头，并且保证簇头节点之间的有一定的间距，这样避免簇头分布过密和位置过偏，确保了网络负载的均衡性。数据传输阶段实现多跳式传输，外层区域的簇头节点向内层区域簇头发送数据，直到最内层区域簇头直接发送给基站，减少了离基站较远的簇头能量的消耗［3］。

1 模型介绍

(1)网络模型:1)有节点完全相同并且都具有有限的初始能量;2)络中所有传感器节点都静止;3)线传感器网络中每个节点有6个属性字段ID(节点标识)，Cid(聚类标识)，C(是否簇头)，E_mode(节点剩余能量)，Px，y(节点位置信息)，AreaID(子域标识)。其中，节点自身的坐标值由自带的GPS获得。

(2)能量模型:1)网络中所有节点完全相同;2)无线电信号在各个方向上能量消耗相同;3)信道是对称的，从节点A发到节点B的能量消耗与从节点B发到节点A的能量消耗相同［4］。

传感器节点发送k bit数据消耗的能量分为两部分，一部分是信号发射电路所消耗的能量，一部分是信号放大电路所消耗的能量，为:

传感器节点接收k bit字节所消耗的能量为:

式中，Eelec是发送电路和接收电路消耗的能量;d是信号传输的距离［5］。

2 EELCA分簇算法思想

2.1 分簇算法准备

基于网络能耗最小的考虑，通过数学推导和仿真实验，一般选取簇头比例为5%，即簇头产生概率P=0.05。对于一个节点数为100的区域，最多有簇头数为5个。当簇头分布较合理时，簇的范围应尽量均匀覆盖整个区域。因此簇头间的距离必须适中，太近或太远都不合适，且在一定间距内不能出现其他簇头。设传感器区域面积为S，节点数为N，簇头产生比例为P，要覆盖整个节点区域，则簇的平均半径R满足:

簇头间距接近2R时，簇头分布较合理。对于一个边长为100m的正方形区域，节点个数100，簇头比例P为0.05，则R≥25.2m。这里采用LEACH协议运行模式，如图1所示:

图1 LEACH运行过程

假设第i个簇中成员节点个数为Ni，一轮的数据传输时间为Tdata，每个成员节点分配的时槽长度是Tslot，则在一轮内，簇i中一个成员节点消耗的能量为:

式中，Ni越大，Ei越小，即簇内节点数越多，节点消耗的能量越小;反之，簇内节点数目越少，节点消耗的能量越多。

2.2 簇的形成阶段

簇的形成在整个协议中占着举足轻重的作用，其分布的好坏决定了整个网络的寿命。EELCA算法采取:(1)根据最优簇头概率设置簇头个数为N×p，其中N为区域中传感器节点总数;(2)离基站较远的簇，成员节点可以适当多一些，这样簇内能量消耗少;(3)在簇头的选举中，引入簇间距，使得每个簇头的形成必须考虑和其他簇头的距离。

(1)区域的划分。假设有个100×100m的区域(L=100)，随机分布了N=100个节点。基站位置(50，50)。那么最优簇头个数为k=100×5%=5，根据前文所说，簇头覆盖半径取R=26m，区域边长为100，即簇头可能最大间距为100，这里规定的簇头间距为2R=52m，要想簇头覆盖到所有节点，每个子域的直径需为2R，因此可以推断出所要划分的子域个数为［L/2R］=［100/52］=2，通过计算得出两个子域面积之比SI:SII=1:6，现在有5个节点，子域I(内层)分布一个节点，子域II(外层)分布其余4个节点。节点在每个子域的分布个数根据实际情况而定，随着区域面积的增大，最内层子域的个数增多。

(2)簇首选举。为了使簇头在子域内分布均匀，选举时确保各个簇头的间距在2R=52左右，这里定义下一个簇头只要在已经选出的簇头所在的［2R，2R(1+α)］邻域内就可以了。α是参数，在在0～1之间。考虑到能量的消耗，则在已选为簇头的邻域内，节点剩余能量最高的当选簇头。以此类推，直到子域内的簇头全部选举完毕。

(3)簇的形成。对任意的节点i，会收到多个簇头发来的消息，首先比较信号强度最高的两个簇头I和J，假设I的强度大于J，即SignalI＞SignalJ。NI，NJ为簇I和簇J内成员节点的个数。dtoBS(I)，dtoBS(J)为簇到基站的距离。依据均衡原则来选择加入的簇。

均衡原则是:节点i不但可以加入所属区域的簇，还可以加入和自己不在同一个区域的簇，条件最优者优先，具体为:若SignalI/SignalJ≥ε，则节点i选择加入簇I;否则，若|NI－NJ|≥λ，则节点i选择加入NI，NJ中较小的簇;否则，若dtoBS(I)－dtoBS(J)≥0，则节点i选择加入簇I，否则加入簇J，即选择离基站远的簇头加入。其中ε，λ为参数，根据情况自己设定。

所有子域内的簇头全部选择好后，簇头发送广播通知域内其他节点自己成为簇头的消息，其余节点根据均衡原则决定加入的簇，并向簇首发送申请消息。当某个子域的簇形成后，若其他子域还未完成簇的形成，那么已经完成的子域中所有节点将进入休眠状态，等待其他子域簇的形成。根据区域划分的特点，可以推断出，最内层的子域最先完成簇的形成，最外面的子域则最后完成。当最后一个完成后，将其他子域内的节点唤醒，进入簇的稳定阶段。经过一定时间后，进入下一轮簇首选择。

2.3 簇的稳定阶段

每个传感器节点都在探测周围信息，有信息接收时，开始判断:1)如果接收信息的是基站，则接收完成;2)如果接收信息的是簇头，那么该节点将信息传给比自己AreaID小1的且信号最强的簇头。不断循环该步骤，直到信息传递到AreaID=1的簇头，然后直接传给基站;3)如果普通节点接收到信息，那么将信息传递给所在簇的簇头，转入步骤2。

3 仿真结果分析与比较

本文中采用的仿真工具为Matlab 6.5，在100×100m的区域(L=100)，随机分布了N=100个传感器节点，基站坐标为(50，50)。

实验参数设置:节点初始能量为0.001J(为了缩短程序运行时间，减少轮转次数少)，每个数据包含50bit，Eelec=50nJ/bit。簇头产生概率为0.05。在均衡原则中，两个簇头的信号强度比ε=1.5，两个簇头中的成员数之差λ=5。

在传感器网络中，分簇算法的好坏主要根据网络生存时间、能耗、覆盖率等来衡量。其中网络生存时间和能耗是两个比较重要的参数。

该文将分簇协议中最为经典的LEACH协议拿来和EELCA算法最仿真比较。仿真结果如下:1)首先在簇的分布上，当程序运行到第200轮时，EELCA算法簇的分布比LEACH协议的更为合理，而且簇中的成员数也较为均匀;2)其次是网络生存时间，程序运行的轮数越大，EELCA比LEACH节点存活数越多;3)最后是能量消耗，程序运行到最后，EELCA节点的平均剩余能量明显高于LEACH协议。

4 结束语

综上所述，从簇的分布，网络生存时间以及能量消耗这几个方面来看，EELCA算法明显优于LEACH协议，说明此算法设计的较为合理，在一定程度上减少了能量的消耗，做到了能量均衡的效果。该文在说明EELCA算法时，对区域的划分和每个子域簇头个数的分配，针对较具体的网络环境给出具体方法，没有明确给出一个普遍适用的计算方法，只是提出了思想。在今后的工作中可进一步总结并给出在其他应用场景下的计算方法。

［1］ Cullar D，Estrin D，Strvastava M.Overview of sensor network［J］.Computer，2004，37(8):41 －49.

［2］ 孙利民，李建中，陈渝.无线传感器网络［M］.北京:清华大学出版社，2005:13－15.

［3］ Raghunatha，Schurgers V，Sung Park C.Energy － aware wireless microsensor networks［J］.IEEE，Signal Processing Magazine，2002，19(2):40 －50.

［4］ Heinzelman W.Application－Specific protocol architectures for wireless networks［D］.Boston:Massachusetts Institute of Technology，2000.

［5］ Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for self－ organization of a wireless sensor network［J］.IEEE Personal Communications，2000，7(5):16 －27.