基于分簇的无线传感器网络路由算法

付菁波

(1.西安电子科技大学研究生院，陕西西安 710071;2.杨凌职业技术学院文理学院，陕西杨凌 712100)

无线传感器网络综合了传感器、分布式信息处理、嵌入式和无线通信技术，形成一种新的信息获取和处理方式，实现了物理世界、计算机和人类社会的交互，是物联网络发展的基础［1］。被广泛应用于国防军事、环境监测、农业科技和医疗卫生等领域。

无线传感器网络由部署在户外无人看护的大量传感器节点构成。这些传感器节点肩负着监测和传输数据的任务，而传感器节点本身体积微小，由电池供电，所以能量成为网络中珍贵的资源，也是网络运行中的关键问题。数据聚合技术是无线传感器网络中多个节点将数据包传送到一个节点后对数据进行聚合处理的数据传输方式。这样可以有效消除网络中的冗余数据，减少数据的传输量，延长网络寿命。因此将数据聚合技术引入到无线传感器网络中具有广泛的应用前景。

1 问题分析与改进策略

LEACH是较早提出的经典分层路由协议，随后研究者们提出的多种分层协议都是建立在LEACH协议的基础上。该协议分为簇的建立阶段和稳定传输阶段。在簇建立阶段，簇首随机产生，具体选择方法是传感器节点在0和1之间产生一个随机数，如果该值小于设定的阈值T，则该节点就宣布成为簇首。其中阈值T是没有考虑其他因素随机产生的，没有优化簇首的数量，并且当网络运行一段时间后就会出现簇首分布不均、个别节点由于能耗过大而出现失效等现象。在稳定传输阶段，簇首收集簇成员数据，聚合后直接将结果发送给sink。这里簇首与sink直接通信，对簇首的能量造成快速损耗，不利于网络长时间运行。

基于LEACH的不足，文中对簇首的选举和簇间数据的转发做了改进。首先根据网络的规模和节点个数，预先设定最优的簇首数目。为使簇首分布比较均匀，将剩余能量大于网络节点平均能量的节点作为候选簇首，借鉴两分法的思想，以两个符合能量要求、距离最远的候选簇首节点为当选簇首将网络分成两个簇，在簇内再以两个符合能量要求、距离最远的节点为簇首再分成两个簇，依次类推进行分簇。应用两分法时，从距离sink近的簇分起，当簇首数目等于预先设定的最优簇个数时停止分簇。这样不但能保证能量较充足的节点当选簇首，而且可以较好地控制簇首分布，有利于能量均衡消耗，从而达到延长网络寿命的目的。其次在大规模网络中，簇首将数据通过其他簇首多跳转发到sink，比直接发送到sink进行远距离通信更节省能量。本文通过考虑到下一跳节点转发的距离和能耗代价两方面的因素给出了数据传输的代价函数，计算出传输代价最小的路径。同时考虑到数据的相关性，给出了簇内数据聚合策略，减少了网络中的冗余信息，提高了网络的寿命。仿真实验表明，在降低网络能耗、延长网络寿命等方面都有显著提高。

2 网络模型和能量模型

2.1 网络模型

针对大规模部署网络考虑数据收集的过程，做以下假设:(1)网络是一个规模较大的平面网络，其中只有一个sink节点，部署在网络区域外一个确定位置。(2)传感器节点是随机部署的，所有节点和sink都处于静止状态，且都有唯一的ID。(3)传感器节点的功能相同，但初始能量不全相同，稍有差别。(4)传感器节点的发送和接收功率是可调整的。(5)可以通过定位算法或GPS等，已知每个节点的位置信息。

2.2 能量模型

传感器节点的能耗分别来自于节点之间的数据通信和节点自身的运算存储。节点自身的运算存储能耗相比节点之间的通信能耗小得多。研究表明，将1 bit数据传输100 m所需的能耗相当于节点执行3 000次运算存储命令［3］。因此研究中忽略了节点自身进行的运算存储能耗。文中节点接收能耗ERx和发送能耗ETx，采用无线通信能耗自由空间模型和多路径衰减模型［4］，如下

