Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering

Previous Articles     Next Articles

A Multicast Linear Network Coding Algorithm Based on Subtree Decomposition

LIU Yantao,XIA Guiyang,XU Jing,QIN Na   

  1. (College of Engineering,Bohai University,Jinzhou 121000,China)
  • Received:2014-08-18 Online:2015-11-15 Published:2015-11-13

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

刘宴涛,夏桂阳,徐静,秦娜   

  1. (渤海大学工学院,辽宁 锦州 121000)
  • 作者简介:刘宴涛(1975-),男,副教授、博士,主研方向:Ad Hoc网络,网络编码,网络仿真;夏桂阳、徐静、秦娜,硕士研究生。
  • 基金资助:
    国家自然科学基金资助项目(61101129,61227001);山东省航天创新基金资助项目(2014JJ005)。

Abstract: 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.

Key words: Linear Network Coding(LNC), Directed Acyclic Graph(DAG), line graph, subtree decomposition, coding vector

摘要: 针对拓扑不变网络的单源组播网络编码问题,基于子树分解提出一种新的线性网络编码算法。该算法由线图变换、子树分解、边不相邻路径搜索、全局编码矢量分配和局部编码矢量计算等过程组成。算法输入为满足组播条件的有向无环网络,输出为各边的全局编码矢量和局部编码矢量。在子树分解过程中,子树内部的边不需要编码,只对子树之间的边进行编码。理论分析和仿真实验结果表明,利用子树分解可以降低网络规模以及路径搜索和分配编码矢量的计算复杂度,缩短编码算法的运行时间,因此该算法是一种高效的单源组播网络编码算法。

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

CLC Number: