低延迟高效率的机会网络编码扩展算法

郝 兵，曹海英

(1.河套学院 数学与计算机系，内蒙古 巴彦淖尔 015000； 2.内蒙古师范大学 计算机系，内蒙古 呼和浩特 010000)

0 引 言

网络编码[1]可提高单源通信的容量，在组播网络中实现最大数据传输率，利用共享无线介质的广播特性，提高带宽、降低延迟，改善传输功率的性能[2]。在组播场景中，网络编码一般实施在应用层[3]，同时在物理层中部署二阶段网络编码以增加频谱效率。本文重点研究无线传感器网络(wireless sensor network，WSN)中的机会网络编码。

机会网络编码[4]的“机会”表示编码的伺机性，仅当机会出现时才对分组进行编码，且不存在增加编码机会数量的机制。开发机会网络编码方案时，需要对路由路径选择、流量负荷平衡，以及网络编码决策[5]等问题进行解决。同时，为缓解高负荷节点超限造成的分组丢失问题，需要考虑负荷平衡[6]，向节点提供可在接收节点处解码的编码分组。

将机会网络编码程序完美集成到当前网络架构很困难。其实施会影响到当前网络协议栈的功能组件，如调度、路由和拥塞控制[6,7]。所有这些组件的交互会增加实施难度和计算复杂度，如基于机会判定规则的网络编码[8]、面向传输优化的机会网络编码(opportunistic network coding-transmission optimization，ONC-TO)[9]和基于聚类的网络编码方法(clustering network coding，CNC)[10]都依赖于在网络层中收集到的信息。基于机会判定规则的网络编码还依赖链路层的调度信息。其它机会网络编码在很多方面实现了性能提升，但增加了复杂度，以及一些额外网络开销。

为提高网络编码性能，必须保持低网络开销。相关研究表明[11,12]，可通过增加编码机会来平衡额外的开销，虽然承载机会网络编码[13](BON)程序带来的开销很小，但由于采用固定设置，其无法很好地应对流量和拓扑变化。因此，本文对BON编码进行扩展，利用自适应处理进行升级，以使其具有自我维持能力，实验结果验证了所提方法的优越性。

1 提出的机会网络编码扩展方法

提出的编码程序位于网络与链路层之间，其核心为编码算法，发现编码机会，通过在单次传输中转发多个分组来提高系统性能。本文假定每个节点知道其所有邻近节点的位置，且节点位置固定。算法仅根据分组上一条和下一条节点位置的相关信息做出编码决策。因此，其独立于所有其它通信层，且与协议完全无关[14]。

所提网络编码方法的主要模块与流程如图1所示。其中，从网络层到达节点上的所有传出分组均被分配到3个传输队列中(根据优先级排序)，即确认分组，重传(本地)分组，以及普通传出(本地)分组。在分组编码模块中，编码算法搜索编码机会，并寻找将消息附加到传出分组的机会。自适应处理观察编码过程，并在编码成功的基础上采用与编码相关的参数。在接收端，使用收到的确认消息来取消计划中的分组重传。如有可能，则对编码分组进行解码；若不能解码，则销毁分组。所有本地分组均保存在分组池中以进行解码，并发送至网络层做进一步处理。

图1 所提网络编码方法的主要模块与流程

1.1 编码算法

根据节点上的可用信息或需要收集的信息，制定将哪些分组编码在一起的决策。这种解决方案不会为网络带来新的额外开销，但其缺点在于，编码程序要实施的层必须包含可用的路由信息。但当前商用通信组件并不总能满足这一条件。通过周期性的计划测量(例如，路由链路投递概率测量)来采集信息，会引入额外的开销，由此造成网络实际吞吐量降低。

编码处理以分组的局部方位为基础，该方位在中继节点上定义，由分组上一跳和下一跳的位置决定，其图形表示如图2所示。没有经过至少一次跃程的分组是不可编码的，也不用定义其方位。以图2(a)为例，来解释方位的定义。

图2 图形表示

(1)

并将其转换到三维空间内，其中还考虑到节点评估(Z)

(2)

