射頻識別(RFID)技術(shù)是近幾年發(fā)展起來的一種自動識別技術(shù)。RFID系統(tǒng)一般通過閱讀器識別帶有唯一電子產(chǎn)品代碼(ID)值的標(biāo)簽,。閱讀器射頻場范圍內(nèi)標(biāo)簽數(shù)量較多時不同標(biāo)簽返回?cái)?shù)據(jù)發(fā)生重疊,，導(dǎo)致閱讀器對接收信號解碼錯誤，可以將其稱為標(biāo)簽沖撞,。由于TDMA時分多址方式應(yīng)用簡單,，容易實(shí)現(xiàn)大量標(biāo)簽數(shù)據(jù)讀寫，因此被多數(shù)防沖撞算法采用?，F(xiàn)有防沖撞算法主要包括ALOHA算法和樹分叉算法兩種,。當(dāng)大量標(biāo)簽并存時，ALOHA算法[1]的幀沖撞嚴(yán)重,，易引起性能急劇惡化,，不適宜大規(guī)模標(biāo)簽讀取。所以,，主要發(fā)展樹分叉算法,。目前樹分叉算法主要有ISO/IEC 18000-6B的類二進(jìn)制搜索算法[2]、后退式二進(jìn)制樹形搜索算法[3],。本文設(shè)計(jì)了一種標(biāo)簽防沖撞算法,。
1 基于標(biāo)簽卡號無序性的防沖撞算法
對于如公路收費(fèi)亭的車輛識別，標(biāo)簽的卡號是無序的(相互間不關(guān)聯(lián)),，此時用動態(tài)調(diào)整二進(jìn)制樹形搜索法,，能快速實(shí)現(xiàn)標(biāo)簽數(shù)據(jù)讀寫。該算法用Manchester編碼準(zhǔn)確判別位碰撞,，并保持后退式二進(jìn)制樹算法的后退機(jī)理,。
1.1 Manchester編碼與防沖撞
該編碼采用以下規(guī)則：
(1)邏輯“1”表示下降沿跳變。
(2)邏輯“0”表示上升沿跳變,。
(3)若無狀態(tài)跳變,，作為錯誤被識別。
當(dāng)多個標(biāo)簽同時返回的數(shù)位有不同之值時,，上升和下降沿互相抵消,，以至無狀態(tài)跳變，閱讀器知該位出現(xiàn)碰撞,，產(chǎn)生了錯誤,。
利用Manchester編碼識別碰撞位,，如圖1所示。假如有兩個標(biāo)簽,，其ID號為10011111和10111011,，利用Manchester可識別出D5和D2位碰撞。
(a)標(biāo)簽1的ID為10011111
(b)標(biāo)簽2的ID為10111011
(c)閱讀接收的ID碰撞為10×11×11
1.2 防碰撞指令規(guī)則
(1)Request(DATA),，請求指令,。DATA長度小于或等于標(biāo)簽ID長度。ID值與DATA匹配的標(biāo)簽回送其ID值給閱讀器,。如Request(10)表示ID開始兩位為10的所有標(biāo)簽應(yīng)答,。并規(guī)定發(fā)送Request(1)后射頻場內(nèi)所有非“靜默”狀態(tài)下的標(biāo)簽都應(yīng)答。
(2)Select(ID),，選擇指令,。與Select攜帶ID值相同的標(biāo)簽被激活，該ID值與標(biāo)簽ID值長度相同,。
(3)Read-Write,，讀寫指令。讀寫被Select激活的標(biāo)簽,。
(4)Quiet(DATA),，靜默指令。對匹配標(biāo)簽進(jìn)行靜默操作,，使其不對閱讀器任何指令作出反應(yīng),。當(dāng)標(biāo)簽離開閱讀器的作用范圍(等于沒有供應(yīng)能量)后復(fù)位。
1.3 動態(tài)調(diào)整二進(jìn)制樹形搜索法
1.3.1 算法機(jī)理
該算法保持后退式二進(jìn)制樹形搜索算法[3]的后退機(jī)理：
碰撞發(fā)生時,，根據(jù)碰撞的最高位,，跳躍式向前搜索；無碰撞時,，采取后退策略,，實(shí)現(xiàn)標(biāo)簽的有序讀取。但具有以下2個特點(diǎn)：
(1)指令長度動態(tài)調(diào)整,，只發(fā)送位數(shù)高于或等于沖突位的指令位,。
(2)基于一位沖突直接識別，當(dāng)只探測到一位碰撞位時,，可直接識別出2個標(biāo)簽ID數(shù)據(jù),。如射頻場內(nèi)有兩個標(biāo)簽10101101, 10100101，閱讀器探測到的返回?cái)?shù)據(jù)為1010x101,，因?yàn)橹挥幸晃粵_突位,，所以閱讀器可直接確定射頻場存在2個標(biāo)簽10101101, 10100101。
1.3.2 算法步驟
(1)閱讀器發(fā)送Request(1)，區(qū)域內(nèi)所有標(biāo)簽應(yīng)答,。
(2)檢測是否有1位碰撞發(fā)生,。當(dāng)無碰撞或只有1位碰撞位時，直接識別標(biāo)簽,。若有多位碰撞發(fā)生,，將碰撞的最高位置0，高于該位的數(shù)值位不變,，低于該位的數(shù)值位忽略,，得到下一次Request命令所需的DATA參數(shù)。重復(fù)步驟(2)直到識別出兩個標(biāo)簽,。
(3)識別標(biāo)簽后，根據(jù)確知的ID值對標(biāo)簽逐個進(jìn)行Select激活,，然后根據(jù)需要進(jìn)行Read-Write操作,，之后用Quiet指令使該標(biāo)簽進(jìn)入靜默狀態(tài)屏蔽掉。并判斷剛才發(fā)送指令是否為Request(1),，若為Request(1)則發(fā)送結(jié)束,。否則，下一次Request命令的DATA參數(shù),，采用后退策略,，由其相鄰的上次發(fā)送指令確定，繼續(xù)步驟(2),。
1.3.3 算法實(shí)現(xiàn)
假設(shè)ID值為8位,，閱讀器作用范圍內(nèi)有8個標(biāo)簽。開始時,，閱讀器對區(qū)域內(nèi)標(biāo)簽處于未知狀態(tài),，發(fā)送Request(1)，令區(qū)域內(nèi)所有標(biāo)簽應(yīng)答,，具體的查詢過程如表1所示,。
表1 動態(tài)調(diào)整搜索法標(biāo)簽查詢過程
在表1中，“xx”表示碰撞位,；“------”表示標(biāo)簽不響應(yīng),；“^^^^”表示標(biāo)簽已被屏蔽為靜默狀態(tài)。每次查詢出ID值后即對標(biāo)簽進(jìn)行屏蔽,。當(dāng)?shù)?次執(zhí)行指令為Request(1)全返回指令,，而只有2個標(biāo)簽應(yīng)答，可知所有標(biāo)簽查詢完畢,。此時可據(jù)確知的8個標(biāo)簽ID值,，按需進(jìn)行其他操作。從表1可知用動態(tài)調(diào)整搜索法識別8個標(biāo)簽只需發(fā)送7次指令，而后退式算法[3]需要2×8-1=15次,?？梢妱討B(tài)調(diào)整搜索法的工作效率有了很大改進(jìn)。
1.4 算法性能分析
由于動態(tài)調(diào)整搜索法是基于后退式算法[3],，因此在最不理想的情況下,，也可保持N個標(biāo)簽的查詢次數(shù)為S(N)=2N-1 。當(dāng)射頻場中碰撞的標(biāo)簽數(shù)量N較大,，此時識別出1位碰撞的幾率較大,。設(shè)在整個識別過程中探測到M次只有1個碰撞位，通過動態(tài)調(diào)整算法的直接識別相當(dāng)于比后退式算法減少了2M次查詢指令,，此時查詢次數(shù)為
S(N)=2(N-M)-1
系統(tǒng)的有效服務(wù)率即吞吐率為
K=N/S(N)=N/(2N-2M-1)
將動態(tài)調(diào)整搜索法與類二進(jìn)制搜索法[2],，后退式算法[3]在ISO/IEC 18000-6B協(xié)議[2]的應(yīng)用中進(jìn)行查詢次數(shù)的比較。為保持與協(xié)議規(guī)范一致,，將使用協(xié)議相關(guān)功能指令GROUP_SELECT_EQ, READ/WRITE, DATA_READ [2] 分別取代第1.2節(jié)的指令Request, Read-Write, Quiet同時用FM0編碼[2]取代Manchester碼,。假設(shè)標(biāo)簽ID長度為16，用Matlab編程可得到仿真結(jié)果的比較如圖2所示,。
圖2 算法的防沖撞性能比較
由圖2可知,，當(dāng)標(biāo)簽數(shù)量較少時，探測到一位碰撞幾率不大,，動態(tài)調(diào)整算法比后退式算法只有稍微優(yōu)勢,，而當(dāng)標(biāo)簽數(shù)量明顯增多時，標(biāo)簽ID值比較接近,，探測到一位碰撞的幾率較大,，M較大，動態(tài)調(diào)整算法效率明顯優(yōu)于后退式算法,。而ISO/IEC 18000-6B協(xié)議的類二進(jìn)制搜索算法是隨機(jī)產(chǎn)生0,1信號進(jìn)行搜索,，不能實(shí)現(xiàn)有效的有序性讀取，仿真結(jié)果也表明其識別能力顯著低于動態(tài)調(diào)整搜索法,?？梢姡瑒討B(tài)調(diào)整搜索法可被有效用于ISO/IEC 18000-6B協(xié)議的標(biāo)簽沖突問題解決,。
尤其當(dāng)2 L 個標(biāo)簽第1次發(fā)送Request(1)識別指令只探測出L個碰撞位時,，可知識別過程中將出現(xiàn)連續(xù)的1位碰撞，此時M=2 L /2=2 L-1 ,S(N)=2(2 L -2 L-1)-1=2 L -1,K=2 L/S(N)=1,。對比后退式算法需要發(fā)送S(2 L )=2 L+1-1次查詢指令,，而系統(tǒng)吞吐率為K=0.5。動態(tài)調(diào)整算法在最優(yōu)情況下,，效率是后退式算法的倍數(shù),。同時，動態(tài)調(diào)整算法對指令長度進(jìn)行了動態(tài)調(diào)整，可以有效地減小發(fā)送信息量提高發(fā)送速率,。
2 基于標(biāo)簽卡號連續(xù)性的防沖撞算法
對于如倉庫的貨物管理,，每一批貨物內(nèi)標(biāo)簽卡號基本上是連續(xù)的，此時可用另一種防沖撞算法基于一位碰撞直接識別的輪詢算法快速識別標(biāo)簽[4],。
2.1 輪詢算法
該算法保持發(fā)送指令和Manchester編碼不變,。(1)發(fā)送Request(1)，利用Manchester編碼確定碰撞位的具體位置得到L個碰撞位,；(2)將除最低碰撞位的L-1個碰撞位看作一個二進(jìn)制數(shù)H,，從0~2 L−1遞增，得DATA,；(3)每次發(fā)完Request(DATA)后,，H自增"1"，得出新的DATA,，即實(shí)現(xiàn)一個輪詢過程,。具體過程如表2所示。
表2 輪詢算法查詢過程
對于表2的8個標(biāo)簽,，用輪詢算法只需發(fā)送5次查詢指令，用動態(tài)調(diào)整搜索法要發(fā)送7次指令,，而用后退式算法需發(fā)送15次,。可見,，對于卡號連續(xù)的情況,，輪詢算法能更有效地實(shí)現(xiàn)標(biāo)簽防沖撞。
2.2 算法性能分析
對于卡號連續(xù)的N個標(biāo)簽,，探測到L個碰撞位時,，發(fā)送的查詢指令次數(shù)為
S(N)=2 L-1+1
系統(tǒng)的有效服務(wù)率即吞吐率為
K=N/S(N)=N/(2 L-1+1)
可知查詢次數(shù)S(N)只與碰撞位數(shù)L有關(guān)，而與標(biāo)簽總數(shù)無關(guān),，吞吐率K不僅與碰撞位數(shù)有關(guān)還與標(biāo)簽總數(shù)有關(guān),。特別地，令待識別的標(biāo)簽卡號從0開始,，與1.3節(jié)介紹的動態(tài)調(diào)整算法的比較如表3所示,。
表3 算法比較
從表3可看出在最優(yōu)情況下，輪詢算法可使吞吐率K達(dá)到2,，而動態(tài)調(diào)整搜索法的最優(yōu)吞吐率K為1,，后退式算法[3]的吞吐率K為0.5?？梢?，輪詢算法具有很大的應(yīng)用潛力。
根據(jù)式(4)可畫出吞吐率K與標(biāo)簽數(shù)量N和碰撞位數(shù)L的關(guān)系曲線，如圖3所示,。
從圖3可看出,，標(biāo)簽數(shù)量較少，而碰撞位數(shù)卻很大時,，吞吐率較低,，此時不適合用輪詢算法。這種缺陷可稱為Hamming懸崖(Hamming cliffs),，相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離,。例如2個標(biāo)簽卡號分別為01111和10000，碰撞位數(shù)為5,，要輪詢25-1+1=17次才讀完這兩標(biāo)簽,，可見效率很低。從圖3可看出只有標(biāo)簽數(shù)量較大時,，吞吐率K受碰撞位數(shù)影響不大,，能克服Hamming懸崖，此時K基本介于1～2之間,，效果比動態(tài)調(diào)整搜索法最優(yōu)吞吐率K=1要好,。
對于卡號連續(xù)的標(biāo)簽，并不要求嚴(yán)格連續(xù),，只要大部分標(biāo)簽卡號滿足一定的連續(xù)性就可有效使用輪詢算法,。另外，輪詢算法只需使用一次Manchester編碼識別碰撞位,，則只需按照規(guī)則發(fā)送指令,，能夠大大降低系統(tǒng)設(shè)計(jì)的復(fù)雜性。
3 結(jié)束語
本文針對RFID技術(shù)日益嚴(yán)重的標(biāo)簽沖撞問題,，指出對一般沖突情況,，可用動態(tài)調(diào)整搜索法進(jìn)行防沖撞，并通過對比表明該算法能有效應(yīng)用于ISO/IEC 18000-6B相關(guān)協(xié)議的RFID系統(tǒng)中,，而當(dāng)具備一定先驗(yàn)知識,，了解到待識別標(biāo)簽卡號滿足一定連續(xù)性，且數(shù)量較大時,，可用輪詢算法進(jìn)行有效的防沖撞處理,。