其中，Eelec表示每比特无线收发电路损耗;k表示接收或发送数据的比特数;d表示通信距离;εfs表示收发电路的基本能耗系数;εmp表示电路放大功率的能耗系数;d0是根据网络具体情况设定的。

路由中采用数据聚合策略，数据聚合的能量模型表示如下:设聚合节点接收了k个节点的数据，每个节点发送lbit数据，对1 bit的数据聚合的能耗为EDa，则对k个节点的数据做聚合的能耗为

以上涉及的参数参考值为Eelec=50 nJ/bit，εfs=10 pJ/bit·m2，εmp=0.001 3 pJ/bit·m4，EDa=5 nJ/bit·signal。

3 改进的路由算法

3.1 簇的建立

文献［4～5］中，根据网络规模和能量消耗分析可以得出最优的分簇数kopt，本文在已知kopt的基础上给出改进的簇建立算法:(1)输入网络中每个节点的剩余能量ei，预设最优的分簇个数为kopt。(2)初始化。计算网络中所有节点的平均剩余能量，记为e;簇首集合D，初始D=∅;网络当前的簇首个数为N，初始N=1。(3)将剩余能量大于平均能量的节点作为候选簇首组成集合S={节点剩余能量ei＞}。(4)在集合S中选出距离最远的节点ti，tj作为簇首，其他节点按就近原则加入簇，网络被分为两个簇S1和S2，D=D+ti+Tj且N=N+1。(5)根据节点的位置信息，计算簇首ti和tj到sink的平面距离d(ti)，d(tj)。(6)若N＜kopt，对距离sink近的簇优先使用两分法，返回步骤(4);若N=kopt分簇结束，算法执行完毕。

各个簇不能同时使用两分法分簇，否则簇的数目是以2n指数型增长，难以保证簇的数目刚好等于最优簇的个数。为解决这个问题，本文提出离sink近的簇优先使用两分法，按照簇首到sink的距离由近及远，逐个分。这样可能还没有等到所有的簇都被分一遍时，已经达到了最优簇的个数，分簇停止。此时离sink较近的簇比较小，而离sink远的簇比较大，这也正符合簇首的能量消耗需求，因为离sink近的簇首会较多地承担中继其他簇首数据的任务。

3.2 簇内数据聚合策略

其中，v0表示簇首节点;CHaggr(v0)表示簇首聚合后的数据包大小;v1，v2，…，vk表示簇内成员节点;data(vi)(i=0，1，2，…，k)表示各节点原始数据包的大小。

由式(4)可看出，两个节点间的距离越大，感知到的数据相关度就越小，data(vi)·［1- ρ(vi，v0)］(i=0，1，2，…，k)就尽可能多地保留了源数据;相反，节点间距离越小，数据相关度越大，数据就相应地被聚合压缩。从而有效删除了网络中的冗余数据，减小了数据的传输量，节约了网络能耗。

3.3 簇间的数据收集策略

LEACH协议在簇间收集数据时，是由簇首直接将数据发送给基站，但当簇首距离sink节点较远的情况下，用于数据发送的能耗过大，将很快耗尽簇首的能量而最终导致网络瘫痪。尤其是针对大规模网络，簇间采用多跳转发的模式是有效节能的手段之一。文中给出了一种基于能耗代价的数据收集策略，基本思想是当一个簇首向另一个簇首转发数据时，考虑距离因素，计算簇首和自己相邻几个簇首的能耗代价，从中选出能耗代价最小的簇首作为数据的下一跳转发簇首。这个能耗代价考虑了通信距离和下一跳簇首的剩余能量两方面因素，并有效防止了数据的回传。

