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

1、課程回顧課程回顧rfid技術(shù)rfid組成rfid工作原理在在rfid系統(tǒng)，因?yàn)槎鄠€讀寫器和多個標(biāo)簽造成的系統(tǒng)，因?yàn)槎鄠€讀寫器和多個標(biāo)簽造成的讀寫器之間和標(biāo)簽之間的互相干擾，統(tǒng)稱為碰撞。讀寫器之間和標(biāo)簽之間的互相干擾，統(tǒng)稱為碰撞。什么是碰撞什么是碰撞碰撞的類型碰撞的類型1.讀寫器碰撞讀寫器碰撞2.標(biāo)簽碰撞標(biāo)簽碰撞防碰撞算法 2.2 rfid技術(shù)rfid工作原理l現(xiàn)有的基于現(xiàn)有的基于tdma防沖突算法可以分為防沖突算法可以分為基于基于aloha的算法和的算法和基于二進(jìn)制樹基于二進(jìn)制樹兩種類型。兩種類型。 2.2 rfid技術(shù)rfid工作原理binary-tree(二進(jìn)制樹二進(jìn)制樹)算法簡介算法簡介

2、純純aloha防沖突算法防沖突算法分時隙的分時隙的aloha防沖突算法（防沖突算法（s-aloha）dynamic binary-tree 算法算法標(biāo)簽防碰撞方法在算法執(zhí)行過程中，讀寫器要多次發(fā)送命令給電子標(biāo)簽，每次命令都把標(biāo)簽分成兩組，多次分組后最終得到唯一的一個標(biāo)簽。在這個分組過程中，將對應(yīng)的命令參數(shù)以節(jié)點(diǎn)的形式存儲起來，就可以得到一個數(shù)據(jù)的分叉樹，而所有的這些數(shù)據(jù)節(jié)點(diǎn)又是以二進(jìn)制的形式出現(xiàn)的，所以稱為“二進(jìn)制樹”。binary-tree(二進(jìn)制樹)算法 2.2 rfid技術(shù)rfid工作原理001100000100何為何為“二進(jìn)制樹二進(jìn)制樹”？101100001110?射頻卡1射頻卡2讀寫

3、器譯碼曼徹斯特碼曼徹斯特碼(mancherster)(mancherster)可在多卡同時響應(yīng)時可在多卡同時響應(yīng)時，譯出錯誤碼字，可以按位識別出碰撞。這樣可，譯出錯誤碼字，可以按位識別出碰撞。這樣可以根據(jù)碰撞的位置，按一定法則重新搜索射頻卡以根據(jù)碰撞的位置，按一定法則重新搜索射頻卡。如何確定碰撞的準(zhǔn)確比特位置？如何確定碰撞的準(zhǔn)確比特位置？二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件q，其作用范圍內(nèi)的標(biāo)簽在同一時刻傳輸他們的序列號至讀寫器。范例：范例：a:10100111b:10110101c:10101111d:10111101r:11

4、111111r:11111111r表示閱讀器二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件q，其作用范圍內(nèi)的標(biāo)簽在同一時刻傳輸他們的序列號至讀寫器。（2）讀寫器對收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號位為0，有的序列號該位為1），則可判斷有碰撞。范例：范例：a:10100111b:10110101c:10101111d:10111101r:11111111r:11111111r表示閱讀器101?1?1二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件q，其作用范圍內(nèi)的標(biāo)簽

5、在同一時刻傳輸他們的序列號至讀寫器。（2）讀寫器對收到的標(biāo)簽進(jìn)行響應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號位為0，有的序列號該位為1），則可判斷有碰撞。（3）確定有碰撞后，把有不一致位的數(shù)最高位置0再輸出查詢條件q，依次排除序列號大于q的標(biāo)簽。范例：范例：a:10100111b:10110101c:10101111d:10111101r:11111111r:11111111r表示閱讀器r:10101111101?1?1搜尋標(biāo)簽過程a:10100111c:10101111r:10101111r:10101111送request（10101111）命令，標(biāo)簽a和c應(yīng)答。解碼數(shù)據(jù)為1010?111,發(fā)

6、生碰撞，算法做下如下，將碰撞的最高置0，其它碰撞位置1。得10100111?r表示閱讀器r:10100111范例：范例：a:10100111c:10101111r:10100111r:10100111 送request（10100111）命令，只有標(biāo)簽a應(yīng)答。沒有發(fā)生碰撞，閱讀器對標(biāo)簽a進(jìn)行閱讀操作。r表示閱讀器可以識別ab:10110101d:10111101二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：二進(jìn)制樹搜索算法的實(shí)現(xiàn)步驟如下：（1）讀寫器廣播發(fā)送最大序列號查詢條件q，其作用范圍內(nèi)的標(biāo)簽在同一時刻傳輸他們的序列號至讀寫器。（2）讀寫器對收到的標(biāo)簽進(jìn)行相應(yīng)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號位為0，

7、有的序列號該位為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)簽的識別。improved anti-collision algorithm搜尋過程搜尋過程第一次搜尋第二次搜尋第三次搜尋第四次搜尋第五次搜尋發(fā)送序號接收序號tagatagbtagctagd1010011110110101101011111011110111111111101?1?1

