0 引言

    2000年，AHLSWEDE R等人首次提出了网络编码^[1]的理论。网络编码允许中间节点对数据进行编码后转发，增加了单次转发的信息量。相比于传统的传输方式可以减少信息的传输次数，提高网络吞吐量，实现理论上的最大传输容量。

    编码感知^[2]是指在路由建立过程中把编码机会考虑进去，通过主动探索、创造并利用网络中潜在的编码机会，使网络的吞吐量得到进一步的提高。将编码感知与路由算法相结合已成为数据转发策略的一个重要研究方向。随着对无线多跳网络中网络编码路由协议研究的不断深入，学者们发现现有的路由协议中编码机会得不到充分的利用，并没有让网络编码的性能得到最大限度的利用。在数据转发过程中，如何发现并利用更多的编码机会已成为科研人员研究的重点。

    文献[3]由KATTI S等人首次提出了适用于无线 mesh的网络编码路由协议COPE。在COPE协议中节点利用机会监听和网络编码减少了数据传输次数，提高了网络吞吐量。但节点需要周期性地广播控制报文信息，且只能探索两跳范围内的编码机会，限制了网络编码的性能。CORE^[4]与CORMEN^[5]是将编码感知与机会式路由相结合，规定在转发节点集内选择具有更多编码机会的节点优先转发数据包，这样在一次传输过程中更加有效地利用网络中的编码机会。该类协议采用的编码机制也是COPE，但它需要维护两跳范围内所有节点缓存队列中的数据包信息，编码带来的网络开销较大。文献[6]根据节点间的社会属性设计了一种编码节点状态感知的容迟网络数据转发机制，该机制减少了网络资源开销，改善了网络资源利用率。文献[7]提出了一种适用于无线mesh网络的编码感知且负载均衡的多播路由，在编码感知的基础上增加了对路径上所有节点通信密集程度与网络拥塞程度的考虑。

    充分考虑节点编码机会的编码感知路由协议^[8] ExCAR能有效地发现多跳范围的编码机会，但该协议在节点编码机会计算时可能存在误判以及在转发节点集内选择最优编码节点时需要交换大量的数据包缓存信息，会导致较大的时延和网络开销。为解决ExCAR协议存在的问题，本文提出了一种适用于多跳无线网络的节点编码感知机会转发路由协议——NAOFP，并对该路由协议的性能进行了理论分析和仿真验证。

1 ExCAR协议问题描述

    经深入研究，发现ExCAR协议存在以下缺陷：

    （1）原协议为了判断数据包在中间节点的编码机会时，将发送节点的所有一跳邻居节点的ID全部附加到即将发送的数据包上，没有考虑实际的无线网络链路存在不稳定性，在判断编码机会时可能会造成误判，导致到达的编码包不能成功解码，浪费网络资源。

    （2）原协议在转发节点集内选择转发节点时，需要节点计算自己的编码机会，而且集合内的各个节点周期性地转发各自拥有的数据包信息和侦听缓存的数据包信息来计算其他节点的编码机会，最后通过与其他节点的比较选择出最佳转发节点。在此过程中，每个节点的传输开销和计算开销比较大，同时由于计算转发集内其他节点的编码机会也会增加数据包的处理时延。

    （3）原协议在侦听缓存时把附加信息packet holders也一并放入缓存中，但这些packet holders附加信息对解码不起作用，且占据了一定的缓存空间。

2 NAOFP协议

    本文提出的NAOFP协议通过引入基于侦听概率的附加ID信息添加、最优转发节点选择、数据包的高效缓存3个新的机制来解决ExCAR协议存在的上述3个问题。下面对NAOFP协议的编码机会的判断、提出的新机制以及该协议的具体执行步骤进行详细介绍。

2.1 编码机会的判断

2.1.1 基于侦听概率的附加ID信息添加机制

    节点转发数据包时，将该节点的ID和一跳邻居节点的ID添加在即将发送的数据包头部。为保证编码包的解码成功率，在添加附加ID时需要将发送节点与其邻居节点的链路情况考虑进来。该机制具体步骤如下：

    (1)计算。依次计算发送节点S与其各个一跳邻居节点n_i的侦听概率P(s，n_i)：

