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