基于碰撞樹的多周期RFID標(biāo)簽識別防碰撞算法研究

賈小林 馮全源 雷全水

(1.西南科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 四川綿陽 621010;2.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 四川成都 610031)

射頻識別(radio frequency identification，RFID)技術(shù)是一種基于無線射頻通信原理的非接觸式自動識別技術(shù)，是物聯(lián)網(wǎng)(IOT)感知層的核心支撐技術(shù)之一［1－4］。RFID系統(tǒng)采用射頻信號通過空間耦合方式實現(xiàn)無接觸信息傳遞，并達(dá)到識別目標(biāo)對象的目的，當(dāng)多個標(biāo)簽在相同信道同時與閱讀器進(jìn)行通信時，信號在空中媒介發(fā)生干擾，就會引發(fā)碰撞(collision)，導(dǎo)致標(biāo)簽識別和數(shù)據(jù)傳送失敗［5－6］。因此，需要建立有效的防碰撞機(jī)制，即防碰撞算法(anti－collision algorithm)或防碰撞協(xié)議(anti－collision protocol)，來協(xié)調(diào)閱讀器與標(biāo)簽之間的通信，以實現(xiàn)多個標(biāo)簽的同時識別。所以，防碰撞算法是RFID多標(biāo)簽識別的關(guān)鍵技術(shù)，也是RFID系統(tǒng)及應(yīng)用研究的核心內(nèi)容之一。

解決RFID多標(biāo)簽識別的防碰撞算法主要分為兩個大類［7－10］:一類是基于 ALOHA的時隙類防碰撞算法，如:純ALOHA算法、時隙ALOHA算法(SALOHA)、幀時隙ALOHA算法(FSA)、動態(tài)幀時隙ALOHA算法(DFSA);另一類是基于樹搜索的防碰撞算法，如:查詢樹算法(QT)、二進(jìn)制樹算法(BT)、二進(jìn)制搜索算法(BS)。這些算法是防碰撞算法研究和應(yīng)用中的經(jīng)典算法和基礎(chǔ)算法，在其基礎(chǔ)上產(chǎn)生了許多改進(jìn)型或雜合型算法。研究表明［7－10］:經(jīng)典防碰撞算法及其改進(jìn)算法或雜合算法的識別效率通常只有34% ～36.8%，還不能滿足RFID多標(biāo)簽識別系統(tǒng)的實際需要。

文獻(xiàn)［11－12］提出了一種基于碰撞樹的防碰撞算法，即碰撞樹算法(collision tree protocol，CT)，將RFID多標(biāo)簽識別效率提高到50%以上。CT算法完全消除了RFID多標(biāo)簽識別過程中可能出現(xiàn)的空周期，打破了多標(biāo)簽識別的效率瓶頸，具有嚴(yán)格的樹型結(jié)構(gòu)對其識別性能和識別過程進(jìn)行分析和描述。因此，CT算法開啟了基于碰撞樹的防碰撞算法系列，并成為該算法系列的代表算法。文獻(xiàn)［13］提出了一種改進(jìn)型碰撞樹算法(ICT)，進(jìn)一步提高了RFID多標(biāo)簽識別效率，特別是當(dāng)標(biāo)簽編號連續(xù)分布時，標(biāo)簽識別效率達(dá)到100%以上。

本文提出另一種基于CT算法的高性能RFID多標(biāo)簽識別防碰撞算法，即多周期碰撞樹算法(multi－cycles collision tree algorithm，MCT)。該算法在保持CT算法優(yōu)勢的同時，減少了閱讀器的查詢次數(shù)，降低了閱讀器和標(biāo)簽的通信復(fù)雜度，將多標(biāo)簽識別效率提高到100%以上。

1 多周期碰撞樹算法

1.1 基本原理

在RFID系統(tǒng)中，標(biāo)簽編號的每一位只有兩種可能取值，即“0”和“1”，且每一次只能取其中之一。同時，根據(jù)標(biāo)簽編號中二進(jìn)制位的取值情況，能且只能將集合中的標(biāo)簽劃分為兩個確定的子集，其中一個子集標(biāo)簽編號該位為“1”，而另一個子集標(biāo)簽編號該位為“0”。這種標(biāo)簽編號位的二元性與標(biāo)簽集合劃分的二元性以及它們相互之間確定的對應(yīng)關(guān)系，即為二元確定性原理［13］。

根據(jù)二元確定性原理，論文將RFID多標(biāo)簽識別中閱讀器與標(biāo)簽之間完成通信的識別周期劃分為3個子周期:閱讀器查詢周期Q，標(biāo)簽的響應(yīng)周期R0和R1.標(biāo)簽根據(jù)收到的查詢命令，確定標(biāo)志位，并根據(jù)標(biāo)志位的值(0或1)選擇響應(yīng)周期(R0或R1)響應(yīng)閱讀器的查詢請求。由此，閱讀器的一次查詢可以獲得兩組標(biāo)簽的響應(yīng)。

