二進制樹搜索算法二進制樹型搜索算法基本思想是：當發(fā)生碰撞時，二叉樹算法根據(jù)標簽ID或者隨機產(chǎn)生的二進制“0”和“1”把標簽集劃分成兩個子集。先查詢子集0，若沒有碰撞，則正確識別標簽，若仍有碰撞則分裂，把1子集分成00和01兩個子集，直到每個集合中只含有一個標簽，讀寫器就能識別作用范圍內(nèi)所有標簽?；诙M制樹的標簽防碰撞算法基于Aloha的算法比較簡單，但是因為標簽之間通過競爭來獲取信道資源，該方法有很大的隨機性，不能完全防止標簽碰撞，存在個別標簽長時間不能被識別的嚴重缺陷，即“標簽饑餓”問題?；跇涞乃惴ㄊ且环N確定性的防碰撞算法。讀寫器以查詢時隙為基本處理單元，在一次查詢中，讀寫器發(fā)送查詢命令，符合的標簽返回響應(yīng)。若響應(yīng)的標簽集包含多個標簽則出現(xiàn)碰撞，此時將標簽劃分為兩個子集0和1，查詢子集0，若沒有沖突則正確識別，若有沖突繼續(xù)分裂成00和01兩個子集，依次類推，直至將子集0中標簽識別完畢，再按此步驟查詢子集1。樹型搜索算法原理基于樹的算法是以查詢時隙為基本處理單元去識別標簽的。在一次查詢中，讀寫器發(fā)送查詢命令給標簽，符合應(yīng)答條件的標簽發(fā)送自身的ID給讀寫器，讀寫器根據(jù)接收到的標簽的信息來確定下一輪查詢命令。如果在一輪查詢中，只有一個標簽響應(yīng)讀寫器，這個標簽就能被正確識別。讀寫器發(fā)送查詢命令，一個標簽集響應(yīng)讀寫器，如果響應(yīng)的標簽集中包含多個標簽就會出現(xiàn)標簽碰撞。該算法有3個關(guān)鍵要素：

a選用適當?shù)幕鶐Ь幋a方式(易于識別碰撞)；

b標簽序列號必須唯一；

c設(shè)計一組有效的指令規(guī)則，高效、迅速地實現(xiàn)選卡。101100001110??????射頻卡1射頻卡2讀寫器譯碼曼徹斯特編碼檢測碰撞位

在二進制搜索算法的實現(xiàn)中，利用標簽ID序列號的唯一性劃分標簽子集，要求讀寫器所使用的信號編碼必須能夠確定碰撞的準確比特位置。曼徹斯特編碼中，位中間存在跳變，向低電平跳變表示二進制1，向高電平跳變表示二進制0，中間不發(fā)生跳變?yōu)殄e誤編碼。由此，曼徹斯特編碼能夠檢測出數(shù)據(jù)中是否有碰撞發(fā)生，可以按位識別出碰撞?；诙鏄涞乃惴ㄆ毡槭褂寐鼜厮固鼐幋a。范例A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111送REQUEST（11111111）命令，要求區(qū)域內(nèi)所有標簽應(yīng)答，根據(jù)曼徹斯特編碼，解碼數(shù)據(jù)為101??1?1,發(fā)生碰撞，算法做下如下，將碰撞的最高置0，其它碰撞位置1。得下次的REQUEST(10101111)???R表示閱讀器二進制搜索樹算法的實現(xiàn)步驟A:10100111C:10101111R:10101111R:10101111

送REQUEST（10101111）命令，標簽A和C應(yīng)答。解碼數(shù)據(jù)為1010?111,發(fā)生碰撞，算法做下如下，將碰撞的最高置0，其它碰撞位置1。得10100111?R表示閱讀器二進制搜索樹算法的實現(xiàn)步驟A:10100111C:10101111R:10100111R:10100111

