无线传感器网络分簇路由算法研究与改进

许东菊 郑明春

山东师范大学管理科学与工程学院 山东 250014

0 引言

无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作的感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。一个传感器节点由传感器模块、处理器模块、无线通信模块和能量供应模块四部分组成，其中能量供应模块提供传感器节点运行所需的能量，它通常采用能量有限的微型电池供电，因此如何提高电池能量的利用率，延长网络寿命，成为近年来研究的热点。

在分簇路由算法中，网络通常被划分为簇(Cluster)。簇，即具有某种关联的网络节点集合。每一个簇由一个簇首(Cluster Head)和多个簇内成员(Cluster Member)组成。分簇式的层次型拓扑结构具有很多优点：数据融合主要是由簇头节点来承担，减少了数据通信量；采用分簇式的拓扑结构有利于应用分布式算法，适合大规模的网络；成员节点大部分时间可以关闭通信模块，由簇首构成一个更上一层的连通网络来负责数据的长距离路由转发，可以显著地延长网络寿命；便于扩展和管理，并能够很好地解决传感器节点移动带来的定位问题。本文提出的路由算法，正是考虑了分簇的层次拓扑结构的这些优点，采用了新的簇首选择方法，同时构造簇间多跳路由，利用Wardrop均衡原理，选择“费用”最少的路径传输数据到Sink节点，从而进一步降低能量消耗，延长整个网络的寿命。

1 相关工作

在传感器网络中，传感器节点的无线通信模块在空闲时的能量消耗与在收发状态时相当，所以只有关闭节点的无线通信模块，才能大幅度的降低节点的能量开销。层次型拓扑结构的分簇算法将节点划分为簇首节点和普通节点，通过采取一定的机制选择某些节点为簇首节点，打开簇首节点的无线通信模块，并关闭普通节点的通信模块，由簇首节点构建一个连通网络来负责数据的路由转发。这样既能保证全网内的数据通信，又在很大程度上节省了节点的能量。由于簇首节点需要负责簇内节点数据的融合和转发，能量消耗较大，所以周期性的选择簇首，可以避免某些节点由于能量消耗过快而很快死亡，从而均衡网络节点的能量消耗。

2 LEACH算法改进的新算法

近年来，针对LEACH协议的改进主要表现在两个方面：(1)簇头的选择；(2)簇间采用多跳通信方式传输数据到Sink节点。本文正是从这两个方面对LEACH协议进行改进，设计一种基于分簇的高效路由算法(An Efficient Cluster-based Routing Algorithm，AECRA)，其基本思想是：在考虑节点的剩余能量和相邻节点间的能量消耗的基础上选择簇首节点；簇首节点确定以后，利用贪婪算法结合Wardrop均衡原理，选择簇首节点到Sink节点“费用”最少路径传输数据，降低整体能量消耗，延长网络寿命。

2.1 模型描述

在特定的区域内，N个无线传感器节点随机均匀分布，周期性收集周围环境的信息，并具有如下一些性质：

假设所有的传感器节点一经部署后都是静止不动的，且每一个节点都有惟一的一个预先分配的标识ID。

假设只考虑单一的Sink节点，且Sink节点的能量不受限制假设节点可以根据接收方距离的远近自动调节发射功率。

假设链路是对称的。

AECRA算法采用和LEACH算法相同的无线通信模型，当节点传输lbit数据到距离为d的节点所消耗的能量为：

接收lbit数据消耗的能量为：

2.2 算法描述

同LEACH算法一样，AECRA算法也是按轮进行的。当节点随机部署完成以后，首先要做的就是寻找邻居节点，并建立一个邻居列表，存储邻居节点惟一的 ID及节点的一些特性，如果某个节点的能量耗尽，它的 ID将从邻居列表中移除(见表1)。

表1 邻居表内容

2.2.1 AECRA簇的建立

