汪國強，趙 璐，鄭 東

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

0 引 言

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

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

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

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

1 FSA算法

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

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

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

2 二進制搜索算法

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

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

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

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

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

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

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

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

圖3 二進制搜索算法仿真圖Fig．3 Simulation result of binary search algorithm

3 混合算法

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

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

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

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

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

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

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

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

3．2 算法描述

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

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

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

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

4 結(jié) 論

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

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

［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．