基于模運算標簽分類的RFID標簽防碰撞識別方法

梁彪 鄭勇鑫 王玉瑩 秦中元

摘 要：為了解決射頻識別（RFID）系統中的多標簽防碰撞問題，在分析幀時隙ALOHA算法的基礎上，提出一種基于模運算標簽分類的RFID標簽防碰撞識別方法。引入一種檢測信息碰撞的時隙選擇信息，對標簽所選取時隙的碰撞情況進行分析并估計標簽數量；然后對標簽EPC編碼進行逐級的取模運算，將同余的標簽歸為一組。各個標簽經過K次取模運算后，分為2k組，每組只有發生少量碰撞位的標簽。再將標簽按照分組對應的時隙發送，碰撞標簽采用二叉樹后退式算法處理。本方法極大的提高了標簽的識別效率，適用于射頻識別系統中閱讀器對于大量電子標簽的快速識別。

關鍵詞：射頻識別；標簽防碰撞；模運算分組

RFID tag anti-collision identification method

based on modular arithmetic tag classification

Zheng Yongxin Wang Yuying Qin Zhongyuan（Southeast University，Nanjing China 211189）

Abstract：In order to solve the problem of multiple tags collision in RFID system，on the basis of ALOHA algorithm， RFID tag anti-collision identification method based on modular arithmetic tag classification was proposed. Bring in a kind of slot selection information used to detect information collision， it analyze the collision caused by slot and estimate the number of tag； Then do the modular arithmetic on the Tag EPC step by step， the tags with the same remainder are classified as a group.After K times modular arithmetic， tags are divided into 2K groups，The tag in each group has little collision bit. Then tags are sent according to the corresponding slot， collision tags can be dealed with binary tree backword algorithm. This method greatly improve the efficiency of the tag identification， it is suitable for readers which has a large number of electronic tags to identify in RFID system.

Key words：RFID；Tag anti-collision；Modular arithmetic

1 概述

無線射頻識別技術（Radio Frequency Identification，簡稱RFID）是一種非接觸的自動識別技術，其基本原理是利用射頻信號或空間耦合（電感或電磁耦合）的傳輸特性，實現對物體或商品的自動識別。RFID技術同其它的自動識別技術（條形碼技術、光學識別和生物識別技術，包括虹膜、面部、聲音和指紋）相比，具有抗干擾能力強、信息量大、非視覺范圍讀寫和壽命長等特點，被廣泛應用于物流、供應鏈、動物和車輛識別、門禁系統、圖書管理、自動收費和生產制造等領域[1]。RFID系統主要的難題在于多標簽碰撞時較低的標簽數據識讀率，多標簽碰撞是指當多個標簽同時存在于同一個射頻信道內時，閱讀器無法讀取標簽數據的現象。目前，解決RFID標簽閱讀沖突問題最廣泛的是幀時隙ALOHA算法和二進制搜索算法。由于簡單實用，幀時隙ALOHA算法應用更為頻繁[2]，例如ISO/IEC18000-6 Type A協議和EPC Class1協議都是使用幀時隙ALOHA算法。

2 基本算法研究

2.1 幀時隙ALOHA算法

幀時隙 ALOHA（Framed Slotted ALOHA，FSA）算法是一種隨機時分多址方式的用戶信息通信收發算法。該算法將信道用信息幀表示，其中，幀是指由閱讀器要求的包含若干時隙的時間間隔。信息幀可以分成多個時隙，其中，時隙是指標簽發送自身標識的時間長度。當一個時隙只被一個標簽占有時，閱讀器才會正確識別該標簽，而當一個時隙內有2個或2個以上標簽時，會發生碰撞，讀寫器無法正確識別，若時隙為空則跳過[3]。

ALOHA算法吞吐率低，僅為18.4%。幀時隙ALOHA算法FSA（Framed Slotted ALOHA）是基于ALOHA算法的擴展，FSA算法在幀長約等于未識別的標簽數目時吞吐率最大，約為36.8%[4]。基于ALOHA算法的一些改進算法如動態幀時隙ALOHA算法ALOHA（Dynamic Slotted ALOHA）[5]是根據標簽數量來動態調整幀長的方法以保證最大吞吐效率的。因此在標簽數量少時這類概率性防碰撞算法的識別效率不高，而且消耗時隙量大。

2.2 二進制搜索算法

