標(biāo)簽防沖撞算法設(shè)計(jì)

　　1.2 防碰撞指令規(guī)則

　　(1)Request(DATA)，請(qǐng)求指令。DATA長(zhǎng)度小于或等于標(biāo)簽ID長(zhǎng)度。ID值與DATA匹配的標(biāo)簽回送其ID值給閱讀器。如Request(10)表示ID開(kāi)始兩位為10的所有標(biāo)簽應(yīng)答。并規(guī)定發(fā)送Request(1)后射頻場(chǎng)內(nèi)所有非“靜默”狀態(tài)下的標(biāo)簽都應(yīng)答。

　　(2)Select(ID)，選擇指令。與Select攜帶ID值相同的標(biāo)簽被激活，該ID值與標(biāo)簽ID值長(zhǎng)度相同。

　　(3)Read-Write，讀寫(xiě)指令。讀寫(xiě)被Select激活的標(biāo)簽。

　　(4)Quiet(DATA)，靜默指令。對(duì)匹配標(biāo)簽進(jìn)行靜默操作，使其不對(duì)閱讀器任何指令作出反應(yīng)。當(dāng)標(biāo)簽離開(kāi)閱讀器的作用范圍(等于沒(méi)有供應(yīng)能量)后復(fù)位。

　　1.3 動(dòng)態(tài)調(diào)整二進(jìn)制樹(shù)形搜索法

　　1.3.1 算法機(jī)理

　　該算法保持后退式二進(jìn)制樹(shù)形搜索算法[3]的后退機(jī)理：

　　碰撞發(fā)生時(shí)，根據(jù)碰撞的最高位，跳躍式向前搜索；無(wú)碰撞時(shí)，采取后退策略，實(shí)現(xiàn)標(biāo)簽的有序讀取。但具有以下2個(gè)特點(diǎn)：
　　(1)指令長(zhǎng)度動(dòng)態(tài)調(diào)整，只發(fā)送位數(shù)高于或等于沖突位的指令位。

　　(2)基于一位沖突直接識(shí)別，當(dāng)只探測(cè)到一位碰撞位時(shí)，可直接識(shí)別出2個(gè)標(biāo)簽ID數(shù)據(jù)。如射頻場(chǎng)內(nèi)有兩個(gè)標(biāo)簽10101101, 10100101，閱讀器探測(cè)到的返回?cái)?shù)據(jù)為1010x101，因?yàn)橹挥幸晃粵_突位，所以閱讀器可直接確定射頻場(chǎng)存在2個(gè)標(biāo)簽10101101, 10100101。

　　1.3.2 算法步驟

　　(1)閱讀器發(fā)送Request(1)，區(qū)域內(nèi)所有標(biāo)簽應(yīng)答。

　　(2)檢測(cè)是否有1位碰撞發(fā)生。當(dāng)無(wú)碰撞或只有1位碰撞位時(shí)，直接識(shí)別標(biāo)簽。若有多位碰撞發(fā)生，將碰撞的最高位置0，高于該位的數(shù)值位不變，低于該位的數(shù)值位忽略，得到下一次Request命令所需的DATA參數(shù)。重復(fù)步驟(2)直到識(shí)別出兩個(gè)標(biāo)簽。

　　(3)識(shí)別標(biāo)簽后，根據(jù)確知的ID值對(duì)標(biāo)簽逐個(gè)進(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個(gè)標(biāo)簽。開(kāi)始時(shí)，閱讀器對(duì)區(qū)域內(nèi)標(biāo)簽處于未知狀態(tài)，發(fā)送Request(1)，令區(qū)域內(nèi)所有標(biāo)簽應(yīng)答，具體的查詢(xún)過(guò)程如表1所示。

　　表1 動(dòng)態(tài)調(diào)整搜索法標(biāo)簽查詢(xún)過(guò)程

　　在表1中，“xx”表示碰撞位；“------”表示標(biāo)簽不響應(yīng)；“^^^^”表示標(biāo)簽已被屏蔽為靜默狀態(tài)。每次查詢(xún)出ID值后即對(duì)標(biāo)簽進(jìn)行屏蔽。當(dāng)?shù)?次執(zhí)行指令為Request(1)全返回指令，而只有2個(gè)標(biāo)簽應(yīng)答，可知所有標(biāo)簽查詢(xún)完畢。此時(shí)可據(jù)確知的8個(gè)標(biāo)簽ID值，按需進(jìn)行其他操作。從表1可知用動(dòng)態(tài)調(diào)整搜索法識(shí)別8個(gè)標(biāo)簽只需發(fā)送7次指令，而后退式算法[3]需要2×8-1=15次?？梢?jiàn)動(dòng)態(tài)調(diào)整搜索法的工作效率有了很大改進(jìn)。

