WSN中基于排序转发列表的机会路由协议

刘友武，王 晶，刘持标，3

(1.三明学院 现代教育技术中心, 福建 三明 365004; 2.三明学院 信息工程学院， 福建 三明 365004;3.福建省农业物联网应用重点实验室， 福建 三明 365004)

无线传感器网络因其低成本、可快速部署等优点正逐渐成为一种新的有吸引力的通信模式[1]。在大多数传感器网络中，降低能耗是主要的挑战[2]。通常，传感器网络被设计成长时间无人看管模式，因此必须节省电池充电，以延长每个传感器和整个传感器网络的寿命[3]。当路由协议应用于传感器网络时，应始终考虑协议对传感器寿命的影响，能量效率是无线传感器网络路由协议设计的主要考虑因素之一[4-5]。目前，越来越多的WNS协议在设计时考虑能量效率问题，如异构无线传感器网络的节能数据收集协议[6]，能量有效的无线传感器网络无标度拓扑模型[7]等。

对于无线传感器网络节能路由协议已经进行了大量研究。文献[8]提出一种具有移动sink的无线传感器网络的节能ring路由协议，减少了移动sink的位置通告给网络在能量消耗和分组延迟方面引入的开销。文献[9]提出了基于PSO的路由和用于无线传感器网络的聚类，PSO路由建立了传输距离和跳数之间的权衡，聚类算法平衡了CH的能量消耗，在网络寿命和能耗方面具有优越性。文献[10]提出一种基于非均匀分簇的无线传感器网络路由协议，通过多维条件(如剩余能量、到节点的距离等)来选择簇头，然后通过单跳和多跳混合方法发送数据。该方法能够缓解能量空洞问题，延长网络寿命。

机会路由中节点分布稀疏，网络拓扑结构不断发生变化，数据方法是多跳，其转发节点从多个候选节点选出最终的转发节点，其优点是具有更高的传输可靠性以及端到端的吞吐量。机会路由允许在转发器列表中(能够偷听传输并且更接近目的地)的节点参与到包保护中，根据当前链路质量状况进行机会选择得到路由路径[11]。文献[12]提出一种候选节点间协同时延最优的机会路由协议，实现对候选节点协同转发过程的机理建模，得到期望端到端协同时延，并以此作为路由测度，增加了网络吞吐量，减少了端到端的平均时延。文献[13]提出针对异步工作循环无线传感器网络的网络内聚合的机会路由，能提高保持数据包的节点的占空比，增加网内聚合的机会，从而降低能耗，延长网络生命周期。文献[14]提出一种多跳传感器网络中基于能量感知的机会路由协议，在平衡链路质量和能量的前提下提出一种新的路由度量标准，并以此为准则，设计了候选集选择算法和节点协调机制。文献[15]提出一种基于网络编码的WSN机会路由优化算法，通过计算接收编码包失败的概率减少编码包的重传次数，达到延长网络生存时间、降低平均能耗的目的。

本文在研究现有无线传感器网络的机会路由协议的基础上，提出了一种节能的排序转发列表的机会路由(sorted forwarding list-based opportunistic routing,SFLOR)协议，给出转发列表的选择和优化算法，得到最大范围传感器节点的转发列表，使得能耗最小化。SFLOR协议能够降低网络能耗和丢包率，改善网络中节点能量的均衡性。

1 机会路由

为确保无线传感器网络的可靠通信，Biswas等提出的机会路由根据与目的地的接近标准选择下一个邻居。机会路由是无线传感器网络中一种新的路由选择方法，它充分利用无线信道的广播特征，提供高吞吐量，降低能耗成本，并在选择最佳路由时使用优先级概念。 机会路由基于以下规则：

1) 每个网络节点发送问候消息以发现相邻节点。

2) 每个节点将相同的消息发送到相邻节点。

3) 使用协调方法选择最佳节点。

4) 选择目标的最近节点。

机会路由协议针对无线信号的时变性以及不稳定性问题，利用无线信道广播的特征，从多路径机制和多节点转发机制这两个方面减少数据分组传输过程中的路由跳数，提高单跳传输成功率。机会路由多路径机制和多节点转发机制如图1、2所示。

图1 机会路由多路径机制

图2 多节点转发机制

图1中，S、A、B、D分别表示源节点、中间节点、中间节点和目的节点，百分数字表示传输成功率。在源节点S发送消息到目的节点D时，直接转发是最简单的方式，但由于链路质量问题导致传输效率只有20%。对于传统路由协议，为了提高传输成功率，选择链路质量好的路径转发数据。例如，数据分组选择S→A→B→D的路径，该路径的传输成功率最高，降低了分组重传的次数，缺点是数据分组转发次数较多。

对于机会路由协议，节点的邻居节点以大概率侦听到本节点的广播数据。在源节点S广播数据分组的过程中，目的节点可以直接接收数据分组，其优于传统路由的方面在于：数据分组无需按照选定的路径传输，在未收到数据的情况下，目的节点能够通过中间节点A或B的广播接收数据分组，在保证传输成功率的同时节省了网络资源。机会路由不需要提前选定传输路径，利用多路径机制和信道的广播特性，能够使得数据分组快速到达目的节点，在减少传输过程中路由跳数的同时节省网络资源，提高网络吞吐量。

机会路由的下一跳是选择最佳转发节点进行转发，选择条件是按照一定的度量。在图2中，假设源节点S至相邻3个节点之间的数据传输成功率相等且均为30%，在传统路由协议中，源节点S通过预设的路径(选择3个中间节点的1个作为中间节点)将数据传输到目的节点D，此时，源节点S到目的节点D的数据传输成功率只有30%。在几种路由中，3个节点都有可能作为下一跳接收到数据包并转发给D，此时，数据传输的成功率为1-(1-30%)3=0.657，较传统路由协议有了很大的提高。因此，在链路质量较差的无线传感器网络条件下，机会路由能显著提高网络端到端的可靠性。

MIT开发的ExOR(extremely opportunistic routing)协议是较经典的机会路由协议，其中路由度量是预期传输计数(expected transmission count,ETX)，是最受欢迎的路由度量之一，在确定链路质量方面具有良好的准确性。ETX可用于提高网络吞吐量，特别是对于长路径情况。

2 SFLOR机会路由协议

无线传感器网络因其独特的特性(易于部署和灵活性)被认为是技术发展最活跃的领域之一。为延长网络寿命，无线传感器网络的研究主要围绕能耗参数的路由算法展开。在这种情况下，本文提出了一种排序转发列表的机会路由(sorted forwarding list-based opportunistic routing,SFLOR)协议。SFLOR协议是节能机会路由(energy efficient opportunistic routing,EEOR)的改进协议，其中选择到目的地的距离最小的节点被添加到EEOR协议中。另外，本文的机会路由协议采用多元维度(到目的地的距离、错误率、节点的能量和发送成本)度量，以提高无线传感器网络的路由性能。本文中SFLOR协议的目标是：① 最大限度地降低能耗；② 延长传感器网络的使用寿命；③ 增加传输的数据量；④ 最小化控制消息的数量。

2.1 转发列表的选择和优化

无线传感器网络模型为G(u,FWD)，其中u代表传感器节点，FWD是u的转发列表。两个节点(i,j)之间链路的成本由C=1-P计算得到。该表达式表示正确接收分组的概率，P是传感器u发送分组但未被任何节点接收的概率。

(1)

其中：1-euvi是节点u正确地将数据包发送到节点v的概率。转发列表的计算方法为

FWD(u)=vi…vj,i

(2)

根据列表中的成本来处理节点。在计算每个节点的转发列表后，计算从源节点到目标节点发送数据包的总成本，总成本分为3个部分：

(3)

C(FWD*)=W/P

(4)

(5)

(6)

2.2 本文协议网络模型

无线传感器网络中的传感器节点可以使用单跳或多跳连接，具体取决于传感器节点的传输范围。 连接源节点和目标节点的跳数增加会增大节点传输和节能的延迟。本文SFLOR协议的目的是减少传感器节点在接收、传输信息时所消耗的能量，并减少无线传感器网络中从源节点到目标节点传输数据的延迟。假设无线传感器网络中：传感器节点部署的类型是静态的；网络中的节点密度是一致的；所有传感器节点具有相同的初始能量；网络中数据生成的频率是一致的；网络中所有节点具有相同的传输范围。

在网络中发送的从源节点到目标节点的分组可以被认为包括3个部分：

1) 源节点将分组发送到一个邻居节点，并且该节点是目标节点；

2) 如果目标节点是远离源节点的一跳，则在邻居列表中至少有1个节点将分组中继到目标；

3) 在发送节点的邻居之间选择实际中继节点的协议。

本文协议在假设数据聚合的情况下提出了最大化寿命的问题，对于仅具有1个源节点和1个目标节点的传感器阵列，考虑具有调整传输功率能力的传感器，得到最短路径处理路由。网络建模为G(U,V)，U是节点集，V是链路集，每个有向链路(i,j)具有非负权重，由w(i,j)表示，是节点i向节点j发送分组所需的最小传输功率。节点i的相邻节点的数量随着节点i在发送分组时消耗的功率而变化。当节点i以功率w发送时，令Nw(i)表示节点i的相邻节点。当未提及下标w时，意味着节点正在使用最大功率，即N(i)=NW(i)。此外，每个链路(i,j)的错误概率用e表示，是链路(i,j)上传输不成功的概率。节点i必须消耗至少w(i,j)功率才有1-e的机会将数据包发送到节点j，否则无法传输。节点U和目标节点之间的距离用d表示，c表示节点的预期成本。本文SFLOR协议的模型和预期成本如图3所示。

