基于魯棒估計的最大前綴RFID防碰撞算法

王 勇,唐小虎,張莉涓,楊瑞琴

(1.西南交通大學a.物理科學與技術學院;b.信息科學與技術學院,成都610031; 2.中國石油四川成都銷售分公司,成都610072)

基于魯棒估計的最大前綴RFID防碰撞算法

王 勇1a,1b,唐小虎1b,張莉涓1b,楊瑞琴2

(1.西南交通大學a.物理科學與技術學院;b.信息科學與技術學院,成都610031; 2.中國石油四川成都銷售分公司,成都610072)

針對射頻識別(RFID)系統中標簽數量未知的情況,采用傳統ALOHA算法進行標簽估計,在標簽數量較大而初始幀長度較小造成估計誤差較大時,初始幀長度為固定值,通過改變響應標簽數量的方式,達到準確估計標簽的目的。研究標簽魯棒估計算法和隨機前綴查找樹(PRQT)防碰撞算法,在此基礎上提出基于魯棒估計的自適應最大前綴查找樹(PMQT)防碰撞算法。理論分析和仿真結果表明,該算法系統效率可達50%以上。PMQT算法比PRQT算系統效率提高18%～30%,對標簽估計偏差具有較高的魯棒性。

射頻識別;標簽識別;標簽估計;防碰撞算法;魯棒性;自適應

1 概述

防碰撞算法要求高效可靠地識別標簽,這對于射頻識別(Radio Frequency Identification,RFID)系統工程應用是一個現實的問題。在Reader-Talk-First模式中,閱讀器首先發出查詢命令,其查詢范圍內的標簽將返回存儲的信息。因為所有的標簽是共享信道方式和閱讀器通信,所以不可避免地導致互相干擾(碰撞),造成多標簽傳輸時系統性能的下降。

防碰撞問題與經典的多址通信相似,解決方案有樹型協議、ALOHA協議和載波偵聽多路訪問(Carrier Sense Multiple Access,CSMA)等。然而防碰撞算法極大地受限于標簽本身的弱計算能力和小內存,同時無源標簽無法檢測信道情況,所以CSMA在RFID防碰撞算法中無法使用。目前的防碰撞算法主要集中在基于分時的方式:樹型[1]或者ALOHA算法[2]。

本文提出最大前綴查找樹(Prefix Maximized Query Tree,PMQT)算法,根據修改的Park的標簽估計算法,自適應選擇最大查詢前綴長度,同時引入曼徹斯特編碼提高算法性能。因為有高效和高精確的估計算法,PMQT算法可以迅速地將大量標簽劃分成小組。同時,進一步利用曼徹斯特編碼精確的檢測沖突比特,從而達到自適應最大化查詢前綴的目的。

2 背景介紹

在樹型協議中,閱讀器發出查詢請求,標簽基于ID進行響應。樹型協議有多個變種,經典的輪詢方案在標簽數量太多的情況下有延時過大的問題。除此之外,標簽的分布及ID的長度也極大地影響識別效率。例如傳統的查找樹(Query Tree,QT)算法雖然簡單,但其最差時間復雜度很大[3]。

對于ALOHA協議,標簽響應閱讀器以隨機時隙方式實現,不受標簽分布和ID長度的限制。其也有很多變種[4],在這些協議族中,DFSA是理論研究和實際應用較多的防碰撞算法。然而系統效率有36.8%的理論上限[5],并且在標簽數量未知的情況下,不能保證所有標簽被識別。

在樹型協議族中[6],隨機前綴查找樹(Prefix Randomized Query Tree,PRQT)算法系統效率可達42%,是目前最好的防碰撞協議之一。通過隨機地選擇查詢前綴長度而非基于ID的逐位搜索方式,可以避免標簽分布和ID長度的限制。然而,PRQT協議是根據預定義的優化參數表來選擇前綴長度,其本身沒有標簽估計階段,而標簽數量在識別前一般是無法預知的,沒有標簽估計就無法確定查詢前綴的長度,所以這種方法在實踐中是不可行的。

3 PMQT算法

PMQT算法分為標簽估計階段和標簽識別階段。

標簽估計階段偽代碼如下:

在標簽估計階段,在Park標簽估計的基礎上做了一點修改[7]。Park利用具有固定幀長Lest的幀時隙ALOHA協議,參數fd位掩膜方式控制響應標簽的數量,直到沖突的概率Pcoll不大于閾值Pcoll_th。n代表準確的標簽數量,nest代表估計標簽的數量。通過解式(1),得到Pcoll_th所對應的閾值標簽數nth:

由位掩膜fd的控制反饋標簽的數量,則第2次估計的標簽數:,第3次估計的標簽數:,同理,第i次估計標簽數:,那么當滿足下式時:

