RFID混合碰撞算法研究

汪國強，趙 璐，鄭 東

（黑龍江大學(xué) 電子工程學(xué)院，哈爾濱 150080）

0 引 言

RFID是Radio Frequency Identification的縮寫，中文譯名射頻識別技術(shù)，其技術(shù)最大的特點就是通過無線射頻信號自動對目標(biāo)進(jìn)行無接觸識別［1］。RFID系統(tǒng)由閱讀器 （Reader）、電子標(biāo)簽（Tag）、應(yīng)用系統(tǒng)3個部分組成。閱讀器在自己的工作范圍內(nèi)，不斷地通過天線發(fā)送特殊的射頻信號，當(dāng)標(biāo)簽進(jìn)入工作區(qū)域內(nèi)，標(biāo)簽會有感應(yīng)電流產(chǎn)生，這個感應(yīng)電流驅(qū)動電子標(biāo)簽，使其獲得一定的能量，將自身攜帶的序列號信息由天線發(fā)送出去，閱讀器接收到這個信息后，對信息進(jìn)行一定的處理（解調(diào)、解碼），再把處理后的信息發(fā)送到應(yīng)用系統(tǒng)中，應(yīng)用系統(tǒng)會發(fā)出下一步工作的指令。

RFID系統(tǒng)工作時經(jīng)常會有這樣一種情況出現(xiàn)，多個電子標(biāo)簽存在于閱讀器的工作范圍內(nèi)，多個使用者共同使用一個無線信道，必然會發(fā)生信道爭搶、信息干擾等問題，最終導(dǎo)致電子標(biāo)簽無法被閱讀器識別，這種情況稱之為發(fā)生了沖突或者出現(xiàn)了碰撞 （Collision）。在RFID系統(tǒng)中碰撞問題可以分為兩大類：閱讀器碰撞、標(biāo)簽碰撞。從軟件的角度采用一定的策略或方法來避免沖突現(xiàn)象的發(fā)生的過程稱為防沖突，或者防碰撞。由于碰撞產(chǎn)生的相關(guān)問題制約著RFID技術(shù)的推廣與應(yīng)用，尤其是當(dāng)RFID技術(shù)廣泛應(yīng)用于工業(yè)生產(chǎn)、銷售、貨運等需要準(zhǔn)確實現(xiàn)多目標(biāo)識別的領(lǐng)域時，由于碰撞造成數(shù)據(jù)的錯誤傳輸，信息讀取無法正常進(jìn)行，最終導(dǎo)致產(chǎn)品識別的失敗，以及產(chǎn)品信息的丟失，造成的后果會更嚴(yán)重。因此，解決碰撞問題的技術(shù)也就成為RFID系統(tǒng)中的一項至關(guān)重要的技術(shù)，由此可知對于碰撞問題的深入研究是非常有必要的。

RFID系統(tǒng)中的標(biāo)簽碰撞問題屬于多目標(biāo)識別問題，即 “多路存取”問題?！岸嗦反嫒　北旧砭褪菬o線電技術(shù)中長期面臨的難題。因此，可以通過解決多路存取問題的方法來解決標(biāo)簽的碰撞問題。一般來說總共分4類，即空分多址 （SDMA）法、頻分多址 （FDMA）法、碼分多址 （CDMA）法、時分多址 （TDMA）法［2］。從RFID的通信形式、系統(tǒng)的構(gòu)造以及成本問題上來看，TDMA法是最適合的。隨著研究的不斷深入，時分多址法又可以分為兩種不同的算法。不確定性算法、確定性算法［3］。不確定性算法主要是ALOHA類算法，包括純ALOHA算法、時隙ALOHA算法、幀時隙ALOHA算法等；確定性算法主要是二進(jìn)制算法，包括二進(jìn)制搜索算法、動態(tài)二進(jìn)制樹搜索算法等。

現(xiàn)在如何提高RFID系統(tǒng)的工作效率成為該技術(shù)發(fā)展的一個核心話題，為此本文對幀時隙ALOHA算法和二進(jìn)制搜索算法進(jìn)行了詳細(xì)研究，采用標(biāo)簽數(shù)量預(yù)測判定與分組結(jié)合的方式，對其進(jìn)行改進(jìn)，形成了一種有效的標(biāo)簽碰撞算法，并對其進(jìn)行了仿真分析。

1 FSA算法

