一种二进制删除信道下的喷泉码方法

摘要

本发明是一种二进制删除信道下的喷泉码方法：它对原始数据流进行基础LT码预编码；将编码数据流进行分割处理，按需要分成数个支信息流；对每个支信息流进行基础LT码编码；按预先制定好的路由方案发送各支路信息流；在译码端用最大似然法解码最先到达的支信息流；将经过编译的支信号流按原分割方案进行重组；对重组信息流进行最大似然解码法编译，得到原始数据流，完成了对原始数据的正确完整编译。其方法设计合理，它能基本达到信息传输时机密性、完整性、可用性，也可以保证译码方的正确译码。本发明为信息的安全传输奠定了基础，对编码理论、网络信息安全架构建设具有重大意义。

说明书

技术领域

 本发明属于编码领域，具体地说是涉及一种改进的二进制删除信道下喷泉码的编译码方法。

背景技术

随着互联网及其应用的快速发展，近年来政府、军事以及民用信息的安全传递越发重要。安全信息传输要求信息安全三要素--机密性、完整性和可用性之间相互平衡，达到网络资源的最佳分配，提供必要的网络弹性。网络的弹性通常经由网络节点、链路的冗余，信息重新传输，数据的复制，多样性来实现， 需要牺牲某些资源来达到最佳网络弹性，使得网络在受到自然影响、不确定干扰、甚至蓄意破坏的情况下仍能维持一定质量的服务，同时完成信息安全三要素之间的平衡。

如何通过对信息进行加密编码，使之在无线或有线网络信道受到潜在窃听、信道损坏、信道不稳定的情况下中进行安全传输，已成为近年来的热门研究课题。目前，已有多种编码手段已得到了理论证明和实验考证，实现了一定程度上信息安全的保障。例如，参考文献题目为Protecting Network Coded Packets in Coalition Networks（该文作者是：Soon Y. Oh和Mario Gerla，洛杉矶加利福尼亚大学计算机科学学院，2010年出版在Wireless On-demand Network Systems and Services (WONS), 2010 Seventh International Conference），文献阐述了如何利用网络编码实现对传输过程中各节点的控制，在网络节点不可信任度高达50%、并且信道因遭受不稳定、损坏和堵塞而产生错误传输的严峻情况下提高正确传输成功率；参考文献题目为Wireless Information-Theoretic Security（该文作者是：Matthieu Bloch，Jo?o Barros，Miguel R. D. Rodrigues和Steven W. McLaughlin，2008年出版在期刊：IEEE Transactions on Information Theory），文中提出了根据衰减信道震荡情况产生密钥，在传统通讯系统中添加一层新的加密层，使得单方向数据传输可以在准静态无线信道中得到安全保证，虽然此法可以在很大的SNR范围内提供绝对安全传输，但其算法繁复、对存储的要求非常高；参考文献题目为Secrecy and Reliability Using Raptor Codes in the Presence of a Wiretapper in Multiple Path Wireless Network，（该文作者是：Anna Kacewicz和Stephen B. Wicker，2009年出版在IEEE）,根据信道的擦除概率和所用LT编码数据，计算出可纠正的擦出概率，从而制定相应的路由方案；参考文献题目为Raptor Codes（该文作者是：Amin Shokrollahi and Michael Luby，2009年发表于Foundations and Trends   in Communications and Information Theory）中，对喷泉码及其应用进行了详尽的介绍。

TCP/IP采用重传机制来保证传输的可靠性，但在严重损坏的信道上进行传输（质量很差的无线或卫星链路）或传输距离太长的时候其性能很差，因为将导致发送方等待反馈确认信息时的空闲时间长。另外，当接收者数量很多时，也不太可能估计每个信道的删除概率和丢包情况。数字喷泉码——LT码是Luby于2002年提出的，主要针对大规模数据分发和可靠广播的应用特点而提出的一种理想的解决方案。LT码生成的编码包中有少量连接度很高的包，这些包的作用主要是保证对所有数据包的良好覆盖，从而保证译码的完整性，然而这些高连接度数据包的存在,消耗了很多编译码异或操作，同时也降低了低连接度数据包的比例，从而减小了译码过程中可译集的大小，降低了译码成功率。为了代替高连接度数据包完成对数据的良好覆盖,有效地提高译码成功率并降低编译码复杂度，Shokrollahi提出了Raptor码。Raptor码采用两步编码的方式：第一步，对原始信息用一个分组码进行预编码，然后采用一个弱化的LT码对数据进行编码并发送。

