朱葛俊

（常州機電職業(yè)技術(shù)學院 信息工程系，常州 213164）

0 引言

EPCClass-1Gen-2標準所采用的是時隙隨機防沖突算法（SR算法），這種算法有著自己獨特的優(yōu)越性， SR算法可以根據(jù)標簽時隙的分布情況隨時令標簽在下一輪的幀循環(huán)操作中進入，這樣就避免了必須等這一幀中的時隙全部處理完畢的現(xiàn)象[1]。SR算法與其他動態(tài)幀時隙ALOHA算法有很大的相似之處，其算法能夠更加靈活地對大小進行調(diào)整，來促使其在通信次數(shù)與吞吐率上的優(yōu)越性。

1 基本的RFID防碰撞算法

在一個閱讀器內(nèi)存在很多標簽是不可避免的，為了能正確的區(qū)分這些相同的標簽，RFID的防碰撞算法協(xié)議就起到了作用，一般情況下，防碰撞算法主要包含兩種形式，一種是二進制的樹形搜索算法，另一種是時隙的隨機防沖突算法，兩種算法各自有著各自的特點。

1.1 幀時隙ALOHA算法（FSA算法）

時隙ALOHA算法（SA算法）是閱讀器控制驅(qū)動的方法，它把時間分為離散的時隙，同時必須有全局的時間同步。與簡單的ALOHA法相比，時隙ALOHA法可能出現(xiàn)的碰撞的時間只有前者的一半。FSA算法在SA算法基礎上，把每個時隙進一步分割成若干時隙并打包成幀。標簽在幀內(nèi)只隨機發(fā)送一次信息包，故該算法進一步降低了碰撞的機會。該算法中幀時隙的長度是固定的，而實際應用中電子標簽的數(shù)量未知且動態(tài)變化。因此其缺點是如果標簽數(shù)遠遠多于固定的時隙數(shù)，會產(chǎn)生過多碰撞；反之，會產(chǎn)生較多空閑時隙，造成資源浪費。

動態(tài)幀時隙ALOHA算法（DFSA算法）對FSA算法又做了進一步的改進，DFSA算法應用于當FSA算法始終遇到有碰撞發(fā)生時。閱讀器在等待狀態(tài)中的循環(huán)時隙段內(nèi)發(fā)送請求指令，該指令使工作狀態(tài)的電子標簽同步，然后提供1個或2個時隙給電子標簽使用，電子標簽將選擇自己的傳送時隙，如果在這1或2個時隙內(nèi)有較多電子標簽發(fā)生了數(shù)據(jù)碰撞，則閱讀器就用下一個請求指令增加可使用的時隙數(shù)，直至碰撞消失，從而大大提高了吞吐率。該算法由于操作簡單和性能良好而成為目前最常用的算法之一。其特點是：幀的時隙數(shù)是動態(tài)產(chǎn)生且可變的，解決了FSA算法中時隙的浪費問題，但在標簽數(shù)量很多、發(fā)送時隙受限時，DFSA算法幾乎顯示不出其優(yōu)越性。

1.2 二進制樹形搜索算法

二進制樹形搜索算法比較復雜，識別時間較長。在基于序列號的方式中需要電子標簽具有唯一標示符以保證識別，同時閱讀器所使用的信號編碼應能準確確定碰撞的比特位置；在基于隨機數(shù)和時隙的方式中要求應答器中有一個隨機數(shù)產(chǎn)生器。該方法采用遞歸的工作方式，遇到碰撞就分解成兩個子集。這些分支越來越小，直到最后分支下面只有一個信息包或者為空。當所有發(fā)生碰撞的信息包都被成功識別和傳輸后，碰撞問題即得解決。

2 EPC C1G2防碰撞算法及仿真

