基于馬爾科夫鏈的射頻識別防碰撞測試*

侯周國 何怡剛 李 兵

1)(湖南大學電氣與信息工程學院，長沙 410082)

2)(湖南人文科技學院通信與控制工程系，婁底 417000)

(2009年10月12日收到;2010年5月5日收到修改稿)

基于馬爾科夫鏈的射頻識別防碰撞測試*

侯周國1)2)?何怡剛1)李 兵1)

1)(湖南大學電氣與信息工程學院，長沙 410082)

2)(湖南人文科技學院通信與控制工程系，婁底 417000)

(2009年10月12日收到;2010年5月5日收到修改稿)

分析了自適應Q值算法的防碰撞原理以及射頻識別(RFID)通信的時序，定義防碰撞過程的識別效率、識別速度和標簽數目及Q值的數據狀態(Q，n).在此基礎上討論并建立了多標簽的狀態轉移過程的馬爾科夫鏈模型.通過蒙特卡羅統計方法，對馬爾科夫鏈模型求解，得出識別效率和識別速度.用軟件無線電測試方案實現防碰撞測試，有效地實現了RFID防碰撞過程的識別效率和識別速度的量化分析.模型仿真結果和測試數據的一致證明了測試模型的有效性和測試方法的正確性.

射頻識別，防碰撞測試，馬爾科夫鏈，時隙計數器

PACS:52.70.Gw，06.90.+v

1.引 言

射頻識別(RFID)技術提供了一種自動識別和收集目標對象信息的高效且低成本的手段.RFID系統包括標簽和讀寫器，由貼附在物體上的電子標簽通過無線信道向讀寫器傳輸其惟一的標識字符串(ID)，讀寫器對此ID進行識別并可進一步讀寫操作，完成對標簽貼附目標的信息識別和記錄［1］.對超高頻RFID應用的推廣，其挑戰之一是提高多標簽情形下防碰撞算法的系統效率和速度，提高效率和減少識別時間是 RFID走向實用的關鍵［2，3］.目前RFID防碰撞的研究多為改進各種ALOHA算法和Tree算法，有效地提高防碰撞效率［2—6］.ISO18000-6C(簡稱-6C)協議標準采用的ALOHA算法，通過調整時隙數來有效減少碰撞概率，但標簽或讀寫器數目增大時，碰撞概率提高，識別效率降低，識別時間飛速增長［2，4］.因此有效調整 Q值是提高效率的關鍵，同時需要依賴解碼性能、信號捕獲能力以及散射功率等［5］.人們對防碰撞算法進行討論，分析標簽應答的三種狀態的時序關系，通過調整時隙來減少碰撞概率［5，7—9］，理論估計各算法的效率，但缺乏對RFID系統性能的具體測試結果，沒有解決防碰撞性能的量化分析和測試.

為了有效地對射頻識別系統的性能進行分析和測試，本文提出采用馬爾科夫鏈模型來量化系統的識別效率和識別速度，并結合虛擬儀器技術實現對防碰撞過程的效率測試.首先介紹了-6C協議規定的動態時隙參數自適應Q值算法［10］，分析系統的通信時序，指出標簽在每一幀中選擇時隙滿足二項分布隨機過程，并定義了標簽數目和時隙參數Q的變化數據對狀態(Q，n)，在此基礎上討論并建立數據對狀態(Q，n)轉移過程的馬爾科夫鏈模型，有效地模擬Q值調整過程，以提高系統識別效率.通過定義防碰撞過程的識別效率和識別速度，給出了馬爾科夫鏈模型的求解過程.通過對識別效率和識別速度的分析，結合軟件無線電測試理論，利用具有良好解碼性能、信號俘獲能力的射頻識別測試系統［11］進行測試，有效地實現了 RFID的識別效率和識別速度的量化，測試的系統效率優于查詢樹(QT)、改進查詢樹(QTI)等算法［9］的結果.