　　1.4 算法性能分析

　　由于動(dòng)態(tài)調(diào)整搜索法是基于后退式算法[3]，因此在最不理想的情況下，也可保持N個(gè)標(biāo)簽的查詢(xún)次數(shù)為S(N)=2N-1 。當(dāng)射頻場(chǎng)中碰撞的標(biāo)簽數(shù)量N較大，此時(shí)識(shí)別出1位碰撞的幾率較大。設(shè)在整個(gè)識(shí)別過(guò)程中探測(cè)到M次只有1個(gè)碰撞位，通過(guò)動(dòng)態(tài)調(diào)整算法的直接識(shí)別相當(dāng)于比后退式算法減少了2M次查詢(xún)指令，此時(shí)查詢(xún)次數(shù)為
      S(N)=2(N-M)-1

　　系統(tǒng)的有效服務(wù)率即吞吐率為
      K=N/S(N)=N/(2N-2M-1)

　　將動(dòng)態(tài)調(diào)整搜索法與類(lèi)二進(jìn)制搜索法[2]，后退式算法[3]在ISO/IEC 18000-6B協(xié)議[2]的應(yīng)用中進(jìn)行查詢(xún)次數(shù)的比較。為保持與協(xié)議規(guī)范一致，將使用協(xié)議相關(guān)功能指令GROUP_SELECT_EQ, READ/WRITE, DATA_READ [2] 分別取代第1.2節(jié)的指令Request, Read-Write, Quiet同時(shí)用FM0編碼[2]取代Manchester碼。假設(shè)標(biāo)簽ID長(zhǎng)度為16，用Matlab編程可得到仿真結(jié)果的比較如圖2所示。

圖2 算法的防沖撞性能比較

　　由圖2可知，當(dāng)標(biāo)簽數(shù)量較少時(shí)，探測(cè)到一位碰撞幾率不大，動(dòng)態(tài)調(diào)整算法比后退式算法只有稍微優(yōu)勢(shì)，而當(dāng)標(biāo)簽數(shù)量明顯增多時(shí)，標(biāo)簽ID值比較接近，探測(cè)到一位碰撞的幾率較大，M較大，動(dòng)態(tài)調(diào)整算法效率明顯優(yōu)于后退式算法。而ISO/IEC 18000-6B協(xié)議的類(lèi)二進(jìn)制搜索算法是隨機(jī)產(chǎn)生0,1信號(hào)進(jìn)行搜索，不能實(shí)現(xiàn)有效的有序性讀取，仿真結(jié)果也表明其識(shí)別能力顯著低于動(dòng)態(tài)調(diào)整搜索法?？梢?jiàn)，動(dòng)態(tài)調(diào)整搜索法可被有效用于ISO/IEC 18000-6B協(xié)議的標(biāo)簽沖突問(wèn)題解決。

　　尤其當(dāng)2 ^L 個(gè)標(biāo)簽第1次發(fā)送Request(1)識(shí)別指令只探測(cè)出L個(gè)碰撞位時(shí)，可知識(shí)別過(guò)程中將出現(xiàn)連續(xù)的1位碰撞，此時(shí)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。對(duì)比后退式算法需要發(fā)送S(2 ^{L )}=2 ^L+1-1次查詢(xún)指令，而系統(tǒng)吞吐率為K=0.5。動(dòng)態(tài)調(diào)整算法在最優(yōu)情況下，效率是后退式算法的倍數(shù)。同時(shí)，動(dòng)態(tài)調(diào)整算法對(duì)指令長(zhǎng)度進(jìn)行了動(dòng)態(tài)調(diào)整，可以有效地減小發(fā)送信息量提高發(fā)送速率。

　　2 基于標(biāo)簽卡號(hào)連續(xù)性的防沖撞算法

　　對(duì)于如倉(cāng)庫(kù)的貨物管理，每一批貨物內(nèi)標(biāo)簽卡號(hào)基本上是連續(xù)的，此時(shí)可用另一種防沖撞算法基于一位碰撞直接識(shí)別的輪詢(xún)算法快速識(shí)別標(biāo)簽[4]。

　　2.1 輪詢(xún)算法

