魏 鑫， 周世杰, 彭 牧, 冯 诚

(东北林业大学 信息与计算机工程学院， 哈尔滨 150040)

0 引 言

无线传感器网络路由协议主要负责将数据包从源节点通过网络转发到目的节点，即在传感器节点和sink节点之间建立路由,从而进行可靠的数据传输[1-3]。分簇路由协议与其它路由协议相比具有非常明显的优势[4-5]。其中，LEACH算法[6]是Heinzelman等人提出的第一个无线传感器网络自适应分簇路由算法。由于该算法仍存在很多缺点，研究学者们对其进行了诸多改进[7-10]。Kaur等人[7]考虑到节点剩余能量这一因素，通过改进阈值从而达到延长网络生命周期的目的，但仍显现出一定不足，如并未考虑为了均衡各个节点的负载，需要修改各个因子的权重。唐甲东[8]提出将簇头选举分为全网选举和簇内选举两个阶段，从而更好地平衡各个节点的能量，但依然没有着重考虑剩余能量。Mankita等人[9]考虑到节点的剩余能量，通过修改阈值增大剩余能量较高的节点成为簇头的概率。同时引入副簇头(vice cluster)的概念，减少每个簇的能量消耗以延长生命周期，但并未考虑某些剩余能量较高的节点能量利用不充分的情况。杨颖辉等人[10]考虑到节点剩余能量和普通节点距sink节点的距离两种因素，提出了LEACH-O算法降低网络能耗，但还需指出，研究中并未关注到随着轮数的增加，各个因子对网络负载均衡的影响力不同这一特征。本文针对LEACH算法的不足，考虑能量因子侧重度对簇头选举阈值进行改进，提出一种新型的LEACH-OE(LEACH based on energy factors)自适应算法。本文拟对此展开研究论述如下。

1 系统建模

1.1 网络模型

本文研究的无线传感器网络节点随机地分布在一个正方形监测区域内[11]，传感器节点和sink节点在部署之后位置固定不变[12]，并且不再进行人为干涉；节点同构且能量受限，具有相同初始能量[13]，处理能力和通信能力相等，被选中的概率相同；每个节点都具备了数据融合功能[14]，能感知自己的剩余能量并且具有全网唯一标识ID[15]；节点的无线发射功率可以自我调控，可自主选择发射功率[16]；sink节点计算能力和能量不受限制[17]。

1.2 能耗模型

本文采用的是一阶无线电能量消耗模型(first order radio model)[18]。假设传感器节点在传输距离为d时传送k比特的数据，所消耗的能量为：

(1)

信号在路径中的衰减模型分为自由空间信道模型(free space channel model)和多径衰减信道模型(multi-path fading channel model)两种[19]。其中，Eelec为发射电路或接收电路发送或接收1比特数据的耗能；d0为自由空间信道模型与多径衰减信道模型的切换阈值[20]，d

(2)

节点接收k比特数据消耗的能量为ERX(k) =kEelec；对k比特数据进行数据融合消耗的能量为Eagg(k) =kEda，其中Eda为传感器节点融合1比特数据消耗的能量。

2 LEACH-OE算法

2.1 LEACH算法概述

LEACH算法的执行过程是周期性的，因此可以引入“轮”的概念去描述。该算法在每轮的执行过程中不断地进行簇的重构过程，每轮循环分为簇的建立阶段和稳定的数据通信阶段，后一阶段通常比前一阶段时间复杂度高[21]。对此可做阐释解析如下。

2.1.1 簇的建立阶段

簇的建立阶段分为4个过程[22-23]。各过程设计详情可见如下。

(1)簇头节点的选择。T(n)为节点n自身的簇头选举阈值，每个节点产生一个0～1之间的随机数，如果这个数小于其自身阈值T(n)，则该节点成为簇头。T(n)值的计算公式如下：

(3)