1.2 算法過程

多周期碰撞樹算法(MCT)的基本過程如圖1所示。

圖1 多周期碰撞樹算法(MCT)的工作流程Fig.1 Work processes of MCT

初始時，閱讀器向前綴緩沖池中放入一個空串ε，并將標(biāo)簽編號tagID置為空NULL。開始識別時，閱讀器從前綴緩沖池中取出一個前綴，并以此前綴為參數(shù)，發(fā)送查詢命令Query(prefix)。閱讀器進(jìn)入等待狀態(tài)，等待并接收標(biāo)簽的響應(yīng)。

由于初始時搜索前綴prefix為空串，所以，在第一次查詢中，所有標(biāo)簽均響應(yīng)閱讀器的查詢請求。此時，標(biāo)簽編號的第一位即為首個標(biāo)志位。標(biāo)志位為0的標(biāo)簽，在R0中發(fā)送自己的編號ID，響應(yīng)閱讀的請求;標(biāo)志位為1的標(biāo)簽，在R1中發(fā)送自己的編號ID，響應(yīng)閱讀的請求。

通常情況下，標(biāo)簽編號ID中與prefix匹配后，緊鄰的一位為標(biāo)志位。例如:對于前綴p1，p2…pk，標(biāo)簽編號r1r2…rjrj+1…與之相匹配，則rj+1為標(biāo)志位。rj+1=0的標(biāo)簽在R0響應(yīng)閱讀器的查詢，rj+1=1的標(biāo)簽在R1響應(yīng)閱讀器的查詢。標(biāo)簽響應(yīng)過程中，只需要傳送編號ID中與p1p2…pk匹配之后的部分，即rj+1…，與前綴相同的部分，不需要發(fā)送。

閱讀器重復(fù)上述查詢過程，直到前綴池為空(NULL)，即完成所有標(biāo)簽的識別。

1.3 算法實例

圖2給出了MCT算法的一個實例，即采用MCT算法識別標(biāo)簽 組 {001010，011100，000110，010101，111001，110001，110010，111010}的基本過程及樹型結(jié)構(gòu)。如圖2所示，MCT算法經(jīng)過7次查詢和響應(yīng)過程，完成了這8個標(biāo)簽的識別。每次閱讀器查詢，兩組標(biāo)簽分別在R0和R1對閱讀器的請求發(fā)出響應(yīng)。如果一個響應(yīng)子周期只有一個標(biāo)簽滿足條件，發(fā)出了響應(yīng)，則閱讀器識別到該標(biāo)簽，而且，閱讀器可以在一次查詢中識別到兩個標(biāo)簽，如圖2中粗體表示的結(jié)點所示。

圖2 MCT算法的識別實例Fig.2 An example of MCT

表1給出了MCT算法實例(圖2)中閱讀器與標(biāo)簽之間的通信過程。首次查詢，閱讀器以空串ε作為前綴，所有標(biāo)簽以首位為標(biāo)志位，并根據(jù)標(biāo)志位的值，選取響應(yīng)子周期，發(fā)送各自的編號ID。閱讀器收到的響應(yīng)中，如果發(fā)生碰撞(表1中用“x”表示)，則生成一個新前綴，放入前綴池;如果沒有發(fā)生碰撞，則成功識別到一個標(biāo)簽。除首次響應(yīng)外，標(biāo)簽在響應(yīng)閱讀器請求時，只發(fā)送與前綴匹配后余下的編號位。當(dāng)前綴池為空(NULL)時，閱讀器完成全部標(biāo)簽識別。

表1 MCT算法實例中閱讀器與標(biāo)簽之間的通信過程Table 1 Communications between the reader and tags in the example of MCT

為了便于比較分析，圖3給出了采用CT算法識別這組標(biāo)簽的基本過程及樹型結(jié)構(gòu)。如圖3所示，經(jīng)過15次查詢和響應(yīng)過程，CT算法完成這8個標(biāo)簽的識別。閱讀器每次查詢只能獲得一組標(biāo)簽響應(yīng)。如果只有一個標(biāo)簽響應(yīng)，沒有發(fā)生碰撞，則閱讀器識別到一個標(biāo)簽，如圖3中葉節(jié)點所示。

圖3 CT算法識別圖2中標(biāo)簽的基本過程Fig.3 Basic Process of using CT to identify the tags in Fig.2

2 MCT算法性能分析

2.1 時間復(fù)雜度

