喷泉编码在DTN网络中的应用研究

徐键卉，杜昊阳，雷旺春，王青媛

(解放军理工大学 通信工程学院，江苏 南京210007)



喷泉编码在DTN网络中的应用研究

徐键卉，杜昊阳，雷旺春，王青媛

(解放军理工大学 通信工程学院，江苏 南京210007)

摘要：DTN(Delay and Disruption Tolerant Networks)的间歇连通性以及数据包易丢失的特性给数据传输带来了很大挑战。针对这一问题，大量的研究表明[1-3]在DTN中使用网络编码能有效提升其数据传输能力，但网络编码的使用又会带来较高的复杂度和较大的编码时延,以及更高的能量消耗。指出将喷泉码应用于DTN网络可以有效克服上述问题，并对目前喷泉码在DTN网络的研究现状做了分析与总结。

关键词：网络编码；喷泉编码；DTN网络；编译码复杂度；传输延迟

0引言

DTN网络是为处理受限网络中频繁网络断开、高延时和异构性等问题而提出的一种覆盖型网络架构，是一种针对端到端连接和结点资源受限时的网络解决方法，以满足随机性的异步消息的可靠性传递[1]。对DTN的研究将会对未来军事战争、深空通信以及应急抢险等领域提供重要的科学依据[2]。

DTN网络的上述特点使得网络中节点间转发机会变得极其稀缺与重要,因此在提高网络吞吐量的同时尽量减少数据传输次数,成为了DTN网络研究的重点内容[3]。而事实证明通过在信源处数据分块后进行网络编码、在信宿处进行数据译码的方法，可以在较少的传输次数下达到较高的网络吞吐量。但是同时该方法带来较高的复杂度和较大的编码时延,以及更高的能量消耗。而喷泉码的优势在于：① 可以像其他网络编码一样有效提升系统吞吐量；② 较低的编译码复杂度将有效减少编译码时延；③ 无须反馈的特点又大大减小了传输时延；④ 无速率的特性使得其对复杂信道具有良好的适应能力[4]。

1DTN网络

1.1DTN网络简介

DTN网络最初来源于IPN(Interplanetary Internet)通信中遇到的问题，并于2003年由K.Fall等人作为正式网络概念提出。初衷是尽力使得数据在地球与很远距离的星空间的通信就好像地球上任何2个地方通信一样简单。之后这一概念被广泛应用于野生动物监测传感网络、移动车载网、战术通信网、口袋交换网、水下传感器网、乡村通信网络和空间光通信网等一系列“受限网络(challengednetworks) ”。

由于传统的TCP/IP协议的因特网服务模型基于以下假设[5]：① 在通信持续的时间里，信源和信宿之间必须存在端到端路径；② 节点间通信的最大往返时间不能太长；③ 丢包率较小等。因此单是对于太空通信这种高延迟、和高中断率的链路来说，就足以说明TCP/IP协议不再实用于DTN网络。

为了克服TCP/IP协议的不足，DTN网络利用位于传输层和应用层之间的Bundle层通过持久存储来应对网络的频繁中断以及高时延问题，包括逐跳的可靠数据传递以及路径的选择。可见，Bundle层是一个端到端的面向消息的网络覆盖层，在这种机制中,发送方在发送Bundle包的同时会开启一个等待确认的定时器。若下一个结点正确接收到Bundle包,则返回一个成功的信号给发送方;否则将不做任何反应,并且等待超时后发送方重传该Bundle包[6]。

这种利用中间结点的“存储-运载-转发”技术，的确可以在链路不存在的时候将信息缓存下来，然后等待时机再次传输，但是当出现丢包或传输出错的现象时，它的这种“确认重传”机制无疑会造成更大的传输延迟，从而降低了数据信息传输的有效性和可靠性。

1.2DTN网络的路由协议研究

