二進(jìn)制樹搜索算法yuanyc@njcit.cn基本思想是：當(dāng)發(fā)生碰撞時，二叉樹算法根據(jù)標(biāo)簽ID

或者隨機(jī)產(chǎn)生的二進(jìn)制“0”和“1”把標(biāo)簽集劃分成兩個子集。先查詢子集0,若沒有碰撞，則正確識別標(biāo)簽，

若仍有碰撞則分裂，把1子集分成00和01

兩個子集，直到每個集合中只含有一個標(biāo)

簽，讀寫器就能識別作用范圍內(nèi)所有標(biāo)簽。110

11沖突節(jié)點100101非沖突節(jié)點二進(jìn)制樹型搜索算法O基于Aloha的算法比較簡單，但是因為標(biāo)簽之間通過競爭來

獲取信道資源，該方法有很大的隨機(jī)性，不能完全防止標(biāo)簽碰撞，存在個別標(biāo)簽長時間不能被識別的嚴(yán)重缺陷，即“標(biāo)簽

饑餓”問題。※基于樹的算法是一種確定性的防碰撞算法。讀寫器以查詢時隙為基本處理單元，在一次查詢中，讀寫器發(fā)送查詢命令，

符合的標(biāo)簽返回響應(yīng)。若響應(yīng)的標(biāo)簽集包含多個標(biāo)簽則出現(xiàn)

碰撞，此時將標(biāo)簽劃分為兩個子集0和1,查詢子集0,若沒

有沖突則正確識別，若有沖突繼續(xù)分裂成00和01兩個子集，

依次類推，直至將子集0中標(biāo)簽識別完畢，再按此步驟查詢子

集

1

?；诙M(jìn)制樹的標(biāo)簽防碰撞算法子集1子集11子集101子集100圖7.2-6

二進(jìn)制樹示意圖子集01

子集10子集00子集0樹型搜索算法原理必基于樹的算法是以查詢時隙為基本處理單元去識別標(biāo)簽的。必在一次查詢中，讀寫器發(fā)送查詢命令給標(biāo)簽，符合應(yīng)答條件的標(biāo)簽發(fā)送自身的ID

給讀寫器，讀寫器根據(jù)接收到的標(biāo)簽的信息來確定下一輪查詢命令。必如果在一輪查詢中，只有一個標(biāo)簽響應(yīng)讀寫器，這個標(biāo)簽就能被正確識別。讀寫器發(fā)送查詢命令，一個標(biāo)簽集響應(yīng)讀寫器，如果響應(yīng)的標(biāo)簽集中包含多個標(biāo)簽就會出現(xiàn)標(biāo)簽碰撞?！撍惴ㄓ?個關(guān)鍵要素：※

a選用適當(dāng)?shù)幕鶐Ь幋a方式(易于識別碰撞);※

b

標(biāo)簽序列號必須唯一；c設(shè)計一組有效的指令規(guī)則，高效、迅速地實現(xiàn)選卡。曼徹斯特編碼檢測碰撞位※在二進(jìn)制搜索算法的實現(xiàn)中，利用標(biāo)簽ID序列號的唯一性劃分標(biāo)簽子集，要求讀寫器所使用的信號編碼必須能夠確

定碰撞的準(zhǔn)確比特位置。※曼徹斯特編碼中，位中間存在跳變，向低電平跳變表示二進(jìn)制1,向高電平跳變表示

二進(jìn)制0,中間不發(fā)生跳變?yōu)殄e誤編碼。由此，曼徹斯特編碼能夠檢測出數(shù)據(jù)中是否

有碰撞發(fā)生，可以按位識別出碰撞?；诙鏄涞乃惴ㄆ毡槭褂寐鼜厮固鼐幋a。射頻卡1讀寫器譯碼??

??

??00射頻卡2工00范例R:11111111送REQUEST

(11111111)

命令，要求區(qū)

域內(nèi)所有標(biāo)簽應(yīng)答，根據(jù)曼徹斯特編碼，

解碼數(shù)據(jù)為101??1?1,發(fā)生碰撞，算法做

下如下，將碰撞的最高置0,其它碰撞位

置1。得下次的REQUEST(10101111)A:

10

1

0011B:101

10101C:10101111

D:10111

101R:11111111??

?R表示閱

讀器A:10100111C:1010111送REQUEST(10101111)

命令，標(biāo)簽A和C應(yīng)答。解碼數(shù)據(jù)為1010?111,發(fā)生碰撞，算法做下如下，將碰撞的最高置0,其它碰撞位置1。得10100111?R:10101111R:10101111R表示閱