Raptor码同时使用高连接度和低连接度的编码数据包，完成对数据的良好覆盖，有效地提高译码成功率，同时降低了编译码复杂度。在Raptor编码中，弱化的LT码是指它生成的编码包没有高连接度包，无法完全译出原始数据。Raptor码译码时，首先用BP算法对数据进行正常译码。由于弱化LT码能以很高的概率恢复出绝大多数的数据包，因此剩下未被译码的数据包所占的比例就被控制在一个很小的范围以内，这些未被译码的数据不再通过高连接度的编码包来保证覆盖和恢复，而是利用预编码的纠错能力进行恢复。通过联合优化弱化LT码和预编码的码率和参数，Raptor可以获得更低的编译码复杂度，而在相同译码开销下能实现更高的译码成功率。

Raptor解决了基于重传机制的TCP/IP在应用过程中所遇到的问题,但是Raptor对于信息的安全性保障存在缺陷。根据其设计原理，任意接收端或窃听者只要截获足够数量的数据包，即可解码数据窃取信息。

发明内容

本发明所要解决的技术问题是针对现有技术的不足，提供了一种改进了的二进制删除信道下的喷泉码方法；该方示在保持译码可靠性的条件下，获得提高编码效率、降低译码复杂度的信道编码策略。

本发明所要解决的技术问题是通过以下的技术方案来实现的。本发明是一种二进制删除信道下的喷泉码方法，其特点是，其步骤如下：

（1）对原始数据流使用分组码进行预编码操作，c =dG；其中，c为预编码数据包，d为原始数据包，G为生成矩阵，在预编码时选用密度为0.2的稀疏矩阵作为生成矩阵来获得预编码数据；生成矩阵是由众多小稀疏矩阵构成，然后按行与列分别进行洗牌而得到的；

（2）将预编码后得到的数据流进行分割处理，按需要分成数个支信息流；

（3）对每个支信息流按LT码的定义进行编码，LT编码时“度”Ω参数的选取范围是1 < Ω < K；其中，K为原始数据包长度；

（4）按预先制定好的路由方案发送各支路信息流；

（5）在译码端用高斯消元法也即最大似然法解码最先到达的支信息流，d’ =c’/G’，其中，c’为接收到的数据包，d’为LT编码前的数据包， G’为LT编码生成矩阵；

（6）将经过编译的各路支信号流按原分割方案进行重组；

（7）对重组后的信息流进行最大似然解码法编译，得到原始数据流，完成了对原始数据的正确完整编译。

本发明所述的二进制删除信道下的喷泉码方法的步骤（3）中，“度”Ω的优选范围是1 < Ω < 6。这样可以提高译码效率。

本发明所述的二进制删除信道下的喷泉码方法中：步骤（4）所制定的路由方案考虑每段路径的擦除信道概率，保证在物理距离最短且丢包现象避免得最好，优选的路由方案如下：

（1）根据每一段路径的长短，为其相关一个模拟的擦除信道概率Pi=di/d总；其中，Pi是该段路径的擦除概率，di为该路径的长度，d总为收端到发端的直线距离；注意，这里假设的擦除信道是一个根据实际路径长度得到的简单估计，真实的网络布局中，每段路径的擦除概率是不一定的，并且会是事实变动的，所以应该配备更加灵活的路由方案；

（2）将网络中检测到的处于收端和发端之间的节点位置，计算所有可能的路径；这种计算方法属于列举法，比如：只跳一步就能到达收端的路径是“发端-收端”，只跳2步就能到达收端的路径有“发端-某中间节点-收端”，3步到达的路径有“发端-某中间节点-另个中间节点-收端”；需要跳的步数越多，可能的路径越多，算法时间也就越长；