在RFID系統(tǒng)中，防碰撞算法的時間復(fù)雜度(time complexity)是指完成標(biāo)簽集合中全部標(biāo)簽的識別所需要的查詢周期數(shù)。樹型防碰撞算法中，多標(biāo)簽識別的過程就是從根節(jié)點搜索葉節(jié)點的過程，因此，防碰撞算法的時間復(fù)雜度與樹型結(jié)構(gòu)中節(jié)點總數(shù)相等。由MCT算法與CT算法的識別過程可知，MCT算法中每一個節(jié)點涵蓋了CT算法中3個節(jié)點，包括雙親節(jié)點及其兩個孩子節(jié)點，如圖2和圖3所示。所以，MCT算法樹型結(jié)構(gòu)中的節(jié)點總數(shù)與CT算法樹型結(jié)構(gòu)中的中間節(jié)點數(shù)相等。因此，除去CT算法樹型結(jié)構(gòu)中的葉節(jié)點，即可得到MCT算法的樹型結(jié)構(gòu)。

由文獻(xiàn)［11］的分析:CT算法的時間復(fù)雜度為:

其中，n為識別標(biāo)簽的數(shù)量，且等于CT算法樹型結(jié)構(gòu)中葉節(jié)點的數(shù)量。所以，由MCT算法和CT算法的關(guān)系，可以得到MCT算法的時間復(fù)雜度為:

其中，n＞1。當(dāng)n=1時，T(n)=1。

2.2 通信復(fù)雜度

防碰撞算法的通信復(fù)雜度(communication complexity)是指RFID多標(biāo)簽識別過程中閱讀器和標(biāo)簽傳輸二進(jìn)制數(shù)的位數(shù)。設(shè)C(n)為MCT算法的通信復(fù)雜度，CR(n)和CT(n)分別為其閱讀器通信復(fù)雜度和標(biāo)簽通信復(fù)雜度，其中，n為標(biāo)簽數(shù)量，則有:

設(shè)lcom為標(biāo)簽識別過程中命令字的長度，lpre，i為閱讀器在識別周期i發(fā)送的前綴長度，lrep，i為標(biāo)簽在識別周期i發(fā)送的響應(yīng)二進(jìn)制位串的長度，則公式(3)可改寫為:

其中，T(n)為MCT算法的時間復(fù)雜度。設(shè)lID為標(biāo)簽編號的長度，由MCT算法閱讀器和標(biāo)簽通信響應(yīng)過程，則有:

由公式(2)，(4)，(5)，可得:

2.3 識別效率

防碰撞算法的識別效率(identification efficiency)是指識別標(biāo)簽的數(shù)量與完成這些標(biāo)簽識別所需要的查詢周期數(shù)量之間的比率。設(shè)E(n)為MCT算法的識別效率，則由公式(2)可得:

由于n為正整數(shù)，n＞1，所以有:

3 實驗及結(jié)果分析

論文主要將MCT算法與幾種經(jīng)典的主流防碰撞算法進(jìn)行實驗對比，對比算法包括:CT算法、QT算 法［9，12］、BT 算 法［9，12］、BS 算 法［6］、FSA 算法［7－8，10］。參照 EPCglobal Class 1 Generation 2 相關(guān)要求，實驗環(huán)境設(shè)置如下［11－13］:

系統(tǒng)為單閱讀器多標(biāo)簽識別系統(tǒng)，標(biāo)簽數(shù)量從4個增加到4 096個，標(biāo)簽編號長度為96位;所有實驗組的標(biāo)簽編號均勻分布，且其中沒有任何兩個標(biāo)簽的編號相同;選用兩個必要的通信命令:Query命令(22位)用于閱讀器查詢標(biāo)簽，ACK命令(18位)用于通知成功識別到的標(biāo)簽。

3.1 時間復(fù)雜度比較

圖4給出了MCT算法在時間復(fù)雜度方面的比較優(yōu)勢曲線。與其它幾種防碰撞算法的時間復(fù)雜度相比，MCT算法在時間復(fù)雜度性能上具有明顯的優(yōu)勢。完成一個標(biāo)簽的識別，MCT算法平均僅需要1次查詢搜索，CT算法需要2次，QT算法需要3次，而FSA算法、BT算法、BS算法則需要花費(fèi)更多次的搜索查詢。

圖4 MCT算法的時間復(fù)雜度優(yōu)勢Fig.4 Advantage of time complexity of MCT

3.2 通信復(fù)雜度比較

圖5給出了MCT算法在通信復(fù)雜度方面的比較優(yōu)勢曲線。在通信復(fù)雜度方面，MCT算法也具有明顯的優(yōu)勢。完成一個標(biāo)簽的識別，MCT算法的平均數(shù)據(jù)傳輸量只有CT算法的75%左右，QT算法的50%左右。通信復(fù)雜度在一定程度上反映了在多標(biāo)簽識別過程中系統(tǒng)的能量消耗。因此，在系統(tǒng)能耗方面MCT算法也具有明顯的優(yōu)勢。

