1.二進(jìn)制樹(shù)搜索算法
     二進(jìn)制樹(shù)搜索算法（其模型如圖7-11所示）的基本思想是將處于沖突的標(biāo)簽分成左右兩個(gè)子集0和1，先查詢子集0，若沒(méi)有沖突，則正確識(shí)別標(biāo)簽，若仍有沖突則再分裂，把子集0分成00和01兩個(gè)子集，以此類推，直到識(shí)別出子集0中的所有標(biāo)簽為止，然后再按此步驟查詢子集。
      二進(jìn)制樹(shù)搜索算法是以一個(gè)獨(dú)特的序列號(hào)識(shí)別標(biāo)簽為基礎(chǔ)的。其基本原理如下：閱讀器每次查詢發(fā)送的一個(gè)比特前綴p0p1…pi，只有與這個(gè)查詢前綴相符的標(biāo)簽才響應(yīng)閱讀器的命令。當(dāng)只有一個(gè)標(biāo)簽響應(yīng)，閱讀器成功識(shí)別標(biāo)簽；當(dāng)有多個(gè)標(biāo)簽響應(yīng)的就發(fā)生沖突。在下一次循環(huán)中，閱讀器給查詢前綴增加一個(gè)比特0或1，并在閱讀器中設(shè)一個(gè)隊(duì)列Q來(lái)補(bǔ)充前綴，這個(gè)隊(duì)列Q用0和1來(lái)初始化，閱讀器從Q中查詢前綴并在每次循環(huán)中發(fā)送此前綴，當(dāng)前綴p0p1…pi是一個(gè)沖突前綴時(shí)，閱讀器就把查詢前綴設(shè)為p0p1…pi，并把前綴p0p1…pi放入隊(duì)列Q中，然后閱讀器繼續(xù)這個(gè)操作直到隊(duì)列Q為空為止。通過(guò)不斷增加和減少查詢前綴，閱讀器能識(shí)別其閱讀區(qū)域內(nèi)的所有標(biāo)簽。
2.二進(jìn)制樹(shù)搜索算法的實(shí)現(xiàn)步驟
（1）閱讀器廣播發(fā)送最大序列號(hào)（11111111），查詢前綴Q讓其作用范圍內(nèi)的標(biāo)簽響應(yīng)，同時(shí)傳輸它們的序列號(hào)至閱讀器。
（2）閱讀器對(duì)比標(biāo)簽響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)，如果出現(xiàn)不一致的現(xiàn)象（即有的序列號(hào)的該位為0，而有的序列號(hào)的該位為1），則可判斷出有碰撞。
（3）確定有碰撞后，把有不一致位的數(shù)的最高位置0再輸出查詢前綴Q，依次排除序列號(hào)大于Q的標(biāo)簽。
（4）識(shí)別出序列號(hào)最小的標(biāo)簽后，對(duì)其進(jìn)行數(shù)據(jù)操作，然后使其進(jìn)入“無(wú)聲”狀態(tài)，則對(duì)閱讀器發(fā)送的查詢命令不進(jìn)行響應(yīng)。
（5）重復(fù)步驟（1），選出序列號(hào)為倒數(shù)第二的標(biāo)簽。
（6）多次循環(huán)完后完成所有標(biāo)簽的識(shí)別。
     針對(duì)標(biāo)簽發(fā)送數(shù)據(jù)所需的時(shí)間和所消耗的功率，有人提出了改進(jìn)的二進(jìn)制樹(shù)搜索算法，其改進(jìn)思路是把數(shù)據(jù)分成兩部分，閱讀器和標(biāo)簽雙方各自傳送其中的一部分?jǐn)?shù)據(jù)，由此可把傳輸?shù)臄?shù)據(jù)量減小一半，達(dá)到縮短傳送時(shí)間的目的。根據(jù)二進(jìn)制樹(shù)搜索算法的思路再進(jìn)行改良，即當(dāng)標(biāo)簽ID與查詢前綴相符時(shí)，標(biāo)簽只發(fā)送其余的比特位，這樣也可以減少每次傳送的位數(shù)，進(jìn)而縮短傳送的時(shí)間，最終縮短防碰撞執(zhí)行時(shí)間。

