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

梁彪 鄭勇鑫 王玉瑩 秦中元

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

關(guān)鍵詞：射頻識(shí)別；標(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 概述

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

ALOHA算法吞吐率低，僅為18.4%。幀時(shí)隙ALOHA算法FSA（Framed Slotted ALOHA）是基于ALOHA算法的擴(kuò)展，F(xiàn)SA算法在幀長(zhǎng)約等于未識(shí)別的標(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ù)量來(lái)動(dòng)態(tài)調(diào)整幀長(zhǎng)的方法以保證最大吞吐效率的。因此在標(biāo)簽數(shù)量少時(shí)這類概率性防碰撞算法的識(shí)別效率不高，而且消耗時(shí)隙量大。

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

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

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

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

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

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

閱讀器初始化，使所有標(biāo)簽進(jìn)入激活狀態(tài)。接著閱讀器選擇一個(gè)數(shù)估計(jì)幀長(zhǎng)，一般選擇較大的數(shù)，例如256。閱讀器向可讀取范圍內(nèi)的所有標(biāo)簽發(fā)送標(biāo)簽預(yù)估命令-Estimate命令，標(biāo)簽根據(jù)最大幀長(zhǎng)的ALOHA算法發(fā)送各自EPC編碼，閱讀器統(tǒng)計(jì)碰撞時(shí)隙，空閑時(shí)隙和成功識(shí)別時(shí)隙個(gè)數(shù)，利用概率知識(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ù)附加請(qǐng)求與命令Query一起發(fā)送給所有標(biāo)簽，作為這一幀的開(kāi)始。假設(shè)經(jīng)過(guò)第一輪的標(biāo)簽估計(jì)，標(biāo)簽數(shù)量為N=100，計(jì)算標(biāo)簽分組次數(shù)k=6。閱讀器設(shè)置這一幀的時(shí)隙個(gè)數(shù)為2k=64，即幀長(zhǎng)L為64。

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

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

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

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

4 仿真分析

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

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

表中第一列為時(shí)隙號(hào)，其余列的每行為在該時(shí)隙發(fā)送的標(biāo)簽的EPC編碼。由于時(shí)隙號(hào)對(duì)應(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)簽信息后，得到信號(hào)為X1XX，閱讀器再次發(fā)送QueryAdjust命令附加參數(shù)0111，當(dāng)前時(shí)隙的三個(gè)標(biāo)簽收到該命令后，檢測(cè)發(fā)送編碼是否小于0111，小于則計(jì)數(shù)器置0并回復(fù)EPC編碼，大于則計(jì)數(shù)器置1并轉(zhuǎn)為wait狀態(tài)。閱讀器成功識(shí)別編碼為0110（416）的標(biāo)簽后，再次發(fā)送QueryAdjust命令附加參數(shù)1111，剩余兩個(gè)標(biāo)簽計(jì)數(shù)器置0并回復(fù)，接下來(lái)的過(guò)程和二進(jìn)制搜索算法相同。在第2個(gè)時(shí)隙中，需要閱讀器與標(biāo)簽5回合的交互來(lái)完成識(shí)別。當(dāng)時(shí)隙中標(biāo)簽數(shù)量為2個(gè)時(shí)，則只需要3回合的交互。

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

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

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

5 結(jié)論

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

[參考文獻(xiàn)]

[1]丁治國(guó).RFID關(guān)鍵技術(shù)研究與實(shí)現(xiàn)[D].安徽：中國(guó)科學(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í)別技術(shù)[M].3版.吳曉峰，陳大才，譯.北京：電子工業(yè)出版社，2006.

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

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

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