二進制搜索算法又稱為二叉樹搜索算法，它要求能夠在閱讀器中確定數據碰撞位的準確位置。因此，必須要有合適的位編碼法。曼徹斯特碼用上升沿表示0，用下降沿表示1，在數據傳輸過程中不允許/沒有變化0的狀態。如果采用ASK調制方式，當2個（或多個）應答器同時發送的數據位為不同的值，則對應的曼徹斯特碼的上升沿和下降沿互相抵消，接收到的副載波就是不間斷的，造成一種錯誤的狀態，從而可以確定碰撞位置。

基于二進制的防碰撞算法，國外的研究有很多，比如BBT（bit-by-bit tree）[6]算法。BBT算法的基本思想是：閱讀器發送請求命令，請求標簽回送序列號。響應的標簽每次只發送1 位序列號。如果閱讀器端沒有發生沖突，則在內存中保存該接收位，然后請求下一位；如果閱讀器處發生沖突，則將該沖突位分為2支，即分支0和分支1，從中選擇一個分支，然后請求下一位。閱讀器重復上述過程直至序列號的每一位都被識別。國內主要研究的有：基于后退式的二進制搜索算法[7]，當識別出一個標簽后，算法根據上一次請求命令參數來獲得下一個請求命令，以此來極大地縮短識別過程；動態二進制搜索算法和多狀態二進制搜索算法[8]等，主要通過減少基本算法中閱讀器命令和標簽響應信息中存在的大量冗余數據來提高識別效率。雖然這類確定性防碰撞算法識別率高，適應大規模標簽數量的場合，但是這類算法需要發送全部或部分標簽EPC進行搜索，對于標簽代碼位數較多的情況，存在標簽與閱讀器之間的通信量過大的問題[9]。

3 基于模運算標簽分類的RFID標簽防碰撞識別方法

為了提高大量標簽存在時的識別效率，提出了一種基于模運算標簽分類的RFID標簽防碰撞識別方法，采用逐級分組機制，每一組只有少量標簽，一般可將每組標簽數控制在少于4個。本方法構造出一種有利于標簽識別的碰撞環境，使得每組的標簽具有大量相同位和少量碰撞位的特征，結合曼徹斯特編碼的特征和二進制搜索算法的特點可以高效的識別標簽。閱讀器識別標簽的具體步驟如圖1所示

3.1 標簽數量估計

閱讀器初始化，使所有標簽進入激活狀態。接著閱讀器選擇一個數估計幀長，一般選擇較大的數，例如256。閱讀器向可讀取范圍內的所有標簽發送標簽預估命令-Estimate命令，標簽根據最大幀長的ALOHA算法發送各自EPC編碼，閱讀器統計碰撞時隙，空閑時隙和成功識別時隙個數，利用概率知識估算標簽數量。

3.2 標簽分組

3.2.1 閱讀器發送分組次數

閱讀器計算標簽分組次數k，k的計算方法：

其中N為第一步估計出的標簽數量。閱讀器將k作為參數附加請求與命令Query一起發送給所有標簽，作為這一幀的開始。假設經過第一輪的標簽估計，標簽數量為N=100，計算標簽分組次數k=6。閱讀器設置這一幀的時隙個數為2k=64，即幀長L為64。

3.2.2 標簽分組計算

根據上文計算出的分組次數k，對標簽的EPC編碼進行k次摸2運算，根據運算結果對標簽進行分組。下面詳細說明：標簽收到RFID閱讀器發送的k值后，將計數器的值設為k。開始進行k次取模運算。由于標簽ID模2運算相當于右移一位操作，下文將以標簽ID位數來更直觀的說明，如圖2所示。第1次分組，將余數為0的分為一組，在前32個時隙發送，余數為1的分為另一組，在后32個時隙發送，相當于將EPC編碼最低位為0和最低位為1的標簽分開。執行該次運算后，標簽將0或1存儲在臨時寄存器的最高位，計數器值減一。第2次分組，標簽EPC編碼模22運算，將次低位分別為0和1的ID分開，即分為“00”，“10”，“01”，“11”四組，標簽將0或1存儲在臨時寄存器的次高位，依此類推，通過6次分組后，100個標簽被分為64組，分別在64個時隙里發送。通過比較標簽ID和時隙的對應關系可以發現，EPC編碼的后k位數和發送的時隙之間存在逆序關系，例如ID后6位為101100的標簽將在第001101（即十進制數13）個時隙發送。將經過逆序處理之后的標簽分組序列存儲在臨時寄存器中，以供標簽匹配。

