賈小林 馮全源 雷全水

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

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

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

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

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

1 多周期碰撞樹(shù)算法

1.1 基本原理

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

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

1.2 算法過(guò)程

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

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

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

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

通常情況下，標(biāo)簽編號(hào)ID中與prefix匹配后，緊鄰的一位為標(biāo)志位。例如:對(duì)于前綴p1，p2…pk，標(biāo)簽編號(hà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)過(guò)程中，只需要傳送編號(hào)ID中與p1p2…pk匹配之后的部分，即rj+1…，與前綴相同的部分，不需要發(fā)送。

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

1.3 算法實(shí)例

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

圖2 MCT算法的識(shí)別實(shí)例Fig.2 An example of MCT

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

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

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

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

2 MCT算法性能分析

2.1 時(shí)間復(fù)雜度

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

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

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

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

2.2 通信復(fù)雜度

防碰撞算法的通信復(fù)雜度(communication complexity)是指RFID多標(biāo)簽識(shí)別過(guò)程中閱讀器和標(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)簽識(shí)別過(guò)程中命令字的長(zhǎng)度，lpre，i為閱讀器在識(shí)別周期i發(fā)送的前綴長(zhǎng)度，lrep，i為標(biāo)簽在識(shí)別周期i發(fā)送的響應(yīng)二進(jìn)制位串的長(zhǎng)度，則公式(3)可改寫為:

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

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

2.3 識(shí)別效率

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

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

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

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

3.3 識(shí)別效率比較

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

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

4 結(jié)論

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

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

［2］寧煥生，王炳輝.RFID重大工程與國(guó)家物聯(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］