2023學(xué)年完整公開課版AnticollisionAlgorithmofbinarytreesearch_第1頁
2023學(xué)年完整公開課版AnticollisionAlgorithmofbinarytreesearch_第2頁
2023學(xué)年完整公開課版AnticollisionAlgorithmofbinarytreesearch_第3頁
2023學(xué)年完整公開課版AnticollisionAlgorithmofbinarytreesearch_第4頁
2023學(xué)年完整公開課版AnticollisionAlgorithmofbinarytreesearch_第5頁
已閱讀5頁，還剩15頁未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

Presenter:MiZhiqiangHunanModernLogisticsCollegeAnti-collisionAlgorithmofBinaryTreeSearchContents1BinaryTreeSearchAlgorithms2Implementationstepsofbinarytreesearchalgorithm3BinarysearchalgorithmThebasicideaofthebinarytreesearchalgorithm(themodelisshowninFigure7-11)istodividetheconflictingtagsintotwoleftandrightsubsets0and1,andfirstquerythesubset0.Ifthereisnoconflict,thelabeliscorrectlyidentified.Ifthereisaconflict,splitagain,dividethesubset0intotwosubsetsof00and01,andsoon,untilallthelabelsinthesubset0areidentified,andthenfollowthissteptoquerythesubset1.Binarytreesearchalgorithm01Figure7-11BinarytreesearchalgorithmmodelconflictingnodeNon-conflictingnode01BinarytreesearchalgorithmThebinarytreesearchalgorithmisbasedonauniqueserialnumberidentificationtag.Thebasicprincipleisasfollows:thereadersendsabitprefixp0p1...piineveryquery,andonlythetagmatchingtheprefixrespondstothereadercommand.Whenthereisonlyonetagresponse,thereadersuccessfullyidentifiesthetag;whentherearemultipletagsresponding,aconflictoccurs.Inthenextiteration,thereaderaddsabit0or1tothequeryprefixandsetsaqueueQinthereadertosupplementtheprefix.ThisqueueQisinitializedwith0and1,andthereaderqueriestheprefixfromQandsendsthisprefixineachiteration.Whentheprefixp0p1...piisaconflictingprefix,thereadersetsthequeryprefixtop0p1...piandputstheprefixp0p1...piintothequeueQ.Then,thereadercontinuesthisoperationuntilthequeueQisempty.Byconstantlyincreasinganddecreasingthequeryprefix,thereadercanidentifyallthetagsinitsreadingarea.Implementationstepsofbinarytreesearchalgorithm02(1)Thereaderbroadcaststhemaximumsequencenumber(11111111),queriestheprefixQforthetagresponsewithinitsscope,andtransmitstheserialnumbertothereader.(2)Thereadercomparesthenumberofthesamedigitsoftheserialnumberofthetagresponse.Ifthereisaninconsistency(thatis,thebitofthesequencenumberis0,andthebitofthesequencenumberis1),thereisacollision.(3)Afteridentifyingthatthereisacollision,thehighestposition0ofthenumberofinconsistentbitsgoestothequeryprefixQ,andthelabelwhoseserialnumberisgreaterthanQissequentiallyexcluded.(4)Afteridentifyingthelabelwiththesmallestserialnumber,performdataoperationonit,andthenenterthe"silent"state,anddonotrespondtothequerycommandsentbythereader.(5)Repeatstep(1)toselectthelabelwiththeserialnumberasthepenultimate.(6)Theidentificationofalltagsiscompletedaftermultiplecycles.02ImplementationstepsofbinarytreesearchalgorithmTheRFcardenterstheworkingrangeofthereader.ThereadersendsamaximumserialnumbertoallowallRFcardstorespond;atthesametime,theytransmittheserialnumbertothereceivermoduleofthereader.ThereadercomparesthenumberofidenticaldigitsoftheserialnumberoftheRFcardresponse.InconsistentThatis,someserialnumberis0,andotherserialnumberis1Setthenumberofinconsistentbitsfromthehighesttothelowestandthenoutputtheserialnumber,thatis,excludethenumberwiththelargeserialnumber,andwhenthenumberofthesamedigitsoftheserialnumberoftheRFcardresponseisexactlythesame,thereisnocollision.Afterselectingthesmallestnumberofserialnumbers,thelabelisexchangedfordata,andthenthecardisputintoa"silent"state.YN02ImplementationstepsofbinarytreesearchalgorithmSupposethereare4tagswhoseserialnumbersare10110010,10100011,10110011,and11100011,respectively.ThebinarysearchalgorithmimplementationprocessisshowninTable7-1.QueryprefixQFirstquery11111111Secondquery10111111Thirdquery10101111Labelresponse1×1×001×101×001×10100011TagA1011001010110010

TagB101000111010001110100011TagC1011001110110011

TagD11100011

