计算机研究与发展

ISSN100021239ΠCN1121777ΠTP

()网络编码下的编码开销2链路开销联合优化

邓　亮　赵　进　王　新

(复旦大学计算机科学技术学院　上海　200433)

(综合业务网理论及关键技术国家重点实验室　西安　710071)(jzhao@fudan.edu.cn)

OntheJointOptimizationofCodingCostandLinkCostwithNetworkCoding

DengLiang,ZhaoJin,andWangXin

(SchoolofComputerScience,FudanUniversity,Shanghai200433)(StateKeyLaboratoryofIntegratedServiceNetworks,Xiπan710071)

Abstract　Networkcodingisakindofnovelnetworktransmissiontechnology,whichcanachievethenetworkmulticastcapacity.Inthispaper,anoverheadoptimizationproblem(OOS)ispresentedtominimizethesumcostofnetworkcodingandnetworklinkinnetworkswithcoding.Thisoptimizationtakesnotonlythelinktransmissionoverheadbutalsotheincurredbynetworkcodingintoconsideration.Byusingtwomodels,whicharethereceiversπdataflowmixturemodelandthe,generalformsofbothkindsofoverheadarepresentedseparately.hard,onlytheapproximatelyoptimizedsolutioncanbeIntheexperiments,differentgeneticalgorithmsπdifferentinformationflowmodelsanddifferentrandomitmakestheoptimizationproblemevenmorecomplexthattakestheoverheadintoconsideration,thecomputedapproximatesolutionmaybepoorerthanonlyconsideringthenetworklinkcost.Simulationresultsshowthatonlyundertheconditionoftheoverheadcoefficientγ>1000,thejointoptimizationcangetabettersolution.Thisresultmayhaveconsiderableimportancewhennetworkcodingcomesintopracticeinthefuture.Keywords　networkcoding;jointoptimization;codingoverhead;geneticalgorithm;networkinformationflow

摘　要　网络编码是一种新的网络传输技术,能够充分利用网络的理论组播速率上限.讨论了在网络编

码下综合考虑编码开销和网络链路开销的网络总开销优化问题,将由网络编码引起的编码开销同样纳入优化问题的考虑范围.给出了2种各有优劣的网络信息流模型描述这一问题,并在不同模型下定义了2种开销的一般形式.由于这一优化问题属于NP难问题,目前一般采用启发式算法获得近似的优化解.随后的实验中,在不同规模的拓扑下对比了基于2种不同信息流模型的启发式算法的性能.由于考虑了编码开销使得联合优化问题远比链路开销优化问题复杂,模拟实验显示,只有当编码开销与链路开销价值系数之比达到1000以上时,才能获得比单纯链路优化更小的总开销.在提出基于遗传算法的方案之前,还简单地讨论了联合优化问题的复杂度.

关键词　网络编码;联合优化;编码开销;遗传算法;网络信息流中图法分类号　TP391

　收稿日期:2008-03-25;修回日期:2009-07-02

　基金项目:国家自然科学基金项目(60702054);上海市科委启明星计划基金项目(08QA14009);上海市教育发展基金会晨光计划项目

(2007CG07);上海市科委科技攻关基金项目(08dz150010E)