讀器R:10100111送REQUEST(10100111)

命令，只

有標(biāo)簽A應(yīng)答。解碼數(shù)據(jù)為1010?111,

沒有發(fā)生碰撞，閱讀器對標(biāo)簽A進(jìn)行閱

讀操作。A:10100111C:10101111R:10100111可以識別AR表示閱

讀器第一次搜尋第二

尋次搜第三次搜

尋第四次搜尋第五次搜

尋發(fā)送序號111111110101111010011111111110101111接收序號10??1?11010?111識別TagA10??1?1TagA101001111010011110100111識別TagCTagB100101101010ITagC10101111101011111010111110101111TagD10111011011101二進(jìn)制搜索樹算法的實現(xiàn)步驟ImprovedAnti-collisionAlgorithm搜尋過程第六次搜尋第七次搜

尋第八次搜

尋第九次搜

尋第十次搜

尋發(fā)送序號11111111011010110111101接收序號101?101識別TagATagB101010110110101TagCTagDTagD101110110111101二進(jìn)制搜索樹算法的實現(xiàn)步驟ImprovedAnti-collisionAlgorithm搜尋過程識別TagB二進(jìn)制搜索樹算法的實現(xiàn)步驟二進(jìn)制搜索算法的工作流程是：射頻卡進(jìn)入讀寫器的工作范圍，讀寫器發(fā)出一個最大序列號讓所有

射頻卡響應(yīng)；同一時刻開始傳輸它們的序列號到讀寫器的接收模塊。讀寫器對比射頻卡響應(yīng)的序列號的相同位數(shù)上的數(shù)。把有不一致位的數(shù)從最高位到低位依次置0再輸出系列號，

即依次排除序列號大的數(shù)，至讀寫器對比射頻卡響應(yīng)的序列號

的相同位數(shù)上的數(shù)完全一致時，說明無碰撞。選出序列號最小的數(shù)后，對該標(biāo)簽進(jìn)行數(shù)據(jù)交換，然后使

該卡進(jìn)入“無聲”狀態(tài)。即有的序列號該位

為0,而有的序列

號該位為1出現(xiàn)不一致的現(xiàn)象N(4)a、

若有一個以的標(biāo)簽發(fā)送，則重復(fù)步驟(2);b、若只有一個發(fā)送，則讀寫器發(fā)送包含識別碼的“DATA_READ”,指令，標(biāo)簽正確接收此指令進(jìn)入“數(shù)據(jù)交互”,通信完成后，發(fā)送SUCCESS指令；C、當(dāng)標(biāo)簽沒有被正確接收，則讀寫器將發(fā)送一個RESEND指令。(3)所有接收到FAIL指令且內(nèi)部計數(shù)器不等于0的標(biāo)簽計數(shù)器加1。所有接收

到FAIL指令且內(nèi)部計數(shù)器等于0的標(biāo)簽將產(chǎn)生一個1或者0的隨機(jī)數(shù)，如果是1,則標(biāo)簽計數(shù)器加1,如果是0,則標(biāo)簽計數(shù)器保持不變，并再次發(fā)送其識別碼。(2)當(dāng)有一個以上的標(biāo)簽發(fā)送時，讀寫器因不能正確識別信號為發(fā)送FAIL指令。

(1)所有處于“識別”狀態(tài)且內(nèi)部計數(shù)器為0的應(yīng)答器發(fā)送它們的識別碼。

當(dāng)進(jìn)入“識別”有多個標(biāo)簽----碰撞仲裁當(dāng)進(jìn)入“識別”有多個標(biāo)簽----防碰撞指令規(guī)則(1)REQUEST——請求(序列號)。此命令發(fā)送一序列號作為

參數(shù)給射頻卡。應(yīng)答規(guī)則是，射頻卡把自己的序列號與接收

到的序列號比較，如果自身序列號小于或等于REQUEST指令序

列號參數(shù)，則此射頻卡回送其序列號給讀寫器。這樣可以縮

小預(yù)選的射頻卡的范圍；如果大于，則不響應(yīng)。(2)SELECT——

選擇(序列號)。用某個(事先確定的)序列號

作為參數(shù)發(fā)送給射頻卡。具有相同序列號的射頻卡將以此作

為執(zhí)行其他命令(例如讀出和寫入數(shù)據(jù))的切入開關(guān)，即選擇

這個射頻卡。具有其他序列號的射頻卡只對REQUEST命令應(yīng)答。(4)UNSELECT——去選擇。取消一個事先選中的射頻卡，射頻卡進(jìn)入