2.自適應Q值算法

2.1.標簽盤存時序

-6C規定了標簽盤存可由多個盤存周期組成.盤存周期以Query開始，以隨之Query或Select命令止.“盤存”規定了三條查詢指令:Query，QueryAdjust和 QueryRep，本文用 Query(含 Query，QueryAdjust(Adj)，QueryRep(Rep))指代.Query編碼位中含有4 bits時隙參數(Slot Count，SC)Q，即 0≤Q≤15.由Seletc所激活的標簽群，在 Query發出后在［0，2Q－1］間隨機選取一個數值并載入其SC.Adj指令用來在盤存周期中調整 Q 值［5，10］.

標簽識別過程的時序如圖 1 所示［1，5，10］.其中Tqj可分別表示 Query，Adj，Rep三指令的發送時長(用 Tq1，Tq2和 Tq3表示).用 Tid，Tc，Ts分別表示空閑、碰撞、成功識別的時間長度.

圖1 RFID通信時序圖

其中:Tidj=Tqj+T1+T3;Tcj=Tqj+T1+Trn+T2;Tsj=Tqj+2(T1+T2)+Trn+Tack+Tepc;j=1，2，3 分別對應為 Query，Adj，Rep三條指令的各自操作時序.

2.2.自適應Q值算法

基于動態幀時隙ALOHA算法的Q值算法如圖2 所示［1，10］，動態調整 Q 值可以減少碰撞概率.圖中用浮點數 Qfp來代表 Q值，將其四舍五入為整數 Q值.C為一個調整參數，取0.1

定理 在較長時間情形下，Q值+1(或－1)和Q不變的概率分別為C和1－C.

3.性能分析

系統識別效率可用來衡量各種防碰撞算法的效果，定義為讀寫器發送Query指令中成功識別標簽次數與發送總次數之比;識別速度是另一個評價算法效果的參數，定義為總的成功識別次數與總的時長之比［4］.現假設信道是理想的，標簽識別過程由一系列(K個)的盤存周期組成.則第i個盤存中，發送了Yi條 Query指令，Xi為在第i個盤存內被成功識別的標簽數(Xi≤Yi)，Ti為該盤存周期的時間長度(1≤i≤K)，定義Rsr表示一條Query可能識別一個標簽，也最多識別一個標簽的概率;Tis表示在給定時間內及足夠多標簽的情形下讀寫器識別標簽的速度，Rsr為讀寫器質量的參考因素，Tis與Rsr緊密相關.Rsr和 Tis主要依賴防碰撞分解算法的效率，但同時也受標簽數目、天線之間的距離、背景噪聲、標簽的貼附物體等的影響［4，8］.

圖2 自適應Q值算法

設當前盤存周期的 Q值為q，待識別標簽數為N，用(q，N)數據對表示.若干條 Query指令發送后，剩余的待識別標簽數為 n(0≤n≤N)，n=0表示標簽都被識別，n=N表示沒有標簽被識別.持續發送Query指令，(q，n)的變化為標簽識別與否的依據.在每一條Query指令后，Q值在原來的基礎上可加1，減1或保持不變，而 n值從 N開始或保持不變，或減1.在多個標簽時Q值的變化會出現前述五種情形，結合前述定理可得(2)式，其中 pi(q，n)，pc(q，n)，ps(q，n)分別表示在(q，n)狀態下發送一個Query指令后出現空閑、碰撞和成功識別的概率［2，12］，滿足 pi(q，n)+pc(q，n)+ps(q，n)=1，且

3.1.模型分析

在RFID的典型應用環境下，每個盤存周期中可能出現的標簽數目不確定，需要讀寫器首先估計激活標簽的數目，然后讀寫器自動調整Q值，再次給激活的標簽隨機賦值，每幀中出現碰撞、空閑和成功識別三種情形.下一幀識別出的標簽數目(0或1個)由當前幀時的q值和標簽數量n決定，而與先前幀所識別出的標簽數量無關，可用馬爾科夫鏈來分析此過程［12，13］.