送REQUEST（10100111）命令，只有標簽A應(yīng)答。解碼數(shù)據(jù)為1010?111,沒有發(fā)生碰撞，閱讀器對標簽A進行閱讀操作。R表示閱讀器可以識別A二進制搜索樹算法的實現(xiàn)步驟ImprovedAnti-collisionAlgorithm搜尋過程二進制搜索樹算法的實現(xiàn)步驟第一次搜尋第二次搜尋第三次搜尋第四次搜尋第五次搜尋發(fā)送序號接收序號TagATagBTagCTagD1010011110110101101011111011110111111111101??1?11010111110100111101011111010?1111010011110100111識別TagA10110101101011111011110111111111101??1?11010111110101111識別TagCImprovedAnti-collisionAlgorithm搜尋過程二進制搜索樹算法的實現(xiàn)步驟第六次搜尋第七次搜尋第八次搜尋第九次搜尋第十次搜尋發(fā)送序號接收序號TagATagBTagC

TagD1011010110111101111111111011?10110110101101101011011110110111101識別TagB識別TagD

射頻卡進入讀寫器的工作范圍，讀寫器發(fā)出一個最大序列號讓所有射頻卡響應(yīng)；同一時刻開始傳輸它們的序列號到讀寫器的接收模塊。

讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)。出現(xiàn)不一致的現(xiàn)象即有的序列號該位為0，而有的序列號該位為1

把有不一致位的數(shù)從最高位到低位依次置O再輸出系列號，即依次排除序列號大的數(shù)，至讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)完全一致時，說明無碰撞。選出序列號最小的數(shù)后，對該標簽進行數(shù)據(jù)交換，然后使該卡進入“無聲”狀態(tài)。YN二進制搜索算法的工作流程是：二進制搜索樹算法的實現(xiàn)步驟（1）所有處于“識別”狀態(tài)且內(nèi)部計數(shù)器為0的應(yīng)答器發(fā)送它們的識別碼。（2）當有一個以上的標簽發(fā)送時，讀寫器因不能正確識別信號為發(fā)送FAIL指令。（3）所有接收到FAIL指令且內(nèi)部計數(shù)器不等于0的標簽計數(shù)器加1。所有接收到FAIL指令且內(nèi)部計數(shù)器等于0的標簽將產(chǎn)生一個1或者0的隨機數(shù)，如果是1，則標簽計數(shù)器加1，如果是0，則標簽計數(shù)器保持不變，并再次發(fā)送其識別碼。1當進入“識別”有多個標簽----碰撞仲裁

防碰撞機制的實現(xiàn)

所有接收到FAIL指令且內(nèi)部計數(shù)器不等于0的標簽計數(shù)器加1。所有接收到FAIL指令且內(nèi)部計數(shù)器等0的標簽將產(chǎn)生一個1或者0的隨機數(shù)，如果是1，則標簽計數(shù)器加1，如果是0，則標簽計數(shù)器保持不變，并再次發(fā)送其識別碼。（4）a、若有一個以的標簽發(fā)送，則重復(fù)步驟（2）;b、若只有一個發(fā)送，則讀寫器發(fā)送包含識別碼的“DATA_READ”，指令，標簽正確接收此指令進入“數(shù)據(jù)交互”，通信完成后，發(fā)送SUCCESS指令；C、當標簽沒有被正確接收，則讀寫器將發(fā)送一個RESEND指令。（1）REQUEST——請求(序列號)。此命令發(fā)送一序列號作為參數(shù)給射頻卡。應(yīng)答規(guī)則是，射頻卡把自己的序列號與接收到的序列號比較，如果自身序列號小于或等于REQUEST指令序列號參數(shù)，則此射頻卡回送其序列號給讀寫器。這樣可以縮小預(yù)選的射頻卡的范圍；如果大于，則不響應(yīng)。2當進入“識別”有多個標簽----防碰撞指令規(guī)則

所有接收到FAIL指令且內(nèi)部計數(shù)器不等于0的標簽計數(shù)器加1。所有接收到FAIL指令且內(nèi)部計數(shù)器等0的標簽將產(chǎn)生一個1或者0的隨機數(shù)，如果是1，則標簽計數(shù)器加1，如果是0，則標簽計數(shù)器保持不變，并再次發(fā)送其識別碼。