其中,p为簇头在所有节点中所占的百分比；r为当前选举轮数；mod为取模运算符；G为前⎣1/p」轮中未当选过簇头的节点集合。随着当选过簇头的节点数目增加，剩余节点的阈值T(n)随之增加，未当选过簇头的节点成为簇头的概率增大。LEACH算法能够保证各个节点等概率地担任簇头，从而使整个网络的能量负载平均分配到每个传感器节点中。

(2)簇头节点的广播。节点成为簇头之后，发出广播消息通知自己是新簇头。

(3)簇的形成。节点成为簇头之后，普通节点根据自身与簇头之间通信的强弱来决定加入哪个簇并告知该簇头。

(4)调度机制的生成。簇头节点产生TDMA定时消息，为簇中每个普通节点分配向其传送数据的时间片。

2.1.2 稳定的数据通信阶段

该阶段的主要任务是进行数据的传送。数据传送采用TDMA[24-25]方式，每个节点按时间片将自己感知到的数据传送给相应的簇头节点，簇头节点经过数据融合将数据传送给更高级别的簇头或者sink节点。稳定阶段持续一定时间后，传感器网络重新执行簇的重构 ，并以此不断循环，直到不满足网络性能要求为止。

2.2 LEACH-OE算法设计

由于LEACH算法的簇头选举具有随机性，因此可能导致剩余能量过低的节点当选为簇头节点。为此，LEACH-OE算法引入能量因子对LEACH的阈值T(n)表达式进行改进。同时，分析可知每一轮中均会存在某些剩余能量较高的节点未参加簇头选举，则可通过自适应阈值的方法将这些节点重新加入未当选过簇头的集合并参加簇头选举，从而充分利用节点的剩余能量。该算法可以降低条件不佳的节点成为簇头的概率，减缓节点的死亡速度，平衡整个网络的能量负载，避免部分节点过早死亡造成网络瘫痪。这里，针对各研究要点，可给出探讨分述如下。

2.2.1 能量因子

网络初始阶段，各节点能量相同，均为E0。随着节点之间信号的传输，部分节点当选为簇头，其它节点成为普通节点。因为簇头节点消耗的能量远远大于普通节点，若某些节点频繁当选为簇头，这些节点将因电量迅速下降而枯竭死亡，最终导致网络部分瘫痪。因此，在进行簇头选举时，必须将节点的剩余能量考虑在内。定义节点的能量因子的数学公式如下：

(4)

其中，E(n)表示节点n的能量因子；Eresidual(n)表示该节点的剩余能量；Eave表示整个网络所有节点的平均剩余能量。可以看出，剩余能量越低的节点其能量因子越小。

2.2.2 阈值的修正

在改进算法中，针对每一轮选举簇头时节点n是否在前rmodp-1轮中当选过簇头，阈值T(n)被分为T1(n)和T2(n)两类。对此可得剖析论述如下。

(1)若节点n在前rmodp-1轮中当选过簇头且满足：

Eresidual(n)>Eave

(5)

则该节点再次参与簇头选举，相应的阈值为：

[αE(n)+ωA]

(6)

其中，参数n、p、r、G和式(3)中相同，α、ω是小于1的影响因子，并且α+ω=1。通过仿真实验发现，取α= 0.8 -Eresidual(n) /E0，ω=0.2+Eresidual(n)/E0时效果较好，A= (r-rlast) modp-1，rlast表示节点n上一次成为簇头的轮数，即A表示节点n从上次成为簇头之后经过的轮数。经过的轮数越多，该节点成为普通节点的时间越长，下一轮被选中的概率越大。

(2)若节点n在前rmodp-1轮中未当选过簇头，相应的阈值为：

(7)

其中,参数n、p、r、G和式(3)中相同。

对于能量因子的影响因子α，随着轮数的增加，节点的剩余能量越来越少。为了减缓节点的枯竭速度，均衡各个节点的负载，需要更加侧重考虑剩余能量这一因素。因此，随着传输轮数的增加，α逐渐增大，ω相对减小。各个因子的影响因子值总满足和为1。LEACH-OE 算法针对不同的网络负载情况自适应地调节参数α和β的影响因子值，使修正后的阈值达到最优。