其中，P(s，n_i)为邻居节点n_i成功侦听到节点S发送数据包的概率，n_i为发送节点S的第i个邻居节点，P_f(s，n_i)为节点S到其邻居节点n_i的链路正向丢包率；

    (2)判断。依次判断每个邻居节点的侦听概率P(s，n_i)与阈值P_th的大小；

    (3)添加。如果某一邻居节点的P(s，n_i)比阈值P_th大，说明S到该邻居节点n_i的链路状况良好，则将此邻居节点的ID附加到待发数据包p的头部。

    如图1所示，节点S₁需发送数据包p到目的节点D₁，节点S₂需发送数据包q到目的节点D₂。当S₁在发送数据包p前，利用基于侦听概率的附加ID信息添加机制将符合要求的节点ID添加到数据包P的头部，假设其邻居节点R₁、R₂、D₂的侦听概率均满足上述要求，则数据包p的附加ID信息的添加情况如图2所示。

    在数据包相遇时，可由packet holders信息得知哪些节点已缓存了该数据包的备份。

2.1.2 编码机会判断规则

    数据包能在一起编码的前提是目的节点已缓存了能用于解码的数据包，保证编码包在目的节点能成功解码。本文利用附加ID信息来判断数据包在编码前目的节点是否已缓存了用于解码的数据包。假设中间节点收到来自不同数据流的两个数据包p、q，若同时满足式(2)和式(3)成立，则数据包p、q可进行编码发送。

2.2 最优转发节点选择机制

    转发节点集内的节点各自计算本节点的编码机会，然后各节点间只需通过交换各自的编码机会次数选择出次数最多的节点。

    假设转发节点集内有x、y两个节点，当收到带有附加ID信息的数据包p时，从转发节点集内选择出最优转发节点的具体步骤如下：

    第一步：转发节点集内的每个节点各自计算编码机会次数count，即节点x、y的发送队列中能与数据包p一起编码发送的数据包个数。以节点x为例，具体计算过程如下所示。

输入：p ； //节点x收到带有附加ID的数据包p

输出：count(x) ； //节点x的输出队列中能与P一起编码的数据包个数

Procedure：

count(x)=0；

    while(node x output queue !=Null)   {

    for(i=1；i<n；i++)   {

     //判断是否满足编码机会判断规则，其中pi表示节点

       x的输出队列中的第i个数据包

    If(Dest_p∈Setpi && Dest_pi∈Setp)   {

    pcode1=p⊕pi；//进行编码，获得编码包pcode1

    Count(x) ++；//更新编码包pcode1的附加信息

    Setpcode1=Setp∩Setpi；

    Dest_pcode1=Dest_p∪Dest_pi；

    pcode1 is stored to the buffer；

    remove pi from output queue；

    p=pcode1； }

    continue； }

    return  count(x)； }

    同理，节点y也可以通过上述过程计算出能与p一起编码的数据包个数count(y)。

    第二步：转发集内节点交换各自的编码机会。此时，节点x知道count(y)的值，节点y知道count(x)的值；

    第三步：转发节点集内的节点通过与其他节点的count值比较，如果发现自己的count值最大，则选为最优转发节点。

2.3 数据包高效缓存机制

    由于无线链路的广播特性，网络中有数据发送时，位于该节点的邻居节点能够以一定的概率侦听到该数据包并放入缓存中，用于编码数据包的解码。在NAOFP协议中，网络中的节点侦听到数据包时，去掉附加在数据包上的packet holders信息后放入缓存。由于去掉了packet holders附加信息，在节点缓存大小相同的情况下能够缓存更多数量的数据包用于解码，提高了编码包的解码成功率，进而提高了网络的实际吞吐量。

2.4 NAOFP协议的执行步骤

    NAOFP协议各阶段的具体执行步骤如下。

    （1）附加ID信息的添加

    当网络中的节点有数据包要发送时，按照2.1.1节所述的基于侦听概率的附加ID信息添加机制将该发送节点的ID和符合要求的邻居节点ID添加在即将发送的数据包的头部，用于编码机会的判断。

    （2）转发节点集的选取

    在NAOFP协议中不预先使用指定的节点对数据包转发，而是在数据包发送前预先选取多个节点作为数据包的潜在转发节点，这些节点的集合即为转发节点集。以下为转发节点集内节点选取所必须满足的条件：

    ①该节点必须是发送节点的下一跳邻居节点；

    ②为了避免数据包的转发远离目的节点，该节点必须距离目的节点更近。本文使用ETX度量值来衡量，即转发节点集内节点的ETX度量值要小于发送节点的ETX度量值；

    ③在转发节点集内的节点必须能够相互侦听；

    ④转发节点集选取节点的个数不应超过6个。

    （3）最优转发节点的选择

    将带有附加ID信息的数据包发送到转发节点集内的节点后，按照2.2节所述的最优转发节点选择机制，选择出具有编码机会数量最大的节点选作该数据包的下一跳转发节点。如果转发节点集内出现具有相同编码机会次数的多个节点时，应选择ETX度量值最小的节点来进行数据包的转发。转发集内的其他节点侦听到该数据包被成功发送后，将该数据包从发送队列中删除。

    网络中的节点侦听到的数据包按照2.3节所述的数据包高效缓存机制进行处理。