通过增加容限角，可以覆盖更大区域，由此提高分组满足条件的概率[15]。但加大容限角参数，接收节点不能对分组解码的概率也随之上升。降低参数ε的数值将减少编码机会，但接收节点成功完成分组解码的概率则会增加。

对方位机会网络编码程序进行扩展，可支持多个分组的编码。当所有分组对及其相应节点均在邻近区域内，可以将多个分组编码到一个分组中。ε的数值越大，可编码多个分组的概率越高；另一方面，若至少一个ε=0， 则仅可对两个分组进行编码。提出的编码程序中，通过参数ε实现编码机会和分组成功解码之间的平衡，而参数ε在每个节点上自动调整。

1.2 容限角的自适应

在决策制定过程中，根据定义2，容限角ε必须为已知。若将参数ε设为过低的数值，算法可能无法发现所有可能的编码机会，从而导致网络性能下降。若参数ε的数值过大，则接收节点很可能将无法对分组内容进行解码，需要重传分组，同样会导致性能下降。此外，由于无线网络中链路质量的变化，算法必须能够快速自动调整参数ε。

根据重传比(RR)参数来调整容限角ε，RR反映了分组编码成功率，节点Vi的RR计算为

(3)

式中：KCVi>0为编码分组一部分的本地分组数量，即节点上的编码分组；KPVi>0为从网络层传递到网络编码层的分组数量。KRVi为节点上网络编码层重传分组的数量。RR值较高意味着分组重传比率较大，重传原因是分组解码不成功或分组投递失败。这种情况下，说明网络条件可能比较差，需要考虑保守的编码条件，即较小的ε值。

当KRVi/KCVi较小，或KPVi较大(足以补偿较高的KRVi/KCVi比)时，将得到较小的RR值。第1种情况意味着较好的编码条件，因为与编码分组数量相比，重传次数较少，因此可考虑宽松的编码条件，即增加ε。第2种情况下，若实际上进行的编码数量很少，且节点正在处理大量分组时，KPVi数值可能会较大。一般来说，可利用这种情况对介质进行测试，由此希望放宽编码条件。

容限角参数ε的更新过程如图3所示，首先，给出ε的初始值。在更新周期TεU中统计KR、KC和KP。其后，计算更新周期的重传比RR值。接着，将得出的数值与最大阈值RRmax和最小阈值RRmin相比较。根据比较结果，给出参数ε增加、减少或保持不变的决策。在更新过程结束时，重置KR、KC和KP的记数器。若网络条件适合编码，重传次数很少，则增加ε。由此可发现更多的编码机会。若决策不正确，分组重传次数会增加，那么在自适应的下一次迭代中会降低ε。需要对ε进行连续调整，因为需要使用普通传出分组对介质进行测试，以发现新的机会。

图3 容限角的自适应更新流程

在更新的过程中，RR是一个非常重要的参数，其定义如下

(4)

式中：m={1,2,3,…}， 在时间间隔 [(m-1)TεU,mTεU) 中对KRmVi、KCmVi和KPmVi进行测量。

以下算法给出了更新参数ε的详情。在解释基本程序之外，本文还考虑到本地分组处理数量KP，KP应该大于KPMIN以应对各种不同情况的变更。若较长周期内未发现编码机会，则增加参数ε。即，满足未编码阈值条件时，则增加ε值。参数ε的数值设定过低可能会造成节点上无编码机会。因此，通过提高ε值，可以提升编码算法的分组编码概率。

此外，还需要考虑KR、KC和KP的采样周期，因为修改参数ε导致的重传会在重传调度时间Tretrans后首次出现。至t+Tretrans之前的采样周期将记录参数ε之前状态。如前文定义，参数ε必须大于等于0。此外，参数ε不应大于εmax。函数Increase_Epsilon(ε,Δε,εmax) 和Decrease_Epsilon(ε,Δε) 在增加或减少ε(Δε为步长)时考虑到了这一点。函数Sche-dule_Update(T)在时间T调度启动ε更新程序的事件。

算法： 更新容限角ε算法

(1)if(KP>KPMIN)do

(2)if(KC>0)do

(3)if(在上一次更新中增加了ε)do

(4)CounterTrunsWithoutCoding=0；//无编码记录的时长

