標簽防沖撞算法設計

1、標簽防沖撞算法設計射頻識別(RFID)技術(shù)是近幾年發(fā)展起來的一種自動識別技術(shù)。RFID系統(tǒng)一般通過閱讀器識別帶有唯一電子產(chǎn)品代碼(ID)值的標簽。閱讀器射頻場范圍內(nèi)標簽數(shù)量較多時不同標簽返回數(shù)據(jù)發(fā)生重疊，導致閱讀器對接收信號解碼錯誤，可以將其稱為標簽沖撞。由于TDMA時分多址方式應用簡單，容易實現(xiàn)大量標簽數(shù)據(jù)讀寫，因此被多數(shù)防沖撞算法采用?，F(xiàn)有防沖撞算法主要包括ALOHA算法和樹分叉算法兩種。當大量標簽并存時，ALOHA算法1的幀沖撞嚴重，易引起性能急劇惡化，不適宜大規(guī)模標簽讀取。所以，主要發(fā)展樹分叉算法。目前樹分叉算法主要有ISO/IEC18000-6B的類二進制搜索算法2、后退式二進制樹形

2、搜索算法3。本文設計了一種標簽防沖撞算法。1基于標簽卡號無序性的防沖撞算法對于如公路收費亭的車輛識別，標簽的卡號是無序的(相互間不關(guān)聯(lián))，此時用動態(tài)調(diào)整二進制樹形搜索法，能快速實現(xiàn)標簽數(shù)據(jù)讀寫。該算法用Manchester編碼準確判別位碰撞，并保持后退式二進制樹算法的后退機理。1.1Manchester編碼與防沖撞該編碼采用以下規(guī)則：(1)邏輯“1”表示下降沿跳變。(2)邏輯“0”表示上升沿跳變。(3)若無狀態(tài)跳變，作為錯誤被識別。當多個標簽同時返回的數(shù)位有不同之值時，上升和下降沿互相抵消，以至無狀態(tài)跳變，閱讀器知該位出現(xiàn)碰撞，產(chǎn)生了錯誤。 利用Manchester編碼識別碰撞位，如圖1所示。

3、假如有兩個標簽，其ID號為10011111和10111011，利用Manchester可識別出D5和D2位碰撞。(a)標簽1的ID為10011111(b)標簽2的ID為10111011(c)閱讀接收的ID碰撞為101111在表1中，“xx”表示碰撞位；“-”表示標簽不響應；“”表示標簽已被屏蔽為靜默狀態(tài)。每次查詢出ID值后即對標簽進行屏蔽。當?shù)?次執(zhí)行指令為Request(1)全返回指令，而只有2個標簽應答，可知所有標簽查詢完畢。此時可據(jù)確知的8個標簽ID值，按需進行其他操作。從表1可知用動態(tài)調(diào)整搜索法識別8個標簽只需發(fā)送7次指令，而后退式算法3需要28-1=15次?？梢妱討B(tài)調(diào)整搜索法的工作效

4、率有了很大改進。1.4算法性能分析由于動態(tài)調(diào)整搜索法是基于后退式算法3，因此在最不理想的情況下，也可保持N個標簽的查詢次數(shù)為S(N)=2N-1 。當射頻場中碰撞的標簽數(shù)量N較大，此時識別出1位碰撞的幾率較大。設在整個識別過程中探測到M次只有1個碰撞位，通過動態(tài)調(diào)整算法的直接識別相當于比后退式算法減少了2M次查詢指令，此時查詢次數(shù)為 S(N)=2(N-M)-1系統(tǒng)的有效服務率即吞吐率為 K=N/S(N)=N/(2N-2M-1)將動態(tài)調(diào)整搜索法與類二進制搜索法2，后退式算法3在ISO/IEC18000-6B協(xié)議2的應用中進行查詢次數(shù)的比較。為保持與協(xié)議規(guī)范一致，將使用協(xié)議相關(guān)功能指令GROUP_S