在DTN网络中，一个很关键的问题就是路由问题。而在DTN体系结构中，路由是在Bundle层完成的。由于网络连接经常断开和巨大的延迟，传统的Internet中的路由协议在 DTN 中基本不可用，因此有必要研究针对DTN网络特性的路由。

因为极大部分的DTN网络中各个节点的运动是随机的,无法对其未来的运动轨迹进行准确的预测与计算,所以对DTN路由算法的研究主要集中于随机性路由，主要分为以下4类[7]。

(1)基于扩散的DTN路由

该路由协议的核心思想是,当网络中的某节点接收到信息后，将其复制转发给通信范围内的所有其他节点，所以该路由又被称为“传染病路由”。此路由算法无须了解网络的任何先验知识,实现较为简单,但消耗较高的网络资源。

(2)基于机会链路代价评估的DTN路由

与扩散路由相比,该路由协议的特点是：中间节点不再是简单的复制转发，而是需要对通信范围内的每一条机会链路进行转发代价的评估，从而决定是直接对数据进行复制转发还是等待最优路径出现后再复制转发。

(3)基于构建移动模型的DTN路由

通常情况下，DTN网络中的节点经过一系列运动过后,其运动轨迹都会呈现出一定的规律性，并不能说成完全随机的运动，所以对DTN网络中节点的运动轨迹构建相应的移动模型有一定的研究价值。

(4)基于网络编码的DTN路由

在信源处进行数据分块并进行网络编码、在信宿处进行数据译码的方法，可以在较少的传输次数下达到较高的网络吞吐量。虽然该方法有上述优点，但网络编码的使用通常会带来较高的复杂度、较大的编码时延以及更高的能量消耗。

2喷泉编码

1998年Luby等人为了解决大规模数据分发以及可靠传输的问题，首次提出了数字喷泉的概念。该概念的思想是将被传输的数据进行编码，形成“一粒粒水滴”，接收端只须接收到足够的“水滴”便可以高概率译码，而不用去考虑具体接收到了哪些“水滴”。2002年Luby提出了第一种实用的喷泉码—LT码(Luby transform code);2006年Shokrollahi在LT码的基础上提出了一种性能更优的Raptor码，目前，一种由Digital Fountain公司设计的系统Raptor码已经被DVB-H标准和3GPP组织的多媒体广播和组播业务(MBMS)标准采用，并且正在参与其他多项国际标准的制定。2011年Luby等人再次提出了一种伽罗华域GF(256)的Raptor码，称为RaptorQ码[8]，在译码开销接近于零的情况下可以将误码率降低到10-7以下，并且可以支持更多信息分组的编码传输，随之而来的缺点是较高的编译码复杂度。

2.1喷泉码的性能评估

喷泉码性能的好坏决定于以下因素[9]：

定义1：度分布(degree distribution)：表示喷泉码编码过程中形成每个编码包所需要选取的数据包的个数，是决定喷泉码性能优劣的重要指标。

定义2：编码复杂度(encoding complexity)：生成编码分组时所需计算的操作次数。

定义3：译码复杂度(decoding complexity)：成功译码时所需计算的操作的次数。

定义4：译码开销(overhead)：定义为ε=m/k-1，其中m为成功译码时所需要接收的数据包个数，k为输入端参与形成编码包的所有数据包个数。

2.2LT码

LT码作为第一种实用的喷泉码，其编码过程(如图1所示)较为简单，下面就某一编码包的产生过程介绍如下：

① 由已定的度分布ρ(d)随机选取一个度值d;

② 从输入端的原始数据包中随机选取d个不同的数据包;

③ 将这d个不同的数据包求异或和，生成该编码包。

图1　LT编码过程

由于喷泉码的无速率性，按照该编码方法可以产生无数的编码包，就像喷泉中有无数“水滴”一样。此时，接收端只要接收到足够的“水滴”便可以高概率译码。

