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

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

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