Table7-1ImplementationprocessofbinarytreesearchalgorithmNote:×indicatesaconflict.02ImplementationstepsofbinarytreesearchalgorithmDynamicbinarynumbersearchalgorithmAnimprovedbinarytreesearchalgorithmhasbeenproposedforthetimerequiredandthepowerconsumedforthetagtotransmitdata.Theimprovedideaistodividethedataintotwoparts,andthereaderandthetagrespectivelytransmitapartofthedata,therebytheamountofdatatransferredisreducedbyhalftoachievethepurposeofshorteningthetransmissiontime.Accordingtotheideaofthebinarytreesearchalgorithm,whenthetagIDmatchesthequeryprefix,thetagonlytransmitstheremainingbits,whichcanalsoreducethenumberofbitspertransmission,therebyshorteningthetransmissiontimeandultimatelyshortentheexecutiontimeofanti-collision.02ImplementationstepsofbinarytreesearchalgorithmA:10100111B:10110101C:10101111D:10111101R:11111111R:11111111RstandsforreaderSendtheREQUEST(11111111)command,requestallthetagsintheareatorespond.AccordingtotheManchestercode,thedecodeddatais101??1?1,andthecollisionoccurs.Thealgorithmisasfollows,thehighestcollisionissetto0,andtheothercollisionpositionsare1.GotthenextREQUEST(10101111)02ImplementationstepsofbinarytreesearchalgorithmA:10100111C:10101111R:10101111R:10101111RstandsforreaderSendtheREQUEST(10101111)command,andtagsAandCrespond.Thedecodeddatais1010?111,andthecollisionoccurs.Thealgorithmisasfollows,thehighestcollisionissetto0,andtheothercollisionpositionsare1.Got1010011102ImplementationstepsofbinarytreesearchalgorithmA:10100111C:10101111R:10100111R:10100111CanrecognizeASendtheREQUEST(10100111)command,onlythetagAanswers.Thedecodeddatais1010?111,nocollisionoccurs,andthereaderreadsthetagA.02ImplementationstepsofbinarytreesearchalgorithmRstandsforreaderFirstquerySecondqueryThirdqueryFourthqueryFifthquerySendserialnumberReceiveserialnumberTagATagBTagCTagD1010011110110101101011111011110111111111101??1?11010111110100111101011111010?1111010011110100111RecognizeTagA10110101101011111011110111111111101??1?11010111110101111RecognizeTagCQueryprocessofimprovedAnti-collisionAlgorithm02ImplementationstepsofbinarytreesearchalgorithmSixthquerySeventhqueryEighthqueryNinthqueryTenthquerySendserialnumberReceiveserialnumberTagATagBTagC

TagD1011010110111101111111111011?1011011010110110101101111011011110102ImplementationstepsofbinarytreesearchalgorithmRecognizeTagCRecognizeTagCQueryprocessofimprovedAnti-collisionAlgorithmBinarysearchalgorithm03Thebinarysearchalgorithmissimilartothesuccessivecomparisonmethodusedinthebalance.Itcontinuouslyfiltersoutdifferentserialnumbersthroughmultiplecomparisons,andperformstime-multiplexedsignalexchangebetweenthereaderandthetag,andisbasedonauniqueserialnumberidentificationtag.Inordertoselectoneofasetoftags,thereaderissuesarequestcommandtoconsciouslydirectthedatacollisionwhenthetagserialnumberistransmittedtothereader,thatis,identifywhetherthecollisionoccursbythereader,andifthereisacollision,narrowtherangetomakeafurthersearch.Thebinarysearchalgorithmconsistsofasetofcommandandresponserulesdefinedbetweenareaderandmultipletags.Thepurposeistoselectanyoneofthemultiplecardstoimplementdatacommunication.Thealgorithmhasthreekeyelements:Usetheappropriatebasebandcoding(easytoidentifycollisions)UtilizesuniqueserialnumberofthetagcardDesignasetofeffectiveinstructionrulestoefficientlyandquicklyselectcard1)ManchesterCode(Mancherster)Intheimplementationofthebinarysearchalgorithm,itisdecisivethatthesignalencodingusedbythereadermustbeabletodeterminetheexactbitpositionofthecollision.Manchestercodecandecodetheerrorcodewordwhenmultiplecardsrespondatthesametime,andcanrecognizethecollisionbybit,sothatthetagcanbesearchedagainaccordingtothepositionofthecollisionbycertainrules.Manchestercodingandanti-collisioncodingusesthefollowingrules:alogic"1"indicatesafallingedgetransition;alogic"0"indicatesarisingedgetransition;ifnostatetransitions,itisidentifiedasanerror.Whenthedigitsreturnedbymultipletagshavedifferentvaluesatthesametime,therisingandfallingedgescanceleachotherout,andthestatelessjumps,thereaderknowsthatthebitcollidesandgeneratesanerror.03Binarysearchalgorithm1)ManchesterCode(Mancherster)TheManchestercodeisusedtoidentifythecollisionbit:asshowninFigure7-12,iftherearetwotagswhoseIDnumbersare10011111and10111011,ManchestercanrecognizethecollisionofD5andD2bits.Figure7-12Manchesterbitrecognitioncollisionbit03BinarysearchalgorithmIDofTAG1IDofTAG2IDcollusionreceivedbyreaders2)Anti-collisioninstructionrulesREQUESTSERIELNO.

SELECTSERIELNO.Thiscommandsendsaserialnumberasaparametertothelabel.Theresponseruleis:thetagcomparesitsownserialnumberwiththereceivedseria

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論