计算机工程
計算機工程
계산궤공정
Computer Engineering
2015年
11期
153-159
,共7页
刘宴涛%夏桂阳%徐静%秦娜
劉宴濤%夏桂暘%徐靜%秦娜
류연도%하계양%서정%진나
线性网络编码%有向无环图%线图%子树分解%编码矢量
線性網絡編碼%有嚮無環圖%線圖%子樹分解%編碼矢量
선성망락편마%유향무배도%선도%자수분해%편마시량
Linear Network Coding (LNC)%Directed Acyclic Graph (DAG)%line graph%subtree decomposition%coding vector
针对拓扑不变网络的单源组播网络编码问题,基于子树分解提出一种新的线性网络编码算法.该算法由线图变换、子树分解、边不相邻路径搜索、全局编码矢量分配和局部编码矢量计算等过程组成.算法输入为满足组播条件的有向无环网络,输出为各边的全局编码矢量和局部编码矢量.在子树分解过程中,子树内部的边不需要编码,只对子树之间的边进行编码.理论分析和仿真实验结果表明,利用子树分解可以降低网络规模以及路径搜索和分配编码矢量的计算复杂度,缩短编码算法的运行时间,因此该算法是一种高效的单源组播网络编码算法.
針對拓撲不變網絡的單源組播網絡編碼問題,基于子樹分解提齣一種新的線性網絡編碼算法.該算法由線圖變換、子樹分解、邊不相鄰路徑搜索、全跼編碼矢量分配和跼部編碼矢量計算等過程組成.算法輸入為滿足組播條件的有嚮無環網絡,輸齣為各邊的全跼編碼矢量和跼部編碼矢量.在子樹分解過程中,子樹內部的邊不需要編碼,隻對子樹之間的邊進行編碼.理論分析和倣真實驗結果錶明,利用子樹分解可以降低網絡規模以及路徑搜索和分配編碼矢量的計算複雜度,縮短編碼算法的運行時間,因此該算法是一種高效的單源組播網絡編碼算法.
침대탁복불변망락적단원조파망락편마문제,기우자수분해제출일충신적선성망락편마산법.해산법유선도변환、자수분해、변불상린로경수색、전국편마시량분배화국부편마시량계산등과정조성.산법수입위만족조파조건적유향무배망락,수출위각변적전국편마시량화국부편마시량.재자수분해과정중,자수내부적변불수요편마,지대자수지간적변진행편마.이론분석화방진실험결과표명,이용자수분해가이강저망락규모이급로경수색화분배편마시량적계산복잡도,축단편마산법적운행시간,인차해산법시일충고효적단원조파망락편마산법.