基于多路径的非均匀分簇路由协议

徐万一， 王 军， 张亚君， 马德朋

(沈阳化工大学 计算机科学与技术学院， 辽宁 沈阳 110142)

无线传感器网络WSN(Wireless Sensor Network)是由大量的无线传感器节点构成的、利用无线通信方式组成的一个多跳自组织网络系统[1-3].它能够实时监测、采集所处环境中的对象信息，并对其进行量化、融合等处理，把处理后的信息通过无线方式发送给基站.WSN综合了无线网络技术、分布式技术和传感器技术，是一种新型的信息采集和信息处理技术.

随着无线传感器网络的广泛应用[4]，对无线传感器网络的研究也成为了国内外研究的一个热点.在国际上，美国自然科学基金会开设了相关项目对其进行研究；同时国内的清华大学、哈尔滨理工大学也开展了对WSN的研究工作.对无线传感器网络能耗的研究是无线传感器网络研究的热点之一.

在传统网络的路由机制中，源节点选择距离目的节点最短的符合条件的路径来传输数据.在无线传感器网络中如果采用传统网络的路由机制频繁使用同一条路径来传输数据，由于节点能量等资源的限制，该路径上的节点就会因过度耗能而提前死亡，缩短网络的生存周期.由文献[5]可知：采用非均匀分簇的路由机制可以有效地节约单个节点的能量，延长网络生存周期.在源节点与目的节点采用多路径路由机制将使数据传输所消耗的能量均衡地分配到整个网络.

本文以节约能耗、增加网络有效运行时间为目标，综合考虑数据传输效率和路径的可用性，提出一种改进的基于多路径的非均匀分簇路由协议[6](MEEUC协议)，该协议综合了多路径和分簇路由协议的优点，具有更好的性能.

1 相关研究

1.1 EEUC

EEUC协议是一种非均匀分簇的无线传感器网络路由协议[7],采用的是EEUC路由算法.该算法是分布式的竞争算法，通过定义节点的竞争半径R，使距离Sink节点近的簇半径较小，距Sink节点远的簇半径较大，半径较小的簇其成员节点就较少，簇头节点就可以把能量用于数据转发.EEUC协议与LEACH协议[8]相比，EEUC协议在平衡簇首节点的能量消耗方面做得更好，延长了网络的生存周期.

EEUC协议簇首的选举分为两个阶段：候选簇首产生阶段和最终簇首产生阶段.候选簇首阶段，传感器节点用自身产生的0到1之间的随机数μ与预先设定的阈值相比较，若μ较小，则节点当选为候选簇首，参与竞选最终簇首[9].在最终簇首产生的过程中，候选簇首利用自身到汇聚节点的距离建立一个以自身为中心的控制范围，其半径为R，假设ni为一个节点，则其竞争半径为：

(1)

式1中:dmax是节点到汇聚节点的最大距离;dmin是最小距离；DS为汇聚节点；d(ni,DS)为节点ni到汇聚节点的距离；R0表示候选簇首的最大竞争半径;c为用于控制节点半径取值范围的参数[8].

候选簇首根据竞争半径建立邻候选簇首集，然后剩余能量高的成功当选为最终簇首，其他候选簇首节点成为普通节点.最终簇首产生后，普通节点会选择最近的簇首加入，完成簇的形成阶段.当进行数据传输时，EEUC协议把通信过程分为两步：簇内通信与簇间通信.簇内由于节点间距离较近，采用单跳通信的方式；而簇间通信为了节省网络能耗采用多跳的通信方式[10].

1.2 问题描述

EEUC协议需要计算所有传感器节点到基站的距离，从中找出最近距离与最远距离，以计算各个节点的竞争半径.若距离基站最近或最远的节点出现问题，则需要重新确定最近或最远距离，各节点重新计算其竞争半径，并告诉其他节点，这种方法增加了节点的能耗，也增加了网络通信量.

EEUC在选择候选簇首时，以预先设定好的概率参加竞选，这样会导致当选簇首的节点不够均衡，有些节点的能量可能不足.在选取下一跳节点时，只考虑了节点的能量，没有考虑节点间的距离[11]，会导致数据传输路径的距离过长，增加节点的能耗.

EEUC采用单路径进行数据的传输，会使节点能耗分布不均衡，传输可靠性低.路由更新策略为经过一定的轮次后进行更新，这种更新策略灵活性不好，开销比较大.

综上所述，EEUC协议还存在问题，需要继续进行改进，使无线传感器网络更有效率.

2 MEEUC路由协议

2.1 MEEUC协议的网络环境