EPCGen2協(xié)議是超高頻第二代空中接口標準射頻識別協(xié)議。其防碰撞算法本質(zhì)上是動態(tài)幀時隙ALOHA算法，這種算法可以隨意的動態(tài)調(diào)整每一幀中的時隙數(shù)量，并且可以根據(jù)標簽中時隙的分布情況隨時進行下一個指定來進入下一個循環(huán)操作，這就避免了要等上一輪循環(huán)完成以后才可進行指令的弊端。此算法中的防碰撞機制是通過Q參數(shù)控制幀的長度，然后根據(jù)讀取過程中的讀取結(jié)果進行實施調(diào)整，在一個識別周期內(nèi)隨時更改時隙數(shù)，讓未識別標簽重新選擇，實現(xiàn)了時隙數(shù)的自適應過程。

2.1 算法概述

在EPC Class1Gen2的空中接口協(xié)議中，防碰撞算法通過Query，QueryAdjust，QueryRep等指令完成，這種算法是通過閱讀器發(fā)送的Query指令，然后開始第一輪的盤點周期，這期間包含了一個參數(shù)Q，也就是說該幀有2Q個時隙，Q初始值為4。任何一個標簽收到此指令后便會產(chǎn)生0～2Q-1之間的隨機數(shù)來作為應答時隙，然后通過隨機時隙計數(shù)器將其載入，時隙計數(shù)器中的時隙為0的標簽向閱讀器發(fā)送RN16作為應答信息，這時閱讀器發(fā)送Query指令，然后對其進行檢測RN16的碰撞情況，如果沒有遇到碰撞情況，閱讀器便很順利的識別出該標簽并發(fā)送ACK指令。如果遇到碰撞現(xiàn)象就會發(fā)出NAK，標簽這時接到ACK指令后發(fā)出不參與余下過程的指令。如果遇到標簽沒有向閱讀器發(fā)送RN16，這說明所有標簽可以從新選擇應答時隙，標簽時隙可以減1來減少Q(mào)值，這樣就可以使得標簽時隙0的幾率大大增加，當遇到標簽發(fā)送RN16的時候，這說明標簽遇到了沖突，這時候閱讀器可以把標簽時隙減1，增加Q值來擴大標簽的隨機選擇時隙，進而實現(xiàn)減少和避免沖突的概率，這樣通過動態(tài)的調(diào)整Q值來實現(xiàn)的標簽的時隙進行數(shù)據(jù)傳輸，此時閱讀器既可以使所有標簽的時隙減1（發(fā)送QueryRep指令），也可以通過減少Q(mào)值（發(fā)送QueryAjust指令）的方法令所有標簽重新選擇應答時隙，這樣便可以使標簽的時隙為0的概率增大；如果有多于一個的標簽向閱讀器發(fā)送了RN16，這時便產(chǎn)生了標簽間的沖突，此時閱讀器既可以使所有標簽的時隙減1（發(fā)送QueryRep指令），也可以增大Q值（發(fā)送QueryAjust指令）使標簽在更大的范圍內(nèi)隨機選擇時隙，從而減少發(fā)生沖突的概率。閱讀器通過動態(tài)調(diào)整Q值從而調(diào)節(jié)各個標簽的時隙，使得標簽分別占用不同的時隙與閱讀器進行數(shù)據(jù)傳輸進而實現(xiàn)防碰撞的算法[2]。

圖1 所需時隙數(shù)

圖2 系統(tǒng)吞吐率

Q值的大小會使得隨機時隙的大小變化，大的Q值可以減少沖突，但是要增加空閑時隙，小的Q值會增加碰撞幾率，但是會減少空閑。過多的空閑時隙會降低識別效率，產(chǎn)生識別效率降低的現(xiàn)象，因此，要在閱讀器的時隙狀況實施調(diào)整的狀態(tài)下，才能使標簽的取值范圍更好。

2.2 算法性能仿真及比較

FSA算法、二進制樹搜索算法及EPCGen2算法的性能分別用matlab進行仿真并進行了比較，如圖1及圖2所示。

