ISSN 
-45-5-720-2.jpg)
-45-5-720-3.jpg)
-45-5-720-4.jpg)
-45-5-720-5.jpg)
-45-5-720-6.jpg)
-
DTN中通信节点间的连接具有间断性，源节点和目的节点之间很少存在持久不间断的端到端路径。正是由于节点间这种固有的间歇性连接特征，数据转发成为DTN最具挑战性的难题之一[1]。研究表明，网络编码能够有效改善网络环境，提高网络的资源利用率[2]，尤其是随机网络编码[3]的提出，更是将网络编码带入到更加实用的分布式网络领域中。因此，将网络编码应用到DTN数据转发策略中引起了人们广泛的关注。
文献[4]将随机网络编码和传染路由结合在一起，提出了基于网络编码的传染路由算法(network coding based epidemic routing，NCER)，并通过理论分析和仿真实验验证了NCER算法对于网络性能的提升。文献[5]针对多数据流并存情况下的流间编码问题提出在NCER路由协议的基础上，根据数据包目的节点的不同，只对目的节点相同的数据或编码包进行编码，有效地解决了多数据流并存时引起的编码向量长度增加的问题，减少了目的节点等待解码的时间。文献[6]针对釆用随机网络编码会存在冗余编码包而带来额外网络开销这一问题，提出了冗余度的概念，利用冗余度来控制编码包的传输，降低了冗余的网络开销。文献[7]针对传统随机网络编码中继节点在某些网络拓扑结构下存在编码无效的问题，提出一种选择有效信息编码的算法，在理论上达到了减少编码时间、降低编码冗余度的目的。文献[8]针对编码包泛洪传输过程中信息冗余大、无效投递较多等问题，设计了基于蚁群算法的编码包路由策略，降低了编码投递过程中的数据冗余，减少投递时延。
在诸如会议场所、校园、智能电话和车载路由器等以人类活动为中心的DTN中，存在小部分中心度高的节点能够和大部分节点进行连接[9-11]，即节点的中心度遵循幂律分布[12]。针对该场景，文献[13]利用幂律分布这一特性，并结合网络编码提出一种新的DTN数据转发机制。该文献主要阐述了Hubcode V1和Hubcode V2两种算法。这两种算法都是只利用中心度高的节点作为消息的中继，并在这些节点上采用随机网络编码来处理到达同一目的地的多条消息。其中，经过对Hubcode V1算法研究后发现，该算法在原理方面仍然存在以下两个突出的缺陷：1) beacon信息包中携带编码系数矩阵进行周期性广播，会带来较大网络开销，消耗较多网络资源；2)目的节点接收到编码包后，必须等到编码系数矩阵满秩后才能进行解码，如果目的节点后续接收到的编码包的长度比先接收到的编码包的长度长时，会影响先前接收到的编码包不能及时解码，从而使得目的节点不能及时获得原始数据包。本文为解决上述两个问题，提出了一种基于解码预判的高效低时延数据传输算法HLDA。
-
文献[13]提出的Hubcode V1算法的主要思想是：每个节点周期性广播含有节点标签和编码系数矩阵的beacon信息包；当源节点与hub节点相遇时，将数据包进行编码传输；当两个hub节点相遇时，将发往同一目的节点的编码包进行再编码，并利用接收到的相遇节点的编码系数矩阵来判断新生成的编码包的线性相关性，线性无关则发送；当hub节点遇到目的节点时，则直接将编码包进行编码发送；目的节点收到足够多的编码包后解码恢复出原始数据包。
Hubcode V1算法有效地提高了投递率，减少了传输开销和端到端时延，具有较好的数据转发性能，但仍存在以下不足：
1) 网络中节点周期性广播含有编码系数矩阵的beacon信息包，会带来较大的网络开销，浪费网络资源；
2) 目的节点接收到编码包后，必须等到编码系数矩阵满秩后才可解码。在目的节点等待接收编码包的过程中，若目的节点后续接收到的编码包的长度比缓存中的编码包的长度长时，会影响缓存中的编码包不能及时解码，等待被解码的时间也随之延长，进而影响数据包的端到端时延。
-
为了解决Hubcode V1算法存在的上述问题，本文提出HLDA算法。HLDA算法提出了3个新机制，分别是单播、广播混合传输机制、减少编码系数矩阵交互机制和hub节点解码预判机制，从而可以降低网络开销和减少端到端时延等。
定义 1 原始数据包序号ID集合I，用来记录编码包中的原始数据包序号ID的集合。hub节点接收到编码包后，记录参与编码该编码包的原始数据包的序号ID，将目的节点相同的原始数据包的序号ID放在同一个集合中。
定义 2 缓存集合C，用来记录节点自身缓存中与其相遇的节点而缓存中没有的原始数据包序号ID的集合。当两个hub节点M、N相遇时，交换彼此beacon信息包中的集合IM、IN，N接收到集合IM后，运算IM与IN，得到节点M缓存中没有而节点N缓存中有的原始数据包序号ID的缓存集合：
$${{C}_{N}}={{I}_{N}}+\overline{{{I}_{M}}}$$ (1) 初始化C=Ø。
定义 3 解码集合D，用来记录目的节点解码出的原始数据包的集合。
定义 4 未解码集合Ti，用来记录第i个编码包中尚未被解码出来的原始数据包的集合。当hub节点与目的节点相遇时，hub节点利用接收到目的节点发送的解码集合D中的信息来对自己缓存中的编码包进行解码判断，将不能从编码包中解码出来的原始数据包进行记录，初始化Ti= Ø。用Ri表示未解码集合Ti中元素的个数，初始化Ri=0。
-
为了解决Hubcode V1算法中beacon信息包的冗余发送带来的开销问题，本文提出单播、广播混合传输机制。该机制将beacon信息包分为必须周期性广播发送的beacon_1和需要时才单播发送的beacon_2两部分，通过发送节点和接收节点对beacon_1和beacon_2的发送时机和发送方式进行额外的判断和管理，避免了不必要的beacon_2信息包在网络上的冗余发送和传输。单播、广播混合传输机制的具体操作步骤如下：
1) 将beacon信息包分为beacon_1和beacon_2两部分并在两种情况下分别进行传输。其中，beacon_1携带节点标签，beacon_2携带集合I；
2) 每个节点周期性广播beacon_1，当接收节点接收到beacon_1时可根据节点标签判断出对方节点是否是hub节点；
3) 当对方节点是hub节点时，则节点将beacon_2单播给对方节点，而不再是广播的形式。
-
为解决Hubcode V1算法中编码系数矩阵交互开销问题，本文提出减少编码系数矩阵交互机制，当两个hub节点相遇后，具体操作步骤如图 1所示。
-45-5-720-1_mini.jpg)
图 1 减少编码系数矩阵交互机制流程图
-
针对Hubcode V1算法中目的节点等待解码时延较长的问题，本文提出hub节点解码预判机制，将越有利于目的节点解码的编码包优先发送给目的节点，减少数据包的端到端时延。具体步骤如下：
1) 当目的节点与hub节点相遇时，目的节点将含有解码集合D的beacon信息包发送给hub节点；
2) hub节点根据解码集合D更新目的节点为对方节点的各个编码包的未解码集合Ti以及Ri；
3) hub节点将min{R1,R2,…,Rk|Ri≠0，i=1,2,…,k}所对应的编码包发送给目的节点；
4) 为了避免将冗余的编码包发送给目的节点，在执行完步骤3)后需要进行“规避冗余”操作，即将步骤3)中发送出去的编码包中的原始数据包序号ID从未解码集合Ti中剔除，并更新Ri。然后继续执行步骤3)，直到全部Ri都为0；
5) 目的节点接收到编码包后先利用已解码出的编码包进行初次解码操作，对于不能解码的编码包进行缓存，等待编码系数矩阵满秩后再进行解码。
-
引理 1 HLDA算法beacon信息包的比特开销小于Hubcode V1算法。
证明：设在网络中任意一个hub节点缓存中编码包的目的节点有k个，其中，到达相同目的节点的编码包有ni(1<i<k)个。这ni个编码包是由mi个不同的原始数据包参与编码，编码系数从伽罗华域F(216)中随机选取，可知编码系数矩阵为的矩阵。
在Hubcode V1算法中，beacon信息包含节点标签和编码系数矩阵两部分内容。其中，节点标签的长度为bits，编码系数矩阵的长度为16bits。
故beacon信息包的总比特开销为：
$$\mathop{T}_{\text{HubcodeV1}}=l+\sum\limits_{i=1}^{k}{16{{n}_{i}}{{m}_{i}}}$$ (2) 而在HLDA算法中，beacon信息包携带节点标签和原始数据包ID集合I。集合I可看成是一个的矩阵，故beacon信息包的总比特开销为：
$$\mathop{T}_{\text{HLNC}}=l+\sum\limits_{i=1}^{k}{16{{m}_{i}}}$$ (3) 显然有：
$$\begin{align} & \mathop{T}_{\text{HubcodeV1}}-\mathop{T}_{\text{HLNC}}=\left( l+\sum\limits_{i=1}^{k}{16{{n}_{i}}{{m}_{i}}} \right)-\left( l+\sum\limits_{i=1}^{k}{16{{m}_{i}}} \right)= \\ & \sum\limits_{i=1}^{k}{16(\mathop{n}_{i}-1)\mathop{m}_{i}} \\ \end{align}$$ (4) $$\left\{ \begin{matrix} \mathop{n}_{i}\ge 1 \\ \mathop{m}_{i}\ge 1 \\ \end{matrix} \right.$$ (5) 由式(4)和式(5)可得：
$$\mathop{T}_{\text{HubcodeV1}}\ge \mathop{T}_{\text{HLDA}}$$ (6) 当只有一个编码包时，上式中的等号才成立。
所以，HLDA算法beacon信息包的比特开销小于Hubcode V1算法。证毕。
-
为了进一步阐明HLDA算法解码预判的有效性，分别对Hubcode V1算法和HLDA算法进行应用分析。简述起见，在该分析中只选择一个hub节点作为描述对象，阐述其与目的节点相遇后在两种算法中分别进行何种操作。
假设hub节点与目的节点相遇，其中hub节点缓存中到达该目的节点的编码包的编码系数矩阵示例如图 2和图 3所示。图中Pj和Xi分别表示编码包和编码包中参与编码的原始数据包。已知目的节点已解码获得了原始数据包X1和X2，缓存中有一编码包为：
-45-5-720-2_mini.jpg)
图 2 Hubcode算法应用举例
-45-5-720-3_mini.jpg)
图 3 HLDA算法应用举例
$${{P}_{7}}={{b}_{1}}{{X}_{1}}+{{b}_{2}}{{X}_{2}}+{{b}_{3}}{{X}_{3}}+{{b}_{4}}{{X}_{4}}$$ (7) 首先，具体阐述Hubcode V1算法的应用过程，如图 2所示。
当hub节点与目的节点相遇后，hub节点将编码包P1、P2、P3、P4先进行再编码操作：
$${{P}_{5}}={{\alpha }_{1}}{{P}_{1}}+{{\alpha }_{2}}{{P}_{2}}+{{\alpha }_{3}}{{P}_{3}}+{{\alpha }_{4}}{{P}_{4}}$$ (8) 然后将编码包P5发送给目的节点。此时，目的节点收到P5后，利用已解码出的X1、X2并不能将缓存中的编码包P7解码获得原始数据包，并且因收到hub节点发送的编码包P5后，由原来只需等待接收一个线性无关的编码包即可解码变为在接收到P5这一编码包后仍需再等待接收一个线性无关的编码包才能解码。
下面利用图 3来分析HLDA算法的应用过程。图 3中用正六边形和圆形标记分别表示hub节点第1次、第2次选择发送的编码包。
首先，hub节点根据自身的编码系数矩阵更新编码包P1、P2、P3和P4的未解码集合为T1={X1,X2}、T2={X1,X2,X3}、T3={X3}、T4={X1,X2,X3,X4,X5}以及R1=2、R2=3、R3=1、R4=5。当hub节点接收到目的节点的解码集合D={X1,X2}后，更新未解码集合T1=Ø、T2={X3}、T3={X3}、T4={X3,X4,X5}以及R1=0、R2=1、R3=1、R4=3。
其次，hub节点将非0的最小R值所对应的编码包P2发送给目的节点，并采取规避冗余措施，更新T1=Ø、T2=Ø、T3=Ø、T4={X4,X5}；R1=0、R2=0、R3=0、R4=2。
然后，hub节点继续选择非0的最小R值所对应的编码包P4发送给目的节点，并更新T1=Ø、T2=Ø、T3=Ø、T4=Ø；R1=0、R2=0、R3=0、R4=0。此时hub节点需要发送的编码包已全部发送完毕。
当目的节点接收到编码包P2后，利用已解码出的原始数据包X1和X2，可将缓存中的P7进行解码获得原始数据包X3、X4；接收到编码包P4后，目的节点利用原始数据包X1、X2、X3和X4对编码包P4进行解码，进而获得原始数据包X5。显然，目的节点第一次接收到编码包P2后，即可解码获得原始数据包X3、X4，比Hubcode V1算法更早获得原始数据包，可以减少目的节点等待解码的时间，进而减少端到端的时延。
-
HLDA算法主要包括编解码和辅助信息交互两部分。假设在网络中传输n个数据包。那么在编解码部分中，编码的计算复杂度为O(n)。由于编码系数矩阵为矩阵，因此解码的计算复杂度为O(n2)。在辅助信息交互部分，集合I和集合D的可能最大长度为n，因此总的beacon交互的计算复杂度为O(n)。在减少编码系数矩阵交互机制中，最坏的情况下，即hub节点缓存中没有携带新信息且编码系数矩阵未满秩，此时两个hub节点之间不得不交互编码系数矩阵，相应的计算复杂度为O(n2)。故HLDA算法的计算复杂度为O(n2)。HLDA算法和Hubcode V1算法在空间复杂度上属于同一级别，都为O(n2)。
-
本文使用网络仿真软件OPNET 14.5进行建模和仿真，仿真实验中用到的主要仿真参数如表 1所示。
表 1 仿真场景的主要参数设置
参数 数值 网络覆盖区域/m2 1 500×300 传输速率/Mbps 54 节点个数 50 hub节点所占比例/% {20,40,60,80,100} 随机种子值 {64,128,256,512,1 024} 仿真时间/s 4 000 -
归一化控制开销是指网络运行时间内累加的所有节点发出的beacon信息包的比特总数与到达目的节点的原始数据包的比特总数的比值，表示为：
$$C=\frac{\sum\limits_{i=1}{\mathop{N}_{i}}}{\sum\limits_{i=1}{\mathop{N}_{i}}+\sum\limits_{i=1}{\mathop{D}_{i}}}$$ (9) 式中，C为归一化控制开销；Ni表示第i个beacon信息包的比特数；Di表示第i个到达目的节点的原始数据包的比特数。仿真结果如图 4所示。
-45-5-720-4_mini.jpg)
图 4 归一化控制开销比较
图 4表明，与Hubcode V1算法相比，HLDA算法能够减少归一化控制开销16.92%以上。开销减少的原因主要有两点：1) 采用单播、广播混合传输机制，减少了beacon信息包的广播次数；2) 将Hubcode V1算法beacon信息包中携带的编码系数矩阵变为原始数据包ID集合I，减少了beacon信息包中的比特开销。
-
数据包平均端到端时延是指所有数据包从源节点到达目的节点的平均时延。其表达式为：
$${{T}_{\text{avg}}}=\frac{\sum\limits_{i=1}{{{T}_{i}}}}{{{N}_{\text{num}}}}$$ (10) 式中，Tavg为数据包平均端到端时延；Ti为第i个数据包到达目的节点的数据包的时延；Nnum为已到达目的节点的数据包总个数。仿真结果如图 5所示。
-45-5-720-5_mini.jpg)
图 5 平均端到端时延比较
图 5表明，与Epidemic算法和Hubcode V1算法相比，HLDA算法消息的平均端到端时延至少减少了3.35%，这是因为当hub节点与目的节点相遇时，HLDA算法采用hub节点解码预判机制，充分利用目的节点已经解码出的原始数据包，将能够解码出全部或者部分原始数据包的编码包优先发送至目的节点，使得目的节点尽早获得原数据包，并且缩短目的节点未解码的编码包的长度，减少了编码包的传输次数。
-
在本文采用的网络模型中，选取连通度高的节点作为hub节点来担任全网消息中继的角色，为阐明hub节点在全网中的所占比例对消息接收成功率的影响，现将仿真结果分析如下。
接收成功率是指消息成功达到目的节点的个数占全网中源节点发送消息总数的比例，其值为：
$$R=\frac{D}{S}$$ (11) 式中，R表示接收成功率；D表示已到达目的节点的原始数据包的个数；S表示源节点发送的原始数据包的个数。仿真结果如图 6所示。
-45-5-720-6_mini.jpg)
图 6 接收成功率比较
从图 6中可知，当hub节点占到全网20%左右时，HLDA算法和Hubcode V1算法的接收成功率最高，但超过20%后接收成功率则随着hub节点所占比例的增加反而会降低。这是因为在全网中hub节点所占的比例越大，编码包在各个hub节点上分散的越多，hub节点将编码包投递给目的节点的机会随之减少。
-
本文针对编码节点受限的数据转发机制存在的网络开销大和解码时延较长等问题，提出一种基于解码预判的高效低时延数据传输算法HLDA。新算法提出3个新机制，分别为单播、广播混合传输机制、减少编码系数矩阵交互机制和hub节点解码预判机制。仿真结果表明，该算法能够有效降低网络开销，减少数据包的端到端时延。
A High-efficiency and Low-Delay Data Transmission Algorithm in DTN Based on Decoding Anticipate
-
摘要: 针对延迟容忍网络（DTN）中编码节点受限的数据传输机制（Hubcode）存在网络开销大、解码时延长的问题，该文提出一种基于解码预判的高效低时延数据传输算法（HLDA）予以解决。HLDA算法提出了hub节点解码预判新机制以减少数据包的端到端传输时延。通过提出单播、广播混合传输新机制减少beacon信息包的广播次数，从而减少网络开销；并提出减少编码系数矩阵交互机制，更进一步地减少网络开销。仿真结果表明，该算法能够有效降低网络开销，减少端到端的时延。Abstract: A high-efficiency and low-delay data transmission algorithm based on decoding anticipate (HLDA) is proposed to address the problems that there exist large overhead for broadcasting beacon which carrys coding coefficient matrix and the destination nodes wait a long time to decode in the hub-based forwarding using network coding in delay tolerant networks(DTN). The HLDA proposed a new mechanism of anticipating decoding by hub nodes is presented in HLDA to decrease the end-to-end delay and proposed a unicast and broadcast mixing mechanism to decrease the overhead. By decreasing the coding coefficient matrix interaction mechanism to further reduce overhead. Simulation results show that HLDA can reduce the overhead and average end-to-end delay as compared to the Hubcode.
-
Key words:
- decoding anticipate /
- DTN /
- hub relay /
- network coding /
- overhead
-
表 1 仿真场景的主要参数设置
参数 数值 网络覆盖区域/m2 1 500×300 传输速率/Mbps 54 节点个数 50 hub节点所占比例/% {20,40,60,80,100} 随机种子值 {64,128,256,512,1 024} 仿真时间/s 4 000 
下载: 导出CSV
-
[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks:Overview and challenges[J]. Communications Surveys & Tutorials, 2006, 8(1):24-37. http://cn.bing.com/academic/profile?id=1965396227&encoded=0&v=paper_preview&mkt=zh-cn [2] ZHANG Q, JIN Z, ZHANG Z, et al. Network coding for applications in the delay tolerant network[C]//Proceeding of the 5th International Conference on Mobile Ad Hoc and Sensor Networks. Fujian, China:IEEE, 2009:376-380. [3] TRACEY H O, MEDARD M, KOETTER R, et al. A random linear network codig approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10):4413-4430. doi: 10.1109/TIT.2006.881746 [4] LIN Y, LIANG B, LI B. Performance modeling of network coding in epidemic routing[C]//Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking. San Juan, Puerto Rico:ACM, 2007:67-74. [5] 白云飞. 基于链路代价综合评估和网络编码的延迟容忍网络路由优化研究[D]. 北京:北京邮电大学, 2012. http://cdmd.cnki.com.cn/article/cdmd-10013-1012499251.htm BAI Yun-fei. Research on delay tolerant network routing optimization based on syntheticl estimation of contact metrics and network coding[D]. Beijing:Beijing University of Posts and Telecommunications, 2012. http://cdmd.cnki.com.cn/article/cdmd-10013-1012499251.htm [6] ZHAO B, PENG W, SONG Z, et al. Towards efficient and practical network coding in delay tolerant networks[J]. Computers & Mathematics with Applications, 2012, 63(2):588-600. http://cn.bing.com/academic/profile?id=1968830405&encoded=0&v=paper_preview&mkt=zh-cn [7] 王琦, 李佶恒, 赫云祥, 等. 利用线性相关优化随机网络编码中继节点算法[J]. 合肥工业大学学报, 2014, 12(37):1446-1450. http://www.cnki.com.cn/Article/CJFDTOTAL-HEFE201412008.htm WANG Qi, LI Ji-heng, HE Yun-xiang, et al. An optimization algorithm of random linear network coding for relay node by linear correlation[J]. Journal of Hefei by University of Technology, 2014, 12(37):1446-1450. http://www.cnki.com.cn/Article/CJFDTOTAL-HEFE201412008.htm [8] 邓广宏, 曹万华, 张剑, 等. DTN网络环境下基于蚁群算法的数据编码分[J]. 电子学报, 2014, 8(32):1636-1641. http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201408028.htm DENG Guang-hong, CAO Wan-hua, ZHANG Jian, et al. Data dissemination mechanism with network coding based on ant colony algorithm in DTN environment[J]. Chinese Journal of Electronics, 2014, 8(32):1636-1641. http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201408028.htm [9] HUI P, CHAINTREAU A, SCOTT J, et al. Pocket switched networks and human mobility in conference environments[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. NewYork, USA:ACM, 2005:244-251. [10] ZHANG X, KUROSE J, LEVINE B N, et al. Study of a bus-based disruption-tolerant network:Mobility modeling and impact on routing[C]//Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking. Canada:ACM, 2007:195-206. [11] HSU W, HELMY A. On modal encounter patterns in wireless LAN traces[C]//The 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. Boston:IEEE, 2006:1-10. [12] HUI P, CHAINTREAU A, SCOTT J, et al. Pocket switched networks and human mobility in conference environments[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. NewYork, USA:ACM, 2005:244-251. [13] AHMED S, KANHERE S S. Hubcode:Hub-based forwarding using network coding in delay tolerant networks[J]. Wireless Communications and Mobile Computing, 2013, 13(9):828-846. doi: 10.1002/wcm.v13.9 -
点击查看大图
-45-5-720-1.jpg)
图(6) / 表(1)
计量
- 文章访问数: 4016
- HTML全文浏览量: 1266
- PDF下载量: 153
- 被引次数: 0