考虑一个由N个传感器节点随机均匀分布的网络，其应用场景为需要大量快速的转发数据.传感器节点的传输范围、初始能量、数据处理能力与无线通信能力都相同，每个节点都有一个唯一标识能进行数据融合，并且能在通信过程中确定彼此的相对位置.传感器节点均可以计算自己的剩余能量、可用的存储空间、与相邻节点的距离.

2.2 MEEUC协议的改进思想

MEEUC(Multipath-EEUC)协议是在EEUC协议的基础上进行了改进，主要是改进簇头竞争半径的计算方法和以可靠性评估参数为依据在源节点与目的节点间建立多条路径[12]进行数据传输.相对于传统的EEUC协议采用的单路径路由，其传输可靠性高，节点能耗更加均衡.可靠性评估参数综合考虑了可用缓存大小、剩余能量[13]、信道质量、节点距离等信息，对节点的资源状况全面进行分析，解决了选取下一跳节点时没有考虑节点距离的问题，避免了节点的过早死亡，延长了网络生存周期.可靠性评估参数的计算方法如下：na表示节点a所有邻节点的集合，表1为节点的各个参数：

表1 节点状态参数

如果b节点想要成为a节点的下一跳节点，则其可靠性评估参数为：

Ra,b=maxb∈na{w0Eb+w1Bb+w2Qab+

(2)

式(2)中:Ra，b是节点a与节点b的可靠性评估参数;Eb、Bb、Qab、Nb、Dab分别为节点b的剩余能量、节点b的可用缓存大小、节点a与节点b的信道质量、节点b的簇内成员数目、节点a与b之间的距离.用节点的状态信息计算出单节点的可靠性评估值.在考虑节点剩余能量时，只考虑将要参加下一跳路由竞选的节点.可靠性评估值将作为节点选取下一跳路由节点时的依据.

若源节点s到目标节点d一共由X个节点组成一条路径P，则该路径的可靠性评估值为：

(3)

式(3)中:源节点s到目标节点d一共X个节点，l个可靠性评估参数；RP表示P路径的可靠性评估参数；(i,j)表示路径中任意相邻的两个节点；j∈ni表示节点j为节点i的相邻节点；R(i,j)l表示路径中相邻两节点的可靠性评估参数.随着网络节点不断传输数据，节点的状态发生改变，可靠性评估值也会变化.当网络结构发生变化时将重新计算路径的可靠性评估参数.

2.3 改进的MEEUC协议算法描述

2.3.1 簇头竞争半径的计算规则

改进后的MEEUC协议，节点计算其竞争半径时,不依赖节点到汇聚节点的最近和最远距离.由于节点的部署区域是固定的，并且节点的竞争半径与所处的区域关系密切，因此,MEEUC协议采用下面公式计算节点的竞争半径：

(4)

式(4)中:d为汇聚节点到节点部署区域的最远距离；d(ni,DS)为节点到汇聚节点的距离；Xm、Ym表示节点在部署区域的横坐标与纵坐标；R0表示最大竞争半径的取值；c是用于控制节点半径取值范围的参数.采用这种计算方式，形成大小非均匀的竞争范围，形成非均匀分簇[14]，这样靠近汇聚节点的候选簇首竞争半径较小，会将更多能量用在簇间通信，降低了最近或最远节点发生变化时重新计算节点竞争半径所消耗的能量.

2.3.2 路径查找规则

无线传感器网络中的节点收集其可控范围内节点的信息，源节点根据这些信息选择、创建到达最终节点的路径.多条路径可以共用一个节点，即除了起始节点和结束节点外，存在相重合的节点.MEEUC协议中这种共享节点经过计算可以为多条路径的数据传输提供能量，节点不会因能耗增加而在极短的时间内死亡.这种节点相交的多路径占用的网络资源少，合理利用了网络资源，平衡了网络的能耗，充分利用了节点的能量.有研究表明能量优化的节点相交路径的路由性能好于传统多路径路由[15].

MEEUC协议采用的是节点相交的多路径，该协议创建从源节点到目的节点3条路径，即主路径和2条次要路径，3条路径同时进行数据的传输.路径创建过程采用的算法类似于启发式搜索，先对要搜索的位置进行评估，从而得到最好的位置，再从这个位置进行搜索,直到到达目标.这样就可以节省大量无畏路径的搜索，极大提高了搜索效率.MEEUC协议用可靠性评估值对位置进行评估.

节点搜索过程的伪代码如下：

选取节点n为源节点；

while(Neighbor！=NULL)

{if(n节点==目标节点){

break;}

for(当前节点n的每个子节点X)

{计算X的可靠性评估值;

if(X节点没有达到饱和状态){

{

if(X的可靠性评估值是最大的){

把X设置为n的下一跳节点;

更新节点自身的标记值;}

}

}

if(X节点已经达到饱和状态){

拒绝其余节点发送的消息;}

}

“新的“两委”班子成员到位以后，我们作为前任领导，从工作上从思想上多方面地给予帮助，年轻人学习也快，进入角色转变角色都非常快，现在都能正常地开展工作了。”一〇四团西城西社区原负责人刘军欣慰地说。□

}

在路径查找时，可靠性评估值R最大的节点将会作为下一跳节点的最佳选择，普通节点会向此节点发出其成为路由请求消息.在这个路由请求消息中包含的信息有源节点和目的节点的地址、与此节点的距离、中间信道的质量、路由请求消息的有效时长、路径的标识信息[16].节点收到路由请求消息，如果符合条件,接受路由请求，并返回一个确认消息，确认消息中包含此节点的地址、节点的状态信息和路径可靠性评估.

节点转发路由消息的条件：

(a) 当节点比发送消息的邻节点距离源节点更远、距离目的节点更近时才转发路由请求信息，否则会丢弃此路由请求信息；

(b) 当节点状态已经达到饱和状态后进入封闭状态，抛弃其余节点发来的路由请求消息.

条件(a)保证在路径可靠性基础上下一跳向目的节点方向收敛，条件(b)保证节点不会过早死亡[17].传感器网络用可靠性评估值R来选取下一跳路由节点，可靠性评估值越大，其当选下一跳节点的优先级越高.以此类推，如果优先级最大的节点不能满足路由消息转发的条件，将按照优先级依次往下筛选，直至有符合条件的节点加入路径.

每个节点都有一个using状态值，其作用是记录加入的路径数，满足条件的下一跳节点会将其 using值加1，记录本节点已经加入的路径.然后节点计算其自身剩余能量[18]，当剩余能量大于节点总能量的60 %时，继续接受其他节点发来的路由请求信息，直至低于60 %时，节点不再接收路由请求消息，节点将其using值变为100，表示节点达到饱和状态，同时向其余节点发送广播信息，表明自己拒绝接收路由请求信息.节点按照这种策略进行下一跳路由节点的选取，直至路由请求消息达到目的节点.当同时有多个节点的R值满足条件时，节点根据收集到的信息优先选取using值为0的节点作为下一跳节点，using 值越小优先级越高，当出现多个节点using值相同时，选取R值较大的作为下一跳节点.

2.3.3 路径查找过程

(1) 初始化

节点向邻节点发送一条初始化的广播消息，当相邻节点收到消息后建立并维护一张Neighbor表，该表记录了邻节点的ID和相关参数及度量值.初始化消息中包含的内容有源节点的ID、可用缓存大小、剩余能量、信道质量、与此节点的距离.

(2) 主路径发现

当初始化工作完成后，源节点根据自身的Neighbor表，用可靠性评估值计算首选的下一跳节点，并向其发送路由请求消息，按照MEEUC协议的规则进行选择，如此循环直到下一跳节点为目的节点，具体过程如图1所示.此时，目的节点向源节点发送一个路径确认消息，源节点收到此消息后更新自己与目的节点的路由表，至此，主路径创建完成.

图1 路径发现过程

(3) 次要路径发现

从源节点到目的节点建立的第一条路径为主路径.当主路径的信息更新完毕后，源节点继续建立符合条件的次要路径.以图1为例，主路径1-2-3-4-5已经创建完毕，当创建次要路径时，节点7向节点6发送路由请求信息，但是节点6距离目的节点更近，不满足转发路由消息的条件，所以节点6向节点7返回拒绝消息.然后节点7根据收集到的信息再向节点2发送路由请求信息，但此时如果节点2达到饱和状态，using值变为100，节点2不满足转发路由消息的条件，就会把节点7的路由请求消息丢弃，并且返回一个拒绝消息说明此节点已饱和.节点7收到拒绝消息后在自己的Neighbor表中将节点2标记，然后继续选择下一节点.节点7向节点8发送路由请求消息，此时节点8符合成为下一跳路由节点的要求，接收此路由请求并返回确认消息，至此下一跳节点选择完成.节点8继续选择下一跳路由节点，假如此时节点4和节点9的可靠性评估值相同并且都符合转发路由消息的条件，节点8会根据using值进行选择，节点4的using值为1，节点9的using值为0，最终节点8选取节点9为下一跳节点.如此重复直到路由请求消息到达目的节点，目的节点返回最终确认消息.至此，从源节点到目的节点的次要路径发现完毕.重复以上过程直到发现所有的次要可用路径.

2.3.4 路径选择阶段

当路径创建完毕后，簇首节点计算每条路径的性能，从所有可用次要路径中选出2条，同主路径一同传输数据.

Mi=C1×Rmin(i)+C2×Ri

(5)

式(5)中:Mi表示路径的性能；C1、C2为权重值，C1=0.6,C2=0.4;Ri为路径的可靠性评估参数;Rmin为可用路径中可靠性评估参数最小的值.令Pi为第i条路径的传输概率，则：

(6)

簇首节点根据路径的传输概率动态选择两条概率大的路径同主路径一同进行数据传输.通信数据分时隙沿3条路径进行传输，每条路径传输的数据是不同的，实现了网络的负载平衡，减少了端对端的延迟，增加了其容错性.

2.3.5 路由更新

MEEUC协议采用按接收数据包的大小更新路由.首先设置一个传输数据量阀值T(kb)，目的节点记录已经传输的数据的量，其初始状态为0，当传输的数据量的大小超过阀值T时，记录重置,撤销创建的路径，此路径的节点的标记量using值重置为0，进行下一轮的路径选择.

这种根据传输数据量设定的路由更新策略能更好地适应网络的变化.与传统的路由更新策略相比较，这种把已经传输数据量的大小作为更新路由频率依据的策略能更好地减少能量损耗，延长网络生存周期.

2.4 改进的MEEUC协议分析

与EEUC协议相比较，经过改进的MEEUC协议综合考虑了节点的资源状况，增加了可靠性评估参数，避免了传输路径过长的情况.EEUC协议需要先计算节点距汇聚节点的最近和最远距离，再计算节点竞争半径，并且当节点发生变化时需要重新计算节点的竞争半径；MEEUC无需考虑节点到汇聚节点的最近或最远距离，采用节点在部署区域中的坐标来计算竞争半径，降低了能量的消耗.EEUC采用单路径路由进行数据传输，MEEUC协议根据可靠性评估参数建立多条路径传输数据，平衡了节点能耗[18]，增加了传输可靠性.EEUC协议采用周期性进行路由更新的方式，MEEUC协议考虑了发送数据量的大小，按数据量的大小进行路由的更新.

3 仿真实验结果与分析

使用NS-2进行仿真实验.实验中统计传感器节点接收、发送控制包与数据包，融合数据损耗的能量.使用以下参数进行仿真实验：节点总数为400，网络区域面积200 m×200 m，目的节点和源节点分别位于网络区域的对角线两端.假设实验区域内节点的发送功率为15mW，为了模拟快速大量转发数据的环境，数据发送速率由标准的10 kb/s提高到20 kb/s，自身所含初始能量为2 J，有效传输距离为25 m，数据包长度为3 000 bit，控制包为200 bit，w0∶w1∶w2∶w3∶w4=3∶2∶3∶2∶2，实验中采用理想无衰落信道，忽略无线通信模块能量损耗.

图2是LEACH、EEUC与MEEUC三种协议簇首损耗的总能量随轮次的变化情况，数据范围选取其前20轮中簇首损耗总能量.从图2中可以看出：MEEUC协议中簇头能量消耗随轮数的增加保持比较平稳的趋势，能耗量也低于另外两种协议.

图2 每轮中簇头损耗的能量

图3中表示了网络中存活节点数量随轮数的变化情况.从图3中可以看出：LEACH协议的第一个节点最早死亡，EEUC次之，网络中一半节点的死亡轮次LEACH最早，EEUC次之，在这两方面MEEUC都有优势.可以看出MEEUC协议使网络中节点的能量消耗更加均衡，避免了节点的过早死亡，增加了传感器网络的有效存活时间，很大程度上提高了网络的稳定性.

图3 不同协议的网络节点存活数目对比

图4表示了1 000轮中节点平均剩余能量的变化.从图4中可以看出：MEEUC协议中节点平均剩余能量的变化幅度较小，变化率较低，节点的生存时间较长，表明其能量消耗很均衡，在单位能量下能够获得更长的有效存活时间.

图4 不同协议的节点剩余能量对比

网络的传输延迟是指数据包从网络的源目标到目的目标所需的时间.图5为3种协议的平均端对端延迟变化情况.从图5中可以看出：MEEUC协议的曲线变化幅度较小，平均延迟低，说明MEEUC协议有效地降低了网络的延迟时间和阻塞，提高了网络的性能.在相同的时间和能量下可以传输更多的数据，提高了能量的利用率.

图5 不同协议的传输延迟对比

4 结束语

增加网络节点生存时间，均衡网络节点的能耗，延长网络寿命是无线传感器网络路由协议设计非常重要的目标.本文通过分析研究已有的路由协议，在其基础上提出了一种改进的基于多路径的路由协议.该协议对节点的剩余缓存大小、剩余能量、邻节点簇内成员数量等状态信息进行综合考虑，通过优化传输路径来平衡网络节点的能量损耗.仿真实验结果表明:该协议更好地平衡了网络中所有节点的能量消耗，充分利用有限资源，延长了无线传感器网络的生存周期.