《二進(jìn)制樹搜索算法》

課程回顧RFID技術(shù)☆ RFID組成 RFID工作原理整理ppt在RFID系統(tǒng)，因?yàn)槎鄠€(gè)讀寫器和多個(gè)標(biāo)簽造成的讀寫器之間和標(biāo)簽之間的互相干擾，統(tǒng)稱為碰撞。什么是碰撞碰撞的類型1.讀寫器碰撞2.標(biāo)簽碰撞防碰撞算法2.2RFID技術(shù)RFID工作原理整理ppt現(xiàn)有的基于TDMA防沖突算法可以分為基于ALOHA的算法和基于二進(jìn)制樹兩種類型。2.2RFID技術(shù)RFID工作原理Binary-Tree(二進(jìn)制樹)算法簡介純ALOHA防沖突算法分時(shí)隙的ALOHA防沖突算法（S-ALOHA）DynamicBinary-Tree算法標(biāo)簽防碰撞方法☆整理ppt在算法執(zhí)行過程中，讀寫器要多次發(fā)送命令給電子標(biāo)簽，每次命令都把標(biāo)簽分成兩組，多次分組后最終得到唯一的一個(gè)標(biāo)簽。在這個(gè)分組過程中，將對應(yīng)的命令參數(shù)以節(jié)點(diǎn)的形式存儲起來，就可以得到一個(gè)數(shù)據(jù)的分叉樹，而所有的這些數(shù)據(jù)節(jié)點(diǎn)又是以二進(jìn)制的形式出現(xiàn)的，所以稱為“二進(jìn)制樹”。Binary-Tree(二進(jìn)制樹)算法☆2.2RFID技術(shù)RFID工作原理001100000100何為“二進(jìn)制樹”？整理ppt101100001110??????射頻卡1射頻卡2讀寫器譯碼曼徹斯特碼(Mancherster)可在多卡同時(shí)響應(yīng)時(shí)，譯出錯(cuò)誤碼字，可以按位識別出碰撞。這樣可以根據(jù)碰撞的位置，按一定法則重新搜索射頻卡。如何確定碰撞的準(zhǔn)確比特位置？整理ppt二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號至讀寫器。整理ppt范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示閱讀器整理ppt二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號至讀寫器。（2）讀寫器對收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號位為0，有的序列號該位為1），則可判斷有碰撞。整理ppt范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示閱讀器101??1?1整理ppt二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號至讀寫器。（2）讀寫器對收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號位為0，有的序列號該位為1），則可判斷有碰撞。（3）確定有碰撞后，把有不一致位的數(shù)最高位置0再輸出查詢條件Q，依次排除序列號大于Q的標(biāo)簽。整理ppt范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示閱讀器R:10101111101??1?1整理ppt搜尋標(biāo)簽過程A:10100111C:10101111R:10101111R:10101111送REQUEST（10101111）命令，標(biāo)簽A和C應(yīng)答。解碼數(shù)據(jù)為1010?111,發(fā)生碰撞，算法做下如下，將碰撞的最高置0，其它碰撞位置1。得10100111?R表示閱讀器R:10100111整理ppt范例：A:10100111C:10101111R:10100111R:10100111

