梁彪 鄭勇鑫 王玉瑩 秦中元

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

關(guān)鍵詞：射頻識別；標(biāo)簽防碰撞；模運(yùn)算分組

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 概述

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

2 基本算法研究

2.1 幀時(shí)隙ALOHA算法

幀時(shí)隙 ALOHA（Framed Slotted ALOHA，F(xiàn)SA）算法是一種隨機(jī)時(shí)分多址方式的用戶信息通信收發(fā)算法。該算法將信道用信息幀表示，其中，幀是指由閱讀器要求的包含若干時(shí)隙的時(shí)間間隔。信息幀可以分成多個(gè)時(shí)隙，其中，時(shí)隙是指標(biāo)簽發(fā)送自身標(biāo)識的時(shí)間長度。當(dāng)一個(gè)時(shí)隙只被一個(gè)標(biāo)簽占有時(shí)，閱讀器才會(huì)正確識別該標(biāo)簽，而當(dāng)一個(gè)時(shí)隙內(nèi)有2個(gè)或2個(gè)以上標(biāo)簽時(shí)，會(huì)發(fā)生碰撞，讀寫器無法正確識別，若時(shí)隙為空則跳過[3]。

ALOHA算法吞吐率低，僅為18.4%。幀時(shí)隙ALOHA算法FSA（Framed Slotted ALOHA）是基于ALOHA算法的擴(kuò)展，F(xiàn)SA算法在幀長約等于未識別的標(biāo)簽數(shù)目時(shí)吞吐率最大，約為36.8%[4]?；贏LOHA算法的一些改進(jìn)算法如動(dòng)態(tài)幀時(shí)隙ALOHA算法ALOHA（Dynamic Slotted ALOHA）[5]是根據(jù)標(biāo)簽數(shù)量來動(dòng)態(tài)調(diào)整幀長的方法以保證最大吞吐效率的。因此在標(biāo)簽數(shù)量少時(shí)這類概率性防碰撞算法的識別效率不高，而且消耗時(shí)隙量大。

2.2 二進(jìn)制搜索算法

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

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

3 基于模運(yùn)算標(biāo)簽分類的RFID標(biāo)簽防碰撞識別方法

為了提高大量標(biāo)簽存在時(shí)的識別效率，提出了一種基于模運(yùn)算標(biāo)簽分類的RFID標(biāo)簽防碰撞識別方法，采用逐級分組機(jī)制，每一組只有少量標(biāo)簽，一般可將每組標(biāo)簽數(shù)控制在少于4個(gè)。本方法構(gòu)造出一種有利于標(biāo)簽識別的碰撞環(huán)境，使得每組的標(biāo)簽具有大量相同位和少量碰撞位的特征，結(jié)合曼徹斯特編碼的特征和二進(jìn)制搜索算法的特點(diǎn)可以高效的識別標(biāo)簽。閱讀器識別標(biāo)簽的具體步驟如圖1所示

3.1 標(biāo)簽數(shù)量估計(jì)

閱讀器初始化，使所有標(biāo)簽進(jìn)入激活狀態(tài)。接著閱讀器選擇一個(gè)數(shù)估計(jì)幀長，一般選擇較大的數(shù)，例如256。閱讀器向可讀取范圍內(nèi)的所有標(biāo)簽發(fā)送標(biāo)簽預(yù)估命令-Estimate命令，標(biāo)簽根據(jù)最大幀長的ALOHA算法發(fā)送各自EPC編碼，閱讀器統(tǒng)計(jì)碰撞時(shí)隙，空閑時(shí)隙和成功識別時(shí)隙個(gè)數(shù)，利用概率知識估算標(biāo)簽數(shù)量。

3.2 標(biāo)簽分組

3.2.1 閱讀器發(fā)送分組次數(shù)

閱讀器計(jì)算標(biāo)簽分組次數(shù)k，k的計(jì)算方法：

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

3.2.2 標(biāo)簽分組計(jì)算

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

3.2.3 標(biāo)簽按時(shí)隙發(fā)送

標(biāo)簽分組完成后，檢測當(dāng)前時(shí)隙號和標(biāo)簽臨時(shí)寄存器中存儲(chǔ)的分組號是否匹配，若匹配則標(biāo)簽發(fā)送信息，若不匹配則標(biāo)簽設(shè)為silence狀態(tài)。

4 仿真分析

在RFID系統(tǒng)中，吞吐率和系統(tǒng)識別率是衡量RFID系統(tǒng)好壞的主要指標(biāo)。而吞吐率和系統(tǒng)識別率這兩個(gè)參數(shù)是緊密聯(lián)系的，故在此僅討論系統(tǒng)識別率。系統(tǒng)識別率公式：

其中α為系統(tǒng)識別率，NT為標(biāo)簽數(shù)量，S為總時(shí)隙數(shù)。下面結(jié)合具體實(shí)例進(jìn)行分析。假設(shè)第1到20時(shí)隙的分組結(jié)果為：

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

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

閱讀器通過這一幀64個(gè)時(shí)隙后，識別全部標(biāo)簽，整個(gè)讀取過程結(jié)束。

下面通過計(jì)算機(jī)對ALOHA算法、二叉樹后退式索引算法和本文所提出的算法進(jìn)行Matlab仿真實(shí)驗(yàn)，實(shí)驗(yàn)條件相同，標(biāo)簽為100-1000個(gè)。在仿真中，橫坐標(biāo)為標(biāo)簽數(shù)目，縱坐標(biāo)為系統(tǒng)識別率，可得仿真結(jié)果如圖2所示。

如圖2所示，經(jīng)過Matlab仿真計(jì)算，在相同標(biāo)簽數(shù)目條件下，本文提出的方案系統(tǒng)識別率較高。

5 結(jié)論

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

[參考文獻(xiàn)]

[1]丁治國.RFID關(guān)鍵技術(shù)研究與實(shí)現(xiàn)[D].安徽：中國科學(xué)技術(shù)大學(xué)， 2009，05.

[2]Finkenzeller K.RFID Handbook，F(xiàn)undamentals and Applicationsin Contactless Smart Cards and Identification[M]. 2nd ed.Chichester，UK：John Wiley and Sons Ltd.，2003.

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

[4]李萌，錢志鴻，張旭，等.基于時(shí)隙預(yù)測的RFID防碰撞ALOHA算法[J].通信學(xué)報(bào)，2011，32（12）：43-50.

[5]姜立芬，盧桂章.射頻識別系統(tǒng)中防碰撞算法研究[J].計(jì)算機(jī)工程與應(yīng)用，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中多標(biāo)簽識別缺陷與防碰撞算法分析[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2010（1）：18-20.

[10]郎為民，陶少國.電子產(chǎn)品代碼（EPC）標(biāo)準(zhǔn)化進(jìn)展[J].信息通信，2006，3（3）：9-14.