汪國強(qiáng)，趙 璐，鄭 東

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

0 引 言

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

RFID系統(tǒng)工作時(shí)經(jīng)常會(huì)有這樣一種情況出現(xiàn)，多個(gè)電子標(biāo)簽存在于閱讀器的工作范圍內(nèi)，多個(gè)使用者共同使用一個(gè)無線信道，必然會(huì)發(fā)生信道爭搶、信息干擾等問題，最終導(dǎo)致電子標(biāo)簽無法被閱讀器識(shí)別，這種情況稱之為發(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)、銷售、貨運(yùn)等需要準(zhǔn)確實(shí)現(xiàn)多目標(biāo)識(shí)別的領(lǐng)域時(shí)，由于碰撞造成數(shù)據(jù)的錯(cuò)誤傳輸，信息讀取無法正常進(jìn)行，最終導(dǎo)致產(chǎn)品識(shí)別的失敗，以及產(chǎn)品信息的丟失，造成的后果會(huì)更嚴(yán)重。因此，解決碰撞問題的技術(shù)也就成為RFID系統(tǒng)中的一項(xiàng)至關(guān)重要的技術(shù)，由此可知對于碰撞問題的深入研究是非常有必要的。

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

現(xiàn)在如何提高RFID系統(tǒng)的工作效率成為該技術(shù)發(fā)展的一個(gè)核心話題，為此本文對幀時(shí)隙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）算法稱為幀時(shí)隙ALOHA算法［4］，也可以稱為固定幀時(shí)隙ALOHA算法，這種算法是在純ALOHA算法的基礎(chǔ)上進(jìn)行改進(jìn)的一種算法，這種算法把N個(gè)時(shí)隙綁定成一組形成一幀，其大小在電子標(biāo)簽識(shí)別過程中是固定的，并且?guī)忻總€(gè)時(shí)隙的長度都能保證標(biāo)簽、閱讀器之間完成正常的通信過程，然后在一幀內(nèi)任意選擇一個(gè)時(shí)隙進(jìn)行標(biāo)簽數(shù)據(jù)的發(fā)送。這種算法適合用于傳輸標(biāo)簽數(shù)量相對較大的場合。

幀時(shí)隙ALOHA算法的過程：當(dāng)電子標(biāo)簽進(jìn)入閱讀器的工作范圍時(shí)，閱讀器把幀內(nèi)時(shí)隙數(shù)N發(fā)送給標(biāo)簽，標(biāo)簽本身產(chǎn)生一個(gè)隨機(jī)數(shù)m （m≤N），并根據(jù)自己的隨機(jī)數(shù)選擇時(shí)隙，當(dāng)時(shí)隙數(shù)與m值相等，并且只有一個(gè)標(biāo)簽響應(yīng)，則通信成功，多個(gè)標(biāo)簽響應(yīng)就會(huì)發(fā)生碰撞，沒有響應(yīng)就是空閑狀態(tài)；當(dāng)時(shí)隙數(shù)與m值不相等時(shí)，標(biāo)簽就繼續(xù)等待。因此，在整個(gè)的通信過程中閱讀器會(huì)接收到標(biāo)簽的3種應(yīng)答：成功時(shí)隙、空時(shí)隙、碰撞時(shí)隙。假設(shè)在標(biāo)簽發(fā)送信息的過程中一切的干擾都忽略不計(jì)，信息幀的長度為FL，那么，當(dāng)閱讀M個(gè)標(biāo)簽時(shí)幀內(nèi)成功時(shí)隙數(shù) （S）、空閑時(shí)隙數(shù) （B）、碰撞時(shí)隙數(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左右時(shí)，系統(tǒng)的識(shí)別率最高，正確率最高，約為36．8%；圖1（b）中橫坐標(biāo)代表標(biāo)簽的數(shù)量，縱坐標(biāo)代表系統(tǒng)的識(shí)別率，3條曲線中FL分別為32、128、256，由圖中可以看出當(dāng)標(biāo)簽數(shù)量接近幀長度時(shí)系統(tǒng)的正確率最高約為36．8%，并且隨著標(biāo)簽的數(shù)量的增加，正確率有一定的衰減，這樣的結(jié)果與圖1（a）中結(jié)果是一致的。因此，得到結(jié)論，固定幀時(shí)隙算法當(dāng)標(biāo)簽數(shù)量和幀長度相等時(shí)效率最高約為36．8%。

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

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

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

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

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

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

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

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

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

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

3 混合算法

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

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

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

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

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

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

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

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

3．2 算法描述

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

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

圖4是混合算法與二進(jìn)制搜索算法、FSA算法的軟件仿真結(jié)果比較，由圖4可見，采用改進(jìn)算法的系統(tǒng)效率由原來最高0．368提高到最高為0．52，而且當(dāng)標(biāo)簽數(shù)量很大時(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)行識(shí)別的一種改進(jìn)型算法。這種算法很好地改善了系統(tǒng)的工作效率問題，即使當(dāng)閱讀器范圍內(nèi)有很大數(shù)量的標(biāo)簽時(shí)，也能很好地解決碰撞問題。

在RFID系統(tǒng)通信過程中，碰撞問題是需要解決的重要問題，同時(shí)碰撞也是影響一個(gè)系統(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．