8、1010111110100111101011111010?1111010011110100111識別taga10110101101011111011110111111111101?1?11010111110101111識別tagcimproved anti-collision algorithm搜尋過程搜尋過程第六次搜尋第七次搜尋第八次搜尋第九次搜尋第十次搜尋發(fā)送序號接收序號tagatagbtagc tagd1011010110111101111111111011?10110110101101101011011110110111101識別tagb識別tagd二進(jìn)制搜索算法的工作流程是：出現(xiàn)不一

9、致的現(xiàn)象出現(xiàn)不一致的現(xiàn)象射頻卡進(jìn)入讀寫器的工作范圍，讀寫器發(fā)出一個最大序列號讓射頻卡進(jìn)入讀寫器的工作范圍，讀寫器發(fā)出一個最大序列號讓所有射頻卡響應(yīng)；同一時刻開始傳輸它們的序列號到讀寫器的所有射頻卡響應(yīng)；同一時刻開始傳輸它們的序列號到讀寫器的接收模塊。接收模塊。讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)。讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)。即有的序列號該位即有的序列號該位為為0 0，而有的序列，而有的序列號該位為號該位為1 1把有不一致位的數(shù)從最高位到低位依次置把有不一致位的數(shù)從最高位到低位依次置o o再輸出系列號再輸出系列號，即依次排除序列號大的數(shù)，至讀寫器對比射頻卡響應(yīng)，即依次排

10、除序列號大的數(shù)，至讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)完全一致時，說明無碰撞。的序列號的相同位數(shù)上的數(shù)完全一致時，說明無碰撞。選出序列號最小的數(shù)后，對該標(biāo)簽進(jìn)行數(shù)據(jù)交換，然后選出序列號最小的數(shù)后，對該標(biāo)簽進(jìn)行數(shù)據(jù)交換，然后使該卡進(jìn)入使該卡進(jìn)入“無聲無聲”狀態(tài)。狀態(tài)。y yn n算法性能分析：算法性能分析：l為了從n個標(biāo)簽中找出唯一一個標(biāo)簽，需要進(jìn)行多次請求，其平均次數(shù)l為：ll=log2n+1l則基本二進(jìn)制樹算法識別n個標(biāo)簽所需的總查詢次數(shù)為：sum(n)=n(log2n+1）l查詢次數(shù)是一個關(guān)于n和l的增函數(shù)，要識別一個標(biāo)簽，請求次數(shù)l隨著n值的增大而迅速增加。并且標(biāo)簽每次響應(yīng)閱讀器

11、的請求命令時所傳的id都是完整id。19dynamic binary-tree 算法l在在basic binary-tree算法中，標(biāo)簽每次回送給算法中，標(biāo)簽每次回送給閱讀器的序列號必須是全序列號。然而標(biāo)簽的閱讀器的序列號必須是全序列號。然而標(biāo)簽的序列號并不只是由單字節(jié)構(gòu)成，而是根據(jù)實(shí)際序列號并不只是由單字節(jié)構(gòu)成，而是根據(jù)實(shí)際需要可能長達(dá)需要可能長達(dá) 10 多個字節(jié)。對于這種長序列多個字節(jié)。對于這種長序列號的標(biāo)簽，假如每次都完整的傳輸其號的標(biāo)簽，假如每次都完整的傳輸其 id 值，需值，需要傳輸?shù)臄?shù)據(jù)量很大，再加上閱讀器也是以同要傳輸?shù)臄?shù)據(jù)量很大，再加上閱讀器也是以同樣長度的樣長度的 id 值作

12、為參數(shù)互相傳遞，則會花費(fèi)很值作為參數(shù)互相傳遞，則會花費(fèi)很長的時間，造成識別延遲，降低系統(tǒng)效率。長的時間，造成識別延遲，降低系統(tǒng)效率。l為減少標(biāo)簽和閱讀器之間傳輸?shù)臄?shù)據(jù)量，提高為減少標(biāo)簽和閱讀器之間傳輸?shù)臄?shù)據(jù)量，提高閱讀器的識別效率，在閱讀器的識別效率，在basic binary-tree算法算法的基礎(chǔ)上，提出了一種改進(jìn)的防碰撞算法，稱的基礎(chǔ)上，提出了一種改進(jìn)的防碰撞算法，稱其為其為dynamic binary-tree 算法。算法。 2.2 rfid技術(shù)rfid工作原理l現(xiàn)有的基于現(xiàn)有的基于tdma防沖突算法可以分為防沖突算法可以分為基于基于aloha的算法和的算法和基于二進(jìn)制樹基于二進(jìn)制樹兩種類型。兩種類型。 2.2 rfid技術(shù)rfid工作原理binary-tree(二進(jìn)制樹二進(jìn)制樹)算法簡介算法簡介純純aloha防沖突算法防沖突算法分時隙的分時隙的aloha防沖突算法（防沖突算法（s-aloha）dynamic binary-tree 算法算法標(biāo)簽防碰撞方法21rfid碰撞的概念碰撞的概念防沖突算法分類防沖突算法分類