(5) Schedule_Update(t+Tretrans)；

//计划更新

(6)elsedo

(7) Schedule_Update(t+TεU)；

(8)if(RR≤RRmin)do

(9)ε=Increase_Epsilon(ε,Δε,εmax)；

//增加ε

(10)elseif(RR≥RRmax)do

(11)ε=Decrease_Epsilon(ε,Δε)；

//降低ε

(12)endif

(13)endif

(14)elsedo

(15) Schedule_Update(t+TεU)；

(16)if(CounterTrunsWithoutCoding>No_Coding_Threshold)do

//若无编码记录的时长超过无编码机会阈值

(17)ε=Increase_Epsilon(ε,Δε,εmax)；

(18)elsedo

(19)CounterTrunsWithoutCoding++；

//增加无编码记录的时长

(20)endif

(21)endif

(22)elsedo

(23) Schedule_Update(t+TεU)

(24)endif

2 仿真实验与分析

2.1 评价指标

本文利用OPNET Modeler 17.1[16]开发仿真模型。通过性能评价，分析机会网络编码的两个方面：首先，评估提出的编码程序性能；其次，通过分析服务质量(quality of service，QoS)参数和公平性，评估编码方法的用户感受。

网络实际吞吐量(g)是反映服务质量的基本度量，表示单位时间内网络向特定目的地传输的有效信息比特数。本文将实际吞吐量定义为第i次仿真中特定网络负荷下所有网络节点上所有实际吞吐量之和，即g(i)。此外，将第i次仿真中的增益G(i)定义为与使用网络编码后实现的实际吞吐量增长

(5)

式中：gcoding(i) 表示第i次仿真中，使用网络编码后的网络吞吐量；gnocoding(i) 表示第i次仿真中，不使用网络编码后的网络吞吐量。

现在，分析网络编码对QoS的影响。本文测量了应用层的端到端延迟，以捕捉在多个节点上传输，并分析在传输路径上可能被多次编码的分组影响。所有通信层都会增加应用程序延迟。在分析网络编码对总体延迟的影响时，可以与不使用编码方法作比较，因为其它网络层是相同的。端到端延迟可计算为

(6)

式中：dn为第n个分组的端到端延迟；Ka(i)为应用层接收到的分组数量。

2.2 参数设置

评价中，本文对提出的机会网络编码方法与文献[9]提出的面向传输优化的机会网络编码(ONC-TO)、文献[10]提出的一种基于聚类的网络编码方法(CNC)，以及不使用网络编码的参考场景进行比较。ONC-TO[9]与本文编码程序的操作较为相似，但存在两个主要差异：分组编码算法完全不同。此外，在ONC-TO中，节点使用报告消息来更新其邻近节点的接收分组状态，编码过程依赖于节点通过广播侦听所获取的邻接节点上的分组信息。虽然编码过程简单直接，解码处理的成功率较高，但通过特定消息和侦听所有广播消息获得的信息仅能提供很少的编码机会。当特定邻近节点上的分组信息不可用时，编码程序需要做出猜测。基于预期传递次数的路由协议通过投递概率完成猜测。通过观察分组的上一跳与节点N之间的链路的投递概率，得到节点N持有分组p的节点估计概率。

每轮仿真中，采集第90 s和第150 s之间的结果，以观察稳态条件。每个场景使用30种不同的网络负荷进行评估。针对每种网络负荷运行4次仿真。两种编码程序中，在首次接收分组之后，均将分组保存在分组池30 s。每隔0.5 s，至少发送一次累积确认消息。初始分组传输0.6 s后，发起网络编码层分组重传。若在网络中发现机会，则将累积确认消息附加到普通传出分组上。ONC-TO至少每0.5 s发送一次报告。在可能的情况下，将报告信息附加到普通传出分组或累积确认消息上。表1给出了本文编码方法的自适应参数。在原始节点中生成类UDP流量。通过分组到达间隔时间调整流量密度，分组长度的变换范围在360比特和12 000比特之间[17]。

表1 所提编码方法的参数设置

2.3 结果分析

