分层的无线传感器网络非均匀分簇路由算法

王 桐， 杨 磊

(哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001)

0 引言

无线传感器网络(wireless sensor networks，WSN)是由大量的微型的传感器节点构成的，各个节点通过自组织方式构成无线网络，并以相互协作的方式感知、采集和处理网络覆盖区域内的特定信息[1]。与传统无线网络不同，组成网络的传感器节点的能量有限，且通常无法进行更换。因此，在设计WSN路由算法时，需要重点考虑节点的能量效率以便尽最大可能地延长网络的工作时间[2]。

近年来，在无线传感器网络中，有很多分簇路由算法被提出。为了避免簇头过多地消耗能量和减少通信业务量，文献[3]提出了一种低功耗自适应分簇路由算法(low energy adaptive clustering hierarchy，LEACH)。采用循环随机成簇方式，各节点轮流担任簇头，使网络的能量负载均衡到各个节点上，延长了网络的生存时间，但是LEACH采用单跳通信方式，簇头与基站进行直接通信，造成簇头的通信开销很大。研究已表明，在数据转发过程中簇头和基站之间采用多跳通信方式更有利于节约能量[4]。多跳通信方式进行数据传输和转发时，很容易导致与基站较近的簇头因需承担过多的转发任务而过早的死亡，造成网络能耗极不均衡，即所谓“热区”问题[5－6]。针对该问题，文献[7]给出了一种基于分布式的非均匀分簇算法(energy－efficient uneven clustering，EEUC)，根据候选簇头到基站的距离远近，从地理位置上将网络分成大小不等的非均匀的簇类结构，以便均衡簇头的负载，但是在簇头竞选时没有考虑节点的剩余能量，而且成簇过程中容易出现迭代现象，成簇开销比较大。文献[8]从部署模型上进行考虑，采用蚁群算法优化网络中各个节点的能耗问题，仿真表明，能够延长网络的生存时间，但是需要人工部署限制了其在实际环境中的应用。文献[9]提出了负载均衡的自适应分簇算法，在簇头选择上同时考虑簇半径、节点剩余能量和簇头间距，并采用多跳方式进行数据通信。文献[10]对其进行了改进，还考虑了相邻节点的剩余能量。文献[11]选择剩余能量最多的节点担任簇头，且限制簇的规模。文献[12]针对“热区”问题，提出了采用剩余能量启发合作的传输方式来进行数据传输的方法，以避免能量空洞。但是，上述路由算法皆没有考虑簇间数据传输时的长距离通信问题。

鉴于此，笔者对EEUC算法进行改进，提出了一种基于分层的非均匀分簇路由算法(layered unequal clustering routing algorithm，LUCRA)。LUCRA 的改进之处:一是在EEUC算法的竞争半径计算方式上引入了节点的剩余能量，以使簇头负载更加均衡。二是改进了EEUC算法的成簇过程，避免出现迭代现象，提高了算法的收敛速度。三是通过对簇间长距离通信展开分析，建立多个层次的网络结构，并利用相邻簇的交叉节点进行数据转发，极大地减少了数据通信开销，进一步延长了网络的生存时间。

1 系统模型和问题分析

1.1 系统模型

1.1.1 网络模型

假设无线传感网络由N个节点组成，节点分布在一个固定大小的区域内。设第i个节点为si，则节点集 S={s1，s2，s3，…，sN－2，sN－1，sN}，|S|=N。传感器网络的应用环境是周期性的数据采集，且具有如下性质:基站和节点部署以后不可以移动，且基站仅有一个并位于监测区域外;所有节点具有相同的属性和功能;节点可以根据发射接收信号的强度估算与发射源之间的相对位置;无线发射功率可控，节点能够根据距离调整发射功率的大小。

1.1.2 无线通信模型

采用文献[13]中使用的无线信道模型来计算节点发送和接收数据所消耗的能量。

