, 孙学超1, 王梦源2, 陈文君31. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169;
2. 航天恒星科技有限公司, 北京 100086;
3. 国网辽宁省电力有限公司 大连供电公司, 辽宁 大连 116001
收稿日期：2017-08-02
基金项目：国家自然科学基金资助项目(61701100，61501038，61671141)；中央高校基本科研业务费专项资金资助项目(N161613001)。
作者简介：耿蓉(1979-)，女，辽宁瓦房店人，东北大学讲师，博士。
摘要：针对大多数编码感知路由算法忽略了不同数据流到达编码节点的时间不一致问题.在已有编码感知路由算法的基础上, 提出了基于等待门限值的编码感知路由算法.首先利用编码条件寻找编码节点, 然后引入网络测试获得等待编码时间的门限值, 最后根据实际值和门限值的关系决定是否等待.仿真结果表明:使用该方案的编码感知路由算法比仅仅考虑编码机会的路由算法在编码时延和吞吐量方面有更好的效果.
关键词：网络编码时延门限值权衡路由
Low-Delay Coding-Aware Routing Algorithm Based on Time Threshold Value
GENG Rong1
, SUN Xue-chao1, WANG Meng-yuan2, CHEN Wen-jun31. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
2. Space Star Technology Co., Ltd., Beijing 100086, China;
3. Dalian Electric Power Supply Company, State Grid Liaoning Electric Power Co., Ltd., Dalian 116001, China
Corresponding author: GENG Rong, E-mail: gengrong@mail.neu.edu.cn
Abstract: Existing coding aware routing algorithms ignore a realistic question that different data packets reach the encoding node at different time. To overcome the above problem, an improvement scheme was proposed using a threshold value on the basis of existing coding-aware routing. Firstly encoding condition was used to find the nodes to encode. Then the network delay training phase was introduced to obtain the threshold value of waiting time. Lastly, it was decided whether to wait or not according to the relationship between the actual value and the threshold value. Simulation results show that the algorithm can achieve a better result than the traditional opportunistic coding policy in delivery delay and throughput.
Key words: network codingdelaythreshold valuetradeoffrouting
链路传输时延是衡量网络性能的重要指标之一.但是, 当网络拥塞时, 传输时延性会受到影响, 而网络编码的出现为解决时延问题提供了新的思路.网络中新加入的数据流与网络中已存在的数据流在满足编码条件的情况下, 可以编码在一起进行传输.这种方式不占用额外的信道资源, 可以降低等待信道空闲的时延.然而无论是经典的被动编码算法COPE[1]还是后来的一系列主动编码感知算法[2-6]都是仅仅把编码机会作为判断节点是否适合编码的唯一标准, 而忽略了数据流在该节点的不同步问题:某一时刻在编码节点处只存在一条数据流的数据包, 是等待另一条数据流的数据包到来还是放弃编码直接转发?针对这一问题, 文献[7]把等待时延和传输时延之和作为目标函数, 以马尔可夫过程作为系统模型, 求得了理论上的最优缓存队列长度; 文献[8]仍然以马尔可夫模型下的时延作为研究背景, 用两个参数去描述节点缓存门限, 找到了理论上获得最优门限的计算方法; 文献[9]在数据传输阶段之前引入了网络时延训练阶段, 实现了基于缓存管理的编码感知路由低时延数据传输算法.
本文在以上研究的基础上, 提出了基于等待门限值的编码感知路由算法, 在编码等待时间和编码机会之间作出权衡, 与传统的编码感知路由算法相比性能得到了改善.
1 改进编码感知路由算法理论分析1.1 算法的基本思想根据文献[10], 3个以上的数据包可编码的概率远低于两个数据包的可编码概率, 不失一般性, 假设文中算法的可编码数据流的条数是2.在数据包编码时考虑缓存充足的情况下, 若推迟数据包的转发, 将会增加编码匹配成功率; 而数据包直接转发会损失一部分编码机会, 会减小编码机会的利用率.假设编码节点缓存充足, 需要在等待时延和编码机会之间作出权衡, 达到数据包端到端传递时延最优.为此, 引入了等待时延的门限值Ch.当等待时延Cd超过门限值Ch, 放弃等待直接传输; 当等待时延Cd没有达到门限值Ch时, 继续等待.该方法简单, 但是如果门限值的选取不当会导致端到端时延恶化, 因此门限值的恰当选择至关重要.
1.2 基于编码等待时间的数学模型及分析下面以三节点中继网络示意图为例(图 1), 进行理论分析.中继节点面临着3种情形:①Q1, Q2的缓存中都存在数据包; ②Q1, Q2仅有一个缓存中存在数据包; ③Q1, Q2都没有数据包.
图 1(Fig. 1)
 | 图 1 三节点的中继网络示意图Fig.1 Relay network diagram of three nodes |