FSA （Framed Slotted Aloha）算法稱為幀時隙ALOHA算法［4］，也可以稱為固定幀時隙ALOHA算法，這種算法是在純ALOHA算法的基礎(chǔ)上進(jìn)行改進(jìn)的一種算法，這種算法把N個時隙綁定成一組形成一幀，其大小在電子標(biāo)簽識別過程中是固定的，并且?guī)忻總€時隙的長度都能保證標(biāo)簽、閱讀器之間完成正常的通信過程，然后在一幀內(nèi)任意選擇一個時隙進(jìn)行標(biāo)簽數(shù)據(jù)的發(fā)送。這種算法適合用于傳輸標(biāo)簽數(shù)量相對較大的場合。

幀時隙ALOHA算法的過程：當(dāng)電子標(biāo)簽進(jìn)入閱讀器的工作范圍時，閱讀器把幀內(nèi)時隙數(shù)N發(fā)送給標(biāo)簽，標(biāo)簽本身產(chǎn)生一個隨機數(shù)m （m≤N），并根據(jù)自己的隨機數(shù)選擇時隙，當(dāng)時隙數(shù)與m值相等，并且只有一個標(biāo)簽響應(yīng)，則通信成功，多個標(biāo)簽響應(yīng)就會發(fā)生碰撞，沒有響應(yīng)就是空閑狀態(tài)；當(dāng)時隙數(shù)與m值不相等時，標(biāo)簽就繼續(xù)等待。因此，在整個的通信過程中閱讀器會接收到標(biāo)簽的3種應(yīng)答：成功時隙、空時隙、碰撞時隙。假設(shè)在標(biāo)簽發(fā)送信息的過程中一切的干擾都忽略不計，信息幀的長度為FL，那么，當(dāng)閱讀M個標(biāo)簽時幀內(nèi)成功時隙數(shù) （S）、空閑時隙數(shù) （B）、碰撞時隙數(shù)（C）分別為：

假設(shè)系統(tǒng)的固定幀的長度FL＝64，利用matlab進(jìn)行對該算法的正確率 （S／FL）、空閑率 （B／FL）、沖突率 （C／FL）進(jìn)行仿真，如圖1 （a）所示，隨著標(biāo)簽數(shù)量的不斷增加，沖突率也隨著增加，當(dāng)標(biāo)簽的數(shù)量在64左右時，系統(tǒng)的識別率最高，正確率最高，約為36．8%；圖1（b）中橫坐標(biāo)代表標(biāo)簽的數(shù)量，縱坐標(biāo)代表系統(tǒng)的識別率，3條曲線中FL分別為32、128、256，由圖中可以看出當(dāng)標(biāo)簽數(shù)量接近幀長度時系統(tǒng)的正確率最高約為36．8%，并且隨著標(biāo)簽的數(shù)量的增加，正確率有一定的衰減，這樣的結(jié)果與圖1（a）中結(jié)果是一致的。因此，得到結(jié)論，固定幀時隙算法當(dāng)標(biāo)簽數(shù)量和幀長度相等時效率最高約為36．8%。

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

二進(jìn)制搜索算法中，閱讀器針對于比特前綴進(jìn)行查詢，當(dāng)標(biāo)簽的序列號與查詢前綴一致時，標(biāo)簽才可以對閱讀器進(jìn)行響應(yīng)，發(fā)送其自身的序列號；當(dāng)閱讀器工作范圍內(nèi)，當(dāng)且僅當(dāng)有一個標(biāo)簽響應(yīng)時，標(biāo)簽就可以成功的被識別出來；當(dāng)標(biāo)簽的數(shù)量＞1時，閱讀器會自動給查詢前綴補一個0，進(jìn)行下一輪的查詢，這樣，前綴不斷地被增加，直到所有的標(biāo)簽被識別出來，見圖2。

通過每一輪減少沖突位的方法是二進(jìn)制搜索算法的核心，那么二進(jìn)制搜索算法的關(guān)鍵就是如何發(fā)現(xiàn)沖突位，曼切斯特碼可以有效地解決這個問題。曼切斯特碼的特點就是通過電平的跳變來表示1和0，在傳輸過程中 “無變化”是不被允許的。因此，選用曼切斯特碼來發(fā)現(xiàn)沖突位。另外要實現(xiàn)二進(jìn)制搜索算法，還需要增加一系列的命令：

REQUEST：閱讀器發(fā)送序列號 （發(fā)送請求）。

SELECT：閱讀器發(fā)送給標(biāo)簽早已經(jīng)制定好的一個序列號。

READDATA：被選中的標(biāo)簽進(jìn)行數(shù)據(jù)的發(fā)送，把自身攜帶的信息傳給閱讀器。