此時的i即為完成標簽估計過程需要的總幀數i?。N屬于自然數集合,在幀,估計的標簽數量為:

假設總共使用估計的幀數i?=2時,總的標簽數估計值nest為:

同理,假設總共使用估計的幀數i?=3時,總的標簽數估計值nest為:

那么,當總共使用估計幀數為i?時,總的標簽數估計值nest即為式(3)。

這里,有:

其中,c0,c1,ck分別表示閱讀器在前一幀測量得到空閑時隙數,可讀時隙數和沖突時隙數;是有r個標簽時的數學期望,其數學定義為:

區別于Park的方法,其nest僅與Pcoll=ck/Lest有關,而與c0和c1無關。而本文算法與這3個測量值〈c0,c1,ck〉均有關,這樣估計值更精確。

曼徹斯特編碼比特級的沖突檢測能力已被廣泛接受[9]。在標簽識別階段,采用曼徹斯特編碼提高PRQT算法性能。利用曼徹斯特編碼可以尋找精確的沖突位,使得自適應地查詢前綴達到最大。

推導過程中所用公式參數及含義如表1所示。

表1 公式參數

最后,舉例說明PMQT標簽識別算法:假設有6個標簽,分別為{1001,1010,1011,1100,1101, 1110},如表2所示。

表2 PMQT實例

4 系統效率分析

對PMQT算法,標簽識別過程遞歸應用相同的原則,實際就是N-trees問題,其樹節點數量就是識別完可查詢區域內所有標簽需要的時隙。

假設:標簽ID服從均勻分布同時標簽估計是精確的,可以達到理想狀態,即估計的標簽數量nest和實際的標簽數量n相等,nest=n=L。

讓Pk代表k個標簽選擇同一前綴的概率。Pk服從二項分布:

用t(n)代表識別n個標簽平均需要的時隙(除根節點)。t(k)代表有k個標簽的子樹的大小。t(n)等于所有子樹的和。

顯然有t(0)=t(1)=1,t(2)≤3和t(3)≤6。

設K(n)=t(n)/n,那么系統效率定義為1/K(n)。因此有:

將式(8)代入式(9),得:

容易得到, ,所以有:

因此K(n)≤2,即系統效率1/K(n)至少高于50%,證明PMQT算法是目前較為高效的算法。

5 性能評估

在仿真中,設定Lest=128,Pcoll_th=0.9,fd=4。每一個仿真點代表1000次仿真的平均值,如表3所示。

表3 仿真參數取值情況

當測量的沖突概率變大時,Vogt標簽估計算法估計結果將變得不準確[10]。如果在PMQT中直接使用Vogt估計算法,Vogt估計算法將失效。因為計算表明:當標簽數大于847時,沖突的概率大于99%。首先測試標簽估計算法的性能。標簽數量由100～5 000變化,評估其精度與效率。圖1表明,當標簽數量小于200時,最大偏差達到39%,最大的平均偏差為9%,比單純使用Park算法提高3%。Pcoll_th分別為70%,80%,90%。同時,仿真表明:當標簽數為6 000時,只需3幀就可完成標簽估計過程。

圖1 標簽估計結果

在圖2中,比較了PMQT,QT,PRQT,其中,K= 64。QT算法和PRQT算法平均系統效率為36%和42%。仿真結果表明,PMQT系統效率在大多數情況下高于50%。在最差情況下,即標簽估計誤差過大時,PMQT退化成PRQT,例如A點。為了分析各種因素對PRQT算法的影響,比較了4種復合情況: PRQT與純Park估計(P)、修改的估計算法(V)、曼徹斯特編碼(M)組合,即PRQT+P,PRQT+V, PRQT+P+M,PRQT+V+M。曲線PRQT+V和PRQT+P表明,PRQT在修改的估計算法下比單純的Park算法系統效率要好。曲線PRQT+V+M和PRQT+P+M表明,曼徹斯特編碼能提高10%的系統效率。

圖2 系統效率比較

作為一個魯棒的防碰撞算法,標簽估計有輕微偏差時,系統效率不應受太大影響[11]。圖1中當沖突概率Pcoll_th分別為70%,80%和90%時,估計的結果受輕微影響。對于PMQT算法,系統效率的最大偏差為22%,最大平均偏差3%,均小于標簽估計時的誤差。這說明PMQT算法是魯棒的。不同標簽估計條件下系統效率比較如圖3所示,K=64。

圖3 不同標簽估計條件下系統效率比較

6 結束語

本文提出一種射頻識別系統PMQT協議,用于解決沖突問題,并研究標簽估計的準確性和標簽識別效率。理論分析和仿真結果表明,在標簽數量從稀疏到密集的情景下,PMQT協議在平均和最壞情況下的時間復雜度兩方面均優于PRQT協議。