图3 本文协议模型和预期成本

本文中，路由协议给出转发列表进行选择和优化，并将选择到目标节点的距离最小的节点添加到转发列表，得到最大范围的转发列表。SFLOR策略基于组合度量来提高无线传感器网络的路由性能，组合度量包括预期成本、错误率、源节点与目标节点距离的组合。SFLOR算法基于2个步骤：转发列表和计算成本。

步骤1:转发列表FWD输入:目标节点,源节点,预期成本、错误率和源节点和目标节点距离的组合(c,e,d),功率w。输出:每个节点的转发列表。 a.在FWD列表中添加源节点 b.计算FWD(u)=v1时的预期成本 C=w+(1-e)∗1c∗1d()(1-e) c.如果FWD的预期成本<∑FWD中节点成本,则添加节点

步骤2:计算成本输入:转发列表中的每个节点,目标节点、源节点、预期成本、错误率与源节点和目标节点距离的组合(c,e,d),功率w。输出:从节点u到节点t的预期成本Cu(FWD)。 a.计算每个FWD列表的能源成本 Chu(FWD∗)=W/P b.计算U下的总成本,使用FWD列表将数据包转发到目的地 Chu(FWD∗)=β/P c.计算通信成本达成最佳路径选择协议,直到没有节点添加转发器列表Ccu

对本文协议算法进行验证，节点无法在转发列表中选择其所有邻居。

步骤1计算转发列表中节点v1的成本。

FWD{Source}={N1}

C=(w+(1-e1)×1/c1×1/d1)/(1-e1)=2.33

(7)

步骤2比较节点N1的成本和添加N1后的总成本，C=2.33>c1=1。要添加节点，除非N1成本小于转发列表中节点的总成本，否则完成N1。

(8)

(9)

因此，转发列表包含N3，因为该节点最接近目标节点。总成本的1/d的增加显示了转发列表最小化和最佳节点的选择。

3 实验结果与分析

本文路由协议实验中，实验对象为n∈[10,200]节点拓扑传感器，其中每个无线链路有固定的误差率，节点以预测的随机间隔恢复能量，并假设其电池是理想的。指定本文模拟实验在网络G(U,V)上进行，其中U={N1,N2,N3,…,Ni},i∈[1,n]，n∈[10,200]是节点数，V是链路集，网络参数如表1所示。

表1 网络参数

实验在笔记本电脑上进行。机器配置为8 Intel CORE i7，4GB Ram。模拟的传感器节点配备应用层、随机线性网络编码、机会路由、对介质的随机访问和物理层。表2给出了网络模型和符号。

表2 网络模型中符表示意义

将本文协议与经典ExOR协议、节能机会路由EEOR协议进行比较。图4给出了3种路由协议的能量消耗。

图4 不同协议的能耗

可以看出：本文SFLOR路由协议相比EEOR和ExOR协议具有更好的性能。这是因为本文算法选择到目标节点距离最小的节点添加到EEOR协议，最大限度地降低了能耗。图5给出了不同协议传输过程中丢弃的数据包总数。

图5表明：SFLOR协议在丢弃数据包数量方面提供了更好的性能，SFLOR协议比ExOR协议的丢包率降低了20%左右，比EEOR协议的丢包率降低了11%左右。图6给出了不同协议下的候选节点选择。

图5 不同协议的丢包率

图6 不同协议源和目标节点之间的候选集选择数

更具体地说，在当前节点发送数据分组时，所有成功接收的节点都是FRW，它们彼此协调以确定实际传递的FRW。从图6可以看出：本文SFLOR协议比其他2种协议具有更少的源和目标节点之间的候选集选择数，因而本文SFLOR协议能够以较少的能耗实现数据包传输。

4 结束语

本文研究了如何选择和优先转发列表，减少单播能耗，提出一种排序转发列表的机会路由SFLOR协议。该协议给出了传输功率固定条件下，每个节点选择和排序转发列表的算法，并将选择到目标节点的距离最小的节点添加到转发列表。通过同ExOR协议和EEOR协议的实验表明：SFLOR协议在能耗、丢包率、源与目标节点之间的候选集选择数3个方面的性能优于其他2种机会路由协议。下一步工作中，将选择用于组播和广播的最优转发列表的算法，研究如何将机会路由与网络编码和链路层错误校正相结合，以提高吞吐量并减少重传。