邬厚民

（广州科技贸易职业学院，广东 广州 511442）

0 引 言

能耗问题一直是制约无线传感器网络发展的关键问题。由于传感器节点是依靠电池供电的节点设备，并且考虑其自身尺寸限制及所部署的恶劣环境，人工很难通过“二次供电”的方式为其补充能量，导致传感器节点因能量耗尽得不到补充，造成网络中存在漏测区域，甚至整个传感器网络的瘫痪；因此，在无线传感器网络正常工作过程中，如何有效减少网络中节点能量消耗，均衡网络中传感器节点的能量来延长网络生命周期成为当前无线传感器网络中研究的重点。

大量实验研究表明，通过选定合理的簇头节点、簇头数目及减少簇内的簇头节点处理簇内数据的计算量，可以有效地减少整个传感器网络的能量消耗，延长网络生命周期。本文采用低功耗自适应集簇分层型协议（low energy adaptive clustering hierachy，LEACH）作为自适应分簇拓扑算法对传感器网络进行分簇，在簇的建立阶段着重考虑能量因素，从簇头的选择和簇内通信两方面对LEACH算法进行了改进。该改进算法能够克服传感器网络中整体能量消耗过大及因节点伴随时间推移而能量耗尽所带来的漏测区域的弊端。

1 LEACH算法

LEACH算法是Heinzelman等提出的自适应分簇经典算法。该算法中引入了“轮”的概念，每一轮分为初始化和稳定通信两个阶段。其中，初始化阶段又分为簇头选举和簇的建立。簇头选举过程中，节点产生0~1之间的随机数，若该随机数小于规定的阈值T（n）则自行选举为簇头并进行广播。

式中：p——簇头数量所占的百分比；

r——选举轮数；

G——这一轮循环中未当选过簇头的节点集合。

在簇的建立阶段，接收到簇头广播消息的非簇头节点根据“就近原则”加入簇。在稳定通信阶段，簇头节点将接收到的簇内成员节点的数据进行融合并发送给基站。

LEACH算法初步解决了传感器节点负载平衡的问题，并且比较容易实现，但是还有很多值得改进的地方。如簇头选举阶段，节点随机决定是否成为簇头，导致簇头位置和簇内包含的节点个数很不均匀，并且也没有考虑到节点的剩余能量；在成簇阶段，非簇头节点采用就近原则，加入离自己最近的簇头，也没有考虑到簇头的剩余能量；选取节点没有考虑对区域的覆盖情况等。本文在考虑对区域保证最大覆盖的前提下，结合对能量和距离的综合考虑，对初始化阶段簇头选举和成簇两个子阶段进行改进，用选出的簇头保证对区域的最大覆盖。

2 最优覆盖下基站“数据表”的构建

2.1 传感器网络最大覆盖理想模型

[1]证明，在图1所示相邻的节点拓扑覆盖中，Wang提出定理：节点0所覆盖的区域是一个正六边形时，可以取得无缝最大有效覆盖面积，即

式中：r——圆半径。

图1 最大无缝覆盖示意图

2.2 基站“数据表”的建立

假设传感器的感知半径为R，被监测矩形区域的长为L，宽为W，节点的行数为Ln，每行节点的数目为Hn，所有节点的数目为N*。

通过式（3）可以计算节点所在的行数[2]

计算每行节点的数量Hn的过程非常复杂，底边具有不同的长度，因此每行中包含的节点个数不相等。为了进一步判断分析，作辅助线，假设从左边开始计算，对应每一列节点的左切线，如图2所示。从底向上开始计算，在奇数行中做各个圆的下切线，在偶数行中做各个圆的上切线。奇数行与偶数行之间均为阴影部分。

图2 无线传感器网络理想最优部署模型

N*的数值可以通过Ln的奇偶性来计算：

（2）若Ln为偶数，N*计算公式为

由以上易知此模型下保证最优覆盖所需N*个点，并且可得每个点位置的坐标。

记录这N*个点的坐标（i，xi，yi），i=1，…，N*。形成一个“数据表”，存储在基站中，以备后续改进CDE-LEACH算法的簇头选择过程中应用，用簇头来保证整个部署区域的全覆盖[3]。

3 改进的CDE-LEACH算法

3.1 网络模型