针对情形②进行具体分析.下面假设数据缓存Q1里边有数据包, Q2里边没有数据包, 记此刻是0时刻, 令X(t)表示[0, t]时间段内Q2里边会有数据包到达, 故{X(t), t≥0}是一个泊松过程.由泊松过程的等价定义可知:
 | (1) |
假设编码之后数据包的传输时延和不进行编码数据包的传输时延近似相等, 记为Ct.命题Ch < Ct成立, 即等待时延小于传输时延.
证明????反证法, 如果Ch>Ct, 即等待时延大于链路传输时延, 以三节点的中继网络示意图为例, 不进行编码的时延:只有两次传输时延, 即2Ct; 进行等待编码后的效果优于编码之前, 所以2Ct>Ct+Ch, 即Ct>Ch, 与开始时的假设矛盾.故假设不成立.原命题得证.
综上所述, Ch有界, 0≤Ch≤Ct.
2 改进编码感知路由算法的具体实现算法的实现步骤如下:
1)利用编码条件确定编码节点;
2) 进行网络测试, 获得门限值Ch;
3) 编码节点根据等待时间的门限值决定编码节点是直接转发还是进行等待.
2.1 构造编码条件多跳编码条件可以描述为数据流f1和f2相交于节点C时:
(ⅰ)?d1∈D(c, F1),
s.t.d1∈N(S2),
????S2∈U(c, F2), or d1∈U(c, F2);
(ⅱ)?d2∈D(c, F2)，
s.t.d2∈N(S1),
????S1∈U(c, F1), or d2∈U(c, F1).
2.2 最优等待时间门限值Ch的获取进行网络测试时延, 获得足够多的传输时延值:Ct1, Ct2，…，Ctn, 用这些传输时延的样本值的均值作为对真实传输时延的估计:
 | (2) |
 | (3) |
编码感知路由算法DCAR(distributed coding-aware routing)没有考虑等待时延, 即Ct*=0.为了表征网络中的数据包传递时延, 用一段时间内的平均数据包传输时延来表征, 记为D(Ct*), 则D(Ct*)≤D(0).
2.3 基于等待时间门限值Ch的编码策略两条数据流交汇的节点收到的数据包是编码包时, 交汇点检查解码缓存中是否有用于解码此编码包的其余数据流信息, 如果没有, 则丢弃该编码包; 如果有, 则分离出需要的原始数据包.然后利用编码条件判断交汇点是否是编码节点:如果交汇点不是编码节点, 直接转发给下一节点; 如果交汇点是编码节点, 则检查该交汇点上是否有其他路径上的数据包到达, 如果有则进行编码转发; 如果只有一条数据流上的编码包, 则从此刻开始计时, 等待时间Δt, 如果Δt < Ch*, 继续等待; 反之, 放弃等待, 直接转发.编码流程图如图 2所示.
图 2(Fig. 2)
 | 图 2 编码流程图Fig.2 Coding flowchart |
3 仿真实验以及结果分析图 3为几种算法时延对比.从图 3可以看出，在数据流较少的情况下, 被动网络编码COPE, 基于编码机会的编码DCAR, 改进的DCAR( & DCAR)，三者的时延性能无大差别.随着数据流条数增加, DCAR主动发现网络中的编码机会, 相比于COPE而言, 可利用的编码机会增加，数据包传输次数减少, 时延减小; 而基于等待时间门限的编码策略通过牺牲等待编码时间, 获得更多的编码机会, 减少了数据包的传输次数, 进而降低了传输时延.所以, 总体上改进的DCAR时延优于DCAR, 优于COPE.
图 3(Fig. 3)
 | 图 3 算法的时延对比Fig.3 Delay comparison of algorithms |
