基于路径质量的无线传感网路由协议

龚本灿，周 峰，陈 鹏，任 东

1.三峡大学 计算机与信息学院，湖北 宜昌443002

2.三峡大学 湖北省农田环境监测工程技术研究中心，湖北 宜昌443002

1 引言

无线传感网WSN（Wireless Sensor Networks）广泛应用于环境监测、军事侦察、医疗监护、空间探索、抢险救灾等多种领域，具有重要的科研价值和广阔的应用前景。目前，WSN 的研究主要集中在MAC 层、网络层和传输层，以及各层之间的跨层交互。网络层负责将传感器节点采集的数据逐跳转发至Sink，其性能至关重要，是WSN 的研究热点。资源的局限性给WSN 路由协议的设计带来了巨大的挑战，和传统路由协议相比，WSN路由协议更加关注能量的使用效率和数据传输的可靠性[1]。基于最小跳数的路由协议实现简单，每次都采用从当前节点到Sink 的最大距离进行数据传输，网络延迟少，因而得到了广泛的应用[2]。目前国内外研究人员提出了许多基于跳数的路由协议及其改进算法。

最早的基于跳数的多路径路由协议[3]是在定向扩散协议和洪泛协议的基础上，引入了跳数的概念，以当前节点到达Sink 的跳数作为路由的依据，在一定程度上缓解了洪泛协议的内爆和重叠问题，极大地减少了数据包的传输量和网络的能耗，因其新颖的设计思想而备受关注。文献[4]提出了一种基于跳数的多路径环路由协议（Multipath Ring Routing），其路由形成机制如下：网络部署完毕后，Sink 广播拓扑发现分组，分组中携带了从当前节点到Sink 的跳数（初值为0），收到拓扑发现分组的节点将跳数加1，如果该分组的跳数比节点的当前值更小，则更新节点的跳数，并再次广播，当拓扑发现分组传遍整个网络时，每个节点就都找到了自己到达Sink的最小跳数。数据传输时，节点采用定向广播的方式发送分组，分组中携带了节点的跳数，所有邻节点收到分组后，如果其跳数更小，则再次广播，直到Sink。由于在数据传输过程中所有跳数更小的邻节点都将转发数据，造成转发节点的数量过多，加剧了网络的能量消耗。文献[5]提出了一种基于跳数梯度场的路由协议，源节点产生的消息中携带了梯度值及其邻节点的最小剩余能量，邻节点可根据这些信息判断是否转发该消息，从而控制了转发节点的数量，有效避开了剩余能量过低的节点，该协议能延长网络的寿命，但消息的洪泛仍会造成过多的能耗。文献[6]提出了一种具有可靠性感知能力的自适应多径路由协议，根据网络的可靠性要求和路径权重，适当地选取部分路径进行传输，以此来满足预定的网络可靠性，在网络可靠性、网络开销、传输时延等方面，该路由协议的性能都有明显提升。但是Sink 需要获取网络中所有链路、路径和传感器的状态信息，并由Sink 集中进行路由决策，路由决策信息的收集和扩散会带来开销，不适合分布式网络环境。

前述几种基于跳数的路由协议由于采用多路径传输，虽然提高了传输的可靠性，但将带来较高的能耗，这对能量受限的传感网来说是一个较大的制约因素。为了节省能量，一个有效的方法是采用单路径传输。文献[7]提出了基于最小跳数的传感网路由协议，在路由控制包中包含了节点ID、剩余能量和到Sink 的跳数，节点根据这些信息来建立路由表，路由表中记录了所有的父节点（比自己的跳数小1）、兄弟节点（与自己的跳数相等）、子节点（比自己的跳数大1）及这些节点的ID 和剩余能量，数据转发时节点优先从其父节点中选择一个剩余能量最大的节点转发。协议提供了多条后备路径，具有较强的健壮性，但没有考虑与父节点间的通信距离，且缺乏保证数据传输可靠性的机制。文献[8]对最小跳数路由算法的组网和数据传播阶段进行了改进，节点主动发送Join报文来加入网络，解决了节点实时加入网络的问题，为了节省能量，节点每次只选择一个父节点转发报文，父节点对每个收到的报文都进行确认，但协议没有考虑通信链路的质量，可能引发多次重传，增加网络的能耗。文献[9]提出了一种高效的基于跳数的移动Ad Hoc 网络路由查找算法，它是一种在传输功率和跳数之间进行折衷的自适应路由协议，它假定网络节点都具有不同的发射功率，当节点收到源节点广播的路径查找消息时，该节点将其功率与预设的阈值功率进行比较，如果大于阈值功率，则选择跳数最少的路径，否则，选择跳数更大的路径。所提出的协议能够减少能量消耗和端到端的延迟，但该协议假定节点都具有不同的发射功率，并且路由的建立是按需驱动的，不适合需要周期性采集传感数据的场合。文献[10]从理论上分析了在无线多跳网络中跳数对网络稳定性和路径可靠性的影响。

