基于分层网络拓扑实现分布式的近似理想LT编码的方法

摘要

本发明公开一种基于分层网络拓扑实现分布式的近似理想LT编码的方法：（1）源端把k个数据包广播给各基站；（2）各基站随机选取一个数据包向各第一层中继节点进行广播；（3）各第一层中继节点随机选取一个接收到的数据包：若其已接收过此新数据包或其缓存已满，则丢弃，否则将此新数据包存于缓存中；（4）当各第一层中继节点的缓存中有≥R个数据包时，各第一层中继节点随机选择其中d个数据包异或，并向各第二层中继节点广播异或后的数据包，同时在缓存中删除这d个数据包；（5）各第二层中继节点随机选择两个数据包异或或选取其中一个向接收端发送；（6）接收端对接收到的数据包解码。若成功解码，则结束编码；否则，返回执行步骤（2）。

说明书

技术领域

      本发明涉及一种基于特定分层网络拓扑实现分布式的近似理想LT编码（Luby Transform Codes）的方法。

背景技术

      可删除信道是当今非常重要的一种信道模型，被广泛应用在诸如Internet等现代的通信系统中。由于信道质量、拥塞等因素的影响，经常会发生丢包的现象。通常，为了能够正确无误地传输数据，我们会在发送端和接收端之间建立一条反馈信道。在接收到数据包后，接收端会向发送端发送相应数据包的认证消息。假若发送端没有收到认证消息，它会向接收端请求重发相应的数据包。这种方法虽然不用考虑信道的丢失率，但是当信道的包丢失率非常大的情况下，资源是很浪费的。特别是在多播和广播的场景下，许许多多的反馈信息会使网络变得非常的拥堵，且接收端会收到多余的已经接收过的数据包。

为了解决这个问题，无速率码应运而生。而LT码就是第一种得到实际应用的实现无速率码理念的编码算法。LT码的原理如下：假定发送端有k个数据包，每个数据包都有一个不同的序号来区分。在每次编码之前，首先会根据所谓的强孤子分布μ(d)来取定所编码的度数d（0<d≤k）, 然后在k个数据包中随机选取d个各不相同的数据包进行异或。

，   0<d≤k

其中              

接收端解码先找度数为1的数据包，然后把这些数据包从其参与异或的其他接收到的数据包中减去，再重新找度数为1的数据包。这样的过程一直重复到找不到度数为1的数据包为止，或解码成功，或解码失败并继续接收到来的数据包。

于是，源数据包的信息平均地散布在编码后的数据包中，发送端可以一直不停地发送已编码的数据包，而接收端则持续地接收并不断尝试解码。若解码成功，则通过反馈信道通知发送端已经解码成功，不需要再发送数据包了。由此可见，LT编码可以完全不需要估计信道的状况，但是却最终能够接近香农定义的信道容量。

理论已经证明， LT码不仅有线性的编解码复杂度，而且平均只需要收到总共个数据包就可以成功解码。

如今的城域网以及广域网的网络拓扑已由原来面向连通性的架构发展为面向业务的架构，网络拓扑需要与特定的业务模型结合起来，根据业务提供更可靠、更高效、更具弹性的组网方式。其中，分层的网络架构就是一种非常典型的面向业务的网络拓扑。分层的网络管理方式有利于减轻网络管理人员的负担，广泛应用于政府、电力、广播电视网等几无交互性的场景中。LT码几乎不需要反馈，也不用进行信道估计，却能达到接近理想的信道容量，非常适用于多播以及广播的点对多点的网络拓扑模型中。

然而，现在关于LT码的研究主要集中在在单点进行所有的编码工作，对于分布式的LT码的研究相对比较缺乏。为了降低对于编码端硬件的要求，如何把LT编码的工作分配到各个节点并且又能使编码的性能逼近理想性能，这是一个非常有意义的研究课题。

发明内容

本发明的目的是提供一种新的基于分层网络拓扑实现分布式的近似理想LT编码的方法。

本发明实现其目的所采取的技术方案是：在本发明基于分层网络拓扑实现分布式的近似理想LT编码的方法中，所基于的分层网络拓扑包括一个源端，一个以上基站、一个以上第一层中继节点、一个以上第二层中继节点和一个接收端；

本发明对所述分层网络进行分布式的近似理想LT码编码包括如下步骤：

（1）源端把需要发送的k个大小相同的数据包广播给各个基站，其中k>0；

（2）各基站把收到的k个数据包进行编号，后各基站从k个数据包中随机选择一个数据包向各第一层中继节点进行广播；

（3）各第一层中继节点判断缓存中是否存在已接收数据包，若不存在，则从接收到的新数据包中随机选择由其中一个基站所发送的新数据包存到缓存中；若存在，则将接收到的新数据包存与缓存中的所述已接收数据包进行比对，若第一层中继节点已接收过此新数据包或者其缓存已被占满，则丢弃此新数据包；否则，将此新数据包存储于其缓存中；

（4）当每一个第一层中继节点的缓存中所存储的数据包的个数≥R时，则以概率P选择弱化度分布Ω(d)或以概率1-P选择弱化度分布u’(d)，各第一层中继节点再从各自的缓存中随机选择d个数据包进行异或，然后各第一层中继节点向各第二层中继节点广播异或后的数据包，同时在缓存中删除这d个数据包；其中，

                                 （1）

         （2）

                 （3）

                              （4）

                   （5）

             （6）

                                        （7）

                     （8）

                                  （9）

以上各式中，δ是预设当接收端收到个数据包后解码失败的概率，δ≤1，c是大于0的常数， d表示度数， 0<d≤k；

（5）各第二层中继节点在接收到的数据包中随机选择两个数据包，若所选择的两个数据包的弱化度分布都是Ω(d)，则将该两个数据包进行异或后再向接收端发送；若所选择的两个数据包中的其中一个的弱化度分布是Ω(d)，另一个的弱化度分布是u’(d)，则选择弱化度分布是u’(d)的数据包向接收端发送；若所选择的两个数据包的弱化度分布都是u’(d)，则随机选择其中一个数据包向接收端发送；

（6）接收端将从第二层中继节点接收到的数据包进行解码，若成功解码，则通知源端结束编码过程；否则，返回执行步骤（2）。

进一步地，本发明预先设定源端和基站之间、基站和第一层中继节点之间、第一层中继节点和第二层中继节点之间的信道的数据包丢失率均为0。

进一步地，本发明所述各第一层中继节点的缓存区所能够存储的数据包的个数≤2R。

与现有技术相比，本发明的优点在于：

本发明基于特定的分层网络拓扑，在中间节点上利用弱化的度分布实现分布式的LT编码， 减轻了源端的编码工作量。从最终的接收端看，接收到的数据包近似于在单点上经过理想LT编码的数据包。相比于其他技术，本发明接收端收到的数据包的度分布更加逼近理想的LT编码的度分布。因此，性能也更加优越，即能在接收到尽可能少的数据包的前提下，解码出k个源数据包。

附图说明

图1本发明方法所基于的分层网络拓扑示意图；

图2为使用本发明方法进行编码的性能与理想的LT编码的比较图；其中，本发明的该实施例中，第一层中继节点个数为20、第二层中继节点个数为3和基站个数为5。

图3为本发明方法的流程图。

具体实施方式

如图1所示，本发明方法所基于的分层网络拓扑包括一个源端，一个以上基站、一个以上第一层中继节点、一个以上第二层中继节点和一个接收端。其中，基站和第一层中继节点的数量越多，则编码的性能越接近理想的LT编码。鉴于成本等因素，实际应用中可根据情况选择适当的折中方案。本发明中的度分布是指选择相应的源数据包个数的概率分布，同时各个节点选择包和度数的操作都是互相独立的。为了达到最佳的性能，可以预先设定源端和基站之间、基站和第一层中继节点之间、第一层中继节点和第二层中继节点之间的信道的数据包丢失率均为0。

如图3所示，本发明对所述的分层网络进行分布式的近似理想的LT码编码包括如下步骤：

（1）源端把需要发送的k个大小相同的数据包广播给各个基站，其中k>0。

（2）为了区分不同的数据包以便编解码，各基站把收到的k个数据包进行编号并把编号信息写进数据包的头部，后各基站从k个数据包中随机选择一个数据包向各第一层中继节点进行广播。