UNSELECT：這一輪被選中的標(biāo)簽被取消資格，進(jìn)入 “休息”狀態(tài)。

二進(jìn)制搜索算法實現(xiàn)過程：①發(fā)送REQUEST命令，要求所有的標(biāo)簽應(yīng)答，判斷碰撞發(fā)生位，通過碰撞的情況得到下一次的REQUEST（與第一次發(fā)送是不同的）；②發(fā)送重新制定的REQUEST命令，進(jìn)行第二次判斷碰撞發(fā)生位，再一次地修改REQUEST命令，這樣不斷重復(fù)下去，直到閱讀器工作的作用范圍內(nèi)只有一個標(biāo)簽響應(yīng)，這樣就完成了一個標(biāo)簽的識別，不斷重復(fù)以上的步驟，直到閱讀器工作范圍內(nèi)所有標(biāo)簽都被識別出來為止。這種二進(jìn)制搜索算法從N個標(biāo)簽中識別單個標(biāo)簽平均的次數(shù)為log2N＋1，且每一次標(biāo)簽響應(yīng)閱讀器的命令時所傳輸?shù)男蛄刑柖际峭暾?，但是這種算法的時延相對來說有些長。

圖3是二進(jìn)制搜索算法的matlab仿真圖，由圖3可見，標(biāo)簽的數(shù)量過大時，系統(tǒng)的工作效率不穩(wěn)定，標(biāo)簽的數(shù)量越大系統(tǒng)的工作效率就越低。

圖3 二進(jìn)制搜索算法仿真圖Fig．3 Simulation result of binary search algorithm

3 混合算法

為了更好地解決碰撞問題，所以把幀時隙ALOHA算法和二進(jìn)制算法進(jìn)行一定融合與改進(jìn)，最終改進(jìn)的的碰撞算法過程分為兩個部分：標(biāo)簽數(shù)量確定、標(biāo)簽識別。因此，合適的標(biāo)簽數(shù)量預(yù)測方法與合適的分組方法是決定混合算法效率的關(guān)鍵。

3．1 標(biāo)簽預(yù)測方法選擇

由于RFID系統(tǒng)工作時，閱讀器范圍內(nèi)的標(biāo)簽數(shù)量都是未知的，所以要先對工作范圍內(nèi)的標(biāo)簽進(jìn)行數(shù)量的預(yù)測，一般有以下幾種預(yù)測方案：

1）最小預(yù)測 （low bound）［5］：當(dāng)只有一個標(biāo)簽響應(yīng)閱讀器時，不會發(fā)生碰撞，但是當(dāng)標(biāo)簽響應(yīng)的數(shù)量＞1時，亦即，當(dāng)存在＞2個標(biāo)簽時就有碰撞問題，因此，基于這種思想估算標(biāo)簽的數(shù)量至少為T＝2×Sk。

2）Schout預(yù)測［6］：通過計算得到一個時隙內(nèi)，標(biāo)簽的碰撞率約為0．418，那么得到發(fā)生碰撞標(biāo)簽的數(shù)量為1／0．418＝2．392 2，因此，待識別標(biāo)簽數(shù)量T＝2．392 2×Sk。

3）Vogt預(yù)測［7］：VogtⅡ是一種基于概率統(tǒng)計的估算方法，其思想就是通過理論與實際的成功時隙數(shù)值、空閑時隙數(shù)值以及沖突時隙數(shù)值進(jìn)行對比，得到最小誤差的方法來預(yù)測標(biāo)簽的數(shù)量，通過這種方法預(yù)測到的標(biāo)簽數(shù)量值，比原來的預(yù)測方法得到的結(jié)果更加精確。

式中a0、a1、ak分別為通過預(yù)測得到的實際沖突時隙、成功時隙、空閑時隙的數(shù)值。在標(biāo)簽數(shù)N取值范圍內(nèi)內(nèi)找到ε值，這個ε值所對應(yīng)的N 值就是這種算法預(yù)測到的標(biāo)簽數(shù)。

經(jīng)過上面對3種標(biāo)簽數(shù)量預(yù)測方法的分析，可以發(fā)現(xiàn)VogtⅡ算法是采用統(tǒng)計規(guī)律進(jìn)行誤差模最小估計方法進(jìn)行標(biāo)簽數(shù)量的預(yù)測，結(jié)果更加準(zhǔn)確。因此，采用VogtⅡ算法來進(jìn)行標(biāo)簽數(shù)量的預(yù)測。

3．2 算法描述