Adj和Rep指令必須在Query開始的盤存周期內，Adj用來直接調整Q值，Rep反復調整 SC值，結合2.1節中的三種模式，做如下假設:

1)空閑時，若 Q值改變，則是讀寫器發送了一條Adj指令(標簽重新選 SC)，若 Q值保持不變(Q=round(Qfp))，則是發送了 Rep指令，SC=SC－1;

2)碰撞時，發送Adj指令，以便讓標簽重新選擇SC值，因為這更能有效地提高讀寫器解決碰撞的效率.若碰撞后仍發 Rep，則 SC=SC－1，同樣有較大概率出現碰撞而降低效率;

3)成功識別，設讀寫器重新發送Adj指令，Q不變，調整SC值.

Query指令的發送過程是一馬爾科夫鏈過程.設剩余標簽數為 n(0≤n≤N)，q值滿足0≤q≤15.設初始狀態為(Q0，N)，經過有限步后到達(q，0)，可得到如圖3所示的轉移圖.狀態轉移到次態有四種可能{(q，n)，(q －1，n)，(q+1，n)，(q，n －1)}，在特殊情形下(q=15，q=0或n=1)次態只有三種甚至兩種(q=0且 n=1).從現態(q，n)到次態(q′，n′)只與當前的狀態有關而與過去的狀態無關，(q′，n′)表下一幀后標簽數量的變化由當前狀態所處幀過后識別出標簽的數量決定，且當前狀態轉移到下一狀態的轉移概率是可確定的，與前面的幀中所識別出的標簽數量無關，此過程是馬爾科夫鏈過程［12］.圖中各轉移概率分析如下.

1)1

2)1

3)1

4)n=1且0

5)n=1且q=0，不會發生碰撞，q值保持不變.識別(Es):(q，n －1)←(q，n)，轉移概率為 P4;空閑(Ei0∪ Ei1):(q－1，n)← (q，n)，轉移概率為 P8=P(Ei)=pi(q，n).

6)n=0，則所有標簽都識別完成，此存盤周期結束.

根據前述分析，其一步轉移概率P(q，n)在不同的狀態間雖有所不同，但若只對n來說，轉移是單向的(n只能不變或者減小)，一步轉移概率為

3.2.模型求解

標簽接收到第一條(k=1)指令為 Query，開始盤存周期，其一幀中共有 L=2q個時隙，n=N，標簽隨機選擇一個時隙參數是符合二項分布的隨機過程［2］.選擇 SC=0的標簽數為1，0以及1個以上的概率分別為 ps，pi，pc，則

可以推出N較大的情形下，讀寫器發第k(k≥1)條Query 指令后其各自的概率近似為［2，8］

盡管(5)式為近似值，且在N較大情形下獲得，但是在此近似基礎上的效率和速度測試與仿真結果一致.(5)式的數學期望為標簽數目和時隙數相等獲得最大效率［12］.識別時標簽數目遞減，采用Q值算法，自動更新q值，以期獲取最大吞吐量.

3.3.計算 Rsr和 Tis

由(3)式知道圖3的轉移概率僅依賴pc(q，n)，ps(q，n)，pi(q，n)，結合(5)式分別算出 P1—P8.設初態(4，N)到末態(q，0)共經過 NN步，NN直接決定了RFID系統的效率.在2.2節中定義了5種識別情形，采用蒙特卡羅方法對一個盤存周期中的總步長數進行求解［8，14］.

步驟 1 設 Mi0，Mi1，Mc0，Mc1，Ms五個變量為空閑(q不變或－1)、碰撞(q不變或 +1)以及識別成功五類事件發生的次數且均初始化為0，Q0=4，初始狀態(q，n)=(Q0，N)，C 為常數.