(2)SELECT——選擇(序列號)。用某個(事先確定的)序列號作為參數(shù)發(fā)送給射頻卡。具有相同序列號的射頻卡將以此作為執(zhí)行其他命令(例如讀出和寫入數(shù)據(jù))的切入開關(guān)，即選擇這個射頻卡。具有其他序列號的射頻卡只對REQUEST命令應(yīng)答。

防碰撞機制的實現(xiàn)（3）READ-DATA——讀出數(shù)據(jù)。選中的射頻卡將存儲的數(shù)據(jù)發(fā)送給讀寫器。

3當進入“識別”有多個標簽----防碰撞指令規(guī)則

(4)UNSELECT

——去選擇。取消一個事先選中的射頻卡，射頻卡進入"無聲"狀態(tài)，在這種狀態(tài)下射頻卡完全是非激活的，對收到的REQUEST命令不作應(yīng)答。為了重新話化射頻卡，必須先將射頻卡移出讀寫器的作用范圍再進入，以實行復(fù)位。

防碰撞機制的實現(xiàn)讀寫器防碰撞技術(shù)密集讀寫器環(huán)境是指RFID系統(tǒng)應(yīng)用中，在預(yù)定區(qū)域內(nèi)部署多個RFID讀寫器，以滿足對區(qū)域內(nèi)的所有標簽進行完全的、高可靠的讀取要求。系統(tǒng)網(wǎng)絡(luò)中包含多個讀寫器和一個中央計算機，讀寫器與中央計算機之間一般采用局域網(wǎng)（LAN）或無線局域網(wǎng)（WLAN）方式進行通信連接。目前對RFID系統(tǒng)防沖突算法的研究主要是標簽之間的防沖突算法，對讀寫器防沖突算法研究不是很多，目前主要算法有圖著色（Colorwave）算法、Q．Learning算法、Pulse算法等。讀寫器防碰撞技術(shù)(1)圖著色(Colorwave)算法Colorwave算法通過給讀寫器分配不同的顏色來避免讀寫器之間的沖突，是基于TDMA的一種分布式算法。該算法規(guī)定每個讀寫器從0到最大顏色數(shù)(maxColors)中隨機選擇一個顏色(時隙)傳輸數(shù)據(jù)。如果發(fā)生了沖突，讀寫器選擇一個新的顏色，并且發(fā)送一個較小的控制包給它所有鄰近的讀寫器，告之它選擇了一個新的顏色。如果鄰近的讀寫器有同樣的顏色，它重新選擇一個新的顏色并發(fā)送控制包。這樣一直繼續(xù)下去。這種轉(zhuǎn)換和駐留的動作就被稱為kick。每個讀寫器跟蹤當前的時隙顏色。該算法需要所有讀寫器之間的時間同步，同時還要求所有的讀寫器都可以檢測RFID系統(tǒng)中的沖突。然而，若標簽不具有沖突檢測功能，需多個讀寫器聯(lián)合檢測在標簽處發(fā)生的沖突。另讀寫器移動將會重新分配時隙，重新分配的時隙傳播整個網(wǎng)絡(luò)，將會導(dǎo)致整個系統(tǒng)的無效。讀寫器防碰撞技術(shù)(2)HIQ算法該算法是一個分等級的在線學習算法，通過學習讀寫器沖突模型，動態(tài)的解決RFID系統(tǒng)中讀寫器沖突問題，有效地分配頻率給讀寫器。其思想類似于無線傳感器網(wǎng)絡(luò)中分簇算法。Q學習算法中，讀寫器發(fā)送沖突消息給讀寫器級服務(wù)器層(R．Server)。然后單個的R-server分配資源給它的讀寫器，這樣的方式可使它們之間的相互通信不出現(xiàn)干擾。R．Server通過Q學習服務(wù)器(Q．server)被分配到頻率和時隙。根Q．server具有所有頻率和時隙資源的全部知識，并且能分配它們。Q