在随机部署节点之前，预先定义一个初始能量阀值，嵌入到每一个节点中。在这里我们采用网络中存活节点的剩余能量的平均值作为初始能量阀值。在整个网络生命周期内，Sink节点可以决定剩余能量阀值，并在每一轮开始时，它都是可以改变的。簇头节点收集簇内节点的剩余能量值，并把所有节点的剩余能量的平均值发给Sink节点，Sink节点计算整个网络剩余能量平均值并告知每一个簇头节点，簇内节点通过和其簇头节点进行直接通信，获得新的能量阀值。

如果一个节点剩余能量大于初始能量阀值，并且没有收到来自其它节点宣布为临时簇头的公告信息，则宣布自己为临时簇头，并告知它的邻居节点。同时，收到临时簇头公告信息的邻居节点，需要把自己的剩余能量和 ID反馈给临时簇头。如果一些节点同时收到多个临时簇头的公告信息，它只回复和它相邻最近的临时簇头。这样就建立了临时簇。临时簇的建立过程(见图1)。

图1 临时簇的建立

在每一个临时簇中，簇内成员节点具有较高剩余能量的可以作为潜在的簇头节点，并告知临时簇头。临时簇头和潜在簇头节点通过对比节点剩余能量同邻居节点的平均能耗的比值，确定最终的簇头节点。

进入稳定的运行阶段后，簇内节点持续的检测、采集数据，传给簇头节点后发送给Sink节点，持续一段时间后，进入下一个周期，重新选择簇头。

2.2.2 AECRA簇间动态多跳路由算法

该算法对簇首节点和 Sink节点的通信方式做进一步的改进，采用多跳方式，建立由簇首节点组成，以Sink节点为根的树。

为了确保从簇首节点到 Sink节点之间的路径是最优路径，本文以泛洪(flooding)方式作为路由树的生成方式，具体过程如下：

(1) 定义Sink节点深度为0，距离Sink一跳的簇首节点的深度为1，依此类推，Sink节点用泛洪的方式确定第i簇首节点到Sink节点的深度di；

(2) 从深度为0的Sink节点开始，各节点逐次向其相邻的深度为di+1的邻居节点通报数据包传输到Sink节点的最优费用pi，其中Pi表示从i节点到Sink节点的最小的“费用”路由的总费用；Eij表示从i节点到相邻节点j的能量消耗。

(3) 第i簇首节点收到上一深度相邻簇首节点j、k传送的节点信息后，为每个相邻簇首节点建立路由信息表(见表2)。换为较容易计算的弧流量引入到模型中，并用较为简单的“全有全无”方法进行求解，本文也将应用该方法求解。

表2 路由信息表

3 仿真实验和性能分析

到此从簇首节点到Sink节点的最小“费用”路由树建成。

算法开始时，Sink先以给定的功率向全网发送广播信号，节点根据收到的信号的强弱计算出它到Sink节点的距离d。并假定中继簇头收到上一跳的数据没有冗余信息，且来自不同簇的数据无法进一步融合，中继簇头只是简单的转发来自其他簇头的数据。簇首节点通过公式(1)计算得到它直接传送数据到Sink节点的能量消耗，标记为Etosink；只有满足通过中继转发的费用P＜Etosink，簇首节点才会选择通过多跳方式。由于在每个周期内，每个簇首节点都是自私的寻找一条“费用”最少路径，这就导致某些节点的能量消耗过快，后继数据包在传送时就会选择一些能耗下降较少的次优路径传送，经过一段时间，可认为数据流会根据路由选择机制均匀的分配到不同的路径上，达到一种均衡状态，即 Wardrop均衡，在这种均衡状态下，每一个簇首节点都认为自己采取了最优的路由策略，本文中我们应用文献[10]中的模型求解这种最优的路由策略，实现整个网络的传输“总费用”最小，模型描述如下：

定义数据传输过程中链路(1跳)的“费用”函数为：