步驟 2 計算 pi(q，n)，ps(q，n)，pc(q，n).由隨機數生成器隨機在［0，1)范圍內均勻分布地產生一個隨機數Ra，那么次態就由此隨機數 Ra和前面定義的五類標簽識別事件的發生概率來決定.

步驟3 令 q′=max(0，min(15，q));如果 n′=0，結束;否則，以(q′，n′)為初態，返回步驟 2，見圖 4.

當讀寫器沒有接收到應答且q不變時，讀寫器發送Rep指令;僅在盤存周期開始時發送 Query，而

其他狀態發送 Adj指令.那么一個盤存周期中，Query出現的次數Nq1=1;Adj出現的次數為Nq2=Mi1+Mc0+Mc1+Ms－1，而 Rep出現的次數 Nq3=Mi0，因此一個盤存周期中總的 Query指令數為 NN=Nq1+Nq2+Nq3，Rsr=N/NN，Tis=N/Ttotal.其中

其中 Ts，Tc，Tid分別為識別、碰撞、空閑時的平均通信時長，有

應用馬爾科夫鏈模型做統計分析時，假設閱讀器若能獲取RN16就能對標簽進行解碼，與讀寫器需要正確獲取ID的情形有區別，因此實際操作中有個別誤判現象，即獲取RN16但無法正確獲取ID，可通過提高信噪比來降低統計誤差，因此對統計結果影響不大.當N較大時，Query指令發出后，每幀信道內均有較大概率出現碰撞，而當標簽數目很小時，碰撞概率降低，不影響前面分析的結果.模型中因只簡單統計Query指令及其響應時長，而非讀寫器、標簽之間完整的通信時長(不含Req_RN及其他讀寫操作)，因此本文定義的識別速度與實際意義上的識別速度方面有差異，且實際產品的讀取效率和速度比模型結果要低.采用馬爾科夫鏈模型進行標簽統計識別，其計算過程效率高，其通信用的總的時隙數與標簽數目基本呈線性關系［14］.

4.實驗測試

用軟硬件模擬讀寫器，且收發天線分置，通過上行天線把載波和基帶信號(含參數Q)發送出去，標簽激活后應答，由下行信道把應答(RN16，EPC等)送回讀寫器.實驗測試系統主要由 NI公司的PXI-PCIe8361控制器，PXI-5600射頻下變頻模塊(RF DC)，PXI-5610射頻上變頻模塊(RFUC)以及PCI-5640R板載 FPGA模塊(IF RIO)等組成［11］.

設在K=100個盤存周期內，每個周期在N個標簽全部識別后再進入下個新的周期，統計出每個盤存周期中發送的指令數Yi(等于 NN)和所用時間.根據(1)式，在所有 K個周期內的識別率 Rsr和識別速度Tis分別為

Ttotal，i由(7)式計算，i表示第 i個盤存周期.根據PIE編碼原理，設置相關參數見表1.

表1 18000-6C的部分編碼參數［10］

仿真過程中，假設信道為理想信道，設標簽應答都能被讀寫器成功區分.我們設定每個盤存周期的N數是變化的，N以10為步長從10增加到1000，恰好有100個盤存周期，選擇 Q0=4，參數 C可在0.1到0.5之間變化.根據(7)—(9)式，按圖1所標時序，結合防碰撞的馬爾科夫過程，對多標簽情形 Rsr和 Tis進行計算和仿真，得到 Rsr和 Tis如圖 5所示.