在大小为M×M的矩形监测区域内，随机部署N个传感器节点组成网络。对网络模型作如下假设：

（1）网络中节点是静止的或缓慢移动；

（2）网络中的节点同构且节点初始能量相同，并且有唯一的ID号，节点的坐标由定位算法可得，并且已知；

（3）基站位置固定，假设其能量是无限的（不靠电池供电）；

（4）基站中存有保证网络最优覆盖条件下存有N*个点位置坐标信息的“数据表”；

（5）节点的发射功率动态可调，节点间的通信链路可靠且双向连通。

3.2 无线耗能模型

传感器节点的能量主要消耗在无线传输的过程中，而且随着通信距离的增加，节点能耗呈指数增长。发送和接收l bit数据且传输距离为d，节点消耗的能量分别为

式中：Eel——电路发送或接收功耗；

d0——门限距离；

rd2——传输距离小于d0时，采用自由空间信道环境下的功率放大器功耗；

ηd4——传输距离大于等于d0时，对应多路径衰落信道环境下的功率放大器功耗。

在每一轮簇的重建中消耗的总能量为[4]

式中：dtobs——节点到汇聚节点的平均距离；

Ec——簇头中数据融合时的功耗；

k——簇头节点的个数；

Ei——传感器节点的最初能量；

Ei（r）——对应第r轮选举簇头时的剩余能量；

3.3 选择簇头

由LEACH协议可知，簇头节点的个数影响网络的寿命。若选择的簇头节点个数过少，则导致簇的覆盖区域过大，簇内节点到簇头的通信距离比较远，相应传输数据时需要的能量也多；由于簇头节点需要的能量远大于非簇头节点，若选择的簇头节点个数过多，每一轮工作过程中整个网络中所有节点总的能耗会增大，进而导致数据融合[5]效率降低。

网络在每一轮的簇重建中消耗能量最小[5-7]，是选举最优簇头节点个数的准则，并且保证对所监测区域的网络覆盖。首先考虑在式（8）中Etotal达到极小值时的k值点。给定网络参数的前提下，当k＞0时Etotal对应以k为变量的连续函数。

即k0为极值点。

经过计算得到k0为最小值。k0由汇聚节点计算，并且每隔预先设定的若干个周期重新计算一次，因为网络中存在因能量耗尽而死亡的节点。

此时计算的k0值满足簇重建过程中所需能量最小，但是并不能保证区域网络的覆盖，为此在此区域下结合利用式（4）或（5），从k0个节点中在前述条件下计算出保证网络最优覆盖的节点个数N*，从而挑选出满足所需条件最优的k0个节点。考虑2种情况：

（1）当 k0≥N*时

（2）k0＜N*时

在簇头选举时综合考虑覆盖、能量和距离两个因素，首先在能量和距离因素下，为每个节点分配表示其适合充当簇头的概率权值。定义某个节点i在第r轮簇头选举中的竞选概率权值为

Ei（r）——对应节点i第r轮剩余能量；

E（r）——节点的最初能量；

μ——区间[1/2，1]内递增；

dmax——节点到汇聚节点的最远距离；——节点i到汇聚节点的距离；

前述可知，在CDE-LEACH算法中，对簇头的选举需要知道当前网络中的平均剩余能量，方法：每轮过后，簇内节点在最后要发送的数据分组中装载有自身的剩余能量信息，传输给簇头；簇头对这些信息进行收集融合，将融合后的数据信息发送给基站；在基站中完成对整个网络中的平均剩余能量的计算，并将结果装载到下一轮的重新选簇命令中，广播给网络内所有的传感器节点。由此，完成了对网络平均剩余能量的计算。

初始化阶段，基站首先广播簇头开始竞选消息，这个消息中包含当前网络平均剩余能量信息。当节点收到这个消息后，首先将自身剩余能量与当前网络的平均剩余能量进行对比，若自身剩余能量比当前网络的平均剩余能量小，则直接放弃竞选，并随后加入某一簇；若自身剩余能量比当前网络的平均剩余能量大，则向基站发送消息，消息中包括节点的ID和剩余能量等信息，即竞选簇头消息。基站收到所有参加竞选节点发送的竞选簇头消息后，根据式（11）确定的竞选权值按前述方法选择出的k0′个节点作为簇头，并全网广播该k0′个节点作为簇头的消息，消息中包括选出的k0′个簇头节点的ID。网络中节点接收到此消息后如果发现任命的簇头中有自身，就当选为簇头。

