能量高效的无线传感器网络分簇路由协议*

贾惠丽, 范训礼, 吕艳峰

(西北大学 信息科学与技术学院，陕西 西安 710127)

0 引 言

如何高效利用节点能量并最大化网络生存周期是无线传感器网络( wireless sensor networks,WSNs) 研究领域始终面临的一个难点和实用性问题。

文献[1,2]中基于低能量自适应聚簇分层(low energy adaptive clustering hierarchy,LEACH)协议[3]存在随机选择簇首(cluster head,CH)的缺点，引入剩余能量等因素,根据能量和距离选择中继节点，构造簇首多跳传输路径。但在选择簇首时并未考虑节点的位置因素。为了优化网络节点分簇，提出基于K均值(K-means)聚类的分簇路由协议[4～7]。算法在初始阶段，利用K-means对节点进行分簇，根据某个或多个状态优化簇首选择。文献[4,8]中提出基于粒子群优化算法的分簇路由协议,但在数据传输时仍然采用单跳通信方式，增加网络能耗。文献[9,10]中基于遗传算法优化网路性能，但在选择簇首时未考虑节点的剩余能量。Singh R等人[9]提出基于交叉层感知的分簇算法，但该算法仍采用LEACH协议选择簇首，并且节点使用单跳模式通信，增加传输能耗。文献[12]中提出基于ZigBee的无线传感器网络改进，引入时间同步和碰撞避免等措施减少能量消耗。文献[13,14]分别采用了数据压缩感知，优化分簇结构提高感知节点的能量效率。

本文提出基于K-means和模糊综合评价方法——KAF(K-means and FAH)算法，根据改进的K-means聚类模型，优化分簇结构；结合节点当前状态改进簇首选择方式、考虑节点间距离、能量、可负载能力等因素，优化了数据传输时的多跳路由方式，减少传输能量耗费，延长网络生命周期。

1 能耗模型

本文采用一阶无线电能耗模型，节点在传输L-bit感知数据时的能耗计算为

(1)

(2)

节点接收L-bit的数据需要消耗的能量为

Erx=l×Eele

(3)

式中Eele为接收或者发送L-bit数据时电路所消耗的能量；Efs和Ems分别为自由空间信道模型及多路径衰减模型下的放大器的功率放大倍数；d为节点间的物理距离

(4)

式中 (x1,y1)和(x2,y2)为两节点的坐标。

2 KAF算法

2.1 算法模型

算法中采用的网络模型特点为：1)节点随机部署在监测环境范围内；2)节点和基站的位置固定不可移动；3)接收方节点根据发送方节点的发射功率计算出两者之间的距离；4)传感器节点的类型相同，具有数据融合的能力，彼此之间能够通信且均具有唯一的编号。

2.2 簇的划分

KAF在初始化阶段，采用K-means算法对节点进行分簇，为避免聚类效果依赖于初始聚类中心的选择，易陷入局部最优，引入蚁群聚类算法优化K-means对初始聚类中心的选择。此外，基本的K-means聚类将节点分配给距离最近的簇，较大的传输距离增加了网络的能耗，因此，为了使K-means更加适用于节点分簇，同时避免较低能量的簇首负载过重，考虑节点剩余能量，当节点选择簇首时，通过权值函数(式(5))优化节点分簇

(5)

2.3 簇首竞争

在选择簇首时，采用模糊层次综合评价方法，根据节点的当前状态选择簇首。主要步骤如下：

1)根据9标度法表构成判断矩阵A。

2)计算矩阵A中各行元素的乘积

(6)

3)计算Mi的n次方根，得到新的向量B

(7)

4)对向量B进行归一化处理，得到向量G

(8)

5)计算A和G的乘积，得到权值向量W。

6)计算最大特征值

(9)

7)对最大特征值进行一致性检验

(10)

式中RI为平均随机一致性指标，可查表获取具体值;n为矩阵A的阶数。

8)若计算出的CR值小于0.1，表示最后得到的权值向量W是可接受的。

9)确定簇内节点的评价指标构成的因素集U=(u1，u2,u3,…,un),其中ui为节点的剩余能量、节点的能量效率、到基站的距离、距簇中心的距离、节点计算能力等评价指标。

10)确定评价对象，即簇内所有可能被选为CH的节点。根据步骤(8)确定节点i在评价指标j处的值|uij|。

11)确定评价矩阵R=|rij|

(11)

式中umax,umin为所有评价对象在评价指标j处的最大、最小值

12)由层次分析法求得的评价指标权重，计算W×R，得到各对象的评价结果向量B，对B进行归一化操作，即可得到各节点成为簇首的概率。选择值最大的节点作为簇首节点。

2.4 数据转发

KAF算法采用多跳路由对节点的数据进行转发。网络中，所有CH和基站(base station,BS)构成连通无向图。 在该无向图中，CH与之间存在一条或多条传输路径，可通过以下标准判断最优路径：1)通过该条路径所消耗的能量；2)该路径上节点剩余总能量；3)该路径到基站经过的跳数。

最终判断权重函数式(12)评估路径是否为最优

(12)

CH选择其中一条路径进行传输数据时，根据式(12)计算路径的适应度值，选择最优路径进行数据转发。

3 仿真与分析

3.1 实验仿真环境及参数设定

采用MATLAB平台对KAF算法进行仿真实验，并将实验结果与(K-means-based routing,KMR)[11]， LEACH-K(LEACH and K-means),(K-means and particle swarm optimization,KPSO)[7]，KEE(energy efficient algorithm based K-means)[10]进行了比较。实验仿真环境为100 m×100 m区域中随机分布100个感知节点，汇聚节点位于(50 m,50 m)位置，每个节点初始能量为0.5 J，Eele，εfs，εms分别为50 nJ/bit， 10 pJ/bit/m2， 0.001 3 pJ/bit/m4。

3.2 实验结果

图1为各个算法的死亡节点随着迭代次数增加时的变化趋势。在相同时间内LEACH-K中节点死亡较多。而KAF算法优化了K-means分簇结构和簇首生成机制，首节点死亡时间最迟，有效延长了节点的生命周期。

图1 死亡节点变化对比

图2给出了各算法在进行一定轮次数据传输后节点剩余能量的变化情况。KAF算法中，簇首根据适应值函数选择最优路径进行数据转发，和其他算法相比较，有效地减少了节点能耗。

图2 节点总能量变化对比

图3表示不同算法的网络吞吐量变化趋势。结果显示， KAF由于节点能耗的减少使得基站在每轮中接收到更多的数据包，具有较高的网络吞吐量。

图3 每轮次传送数据包的个数

图4、图5表明，当基站距离监测环境较远时，死亡节点和网络总能量的变化趋势。KAF中簇首根据权值函数选择合适的路由，采用多跳转发的方式进行数据传输，有效减少了节点的能量消耗，节点具有较长的生命周期。

图4 死亡节点变化

图5 网络总能量变化

4 结 论

本文提出了基于分簇的KAF路由算法，扩展了网络的应用规模，延长了节点的生命周期，增加了网络吞吐量。