无线传感器网络Leach算法在某突发情况下的改进①

林 蔚， 陈勖之

(哈尔滨工程大学理学院，黑龙江 哈尔滨 150001)

0 引言

近年来，无线传感器网络技术得到迅猛地发展，并且受到了普遍重视，作为一种新型网络技术，它的产生和发展对现代网络技术造成了极其深远的影响[1].本文中，无线传感器网络的研究主要是针对以下几个特性进行的:能源有效性;生命周期;容错性[2].由于在无线传感器网络中传感器节点是能源有限的，所以让有限的能源得到高效的利用，延长的网络生存时间有积极意义[3].无线传感器网络的容错机制，能达到延长网络生命这一目的.改善其容错能力，对无线传感器网络发展和应用都具有十分重要的意义[2].

Leach算法是无线传感器网络的一种传统经典的分簇算法，有极强的代表性.Leach在循环的分簇机制下，不断地执行簇的重构过程.但是，Leach算法在一些突发情况发生时，缺乏有效的容错能力，因此本文针对Leach算法在出现部分节点突然死亡的情况，使用一种静态容错模型[4]，本文提出了一种改进的Leach算法(τ－Leach算法).通过平衡突发事件发生前后节点的能量，根据死亡节点数，给出一个系数τ，改变准入节点成为簇头的阈值，来实现延长突发情况下网络存在时间.

1 Leach算法及存在问题

1.1 Leach算法

Heinzelman等人在[5]中提出了 Leach算法.Leach定义了“轮”的概念，工作“轮”由初始化和稳定工作阶段组成.算法中阈值T(n)的计算公式十分重要，按等式(1)计算:

在上式(1)中，p=k/N，n为网络中传感器节点数，p为一轮中需要的簇头节点的百分数，k为一轮中网络中的簇数，r为当前的轮数，G为之后1/p轮中没有成为簇头的传感器节点组成的集合.各个节点依照阈值T(n)进行分簇.簇构建完成，数据通信便开始，网络进入稳定阶段.节点采集监测数据，并将采集数据发送给簇头.当一轮的数据传输完毕后，簇头节点会对数据进行处理，然后发送到sink节点，一段时间后，进入下一工作轮.

1.2 存在问题

因为无线传感器网络应用广泛，特别是在军事国防、环境监测、交通管理等方面有重要作用.在实际应用中会出现如下情况:当网络工作到某一轮rx时，在网络分布区域内，因为某些原因导致部分区域内的节点死亡.死亡节点带有的能量被无端损耗，在网络中其能量应视为0.这时，按照原有的阈值设计原理，不可避免的在(1/p－1)轮中出现下述情形:在这些节点中，必然存在在原各自周期内从未成为簇头的节点.然而按照原有的阈值设计原理，这些节点的损耗占总损耗节点的比例势必影响剩余节点选举簇头的周期性规律.但若原有阈值仍维持不变将导致错误的簇头选举规律，从而导致之后的周期性簇头产生所占比例过多或过少，不能均衡承担网络工作负担，不能适应改变后的节点和簇头的比例，进而导致节点能量消耗加快.

2 τ－Leach协议分簇算法

2.1 τ－Leach算法的设计思路

τ－Leach算法，是针对上述问题而提出对Leach算法的一种改进，是在Leach算法在工作到某一轮rx时，突然出现一个区域内全部节点突然死亡的情况下，通过引入一个系数τ，调整Leach算法的阈值T(n)为τ*T(n)，使得节点成为簇头的概率发生改变，调整每轮产生的簇头的个数，优化簇的个数和剩余节点的比例，以使网络在新状态下的生存时间达到最优化.

2.2 τ的确定

τ－Leach算法，也是基于各节点能量的消耗前后保持均衡为前提考虑的，不可避免的，我们要根据在Leach算法中，节点能量的消耗作出调整.假设在一确定区域内均匀分布着N个节点，如果每轮生成k个簇，每个簇内约有N/k个节点.首先，考察每个簇头节点能量消耗.因为簇头离基站较远，所以采用能量损耗适用多径衰落信道模型(d4功率损耗)[6].每个簇头节点的能量损耗为:

然后，再考察每个非簇头节点能量消耗.通信消耗采用 Friss自由空间衰落模型(d2功率损耗)[6－7].每个非簇头节点消耗的能量为:

