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

摘要

为了解决适用于多源组播通信的网络编码构造算法存在收敛时间较长的问题,提出一种基于网络编码的确定线性逐层构造算法.在已有研究基础上,利用虚拟信源点进行虚拟试播:首先,根据决策树算法逐层确定获得非满秩局部编码矩阵的节点;然后,重构与该节点对应的上层变换节点的局部编码系数,生成新的编码向量;最后,重传这些编码向量至对应节点,使该节点的局部编码矩阵满秩,从而得到可行的编码方案.在试播过程中允许对出现数据冗余的链路进行修剪枝,以提高带宽利用率.与基于信宿反馈的确定网络编码(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.