本文利用 NS-2仿真平台对 LEACH、LEACH-C和AECRA算法进行仿真比较，在100m×100m的矩形区域内随机部署 100个传感器节点，Sink节点位于(50,175)，所有节点的通信距离为20m，节点的初始能量E0=2J，原始数据产生速率为1kb/s，发射电路和接收电路需要消耗的能量ETX=ERX=50nJ/bit，簇头融合数据消耗的能量Edf=50pJ/bit ，功率放大器消耗的能量Efs=100pJ/(bit⋅d-2)，信号放大器倍数εmp=0.0013pJ/bit/m4，采样周期为10s，簇头个数Kopt=5，节点能量为0时，认为节点死亡，并且假定数据融合率为 100%，在转发过程中不存在数据包丢失，无误码率。

图 2是存活节点数和轮数关系图。可以看出，LEACH协议的曲线下降比较快，网络中节点能量消耗大，LEACH-C协议曲线在300轮前节点能量消耗比LEACH大，但是之后存活节点个数多于 LEACH，且整个网络的生命周期明显比LEACH长。这是由于LEACH-C在每轮循环中，节点都要向Sink节点发送自己的位置和剩余能量，所以刚开始时节点能量消耗比LEACH大，但是由于LEACH-C是Sink节点合理的选取簇头，所以运行一段时间后，存活节点的个数多于LEACH。而AECRA算法由于考虑了解点的剩余能量和簇头节点间采用多跳的方式传输数据，所以在每轮循环中存活节点的个数明显优于LEACH和LEACH-C，从而延长了整个网络的生存周期。

其中A为所有链路的集合。

可以证明，模型的一阶必要条件满足本文提出的路由选择方式。直接求解该模型是非常困难的，针对这类问题，Backmann提出Frank-Wolf方法，将难以计算的路径流量转

图2 存活节点数和轮数关系图

图3是节点能耗和轮数关系图，显示的节点的总的能量消耗情况，仿真实验中每隔 10轮做 1次采样记录。从图 3可以看出，新算法的节点总能量消耗少于LEACH算法，说明新算法有效的节省了能量，延长整个网络寿命。

图3 节点能耗和轮数关系图

4 结束语

本文提出一种基于能量和距离的分簇多跳路由算法-AECRA算法，簇头的选择考虑了节点的剩余能量和相邻节点间的能量消耗，并且改进了簇头和Sink节点间通信的方式，应用Wardrop均衡原理寻找最优路由策略进行数据转发。仿真结果表明，与LEACH算法和LEACH-C算法相比较，新算法有效的节省了节点的能耗，延长了整个网络的生存周期。

[1] 邱天爽,唐洪等译.无线传感器网络协议与体系结构[M].北京:电子工业出版社.2007.

[2] 蔡绍滨.无线传感器网络关键技术的研究与应用[M].哈尔滨工业大学出版社.2011.

[3] Heinzelman W, Chandrakasan A, Balakrishnan H.Energy-Efficient communication protocol for wireless microsensor networks[R].In:Proc. of the 33rd Annual Hawaii Int’l Conf. on System Sciences.Maui: IEEE Computer Society.2000.

[4] 孙利民,李建中等著.无线传感器网络[M].北京:清华大学出版社.2011.

[5] Younis O, Fahmy S. Heed: A hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks[J]. IEEE Trans. on Mobile Computing, 2004.

[6] Heinzelman W R,Chandrakasan A,Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Micro-Sensor Networks［J.IEEE Transaction on Wireless Communications.2002.

[7] Tillapart P, Thumthawatworn T,Pakdeepinit P,Yeophantong T,Charoenvikrom S,Daengdej J.Method for cluster heads selection in wireless sensor networks[R].In:Proc.of the 2004 IEEE Aerospace Conf. Chiang Mai: IEEE Press.2004.

[8] 刘琼，成运.一种无线传感器网络分簇路由算法研究[J].现代电子技术.2010.

[9] 刘铁流，巫咏群.基于能量优化的无线传感器分簇路由算法研究[J].传感器技术学报.2011.

[10] 黄海军.城市交通网络平衡分析-理论与实践[M].北京:人民交通出版社.1994.

[11] Beckmann M,Mcguire CB,Winsten CB.Studies in the Economics of Transportation[M].New Haven: Yale University Press.1955.

[12] Yuan YX,Sun WY.Optimization Theory and Methods[M].Beijing:Science Press.1997.