RFID中間件設計及抗碰撞算法優(yōu)化

王月瑩+湯錦茂+陳望玥+鄒文平

摘 要：在生產(chǎn)實踐中，發(fā)現(xiàn)RFID系統(tǒng)隨著標簽數(shù)量的增加，碰撞概率隨之提高，無法高效地識別標簽。為了在大規(guī)模使用RFID標簽的情況下提高抗碰撞性能，通過分析、建模、實驗，發(fā)現(xiàn)應用概率模型的識別概率曲線，可以從一次掃描獲得的識別標簽數(shù)反推外部的標簽規(guī)模，從而智能調整幀時隙數(shù)，降低碰撞概率。該方法能優(yōu)化RFID系統(tǒng)在大規(guī)模標簽中的識別效率，適用于物流領域中標簽數(shù)量很多的場景。

關鍵詞：射頻識別；電子標簽；RFID技術；RFID系統(tǒng)

DOIDOI：10.11907/rjdk.171898

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0036-03

0 引言

隨著科技的發(fā)展，RFID（Radio Frequency Identification，無線射頻識別）技術愈發(fā)成熟，其應用領域也日益廣泛。20世紀90年代，RFID作為一種非接觸式的自動識別技術在多個領域興起。RFID是一種相對簡單的無線系統(tǒng)，系統(tǒng)由兩個基本的器件組成，一個閱讀器和若干標簽（也稱應答器），可用于控制、跟蹤和檢測物體[1]。

由于RFID技術具有多目標識別、高速移動物體識別、非接觸識別等特點，因而其在生產(chǎn)、管理、信息傳送、信號識別等方面顯示出較好的發(fā)展?jié)摿涂捎每臻g，被認為是21世紀最具有發(fā)展前途的信息科學技術之一[2]。

RFID技術利用無線射頻信號，無需接觸就能自動識別物體，其識別率一直是影響它更大范圍應用的根本原因。針對此問題，本文重點研究如何改善RFID系統(tǒng)在大規(guī)模標簽環(huán)境中的識別效率及如何降低碰撞概率[3]。

1 系統(tǒng)設計

1.1 RFID技術工作原理

完整的RFID系統(tǒng)由如下4個部分組成：閱讀器（Reader）、電子標簽（Tag）即所謂的應答器（Transponder）、中間件（Middle Ware）及應用軟件系統(tǒng)（Application Software System）。工作原理如下：RFID閱讀器通過天線持續(xù)發(fā)送出特定頻率的射頻信號，當RFID標簽進入磁場即閱讀器射頻信號觸及工作場內，憑借感應電流所獲得的能量支持標簽發(fā)送存儲在芯片中所保存的約定格式的電子信息（Passive Tag，無源標簽或被動標簽），或者主動發(fā)送某一頻率的信號（Active Tag，有源標簽或主動標簽），隨后解讀器讀取信息并解碼后，將數(shù)據(jù)傳送至RFID中間件進行相關處理。RFID中間件是一種面向消息的程序模塊，利用高效可靠的消息傳遞機制進行平臺的數(shù)據(jù)交互，信息以消息的形式傳遞，從RFID硬件控制程序主動通過同步或異步的傳輸方式將信息傳送至上層的應用程序。RFID中間件對接收的數(shù)據(jù)進行相應的處理后送至中央計算機系統(tǒng)進行相關數(shù)據(jù)處理[4]。

1.2 RFID中間件設計

RFID中間件是介于RFID閱讀器與應用系統(tǒng)之間的、用于處理和管理RFID數(shù)據(jù)的平臺[5]。在RFID閱讀器和應用系統(tǒng)之間，RFID中間件起到中介作用，閱讀器通過在應用程序端使用RFID中間件提供的一組應用程序編程接口（API），實現(xiàn)對RFID電子標簽數(shù)據(jù)的讀取和各類參數(shù)的設置及寫入功能。在復雜的網(wǎng)絡計算機系統(tǒng)環(huán)境中，中間件與各種分布對象有機地結合在一起，交互通訊完成系統(tǒng)快速高效的運作，實現(xiàn)對象的重用，提高生產(chǎn)效率，降低軟件開發(fā)成本。有了中間件的支撐，在應用軟件中用到中間件對應的功能時，不需要應用端開發(fā)人員自己實現(xiàn)，可直接利用中間件將其中已經(jīng)實現(xiàn)好的功能快速集成到應用軟件系統(tǒng)中，使不同操作系統(tǒng)和各種應用程序間無縫連接成為可能。即使RFID硬件升級和改變，應用端不需修改，通過改寫中間件就能適應硬件的升級，減小了系統(tǒng)運行維護的工作量。