（3）为所有这些路径计算丢包率；即：将第一步所得到的擦除信道概率应用到每段路径中去，计算采用每种可能的路线时的丢包情况；将所有路线的丢包情况进行排序，选择丢包情况最优的前几种方案。

最优路线条数的选择应遵循本发明中所设置的限制（即：排序选择路线时，任意节点被使用次数达到上限时，之后所有经过它的线路都不能被选用）。这样，路由方案就完美地配合了编码方案，达到了数据传输绝对安全保密的效果。

使用该方法编译的数据在进行传输时，配合特定的路由方案可以100%保证信息不被第三方窃听，达到了信息传输的绝对安全；同时，由于采用喷泉码作为编码基础，可以保证译码方的正确译码。

本发明改进的编码方法遵循“预编码-分流-LT编码”思路。本发明中：（1）对原始数据流进行基础LT码预编码，在预编码时选用了密度为0.2的稀疏矩阵来生成预编码数据，生成矩阵由众多小稀疏矩阵构成，然后按行与列分别进行洗牌。详细方法可参见2009年Luby在Foundations andTrends in Communications and Information Theory发表的文章Raptor Code。（2）将预编码数据流进行分割处理，按需要分成数个支信息流，每个支信息流后续将对应一条支路进行传播。如图1所示，是一个具有多节点的网络中使用本发明的编译码方案模型。在本网络中，数据可经由中间节点从数据源发送到目标地。经过预编码的K_pre比特数据包被分为5路，分割后的数据包分别为SplitC比特和SplitD比特。这两路数据包将会分别接受后续LT编码处理，并经由不同的物理路径传送出去。

对于复杂的网络，需要事先确定将要使用的路径数，然后依此确定相应的分割数。为了保证接收端数据的可还原性，并且保证网络中其它任何节点不能破译出原始数据，分割数据包Split必须小于K_original=100比特。这是由于如果编码数据包不大于原始数据包长度，就无法还原出原始数据包，且其还原结果在数学上将会有无数个解。

另外，可对原始预编码数据包进行多一些的分割，设置稍微多一些的发送支路来对它们一一传送。这样当接收端最早接收到的几个分割数据包中数据总长度超过了K_original，不必等接收到所有支路数据包就可开始解码。如图中，分割后每路数据包长度为40比特，则在接收端，根据最先收到的3个子数据包（即收到40比特x3=120比特的预编码数据包），即可解码原数据包。这样的设置可以保证在网络中某些节点或支路出现故障时接收端仍然能尽可能快地收取足够多数据来译码原数据。因此，实际支路数（分割数）可以大于所必需的支路数（分割数）。

而当网络分布较为复杂时，传播路径数确定后，分割后的数据包如果制定了大小限制为Split_min到Split_max比特（Split_max<K_original），则在制定传播路线时，须确定每个网络中的节点都不得被使用超过?K_original/Split_max?次，以保证任何网络中间结点都不能解码获得原始数据；

与现有技术相比，本发明所述的一种改进的二进制删除信道下的喷泉码方法设计合理，它能基本达到信息传输时机密性、完整性和可用性的100%安全保证。使用该算法编译的数据在进行传输时，配合适当的路由方案可以100%保证信息不被第三方窃听，达到了信息传输的绝对安全；同时，由于采用喷泉码作为编码基础，可以保证译码方的正确译码。本发明为信息的安全传输奠定了基础，对编码理论、网络信息安全架构建设具有重大意义。

附图说明

图1为编译码示例模型；

图2为简单传输信道模型；

图3为编译码及传输流程示意图；

图4为复杂传输信道模型；

图5为模型的运行结果图;

图6展示的是优化后的路由方案。

具体实施方式

以下参照附图，进一步描述本发明的具体技术方案，以便于本领域的技术人员进一步地理解本发明，而不构成对其权利的限制。

实施例1，一种二进制删除信道下的喷泉码方法，其步骤如下：