當標簽數(shù)超過600時，F(xiàn)SA算法識別標簽所需的時隙數(shù)呈現(xiàn)大幅增長的趨勢。FSA算法的系統(tǒng)吞吐率較低且吞吐穩(wěn)定性差。FSA算法適合于識別數(shù)量在600個以內(nèi)的電子標簽，且在識別效率上與其他兩種算法相比存在一定差距。二進制樹搜索算法的時隙數(shù)與標簽數(shù)呈線性關(guān)系，識別標簽所需的時隙數(shù)介于其他兩者之間，系統(tǒng)吞吐率差。EPCGen2算法的最大時隙數(shù)可達215，實際中即使識別大數(shù)量的標簽也不會受到時隙數(shù)限制。采用EPCGen2算法系統(tǒng)吞吐率最高且保持在一個穩(wěn)定值附近。在識別大數(shù)量標簽時，EPCGen2算法識別標簽所需要的時隙數(shù)比其他兩種算法少很多，識別速度快。EPCGen2算法相對復雜，適合識別大數(shù)量電子標簽[3]。

2.3 建立仿真程序

選擇Excel2007作為仿真計算軟件，首先建立一個標簽類CTag，用于進行仿真標簽的行為，數(shù)據(jù)成員分別用槽值表示和用“未響應”、“沖突”和“成功”三種狀態(tài)來表示，閱讀器調(diào)用前三個方法查詢標簽，調(diào)用第四個方法把標簽設為沖突狀態(tài)。Query和QueryAdjust需要的隨機數(shù)可利用Excel2007的新增函數(shù)RandBetween生成，來自動選擇函數(shù)的順序。然后建立一個閱讀器類CReader，該類主要包含三個方法Select、Inventory和AdjustQ，來進行仿真閱讀，其中Select用于設置標簽數(shù)量，并生成對應的標簽對象數(shù)組。Inventory用于清點所有標簽。該方法首先調(diào)用所有標簽的Query方法，然后重復調(diào)用QueryRep或QueryAdjust方法。如果中途發(fā)現(xiàn)有多個標簽的槽值為0，則調(diào)用Collide方法，體現(xiàn)并記錄沖突，AdjustQ是私有方法，僅由Inventory方法調(diào)用，用于每次查詢后根據(jù)適當條件調(diào)整標簽的Q值。目標的變化后文將實現(xiàn)兩個版本的AdjustQ方法。退出清點循環(huán)的判斷條件為：在某一Q值下連續(xù)執(zhí)行2Q次查詢都沒有發(fā)生沖突。Q選擇算法執(zhí)行過程中，標簽與Q值得減少為結(jié)束條件對整體效率的影響較小。但是當標簽較少，而Q的初值較大時，需經(jīng)多次查詢，Q值才能減小到合適的程度，因此Q的初值應較小，一般可取不大于3的值[4]。

3 結(jié)束語

關(guān)于RFID 讀寫器多標簽沖突現(xiàn)狀，結(jié)合 EPC Class-1 Gen-2 標準中的讀寫器與標簽的通信指令，研究并實現(xiàn)了防沖突算法，從仿真結(jié)果可以看出EPC Gen2算法在標簽識別效率及系統(tǒng)吞吐率上的優(yōu)越性。

[1] Ki Yong JEON,Sung Ho CHO.A R fid Epc C1 Gen2 System With Channel Coding Capability In Awgn Noise Environments [J].IEICE Transactions on Communications,2009,e92/b(2)_4.DOI:10.1587/transcom.E92.B.608.

[2] 羅恰嗣,郭立,周云超,等.一種EPC Gen2 RFID標簽時鐘校準方法[J].中國科學院研究生院學報,2009,26(6)4.

[3] 周盛華,楊志超,吳南健,等.小面積低功耗RFID射頻前端電路設計[J].半導體學報,2006,27(z1)4.

[4] 鐘學毅,呂寧,王昌明,等.RFID系統(tǒng)的Matlab/Simulink建模及特性分析[J].電訊技術(shù),2006,46(5)4.