2.2.3 算法流程

LEACH-OE算法对LEACH的簇头选举过程的研发改进主要可归纳为如下2点，即：

(1)引入能量因子来修正簇头选举阈值。

(2)在未当选过簇头的节点进行簇头选举之前，判断前rmodp-1轮当选过簇头的节点能否再次成为簇头。

其它过程与LEACH算法相同。这里，r表示当前轮数，Node(n)表示节点n。LEACH-OE算法成簇阶段的伪代码设计表述详见如下。

输入：传感器节点网络拓扑Gn

输出：分簇的传感器节点网络拓扑Gn′

ifNode(n)∉G

ifEresidual(n) >Eavethen

G←Node(n)

由式(6)计算T1(n)并生成随机数ξ1

ifξ1

Node(n)当选为簇头

end if

else

Node(n)退出簇头选举并成为普通簇头

end else

end if

else

由式(7)计算T2(n)并生成随机数ξ2

ifξ2

Node(n)当选为簇头

end if

else

Node(n)退出簇头选举并成为普通簇头

end else

end if

3 实验仿真及分析

3.1 仿真环境参数设置

采用Matlab R2014b作为实验仿真平台，将LEACH和LEACH-OE算法进行仿真和性能对比分析。仿真参数设置见表1。

3.2 实验结果及分析

节点的分布情况如图1所示，可以看出节点均匀分布在监测区域内。

随着仿真轮数的增加，2种算法不同数量死亡节点对应的轮数见表2。若以90%节点死亡的轮数作为衡量网络性能的标准，LEACH-OE算法的网络生命周期较LEACH算法提高了约13.12%。

表1 仿真参数

图1 节点分布

算法种类轮数第一个节点50%节点90%节点LEACH347687983LEACH-OE3117461 112

图2显示了随着仿真轮数的增加，2种算法在网络中存活节点数的变化情况。可以看出，采用LEACH算法出现第一个死亡节点的轮数在第347轮，而采用LEACH-OE算法虽然第一个节点死亡的时间比LEACH算法早，在第311轮，但是从LEACH-OE算法出现第一个死亡节点的轮数到第1 200轮，在大部分时刻LEACH-OE算法存活节点的数量要高于原始的LEACH算法。

主要是由于LEACH没有充分考虑到节点剩余能量的因素，有些节点自身能量过低，但在下一轮簇头选举时仍被选为簇头，这样会使节点剩余能量耗尽，加速该节点的死亡，甚至导致在节点未完成本轮通信时就提前死亡，降低网络传输效率和网络鲁棒性。同时，LEACH-OE算法还考虑到某些剩余能量较高的节点能量未被充分利用的情况，使满足条件的节点重新参与簇头选举，充分利用了节点的剩余能量。因此，LEACH-OE算法减少了簇内和簇间的网络消耗，减缓了节点的死亡速度，均衡了全网节点的能量负载，同时相较其它算法能耗更低，有效延长了整个网络的生命周期。

图2 存活节点数随轮数的变化

4 结束语

针对LEACH算法的不足，本文提出一种考虑能量因子的无线传感器网络分簇路由算法。该算法采用新型簇头选举机制来均衡全网能量负载，并考虑到应尽可能减小剩余能量较低的节点当选簇头的概率，引入能量因子来修正簇头选举阈值并且在因子前面赋上相应系数，从而避免低能量的节点成为簇头。此外，通过自适应阈值的方法使部分剩余能量较高且已当选过簇头的节点重新参加簇头选举。实验证明，改进算法相较其它算法能耗更低，有效避免了节点过早死亡，从而延长了网络的生命周期。下一步，拟将继续研究大规模网络下分簇路由算法的优化问题。