（1）对原始数据流使用分组码进行预编码操作，c =dG；其中，c为预编码数据包，d为原始数据包，G为生成矩阵，在预编码时选用密度为0.2的稀疏矩阵作为生成矩阵来获得预编码数据；生成矩阵是由众多小稀疏矩阵构成，然后按行与列分别进行洗牌而得到的；

（2）将预编码后得到的数据流进行分割处理，按需要分成数个支信息流；

（3）对每个支信息流按LT码的定义进行编码，LT编码时“度”Ω参数的选取范围是1 < Ω < K；其中，K为原始数据包长度；

（4）按预先制定好的路由方案发送各支路信息流；

（5）在译码端用高斯消元法也即最大似然法解码最先到达的支信息流，d’ =c’/G’，其中，c’为接收到的数据包，d’为LT编码前的数据包， G’为LT编码生成矩阵；

（6）将经过编译的各路支信号流按原分割方案进行重组；

（7）对重组后的信息流进行最大似然解码法编译，得到原始数据流，完成了对原始数据的正确完整编译。

实施例2，实施例1所述的二进制删除信道下的喷泉码方法中：步骤（3）中，“度”Ω的选取范围是1 < Ω < 6。

实施例3，实施例1或2所述的二进制删除信道下的喷泉码方法中：步骤（4）所制定的路由方案考虑每段路径的擦除信道概率，保证在物理距离最短且丢包现象避免得最好，具体的路由方案如下：

（1）根据每一段路径的长短，为其相关一个模拟的擦除信道概率Pi=di/d总；其中，Pi是该段路径的擦除概率，di为该路径的长度，d总为收端到发端的直线距离；

（2）将网络中检测到的处于收端和发端之间的节点位置，计算所有可能的路径；

（3）为所有这些路径计算丢包率；即：将第一步所得到的擦除信道概率应用到每段路径中去，计算采用每种可能的路线时的丢包情况；将所有路线的丢包情况进行排序，选择丢包情况最优的前几种方案。

实施例4，二进制删除信道下的喷泉码方法实例：

如图2所示，为一个简单的传输信道模型。A点和B点分别为发送端和接收端。C、D两点为中转节点，也即模拟的窃听者。每段信道都有一个二进制删除信道概率，记为                                               。发送端A点的数据流分两路到达接收到B点。 SHAPE  \* MERGEFORMAT 

本实例的编码方案遵循“预编码-分流-LT编码”思路，在Raptor码的基础上引进了分流操作。具体流程如图2所示。

（1）如图3， SHAPE  \* MERGEFORMAT K_original比特为要传递的数据包，首先，该数据包被预编码。在预编码时选用了密度为0.2的稀疏矩阵来生成预编码数据，生成矩阵由众多小稀疏矩阵构成。K_original被扩大为K_bit比特。预编码的码率，结合分发支路数量，有严格的限制。即预编码后的数据包，要求长度K_pre满足:

K_original<K_pre<K_original*(L-1)

其中，L为支路数, 预编码码率最小值为1/L。

（2）将K_bit分流，得到长度分别为SplitC比特和SplitD比特的两个子数据包, 因一串长为K_original的数据包不能被长度比它短的数据包译码，所以预编码后分割出的每个支路数据包长度不得超过K_original，即SplitC和SplitD最大值为K_original-1比特。

（3）对SplitC比特和SplitD比特这两个子数据包进行LT编码，长度变为TxC比特和TxD比特。为了提高译码效率，在本发明中“度”Ω的最终选取范围是1 < Ω < 6。

（4）在二进制删除信道中，数据包收到损耗丢失，到达中转站C、D两点时，子数据包长度衰减为EvsC比特和EvsD比特。中转C和D点无权对经过的数据进行任何操作，直接将子数据包再转发到B点，最终接收端B收到的两个子数据包分别为RxC比特和RxD比特。

（4-1）根据每一段路径的长短，为其相关一个模拟的擦除信道概率Pi=（di/(d总)）。其中，Pi是该段路径的擦除概率，di为该路径的长度，d总为收端到发端的直线距离。