基于跳数的单路径路由协议虽然比多路径路由协议节省了能量，但由于节点总是选择跳数最少的路径传输数据，造成节点传输的距离远，网络的丢包率很高。研究表明在路由建立的过程中如果考虑节点间的链路质量，将能有效地提高网络的包投递率。文献[11]提出了一种改进的基于跳数的无线传感器网络路由算法（R-MHC），对最小跳数路由算法的组网和数据传播阶段进行了改进。源节点优先选取跳数最小的父节点作为转发节点，如果多个邻节点跳数相同，则综合考虑邻节点的剩余能量、链路状态和接收信号强度，并通过权值公式选取权值最大的父节点作为最优转发节点，改进后的算法在可靠性、负载均衡、网络寿命和路由开销等方面具有一定的优势。但算法优先选取跳数最小的父节点作为转发节点，如果当前节点与父节点之间的链路质量较差，则仍会带来较高的丢包率。文献[12]提出了一种具有链路质量感知能力的基于队列的路由协议（LRP），在稀疏和密集部署的传感器网络中，LRP 能够避免路径环路和分组丢失，提高了数据的传递率，但是缺乏对数据延迟的控制，不适用于实时性网络。文献[13]提出了一种链路质量和能量感知的路由协议（LQEAR），它根据链路质量、节点的剩余能量、转发节点与Sink 之间的距离来选择下一跳节点，LQEAR 能够提供更高的传输可靠性，并能有效地平衡节点的能量消耗，该协议要求每个节点能够准确获得自己的位置信息以便计算节点间的距离，它只适合于节点具备定位功能的传感网场合。文献[14]提出了一种应用链路质量和节点的能量状态进行路由发现的LE-AODV 路由协议，有效地提高了包投递率和网络的生存时间，但该协议是针对移动自组网设计的，不太适合以数据为中心的传感网。文献[15]提出了一种基于压力传感器的可靠路由协议（PSBR），它依靠链路质量估计器、节点深度及节点的剩余能量来选择数据转发节点，达到了很高的数据传输效率。文献[16]针对水声传感器网络提出了一种可靠、节能的路由协议（RRP），它融合了基于方向的洪泛路由和基于矢量的避障协议的特点，通过逐跳测量节点之间的链路质量来控制转发数据包的节点数量以提高可靠性，PSBR 和RRP 协议仅适合于水声传感网。文献[17]提出了一种基于链路质量的能量高效的分布式路由协议（EEDR），它具有较小的跳数、较低的时延和较高的吞吐量，但它仅考虑了与邻节点的链路质量，不能保证整条路径所有链路的综合质量最优。

以上路由协议在一定程度上提高了网络分组的投递率，减少了网络的能耗，但这些方法都只基于本节点及邻节点的局部信息进行路由决策，容易限入局部最优，为了解决这一问题，本文提出了一种基于路径质量的无线传感网路由协议，以路径质量（包括跳数、综合链路质量和节点能量）作为网络路由选择的标准，各节点能够根据路由发现分组中包含的路径质量信息选择一条到达Sink 的最佳路径，进一步改进网络的性能，达到全局最优。

2 网络模型与问题描述

2.1 网络模型

定义1一个无线传感网可表示为一个加权图G=(V,E,W)，其中，V 表示由传感器节点组成的集合，V={v1,v2,…,vn},E 表示由通信链路组成的集合，E={e1,e2,…,en},W 是由节点之间的链路质量组成的集合，W={w1,w2,…,wn}。

定义2链路质量指示LQI（Link Quality Indicator），用于表示接收到的帧的质量，其值可根据物理层所接收到的无线信号强度RSSI（Received Signal Strength Indi‐cator）计算出来，计算公式如下：

定义3设p(s,d)表示从源节点s到目的节点d 的路径，其中，s,d ∈V，则综合链路质量GLQI（Global Link Quality Indicator）的定义如下：

LQI仅反映了两个相邻节点间的链路质量信息，而GLQI 反映了从Sink 到当前节点的所有链路的质量信息，其值越大，则路径的质量越高。

定义4路径包投递率PPDR（Path Packet Delivery Rate）的定义如下：

其中，packet_loss(e)为路径中每条链路的丢包率。

定义5假设网络的节点数为n，节点i 所消耗的能量为E(i),Sink 收到的数据包的个数为N，则平均包能耗APEC（Average Packet Energy Consumption）的计算公式如下：

APEC 表示了Sink 每收到一个数据包所消耗的网络能量。

