CCCN2010报告混沌在网络传输应用层的数字喷泉编码技术中的应用报告人：陈增强报告人：陈增强报告人：陈增强报告人：陈增强单位：南开大学单位：南开大学20102010年年1010月月混 沌 简 介u 混沌是确定性非线性系统所表现的随机混沌是确定性非线性系统所表现的随机行为的总称行为的总称u 它的轨道有界；但却不是固定点，周期它的轨道有界；但却不是固定点，周期轨，极限环或是准周期轨轨，极限环或是准周期轨u 具有具有对初始条件敏感对初始条件敏感, ,内随机性，遍历性内随机性，遍历性等特征等特征 u 出现在自然科学和社会科学的几乎各个出现在自然科学和社会科学的几乎各个领域领域l数字喷泉码产生的背景 l数字喷泉码实现的各个发展阶段l数字喷泉码的研究现状l混沌在数字喷泉码中的应用研究的意义和主要工作混沌在数字喷泉码中的应用研究数字喷泉码产生的背景 因特网上数据的可靠传输已成为人们研究的一个热点问题因特网上数据的可靠传输已成为人们研究的一个热点问题. . 目前目前, , 大多数网络通讯通大多数网络通讯通过运用合适的通讯协议来保证传输的可靠性过运用合适的通讯协议来保证传输的可靠性, , 例如例如TCP/IPTCP/IP协议协议lTCPTCP协议把数据处理成有序的数据包，并利用发送确认信息和重传丢失的数据包的协议把数据处理成有序的数据包，并利用发送确认信息和重传丢失的数据包的方法来保证传输质量。方法来保证传输质量。l引发的问题：服务器的负荷过重引发的问题：服务器的负荷过重, , 网络拥塞，在有些情况下网络拥塞，在有些情况下, , 网络根本没有发送网络根本没有发送反馈信息的条件反馈信息的条件, , 例如有些无线网络和卫星通讯网络例如有些无线网络和卫星通讯网络纠错（删）编码技术（Erasure coding）: 利用冗余信息恢复丢失数据数字喷泉码（Digital Fountain Codes）什么是数字喷泉码？数字喷泉码的编码方法可以由原始数据包生成任意数量的编码包数字喷泉码的编码方法可以由原始数据包生成任意数量的编码包, , 而而接收方只要收到其中任意接收方只要收到其中任意 m m 个编码包个编码包, , 即可通过解码以高概率成功即可通过解码以高概率成功恢复全部原始数据包。一般情况下恢复全部原始数据包。一般情况下, , 这里的这里的 m m 略大于略大于 k , kk , k是原始是原始数据的长度。数据的长度。 数字喷泉码的特点单向传输，不受丢包率影响，纠错能力强单向传输，不受丢包率影响，纠错能力强快速编码和解码算法，具有线性编解码复杂度的新型随机编码方式。快速编码和解码算法，具有线性编解码复杂度的新型随机编码方式。与码率无关与码率无关 ，由原始数据包生成任意数量的编码包，由原始数据包生成任意数量的编码包支持异步接入，且与多种编码技术和传输协议兼容支持异步接入，且与多种编码技术和传输协议兼容应用：多播，并行下载，视频流，无线网络等领域多播，并行下载，视频流，无线网络等领域 数字喷泉码的发展J. Byers, M. J. Byers, M. LubyLuby 1 1等人于等人于1998 1998 年首次提出数字喷泉的概念年首次提出数字喷泉的概念, , 但当时并但当时并没有给出现实可行的喷泉码设计方案。没有给出现实可行的喷泉码设计方案。 M. M. LubyLuby、A. A. ShokrollahiShokrollahi 等人联合等人联合创立了创立了Digital Fountain Digital Fountain 公司公司, , 以推广数字喷泉概念的实际应用。以推广数字喷泉概念的实际应用。2002 2002 年年, M. , M. LubyLuby 2 2 提出了第一种现实可行的喷泉码提出了第一种现实可行的喷泉码LT (LT (LubyLuby transform) transform) 码。在学术理论日渐完善的同时码。在学术理论日渐完善的同时, , 喷泉码也日益受到产业界的关喷泉码也日益受到产业界的关注注, , 获得了越来越多的实际应用。获得了越来越多的实际应用。目前目前, , 一种由一种由Digital Fountain Digital Fountain 公司设计的系统公司设计的系统Raptor Raptor 码码 3 3 已经被已经被DVB- DVB- H H 标准和标准和3GPP 3GPP 组织的组织的 MBMS MBMS 标准采用标准采用, , 并且正在参与其他多项国际标准的制并且正在参与其他多项国际标准的制定。定。数字喷泉码实现的各个阶段Reed-Reed-SolomnSolomn (RS) (RS)码：编码在有限域上的操作限制了生成的编码的数目；对码：编码在有限域上的操作限制了生成的编码的数目；对于数目较大的于数目较大的 k k 和和 m m，其编码算法的复杂性令人望而却步，其编码算法的复杂性令人望而却步 Tornado Tornado 码（码（19981998年）：从严格意义上讲还不是数字喷泉码，因为其每次编年）：从严格意义上讲还不是数字喷泉码，因为其每次编码生成的包的数目是事先确定并固定不变的，这与喷泉码的初衷相悖。但是码生成的包的数目是事先确定并固定不变的，这与喷泉码的初衷相悖。但是它以其稀疏不规则随机二分图和以异或操作来定义边的思想成为了后来的它以其稀疏不规则随机二分图和以异或操作来定义边的思想成为了后来的 LT LT 码和码和Raptor Raptor 码的先驱。码的先驱。 LT LT 码（码（20022002年）：年）：M. M. LubyLuby 提出的提出的 LT LT 码是第一种实用的数字喷泉码码是第一种实用的数字喷泉码, , 具具有简单的编译码方法以及较小的解码开销和编解码复杂度有简单的编译码方法以及较小的解码开销和编解码复杂度, , 为喷泉码的进为喷泉码的进一步发展奠定了基础。一步发展奠定了基础。Raptor Raptor 码（码（20062006年）：年）：A. A. ShokrollahiShokrollahi 设计的设计的 Raptor Raptor 码是目前数字喷码是目前数字喷泉码的最好的实现。生成每个编码包需要的运算量是一个与泉码的最好的实现。生成每个编码包需要的运算量是一个与 k k 无关的常数无关的常数, , 而成功解码而成功解码 m m 个编码包获得个编码包获得 k k 个原始数据包需要的运算量是一个关于个原始数据包需要的运算量是一个关于 k k 的线性函数。的线性函数。数字喷泉码的研究现状研究工作主要分为两个方面：研究工作主要分为两个方面：一方面致力于从理论上分析和提高喷泉码的性能，例如：一方面致力于从理论上分析和提高喷泉码的性能，例如：l提出严格分析提出严格分析LTLT码的模型码的模型66 。l设计了一种优化算法的方法来寻找使设计了一种优化算法的方法来寻找使LTLT码性能最好的度分布码性能最好的度分布77 l从解码算法入手，利用接收到的编码包所含的冗余信息，来提高从解码算法入手，利用接收到的编码包所含的冗余信息，来提高LTLT码的成码的成功解码概率功解码概率 l从理论上验证了用伪随机数发生器实现的从理论上验证了用伪随机数发生器实现的LTLT码的性能和理论上差别不大码的性能和理论上差别不大99l分析在更现实的通信信道环境下，分析在更现实的通信信道环境下，LTLT码和码和RaptorRaptor码的纠删率与编码包长度码的纠删率与编码包长度之间的依赖关系之间的依赖关系1010 。数字喷泉码的研究现状（续）研究工作主要分为两个方面：研究工作主要分为两个方面：另一方面致力于数字喷泉码的应用研究另一方面致力于数字喷泉码的应用研究 ，例如：，例如：lRaptor codesRaptor codes在无线广播系统中的可靠下载在无线广播系统中的可靠下载1212和手机广播网络中的多媒和手机广播网络中的多媒体可靠下载体可靠下载1313中的应用中的应用 l将基于数字喷泉码的协议与基于将基于数字喷泉码的协议与基于TCPTCP协议在拥塞情况下的通信效果进行比较协议在拥塞情况下的通信效果进行比较 l存储系统存储系统14, 14, 视频编码视频编码1515，流媒体技术，流媒体技术1616，无线传感网络，无线传感网络1717等领等领域的应用域的应用 混沌在数字喷泉码中的应用的研究意义和主要工作将混沌应用到数字喷泉码中是一个创新性的想法，目前还没有这方面将混沌应用到数字喷泉码中是一个创新性的想法，目前还没有这方面的研究工作。的研究工作。 选题依据：选题依据：l目前数字喷泉码的编码实现过程中需要用到伪随机数发生器来选择编码目前数字喷泉码的编码实现过程中需要用到伪随机数发生器来选择编码包的度和邻居；包的度和邻居；l混沌本身就是一种复杂的类似噪声的行为，且具有如下特性：（混沌本身就是一种复杂的类似噪声的行为，且具有如下特性：（1 1）时域）时域上为类似随机过程；（上为类似随机过程；（2 2）频域上为宽带非对称连续谱；（）频域上为宽带非对称连续谱；（3 3）对初始值）对初始值的敏感依赖性；（的敏感依赖性；（4 4）具有分形结构。混沌的这些特征非常适合用来设计）具有分形结构。混沌的这些特征非常适合用来设计形式简单，性能好的伪随机数发生器形式简单，性能好的伪随机数发生器 因此，可以用混沌系统的这些特性来帮助确定编码包的度和邻居信因此，可以用混沌系统的这些特性来帮助确定编码包的度和邻居信息息 混沌在数字喷泉码中的应用的研究意义和主要工作（续）混沌在数字喷泉码中的应用的优势：l混沌系统的遍历性的特征，可以帮助编码过程中的原始数据包以更均匀混沌系统的遍历性的特征，可以帮助编码过程中的原始数据包以更均匀的概率被随机选择，使解码的成功概率更高，减小解码开销。的概率被随机选择，使解码的成功概率更高，减小解码开销。 l由于混沌伪随机数发生器形式简单且生成的时间序列是确定性的，可使由于混沌伪随机数发生器形式简单且生成的时间序列是确定性的，可使发送方在向接收方发送了混沌系统的方程和初始条件之后，通过接收双发送方在向接收方发送了混沌系统的方程和初始条件之后，通过接收双方的同步，使接收方自动推算出接收到的各个编码包的度和邻居信息，方的同步，使接收方自动推算出接收到的各个编码包的度和邻居信息，这样就不需要在编码包中放入度和邻居信息，尤其在原始数据包数目大这样就不需要在编码包中放入度和邻居信息，尤其在原始数据包数目大的情况下，可以极大减少传输的消耗，提高信道容量的利用率。的情况下，可以极大减少传输的消耗，提高信道容量的利用率。l目前混沌加密的研究已有良好的基础，如果将数字喷泉码的混沌编码和目前混沌加密的研究已有良好的基础，如果将数字喷泉码的混沌编码和混沌加密巧妙的结合起来，就可以同时实现数据的可靠传输和保密通信。混沌加密巧妙的结合起来，就可以同时实现数据的可靠传输和保密通信。 混沌在数字喷泉码中的应用的研究意义和主要工作研究工作将从形式简单的研究工作将从形式简单的LTLT码的实现入手，以减少解码开码的实现入手，以减少解码开销为目标，选择合适的混沌系统利用到销为目标，选择合适的混沌系统利用到LTLT码的编码过程中，码的编码过程中，在解码过程中利用混沌减少解码成功需要的编码包的数目。在解码过程中利用混沌减少解码成功需要的编码包的数目。p喷泉码：一种迥异于一种迥异于TCP/IPTCP/IP的新颖的信道编码技术；更可靠，的新颖的信道编码技术；更可靠，更省时；丢包率更小更省时；丢包率更小 混沌在数字喷泉编码技术中的应用l发送方：发送方：像水龙头像水龙头 不需要区分各个接收者不需要区分各个接收者l接收方：接收方：像杯子像杯子 不关心接包的顺序，只关心接收的数据不关心接包的顺序，只关心接收的数据包的数目包的数目研究背景研究背景混沌在数字喷泉编码技术中的应用LT码: 第一种真正意义上的喷泉码，现实可行,具有简单的编译码方法以及较小的解码开销和编解码复杂度编码过程：nLT 码的每个编码包的生成步骤： （1）按照事先确定的度分布(d) 为该编码包随机抽样选择度d的值。 （2）以均匀概率从构成源文件的k个数据包中随机选择d个不同的包作为该编码包的邻居。 （3）把这d个邻居的值进行异或操作，得到的值作为该编码包的值。v我们提出了基于Kent 混沌映射的LT 码的编解码算法，巧妙利用混沌序列的随机性和遍历性的特性来替代传统的伪随机数发生器，满足LT 码编码过程中对随机的要求。混沌在数字喷泉编码技术中的应用n一种基于混沌的LTLT码的编解码算法pKent 混沌映射：nLT 码的每个编码包的生成步骤： （1）按照 （2）以特点：（1）对初始条件非常敏感； （2）均匀一致分布混沌在数字喷泉编码技术中的应用n一种基于混沌的LTLT码的编解码算法p编码算法原理（1）编码包的度值的确定：假设构成源文件的输入符号的数目为k ，按照Robust Soliton 度分布函数将(0,1) 这个区间划分成k 个不重叠的长度不等的子区间，并且使每个子区间对应一个度值j （1 j k ）。由于Kent 混沌映射的时间序列的值在（0，1）区间内均匀分布，因此该序列的每个值都会落在其中的某个子区间中，这个子区间对应的度值就可作为一个编码包的度值。（2）编码包的邻居的选取;设已经确定一编码包的度值为d，我们取Kent 映射的一时间序列Y(n)（1 n k ），其长度应为输入符号构成的输入向量的长度，即输入符号的数目k。找出序列Y(n)的前d 个最大值，记录它们在序列中的位置，那么输入向量中与它们位置相同的d 个输入符号就作为该编码包的d 个邻居。混沌在数字喷泉编码技术中的应用n一种基于混沌的LTLT码的编解码算法由伪随机数发生器实现的LT码的传输效率由混沌序列实现的LT码的传输效率混沌在数字喷泉编码技术中的应用p仿真研究结果源文件长度k=1000源文件长度k=2000混沌在数字喷泉编码技术中的应用n一种基于混沌的LTLT码的编解码算法p仿真研究结果由伪随机数发生器实现的LT码的传输效率由混沌序列实现的LT码的传输效率源文件长度k=5000源文件长度解码低效率系数传统伪随机数发生器KENT混沌映射k=10001.1651.095k=20001.1151.079k=50001.0871.065l提出了一种基于混沌的LT码的编解码算法，巧妙使用了混沌序列的随机性，遍历性特征为编码包选择度值和邻居。l仿真结果发现在编码中使用混沌序列替代传统的伪随机数发生器能够提高LT码的传输效率。l并且基于混沌的LT码能够使发送方和接收方更方便有效的通信编码包的度和邻居信息，减小传输消耗。混沌在数字喷泉编码技术中的应用n一种基于混沌的LTLT码的编解码算法p结论：结论：在改进的Robust Soliton 分布中，我们将原度分布中的(i) 和(i) 结合起来，并取消了允许失败概率参数。依据是在仿真研究中，我们发现这个概率只是近似值，而实际的失败概率由参数c 和 共同决定，且比的取值要大。该分布函数只有一个调节参数，便于调节。混沌在数字喷泉编码技术中的应用n一种改进的LT码的Robust Soliton度分布混沌在数字喷泉码中的应用l仿真结果表明这种改进的仿真结果表明这种改进的Robust Robust SolitonSoliton分布具有与原分布具有与原Robust Robust SolitonSoliton分布相当的解分布相当的解码效率，并且能够极大地减少解码所需的运算。码效率，并且能够极大地减少解码所需的运算。