　　該算法保持發(fā)送指令和Manchester編碼不變。(1)發(fā)送Request(1)，利用Manchester編碼確定碰撞位的具體位置得到L個(gè)碰撞位；(2)將除最低碰撞位的L-1個(gè)碰撞位看作一個(gè)二進(jìn)制數(shù)H，從0~2 ^L−1遞增，得DATA；(3)每次發(fā)完Request(DATA)后，H自增"1"，得出新的DATA，即實(shí)現(xiàn)一個(gè)輪詢(xún)過(guò)程。具體過(guò)程如表2所示。

　　表2 輪詢(xún)算法查詢(xún)過(guò)程

　　對(duì)于表2的8個(gè)標(biāo)簽，用輪詢(xún)算法只需發(fā)送5次查詢(xún)指令，用動(dòng)態(tài)調(diào)整搜索法要發(fā)送7次指令，而用后退式算法需發(fā)送15次?？梢?jiàn)，對(duì)于卡號(hào)連續(xù)的情況，輪詢(xún)算法能更有效地實(shí)現(xiàn)標(biāo)簽防沖撞。

　　2.2 算法性能分析

　　對(duì)于卡號(hào)連續(xù)的N個(gè)標(biāo)簽，探測(cè)到L個(gè)碰撞位時(shí)，發(fā)送的查詢(xún)指令次數(shù)為
　　S(N)=2 ^L-1+1

　　系統(tǒng)的有效服務(wù)率即吞吐率為
　　K=N/S(N)=N/(2 ^L-1+1)

　　可知查詢(xún)次數(shù)S(N)只與碰撞位數(shù)L有關(guān)，而與標(biāo)簽總數(shù)無(wú)關(guān)，吞吐率K不僅與碰撞位數(shù)有關(guān)還與標(biāo)簽總數(shù)有關(guān)。特別地，令待識(shí)別的標(biāo)簽卡號(hào)從0開(kāi)始，與1.3節(jié)介紹的動(dòng)態(tài)調(diào)整算法的比較如表3所示。

　　表3 算法比較

　　從表3可看出在最優(yōu)情況下，輪詢(xún)算法可使吞吐率K達(dá)到2，而動(dòng)態(tài)調(diào)整搜索法的最優(yōu)吞吐率K為1，后退式算法[3]的吞吐率K為0.5?？梢?jiàn)，輪詢(xún)算法具有很大的應(yīng)用潛力。

　　根據(jù)式(4)可畫(huà)出吞吐率K與標(biāo)簽數(shù)量N和碰撞位數(shù)L的關(guān)系曲線，如圖3所示。

　　從圖3可看出，標(biāo)簽數(shù)量較少，而碰撞位數(shù)卻很大時(shí)，吞吐率較低，此時(shí)不適合用輪詢(xún)算法。這種缺陷可稱(chēng)為Hamming懸崖(Hamming cliffs)，相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離。例如2個(gè)標(biāo)簽卡號(hào)分別為01111和10000，碰撞位數(shù)為5，要輪詢(xún)25-1+1=17次才讀完這兩標(biāo)簽，可見(jiàn)效率很低。從圖3可看出只有標(biāo)簽數(shù)量較大時(shí)，吞吐率K受碰撞位數(shù)影響不大，能克服Hamming懸崖，此時(shí)K基本介于1～2之間，效果比動(dòng)態(tài)調(diào)整搜索法最優(yōu)吞吐率K=1要好。

　　對(duì)于卡號(hào)連續(xù)的標(biāo)簽，并不要求嚴(yán)格連續(xù)，只要大部分標(biāo)簽卡號(hào)滿足一定的連續(xù)性就可有效使用輪詢(xún)算法。另外，輪詢(xún)算法只需使用一次Manchester編碼識(shí)別碰撞位，則只需按照規(guī)則發(fā)送指令，能夠大大降低系統(tǒng)設(shè)計(jì)的復(fù)雜性。

3 結(jié)束語(yǔ)

　　本文針對(duì)RFID技術(shù)日益嚴(yán)重的標(biāo)簽沖撞問(wèn)題，指出對(duì)一般沖突情況，可用動(dòng)態(tài)調(diào)整搜索法進(jìn)行防沖撞，并通過(guò)對(duì)比表明該算法能有效應(yīng)用于ISO/IEC 18000-6B相關(guān)協(xié)議的RFID系統(tǒng)中，而當(dāng)具備一定先驗(yàn)知識(shí)，了解到待識(shí)別標(biāo)簽卡號(hào)滿足一定連續(xù)性，且數(shù)量較大時(shí)，可用輪詢(xún)算法進(jìn)行有效的防沖撞處理。