网络分簇后，簇内节点调整通信功率只与簇首通信即可。sink节点向簇首以洪泛的形式发出报文，此报文包含了sink节点的位置信息ID和跳数计数值hop，sink节点的跳数值初始化为hopv0=0。从节点vi处接收到此广播的节点vj用自己的ID替换原报文中的ID，并更新跳数值hopvj=hopvi+1。当某个簇首重复收到报文信息时，则与自己的hopvj比较判断跳数值:(1)若 hopvj=hopvi+1，则vj记录发送节点vi的ID，保留跳数值不变。这些被记录ID的节点vi跳数值比vj的小1，是vj的上一级节点，可列为vj转发对象。(2)若hopvj＞hopvi+1，则重新记录节点vi的ID，并更新vj的跳数值为hopvi+1。(3)若 hopvj＜hopvi+1，且vj的跳数值比hopvi+1小1，则记录发送节点vi的ID，保留跳数值不变，这些记录下来的节点vi的跳数值与vj的跳数值相等，和是同一级的节点。若hopvj与hopvi+1之差＞1，则不记录发送节点的ID，保留跳数值不变，丢弃该报文。

上述的跳数值是数据发送到sink需要转发的次数，直接反应了簇首和sink节点之间的距离。当报文按照上述方法在簇首之间广播完毕后，每个簇首节点记录了自己的跳数值信息，同时记录了上级簇首节点和同级簇首节点的ID信息。在下一步数据转发过程中，每个簇首就只需计算与自己上级或同级簇首通信的能耗代价。

每个簇首计算刚记录下来的相邻簇首的能耗代价，代价函数Costmn具体表示为

其中，d(m，n)表示簇首m与n的距离;Ere(n)表示下一跳簇首n的剩余能量;hopmax表示簇首的最大跳数值;hopn表示下一跳簇首n的跳数值;α，β，γ为权重因子，且 α+β+γ=1，γ＞α，β。

由式(5)可看出，代价函数Costmn正比于簇首间的传输距离，两簇首间的距离越小能耗就越小;反比于下一跳簇首的剩余能量，数据优先向剩余能量多的簇首转发;正比于下一跳簇首的跳数值，且此项的调节因子γ大于其他两项的调节因子，说明在转发过程中要把数据发送到距离sink节点近的簇首，而不能回传，耗费网络的能量。如图1所示，B为sink节点，A，C，D是簇首，虽然A到D的距离最短，但是D远离sink，从整体看A通过D到sink所消耗的能量比A通过C到sink所消耗的能量大，因此从节能的角度出发，A的数据通过C发送到sink，避免数据的回传现象。从代价函数中可以看到下一跳簇首的跳数值越小，说明该簇首离sink越近，能耗代价就越小。

图1 簇间防止数据回传转发示意图

4 仿真与分析

实验环境是将100个传感器节点随机分布在100 m×100 m的方形平面区域中，sink的位置坐标是(50，150)，数据包大小为1 024 bit，节点的初始能量为2 J。接收和发送消耗能量的参考数据在前文能量模型中已给出。

4.1 簇首能量消耗比较

在基于分簇的无线传感器网络路由算法中，簇内节点都是通过单跳将数据发送到簇首，它们的能量消耗在各种算法中相差都不大，而簇首承担着收集、聚合簇成员节点的数据，并将聚合的结果发送到sink，是各种算法中能量消耗的主要部分。因此本文将LEACH和改进算法中簇首在一轮中消耗的能量加以对比。如图2所示。图2中给出了连续10轮中簇首的能量消耗总和，可以看出本文改进的算法簇首能耗大幅低于LEACH算法，主要原因在于LEACH算法中簇首通过单跳将数据直接发送到sink，远距离的通信大幅消耗了簇首的能量。而本文采用两分法控制了簇首的分布，且簇首间利用代价函数计算出能耗较小的转发路径，将数据通过短距离多跳转发方式发送到sink，从而降低了簇首的能量消耗。

