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

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

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