3.二進(jìn)制搜索算法
二進(jìn)制搜索算法類似于天平中采用的逐次比較方法。它通過(guò)多次比較，不斷篩選出不同的序列號(hào)，時(shí)分復(fù)用地進(jìn)行閱讀器和標(biāo)簽之間的信號(hào)交換，并以一個(gè)獨(dú)特的序列號(hào)識(shí)別標(biāo)簽為基礎(chǔ)。為了從一組標(biāo)簽中選擇一個(gè)，閱讀器發(fā)出一個(gè)請(qǐng)求命令，有意識(shí)地將標(biāo)簽序列號(hào)傳輸時(shí)的數(shù)據(jù)碰撞引導(dǎo)到閱讀器上，即通過(guò)閱讀器判斷是否有碰撞發(fā)生，如果有碰撞，則縮小范圍進(jìn)行進(jìn)一步的搜索。
二進(jìn)制搜索算法由一個(gè)閱讀器和多個(gè)標(biāo)簽之間規(guī)定的一組命令和應(yīng)答規(guī)則構(gòu)成，目的在于從多卡中選出任一個(gè)來(lái)實(shí)現(xiàn)數(shù)據(jù)的通信。
該算法有3個(gè)關(guān)鍵要素：選用適當(dāng)?shù)幕鶐Ь幋a（易于識(shí)別碰撞）；利用標(biāo)簽卡序列號(hào)唯一的特性；設(shè)計(jì)一組有效的指令規(guī)則，高效、迅速地實(shí)現(xiàn)選卡。
1）曼徹斯特編碼（Mancherster）

    在二進(jìn)制搜索算法的實(shí)現(xiàn)中，起決定作用的是閱讀器所使用的信號(hào)編碼必須能夠確定碰撞的準(zhǔn)確比特位置。曼徹斯特編碼可在多卡同時(shí)響應(yīng)時(shí)，譯出錯(cuò)誤碼字，可以按位識(shí)別出碰撞，這樣可以根據(jù)碰撞的位置，按一定法則重新搜索標(biāo)簽。曼徹斯特編碼與防沖撞該編碼采用以下規(guī)則：邏輯“1”表示下降沿跳變；邏輯“0”表示上升沿跳變；若無(wú)狀態(tài)跳變，作為錯(cuò)誤被識(shí)別。
