多源组播连接的线性网络编码构造.pdf

小型微型计算机系统 2009年4月第4期 2009 ofChinese V01．30No．4 Journal ComputerSystems 多源组播连接的线性网络编码构造 蒲保兴h2，杨路明1，王伟平1，段桂华1 1(中南大学信息科学与工程学院，湖南长沙410083) 2(邵阳学院信息工程系。湖南邵阳422001) E—mail：pubook@yahoo．corn．cn 摘要：针对多源组播连接问题，给出运用线性网络编码技术进行数据传输并达到最大吞吐率的编码构造方法．把多源组播网 络划分成多个子图，每一个子图是一个单源组播网络；为了使网络的吞吐率达到最大，本文把划分子图问题转化为一个组合优 化问题。并给出基于遗传算法的求解方法；然后利用实现单源组播连接的线性网络编码技术，对每一个单源组播网络进行编码 构造．仿真测试结果表明，提出的方法是可行的，能够实现多源组播连接的线性网络编码构造． 关键词：多源组播；线性网络编码；子图划分；组合优化问题；遗传算法 中图分类号：TN7ll 文献标识码：A 文章编号：1000—1220(2009)04—0642．05 LinearNetworkConstructionforMulti—sourceMulticastConnection Coding PU Gui—hual Bao—xin91’2。YANGLu—min91。WANGWei—pin91，DUAN 1(School Scienceand South 410083，China) ofInformation Engineering．CentralUniversity，Changsha 422001，China) ofInformationEngineering，ShaoyangCollege，Shaoyang 2(Department atmulti-sourcemuhicastconnection，this alinearnetworkconstructionto Abstract：Aiming paperproposes coding implement withmaximum multi—sourcesmuhieastnetworkisdividedintoseveral each datatransmission throughput．The sub—graphs，and tO themaximal convertsthe ofsub— ofwhichisa muhicastnetwork．Inorder paper partition single—source get throughput，this intoacombinatorial an tosolveit tO graph optimizationproblem，thenproposesalgorithm accordinggenetic over。thenetworkconstructionofeach muhicastnetworkis coding single—source implementedbyexisting tionresultsshowthe isfeasibleandcan thelinearnetworkconstruct