本文采用的网络模型如下：n个传感器节点随机分布在一个正方形区域内，周期性地收集周围的环境信息上传给Sink，并且具有如下性质：

（1）所有传感器节点部署后不再移动，Sink唯一。

（2）所有节点没有安装GPS，不知道其具体位置。

（3）所有节点能够根据接收到的无线信号强度计算出链路质量LQI。

2.2 问题描述

在无线通信中，发射功率的大小、通信距离的远近和外界噪声干扰的强弱是影响丢包率的主要因素，接收方可以根据物理层所接收到的无线信号强度，按照公式（1）计算出当前链路的质量信息。当发射功率和噪声干扰相同时，链路质量间接反映了节点间的通信距离。

以图1 为例说明基于链路质量的最小跳数路由算法存在的问题，以及本文提出的基于路径质量的路由算法PQR 的设计思想。图1 显示了网络节点的分布情况及每条链路的丢包率和LQI值。例如，从Sink 到节点1的丢包率为40%，链路质量为7。

图1 路径选择示意图

在路由建立阶段，Sink 节点广播路由发现分组，路由发现分组分别沿路径1（Sink→节点1→节点2→节点3→节点S）和路径2（Sink→节点4→节点5→节点6→节点S）到达节点S。节点S 是选择路径1 还是路径2 作为数据转发路径需要由路由算法来决定。

如果采用基于链路质量的最小跳数路由算法，由于路径1 和路径2 的跳数相等，都是4 跳，因此，将根据链路质量来选择路径。对于路径1，节点S 到邻节点3 的链路质量为10。对于路径2，节点S 到邻节点6 的链路质量为8。因为路径1的链路质量高于路径2，所以节点S 会选择路径1 来传输数据。但事实上，如果以包投递率作为路径优劣的评价标准，则路径2 要优于路径1。具体计算如下：

根据公式（3），路径1的包投递率=（1-40%）×（1-10%）×（1-10%）×（1-10%）=43.74%。路径2 的包投递率=（1-30%）×（1-10%）×（1-10%）×（1-10%）=51.03%。可见路径2 优于路径1。基于链路质量的最小跳数路由算法只考虑了当前节点到邻节点的单段链路的质量，而没有考虑路径上其他链路的质量，所以选出的路径不一定是最优的。

如果采用本文提出的基于路径质量的路由算法，在跳数相等的情况下，节点S 将根据公式（2）计算出的综合链路质量GLQI来选择路径。路径1的综合链路质量为7，路径2 的综合链路质量为8。因为路径2 的综合链路质量高于路径1，因此，节点S 会选择路径2 来传输数据。

从以上分析可以看出：基于链路质量的路由算法缺乏全局意识，而基于路径质量的路由算法全面考虑了从Sink 到当前节点的所有链路的质量信息，因此，能够筛选出全局最优的路径，能更有效地提高网络的包投递率。

3 PQR路由协议的设计

3.1 分组格式

为了获取当前节点到Sink 的路径质量信息，并控制数据分组的传输，需要定义如表1 和表2 所示的网络分组格式。

表1 路由发现分组的格式

表2 网络数据分组的格式

3.2 路由建立阶段

PQR分路由建立和数据传输两个阶段，PQR的路由建立过程如图2所示。

图2 PQR的路由建立过程

网络启动后，Sink 广播路由发现分组，对于收到路由发现分组的每一个节点，取出包首部的Hops、GLQI、Energy、SenderID、SinkID 等参数，将Hops 加1 得到新的跳数newHops；根据接收信号强度按公式（1）计算出链路质量LQI，并按公式（2）计算出新的综合链路质量newGLQI；然后将newHops、newGLQI 和Energy 与节点当前保存的currentHops 和currentGLQI 和currentEnergy进行比较，如果其值更优，则更新路径质量信息，并将SenderID 记录为父节点，表示该节点已加入网络；最后根据新的路径质量信息修改分组的首部，并重新广播路由发现分组。

新的路径质量是否优于节点的当前值的判断原则是：邻节点的剩余能量要高于门槛值（初始能量的30%），并且跳数和综合链路质量满足以下规则之一：

规则1(isConnected=false)&&(LQI ＞=ThresholdLQI)

规则2(currentHops ＞newHops)&&(newGLQI ＞=currentGLQI||newGLQI ＞=GoodLQI)

规则3(currentHops=newHops)&&(newGLQI ＞currentGLQI)

规则4(currentHops=newHops-1)&&(currentGLQI ＜GoodLQI)(newGLQIcurrentGLQI ＞=GoodLQI-ThresholdLQI)

其中，ThresholdLQI 和GoodLQI 是两个实验参数，前者是链路质量的门槛值，用于淘汰质量太差的链路，后者是丢包率低于10%时的链路质量值，表示链路质量很好。

规则1 表示：如果节点尚未加入网络，且链路质量不是太差，则加入网络。

规则2 表示：新的路径跳数更少，且综合链路质量更优或很好。

规则3 表示：新的路径和当前路径跳数相等，且综合链路质量更优。

规则4 表示：新的路径比当前路径跳数更大，但当前路径的综合链路质量不高，且新路径的综合链路质量远优于当前路径的值。

3.3 数据传输阶段

路由建立阶段结束后，网络进入数据传输阶段，此时如果网络层收到应用层传来的传感器节点采集的数据，则将数据加入发送缓冲队列中，等待发送。如果网络层收到MAC 层传来的数据分组，则先判断自己是否为该分组的接收方，如果是，则接收。再进一步判断，如果自己是Sink，则表明数据已到达目的地，将数据上交应用层处理，否则，将转发该分组。PQR 数据传输的伪代码如下：

FOR each node DO

IF 收到传感器采集的数据THEN

SeqNum++//包序号加1

将数据封装成分组，并加入发送缓冲队列TXBuffer

ENDIF

IF MAC层收到数据分组THEN

取出包中的下一跳地址NextHop

IF(NextHop=self)THEN//self 表示自己的地址

IF(self=sin kID)THEN

将分组上交应用层

ELSE//转发分组

修改分组首部的信息(SenderID、NextHop)

将分组加入发送缓冲队列

ENDIF

ENDIF

ENDIF

IF isConnected THEN//节点已加入网络

WHILE(!TXBuffer.empty())DO//发送缓冲队列非空

读取发送缓冲队列的首元素，并发送

TXBuffer.pop()//删除发送缓冲队列的首元素

ENDWHILE

ENDIF

ENDFOR

4 仿真实验

仿真实验采用的操作系统为Ubuntu 14.04，网络仿真软件为OMNET++4.6[18]。将本文提出的基于路径质量的路由协议PQR和基于链路质量的路由协议EEDR[17]进行了对比实验，实验参数如表3 所示。区域面积从100 m×100 m 到300 m×300 m，每次增加20 m，共11 种区域。对每一区域面积重复实验10 次，取平均值，每次实验采用不同的随机数种子来生成节点的随机分布图。

当区域面积为180 m×180 m 时，随机生成的网络节点分布图如图3 所示，PQR 所生成的网络结构图如图4所示。可以看出网络结构图较为合理，绝大多数节点都找到了到达基站的跳数较少且链路质量较高的最优路径，但也有个别节点的路径不是最优，原因在于：在路由建立阶段，基站广播路由发现分组时存在丢包现象，如果从最优路径传来的路由发现分组丢失，则节点将选择次优路径进行数据传输。

表3 仿真实验参数

图3 随机生成的网络节点分布图

图4 PQR所生成的网络结构图

网络的包投递率对比图如图5 所示。可以看出：对于不同的区域面积，PQR 的包投递率都高于EEDR，当区域面积小于等于220 m×220 m 时，PQR 的包投递率高于80%，随着网络区域面积的继续增大，两种协议的包投递率都迅速下降。包投递率下降的原因在于：当区域面积增大时，节点间的距离也相应增加，造成丢包率增加。另外，当区域面积等于100 m×100 m 时，网络的包投递率并非取得最大值，因为当区域面积太小时，节点间相距较近，通信干扰较大，所以造成网络容易丢包。总体来看，PQR比EEDR的平均包投递率高9.3%。

图5 网络的包投递率对比图

根据公式（4）计算出网络的平均包能耗，两种协议的对比图如图6 所示。可以看出：对于不同的区域面积，PQR 的包能耗都低于EEDR，当区域面积小于等于260 m×260 m 时，两种协议的包能耗都随着区域面积的增加而增大，当区域面积继续增大时，包能耗反而下降。因为当区域面积过大时，节点的分布将非常稀疏，造成部分远离Sink 的节点无法接入到网络中，这样只有离Sink 较近的节点能够接入网络，并发送数据，而离Sink较近的节点产生的数据包，转发次数少，因此，包能耗会下降。总体来看，PQR比EEDR的平均包能耗低5.2%。

图6 平均包能耗对比图

5 结束语

本文提出了一种基于路径质量的无线传感网路由协议，在路由发现过程中，节点能够根据路由控制包中所携带的路径质量信息（包括跳数、综合链路质量和节点能量）选出一条质量最好的路径，从而提高了网络的包投递率，降低了网络的能耗。仿真实验结果表明：PQR 比EEDR 的平均包投递率高9.3%，比EEDR 的平均包能耗低5.2%。