假设节点A向节点B发送l字节的数据，两节点间距离为d，则其能量损耗:

节点B接收l字节数据所消耗的能量为

其中，门限值d0:

式中:Eelec——发送电路和接受电路发送或接受单位比特数据消耗的能量;

εamp——信号放大器的倍数;

εfsd2、εmpd4——无线电功率放大损耗。

1.2 簇间长距离通信

如图1所示，节点A向节点C发送数据有两种方式可以选择，一是直接通信即从A到C;二是间接通信即从A到B再到C，其中节点B位于节点A和节点C之间。各节点之间的通信距离分别为dAB、dBC、dAC。

图1 数据转发Fig.1 Data forwarding

假设dAC大于 d0而 dAB、dBC小于 d0。从节点 A向节点C发送单位比特的数据，根据式(1)、(2)，路径A→C所消耗的能量为

路径A→B→C所消耗的能量为

则EAC与EABC之比:

又由 dAB+dBC=dAC、d2AB+d2BC≥2dABdBC，可得

推导可得:

若令不等式(3)右边小于1，可得

变换可得

求解可知，存在某一值，记为r。当dAC在零到r之间，不等式(4)成立，即有EAC＜EABC，若dAC大于r时，不等式(4)不成立，即有EAC＞EABC。也就是说当两节点间距离小于r时，采用直接通信比间接通信所消耗的能量要少，而当两节点间距离大于r时，采用间接通信比直接通信所消耗的能量要少。经估算r的值在160 m左右。因此，如果在数据转发过程中依照此原则进行路径选择，就可以有效地降低网络的传输能耗。

2 交叉非均匀分簇路由算法

LUCRA算法的整个实现过程包括三个部分:建立网络层次结构、簇形成和多跳传输。

2.1 网络层次结构

假设根据距离基站的远近，整个传感器网络被划分为m个层次。若以基站为原点向外辐射来对各个层次进行统一编号，则最内层为第1层，最外层为第m层。层次数:

式中:dmin——基站距离感知区域的最近距离;

dmax——基站距离感知区域的最远距离。

其中，各个层次的左右边界BLi、BRi分别为

传感器节点部署以后，基站以一定的功率向网络内的所有节点广播网络结构消息。各节点根据接收信号的强度和该消息所包含的各层左右边界信息，确定自身的所属层次，以便竞选簇头和数据传输时使用。

2.2 簇形成

LUCRA算法中，每个节点以一定概率成为候选节点来参与簇头竞选，竞选机制采用非均匀分布的方式进行，同时将节点与基站间的距离和节点的剩余能量作为评价标准。网络采用轮计数方式，每一轮开始时需要重新进行簇头选择。

规则 在簇头竞选过程中，若si当选簇头，则si的竞争半径Rcmp不允许有其他节点再成为簇头。候选节点的竞争半径Rcmp为

式中:dsi，BS——节点 i到基站的距离;

ε1、ε2——(0，1)之间的常数;

R0——系统设置的成簇半径。

从式(5)可见，节点的成簇半径Rcmp随着节点距基站的距离和剩余能量而动态变化，距离基站越近，剩余能量越低，成簇半径越小。

LUCRA算法的整个成簇过程分为6个步骤:

第1步，成簇开始时，节点产生一个0～1的随机数，如果该随机数小于某一值T时，那么该节点成为候选簇头。

第2步，候选簇头根据式(5)计算自身的竞争半径并向竞争半径内所有节点广播竞选信息COMPETE－HEAD－MSG，包括节点的位置、竞争半径和剩余能量。

第3步，若节点i收到节点j的竞选信息，并且两节点之间的距离小于两节点中任意一个的竞争半径，则节点i就将节点j的竞选信息存储到本地的Sct中。

第4步，一段时间后，候选簇头将自身的剩余能量与本地Sct中各竞选信息对应的候选簇头的剩余能量进行比较，如果该候选簇头比本地Sct中任一候选簇头的剩余能量都要大，那么该候选簇头就成为网络的实际簇头，否则竞选失败。然后，成为实际簇头的节点向周围广播竞选结束信息 FINISH－ELECT－MSG。