图 4为几种算法的吞吐量对比.从图 4可以看出，在数据流较少的情况下, 被动网络编码COPE, 基于编码机会的编码DCAR，改进的DCAR( & DCAR)，三者的吞吐量性能无大差别.随着数据流条数增加, DCAR主动发现网络中的编码机会, 相比于COPE而言, 可利用的编码机会增加, 数据包传输次数减少, 单位时间内传输的数据包个数增加, 吞吐量增加; 而基于等待时间门限的编码策略通过牺牲等待编码时间, 获得更多可利用的编码机会, 整体上吞吐量变大.所以, 总体上改进的DCAR吞吐量优于DCAR, 优于COPE.
图 4(Fig. 4)
 | 图 4 算法的吞吐量对比Fig.4 Throughput comparison of algorithms |
4 结语为了解决单一数据流的编码包在编码节点是直接转发还是等待编码问题, 本文提出一种基于等待编码时间门限的编码感知路由算法, 并且给出了门限值的具体计算方法.理论分析和仿真实验都说明本文改进的编码感知路由算法比传统的基于机会的编码感知路由算法具有更低的时延和更高的吞吐量.
参考文献
| [1] | Katti S, Rahul H, Hu W, et al. XORs in the air:practical wireless network coding[J].IEEE/ACM Transactions on Networking, 2008, 16(3): 497–510.DOI:10.1109/TNET.2008.923722 |
| [2] | Le J, Lui J C S, Chiu D M.DCAR: distributed coding-aware routing in wireless networks[C]//International Conference on Distributed Computing Systems.Beijing: IEEE Computer Society, 2009: 462-469. |
| [3] | Zhou Z, Zhou L.Network joint coding-aware routing for wireless ad hoc networks[C]//IEEE International Conference on Wireless Communications, Networking and Information Security.Houston: IEEE, 2010: 17-21. |
| [4] | Guo B, Li H, Zhou C, et al. Analysis of general network coding conditions and design of a free-ride-oriented routing metric[J].IEEE Transactions on Vehicular Technology, 2011, 60(4): 1714–1727.DOI:10.1109/TVT.2011.2121097 |
| [5] | Vu T V, Nguyen T M T, Pujolle G.Distributed opportunistic and diffused coding in multi-hop wireless networks[C]// IEEE International Conference on Communications.Ottawa: IEEE, 2012: 5583-5587. |
| [6] | Chen J, Yuan Q, Du R, et al.MuCAR: a greedy multi-flow-based coding-aware routing in wireless networks[C]// IEEE International Conference on Sensing, Communication, and Networking.Ilsan: IEEE, 2015: 310-318. |
| [7] | Hsu Y P, Abedini N, Ramasamy S, et al. Opportunities for network coding:to wait or not to wait[J].IEEE/ACM Transactions on Networking, 2015, 23(6): 1876–1889.DOI:10.1109/TNET.2014.2347339 |
| [8] | Mohapatra A, Gautam N, Shakkottai S, et al. Network coding decisions for wireless transmissions with delay consideration[J].IEEE Transactions on Communications, 2014, 62(8): 2965–2976.DOI:10.1109/TCOMM.2014.2335211 |
| [9] | 芦存博, 肖嵩, 权磊, 等. 一种编码感知路由低时延数据传输算法[J].西安电子科技大学学报, 2016(4): 17–22. ( Lu Cun-bo, Xiao Song, Quan Lei, et al. Low-delay data transmission algorithm for coding-awaring routing[J].Journal of Xidian University, 2016(4): 17–22.DOI:10.3969/j.issn.1001-2400.2016.04.004) |
| [10] | Wang W P, Wu W, Guan Q J, et al. TCAR:a new network coding-aware routing mechanism based on local topology detection[J].Journal of Central South University, 2014, 21(8): 3178–3185.DOI:10.1007/s11771-014-2289-5 |