1.3 RFID中間件架構設計

RFID中間件的主要功能之一是對傳輸?shù)臄?shù)據(jù)進行處理和分析，為上層應用提供決策支持[6]。為了改善大規(guī)模使用RFID標簽環(huán)境中的識別效率，系統(tǒng)通常使用高頻掃描儀器，當RFID閱讀器掃描范圍內出現(xiàn)一張RFID標簽時，為了保證漏讀率趨近于0，會對其進行上百次掃描。但是這種掃描方式也使系統(tǒng)中產(chǎn)生了大量的冗余數(shù)據(jù)，使用于傳輸數(shù)據(jù)的網(wǎng)絡費用成本上升，普通的網(wǎng)絡系統(tǒng)無法承擔這樣的負荷。同時處理大量的冗余數(shù)據(jù)會降低系統(tǒng)性能，從而出現(xiàn)存取速率降低、傳輸時間延長、查詢效率降低等問題。因此，中間件對傳感器捕獲到的數(shù)據(jù)進行過濾處理十分必要，具體操作方法是：丟棄錯誤數(shù)據(jù)、忽略無關數(shù)據(jù)、合并相同數(shù)據(jù)。

RFID數(shù)據(jù)壓縮方法一般可分為兩種：第一種為多媒體數(shù)據(jù)壓縮，多媒體數(shù)據(jù)壓縮以音頻文件、矢量圖像、彩色圖像、二值圖像等為處理對象；第二種為通用數(shù)據(jù)壓縮，通用數(shù)據(jù)壓縮包含了如LZW、LZ77和LZ78的基于字典模型的壓縮技術，也包含了如算術編碼和Huffinan編碼的基于統(tǒng)計模型的壓縮技術。經(jīng)過多年生產(chǎn)實踐改進和技術創(chuàng)新發(fā)展，位置壓縮（Location Compression）[7]和包壓縮（Containment Compression）成為目前主要的RFID壓縮方法。位置壓縮是指當多個RFID對象在相同位置停留超過一個讀取周期時，系統(tǒng)將自動把一系列數(shù)據(jù)壓縮成一個對象；包壓縮是指當多個帶有RFID標簽的對象同時在同一個容器內以整體的形式移動時，系統(tǒng)將以容器的標簽來表示容器內RFID對象的位置。受外圍周邊環(huán)境和射頻信號等原因的干擾和影響，RFID系統(tǒng)中數(shù)據(jù)讀取的過程中常出現(xiàn)漏讀、誤讀和重讀等現(xiàn)象。這些現(xiàn)象甚至成為制約RFID應用的重要因素，標簽一旦讀取錯誤，可能導致數(shù)據(jù)混亂，增加成本的消耗，亦可導致重大損失的發(fā)生。因此，系統(tǒng)中要增加一個環(huán)節(jié)對有效信息進行過濾，以保證讀取到的數(shù)據(jù)與實踐中的真實數(shù)據(jù)更加接近。對于以上問題，來自美國加州大學伯克利分校的學者提出一種基于概率模型的SMURF自適應數(shù)據(jù)清洗方法，用于改進中間件數(shù)據(jù)清洗模式，方法如下：將RFID標簽所產(chǎn)生的數(shù)據(jù)流看作統(tǒng)計學中的隨機事件，“事件”可以描述為“指示某種行為的信息”，通常信息的形式類似于消息，根據(jù)隨機事件概率的不同來調整窗口大小，提高了數(shù)據(jù)讀取的準確性。endprint

2 RFID抗碰撞算法