3.2.3 標簽按時隙發送

標簽分組完成后，檢測當前時隙號和標簽臨時寄存器中存儲的分組號是否匹配，若匹配則標簽發送信息，若不匹配則標簽設為silence狀態。

4 仿真分析

在RFID系統中，吞吐率和系統識別率是衡量RFID系統好壞的主要指標。而吞吐率和系統識別率這兩個參數是緊密聯系的，故在此僅討論系統識別率。系統識別率公式：

其中α為系統識別率，NT為標簽數量，S為總時隙數。下面結合具體實例進行分析。假設第1到20時隙的分組結果為：

表中第一列為時隙號，其余列的每行為在該時隙發送的標簽的EPC編碼。由于時隙號對應EPC編碼，因此標簽只需發送部分EPC編碼即可。例如第2個時隙中的標簽，其后6位的編碼為100000（逆序），所以EPC編碼為928的標簽只需發送前4位1110即可（EPC編碼10位情況下）。

再根據曼切斯特編碼的特性結合二進制搜索算法，以第2個時隙為例，閱讀器收到標簽信息后，得到信號為X1XX，閱讀器再次發送QueryAdjust命令附加參數0111，當前時隙的三個標簽收到該命令后，檢測發送編碼是否小于0111，小于則計數器置0并回復EPC編碼，大于則計數器置1并轉為wait狀態。閱讀器成功識別編碼為0110（416）的標簽后，再次發送QueryAdjust命令附加參數1111，剩余兩個標簽計數器置0并回復，接下來的過程和二進制搜索算法相同。在第2個時隙中，需要閱讀器與標簽5回合的交互來完成識別。當時隙中標簽數量為2個時，則只需要3回合的交互。

閱讀器通過這一幀64個時隙后，識別全部標簽，整個讀取過程結束。

下面通過計算機對ALOHA算法、二叉樹后退式索引算法和本文所提出的算法進行Matlab仿真實驗，實驗條件相同，標簽為100-1000個。在仿真中，橫坐標為標簽數目，縱坐標為系統識別率，可得仿真結果如圖2所示。

如圖2所示，經過Matlab仿真計算，在相同標簽數目條件下，本文提出的方案系統識別率較高。

5 結論

本方法可以對大量標簽進行快速分組，同時對標簽進行排序，不斷減少同組標簽的碰撞位，以利用曼徹斯特編碼的性質一次識別兩個標簽。通過標簽分組序列號和時隙號的對應關系，減少標簽發送編碼的長度。由于分組中的標簽數量非常少，而且標簽具有大量相同的位，因此本方法很好的發揮了曼徹斯特編碼的特性和二進制后退式搜索算法的特點，提高了多標簽識別效率。

[參考文獻]

[1]丁治國.RFID關鍵技術研究與實現[D].安徽：中國科學技術大學， 2009，05.

[2]Finkenzeller K.RFID Handbook，Fundamentals and Applicationsin Contactless Smart Cards and Identification[M]. 2nd ed.Chichester，UK：John Wiley and Sons Ltd.，2003.

[3]Finkenzeller K.射頻識別技術[M].3版.吳曉峰，陳大才，譯.北京：電子工業出版社，2006.

[4]李萌，錢志鴻，張旭，等.基于時隙預測的RFID防碰撞ALOHA算法[J].通信學報，2011，32（12）：43-50.

[5]姜立芬，盧桂章.射頻識別系統中防碰撞算法研究[J].計算機工程與應用，2007，43（5）：29-32.

[6]MATEUL，MOLLF.Review of energy harvesting techniques and application for microelectronics[C].Proc of SPIE，2009：359-373.

[7]RAGUNATHANV，KANSALA，HSUJ.Design consideration for solar energy harvesting wireless embedded system[C].Proc of the 4th International Symposium on Information Proceeding in Sensor Networks，Piscataway，IEEE Press，2009：457-462.

[8]GAO Yi，SUN Guiling，LI Weixiang，et al.Wireless sensor node design based on solar energy supply[C].Proc of the 2nd International Conference on Power Electronics and Intelligent Transportation System，2009：203-207.

[9]劉猛，徐展.RFID中多標簽識別缺陷與防碰撞算法分析[J].單片機與嵌入式系統應用，2010（1）：18-20.

[10]郎為民，陶少國.電子產品代碼（EPC）標準化進展[J].信息通信，2006，3（3）：9-14.