资源描述：
《Multiflows in multihop wireless networks》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、MultiflowsinMultihopWirelessNetworks[ExtendedAbstract]∗Peng-JunWanDepartmentofComputerScienceIllinoisInstituteofTechnologyChicago,IL60616wan@cs.iit.eduABSTRACTsingle-radiosingle-channelmultihopwirelessnetworkNisspecified,initsmostgeneralformat,byatriple(D,G,b),Thispaperstudiesmaximummu
2、lticommodityflowandwhereDisadirectedgraphrepresentingthecommunica-maximumconcurrentflowinmultihopwirelessnetworkstiontopologyofN,Gisanundirectedgraphrepresentingsubjecttobothbandwidthandinterferenceconstraints.Thetheconflictgraphofthe(communication)linksinD,andbisexistingproofoftheNP-ha
3、rdnessofbothproblemsistoothebandwidthfunctionofthelinksinD.AsetoflinksinDcontrivedtobeapplicabletomeaningfulmultihopwirelessaresaidtobeconflict-freeiftheyarenotadjacentpairwisenetworks.Inaddition,allknownconstant-approximationinG.ConsideramultihopwirelessnetworkN=(D,G,b)algorithmsforb
4、othproblemsrestrictedtovariousnetworkwithD=(V,A).WeuseItodenotethecollectionofsetsclassesaresuper-exponentialinrunningtime.Someofthemofconflict-freelinksinD.A(fractional)linkscheduleinNaresimplyincorrect.Inthispaper,wefirstprovidearig-isasetorousproofoftheNP-hardnessofbothproblemseveni
5、nverysimplesettings.Then,weshowthatbothproblemsS={(Ij,λj):1≤j≤k}restrictedtoabroadfamilyofmultihopwirelessnetworkswithIj∈I,andλj∈R+foreach1≤j≤k.Thevalueadmitpolynomial-timeapproximationscheme(PTAS).Af-Pkterthat,wedevelopaunifiedframeworkforthedesignandj=1λjisreferredtoasthelength(orla
6、tency)ofS,andanalysisofpolynomialapproximationalgorithmsforboth
7、S
8、iscalledthesizeofS.AnylinkscheduleSinNoflengthproblems.Followingsuchframework,weobtainpolyno-AatmostonedeterminesalinkcapacityfunctioncS∈R+ofmialconstant-approximationalgorithmsforbothproblemsDgivenbyrestrictedtoabroad
9、networkfamily.TheapproximationXratiosofthesealgorithmsarealsobetterthanthoseknowncS(e)=b(e)λj
10、Ij∩{e}
11、intheliterature.1≤j≤kforeache∈A.SupposethatwearegivenwithasetofCategoriesandSubjectDescriptorscommoditiesinD.ForanylinkscheduleSinNoflengthatmostone,themaximummultiflowofthesecommoditi
12、esC.2.1[Comp
