資源描述:
《網(wǎng)絡(luò)編碼中的優(yōu)化問題研究new》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
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.?網(wǎng)絡(luò)編碼中的優(yōu)化問題研究1,21,2+黃政,王新1(復(fù)旦大學(xué)計算機科學(xué)
2、技術(shù)學(xué)院,上海200433)2(綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室,陜西西安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摘要:簡要回顧了網(wǎng)絡(luò)編碼的理論研究,闡述了網(wǎng)絡(luò)
7、編碼優(yōu)化問題研究的重要意義.在介紹網(wǎng)絡(luò)信息流模型的基礎(chǔ)上,針對優(yōu)化問題的陳述、特點和解法,結(jié)合最新的研究成果進(jìn)行了綜述.根據(jù)優(yōu)化目標(biāo)的不同,優(yōu)化問題可分成4類:最小花費組播,無向網(wǎng)絡(luò)的最大吞吐率,最小編碼節(jié)點、編碼邊,基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)拓?fù)湓O(shè)計.歸納了問題的求解性質(zhì),對其中的(線性或凸)規(guī)劃問題總結(jié)了求解的一般方法,對NP完全問題討論了最新的啟發(fā)式算法及其設(shè)計難點.同時,展望了未來的發(fā)展方向.關(guān)鍵詞:網(wǎng)絡(luò)編碼;無線網(wǎng)絡(luò)編碼;優(yōu)化;線性規(guī)劃;凸規(guī)劃;NP完全問題;遺傳算法?SupportedbytheNationalNaturalScienceFoun
8、dationofChinaunderGrantNo.60702054(國家自然科學(xué)基金);theNation