隨著電子標簽的縮小和識別距離的增長，在讀寫器工作場區(qū)域內中常出現(xiàn)大量的標簽等待讀卡器識別的問題，此時RFID中間件在設計時需要解決多標簽碰撞問題[8]，工作場景如圖1所示。標簽碰撞指在一個磁場即讀寫器的工作場內出現(xiàn)多個標簽憑借感應電流產(chǎn)生的能量同時響應閱讀器從而發(fā)送自身存儲信息，由于多個標簽同時向讀寫器發(fā)出信息而引起信號碰撞，最終導致讀寫器無法識別標簽，造成通信失敗，而發(fā)送失敗的標簽將會重復發(fā)送直到成功，嚴重影響系統(tǒng)效率，浪費通信時間，增加電子標簽與讀寫器的通信負擔，限制了RFID的推廣和發(fā)展。目前，如何降低RFID系統(tǒng)在大規(guī)模標簽環(huán)境中的碰撞概率是RFID研究中的難點[9]。

2.1 電子標簽工作狀態(tài)

要降低碰撞概率，必須先分析標簽的工作狀態(tài)。滿足EPC GEN2的標簽必須能夠實現(xiàn)就緒、仲裁、應答、確認、開放、保護以及滅活7個工作狀態(tài)。其中，與防碰撞相關的狀態(tài)包括就緒、仲裁、應答以及確認[10]。

使用一組適當合法的指令可以讓RFID標簽進入某種狀態(tài)，且命令只能當標簽在適當?shù)臓顟B(tài)下才能生效，標簽響應命令后將會轉入其它狀態(tài)。

2.2 抗碰撞算法

為了消除或減少RFID系統(tǒng)中的碰撞問題，相關學者提出了許多不同的抗碰撞算法，其中主要有二進制樹形搜索法和ALOHA法[11]。ALOHA算法屬于時分多址（TDMA）方式，其主要算法有P-ALOHA算法、純ALOHA算法、固定幀時隙ALOHA算法、時隙ALOHA算法、動態(tài)幀時隙ALOHA算法，是一種簡單基本的防碰撞算法。其中能優(yōu)化吞吐率較小的ALOHA法是時隙ALOHA法（SA算法）。SA算法是因為讀寫器能控制在同步時隙內傳送數(shù)據(jù)，有概率發(fā)生碰撞的時間區(qū)就減少了1/2，當G=1時，S上升為36.8%，但局限于只讀型電子標簽。另外一種擴展ALOHA算法是FSA算法，是在時隙ALOHA算法基礎上將N個時隙組成一幀，標簽在每幀內隨機選擇一個發(fā)送數(shù)據(jù)的時隙，適合應用于傳輸信息量較大的情況。FSA算法的特點是適用于較大的信息傳輸場合。但在標簽數(shù)量遠大于時隙個數(shù)的情況下，讀取標簽的時間將增加，在標簽數(shù)遠小于時隙個數(shù)情況下，就會造成時隙的浪費。在FSA算法中，當遇到始終有碰撞發(fā)生的情況時，要用到動態(tài)時隙ALOHA法，由于幀中的時隙個數(shù)N是動態(tài)產(chǎn)生的，其時隙可根據(jù)需要變化，從而解決了FSA算法中時隙在過多和較少碰撞時的浪費問題。當讀寫器

在工作時發(fā)現(xiàn)碰撞發(fā)生較多，就提供合理的時隙數(shù)，直到有唯一標簽的時隙為止，從而大大提高吞吐率。

2.3 數(shù)學模型分析

改良的FSA算法可以動態(tài)地改變下一次讀取循環(huán)中每一幀的時隙數(shù)N，N隨著閱讀區(qū)中標簽數(shù)目的增減而改變，這種算法稱為動態(tài)FSA算法，也叫DFSA算法。在輸入的負載率小于1時，動態(tài)時隙ALOHA算法能減少時隙數(shù)N從而節(jié)約標簽讀取時間和空間；在輸入的負載率大于1時，增加時隙數(shù)，減少幀中的碰撞數(shù)目，同時也避免單獨時隙中的標簽被識別的概率變小的情況[12]。

