计算机专业的外文文献.pdf

ARapidTagIdentificationMethodwithTwoSlotsinRFIDSystemsYongHwanKim,SungSooKim,KwangSeonAhnDepartmentofComputerEngineering,KyungpookNationalUniversityDaegu,Korea{hypnus,ninny,gsahn}@knu.ac.krAbstract—RFIDiscoretechnologyintheareaofubiquitouscompu-ting.Identifytheobjectsbeginwiththereader’squerytothetagat-tachedtothesubject.Whenmultipletagsexistinthereader’sinter-rogationzone,thesetagssimultaneouslyrespondtothereader’squery,resultingincollision.InRFIDsystem,thereaderneedstheanti-collisionalgorithmwhichcanquicklyidentifyallthetagsintheinterrogationzone.ThispaperproposestreebasedRapidTagIdenti-ficationMethodwithTwoSlots(RTIMTS).TheproposedalgorithmrapidlyidentifiesatagwiththeinformationofTwoSlotsandMSB(MostSignificantBit).TwoSlotsresolvethetagcollisionbyreceivingtheresponsefromthetagtotheSlot0and1.ThereadercanidentifytwotagsatonceusingMSBofinformationaddedtothetagID.WithRTIMTSalgorithm,thetotaltimeoftagidentificationcanbeshortenedbydecreasingthenumberofquery-responsesfromthereader.Keywords-RFID;Anti-collision;TwoSlots;thenumberofquery-responses.I.INTRODUCTIONRFID(RadioFrequencyIdentification)isatechnologythatdeciphersoridentifiesthetaginformationthroughareader(orinterrogator)withoutcontact.RFIDhavebecomeverypopularinmanyserviceindustries,purchasinganddistributionlogis-tics,industry,manufacturingcompaniesandmaterialflowsystems.AutomaticIdentificationproceduresexisttoprovideinformationaboutpeople,animals,goodsandproductsintran-sit[1][2].Thereaderreceivesrequiredinformationfromthetagsbysendingandreceivingwirelesssignalswiththetag.Sincethecommunicationbetweenthereadersandthetagsshareswire-lesschannels,thereexistcollisions.Thecollisionscanbedi-videdintothereadercollisionandthetagcollision.Thereadercollisionoccurswhenmultiplereaderssendrequestsignalstoonetag,andthetagreceivesthewrongrequestsignalduetosignalinterferencebetweenreaders.Thetagcollisionoccurswhenmorethantwotagssimultaneouslyrespondtoonereaderandthereadercannotidentifyanytags.Thiskindofcollisionmakesthereadertakelongtimetoidentifytagswithintheread-er’sidentificationrangeandimpossibletoidentifyevenonetag[3][4][5][6].Therefore,thecollisionisacrucialproblemthatmustbere-solvedinRFIDsystems,somanystudiestoresolvethisprob-lemhavebeencarriedoutaswellasareongoing.Thispaperfocusesonthetagcollisionproblemwhichoccursinthecasewhereonereaderidentifiesmultipletags.Figure1providesschematizationsofreadercollisionandtagcollision.ThispaperproposestheRapidTagIdentificationMethodwithTwoSlots(RTIMTS),forfastertagidentificationinmul-ti-tagenvironmentwhereonereaderidentifiesmultipletags.Inthetransferpaper[7],theproposedalgorithmdesignsthemethodthatitdoeswithoutthevalueextractingprocedureofeven(orodd)paritybitofIDbit(Tpb),thenumberofidentified‘1’s(T1n),thenumberofremaining‘1’s(Trn),andthenumberofcollidedbit(Tcb)withsimpleitcanpredictatagID.Maximum4tagIDscanbeidentifiedononeroundbyusingTwoslots.a)TheReadercollisionb)TheTagcollisionFigure1.ThecollisionprobleminRFIDSystemII.THERELATEDWORKSA.QueryTreeQueryTree(QT)algorithmisabinarytreebasedanticolli-sionalgorithmandhasanadvantageineasilyimplementationduetoitssimpleoperatingmode[8].QTsetsthereader’squeryandtag’sresponseasoneround,andidentifiestagsbyiteratingtheround.Ineachround,thereaderrequestsprefixtotag’sID.AndwhenIDmatchestheprefix,eachtagtransmitsallIDsincludingprefixestothereader.Atthistime,ifmorethanonetagsimultaneouslyresponds,thereadercannotrecognizetag’sID,butcanrecognizethattherearecurrentlymorethantwotagshavingtheprefix.Thenthereaderadds‘0’or‘1’tothecurrentprefixandqueriesthelongerprefixtothetagsagain.Whenonlyonetagrespondstothereader,itidentifiesthetag.Inotherwords,thereaderaddstheprefixby1bituntilonlyonetagrespondsanditeratesthisprocessuntilidentifyingallthetagswithintherange.Figure2showstheoperatingprocessofQTalgorithms[10].Figure2showstheprocessthatfourtagsrespondaccordingtothereaders’query.Inround1,2,3,and7,thecollisionoc-cursbecausemorethantwotagsrespond,andinround4,5,8,and9,tagcanbeidentifiedbecauseonlyonetagresponds.ThedigitalcodingmethodappliedtoQTcannotdetectthecollisionbits.Whenacollisionoccurs,thereaderadds‘0’or‘1’tothe2009EighthIEEEInternationalSymposiumonNetworkComputingandApplications978-0-7695-3698-9/09$25.00©2009IEEEDOI10.1109/NCA.2009.21292Authorizedlicenseduselimitedto:Xi'anUniversityofTechnology.DownloadedonJuly12,2010at03:17:11UTCfromIEEEXplore.Restrictionsapply.currentprefixandqueriesthisprefixtothetags.Whilehavingameritofthesimplerealization,thisgeneratesanidlecyclewhichhasnoresponselikearound6[10].Figure2.TheoperatingprocessofQueryTreealogrithmB.QueryTreewithCollision-BitPositioningThetagidentificationprocessoftheQueryTreewithcolli-sion-BitPositioning(QT-CBP)algorithmisasfollows[9].Ifacollisionoccurs,thereaderdetectsthelocationofthecollidedbitsandgetsthenumberofthecollidedbits.Ifonecollisionisgenerated,areaderestablishes‘0’and‘1’foracollidedbitanditsavesthemintomemory.Ifmorethantwocollisionsaregen-erated,areaderwillcreateanewqueryprefixbyappending‘0’and‘1’toqueriestoaheadoflocationbitwherethecollisio