電話:13691762133
手機(jī):13691762133
郵件:andy@ownlikes.cn
QQ:317779813
地址:深圳市龍華新區(qū)觀瀾大道35號(hào)1棟3樓
網(wǎng)址 : greezubamboo.cn
1.二進(jìn)制樹搜索算法
二進(jìn)制樹搜索算法(其模型如圖7-11所示)的基本思想是將處于沖突的標(biāo)簽分成左右兩個(gè)子集0和1,先查詢子集0,若沒(méi)有沖突,則正確識(shí)別標(biāo)簽,若仍有沖突則再分裂,把子集0分成00和01兩個(gè)子集,以此類推,直到識(shí)別出子集0中的所有標(biāo)簽為止,然后再按此步驟查詢子集。
二進(jìn)制樹搜索算法是以一個(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í)現(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)制樹搜索算法,其改進(jìn)思路是把數(shù)據(jù)分成兩部分,閱讀器和標(biāo)簽雙方各自傳送其中的一部分?jǐn)?shù)據(jù),由此可把傳輸?shù)臄?shù)據(jù)量減小一半,達(dá)到縮短傳送時(shí)間的目的。根據(jù)二進(jìn)制樹搜索算法的思路再進(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í)行其他命令(如讀出和寫入數(shù)據(jù))的切入開關(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,則用于傳輸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)行讀/寫處理,然后使其進(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ù)交換,讀/寫完畢后卡2進(jìn)入“不響應(yīng)狀態(tài)”。
④ 重復(fù)步驟①,依序可讀/寫卡1、卡3。
在動(dòng)態(tài)二進(jìn)制搜索算法的工作過(guò)程中,要注意通過(guò)附加參數(shù)把有效位的編號(hào)發(fā)送給標(biāo)簽,從而保證每次響應(yīng)的位置是正確的。