5、ELECT_EQ,READ/WRITE,DATA_READ2分別取代第1.2節(jié)的指令Request,Read-Write,Quiet同時用FM0編碼2取代Manchester碼。假設標簽ID長度為16，用Matlab編程可得到仿真結(jié)果的比較如圖2所示。圖2算法的防沖撞性能比較 由圖2可知，當標簽數(shù)量較少時，探測到一位碰撞幾率不大，動態(tài)調(diào)整算法比后退式算法只有稍微優(yōu)勢，而當標簽數(shù)量明顯增多時，標簽ID值比較接近，探測到一位碰撞的幾率較大，M較大，動態(tài)調(diào)整算法效率明顯優(yōu)于后退式算法。而ISO/IEC18000-6B協(xié)議的類二進制搜索算法是隨機產(chǎn)生0,1信號進行搜索，不能實現(xiàn)有效的有序性讀取，仿真結(jié)

6、果也表明其識別能力顯著低于動態(tài)調(diào)整搜索法?？梢姡瑒討B(tài)調(diào)整搜索法可被有效用于ISO/IEC18000-6B協(xié)議的標簽沖突問題解決。尤其當2 L 個標簽第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)整算法對指令長度進行了動態(tài)調(diào)整，可以有效地減小發(fā)送信息量提高發(fā)送速率。2基于標簽卡號連

7、續(xù)性的防沖撞算法對于如倉庫的貨物管理，每一批貨物內(nèi)標簽卡號基本上是連續(xù)的，此時可用另一種防沖撞算法基于一位碰撞直接識別的輪詢算法快速識別標簽4。2.1輪詢算法該算法保持發(fā)送指令和Manchester編碼不變。(1)發(fā)送Request(1)，利用Manchester編碼確定碰撞位的具體位置得到L個碰撞位；(2)將除最低碰撞位的L-1個碰撞位看作一個二進制數(shù)H，從02 L1遞增，得DATA；(3)每次發(fā)完Request(DATA)后，H自增1，得出新的DATA，即實現(xiàn)一個輪詢過程。具體過程如表2所示。表2輪詢算法查詢過程對于表2的8個標簽，用輪詢算法只需發(fā)送5次查詢指令，用動態(tài)調(diào)整搜索法要發(fā)送7次

8、指令，而用后退式算法需發(fā)送15次?？梢姡瑢τ诳ㄌ栠B續(xù)的情況，輪詢算法能更有效地實現(xiàn)標簽防沖撞。2.2算法性能分析對于卡號連續(xù)的N個標簽，探測到L個碰撞位時，發(fā)送的查詢指令次數(shù)為S(N)=2 L-1+1系統(tǒng)的有效服務率即吞吐率為K=N/S(N)=N/(2 L-1+1)可知查詢次數(shù)S(N)只與碰撞位數(shù)L有關(guān)，而與標簽總數(shù)無關(guān)，吞吐率K不僅與碰撞位數(shù)有關(guān)還與標簽總數(shù)有關(guān)。特別地，令待識別的標簽卡號從0開始，與1.3節(jié)介紹的動態(tài)調(diào)整算法的比較如表3所示。表3算法比較從表3可看出在最優(yōu)情況下，輪詢算法可使吞吐率K達到2，而動態(tài)調(diào)整搜索法的最優(yōu)吞吐率K為1，后退式算法3的吞吐率K為0.5?？梢?，輪詢算法具

9、有很大的應用潛力。根據(jù)式(4)可畫出吞吐率K與標簽數(shù)量N和碰撞位數(shù)L的關(guān)系曲線，如圖3所示。從圖3可看出，標簽數(shù)量較少，而碰撞位數(shù)卻很大時，吞吐率較低，此時不適合用輪詢算法。這種缺陷可稱為Hamming懸崖(Hammingcliffs)，相鄰整數(shù)的二進制編碼可能具有較大的Hamming距離。例如2個標簽卡號分別為01111和10000，碰撞位數(shù)為5，要輪詢25-1+1=17次才讀完這兩標簽，可見效率很低。從圖3可看出只有標簽數(shù)量較大時，吞吐率K受碰撞位數(shù)影響不大，能克服Hamming懸崖，此時K基本介于12之間，效果比動態(tài)調(diào)整搜索法最優(yōu)吞吐率K=1要好。對于卡號連續(xù)的標簽，并不要求嚴格連續(xù)，只要大部分標簽卡號滿足一定的連續(xù)性就可有效使用輪詢算法。另外，輪詢算法只需使用一次Manchester編碼識別碰撞位，則只需按照規(guī)則發(fā)送指令，能夠大大降低系統(tǒng)設計的復雜性。3結(jié)