送REQUEST（10100111）命令，只有標(biāo)簽A應(yīng)答。沒有發(fā)生碰撞，閱讀器對標(biāo)簽A進(jìn)行閱讀操作。R表示閱讀器可以識別AB:10110101D:10111101整理ppt二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件Q，其作用范圍內(nèi)的標(biāo)簽在同一時(shí)刻傳輸他們的序列號至讀寫器。（2）讀寫器對收到的標(biāo)簽進(jìn)行相應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號位為0，有的序列號該位為1），則可判斷有碰撞。（3）確定有碰撞后，把有不一致位的數(shù)最高位置0再輸出查詢條件Q，依次排除序列號大于Q的標(biāo)簽。（4）識別出序列號最小的標(biāo)簽后，對其進(jìn)行數(shù)據(jù)操作，然后使其進(jìn)入“無聲”狀態(tài)，則對讀寫器發(fā)送的查詢命令不進(jìn)行響應(yīng)。（5）重復(fù)步驟1，選出序列號倒數(shù)第二的標(biāo)簽。（6）多次循環(huán)完后完成所有標(biāo)簽的識別。整理pptImprovedAnti-collisionAlgorithm搜尋過程第一次搜尋第二次搜尋第三次搜尋第四次搜尋第五次搜尋發(fā)送序號接收序號TagATagBTagCTagD1010011110110101101011111011110111111111101??1?11010111110100111101011111010?1111010011110100111識別TagA10110101101011111011110111111111101??1?11010111110101111識別TagC整理pptImprovedAnti-collisionAlgorithm搜尋過程第六次搜尋第七次搜尋第八次搜尋第九次搜尋第十次搜尋發(fā)送序號接收序號TagATagBTagC

TagD1011010110111101111111111011?10110110101101101011011110110111101識別TagB識別TagD整理ppt二進(jìn)制搜索算法的工作流程是：出現(xiàn)不一致的現(xiàn)象射頻卡進(jìn)入讀寫器的工作范圍，讀寫器發(fā)出一個(gè)最大序列號讓所有射頻卡響應(yīng)；同一時(shí)刻開始傳輸它們的序列號到讀寫器的接收模塊。讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)。即有的序列號該位為0，而有的序列號該位為1把有不一致位的數(shù)從最高位到低位依次置O再輸出系列號，即依次排除序列號大的數(shù)，至讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)完全一致時(shí)，說明無碰撞。選出序列號最小的數(shù)后，對該標(biāo)簽進(jìn)行數(shù)據(jù)交換，然后使該卡進(jìn)入“無聲”狀態(tài)。YN整理ppt算法性能分析：

為了從N個(gè)標(biāo)簽中找出唯一一個(gè)標(biāo)簽，需要進(jìn)行多次請求，其平均次數(shù)L為：L=log2N+1則基本二進(jìn)制樹算法識別N個(gè)標(biāo)簽所需的總查詢次數(shù)為：SUM(N)=N·(log2N+1）查詢次數(shù)是一個(gè)關(guān)于N和L的增函數(shù)，要識別一個(gè)標(biāo)簽，請求次數(shù)L隨著N值的增大而迅速增加。并且標(biāo)簽每次響應(yīng)閱讀器的請求命令時(shí)所傳的ID都是完整ID。整理pptDynamicBinary-Tree算法在BasicBinary-Tree算法中，標(biāo)簽每次回送給閱讀器的序列號必須是全序列號。然而標(biāo)簽的序列號并不只是由單字節(jié)構(gòu)成，而是根據(jù)實(shí)際需要可能長達(dá)10多個(gè)字節(jié)。對于這種長序列號的標(biāo)簽，假如每次都完整的傳輸其ID值，需要傳輸?shù)臄?shù)據(jù)量很大，再加上閱讀器也是以同樣長度的ID值作為參數(shù)互相傳遞，則會花費(fèi)很長的時(shí)間，造成識別延遲，降低系統(tǒng)效率。為減少標(biāo)簽和閱讀器之間傳輸?shù)臄?shù)據(jù)量，提高閱讀器的識別效率，在BasicBinary-Tree算法的基礎(chǔ)上，提出了一種改進(jìn)的防碰撞算法，稱其為DynamicBinary-Tree算法。2.2RFID技術(shù)RFID工作原理整理ppt現(xiàn)有的基于TDMA防沖突算法可以分為基于ALOHA的算法和基于二進(jìn)制樹兩種類型。2.2RFID技術(shù)RFID工作原理Binary-Tree(二進(jìn)制樹)算法簡介純ALOHA防沖突算法分時(shí)隙的ALOHA防沖突算法（S-ALOHA）DynamicBinary-Tr