3 仿真实验及结果分析

3.1 仿真场景及参数设置

    本文采用网络仿真软件OPNET 14.5版本搭建仿真平台，对NAOFP协议与ExCAR协议的性能进行分析与比较。实验场景是在500 m×500 m的区域范围内随机分布15个无线节点，其中MAC层使用较为普遍的IEEE 802.11b标准协议。具体的仿真参数设置如表1所示。

3.2 仿真结果分析

3.2.1 网络吞吐量

    如图3所示，NAOFP协议的网络吞吐量在不同的网络负载下均高于ExCAR协议。这是由于NAOFP协议在进行数据包附加ID信息添加的过程中考虑了无线链路的不稳定性，发送节点与其邻居节点的侦听概率P(s，n_i)小于阈值P_th，则不将此邻居节点的ID添加，这样在目的节点保障了较高的解码率，避免了编码包不能成功解码而造成的网络资源浪费，从而使网络吞吐量得到了有效的提高。

3.2.2 平均端到端时延

    如图4所示，NAOFP协议的数据包平均端到端时延在不同的网络负载下均低于ExCAR协议。这是因为NAOFP协议在转发节点集内选择编码机会数量最大的节点时，并不需要节点间相互交换各自的数据包信息，也不需要计算其他节点的编码机会次数，这样减少了数据包在转发节点的处理和等待时间，从而使网络中的平均端到端时延得到明显的降低。

3.2.3 编码包的解码成功率

    如图5所示，NAOFP协议的编码包的解码成功率在不同的网络负载下均高于ExCAR协议。这是因为在NAOFP协议的步骤一中采用了基于侦听概率的附加ID信息添加机制，保障了编码包的可解性。另外，节点在侦听缓存网络中的数据包时，将数据包的附加信息去掉后缓存，这样在缓存大小一定的情况下可以缓存更多的数据包用于解码，从而使网络中编码包的解码成功率得到有效的提高。

4 结论

    本文针对ExCAR路由协议在无线链路不稳定的情况下，节点在计算编码机会时存在误判，以及在选择最佳编码节点时需要交换大量的数据包缓存信息，提出了一种节点编码感知的机会转发路由协议NAOFP，且在该协议中引入了基于侦听概率的附加ID信息添加机制和最优转发节点选择机制。仿真实验结果表明，与ExCAR路由协议相比，NAOFP协议在网络吞吐量、平均端到端时延、编码包的解码成功率等方面的性能均得到了有效的改善。

参考文献

[1] AHLSWEDE R，CAI N，LI S，et al.Network information flow[J].IEEE Transactions on Information Theory，2000，46(4)：1204-1216.

[2] CHEN C，DONG C，MAO Y F，et al.Survey on network-coding-aware routing in wireless network[J].Journal of Software，2015，26(1)：82-97.

[3] KATTI S，RAHUL H，HU W J，et al.XORs in the air: practical wireless network coding[C].ACM SIGCOMM，Pisa，Italy，2006：243-254.

[4] YAN Y，ZHANG B X，ZHENG J.CORE：A coding-aware opportunistic routing mechanism for wireless mesh networks[J].IEEE Wireless Communications，2010，17(3)：96-103.

[5] ISLAM J，SINGH P K.CORMEN：Coding-aware opportunistic routing in wireless mesh network[J].Journal of Computing，2010，2(6)：71-77.

[6] 王汝言，楼芃雯，樊思龙，等.容迟网络编码节点状态感知的数据转发策略[J].重庆邮电大学学报(自然科学版)，2013，25(2)：215-220.

[7] 沈小建，陈志刚，刘立.无线mesh网络中编码感知且负载均衡的多播路由[J].通信学报，2015，36(4)：89-95.

[8] 赵蕴龙，王博识，张凯，等.充分考虑节点编码机会的编码感知路由协议[J].应用科学学报，2014，32(1)：7-12.

作者信息：

姚玉坤，王  宇，吕盼成

(重庆邮电大学 移动通信技术重庆市重点实验室，重庆400065)