译码方法的选取关乎喷泉码的性能，目前LT码的主要译码方法有BP译码、GE译码(高斯消元法)以及BPML译码。其中，GE译码是矩阵求逆的常用方法,通过对矩阵行(列)变换将矩阵变为上三角或下三角，之后再通过回代来求解每一个未知量，虽然具有较好的误码率性能,但译码复杂度随着码长的增加非线性的增长，只适合码长较短的喷泉码。BP译码即置信传播译码，是一种低复杂度的迭代译码方法，但由于每次迭代译码均需要从度数为1的编码包开始，当不存在这样的编码包时译码便以失败告终，所以其缺点是误码率较高。而BPML译码算法[10]巧妙的结合了二者的优势，不但具有很好的译码性能，而且具有较低的译码复杂度。

由上述分析可知，度分布不仅关系到编码复杂度，而且还关系到LT码的译码成功率，因此如何设计好的度分布对LT码的整体性能至关重要，文献[9]已给出了能够使LT码实现高概率成功译码的鲁棒孤分子度分布,其平均编码复杂度为lnk,其中k为原来的数据包数目。因此,要产生k个数据包大概需要klnk次异或运算,这说明LT码的编码并不具有线性复杂度。

2.3Raptor码

由2.2可知，尽管LT码对度分布进行了精心的设计，但在译码时还需要很大的开销。原因如下[11]：

① 当只有少部分输入数据包未被译出时，随着译码的继续，译码成功的概率增加的越来越缓慢，此时不得不接收更多的编码包，导致译码开销变得更大；

② LT编码包中少量连接度高的包，虽然保证了对所有数据包的良好覆盖，但同时它又造成了可译集的减小，从而降低了译码成功率。

基于上述原因，Raptor码提出了2步编码(如图2所示)的方式[12]:首先，对原始信息进行预编码，一般采用LDPC码或汉明码，然后通过弱化的LT码对数据进行编码并分发。所谓弱化的LT编码是指它生成的编码包不存在连接度较高的包，只通过它无法完整译出原始信息。Raptor码的编码过程的复杂度为O(kln(1/ε)),可见与码长成线性关系，优于LT码。

图2　Raptor编码过程

3喷泉码在DTN中应用的研究现状

3.1网络编码在DTN中的应用

网络编码在提高DTN网络吞吐量以及数据包投递率等方面具有很大优势，文献[13]对其进行了详细的说明并进行了仿真验证。在文献[14]提出一种在网络拓扑以及多播容量动态变化条件下的动态随机网络编码传输方法之前，研究者们通常都假设DTN的网络拓扑为静态或者多播容量已知且不变，很明显这种假设不符合实际情况。此外，文献中指出相比于传统的固定多播率编码方法，动态随机网络编码方法降低了数据的平均传递延迟，提高了数据投递率。需要指出的是虽然文献中提到的方法对提高DTN网络的传输能力具有重要意义，但是相比于对信道具有良好适应性的喷泉码而言，这种方法太过于繁杂，主要表现在为了获取信道速率和信道容量而进行的各种复杂的算法上。

3.2喷泉编码在DTN中应用的研究现状

喷泉码的无速率性对各种复杂信道的适应能力以及很低的编译码复杂度，使得其在DTN网络中的应用有巨大意义。文献[15]中提到，之前采用的固定编码速率的可擦除编码机制中存在一个弊端，那就是为了达到最优的编码速率，设计时会尽量将编码速率的值定的很高，这样一来就会耗费很大的网络资源，比如说带宽。此外，由于实际的信道状况是随着时间改变而改变的，这就需要一种无速率码能够更好的适应信道的复杂变化。最后文献通过仿真证实，将喷泉码应用于DTN网络中在可靠性、传输延迟等方面均取得了非常显著的效果。

此外，喷泉码应用于DTN网络可以大大节约能耗。文献[16]中提到随着车载通信中路车间的频繁通信，所消耗的能量不容小觑，所以从节能和环保的角度考虑，在保证通信质量的前提下，降低车载通信中的能耗具有很大的现实意义。

