performance limits of greedy maximal matching in multi-hop wireless networks

《performance limits of greedy maximal matching in multi-hop wireless networks》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PerformanceLimitsofGreedyMaximalMatchinginMulti-hopWirelessNetworksChangheeJoo,XiaojunLin,andNessB.ShroffAbstractInthispaper,wecharacterizetheperformancelimitsofanimportantclassofschedulingschemes,calledGreedyMaximalMatching(GMM),formulti-hopwirelessnetworks.Forsi

2、mplicity,wefocusonthewell-establishednode-exclusiveinterferencemodel,althoughmanyofthestatedresultscanbereadilyextendedtomoregeneralinterferencemodels.ThestudyoftheperformanceofGMMisintriguingbecausealthoughalowerboundonitsperformanceiswellknown,empiricalobservati

3、onssuggestthatthisboundisquiteloose,andthattheperformanceofGMMisoftenclosetooptimal.Infact,recentresultshaveshownthatGMMachievesoptimalperformanceundercertainconditions.Inthispaper,weprovidenewanalyticresultsthatcharacterizetheperformanceofGMMthroughthetopological

4、propertiesoftheunderlyinggraphs.Tothatend,wegeneralizearecentlydevelopedtopologicalnotioncalledthelocalpoolingconditiontoafarweakerconditioncalledthe-localpooling.Wethendenethelocal-poolingfactoronagraph,asthesupremumofallsuchthatthegraphsatises-localpooling.

5、Weshowthatforagivengraph,theefciencyratioofGMM(i.e.,theratioofthethroughputofGMMtothatoftheoptimal)isequaltoitslocal-poolingfactor.Further,weprovideresultsonhowtoestimatethelocal-poolingfactorforarbitrarygraphsandshowthattheefciencyratioofGMMisnosmallerthand=(2

6、d1)inanetworktopologyofmaximumnode-degreed.WealsoidentifyspecicnetworktopologiesforwhichtheefciencyratioofGMMisstrictlylessthan1.I.INTRODUCTIONOverthelastfewyearstherehasbeensignicantinterestinstudyingtheschedulingproblemformulti-hopwirelessnetworks[1]–[11].

7、Ingeneral,thisprobleminvolvesdeterminingwhichlinksshouldtransmit(i.e.,whichnode-pairsshouldcommunicate)andatwhattimes,whatmodulationandcodingschemesshouldbeused,andatwhatpowerlevelsshouldcommunicationtakeplace.Whiletheoptimalsolutionofthisschedulingproblemhasnowbe

8、enknownforalongtime[2],theresultantsolutionisextremelycomplexandvirtuallyimpossibletoimplement.Recently,severalresearchershavedevelopedsimplerscheduling