Sun Microsystems Laboratories

Abstract---We introduce and analyze CARMA-MC (for Collision Avoidance and Resolution Multiple Access MultiChannel), a new stable channel access protocol for multihop wireless networks with multiple channels. CARMA-MC relies on the assignment of a unique ch

CollisionAvoidanceandResolutionMultipleAccessforMultichannelWirelessNetworks

RODRIGOGARCE

´Srgarces@http://www.51wendang.com

MetricomInc.980UniversityAvenueLosGatos,CA95032

Abstract—WeintroduceandanalyzeCARMA-MC(forCollisionAvoid-anceandResolutionMultipleAccessMultiChannel),anewstablechan-nelaccessprotocolformultihopwirelessnetworkswithmultiplechannels.CARMA-MCreliesontheassignmentofauniquechannelandauniqueidenti ertoeachnodetosupportcorrectdeterministiccollisionresolutioninthepresenceofhiddenterminals.CARMA-MCdynamicallydividesthechannelofeachnodeintocyclesofvariablelength;eachcycleconsistsofoneormorereceivingperiodsandatransmissionperiod.Duringthere-ceivingperiod,stationswithoneormorepacketstosendcompetefortherighttoacquirethe oorofaparticularreceiver’schannelusingadeter-ministictree-splittingalgorithm.Eachreceivingperiodconsistsofcollisionresolutionsteps.Asingleroundofcollisionresolution(i.e.,asuccess,andidleoracollisionofcontrolpackets)isallowedineachcontentionstep.Thereceivingperiodisinitiatedbythereceiverandtakesplaceinthechannelassignedtothereceiverstation.Thechannelutilizationandpacketdelaysarestudiedanalyticallyandbysimulation.

I.INTRODUCTION

Collisionsinapacket-radionetworkcanbecausebydirectorbysecondaryinterference.Directinterferenceoccurswhentwoneighboringnodestransmittoeachotheratthesametime.Secondaryinterferenceoccurswhentwoormorestationsun-awareofeachother’sexistencetransmittothesamereceiveratthesametimeorwhenastationistransmittingtoitsneighborandathirdstationstransmissiontosomeotherstationcausesaninterference.Thisproblemwas rstintroducedbyTobagiandKleinrock[15]andisknownintheliteratureasthehiddenterminalproblem.Severalapproacheshavebeenproposedinthepasttoresolvethehiddenterminalproblem,andcollision-avoidanceprotocolshaverecentlyreceivedconsiderableatten-tion(e.g.,[13],[6]).Inacollision-avoidanceprotocol,senderandreceivercollaboratetryingtoavoiddatapacketsfromcol-lidingwithotherpacketsatthereceiver.However,astraf cloadincreasesinthenetwork,thecollisionofcollision-avoidancecontrolpacketsincreasesandthroughputinthesystemdrops.Awaytostabilizetheoperationofcontention-basedprotocolsisbymeansofcollisionresolutionmechanisms.

SeveralstableMACprotocolshavebeenproposedinthepastbasedontree-splittingalgorithmsforcollisionresolution(e.g.,[4],[7],[20]).Thoseprotocolsinwhichdatapacketsare

usedtoresolvecollisionsachievethroughputbelow

[22]forasinglechannelandfullyconnectednetworks.SeveralMAC

TheworkatUCSCwassupportedinpartbytheDefenseAdvancedResearchProjectsAgency(DARPA)undergrantDAAB07-95-C-D157

J.J.GARCIA-LUNA-ACEVESComputerEngineeringDepartment

UniversityofCaliforniaSantaCruz,California95064NetworkingandSecurityCenterSunMicrosystemsLaboratoriesPaloAlto,California94303

protocolshavebeenproposedthatimplementcollisionreso-lutionusingeithercontrolpacketsthataremuchsmallerthandatapackets,orarebasedontheabilityofthetransmittertoaborttransmissionrapidlyafterdetectingcollision(e.g.,[2],[8],[14]).AmongthosestableMACprotocolsthatachievehighthroughput,somebuildaseparatequeueforthetransmissionofdatapackets,inadditiontothestackorqueueofthecon-trolpacketsusedforcollisionresolution.However,thestablecollisionresolutionapproachesreportedtodateoperateinfully-connectednetworksornetworksbasedoncentralbasestations.Ontheotherhand,severalreservationbasedprotocolshavebeenproposed(e.g.,[1],[10],[12],[14])whichprovidestabil-ityathighloadlevels,andef cientserviceatlowloadlevels.Resourceauctionprotocols,i.e.,[1],[14],requireasigni cantamountofoverheadforeachauctionperiodandaredif culttoimplement.Ontheotherhand,PRMA[10]isrelativelyeasytoimplementbutusesa xedframelengthwhichcanleadtostar-vationifthenumberofactivestationsislarge.Theseprotocolsallrequireabasestation,anddonotoperateinanetworkwithhiddenterminals.Thelimitationoftheseschemesisthatmostofthemrequiretheuseofabasestationwhichisasinglepointoffailure.

Thispaperpresentsanapproachtoutilizingcollisionreso-lutioninmultihopwirelessnetworksbytakingadvantageofuniquechannel(orcode)assignmentstonetworknodes.Inthepast,multichannelnetworkshavebeenconstructedusingmul-tipletransceiversoperatingonseparate xedchannels[21].Suchdeviceswereexpensivetoconstruct.However,currenttransceivertechnology(e.g.,MetricomInc.newgenerationnet-workdevices),enablesradiodeviceswithasmanyas

chan-nelstobecontrolledbyasingleDSP,enablingradiostoswitchfromonechanneltotheotherwithin1sec.Thisallowsmulti-channelnetworkstobeconstructedinexpensivelyusingasin-gledeviceateachstation.Inaddition,usingmultiplechan-nelsrendersbetterdelaycharacteristicsthansingle-channelnet-works[16],[17],[19]andhavebetterfaulttoleranceagainstfadingandnoise[5],[17].EarlyworkinprotocoldesignformultichannelnetworksusedCSMAorALOHAprotocolsinslottedmultiplechannels[18].Areservationprotocolovermultiplechannelsisinvestigatedin[16]forsatellitecommu-nicationsystems.Asequentialmultichannelsystemwhichuses

Word文档免费下载Word文档免费下载:Sun Microsystems Laboratories (共8页,当前第1页)

Sun Microsystems Laboratories相关文档

最新文档

返回顶部