资源描述：
《Optimal Control for Generalized Network-Flow Problems 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1OptimalControlforGeneralizedNetwork-FlowProblemsAbhishekSinha,EytanModianoLaboratoryforInformationandDecisionSystems,MassachusettsInstituteofTechnology,Cambridge,MA02139Email:sinhaa@mit.edu,modiano@mit.eduAbstract—Weconsidertheproblemofthroughput-optimalThealgorithmi
2、n[1]iscombinatorialinnatureanddoespacketdissemination,inthepresenceofanarbitrarymixofnothaveawirelesscounterpart,withassociatedinterference-unicast,broadcast,multicastandanycasttraffic,inageneralfreeedgeactivations.FollowingEdmonds’work,avarietywirelessnetwork.Wepropos
3、eanonlinedynamicpolicy,calledofdifferentbroadcastalgorithmshavebeenproposedintheUniversalMax-Weight(UMW),whichsolvestheaboveproblemefficiently.Tothebestofourknowledge,UMWisthefirstliterature,eachonetargetedtooptimizedifferentmetricsthroughput-optimalalgorithmofsuchversa
4、tilityinthecontextsuchasdelay[2],energyconsumption[3]andfault-toleranceofgeneralizednetworkflowproblems.Conceptually,theUMW[4].Inthecontextofoptimizingthroughput,[5]proposespolicyisderivedbyrelaxingtheprecedenceconstraintsassociatedarandomizedbroadcastpolicy,whichisopt
5、imalforwiredwithmulti-hoprouting,andthensolvingamin-costroutingandnetworks.However,extendingthisalgorithmtothewirelessmax-weightschedulingproblemonavirtualnetworkofqueues.Whenspecializedtotheunicastsetting,theUMWpolicyyieldsasettingprovestobedifficult[6].Theauthorsof[7
6、]proposethroughput-optimalcycle-freeroutingandlinkschedulingpolicy.anoptimalbroadcastalgorithmforageneralwirelessnetwork,Thisisincontrasttothewell-knownthroughput-optimalBack-albeitwithexponentialcomplexity.InarecentseriesofpapersPressure(BP)policywhichallowsforpacket
7、cycling,resulting[8][9],asimplethroughput-optimalbroadcastalgorithmhasinexcessivelatency.ExtensivesimulationresultsshowthatthebeenproposedforwirelessnetworkswithanunderlyingDAGproposedUMWpolicyincursasubstantiallysmallerdelayascomparedtotheBPpolicy.Theproofofthroughpu
8、t-optimalitytopology.However,thisalgorithmdoesnotextendtonon-DAGoftheUMWpolicycombinesideasfromstochasticLyapunovnetworks.th
