不同组播率下线性网络编码的导出与扩展蒲保兴1,2+,杨路明1,王伟平11(中南大学信息科学与工程学院,湖南长沙,410083)2(邵阳学院信息工程系,湖南邵阳,422001)GenerationandExtensionofLinearNetworkCodingatDifferentMulticastRatePUBao-Xing1,2+,YANGLu-Ming1,WANGWei-Ping11(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)2(DepartmentofInformationEngineering,ShaoyangCollege,Shaoyang422001,Hunan,China）+Correspondingauthor:Phn:+86-0739-5432505,E-mail:pubook@yahooReceived2008-10-11;Accepted2009-00-00Abstract:Aimingatsingle-sourcemulticastnetwork,bystudyingtheintrinsicmechanismoflinearnetworkcoding,thispaperproposesaconceptofgenerationandextensionbetweentwocodingschemesatdifferentmulticastrates.Wefindoutthatacodingschemeatlowermulticastrateisagenerationofoneathighermulticastrate,andacodingschemeathighermulticastrateisanextensionofoneatlowermulticastrate.Furthermore,wefindoutadeterminaterelationshipbetweenchannels’globalencodingvectorsundertwogeneration-extensioncodingschemes.Besides,bycombiningwithrandomlinearnetworkcoding,severalimportantpropertiesarederived,whicharehelpfultoimplementlinearnetworkcodingforsingle-sourcemulticastnetwork.Severalrelatedapplicationsareenumerated,andsimulationresultsvalidatetheconclusionsderivedbytheoreticalanalysis.Keywords:single-sourcemulticastnetwork,randomlinearnetworkcoding,generationandextensionofcodingschemesatdifferentmulticastrate.摘要:针对单源组播网络,通过对线性网络编码方案(编码系数的组合)的内在机理进行分析,提出了不同组播率下编码方案的导出与扩展的概念:低组播的编码方案可以由高组播率的编码方案导出,高组播率的编码方案可以由低组播率的编码方案扩展而成.研究了具有导出与扩展关系的两个编码方案下全局编码向量间的相互联系,结合随机线性网络编码,导出了几个重要的性质,这些性质有助于有效地运用线性网络编码技术实现单组播连接,具有一定的应用价值.列出了几个方面的应用,基于相关的应用给出了仿真实验,仿真结果验证了理论分析的结论.关键字:单源组播;随机线性网络编码;不同组播率下编码方案的导出与扩展中图法分类号:TP911文献标识码:A网络编码[1-4]是一种新型的数据传输技术,能提高网络的吞吐率、鲁棒性和安全性.Ahlswede等人[1]首次提出了网络编码的概念,并指出:通过网络中间节点的编码可以实现单源组播网络的最大流界,而传统的路由技术一般情况下不能达到这个极限.李硕彦等人[2]提出了线性网络编码技术,并证明了线性网络编码技术可以充分实现这一功能.Koetter等人[3]给出了线性网络编码的代数框架.因线性网络编码具有简单的特点,从而得到了深入广泛地研究[4,5,6,7,8].运用线性网络编码进行数据传输必须构造编码方案:确定源点的数据传输速率(组播率)和各信道的编码系数.已有文献主要针对同一组播率下的编码方案进行研究,而对不同的组播率下的编码方案之间的关系研究较少.在实际应用中,运用线性网络编码技术面临以下问题:1)有时需要以不同的组播率进行数据传输,如采用已有的方法,则针对不同的组播率要设计不同的编码方案,且编码节点需保存不同组播率下的编码系数,占用了大量的存贮空间;2)尽管有文献[9,10,11]基于网络编码提出了分布式构造编码方案或减少编码代价的方法,但均是针对某一可行的组播率(不超过组播容量)进行研究,且假定组播容量是已知的或者能运用网络的全局拓扑知识采用最大SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60673164,60873265(国家自然科学基金),ProvincialNaturalScienceFoundationofHunanunderGrantNo.06JJ20031(湖南省自然科学基金).作者简介：蒲保兴(1965-),男,湖南邵阳人,博士研究生,副教授,主要研究领域为网络编码,进化计算;杨路明(1947-),男,江西南昌人,博士生导师,教授,主要研究领域为数据库信息系统;王伟平(1969-),女,湖...