基于网络编码的确定性逐层构造算法  

Deterministic layered construction algorithm based on network coding

作　　者：徐光宪[1] 赵越 赖俊宁 

机构地区：[1]辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛125105

出　　处：《计算机应用》2018年第3期769-775,共7页journal of Computer Applications

基　　金：国家科技支撑计划项目(2013BAH12F02);辽宁省高等学校杰出青年学者成长计划项目(LJQ2012029)~~

摘　　要：为了解决适用于多源组播通信的网络编码构造算法存在收敛时间较长的问题,提出一种基于网络编码的确定线性逐层构造算法。在已有研究基础上,利用虚拟信源点进行虚拟试播:首先,根据决策树算法逐层确定获得非满秩局部编码矩阵的节点;然后,重构与该节点对应的上层变换节点的局部编码系数,生成新的编码向量;最后,重传这些编码向量至对应节点,使该节点的局部编码矩阵满秩,从而得到可行的编码方案。在试播过程中允许对出现数据冗余的链路进行修剪枝,以提高带宽利用率。与基于信宿反馈的确定网络编码(SNFDNC)算法相比,该算法只需进行一次虚拟试播。仿真测试结果表明该算法在中等规模网络中收敛时间更短,能进一步提高多源组播通信的平均传输速率。To solve the problem that the construction algorithm of multi-source multicast network coding costs long convergence time, a deterministic layered construction algorithm based on network coding was proposed. On the basis of existing studies, a virtual source was used for virtual trial. Firstly, the nodes with non-full rank local coding matrix were determined layer-by-layer by decision tree algorithm. Then, the local encoding coefficients of the upper transform nodes were reconstructed and a new encoding vector was generated. Finally, the new encoding vector was transmitted to the lower node corresponding to it, and the local coding matrix of the lower node was full rank, so a feasible coding scheme was obtained to realize network coding. Moreover, when redundant data is found in some links, pruning branches method was implemented to improve bandwidth utilization. The algorithm only needs one virtual trial multicast in comparison with the Sink Nodes Feedback Deterministic Network Coding （ SNFDNC）, and the simulation results show that the convergence time of the proposed algorithm is shorter in the medium scale network, and the average transmission rate of multicast communication is further improved.

关 键 词：网络编码 确定性网络拓扑 多源组播 逐层构造 决策树算法 收敛时间 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]