其中，l是每个数据流的bits数，dtoBS是簇头节点到sink的距离，dtoCH是非簇头节点与簇头之间的距离，EDA是簇头数据处理能量消耗，εmp，εfs是信号放大倍数.

通过以上两式不难看出，当rx轮有节点突然死亡的情况发生，即N，k发生变化时，对非簇头节点能量消耗并无影响，只需要保证轮rx前后

其中，k'和N'是变化后的簇头数和节点数，k'=(k/N)(N－ΔN)，ΔN为rx轮中损耗的节点数，就可以保证每个节点能量消耗大致平衡.

Leach算法中，平均N/k轮中每个节点都可以成为一次簇头.这样，某一个节点i，在第r轮被选为簇头节点的概率为:

由上式可知，在前r轮中，没有担任过簇头的节点数期望为N－k*[r mod(N/k)].在N/k轮后，所有节点均已经当选过一次簇头，在接下来的工作轮中，它们又可以继续当选簇头.由式(2)得.

其中Δn为rx轮时，损耗的前中从未成为簇头的节点.

2.3 τ－Leach算法工作机制

工作开始，基站的位置，网络节点的部署，每个节点所带有的能量确定.开始初始化，能量的消耗情况等均满足Leach算法的设定，并且按照Leach算法的工作机制工作.

当到达某一轮rx时，发生某一区域内节点死亡的情况，各簇统计损失的节点数 N以及 rxmod(N/k)轮中从未成为簇头的节点数n，并计算阈值T'(n)=τ*T(n).之后的轮中，网络的工作机制不发生改变，依旧按照Leach算法进行分簇，但是要采用新的阈值来筛选簇头节点.

图1 网络节点存活个数与工作轮数关系(b为a的局部放大图)

3 τ－Leach算法仿真实验

3.1 仿真环境

节点为100个且随机的分布在100m*100m范围内，每个节点的初始能量相同，每个节点在每一轮向自己的簇头节点传输的数据为4000b，基站位置为(50，150).本文对Leach和τ－Leach算法进行了仿真实验并比较.仿真参数如下表所示，实验在Matlab实验平台进行.并有如下表格中的假设.

表1 各仿真参数值假设

0.1 E elec 50 n J/b i t ε fs 10 p J/(b i t m 2)ε mp 0.0013 p J/(b i t m 4)E DA 5 n J/b i t数据包规格 500 b y t e s每轮时间p 8 s

3.2 存活节点数与工作轮数关系

图1是网络节点存活个数与工作轮数关系.因为在第rx轮时出现了节点损失，所以出现了明显的图像反映.rx=123轮后，Leach算法第一个节点死亡大约在第438轮，τ－Leach算法一个节点死亡大约是在464轮，τ－Leach算法比Leach算法提高网络寿命大约8.3%.

4 结论

本文根据无线传感器网络Leach算法容错能力的缺陷，基于能量提出一种改进算法——τ－Leach算法，并且在Matlab实验平台进行测试.根据测试实验结果的显示，新算法虽然简单，但在一定区域内发生节点突然死亡的突发事件时，新算法效果明显.采用τ－Leach算法能够更加均匀地将能量消耗分配到所有节点上，网络的节能和延长网络生存时间更具优势.

[1]Holger K，Andreas W.Protocols and Architectures for Wireless Sensor Networks[M].John Wiley＆ Sons，2006:94－128.

[2]马闯.无线传感器网络容错关键技术研究[D].黑龙江哈尔滨:哈尔滨工业大学，2011.

[3]Akyildiz I，Kasimoglu I.Wireless Sensor and Actor Networks Research Challenges[J].Ad Hoc Networks，2004，2(4):351－367.

[4]马建伟，李银伢.满意PID控制设计理论与方法[M].北京科学出版社，2007:1－3.

[5]Heizelman W，Chandrakasan A，Balakrishnan H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Networking，2002，1(4):660－670.

[6]Mischa D，Yonghui L.孙卓，赵慧，彭岳星(译).协同通信:物理层、信道模型和系统实现[M].机械工业出版社，2011:38－55.

[7]陈友荣，俞立，董齐芬，洪榛.基于近邻算法的无线传感器网络功率控制[J].浙江大学学报(工学版)，2010，44(7):1321－1326.