资源描述：
《网络编码中的优化问题研究new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.20,No.5,May2009,pp.1349−1361http://www.jos.org.cndoi:10.3724/SP.J.1001.2009.03503Tel/Fax:+86-10-62562563©byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.∗网络编码中的优化问题研究1,21,2+黄政,王新1(复旦大学计算机科学
2、技术学院,上海200433)2(综合业务网理论及关键技术国家重点实验室,陕西西安710071)ResearchontheOptimizationProblemsinNetworkCoding1,21,2+HUANGZheng,WANGXin1(SchoolofComputerScienceandTechnology,FudanUniversity,Shanghai200433,China)2(StateKeyLaboratoryofIntegratedServiceNetworks,Xi’an710071,China)+Correspondingau
3、thor:E-mail:xinw@fudan.edu.cnHuangZ,WangX.Researchontheoptimizationproblemsinnetworkcoding.JournalofSoftware,2009,20(5):1349−1361.http://www.jos.org.cn/1000-9825/3503.htmAbstract:Thispaperbrieflyreviewsthetheoreticalresearchesonnetworkcoding,fromwhichthesignificanceofresearchon
4、optimizationproblemsisrevealed.Basedonthenetworkinformationflowmodel,itmakesasurveyontheformulation,characteristicsandalgorithmsofoptimizationproblemswiththelatestresults.Accordingtothegoalofoptimization,thetypicaloptimizationproblemsinnetworkcodingareclassifiedintofourcategori
5、es:minimum-costmulticast,throughputmaximizationinundirectednetworks,minimumnumberofcodingnodesandlinks,topologydesignofnetworkcoding-basedmulticastnetworks.Thegeneralapproachestodealwiththeseproblemsarecategorized.For(linearorconvex)programmingproblems,thesolutionsaresummarized
6、;forNPcompleteproblems,thelatestheuristicalgorithmsandtheirdifficultiesareanalyzed.Theperspectivesonfutureworkarealsodiscussed.Keywords:networkcoding;wirelessnetworkcoding;optimization;linearprogramming;convexprogramming;NPcompleteproblem;geneticalgorithm摘要:简要回顾了网络编码的理论研究,阐述了网络
7、编码优化问题研究的重要意义.在介绍网络信息流模型的基础上,针对优化问题的陈述、特点和解法,结合最新的研究成果进行了综述.根据优化目标的不同,优化问题可分成4类:最小花费组播,无向网络的最大吞吐率,最小编码节点、编码边,基于网络编码的网络拓扑设计.归纳了问题的求解性质,对其中的(线性或凸)规划问题总结了求解的一般方法,对NP完全问题讨论了最新的启发式算法及其设计难点.同时,展望了未来的发展方向.关键词:网络编码;无线网络编码;优化;线性规划;凸规划;NP完全问题;遗传算法∗SupportedbytheNationalNaturalScienceFoun
8、dationofChinaunderGrantNo.60702054(国家自然科学基金);theNation