在圖5(a)中，對C=0.4和0.2時以及 QT和QTI的識別效率進行了對比.由圖5(a)可知，采用馬爾科夫鏈模型得出的 Rsr最終趨近30%，C值的設定對于其影響不大且識別率出現交錯，而QT和QTI算法的識別效率分別為25.5%和29%［9］，低于本文模型的結果.采用本文的模型得到的Rsr隨標簽數目的增加有所降低，但當標簽超過200個時，Rsr基本保持平穩.Rsr接近30%，說明在多標簽情形下，指令的“有用”率約為30%.圖5(b)是對Tis的仿真，當 Tari值增大時，識別速度降低，且基本成反比關系，說明 TRrate對識別速度有很大影響，且在標簽數目超過100個后，Tis值穩定.Tis最大約為700，與-6C協議設想的讀取速度是符合的［5］.Tis并不表示讀寫器每秒能夠對 700個標簽進行完全讀寫，只完成發送ACK指令后接收EPC，整個識別過程也許有后續其他指令，識別速度就會降低.結果表明采用較小的 Tari值，數據傳送速度提高，有助于加快RFID系統的標簽識別速度.采用馬爾科夫鏈模型模擬碰撞過程，發現其碰撞、空閑的時隙數隨標簽數目的增加基本呈線性增加，且總的時隙約為標簽數目的三倍(見圖6)，所得結果略高于文獻［14］所得的結果，整個過程的計算效率高，易于實現.

按照圖1所標的時間序列，在讀寫器天線的足夠功率的定向輻射場范圍內(1 m半徑的60°扇形區域)，共放置20個 Alien公司的 ALN-9640標簽，軟件模擬讀寫器發送Query指令，可得到如圖7所示的波形.圖7表示通信鏈路時序波形圖，在 EPC數據返回之后，標簽還要接收 Req_RN指令，返回Handle數據，以便進行其他的數據讀寫.在保持其他參數不變的情形下，在調整 Tari值，統計各段時間長度后平均，再代入(7)—(9)式得出Rsr和Tis，結果如表2.

從表2中可以看出，通過調整Tari值，可以得到相應的識別速度和識別效率.根據前述模型，Tq由Tq1，Tq2，Tq3求平均得到，Tid，Ts，Tc由(1)式計算，測試結果表明在 Tari值為 6.25，12.5，25 μs時的標簽識別速率分別為每秒665，341和173個，而理論計算的結果分別為每秒726，364和182個，與圖5的仿真結果一致，表明本文所建立的馬爾科夫鏈模型對防碰撞進行模擬結果和測試結果相符合，表明基于馬爾科夫模型的測試理論正確有效.

圖7 射頻識別系統通信鏈路時序波形

本文在理論上提供了一種模擬測試RFID識別效率的方法，能有效真實地模擬標簽識別過程，且所設計的測試過程簡單，仿真算法效率高.但在實際應用中產品的識別速度會低于測試結果，因為實驗結果均按照圖1的時序進行分析，只計算讀寫器“標識”標簽的時間，如果考慮Req_RN指令以及后面的Handle應答，結合具體的讀寫操作，所用的時間會增加.測試設備在完成了對RN16的解碼后才能確定其識別成功，所以測試設備對信號解碼的靈敏度對測試的識別效率有影響，且在測試過程中，測試環境對識別效果有較大影響，讀寫器與標簽的相對位置和標簽間的彼此覆蓋都會影響指令俘獲效果而影響識別效率.

表2 通信時間理論值和測試結果的對比

5.結 論

通過對多標簽情形下的碰撞分解效率和標簽識別速度的討論，建立了馬爾科夫鏈模型來模擬通信鏈路中的碰撞分解過程，通過仿真和實驗測試，發現標簽的識別效率雖然隨標簽的增加有所降低，但是在較多標簽時，變化不敏感;隨Tari值的增加，識別速度降低.本文所建立的馬爾科夫鏈模型對防碰撞進行的模擬結果和測試結果基本一致，表明可以通過該模型對多標簽的讀取速度以及時隙利用效率和防碰撞算法進行有效分析，對RFID產品性能的具體測試很有意義.由于識別過程中時長統計的非完整性，則產品的實際識別效率和速度比理論結果和測試結果要低.模型求解過程是在有足夠多的標簽情形下完成的，實際環境下的標簽分布可能不滿足此條件，且環境因素也影響識別效果，因此模型還有待改進.

