Channel Hopping Multiple Access with Packet Trains for Ad Hoc Networks AsimakisTzamaloukas J.J.Garcia-Luna-Aceves ComputerEngineeringDepartment Baskin School ofEngineering UniversityofCalifornia, SantaCruz, California95064 E-mail: jamal, [email protected] Abstract—Wepresentanewmedium-accesscontrolprotocolfor gralpartofthecollision-avoidancehandshakelimitstheir adhocnetworks thatdoesnotrequire carrier sensingorthepre- applicability. Most commercial radios do not provide assignment of unique codes to nodes to ensure that intended re- truecarriersensing,anddirectsequencespread-spectrum ceiversreceiveunicast,ormulticast,orbroadcastdatapacketswith- out interference from hidden sources. We call this new proto- (DSSS)radiosmaycapturenoneoroneofmultipleover- col channel hopping access with trains (CHAT). CHAT combines lapping transmissions depending on the proximity and the notion of packet trains with synchronous channel hopping to transmission power of the sources. Even if frequency- improve channel utilization. We compare CHAT against two of hoppingspread-spectrum(FHSS)radiosareused,carrier the most efficient protocols proposed to date based on the pre- assignmentofcodes(MACA-CT),orchannelhoppingwithnopre- sensingaddstothecomplexityoftheradio. definedcodeassignment(CHMA)viasimulations.Theresultsshow Sousa and Silvester [6] presented and analyzed vari- thatCHATprovides considerable improvement inthethroughput of an ad hoc network for unicast traffic, broadcast traffic and ous spreading-code protocols that are sender-, receiver- mixedtrafficconsistingofbothunicastandbroadcasttransmissions. or sender-receiver based, i.e., in which codes are pre- CHATisapplicable toadhocnetworks basedoncommercial off- assigned to senders, receivers, or combinations. Sev- the-shelfspreadspectrumradiosoperatinginunlicensedfrequency bands. eralotherproposalshavebeenmadetoimplementcorrect Keywords—MediumAccess Protocols, ad-hocnetworks, packet collision-avoidanceinmulti-hopnetworkswithoutrequir- train,multichannelradio,frequencyhoppingspreadspectrum ing nodesto use carrier sensing; these proposalsrely on multiplecodesassignedtosenders,receiversoracombi- I. INTRODUCTION nationofthetwo.MACA-CT[5]usescollision-avoidance handshakes over a common channel and a transmitter- Medium-accesscontrol(MAC)protocolsbasedoncol- orienteddatachannelpre-assignedtoeachnodetoavoid lisionavoidancehavebeenwidelyusedinwirelessLANs collisionsofdatapackets;MACA-CTisagoodrepresen- and ad hoc networks mainly due to their simplicity and tative of collision-avoidance solutions that eliminate the good performance compared to carrier sensing multiple needforcarriersensingattheexpenseofrequiringunique access (CSMA). With a collision-avoidance MAC pro- channelassignments. tocol, a node that needs to transmit data to a receiver firstsendsarequest-to-send(RTS)packettothereceiver, Code assignmentprotocolscan be implementedusing who responds with a clear-to-send (CTS) if it receives DSSSorFHSSradios. However,mostofthecommercial theRTScorrectly. Asendertransmitsadatapacketonly DSSS radiostodayuse only11chipsperbit, which pre- after receiving a CTS successfully. Several variations cludestheuseofcodedivisionmultipleaccess(CDMA). of this scheme have been developedsince SRMA (split- On the other hand, up to 15 FHSS radios can be co- channel reservation multiple access) was first proposed located with minimum interference problems according byKleinrockandTobagi[7],includingIEEE802.11[1]. to the FCC regulations. Hence, slow frequencyhopping Fullmer andGarcia-Luna-Aceves[2] showedthat, in or- is an attractive approach to achieve multiple orthogonal der to avoid data packets from colliding with any other channelsinadhocnetworks. Thelimitationofprotocols packetsat the intendedreceiversin networks with a sin- basedonthepre-assignmentofcodesisthatsendersand gle channel, the senders had to sense the channel be- receivershaveto find eachothers’codesbeforecommu- foresendingtheirRTSs. Morerecently,receiver-initiated nicatingwithoneanother. collision-avoidance protocols have also been proposed We introduced the channel-hopping multiple access for single-channel networks, in which the receiver initi- (CHMA) protocol [8] to eliminate the need for pre- atesthecollision-avoidancehandshake[3];thesereceiver- assigningcodestonodesinordertoavoidhiddenterminal initiatedcollision-avoidanceprotocolsalsorequirecarrier interferenceinmulti-channelnetworkswithoutusingcar- sensingtoensurecorrectcollisionavoidance. riersensing.However,alimitationofCHMAandallprior The need for collision-avoidance MAC protocols for MACprotocolsbasedoncollision-avoidancehandshakes single-channelnetworksto sense the channelas an inte- isthatasourcecannottransmitapacketdestinedtomulti- plereceiversandguaranteethatallthereceiverscanhear ThisworkwassupportedinpartbytheDefenseAdvancedResearch ProjectsAgency(DARPA)undergrantF30602-97-2-0338. thepacketwithoutexperiencinghidden-terminalinterfer- Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 2000 2. REPORT TYPE 00-00-2000 to 00-00-2000 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER Channel Hopping Multiple Access with Packet Trains for Ad Hoc 5b. GRANT NUMBER Networks 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION University of California Santa Cruz,Computer Engineering REPORT NUMBER Department,Baskin School of Engineering,Santa Cruz,CA,95064 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES The original document contains color images. 14. ABSTRACT 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE 6 unclassified unclassified unclassified Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 ence. lets assume that nodes , , , and remain This paper introduces the Channel Hopping Access in the same channel hopD,1whDer2easDn4ode Dis5 already with Trains (CHAT) protocol. CHAT is the first MAC busy exchanging data with some other noDde6and there- protocol based on collision avoidance that (a) does not fore does not receive the RTS from . Immedi- require carrier sensing to eliminate hidden terminal in- ately, node transmits an SRTSSowuirthcethe format: terference, and (b) guaranteesthat unicastand broadcast Source . Nodes data packets can be transmitted without collisions. Sec- [addarn(dD2);2r;e1a]l[iazeddthra(Dt t5h)e;r5e;i1s][naodddrat(aDp6a)c;k6e;t1t]o be re- tion II describes the operation of CHAT in detail. Sec- cDe1ivedfrDom4 andsynchronizewiththerestofthe tionIIIprovesthat, intheabsenceoffading,CHATpro- nodesinadifSfeoruernctechannel.Node receivestheSRTS tocolprovidescorrectflooracquisitioninamulti-hopnet- and since it is the first entry in theDli2st, transmits a CTS work. Section IV presents the results of simulation ex- rightaftertheendoftheSRTS.Node ,transmitsaCTS perimentsusedtocomparethe throughputachievedwith secondsafter the endof the SRTSDsi5nce it was second CHATagainstCHMAandMACA-CT.SectionVpresents ihnthelistreceivedintheSRTSpacket.Ontheotherhand, ourconclusions. node neverreceivestheSRTSandthereforenoCTSis senttoDn6ode inresponse. Afterthesourcehasre- II. CHAT ceivedanindSicoautirocne(aCTSorsilence)fromallthenodes includedinthelist,ittransmitsallthecorrespondingdata CHAT enhances the control handshake introduced in packetsforwhichaCTSwasreceived. CHMA[8]toallowcollision-freetransmissionsofpacket trains,multicastpackets,andbroadcastpackets.Thebasic D2 D3 Time Node Packet Packet Content operationforCHATisshowninFig.2. Allthenodesfol- t Source RTS sourbciet vadecdtroers:s 0: 1ad0d0r1(1S0o0urce) D1 D4 destination address: addr(D2) addr(D5) addr(D6) low a common channel-hoppingsequence and each hop t+h Source SRTS bit vector index: 2 5 6 lasts the amount of time needed for nodes to receive a Source t+2h D2 CTS number odfe psatsiconkuaerttcisoe:n a ad dd dr e r1es ss :s :a ad dd dr ( r D( S 2 o1)u r c e ) 1 collision-avoidance control packet from a neighbor. A D8 D5 t+3h D5 CTS destsionuartcioen a addddreresss:s :a addddr(rD(S5o)urce) node that has local data packets for any of its neighbors D7 D6 t+4h D6 --- idle slot transmits a ready-to-send (RTS) control packet over the Fig.1. Node transmitsadatapackettraintonodes and currentchannelhopspecifyingitsownaddress,andabit Source D2 D5 vector of 32 bits. Each bit in the bit vector specifies a CHAThasaclearadvantageagainstallpriorMACpro- neighbornode. tocolsbasedon collisionavoidancewhenbroadcasttraf- Ifanodeisalreadyfamiliarwithitspositioninthebit fic is considered. In particular, with CHAT a broadcast vector then after receiving an RTS, either (a) the corre- packet is simply a unicast packet with all the bits in the spondingbitissetandthenoderemainsinthesamechan- bitvectoroftheRTSset. Ifallnodesreturnsuccessfully nel hop, or (b) the bit is not set and the node moves on aCTSthenjustonedatapacketisbroadcasttoallofthem tothenextchannelhop. Ifanodeisnotawareofitspo- in a single handshake. When one or more nodes do not sition in the bit vector, by defaultit remainsin the same replywith a CTS the source nodestill sends a broadcast channel hop. In the following time slot, nodes that ei- data packetto those nodesthat havesuccessfully replied therknoworneedtoknowiftheyareintendedreceivers withaCTS.Thenodesthatdidnotreceivethebroadcast ofpacketsremaininthesamefrequencyhop. Thesource datapacketaresavedinalistandanotherretransmission nodetransmitsaspecializedRTS(SRTS)thathasvariable tosendthesamebroadcastdatapacketisattemptedfrom lengthandcontainsalistwhereeachentryholdsthefol- the source node at a later time. In contrast, in collision- lowing informationfields: (a) the receivernode address, avoidanceprotocols,abroadcastdatapackethastobeser- (b)areceivernumberthatistheindexofthereceivernode vicedasanumberofunicastpackets,oneforeachofthe inthebitvector,and(c)acounterthatrepresentsthenum- neighborsofagivensourcenode. Inthiscase,thesource berofdatapacketsinthepackettrainintendedforagiven nodehastosucceedina numberofcontrolpackethand- node. Afterthe SRTS is receivedbyall the nodesin the shakeswithallofit’sneighborsbeforethebroadcastdata samechannelhop,eachnodecomparesthesetofdestina- packetistransmitted. tionaddresseswithits ownaddress. Ifa matchisfound, Ourselectionofa32bitvectorstemsfromthefactthat, a CTS is sent back at a time that is equal to the current with commercially available frequency-hopping spread- time plus the offset of the match from the beginning of spectrumradios,thenumberofco-locatednodesmustbe thelisttimesaslotduration.AfteraCTSisreceivedsuc- kept below 15 to avoid excessive cross-channel interfer- cessfullythesourcenodetransmitsitsdatapacketoverthe ence. Atthesametime,theincurredoverheadiskepttoa samechannelhop. minimumforbothbandwidthandprocessingspeed. Be- Forexample,assumethatattime ,node trans- causetheslotdurationisfixed,wecannothaveavariable mits an RTS with a simplified 8-bitt vectorSource as lengthRTS with multipledestinations. By introducinga shown in Figure 1. Assuming one-to-one 0m1a0p0p1in1g00be- bit vector in the RTS followed by variable length SRTS tween the names of the nodes and their position in the packet, we guaranteethe robustperformanceof the pro- bitvector,therearethreedatapacketsfornodes , tocolevenin thecase ofa verydense, heavilyloadedad and . If is the hop duration, then at timeD2 D5, hocnetwork, wherethe numberof packetswaiting to be D6 h t + h time hop t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 x->y x->y y->x x->y h1 RTS SRTS CTS UNICAST DATA h2 k->l,m,n k->l,m,n l->k n->k k->l k->n RTS SRTS CTS CTS UNICAST DATA UNICAST DATA h3 a->b a->b RTS SRTS silence c<->d h4 RTS backoff node x sends an RTS and a SRTS with only one destination; node y responds with a CTS and node x sends DATA node k sends an RTS and a SRTS to l,m,n; only nodes l,n respond with a CTS and node k sends a packet train of 2 unicast DATA packets to them node a sends an RTS and a SRTS but b is busy sending data to another node; the same holds for multiple destinations nodes c and d send an RTS at the same time, therefore a collision occurs Fig.2. CHATwithunicastonlydatapacketexchangeillustrated serviced is large. In such a case, a variable length RTS node and sends an RTS to node within seconds. packetwouldhavealonglistwithallthepacketswaiting Sinceknodesd areinthesamenleighborh(cid:28)oodacol- tobeserviced,increasingthevulnerabilityperiodforthe lisionoccursc.;Bdo;tkh;nlodes and havetobackoffandtry controlpackethandshake. tosendanRTSatalaterticme. d When the transmission of data is completed, then In Fig. 3, we see how CHAT can handle broadcast as senderandreceiverre-synchronizetothecurrentcommon well as unicast traffic at the same time. We assume that channelhop. If either multiple RTSs are sentduringthe nodes aretheonlythreeneighborsofnode ,and samechannelhop,orthedestinationnodedoesnotreceive attimel;mn;onde hasabroadcastdatapackettosentk. First the RTS (because it is already engaged in another hand- an RTSt2anda SkRTS controlpacketsaresentjustas with shake),noCTSissenttothesourcenode. Consequently, any unicast data packet. When at least one node replies the source node does not hear anything after sending its withaCTS,node transmitsit’sbroadcastdatapacket.In SRTSandmustrejointherestofthenetwork. thisexample,alltkhreenodesreplywithaCTSandthere- In Fig. 2, all the nodes start at time from hop . fore the broadcast transmission is completed in just one At time the system is at hop andt1so on. Nodeh1 handshake. If oneor morenodesarealreadyengagedin sends antR1TS to node at time h1. All the nodes but x someotherpacketexchangethenoneormoreCTSswill and hop to frequencyy at timt1e . Node sendsxa notbesentbackandthetransmittingnodehastotryagain SRTSy andnode responhds2withaCTt2Sattimex . Upon atalatertime. receptionofacolylisionfreeCTS,node willremta3inatthe Although 400msec is a long time to transmit data in same frequencyalong with to transmxitits data. While ISM bands, it may be desirable to allow nodes sending and , stay in until hyas finished sending its data, data to hop over multiple frequency hops to permit data axll theyother nodehs1continxue to . Similarly, at time exchanges lasting longer than 400msec. In addition by node has local data packets fohr2nodes , , and . tA2 staying at the same frequency for a long period of time SRTSkis send with a list of the addresseslomf , , annd annihilates many inherent advantages that come with a at time . At time , only nodes , , anld mremainn frequencyhoppingmodulation. in frequet3ncy . Immt4ediately, node kthlat is thne first on WhenmultipleRTSsaretransmittedwithinaone-way the list of thehr2eceived SRTS, sends la CTS. At time , propagationdelayacollisiontakesplaceandthenodesin- thereisnoCTSreceivedfromnode possiblyduetotth5e volvedhavetoback-off. Node determinesthatitsRTS fact that was involved in an othemr transmission while wasnotreceivedcorrectlyby xafteratime periodequal node trmansmitted the RTS. Finally, at time node toonehop. Toreducetheprobzabilitythatthesamenodes also reksponds with a CTS. At time , node t6transmitns compete repeatedly for the same receiver at the time of the first data packet in it’s queue tot7node ,kwhereas at thenextRTS,theRTSspecifiesaback-off-periodunitfor time a second data packet for node ils sent. That contention. The involvednodescompute a random time is,2utn1i4castdatapacketsaresendtonodens and inthe thatisamultipleoftheback-off-periodunitadvertisedin samepackettrain. l n the RTS. The simplest case consists of computinga ran- Attime and in frequency , node sendsanRTS dom number of back-off-period units using a uniformly to node btu3tnode is busy trahn3smittingadata to another distributed random variable from 1 to , where is the node(nobticethatwebonlyconsideruni-directionalradios). maximumnumberofneighborsforarecdeiver. d Therefore,node doesnotreceivetheRTSandattime there is silence.bIn this case, node hasto back off ant4d III. CORRECT COLLISION AVOIDANCE thereforecontinuestohopwiththeoathernodestohop . Theorem1belowshowsthatCHAT ensuresthatthere At time and in frequency node sends an RTSht4o arenocollisionsbetweendatapacketsandanyothertrans- t4 h4 c time t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 hop x->y x->y y->x x->y h1 RTS SRTS CTS UNICAST DATA h2 k->l,m,nk->l,m,n l->k m->k n->k k->l,m,n RTS SRTS CTS CTS CTS BROADCAST DATA a->b a->b h3 RTS SRTS silence c<->d h4 RTS backoff node x sends an RTS and a SRTS with only one destination; node y responds with a CTS and node x sends DATA node k sends an RTS and a SRTS to l,m,n; all nodes l,m,n respond with a CTS and node k sends a broadcast DATA packet to them node a sends an RTS and a SRTS but b is busy sending data to another node; the same holds for multiple destinations nodes c and d send an RTS at the same time, therefore a collision occurs Fig.3. CHATwithunicastandbroadcastdatapacketexchangeillustrated missions. Thefollowingassumptionsaremade[2]: IV. PERFORMANCE COMPARISON A0) AnodetransmitsanRTSthatdoesnotcollidewith Anumberofsimulationexperimentsispresentedtoin- anyothertransmissionswithanon-zeroprobability. vestigate the performance of CHAT under different net- A1) All nodes execute CHAT correctly over a perfect work topologies and to show how the results compare channel. againstCHMAandMACA-CT.WeusedtheOPNETsim- A2) The maximum end-to-end propagation time is , thetransmissiontimeofanRTSandaCTSis ,th(cid:28)e ulation tool [4] to implement all three protocols consid- transmission time of a SRTS is variable, the (cid:13)trans- eredinourexperiments. Forthesimulationexperiments, weusedamulti-channelcapableradiothatapproximates missiontimeofadatapacketis ,andthehardware transmit-to-receive transition timÆe is zero; further- a commercially available frequency hopping radio oper- ating over the 2.4GHz ISM band. By using the external more, . A3) The2d(cid:28)w<ell(cid:13)ti(cid:20)meÆ <in1each hop is equal to the time model access (EMA) capability of the OPNET simula- tion tool, we produced a radio modelwith 79 frequency neededto transmit an RTS (or CTS) plus the maxi- channels with 1Mhz bandwidth and maximum data rate mumend-to-endpropagationtime. of1Mbps. Becauseallthecommerciallyavailableradios Theorem1: CHAT provides correct collision avoid- are half duplex, the simulated radio can only receive or ance in the presence of hidden terminals when the time transmitdataatthesametime. spentexchangingdataisshorterthanthetimeelapsedbe- forethesamefrequencyhopisreusedinthecommonhop- Nodesareassumedtobeapproximatelyonemileaway pingsequence. fromeachother,givingamaximumpropagationdelayof Proof: Consider a transmitting node and a receiving 5microseconds.Weincludedanoverheadof24microsec- node andassumethat sendsanRATSattime . We ondstoaccountforreceive-to-transmitturn-aroundtime, denotXewith thedwelltimAeinaparticularhop.If t0does the necessary framing (preamble)bits, and guard-bands. notreceivethheRTScorrectlyduetointerferencefrXomany Becausethesize ofanRTSisequalto 96bits, wechose neighborhiddenfrom , itdoesnottransittothepartic- ourslotstobeequalto120microsecondsor120bitssince ularbasefrequencyinAwhich iswaitingtotransmitit’s ourradioshavea data rateof1Mbps. Whentwo control dataandconsequentlynodataAaresent. Else, receives packetscollidetheyback-offforanamountoftimethatis ’s RTS at time andtransits to tXhe particu- exponentiallydistributed up to the size of a data packet. lAarbasefrequencty1sp=ecti0fie+dhintheRTSfrom . Attime Ifanodefailstoinitiateahandshakeaftersevenretrans- ,node hasreceivedaSRTSfromA andre- missions,thedatapacketisdroppedfromtheheadofthe 0 st1po>ndts0w+ithhaCTSX.Node isthenenabledtotraAnsmitit’s queue. datapacket.Bothnodes Aand hopinthesamehopping Figure4showsthevarioustopologiesusedintheexper- patternthatnevercollideAswithXanyotherhoppingpattern iments.Figure4(a)showsabasestationnetworkinwhich since we have made the assumption that time spent ex- allthetrafficproducedfromnodes to isdirected changingdatais shorterthanthe timeelapsedbeforethe tothecentralnode, . Figure4N(b1)shoNw1s6twogroups samefrequencyhopisreusedinthecommonhoppingse- ofeightnodesthatcBanasheeareachothernodein the same quence.Clearly,thesizeofadatapackettrainmustbere- groupbutarehiddenfromallthenodesintheothergroup. strictedtothemaximumnumberofdatapacketsthatcan Again,trafficisgeneratedfromallthenodesineachgroup betransmittedbeforethesamefrequencychanneloccurs withdestinationthecentralbasestation . InFigure againinthecommonhoppingsequence. 4(c) a multi-hop network of sixteen nodBeassien a four di- 2 THROUGHPUT FOR N=16 N1 Base N16 N2 N15 N3 N14 4 N4 N13 CHAT N5 N12 N6 N11 N7 N8 N9 N10 CHMA T (a) SLO3 S per T E K C A MACA-CT P Base MINI2 N T I U P H G U O (b) R TH1 9 11 1 3 8 10 0 2 0 0.1 0.2 0.3 0.4 0.5 0.6 PROBABILITY OF TRANSMISSION IN A SLOT p 13 15 5 7 Fig.5. AggregatethroughputforCHAT,CHMAandMACA-CTforthe 12 14 topologyinFig.4(b);thenumberofnodesisN=16andthepacket 4 6 lengthisL=10orapproximately150bytes (c) Fig.4. Variousnetworktopologiesusedinthesimulations theothertwotopologiesaswell.Asalsoshownwithanal- ysisin[8]CHMAoutperformsMACA-CTunderanyof- feredloadbyminimizingthecriticalvulnerabilityperiod mensionalhypercubeconfigurationisdepicted. Thelines during which collisions between the control packets can betweenthenodesshowtheconnectivityinthenetwork. occur. Inaddition,CHATexploitsthefactthatmorethan These topologies were chosen for two reasons: to com- onedatapacketscanbetransmittedinjustasimplecon- parewith similar topologiesused in priorwork on colli- trolpackethandshaketofurtherimprovetheutilizationof sionavoidance[2],andtotesttheperformanceofthepro- the medium. Especially under medium to heavy offered tocolsunderwidelydifferentconditions. Noticealsothat load CHAT seems to outperform CHMA by more than eventhoughwith topologies4(a) and 4(b)a packettrain 10%.Whenthedatarateishigherthanwhattheradiocan consists of two or more data packets with the same des- deliver,packetsarelostandtheperformanceofCHATde- tination (the base station), with topology 4(c) in a given gradestothatofCHMA. packettraintheremightbetwoormoredatapacketseach ToexaminethebenefitsofCHATwhenwehavebroad- with a differentdestination address. In this case, CHAT castoramixofbroadcastandunicasttrafficasetofsim- cantakeadvantageofitsspecialhandshakemechanismto ulationswasperformedwiththenetworkshowninFigure servebroadcasttrafficbytransmittingjustonepackettoa 4(c). Firstweassumedonlybroadcasttrafficandthenwe numberofnodesatthesametime. created a mix of broadcastand unicasttraffic with equal DatapacketsaregeneratedaccordingtoaPoissondis- probability(i.e. 50%of the traffic is broadcastand 50% tribution and the data packet size is assumed to be con- isunicast).Theretransmissionpolicyforbroadcastpack- stant equal to 150 bytes, which equals to approximately ets is the same as the one mentioned before for unicast 10 slots (i.e. ) of 120 bits each. The simu- onlytraffic. Since a broadcastpacketis notsuccessfully latedradiomodLeli=nclu1d0esextraoverheadbitsforamore transmitted unless all neighborshave received a copy of accurate representation of the physical effects that take it, in the presence of broadcast traffic we calculate the placewhenapacketissentorreceived(i.e. framingbits, throughput as a single packet exchange. The through- padding bits). To demonstrate that the performance of putresultsforbroadcastonlytrafficare shownin Figure anychannel-hoppingprotocoldoesnotdependonthese- 6. Clearly, the throughputforMACA-CT andCHMA is lected network topology, we collected simulation results much lower than the correspondingone presentedprevi- forallthreetopologiesshowninFigure4.Figure5shows ously with only unicast traffic. Even though there is a the throughput results measured for CHAT, CHMA and penaltywithCHATaswell,thedifferenceisconsiderably MACA-CTforthe networktopologyshownin Fig. 4(b) smaller than MACA-CT and CHMA. Notice that when forunicasttrafficonly. Similar,resultswereobtainedfor broadcasttrafficispresentwithMACA-CTandCHMAa THROUGHPUT FOR N=16 THROUGHPUT FOR N=16 CHAT unicast CHAT unicast 4 CHMA unicast 4 CHMA unicast T T CHAT mix O O SL3 CHAT broadcast SL3 S per S per CHMA mix T T E E K K C C A MACA-CT unicast A MACA-CT unicast P P NI NI MI2 MI2 T IN T IN MACA-CT mix U CHMA broadcast U P P H H G G U U O MACA-CT broadcast O R R H H T1 T1 0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 PROBABILITY OF TRANSMISSION IN A SLOT p PROBABILITY OF TRANSMISSION IN A SLOT p Fig.6. Aggregatethroughput forCHAT,CHMAandMACA-CTfor Fig.7. Aggregate throughputforCHAT,CHMAandMACA-CTfor thetopologyinFig.4(c);broadcastonlytrafficiscomparedagainst thetopologyinFig. 4(c); amixofbroadcastandunicasttrafficis unicastonly;thenumberofnodesisN=16andthepacketlengthis comparedagainstunicastonly;thenumberofnodesisN=16and L=10orapproximately150bytes thepacketlengthisL=10orapproximately150bytes numberofunicastpacketsequalto thenumberofneigh- CHAT against CHMA [8] and MACA-CT [5], which is bors of a given node has to be successfully transmitted arecentexampleofcollision-avoidanceprotocolsthatdo before the broadcast transmission is completed. With not require carrier sensing but need code assignment to CHATa nodecanbroadcasta datapacketwith lesscon- operate correctly. For this comparison, we performed a trolpackethandshakes.Especiallyunderlighttomedium largenumberofsimulationexperimentswithvariousnet- loads where most of the neighbors of a given node are worktopologies,andshowedthatCHATachieveshigher idle, a broadcast packet is sent with just a few attempts throughputthan CHMA and MACA-CT for unicast and leading to throughputthat is almost equal to the case of broadcast traffic, without the need for carrier sensing or unicastonlytraffic. anycodeassignments. Similarconclusionscanbedrawnwhenamixofbroad- cast and unicast traffic is generated. As can be seen in REFERENCES Figure 7 in this case the throughput for MACA-CT and [1] WirelessLANMediumAccessControl(MAC)andPhysicalLayer (PHY)specifications. IEEEStandard802.11,June1999. CHMAisalsoreducedmuchmorethanCHATbutsince [2] C.L.FullmerandJJ.Garcia-Luna-Aceves. Solutions toHidden half of the traffic is unicast the difference is not as big Terminal Problems in Wireless Networks. In Proceedings ACM as in the case of broadcastonly traffic. When there is a SIGCOMM,Cannes,France,September1997. [3] J. J. Garcia-Luna-Aceves and A. Tzamaloukas. Reversing the mixofbroadcastandunicasttraffic, CHAT cancombine Collision-AvoidanceHandshakeinWirelessNetworks.InProceed- inthesamepackettrainbroadcastaswellasunicastdata ingsACMMobiCom’99,Seattle,Washington,August1999. packets. The capability of CHAT to support efficiently [4] MIL3Incorporation. ExternalModelAccess. ExternalInterfaces. [5] M.Joa-NgandI.Lu. SpreadSpectrumMediumAccessProtocol broadcast traffic is a key feature of CHAT, because the withCollisionAvoidanceinMobileAd-HocWirelessnetworks. In routingcontrolandmanyapplicationsrunningonadhoc Proc.IEEEINFOCOM99,April1999. networksarebasedonbroadcastpacketdelivery. [6] E.S.SousaandJ.A.Silvester. SpreadingCodeProtocolsforDis- tributedSpreadSpectrumPacketRadioNetworks. IEEETransac- tionsonCommunications,36,March1988. V. CONCLUSIONS [7] F.A.TobagiandL.Kleinrock.PacketSwitchinginRadioChannels: PartIII-Pollingand(dynamic)SplitChannelReservationMultiple We introduced a channel access control protocol that Access. IEEETransactionsonComputers, 24(7):832–45, August can be used in any commercially available, wireless ra- 1976. [8] A.TzamaloukasandJ.J.Garcia-Luna-Aceves. Channel-Hopping dio operating in an ISM band. CHAT uses the concept Multiple-Access. InProceedingsIEEEInternationalCommunica- of packet train data transmissions to minimize the num- tionsConference(ICC’00),NewOrleans,Louisiana,June2000. ber of control packets needed to establish a collision- free packet exchange for unicast, multicast, and broad- cast traffic. We compared the throughputachieved with