首先使用增益度量，对两种编码程序与无编码案例进行比较，不同网络负荷下的增益(G)变化情况如图4所示，可以看出，与无编码案例相比，ONC-TO、CNC和本文编码程序均大幅提高了网络实际吞吐量，该结果与预期相符。从图4可发现，本文程序可以向指定目的节点传递最大数量的分组。当网络负荷较小时，两种编码程序均不会造成网络性能退化。低负荷状态下，编码机会较为稀疏；节点队列中分组很少，因此编码机会也非常少。此外，在无编码案例中，系统能够将整个负荷传递至目的地，且与编码场景的性能差异可忽略不计。随着负荷增加，编码机会也会增多。通过使用多个编码分组，减少了将相同的通信量传递至目的地所需的传输次数。由此减少了拥塞以及分组冲突概率，提升网络性能。

图4 不同网络负荷下的增益(G)变化情况

网络端到端延迟(ETE)变化情况如图5所示。由图5可知，与无编码案例相比，两种编码程序不但增加了实际吞吐量，而且降低了平均ETE延迟。当网络负荷较低时，本文方法、ONC-TO、CNC和无编码方法的延迟大致相同。随着负荷增加，差异开始出现。无编码案例中的ETE延迟增加最快，且所有负荷的ETE延迟均为最高。本文编码方法的实际吞吐量大于ONC-TO和CNC，且依然能够保持延迟低于ONC-TO和CNC。仿真中，通过网络编码的参数设置来优化网络实际吞吐量。利用网络编码将平均延迟保持在较低水平，虽然编码分组在传输路径中至少有一次解码不成功，但达到目的地的延迟依然远低于平均值。

图5 网络端到端延迟变化情况

本文方法的实际吞吐量和延迟方面的性能均优于ONC-TO和CNC，为深入比较，网络编码层内的分组重传结果如图6所示。从中可发现，与ONC-TO和CNC相比，本文编码方法能够更好地发现合适的编码机会，从而减少分组重传次数。编码程序中更好的决策制定得益于自适应处理。ONC-TO中，根据分组解码概率是否大于阈值来确定编码决策，该阈值是固定的。CNC根据分组的聚类决策。而在本文编码方法中，在每个节点上分别计算出容限角ε， 其中考虑到当前和过去的本地流量和链路条件。这意味着网络瓶颈，并执行大部分编码工作的节点的ε值较低。在大量编码机会中，算法会选择解码可能性较大的机会。由此，减少了不正确的编码决策和重传次数。对于执行编码作业较少的节点(例如位于网络边缘的节点)，将ε设为较大数值，以更投机的方式对分组编码。由此，不正确的编码决策造成重传的情况在这些节点上更可能发生。通过较低的ε值和用于重传的分组队列，确保了较好的分组投递率。

图6 网络编码层内分组重传次数

2.4 关于容限角对编码性能的影响

容限角设置不正确，会造成服务退化，甚至会造成整个数据流的丢失。应根据当前拓扑配置和流量分布设定最优容限角。下面讨论容限角的设置对本文编码方法的性能影响。本文使用恒定分组大小(10 KB)，以排除不理想编码的影响。在每轮仿真中保持容限角ε数值不变，并将结果与使用自适应容限角的结果相比较。图7给出3次最大增益(MaxGain)的均值结果。结果表明，ε值的设置会对性能产生较大影响。从结果中可发现，对于给定的流量分布和拓扑，最高的MaxGain值为25.7%，其中容限角ε=35°。 使用自适应方法时MaxGain为25.1%，稍低于最优固定值设置，但自适应算法大幅提高了可用性。

图7 容限角对本文方法的性能影响

3 结束语

本文提出一种机会网络编码方法，具有自适应性和通用性，适用于静态多跳无线网络，例如城域Wi-Fi网络或无线传感器网络，作为独立层，对上层和下层均具有透明性。且提出的编码程序与路由无关，向网络引入的额外开销非常小，由此使用的无线电资源也更少。对于无编码机会的节点，或者在整个网络负荷较低的情况下，网络开销与不使用编码程序时相同。结果表明与CNC、ONC-TO和不使用网络编码相比，提出的编码程序能够提升网络有效吞吐量，减少延迟。