以杯子總數(shù)表示RFID讀卡器掃描周期中一幀中的時隙數(shù)，用球表示標簽，投球后剩余的空杯數(shù)表示讀寫器一次掃描閱讀后產(chǎn)生的空時隙數(shù)，進行數(shù)學建模，以此實現(xiàn)根據(jù)讀寫器一次閱讀后產(chǎn)生的空時隙數(shù)猜測標簽總數(shù)，從而動態(tài)調整下次閱讀的時隙數(shù)N。

F1（A，B，E）=CA-BA*HE-（A-B）A-B÷HEA 以50個杯子，50個球為例：總可能數(shù)：H=H5050=5.0446*1028；0個空杯：C5050=1；1個空杯：C4950*H149=C4950*H149，P=C4950*C149÷H；2個空杯：C4850*H248=C4850*C249，P=C4850*C249÷H；......n個空杯：C50-n50*Hn50-n=C50-n50*Cn49，P=C50-n50*Cn49÷H；（注：Hnm=Cnm+n-1，Cnm=m！n！*（m-n）?。?/p>

根據(jù)以上公式推導得到概率模型，繪制概率分布曲線如圖2所示。利用各種規(guī)模的杯、球概率分布曲線，就可以從一次閱讀時的標簽識別數(shù)來反推外界標簽的總數(shù)量，再采用DFSA算法，設置讀卡器的幀時隙數(shù)和外界標簽的規(guī)模數(shù)相等，此時RFID的讀卡器效率最高。

3 結語

通過對RFID中間件的設計，以及對抗碰撞算法的探討，推導了概率曲線，進行了仿真實驗，獲得了提高RFID中間件抗碰撞的方法。研究得到以下兩點結論：①推導了標簽識別和標簽規(guī)模相關性的數(shù)學模型，采用概率學方法對RFID標簽碰撞現(xiàn)象進行研究，實現(xiàn)通過已知識別數(shù)反推總標簽數(shù)量；②通過改變讀卡器幀時隙和外界標簽總數(shù)相匹配，將有效提高RFID系統(tǒng)在物流場景中大規(guī)模標簽環(huán)境下的識別效率。

參考文獻：

[1] 林宇洪.木材供應鏈追溯RFIC卡的設計[J].西北林學院學報，2013，28（5）：175-179.

[2] LIU HSIN-CHIN，CHEN YUNG-TING，TZENG WEN-SHIN.A multi-carrier UHF passive RFID systern[C].2007 International Symposium on Applications and the Internet Workshops（SAINT-W），2007：409-412.

[3] ZHENG SHIPU，YU FENGQI，ZHU YUESHENG.A novel RFID transceiver architecture with enhanced readability[C].2007 International Conference on Wireless Communications，Networking and Mobile Computing（WiCOM 2007），2007：2074-2077.

[4] SHARYN LEAVER.Evaluating RFID middleware[Z].Forrester Research，2004.

[5] 陳玲.基于RFID及GIS技術的煙葉物流管理系統(tǒng)研究[D].廈門：廈門大學，2013.

[6] 林宇洪，林敏敏，胡連珍，等.基于AT89C2051的木材供應鏈手持機的設計[J].中南林業(yè)科技大學學報，2017，37（3）：98-103.

[7] PARK H S，JUN C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications，2009，36（2）：3336-3341.

[8] 林宇洪，沈嶸楓，邱榮祖，等.南方林區(qū)林產(chǎn)品運輸監(jiān)管系統(tǒng)的研發(fā)[J].北京林業(yè)大學學報，2011，33（5）：130-135.

[9] SANJAY E，SARMA，STEPHEN A.White paper：RFID system，security&privacy implications[Z].AUTO-ID CENTER，2003.

[10] WANG L C，YANG BOYIN，HU YUHUA，et al.A medium-field multivariate public key eneryption scheme[C].Proc.of CT-RSA06，Berlin，Germany；Springer-Verlag，2006：132-149.

[11] MYUNG JIHOON，LEE WONJUN，SRIVASTAVA JAIDEEP.Adaptive binary splitting for efficient RFD tag Anti-collision[J].IEEE Communications Letters，2006，10（3）：144-146.

[12] 林宇洪，陳清耀，邱榮祖.基于K-means聚類的木材運輸行為的可視化監(jiān)管[J].青海師范大學學報：自然科學版，2016，32（1）：54-59.endprint