一种基于子树分解的组播线性网络编码算法  

A Multicast Linear Network Coding Algorithm Based on Subtree Decomposition

作　　者：刘宴涛[1] 夏桂阳 徐静[1] 秦娜[1] 

机构地区：[1]渤海大学工学院,辽宁锦州121000

出　　处：《计算机工程》2015年第11期153-159,共7页Computer Engineering

基　　金：国家自然科学基金资助项目(61101129;61227001);山东省航天创新基金资助项目(2014JJ005)

摘　　要：针对拓扑不变网络的单源组播网络编码问题,基于子树分解提出一种新的线性网络编码算法。该算法由线图变换、子树分解、边不相邻路径搜索、全局编码矢量分配和局部编码矢量计算等过程组成。算法输入为满足组播条件的有向无环网络,输出为各边的全局编码矢量和局部编码矢量。在子树分解过程中,子树内部的边不需要编码,只对子树之间的边进行编码。理论分析和仿真实验结果表明,利用子树分解可以降低网络规模以及路径搜索和分配编码矢量的计算复杂度,缩短编码算法的运行时间,因此该算法是一种高效的单源组播网络编码算法。Aiming at network coding for single source multicast networks with fixed topology, this paper proposes a Linear Network Coding （LNC） algorithm based on subtree decomposition. It is composed of five steps：line graph transforming,subtree decomposition, edge disjoint path search, global coding vector assignment and local coding vector calculation. The algorithm starts with input of a Directed Acyclic Graph （DAG） with multicast property, and ends with output of global coding vectors and local coding vectors of each edge. Subtree decomposition is based on such a consideration that there is no need of coding within a subtree but only between subtrees. It is proved by theoretical analyses and experimental results show that, both network scale and complexity of path search and coding are greatly decreased through subtree decomposition,which greatly decreases running time of network coding algorithm. It can draw the conclusion that the proposed algorithm is an efficient algorithm to single source multicast networks.

关 键 词：线性网络编码 有向无环图 线图 子树分解 编码矢量 

分 类 号：TN915[电子电信—通信与信息系统]