在下一步工作中,將針對如何簡化標簽估計過程及標簽估計的準確性進行深入研究,同時合理優化查詢前綴的長度和閱讀器與標簽交換信息的長度,進一步提高系統的效率。

[1] ISO/IEC.ISO/IEC18000-6-2004Information Technology——RadioFrequencyIdentificationforItem Management-Part6:ParametersforAirInterface Communications at 860MHz to 960 MHz[S].2004.

[2] EPCglobal.EPCTMRadio-frequency Identity Protocols Class-1Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz[Z].2008.

[3] Law C,Lee K,Siu K.Efficient Memory Less Protocol for Tag Identification[C]//Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. Boston,USA:[s.n.],2000:75-84.

[4] Wang Junyu,Li Bo.Efficient Anti-collision Algorithm Utilizing the Capture Effect for ISO18000-6C RFID Protocol[J].IEEECommunicationLetters,2011, 15(3):352-354.

[5] Shin W J,Kim J G.A Capture-aware Access Control Method for Enhanced RFID Anti-collision Performance[J].IEEE Communication Letters,2009,13(5): 354-356.

[6] Chiang K W,Hua Cunqing,Yum T P.Prefix-randomized Query-tree Protocol for RFID Systems[C]//Proceedings of IEEE International Conference on Communication. [S.l.]:IEEE Press,2006:1653-1657.

[7] Park J,Chung M Y,Lee T J.Identification of RFID Tags in Framed-slotted ALOHA with Robust Estimation and Binary Selection[J].IEEE Communication Letters, 2007,11(5):452-454.

[8] Vogt H.MultipleObjectIdentificationwithPassive RFID Tags[C]//Proceedings of International Conference on Man and Cybernetics.[S.l.]:IEEE Press, 2002:6-13.

[9] Yang Ching-Nung,He Jyun-Yan.An Effective16-bit Random number Aided Query Tree Algorithm for RFID Tag Anti-collision[J].IEEE Communication Letters, 2011,15(5):539-541.

[10] Park J,Lee T J.Error Resilient Estimation and Adaptive Binary Selection for Fast and Reliable Identification of RFIDTagsinError-proneChannel[J].IEEE Transactions on Mobile Computing,2011,11(6):1-28.

[11] Bonuccelli M A,Lonetti F,Martelli F.Tree Slotted ALOHA:A New Protocol for Tag Identification in RFID Networks[C]//ProceedingsofIEEEInternational Symposium onaWorldofWireless,Mobileand Multimedia.[S.l.]:IEEE Press,2006:603-608.

編輯 顧逸斐

Maximized Prefix Anti-collision Algorithm for RFID Based on Robust Estimation

WANG Yong1a,1b,TANG Xiaohu1b,ZHANG Lijuan1b,YANG Ruiqin2
(1a.School of Physical Science and Technology,1b.School of Information Science and Technology, Southwest Jiaotong University,Chengdu 610031,China;
2.Chengdu Sales Branch in Sichuan,China National Petroleum Corporation,Chengdu 610072,China)

In the research of Radio Frequency Identification(RFID)system,when the number of unknown tags is estimated by using the traditional ALOHA algorithm,the large number of tags and the smaller initial frame length will cause large error.Using the initial fixed length of the frame,reader changes the response method to achieve an accurate tag number estimation.This paper studies a robust tag estimation method and the Prefix Randomized Query Tree(PRQT) algorithm,and then proposes Prefix Maximized Query Tree(PMQT)tag anti-collision protocol.The theoretic analysis shows that the system efficiency is more than 50%.The simulation result demonstrates that PMQT outperforms PRQT by about18%～30%with respect to the system efficiency.In addition,PMQT algorithm has tolerance to the inaccuracy of tag estimation.

Radio Frequency Identification(RFID);tag identification;tag estimation;anti-collision algorithm; robustness;self-adaptive

王 勇,唐小虎,張莉涓,等.基于魯棒估計的最大前綴RFID防碰撞算法[J].計算機工程,2015, 41(2):303-307.

英文引用格式:Wang Yong,Tang Xiaohu,Zhang Lijuan,et al.Maximized Prefix Anti-collision Algorithm for RFID Based on Robust Estimation[J].Computer Engineering,2015,41(2):303-307.

1000-3428(2015)02-0303-05

:A

:TN911

10.3969/j.issn.1000-3428.2015.02.058

中央高校基本科研業務費專項基金資助項目(SWJTU09BR246);四川省科技創新苗子工程基金資助項目(2010-016)。

王 勇(1974-),男,講師,主研方向:射頻識別,嵌入式系統;唐小虎,教授、博士生導師;張莉涓,博士研究生;楊瑞琴,工程師。

2013-12-30

:2014-04-09E-mail:wangyonga@swjtu.edu.cn