［1］Dobkin D M 2007The RF in RFID:Passive UHF RFID in Practice(New York:Elsevier)p422

［2］Xu H，Son L 2007Proc.of the9th ICACTBeijing，China，Feb.12—14，2007 p94

［3］Shih D H，Sun P L，Yen D C，Huang S M 2006Computer Communications29 2150

［4］Liu L，Yan D，Lai X，Lai S L 2008The4th ICCSCShanghai，China，May 26—28，2008 p559

［5］Maguire Y，Pappu R 2009IEEE Trans.on Automation Science and Engineering6 16

［6］Piramuthu S 2008JournalofInformation＆Knowledge Management7 9

［7］Tao C，Li J 2007Proc.of the9th ICACTBeijing，China，Feb.12—14，2007 p697

［8］Sohraby K，Mahmoud D，Wang C G，Li B 2009IEEE Trans.on Wireless Communications8 2592

［9］Bonuccelli M A，Lonetti F，Martelli F 2006Proc.of the Int.Symp.on WoWMoM′06 New York，USA，July 10—12，2006 p608

［10］ISO/IEC WD18000-6REV1:Part6:Parameters for air interface communications at860MHz to960Mhzver1 2007

［11］Hou Z G，He Y G，Li B，She K，Zhu Y Q 2010Acta Phys.Sin.59 5606(in Chinese)［侯周國、何怡剛、李 兵、佘開、朱彥卿2010物理學報59 5606］

［12］Tong Q， Zou X， Liu D， Dai Y 2007 Proc.ofthe 3rd WiCOM2007 Shanghai，China，Sep.21—25，2007 p2054

［13］Zhao Z J，Zheng S L，Xu C Y，Kong X Z 2007 Chin.Phys.16 1619

［14］Eom J B，Lee T L 2007 The International Symp.on Comm.and inform.Tech.Sydney，Australia，Oct.17—19，2007 p1027

PACS:52.70.Gw，06.90.+v

Radio frequency identification anti-collision test based on Markov chain model*

Hou Zhou-Guo1)2)?He Yi-Gang1)Li Bing1)
1)(College of Electrical and Information Engineering，Hunan University，Changsha 410082，China)
2)(Department of Communication and Control Engineering，Hunan Institute of Humanities Science and Technology，Loudi 417000，China)
(Received 12 October 2009;revised manuscript received 5 May 2010)

The anti-collision theory of adaptive Q algorithm and radio frequency identification(RFID)communication timing sequence were analyzed.Then a Markov chain model for simulating multi-tag identification process was established based on the following three definitions.The definitions are identifying efficiency，identifying speed and data state(Q，n)，where n is the total remanent tag number，and Q is the slot count.The identifying efficiency and speed were obtained from the model using Monte Carlo statistical method.A software-defined radio program was built to simulate the collision of RFID which could quantify the identifying efficiency and speed effectively.The consistency of model simulation result and test data proves the validity of the model and test method.

radio frequency identification，anti-collision test，Markov chain，slot-count

*國家杰出青年科學基金(批準號:50925727)、國家自然科學基金(批準號:60876022)、國家高技術研究發展計劃(批準號:2006AA04A104)、湖南省科技計劃(批準號:2008GK2022)和廣東省教育部產學研結合計劃(批準號:2009B090300196)資助的課題.

*Project supported by the National Natural Fund for Distinguished Young Scholar of China(Grant No.50925727)，the National Natural Science Foundation of China(Grant No.60876022)，the National High-Tech Research and Development Program of China(Grant No.2006AA04A104)，Hunan Provincial Science and Technology Program，China(Grant No.2008GK2022)，and the Joint Program of Guangdong Province and Ministry of Education of China on Industry，University and Research Institute Integration(Grant No.2009B090300196).