文中最初的设想是，由于无线信号的衰落随传输距离的增大而指数增加，所以可以通过将一个路边设施的大覆盖区域划分成多个路边设施的小覆盖区域的方法来降低能耗。但这样带来的问题是：① 车辆通过一个路边设施的小型覆盖区域往往不能完全接收到所需要的信息，造成译码失败，这样就需要多个路边设施共同协作，达到正确译码的目的；② 为了保证路边设施向车辆发送的数据包能够被正确的接收，往往通过逐一的发送反馈信息，这无疑增大了控制的复杂度；③ 当某个路边设施向多个车辆广播信息时，为了保证每个车辆可以按顺序正确的接收到所有的数据包，就必须再次增大反馈的信息流以及控制的复杂度。文章指出在传输过程中采用喷泉编码能够有效克服以上问题。具体做法如下：首先，不同路边设施对n个数据包进行喷泉编码得到任意数量的编码包，之后多个路边设施的协作接力将足量的编码包传输给目的车辆，研究表明目的车辆只须接收够任意(1+ε)n(ε为译码开销，一般为0.05到0.1)个数据包，便可以高概率译码；其次，当向多个车辆广播信息时，路边设施可以模糊掉车辆之间的差异，不用为某一车辆传输特定的信息，而任何一个车辆只要收到任意(1+ε)n个数据包，便可以高概率译码。可见，通过对发送信息进行喷泉编码后再传输的方法，可以大大简化路边设施发送信息时的控制复杂度，同时减少反馈信息量，甚至不需要反馈信息。文献最后通过数值计算以及仿真证实：将喷泉码应用于该网络中有效减少了数据包的发送量、从而大大降低了能源消耗。

4结束语

将喷泉码应用于具体的网络中是数字喷泉码在网络环境中的自然扩展，也是当前数字喷泉码研究的一个重要趋势，正引起越来越多的关注。本文介绍了喷泉码和DTN网络的基本概念，指出了喷泉码相比于其他网络编码的优势，对喷泉码在DTN网络中应用的研究现状进行了列举与分析，得出以下结论：① 喷泉码对复杂信道有良好的适应性，非常适合于DTN这种信道条件瞬息万变的网络环境；② 喷泉码不仅可以提高系统吞吐量、数据投递率，同时还可以大大缩短传输时延。

但是目前对于喷泉码在具体网络中的应用研究仍处于起步阶段，现有的研究成果仍是不全面的和零散的，系统性的理论尚未形成，许多方面仍然需要进一步研究[17]：① 对网络整体性能进行规划，研究适合具体网络的喷泉码度分布以及网络编码策略，使网络吞吐量达到最大；② 目前的研究主要局限于基本的网络结构模型如单跳中继网络、多跳中继网络、多信源单信宿网络等，而对于复杂的网络结构模型中喷泉编码的应用方面所做的研究工作甚少；③ 目前研究的喷泉码的应用网络模型中主要局限于译码转发型，而对放大转发型的研究甚少。后者中各信源度分布与总体度分布的关系较为复杂，所以仍然有待对其渐近性能做深入的分析。

喷泉码在具体网络(例如DTN网络)中的应用作为数字喷泉码发展过程中的重要分支，是一种高效的网络传输策略，目前正处于起步和不断完善阶段。随着喷泉码在网络中应用的深入研究，相信其研究成果必将为网络信息理论的发展提供强大的推动力。

参考文献

[1]Yoon S K,Haas Z J.Invited Paper Application of Linear Network Coding in Delay Tolerant Networks[C]∥Ubiquitous and Future Networks(ICUFN),2010 Second International Conference on.IEEE,2010:338 - 343.

[2]Bao J,Zhang S,Zhang J,et al.Secure Efficient Routing Based on Network Coding in the Delay Tolerant Networks[C]∥Software Engineering and Service Science(ICSESS),2014 5th IEEE International Conference on.IEEE,2014:456 - 459.