图2 簇首的能耗对比

4.2 网络生存期的比较

首先，定义网络的生存期为网络中第一个节点能量耗尽的时间或轮数。从图3中可以看出，LEACH算法的网络生存期是350轮，改进算法的网络生存期是580轮。相比之下，改进算法有效延长了网络的生存期。分析其原因在于，LEACH算法中簇首是随机选取的，没有考虑当选节点的剩余能量和簇首在网络中的分布情况，能量消耗的不均匀不利于网络长时间运行。而改进算法在考虑节点剩余能量的基础上采用两分法选举簇首，不但保证了新簇首有充足的能量，而且控制了簇首的分布，使网络能耗更加均衡，从而延长了网络的生存期。

图3 两种算法的网络生存期比较

图4 权重因子调整对比图

4.3 能耗代价函数中权重因子的选择

在能耗代价函数式(5)中 α，β，γ是3个权重因子，它们的值决定了代价函数在距离、剩余能量和跳数3方面的侧重程度，从而影响着网络的整体能耗。如图4所示，曲线①中 α=0.5，β=0.5，γ=0;曲线②中α=0.2，β=0.2，γ=0.6;曲线③中 α =0.3，β=0.3，γ=0.4。图4所示曲线①只考虑了到下一跳簇首的距离和剩余能量，没有考虑下一跳簇首到sink的跳数，当节点发送数据时仅根据这两方面的局部信息作出判断容易发生数据回传现象，从而耗费能量。曲线②、③中考虑了跳数因素，防止了数据回传，能耗有所减少，但是曲线②对距离和剩余能量因素侧重较少，使得有些簇首为了把数据发送到跳数小的下一跳簇首，而将数据发送到剩余能量少、距离远的簇首，导致能量的消耗和不均匀分布。相比较，曲线③在有效防止数据回传的基础上，综合考虑了下一跳簇首的距离和剩余能量两方面因素，使得网络整体能耗偏低。说明α，β，γ 3个因子的取值要比较均衡，其中γ的值稍大，这样能兼顾多方面因素，使能量消耗分布相对均衡，有利于延长网络的生命期。

5 结束语

由于基于分簇的路由算法具有较好的可扩展性、便于管理等特点在无线传感器网络的路由算法中被广泛应用。这类算法中簇首的能耗较大，容易产生能量消耗的热点现象，是问题解决的关键。本文在LEACH算法的基础上对簇首的选举、簇首的分布控制和簇首间的数据转发做了改进，并结合数据聚合机制进一步节约网络的能耗。仿真结果表明，算法有效地均衡了网络的能耗，延长网络的生存期。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005.

［2］JUNG W S，LIM K W，YOUNG B K，et al.Efficient clustering-based aggregation techniques for wireless sensor networks［J］.Springer Science+Business Media，LLC Wireless Netwoerk，2011(17):1387-1400.

［3］BARR K C，ASANVIC K.Energy aware lossless data compression［J］.ACM Transactions on Computer Systems，2006(8):1121-1126.

［4］张小庆.无线传感器网络路由协议的研究与仿真［D］.武汉:武汉理工大学，2009.

［5］彭爱平，郭晓松，蔡伟，等.基于估计机制的分簇传感器网络数据融合算法［J］.传感技术学报，2011，1(24):128-133.

［6］沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，7(17):1588-1600.

［7］余勇昌，韦岗.无线传感器网络中能耗均衡的数据收集算法［J］.通信技术，2008(2):93-96.

［8］唐伟，郭伟.无线传感器网络中的最大生命基因路由算法［J］.软件学报，2010，7(21):1646-1656.

［9］RICKENBACH P，WATTENHOFER R.Gathering correlated data in sensor networks［C］.Philadelphia:Proceeding of the Joint Workshop on Foundations of Mobile Computing，ACM Sigmobile，2004:60-66.