（3）各第一层中继节点都有自己的缓存，它们首先会判断缓存中是否存在已接收数据包，若不存在，则从接收到的新数据包中随机选择由其中一个基站所发送的新数据包存到缓存中；若存在，则将接收到的新数据包存与缓存中的所述已接收数据包进行比对。经比对，若第一层中继节点已接收过此新数据包或者其缓存已被占满，则丢弃此新数据包；否则，将此新数据包存储于其缓存中。 为了提高编码的效率，同时降低对硬件配置的要求，缓存的大小可预设为2R，其中，

                              （1）

式（1）中，δ是预设的当接收端收到个数据包后解码失败的概率，且δ≤1；c是大于0的常数。

需要说明的是，当硬件配置的内存较小时，缓存的大小可的预设值可大于等于R且小于 2R。

（4）当每一个第一层中继节点的缓存中所存储的数据包的个数≥R时，则以概率P选择弱化度分布Ω(d)或以概率1-P选择弱化度分布u’(d)。各第一层中继节点根据选择的弱化度分布选定度数d，再从各自的缓存中随机选择d个数据包进行异或，然后各第一层中继节点向各第二层中继节点广播异或后的数据包，同时在缓存中删除这d个数据包。根据上述所选择的弱化度分布具体是Ω(d)还是u’(d)，在异或后的数据包头部中置相应的标志位进行相应标示。其中，

         （2）

                 （3）

                              （4）

                   （5）

             （6）

                                        （7）

                     （8）

                                   （9）

以上各式中，δ是预设当接收端收到个数据包后解码失败的概率，δ≤1，c是大于0的常数， d是度数， 0<d≤k。

（5）各第二层中继节点在接收到的数据包中随机选择两个数据包，若所选择的两个数据包的弱化度分布都是Ω(d)，则将该两个数据包进行异或后再向接收端发送；若所选择的两个数据包中的其中一个采用的弱化度分布是Ω(d)，另一个采用的弱化度分布是u’(d)，则选择采用弱化度分布u’(d)的数据包向接收端发送；若所选择的两个数据包采用的弱化度分布都是u’(d)，则随机选择其中一个数据包向接收端发送；

（6）接收端将从第二层中继节点接收到的数据包进行解码，若成功解码，则通知源端结束编码过程；否则，返回执行步骤（2）。

综上，第一层中继节点采用的弱化度分布结合第二层中继节点的选包规则使得接收端最后收到的数据包的度分布逼近理想LT码的度分布，而在每个节点，包括基站、第一层中继节点和第二层中继节点，相互独立的随机选包最大程度上保证了编码的随机性，从而保证最后的编码性能非常接近理想的LT码。

经过仿真，本发明公开的基于特定分层网络拓扑实现分布式的近似理想LT编码的方法可被证实具有近似LT码的优良性能。针对本发明，仿真可采用matlab软件；仿真参数的设置如下：解码失败的概率δ=0.5，常数c=0.03，基站的个数BS=5，第一层中继节点的个数RS_1=20，第二层中继节点的个数RS_2=3，仿真次数loop=150。上述参数值只是一个实例，当然其也可取其他值，但是基站、第一层以及第二层中继节点个数的选取将影响本发明所述方法的性能：基站和第一层中继节点越多，第二层中继节点越少，性能越好。仿真的性能指标为解码成功的冗余η=(n-k)/k，其中n为解码成功总共需要收到的数据包的个数，k为源数据包的个数。冗余越小，表示更接近信道容量，编码的性能也越好。仿真过程中，k取500到4000之间间隔500的8个值，每个点仿真150次，η取平均值。仿真结果如图2所示，其中X轴表示源数据包的个数k，Y轴表示冗余η。

从图2的仿真结果可以观察到，本发明采用的基于特定分层网络拓扑实现分布式的编码性能已经相当接近理想的LT编码：平均只需要多接收20%左右的冗余数据包就可以成功解码k个源数据包。当k越小，分布式的LT编码性能越接近理想的LT编码。然而，本发明采用的LT编码方法把在源节点进行的所有的的编码工作放在了分布式的节点上进行，减轻了单个节点上的编码工作量，总体性能上接近理想的LT编码。