EPC C1G2防碰撞算法在RFID讀寫(xiě)器中優(yōu)越性的研究

朱葛俊

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

0 引言

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

1 基本的RFID防碰撞算法

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

1.1 幀時(shí)隙ALOHA算法（FSA算法）

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

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

1.2 二進(jìn)制樹(shù)形搜索算法

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

2 EPC C1G2防碰撞算法及仿真

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

2.1 算法概述

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

圖1 所需時(shí)隙數(shù)

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

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

2.2 算法性能仿真及比較

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

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

2.3 建立仿真程序

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

3 結(jié)束語(yǔ)

關(guān)于RFID 讀寫(xiě)器多標(biāo)簽沖突現(xiàn)狀，結(jié)合 EPC Class-1 Gen-2 標(biāo)準(zhǔn)中的讀寫(xiě)器與標(biāo)簽的通信指令，研究并實(shí)現(xiàn)了防沖突算法，從仿真結(jié)果可以看出EPC Gen2算法在標(biāo)簽識(shí)別效率及系統(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標(biāo)簽時(shí)鐘校準(zhǔn)方法[J].中國(guó)科學(xué)院研究生院學(xué)報(bào),2009,26(6)4.

[3] 周盛華,楊志超,吳南健,等.小面積低功耗RFID射頻前端電路設(shè)計(jì)[J].半導(dǎo)體學(xué)報(bào),2006,27(z1)4.

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