第5步，收到结束竞选信息的非簇头节点，根据接收到的竞选结束信息的信号强度选择加入最近的簇头。如果某个节点收到多条竞选结束信息，那么它将选择其中信号强度最大的簇头作为自身的主簇头，并选择信号强度次最大的簇头作为自身的次簇头，成为两相邻簇之间的交叉节点。

第6步，以此类推，建立网络簇类结构，如图2所示。

图2 LUCRA成簇结构Fig.2 Clustering structure of LUCRA

2.3 多跳传输

LUCRA算法采用层间多跳通信方式进行数据传递。网络簇类结构建立以后，每一个簇头搜索并在本地保存一个相邻簇头的集合Gch和一个本簇内交叉节点的集合Cnodes。簇内节点将采集的数据直接发送给簇头，上一层簇头再将数据转发给下一层的簇头，直至数据到达基站为止。其中，在簇头间多跳路径构建中，当簇头si选择下一跳路径时，其转发策略如下:①若si位于第1层，那么它就将数据直接发送给基站。②若si位于其他层中，并且si·Gch中存在下一层中的某一个簇头sj使得d2(si，sj)+d2(sj，BS)最小，那么 si将选择sj作为其下一跳路由。③当si选择sj作为下一跳路由时，若d(si，sj)＞DIS－MAX，那么 si搜素 si·Cnodes中是否两者所在簇的交叉节点，如果存在就以该交叉节点为桥梁进行两者的数据转发，若 d(si，sj)＜DIS－MAX，那么 si直接将数据转发给sj。④若si·Gch中没有下一层的簇头，那么si就将数据转发给同层中距离其最近的簇头，否则，直接将数据转发给基站。

2.4 LUCRA算法分析

首先，分析LUCRA算法消息的复杂度。在成簇开始时，有N×T个节点成为候选簇头，需要广播N×T条竞选消息COMPETE－HEAD－MSG。假设其中有K个节点当选实际簇头，又需要广播K条竞选结束消息FINISH－ELECT－MSG。网络成簇过程中总共需要广播的消息开销为N×T+K条，而EEUC算法的消息开销为(2T+1)K条。因此，相对EEUC算法，LUCRA算法的成簇开销比较小。还有一点，EEUC算法需要经过多次消息迭代才能完成簇头的选择，而LUCRA算法并不需要，从而它的收敛速度较快。

其次，与EEUC算法不同，LUCRA算法在竞争半径Rcmp中还考虑了节点的剩余能量。候选簇头的竞争半径由候选簇头与基站间的距离和它的剩余能量来决定。其中参数ε1、ε2决定两者对竞争半径的影响程度，当ε1取值为0时，竞争半径的大小仅由候选簇头的剩余能量决定;当ε2取值为0时，竞争半径的大小仅由候选簇头与基站间的距离决定。对于不同的网络规模，参数ε1、ε2的优化取值也不同。针对文中的仿真规模，经大量的实验发现ε1、ε2分别为0.6和0.4时网络具有良好的性能。

最后，根据式(4)得到LUCRA算法，采用交叉节点作为簇头间数据转发的中介可以在一定程度上减少数据传输的能量损耗。而且，LUCRA算法采用层间数据转发模式，能够极大地简化路径寻址过程。

3 仿真及结果分析

3.1 参数设置

利用MATLAB对LUCRA算法与LEACH和EEUC算法进行仿真比较。假设采用理想的MAC协议，并忽略无线链路中发生的丢包和碰撞错误。仿真参数如表1所示。

表1 网络仿真参数Table 1 Network simulation parameters

3.2 结果分析