[3]Zeng D,Guo S,Jin H,et al.Segmented Network Coding for Stream-Like Applications in Delay Tolerant Networks[C]∥Global Telecommunications Conference(GLOBECOM 2011),IEEE,2011:1 - 5.

[4]Mousavi L S M,Jabbehdari S,Yousefi S,et al.File transfer in Vehicular Delay Tolerant Networks using Fountain coding[C]∥Computer and Knowledge Engineering(ICCKE).2013 3th International Conference on,IEEE,2013:121 - 128.

[5]侯君婷.简析DTN网络与传统网络的区别[J].电信快报:网络与通信,2010(4):44-46.

[6]周建国.基于DTN的空间综合信息网络关键技术研究[D].武汉:武汉大学,2013:23-30.

[7]白云飞.基于链路代价综合评估和网络编码的延迟容忍网络路由优化研究[D].北京:北京邮电大学,2012:21-33.

[8]IETF RFC(6330(2011)):RaptorQ Forward Error Correction Scheme for Object Delivery[S],2011：2551-2567.

[9]Luby M.LT Codes[C]∥Proceedings of the 43rd Symposium on Foundations of Computer Science.IEEE Computer Society,2002:271-282.

[10]朱宏鹏,李广侠,冯少栋.LT码的BPML译码算法[J].计算机科学,2009,36(10):77-81.

[11]杜超.深空通信中喷泉码编译码性能研究[D].黑龙江:哈尔滨工业大学,2009:18-22.

[12]Shokrollahi A.Raptor Codes[J].IEEE Transactions on Information Theory,2004,52(6):2551-2567.

[13]Zhang Q,Jin Z,Zhang Z,et al.Network Coding for Applications in the Delay Tolerant Network(DTN)[C]∥Proceedings of the 2009 Fifth International Conference on Mobile Ad-hoc and Sensor Networks.IEEE Computer Society,2009:376-380.

[14]邓广宏,曹万华,张剑,等.DTN网络环境下动态随机网络编码方法[J].通信学报,2014,(2):76-86.

[15]Vellambi B N,Subramanian R,Fekri F,et al.Reliable and Efficient Message Delivery in Delay Tolerant Networks Using Rateless Codes[C]∥ Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking,ACM:2007:91-98.

[16]雷维嘉,陈佳,李世成.一种路-车通信中的喷泉协作节能传输机制[J].重庆邮电大学学报:自然科学版,2012,24(5):559-566.

[17]徐大专,邵汉钦,张小飞,等.数字喷泉码及网络喷泉码的最新进展[J].数据采集与处理,2014,29(3):351-362.

Application of Fountain Code in DTN

XU Jian-hui,DU hao-yang,LEI Wang-chun,WANG Qing-yuan

(College of Communications Engineering,PLA University of Science and Technology,Nanjing Jiangsu 210007,China)

Abstract：DTN poses many challenges on file transferring due to intermittent connectivity and packet loss.To improve file transfer in DTN,lots of research results show that network coding can effectively improve the capability of data transmission.However the use of network coding brings about such problem as high encoding and decoding complexity,long data transmission delay and high energy consumption.This paper presents that fountain code can effectively overcome above-mentioned problems,at the same time,analyzes and summarizes the present research of the application of fountain code in DTN.

Key words：network coding; fountain coding; DTN; encoding and decoding complexity; transmission delay

中图分类号：TN91

文献标志码：A

文章编号：1003-3114(2016)03-110-5

作者简介：徐键卉(1990—)，女，硕士研究生，主要研究方向：卫星通信、喷泉编码。杜昊阳(1990—),男，硕士研究生，主要研究方向：短波通信、信道编码。

收稿日期：2016-01-04

doi:10.3969/j.issn.1003-3114.2016.03.29

引用格式：徐键卉，杜昊阳，雷旺春，等.喷泉编码在DTN网络中的应用研究[J].无线电通信技术,2016,42(3):110-114.