在幀時隙算法中可看到標(biāo)簽的比特位數(shù)設(shè)定為8。因此，幀時隙算法中可設(shè)定的最大時隙數(shù)為256，以此來界定分組的閾值。通過Vogt方法進(jìn)行標(biāo)簽數(shù)量的預(yù)測，當(dāng)預(yù)測到的標(biāo)簽個數(shù)＜256時，可通過預(yù)測到的標(biāo)簽數(shù)設(shè)置最佳初始幀，并采用FSA算法進(jìn)行識別，當(dāng)識別過程中有碰撞產(chǎn)生時，就會進(jìn)行第二輪的識別；采用二進(jìn)制搜索算法進(jìn)行識別，可以有效避免碰撞和提高識別效率。當(dāng)預(yù)測到的標(biāo)簽個數(shù)＞256時，采取一定的分組策略對其進(jìn)行平均分組識別，分成的組數(shù)為n＝即取上正數(shù)，且每一組的數(shù)量為256。通過實際預(yù)測到的標(biāo)簽數(shù)，就可得到分成的組數(shù)，并且給各個組編號s［1］～s［n］，在每一組內(nèi)部采用二進(jìn)制搜索算法進(jìn)行識別，一組識別完成后進(jìn)入下一組識別，直到所有組的標(biāo)簽都完成識別。

3．3 仿真結(jié)果分析

圖4是混合算法與二進(jìn)制搜索算法、FSA算法的軟件仿真結(jié)果比較，由圖4可見，采用改進(jìn)算法的系統(tǒng)效率由原來最高0．368提高到最高為0．52，而且當(dāng)標(biāo)簽數(shù)量很大時，系統(tǒng)的效率下降相對很慢，從圖中得出結(jié)論，這種混合的改進(jìn)算法的效率比二進(jìn)制搜索算法、FSA算法的效率有了很大的提高，所以采用這種改進(jìn)的算法更好。

圖4 混合算法與傳統(tǒng)算法仿真對比Fig．4 Comparison efficiency of improved algorithm and traditional algorithm

4 結(jié) 論

混合碰撞算法是在FSA算法與二進(jìn)制搜索算法基礎(chǔ)上提出的，主要是針對于大規(guī)模標(biāo)簽進(jìn)行識別的一種改進(jìn)型算法。這種算法很好地改善了系統(tǒng)的工作效率問題，即使當(dāng)閱讀器范圍內(nèi)有很大數(shù)量的標(biāo)簽時，也能很好地解決碰撞問題。

在RFID系統(tǒng)通信過程中，碰撞問題是需要解決的重要問題，同時碰撞也是影響一個系統(tǒng)穩(wěn)定性的因素，針對這種情況本文在傳統(tǒng)算法的基礎(chǔ)上，采用了一種混合的方式來解決系統(tǒng)的碰撞問題，通過仿真證明，這種算法比傳統(tǒng)的FSA算法有了明顯優(yōu)勢，使系統(tǒng)的性能達(dá)到很高，從而更有效的解決了RFID系統(tǒng)中標(biāo)簽的碰撞問題。

［1］Ponnusamy Kumar，A．Krishnan throughput analysis of the IEEE 802．11distributed coordination function considering erroneous channel and capture effects［J］．International Journal of Automation and Computing，2011，8 （2）：236－243．

［2］Finkenzeller K．RFID handbook，fundamentals and applications in contactless smart cards and identification［K］．John Wiley and Sons Ltd，2003．

［3］Tang Z，He Y．Research of multi－access and anti－collision protocols in RFID systems ［A］．IEEE International Workshop on Anti–Counterfeiting，Security，I－dentification ［C］．Xiamen，China 2007：377－380．

［4］L．Burdet RFID multiple access methods［R］．Technical Report ETH Zurich，2004．

［5］Christian Floerkemeier，Mathias Wille．Comparison of transmission schemes for framed ALOHA based RFID［C］／／Application and the Internet Workshops，2006．SAINT Workshops 2006．

［6］Qiaoling Tong，Xuecheng Zou，Dongsheng Liu，et al．Modeling the anti－collision process of RFID system by Markov Chain ［A］．Wireless Communications，Networking and Mobile Computing ［C］．WiCom 2007．

［7］Yanfei Li，Hongjun Wang，Hua Li．A RFID algorithm based on cyclic redundancy check［A］．Proceedings of the 3rd International Conference on Anti－Counterfeiting，Security，and Identification in Communication［C］．IEEE Press Piscataway，NJ，USA，2009．