當(dāng)多個(gè)標(biāo)簽同時(shí)返回的數(shù)位有不同值時(shí)，上升和下降沿互相抵消，以至無(wú)狀態(tài)跳變，則閱讀器知道該位出現(xiàn)碰撞，產(chǎn)生了錯(cuò)誤。
利用曼徹斯特編碼來(lái)識(shí)別碰撞位：如圖7-12所示，假如有兩個(gè)標(biāo)簽，其ID為10011111和10111011，則利用曼徹斯特可識(shí)別出D5和D2位的碰撞。
2）防碰撞指令規(guī)則
典型的防碰撞指令規(guī)則有以下幾個(gè)。
（1）REQUEST—請(qǐng)求（序列號(hào)）。此命令發(fā)送一序列號(hào)作為參數(shù)給標(biāo)簽。其應(yīng)答規(guī)則是：標(biāo)簽把自己的序列號(hào)與接收到的序列號(hào)進(jìn)行比較，如果其自身的序列號(hào)小于或等于REQUEST指令的序列號(hào)，則此標(biāo)簽回送其序列號(hào)給閱讀器，這樣可以縮小預(yù)選的標(biāo)簽的范圍；如果其自身的序列號(hào)大于REQUEST指令的序列號(hào)，則不響應(yīng)。
（2）SELECT—選擇（序列號(hào)）。此命令將某個(gè)（事先確定的）序列號(hào)作為參數(shù)發(fā)送給標(biāo)簽，具有相同序列號(hào)的標(biāo)簽將以此作為執(zhí)行其他命令（如讀出和寫(xiě)入數(shù)據(jù)）的切入開(kāi)關(guān)，即選擇這個(gè)標(biāo)簽，具有其他序列號(hào)的標(biāo)簽只對(duì)REQUEST命令進(jìn)行應(yīng)答。
（3）READ-DATA—讀出數(shù)據(jù)，即選中的標(biāo)簽將存儲(chǔ)的數(shù)據(jù)發(fā)送給閱讀器。
（4）UNSELECT—去選擇。取消一個(gè)事先選中的標(biāo)簽，則標(biāo)簽將進(jìn)入“無(wú)聲”狀態(tài)，在這種狀態(tài)下標(biāo)簽完全是非激活的，對(duì)收到的REQUEST命令不作應(yīng)答。為了重新激活標(biāo)簽，必須先將標(biāo)簽移出閱讀器的作用范圍再進(jìn)入作用范圍，以實(shí)行復(fù)位。
3）二進(jìn)制搜索算法的改進(jìn)分析
（1）二進(jìn)制搜索算法的傳輸時(shí)間。由二進(jìn)制搜索算法的工作流程可知，防碰撞處理是在確認(rèn)有碰撞的情況下，根據(jù)高低位不斷降值的序列號(hào)一次次篩選出某一標(biāo)簽的過(guò)程，由此可知標(biāo)簽的數(shù)量越多，防碰撞執(zhí)行時(shí)間就將越長(zhǎng)。搜索的次數(shù)N可用下式來(lái)計(jì)算：
式中，M是終端作用范圍內(nèi)的標(biāo)簽片數(shù)；Integ表示數(shù)值取整。
UID的位數(shù)越多（如ICODE達(dá)64位），每次傳送的時(shí)間越長(zhǎng)，數(shù)據(jù)傳傳送的時(shí)間也就會(huì)增大。例如，每次都傳輸完整的UID，每次時(shí)間為T(mén)，則用于傳輸U(kuò)ID的通信時(shí)間為也就是說(shuō)，終端作用范圍內(nèi)的標(biāo)簽片數(shù)越多，UID位數(shù)越多，傳送時(shí)間越長(zhǎng)，總的防碰撞執(zhí)行時(shí)間肯定也就越長(zhǎng)。
（2）動(dòng)態(tài)二進(jìn)制搜索算法。動(dòng)態(tài)二進(jìn)制搜索算法考慮的是在UID位數(shù)不變的情況下，盡量減少傳輸?shù)臄?shù)據(jù)量，使傳送時(shí)間縮短，提高RFID系統(tǒng)的效率。其改進(jìn)思路是把數(shù)據(jù)分成兩部分，收發(fā)雙方各自傳送其中的一部分?jǐn)?shù)據(jù)，由此可把傳輸?shù)臄?shù)據(jù)量減小到一半，達(dá)到縮短傳送時(shí)間的目的。
通常序列號(hào)的規(guī)模在8KB以上，為選擇一個(gè)單獨(dú)的標(biāo)簽，每次不得不傳輸大量的數(shù)據(jù)，效率非常低。根據(jù)二進(jìn)制搜索算法的思路進(jìn)行改良，可以減少每次傳送的位數(shù)，也可縮短傳送的時(shí)間，從而縮短防碰撞執(zhí)行時(shí)間。
（3）動(dòng)態(tài)二進(jìn)制搜索算法的工作步驟。
① 閱讀器第一次發(fā)出一個(gè)完整的UID位數(shù)碼N，每個(gè)位上的碼全為l，讓所有標(biāo)簽都發(fā)回響應(yīng)。
② 閱讀器判斷有碰撞的最高位數(shù) X，把該位置 0，然后傳輸 N～X 位的數(shù)據(jù)后即中斷傳輸。標(biāo)簽接到這些數(shù)據(jù)后馬上響應(yīng)，回傳的信號(hào)位是 X-1～1，即閱讀器和標(biāo)簽以最高碰撞位為界分別傳送前后信號(hào)。傳遞的總數(shù)據(jù)量可減小一半。
③ 閱讀器檢測(cè)第二次返回的最高碰撞位數(shù)X′是否小于前一次檢測(cè)回傳的次高碰撞位數(shù)。若不是，則直接把該位置 0；若是，則要把前一次檢測(cè)的次高位也置 0，然后向標(biāo)簽發(fā)出信號(hào)。發(fā)出信號(hào)的位數(shù)為 N～X，標(biāo)簽收到信號(hào)后，如果這一級(jí)信號(hào)出現(xiàn)小于或等于相應(yīng)數(shù)據(jù)的情況則馬上響應(yīng)，回傳的信號(hào)只是序列號(hào)中最高碰撞位后的數(shù)，即 X-l～l位。若標(biāo)簽返回信號(hào)表示無(wú)碰撞，則對(duì)該序列號(hào)的標(biāo)簽進(jìn)行讀/寫(xiě)處理，然后使其進(jìn)入“不響應(yīng)狀態(tài)”。
④ 重復(fù)步驟①，多次重復(fù)后可完成標(biāo)簽的交換數(shù)據(jù)工作。
動(dòng)態(tài)二進(jìn)制搜索算法與工作步驟相對(duì)應(yīng)的示例如下。在本例中使用的標(biāo)簽有3張，其序列號(hào)分別是：卡1，11010111；卡2，11010101；卡3，11111101。
① 例如，N=8，傳送數(shù)據(jù)為11111111b。最高位為第8位，最低位為l位。根據(jù)響應(yīng)可判斷第6位、第4位、第2位有碰撞。
② X=6，即第6位有碰撞，則傳送數(shù)據(jù)變?yōu)?1011111b。傳送時(shí)，只傳送前面3位數(shù)110b，這時(shí)卡1和卡2響應(yīng)，其序列號(hào)的前3位與標(biāo)簽相同，不回傳，只回傳各自的后5位數(shù)據(jù)，即卡1為10111b，卡2為10101b。由此可判斷第2位有碰撞。
③ X′=2，根據(jù)要求第 4 位也要補(bǔ)零，則傳送數(shù)據(jù)變?yōu)?11010101b，傳送時(shí)只傳送1101010b。這時(shí)只有卡 2響應(yīng)，并返回 1b，表明無(wú)碰撞。閱讀器選中卡 2進(jìn)行數(shù)據(jù)交換，讀/寫(xiě)完畢后卡2進(jìn)入“不響應(yīng)狀態(tài)”。
④ 重復(fù)步驟①，依序可讀/寫(xiě)卡1、卡3。
在動(dòng)態(tài)二進(jìn)制搜索算法的工作過(guò)程中，要注意通過(guò)附加參數(shù)把有效位的編號(hào)發(fā)送給標(biāo)簽，從而保證每次響應(yīng)的位置是正確的。