从实验数据中随机选取15轮，统计每一轮所有簇头消耗的总能量。图3是三种分簇路由算法在每轮中所有簇头消耗的能量之和。可见，在簇头能量损耗上，LEACH消耗最多、EEUC次之、LUCRA最少。这是因为LUCRA和EEUC算法采用多跳通信的方式，可以有效地节省通信开销，同时，LUCRA对簇间通信进行了改进，还避免了簇间的长距离通信。

图3 每轮所有簇头消耗的总能量Fig.3 Total energy consumption of all cluster heads in each round

图4是网络中存活的节点数目随着时间的变化。在仿真过程中，假定当节点的剩余能量小于0.002 J时，则认定该节点死亡，当网络中有50%的节点死亡，则认定网络生存时间到此结束。很明显，无论是在第一个节点死亡时间上还最后一个节点死亡时间上，LUCRA皆较EEUC和LEACH具有良好的性能表现。

图4 网络生存时间Fig.4 Network lifetime

4 结束语

笔者提出了一种基于分层的非均匀分簇路由算法LUCRA。该算法保留了EEUC算法的优点并对其不足之处进行了改进，在竞争半径的计算中同时考虑节点剩余能量和节点与基站间的距离，使得簇大小可以动态变化。另外，LUCRA算法在簇间通信中引入交叉节点来作为簇头间数据转发的桥梁，有效减少簇头能量损耗。最后，LUCRA算法采用从外层到内层的路由寻址方式，实现过程简单、方便。实验表明，与LEACH、EEUC算法相比，LUCRA有效地均衡了网络的系统能耗，显著提高网络生存时间。

[1]孙利民，李建中，陈 渝.无线传感器网络[M].北京:清华大学出版社，2005:3－96.

[2]NICULESCU D，AMERIC N L.Communication paradigms for sensor networks[J].IEEE Communication Magazine，2005，43(3):116－122.

[3]HEIZELMAN W，CHANDRAKSA A，BALAKRISHNAN H.Energy efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rdHawaii International Conference on System Science.Washington，DC:IEEE Computer Society，2000:3005 －3014.

[4]MARCELLONI F，VECCHIO M.Enabling energy-efficient and lossy-aware data compression in wireless sensor networks by multiobjective evolutionary optimization[J].Information Sciences，2010，180(10):1924－1941.

[5]JUNG J W，INGRAM M A.Residual-energy-activated cooperative transmission to avoid the energy hole[C]//Proceedings of IEEE International Conference on Communications Workshops.Piscataway，NJ:IEEE Press，2010:1 －5.

[6]赵志信，郭继坤，彭 保.基于功率控制的无线传感器网络节点定位算法[J].黑龙江科技学院学报，2012，22(2):168－171.

[7]李成法，陈贵海，吴 杰，等.一种基于非均匀分簇的无线传感器网路路由协议[J].计算机学报，2007，30(1):27－36.

[8]LIAO WENHWA，KAO YUCHENG，WU RUTING.Ant colony optimization based sensor deployment protocol for wireless sensor networks[J].Expert Systems with Applications，2011，38(6):6599－6605.

[9]李志宇，史浩山.一种负载均衡的无线传感器网络自适应分簇算法[J].西北工业大学学报，2009，27(6):822－826.

[10]HE YONGGANG，XU TINGRONG.An improved uneven clustering routing algorithm for sensor networks[C]//The International Symposium on Computer Networks and Multimedia Technology.Piscataway，NJ:IEEE Press，2009:1 －5.

[11]彭 铎，张秋余，贾科军.能量高效地无线传感器网络分簇路由协议[J].计算机工程，2009，35(17):123－125.

[12]JUNG J W，INGRAM M A.Residual energy activated cooperative transmission to avoid the energy hole[C]//Proceedings of IEEE International Conference on Communications Workshops.Piscataway，NJ:IEEE Press，2010:1 －5.

[13]曾至文，陈志刚，刘安丰.无线传感器网络中基于可调发射功率的能量空洞避免[J].计算机学报，2010，33(1):13－14.