主动编码的机会网络高效路由算法

孙建飞，高 媛，王淑敏

(中北大学 计算机与控制工程学院,太原 030051)

0 引言

机会网络是不需要源节点和目的节点之间存在完整路径，利用节点移动带来的机会相遇实现网络通信、时延和分裂可容忍的自组织网络。网络编码是2000年由Ahlswed等提出，2005年之后许多国外学者开始研究无线网络中的网络编码。COPE[1]利用机会侦听和接收报告的方式最大化一次传输的数据包数量，但被动的编码机制限制了网络编码提升网络吞吐量的能力；CORE[2]中提出了转发集的概念，每个节点单独计算数据转发的优先级，可同时得到网络编码和机会路由对无线网络所带来的增益；MORE[3]采用随机线性编码的方式提高投递率，但提升网络吞吐量能力有限，网络延时大；PACE[4]中节点每次都着眼于提升节点附近区域中的编码增益，并增加了转发延时有效的控制了碰撞的发生。王少园[5]等提出COPE改进算法，以链路质量度量作为备选转发节点集的选择标准，在一定程度上提高了整体网络的吞吐量，降低了数据端到端的时延。基于上述分析提出了ANCBCR算法。

1 ANCBCR算法

下面是算法的描述。

1.1 主动异或编码

与COPE不同，节点Vi每次转发数据时不是立即计算将符合条件的数据编码后转发给相应的邻居节点，而是通过等待一个时间段T，若在T内侦听到了新的邻居节点，并将此节点加入本次计算，知道时间T到达将满足条件数据包编码转发。编码包计算方式如下：

（1）节点Vi要转发数据时，通过侦听到的邻居信息计算出邻居Vj的请求矢量Requestji，如式（1）：

假设Vi的缓存中储存有n个数据包，且Vi的邻居个数为m个，则可以得到一个m行n列请求矢量组成的矩阵M（如式（2）其中列为节点Vi中数据包的ID，行为Vi的邻居节点ID）。

（2）计算符合编码条件的数据包。

将B中值不为0的个数记为b，C中值不为0的个数记为c，分三种情况：

所以最大编码包数为b-max(B)。

接着将B中值大于1的位置对应的列的值全部置为0，重新计算B、C，利用B、C得到满足编码条件的数据包进行异或编码后多播给相应的邻居节点。

1.2 数据包发送顺序优化

在时间T到达之后，转发节点Vi首先查找自己缓存中是否存在目的节点为邻居的数据包，若存在则优先转发；接着将多个节点要求转发的数据包多播给相应节点；最后，计算得到满足条件的数据包编码后多播给相应节点。至此，一次完整转发结束。

1.3 节点数据缓存管理

节点Vi收到邻居Vj发来的SVj后计算出Vi和邻居Vj都存在的数据分组Commonji，计算方法如式（6）：

接下来节点Vi遍历Commonji，查找目的节点为Vj的数据分组，存在则从本地缓存中将其删除，并将其写入已到达目的节点数据索引中，达到清理缓存和减少网络开销的目的。

1.4 阈值T的确定

T为延迟编码计算的最长时间，如式（7）：

其中Ti(i=1,2,....m)为Vi的m个邻居与Vi处于通信范围内的时间，如式（8）：

其中R为通信半径，d为节点间距，V为节点速度，m邻居个数，t为发送单个数据包所用的时间，如式（9）：

其中M为数据包大小，V0为数据传输速率，t0为传输数据包Head字段所需的时间。

2 仿真与分析

2.1 实验平台搭建与参数设置

本文采用ONE(Opportunistic Network Environment)仿真软件平台，采用(Shortest Path Map Based Movement)为移动模型。

2.2 仿真结果分析

为了验证本文算法的性能，通过数据分组端到端平均时延和网络吞吐量这些指标与COPE算法和COPE改进算法进行比较，通过实验数据对网络性能进行分析。

图1 端到端数据传输时延

（1）端到端数据传输时延。由图1可知，随着网络中数据流数的增加，3种算法的时延均呈现下降趋势，这是因为网络中数据流的增加使网络中的数据包有了更多的转发机会。尤其，本算法较另外两种算法的时延有明显下降，平均下降1200s，这是因为数据包发送顺序优化机制有益于增加数据转发机会。另外，COPE和COPE的改进算法分别在数据流个数为70和60的时候端到端时延有上升趋势，而本算法却保持在了接近2500s的稳定状态，这是因为本算法引入了缓存清理机制克服了因缓存资源不足而造成丢包进而引发数据分组延迟接收的问题。

图2 网络吞吐量

（2）网络吞吐量。网络吞吐量是指单位时间内流经整个网络的数据量。从图2可以看出，在发送数据流小于60kb/s时，三种算法的网络吞吐量均有所提升，两种改进算法均大于COPE算法，这是因为COPE改进算法增加了新的判断机制，而本算法引入了主动编码机制并又花了数据的转发顺序，增加了转发机会。在发送数据流大于60kb/s后，由于网络拥塞，三种算法的吞吐量均有下降趋势，但由于本算法引入了SV缓存清理机制，所以吞吐量下降趋势较另外两种算法明显平缓的多，并且在发送数据流为200kb/s时仍能保持在25kb/s以上。

3 结束语

本文提出的基于主动编码的机会路由算法引入了主动异或编码和多播，充分利用节点的每次相遇机会，提高了整体网络吞吐量和数据分组平均端到端时延，同时增加了缓存清理机制进一步提升了该算法的性能。接下来的工作将致力通过机会网络中节点间相互协作，合理的调度数据的传输顺序来提升区域网络吞吐量的问题。

[1]KATTI S, RAHUL H, HU W, et al. XORs in the air: Practical wireless network coding [C]. Protocols for Computer Communications , 2006:243-254.

[2]YAN Y, ZHANG B, MOUFLAH H T, et al.Practical codingaware mechanism for oppor- tunistic routing in wireless mesh networks[C]. Proceedings of IEEE International Conference on Communications, 2008: 2871-2876

[3]CHACHULSKI S, JENNINGS M, KATTI S, etal. Trading structure for randomness in wireless opportunistic routing[C].Proceedings of Conference on Applications,2007: 169-180

[4]YAN Y, ZHAO Z, ZHANG B, et al. Mechanism for maximizing area-centric coding gains in wireless multihop networks[C].Proceedings of IEEE International Conference on Commun-ications, 2009, 14-18

[5]王少园，吴蒙.基于COPE协议改进的网络编码感知机会路由算法[J].电信快报,2013:41-44.