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

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

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

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

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

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

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

射頻識(shí)別;標(biāo)簽識(shí)別;標(biāo)簽估計(jì);防碰撞算法;魯棒性;自適應(yīng)

1 概述

防碰撞算法要求高效可靠地識(shí)別標(biāo)簽,這對(duì)于射頻識(shí)別(Radio Frequency Identification,RFID)系統(tǒng)工程應(yīng)用是一個(gè)現(xiàn)實(shí)的問題。在Reader-Talk-First模式中,閱讀器首先發(fā)出查詢命令,其查詢范圍內(nèi)的標(biāo)簽將返回存儲(chǔ)的信息。因?yàn)樗械臉?biāo)簽是共享信道方式和閱讀器通信,所以不可避免地導(dǎo)致互相干擾(碰撞),造成多標(biāo)簽傳輸時(shí)系統(tǒng)性能的下降。

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

本文提出最大前綴查找樹(Prefix Maximized Query Tree,PMQT)算法,根據(jù)修改的Park的標(biāo)簽估計(jì)算法,自適應(yīng)選擇最大查詢前綴長度,同時(shí)引入曼徹斯特編碼提高算法性能。因?yàn)橛懈咝Ш透呔_的估計(jì)算法,PMQT算法可以迅速地將大量標(biāo)簽劃分成小組。同時(shí),進(jìn)一步利用曼徹斯特編碼精確的檢測(cè)沖突比特,從而達(dá)到自適應(yīng)最大化查詢前綴的目的。

2 背景介紹

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

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

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

3 PMQT算法

PMQT算法分為標(biāo)簽估計(jì)階段和標(biāo)簽識(shí)別階段。

標(biāo)簽估計(jì)階段偽代碼如下:

在標(biāo)簽估計(jì)階段,在Park標(biāo)簽估計(jì)的基礎(chǔ)上做了一點(diǎn)修改[7]。Park利用具有固定幀長Lest的幀時(shí)隙ALOHA協(xié)議,參數(shù)fd位掩膜方式控制響應(yīng)標(biāo)簽的數(shù)量,直到?jīng)_突的概率Pcoll不大于閾值Pcoll_th。n代表準(zhǔn)確的標(biāo)簽數(shù)量,nest代表估計(jì)標(biāo)簽的數(shù)量。通過解式(1),得到Pcoll_th所對(duì)應(yīng)的閾值標(biāo)簽數(shù)nth:

由位掩膜fd的控制反饋標(biāo)簽的數(shù)量,則第2次估計(jì)的標(biāo)簽數(shù):,第3次估計(jì)的標(biāo)簽數(shù):,同理,第i次估計(jì)標(biāo)簽數(shù):,那么當(dāng)滿足下式時(shí):

此時(shí)的i即為完成標(biāo)簽估計(jì)過程需要的總幀數(shù)i?。N屬于自然數(shù)集合,在幀,估計(jì)的標(biāo)簽數(shù)量為:

假設(shè)總共使用估計(jì)的幀數(shù)i?=2時(shí),總的標(biāo)簽數(shù)估計(jì)值nest為:

同理,假設(shè)總共使用估計(jì)的幀數(shù)i?=3時(shí),總的標(biāo)簽數(shù)估計(jì)值nest為:

那么,當(dāng)總共使用估計(jì)幀數(shù)為i?時(shí),總的標(biāo)簽數(shù)估計(jì)值nest即為式(3)。

這里,有:

其中,c0,c1,ck分別表示閱讀器在前一幀測(cè)量得到空閑時(shí)隙數(shù),可讀時(shí)隙數(shù)和沖突時(shí)隙數(shù);是有r個(gè)標(biāo)簽時(shí)的數(shù)學(xué)期望,其數(shù)學(xué)定義為:

區(qū)別于Park的方法,其nest僅與Pcoll=ck/Lest有關(guān),而與c0和c1無關(guān)。而本文算法與這3個(gè)測(cè)量值〈c0,c1,ck〉均有關(guān),這樣估計(jì)值更精確。

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

推導(dǎo)過程中所用公式參數(shù)及含義如表1所示。

表1 公式參數(shù)

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

表2 PMQT實(shí)例

4 系統(tǒng)效率分析

對(duì)PMQT算法,標(biāo)簽識(shí)別過程遞歸應(yīng)用相同的原則,實(shí)際就是N-trees問題,其樹節(jié)點(diǎn)數(shù)量就是識(shí)別完可查詢區(qū)域內(nèi)所有標(biāo)簽需要的時(shí)隙。

假設(shè):標(biāo)簽ID服從均勻分布同時(shí)標(biāo)簽估計(jì)是精確的,可以達(dá)到理想狀態(tài),即估計(jì)的標(biāo)簽數(shù)量nest和實(shí)際的標(biāo)簽數(shù)量n相等,nest=n=L。

讓Pk代表k個(gè)標(biāo)簽選擇同一前綴的概率。Pk服從二項(xiàng)分布:

用t(n)代表識(shí)別n個(gè)標(biāo)簽平均需要的時(shí)隙(除根節(jié)點(diǎn))。t(k)代表有k個(gè)標(biāo)簽的子樹的大小。t(n)等于所有子樹的和。

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

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

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

容易得到, ,所以有:

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

5 性能評(píng)估

在仿真中,設(shè)定Lest=128,Pcoll_th=0.9,fd=4。每一個(gè)仿真點(diǎn)代表1000次仿真的平均值,如表3所示。

表3 仿真參數(shù)取值情況

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

圖1 標(biāo)簽估計(jì)結(jié)果

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

圖2 系統(tǒng)效率比較

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

圖3 不同標(biāo)簽估計(jì)條件下系統(tǒng)效率比較

6 結(jié)束語

本文提出一種射頻識(shí)別系統(tǒng)PMQT協(xié)議,用于解決沖突問題,并研究標(biāo)簽估計(jì)的準(zhǔn)確性和標(biāo)簽識(shí)別效率。理論分析和仿真結(jié)果表明,在標(biāo)簽數(shù)量從稀疏到密集的情景下,PMQT協(xié)議在平均和最壞情況下的時(shí)間復(fù)雜度兩方面均優(yōu)于PRQT協(xié)議。

在下一步工作中,將針對(duì)如何簡化標(biāo)簽估計(jì)過程及標(biāo)簽估計(jì)的準(zhǔn)確性進(jìn)行深入研究,同時(shí)合理優(yōu)化查詢前綴的長度和閱讀器與標(biāo)簽交換信息的長度,進(jìn)一步提高系統(tǒng)的效率。

[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

王 勇,唐小虎,張莉涓,等.基于魯棒估計(jì)的最大前綴RFID防碰撞算法[J].計(jì)算機(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

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目(SWJTU09BR246);四川省科技創(chuàng)新苗子工程基金資助項(xiàng)目(2010-016)。

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

2013-12-30

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