3.4 选择簇内成员

在非簇内节点成员选择加入簇头时，同样考虑距离和能量两个因素，通过选举出的簇头节点来保证整个区域的最优覆盖，前面簇头选择过程中选择出的簇头已经保证了簇头对整个区域网络的覆盖；因此，这里选择簇内成员时不再考虑最优覆盖的问题。

可以假设非簇头节点接收到来自m个簇头节点的广播消息，广播消息中包含簇头ID和自身剩余能量。此处定义非簇头节点选择加入簇头时的概率权值为

式中：μ——加权系数，可根据实际情况改变；

Ei（r）——节点i第r轮剩余能量；

E（r）——节点的初始能量；

dmax——节点到基站的最远距离；

di——非簇头节点到第i个簇头间的距离。

由式（12）知非簇头节点选择加入簇头时，首先会选择当前簇头节点剩余能量多且距离近的簇头加入，因为距离近，传输数据信息时消耗的能量就少，也就相对节省了能量，这样，非簇头节点选择加入簇头时的概率权值最大。然后非簇头节点向该簇头节点发送加入请求消息，请求消息中包括本节点的ID和所加入簇头的节点ID。簇头节点收到各成员节点的请求信息后，采用TDMA策略为簇内成员分配通道，完成簇阶段的建立过程并开始进入稳定阶段，各簇内成员节点在自己分配的通道内向簇头发送数据，簇头节点融合各成员节点的数据后发送到基站。

4 仿真实验

在100m×100m的监测区域内，随机部署100个传感器节点，如图3所示。节点半径为15，初始能量为 0.5J，汇集节点位于（150，50）处，最大运行轮数为5000。控制不同情况下的传输数据观察节点的死亡情况即网络的运行生命周期[8]。

图3 节点分布图

在上述条件下运行LEACH协议和本文提出的CDE-LEACH算法，采用Matlab 7.0仿真平台对改进前后的LEACH算法对能量的消耗情况进行对比，对比结果如图4所示。

图4 改进算法与原算法性能对比

图4中LEACH1、LEACH2分别代表未采用最优覆盖的LEACH算法与采用最优覆盖的LEACH算法，CDE-LEACH1、CDE-LEACH2分别代表未采用最优覆盖与采用最优覆盖的CDE-LEACH算法。

由图4可知，改进后的LEACH算法协议CDELEACH算法在相同运行周期时死亡节点数相对于LEACH算法明显减少，这说明改进后的算法有效地延长了网络的生命周期。

5 结束语

本文在已有的成熟并广泛应用的LEACH算法协议前提下，提出CDE-LEACH算法，它是一种能保证在网络有效最大覆盖前提下，最大限度地采集网络中的有效数据并降低网络的能量消耗算法。通过Matlab 7.0实验平台验证，改进后的LEACH算法能够有效地减少网络中的传感器节点能量消耗，延长网络的生命周期。

参考文献

[1]Warneke B，LastM，Liebowitz B.Smart dust:communicating with acubic-millimeter computer[J].IEEE Computer Magazine，2001，34（1）：44-51.

[2]吕广辉，崔逊学，侯战胜.一种基于遗传算法的无线传感器网络覆盖模型[J].微型机与应用，2010，29（15）：59-62.

[3]Huang C H，Tseng Y C.The coverage problem in three-dimensional wireless sensor network[J].Journal of Interconnection Networks，2007，8（3）：209-227.

[4]苏莹.无线传感器网络能量有效的分簇优化算法研究[D].武汉：华中师范大学，2008.

[5]陈浩，刘广钟.基于能量和距离的无线传感器网络分簇算法[J].微型机与应用，2009，28（11）：31-33.

[6]胡刚，谢冬梅，吴元忠.无线传感器网络路由协议LEACH的研究与改进[J].传感技术学报，2007，20（6）：1391-1396.

[7]陈洁，赵全明.基于冗余节点的LEACH协议的改进[J].电子设计工程，2011，19（22）：42-44.

[8]毕艳忠，孙利民.传感器网络中的数据融合[J].计算机科学，2004，31（7）：101-103.