（4-2）将网络中检测到的处于收端和发端之间的节点位置，计算所有可能的路径。这种计算方法属于列举法，本网络中一共有3条路径：A-B、A-C-B和A-D-B。注意，本网络示例中网络为正方形，C、D两点距发送端A点距离相同，故不可返回跳步，不会出现A-C-D-B或A-D-C-B的路线情况。另，一般网络中发送端和接收端相距都很远，所以A-B这种情况一般也不会出现，最终确定传播路线只有A-C-B和A-D-B两条。

（4-3）为所有这些路径计算丢包率。即：将（4-1）所得到的擦除信道概率应用到每段路径中去，计算采用每种可能的路线时的丢包情况。由于?K_original/Splt_max?=1，即每个中间节点不得使用超过1次。再将所有路线的丢包情况进行排序，选择出丢包情况最优的2种路由方案，在本发明中也即唯一的两条。

（5）最后，从两个支路ACB和ADB将编码完成的子数据包发往接收端B点。在接收端，对两个子数据包分别进行LT译码。用最大似然法（即高斯消元法）解码最先到达的2支信息流,本发明在实现的过程中采用了“平均分布编码+高斯消元法译码”;

（6）将经过编译的支信号流按原分割方案进行重组；

（7）对重组信息流进行最大似然解码法编译，得到原始数据流，完成了对原始数据的正确完整编译。

在以上过程中，LT码的码率可以无限小，接近于零。这样即使信道遭受严重损坏导致数据大幅丢失，也依然可以保证接收端能够译码。这一特性是继承了喷泉码的译码优越性。但是考虑到LT译码的复杂性和系统性能功耗，可以根据对于信道情况的预估，调整相应的码率，在尽量减少系统功耗的情况下保证LT成功译码。LT成功译码对于整体译码具有重要作用。

将传输信道模型复杂化，如图4是一个具有10个网络节点的模型。点1和点10分别为发送端和接收端，其它的中间节点都是潜在的窃听者。

在这个复杂的模型中，假设一共分类出n个子数据包，从n条支路发送，n<L。为了尽量减少因信道堵塞而引起的延迟，提高传输效率，预编码码率可以更加小，这样在接收端不需要接收到所有n个子数据包就可以进行译码，即设置n>L。至此，接收端可以对发送端发送通知，让其停止发送当前数据包，开始发送下一个数据包。

在这种情况下，虽然每个支路的数据包能保证不被任一中间节点解码出原始数据，但如果某个窃听者截获多个子数据包，则有可能得到足够多的数据来解译原数据。为保证网络中的每个数据节点，不能有机会接触足够多个子数据包。

对于路由方案的确定，根据事先掌握网络中各节点的位置和信道情况，在发送数据前确定好发送路径，保证所经过的每个中转节点只会接手到有限个子数据包。这种关于网络的统计和预估，可以是周期性的，周期越短，发送效率越高，处理机也就越复杂。

使用该算法编译的数据在进行传输时，配合特定的路由方案可以100%保证信息不被第三方窃听，达到了信息传输的绝对安全；同时，由于采用喷泉码作为编码基础，可以保证译码方的正确译码。

图5为用Matlab软件制作模型的运行结果。该模型中，最少3个子数据包就可以还原出原始数据，设定需要路径为5条以便选取最先到达的3个子数据包，提高译码效率和性能。如图5，网络结点一共有10个,点1和点10分别表示发送端和接收端。根据各个链路的擦除信道以及各结点的地理位置，最终确定了5条路径，由运行结果可见，排名最优的路径开销最小，但是受到信道擦除概率的影响，物理距离最短的并不一定是最优路径。

图6展示的是优化后的路由方案。这种方案对落在虚线外的网络节点采取屏蔽措施，只考虑地理位置处于发送端和接收端之间的结点，从而提高了计算路由方案时的效率，避免了对于较远网络结点的考虑。

以上运行结果表示出本发明对于数据完整传输处理过程的优越性和可靠性。由图可见，开销控制在10%左右，最优时可达1%以内，非常高效。可见，发送端在对网络情况进行估计后，可以对整个编译码方案进行综合平衡，在保证可译码性和完整性的同时，快速地将数据绝对可靠地传输给目标地址。