由于在FSA算法中標(biāo)簽通過隨機(jī)生成的時隙號選擇一幀中的時隙進(jìn)行數(shù)據(jù)傳送，閱讀器也不需要發(fā)送前綴信息。因此，F(xiàn)SA算法的通信復(fù)雜度低于其它幾種防碰撞算法的通信復(fù)雜度，但是，F(xiàn)SA算法的通信復(fù)雜度卻比MCT算法高出約20%。

圖5 MCT算法的通信復(fù)雜度優(yōu)勢Fig.5 Advantage of communication complexity of MCT

3.3 識別效率比較

在識別效率方面，MCT算法的性能遠(yuǎn)遠(yuǎn)超過了其它防碰撞算法。如圖6所示，MCT算法的識別效率始終在100%以上，CT算法的識別效率為50%，QT算法的識別效率約為34%，其它幾種防碰撞算法的識別效率更低。除CT算法和MCT算法外，其它防碰撞算法的識別效率均在50%以下。

圖6 MCT算法的識別效率優(yōu)勢Fig.6 Advanfage of Identification efficiency of MCT

4 結(jié)論

本文提出了一種高性能的RFID多標(biāo)簽識別防碰撞算法，即多周期碰撞樹算法(MCT)。MCT算法在降低算法時間復(fù)雜度、通信復(fù)雜度和系統(tǒng)能耗的同時，提高了多標(biāo)簽識別的效率，在識別性能上具有明顯的優(yōu)勢。同時，在MCT算法中，標(biāo)簽的每次響應(yīng)只與當(dāng)前收到的前綴有關(guān)，而與過往的查詢過程和響應(yīng)歷史無關(guān)。因此，同CT算法一樣，MCT算法也屬于無記憶(memoryless)防碰撞算法，可適用于無源被動RFID多標(biāo)簽識別系統(tǒng)及其它RFID應(yīng)用系統(tǒng)，解決標(biāo)簽碰撞問題。

［1］中國科技部，等.中國射頻識別(RFID)技術(shù)政策白皮書［Z］.2006.

［2］寧煥生，王炳輝.RFID重大工程與國家物聯(lián)網(wǎng)［M］.機(jī)械工業(yè)出版社，2009.

［3］WANG Yong－ heng，ZHANG Xiao－ ming.Internet of Things［M］.InternationalWorkshop IOT 2012，Springer－Verlag，Berlin，Heidelberg，2012.

［4］JIA Xiao － lin，F(xiàn)ENG Quan － yuan，F(xiàn)AN Tai－ hua，et al.RFID Technology and Its Applications in Internet Of Things(IOT)［C］.2nd International Conference on Consumer Electronics，Communications and Networks，2012，(2):1282 －1285.

［5］Bang O，Choi JH，Lee D，et al.Efficient Novel Anticollision Protocols for Passive RFID Tags:Bi－slotted Tree Based RFID Tag Anti－ collision Protocols，Query Tree Based Reservation，and the Combining Method of Them［R］.Auto－ID Labs White Paper WP－HARDWARE －050，MIT，2009.

［6］FINKENZELLER K.RFID Handbook:Fundamentals and Applications in Contactless Smart Cards，Radio Frequen-cy Identification and Near Field Communication［M］.New York:Wiley，2010.

［7］KLAIR D K，CHIN KW，RAADR.A survey and tutorial of RFID anti－ collision protocols［J］.IEEE Communications Surveys＆ Tutorials，2010，12(3):400－421.

［8］SHIH D H，SUN P L，YEN D C，et al.Taxonomy and survey of RFID anti－ collision protocols［J］.Computer Communications，2006，29(11):2150 －2166.

［9］JIA Xiao － lin，F(xiàn)ENG Quan － yuan，F(xiàn)AN Tai－ hua，et al.Analysis of Anti－collision Protocols for RFID Tag Identification［C］.2nd International Conference on Consumer Electronics，Communications and Networks，2012(2):877－880.

［10］BONUCCELLIM A，LONETTIF，MARTELLIF.Instant collision resolution for tag identification in RFID networks［J］.Elsevier，Ad Hoc Networks，2007，5(8):1220 －1232.

［11］JIA Xiao－lin，F(xiàn)ENG Quan－yuan，MA Cheng－zhen.An efficient anti－collision protocol for RFID tag identification［J］.IEEE Communications Letters，2010，14(11):1014－1016.

［12］JIA Xiao－lin，F(xiàn)ENG Quan－yuan，YU Li－shan.Stability analysis of an efficient anti－collision protocol for RFID tag identification［J］.IEEE Transactions on Communications，2012，60(8):2285 －2294.

［13］JIA Xiao－lin，F(xiàn)ENG Quan－yuan.An improved anticollision protocol for radio frequency identification tag［J］.International Journal of Communication Systems，2013.［on line］