EPC C1G2防碰撞算法在RFID讀寫器中優越性的研究

朱葛俊

（常州機電職業技術學院 信息工程系，常州 213164）

0 引言

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

1 基本的RFID防碰撞算法

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

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

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

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

1.2 二進制樹形搜索算法

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

2 EPC C1G2防碰撞算法及仿真

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

2.1 算法概述

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

圖1 所需時隙數

圖2 系統吞吐率

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

2.2 算法性能仿真及比較

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

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

2.3 建立仿真程序

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

3 結束語

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

[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系統的Matlab/Simulink建模及特性分析[J].電訊技術,2006,46(5)4.