"無聲"狀態(tài)，在這種狀態(tài)下射頻卡完全是非激活的，對收到的REQUEST命

令不作應(yīng)答。為了重新話化射頻卡，必須先將射頻卡移出讀寫器的作用

范圍再進(jìn)入，以實行復(fù)位。(3)READ-DATA——讀出數(shù)據(jù)。選中的射頻卡將存儲的數(shù)據(jù)

發(fā)送給讀寫器。3

當(dāng)進(jìn)入“識別”有多個標(biāo)簽----防碰撞指令規(guī)則讀寫器防碰撞技術(shù)※密集讀寫器環(huán)境是指RFID

系統(tǒng)應(yīng)用中，在預(yù)定區(qū)域內(nèi)部署多個RFID讀寫器，以滿足對區(qū)域內(nèi)

的所有標(biāo)簽進(jìn)行完全的、高可靠的讀取要求。系統(tǒng)網(wǎng)絡(luò)中包含多個讀寫器和一個中央計算機(jī)，

讀寫器與中央計算機(jī)之間一般采用局域網(wǎng)(LAN)或無線局域網(wǎng)(WLAN)方式進(jìn)行通信連接。※目前對RFID系統(tǒng)防沖突算法的研究主要是標(biāo)簽之間的防沖突算法，對讀寫器防沖突算法研究

不是很多，目前主要算法有圖著色(Colorwave)算法、Q.Learning算法、Pulse算法等。讀寫器沖突圖7-25讀寫器沖突的分類及算法解決方法讀寫器與讀寫器間干擾讀寫器與標(biāo)簽間干擾圖著色

算法模擬

褪火遺傳

算法神經(jīng)

網(wǎng)絡(luò)HIQ

算法讀寫器防碰撞技術(shù)※(1)圖著色(Colorwave)算法※Colorwave

算法通過給讀寫器分配不同的顏色來避免讀寫器

之間的沖突，是基于TDMA的一種分布式算法。該算法規(guī)定

每個讀寫器從0到最大顏色數(shù)(maxColors)中隨機(jī)選擇一個顏

色(時隙)傳輸數(shù)據(jù)。如果發(fā)生了沖突，讀寫器選擇一個新的

顏色，并且發(fā)送一個較小的控制包給它所有鄰近的讀寫器，

告之它選擇了一個新的顏色。如果鄰近的讀寫器有同樣的顏

色，它重新選擇一個新的顏色并發(fā)送控制包。這樣一直繼續(xù)

下去。這種轉(zhuǎn)換和駐留的動作就被稱為kick

。每個讀寫器跟

蹤當(dāng)前的時隙顏色。必該算法需要所有讀寫器之間的時間同步，同時還要求所有的

讀寫器都可以檢測RFID

系統(tǒng)中的沖突。然而，若標(biāo)簽不具有

沖突檢測功能，需多個讀寫器聯(lián)合檢測在標(biāo)簽處發(fā)生的沖突。

另讀寫器移動將會重新分配時隙，重新分配的時隙傳播整個

網(wǎng)絡(luò)，將會導(dǎo)致整個系統(tǒng)的無效。*

(2)HIQ

算法必該算法是一個分等級的在線學(xué)習(xí)算法，通過

學(xué)習(xí)讀寫器沖突模型，動態(tài)的解決RFID

系統(tǒng)中讀寫器沖突問題，有效地分配頻率給讀寫

器。其思想類似于無線傳感器網(wǎng)絡(luò)中分簇算法?！鵔

學(xué)習(xí)算法中，讀寫器發(fā)送沖突消息給讀寫器

級服務(wù)器層(R

.Server)。然后單個的R-server分配資源給它的讀寫器，這樣的方式可

使它們之間的相互通信不出現(xiàn)干擾。R.Server

通過Q學(xué)習(xí)服務(wù)器(Q.server)被分

配到頻率和時隙。根Q.server

具有所有頻率

和時隙資源的全部知識，并且能分配它們。Q.server

不像R.Server—樣，沒有單個讀

寫器問約束關(guān)系，這種關(guān)系通過該層下面的服務(wù)器之問的相互作用來推斷

。沖突信息根

Q-ServerQ-Server

QServerR-ServerR-Server頻率與時隙分配讀寫器圖7-26Q學(xué)習(xí)算法多層結(jié)構(gòu)讀寫器防碰撞技術(shù)讀寫器防碰撞技術(shù)※(3)Pulse

算法※該算法將通信信道分為控制

信道和數(shù)據(jù)信道兩個部分。