楊曉嬌1,，吳必造2

　?。?． 重慶交通大學(xué) 信息技術(shù)中心，重慶 400074,；2. 中移物聯(lián)網(wǎng)有限公司 解決方案中心,， 重慶 401336）

     摘要：先對(duì)RFID系統(tǒng)中的確定性防碰撞算法BS的工作原理進(jìn)行介紹，同時(shí)對(duì)基于BS的改進(jìn)算法原理做分析,；然后介紹了QT算法工作原理,，并對(duì)基于QT算法的改進(jìn)算法工作原理做了分析；最后結(jié)合作者自身的經(jīng)驗(yàn)對(duì)未來(lái)確定性防碰撞算法可以繼續(xù)進(jìn)行研究的方向給出建議,，對(duì)確定性防碰撞算法的后續(xù)研究具有一定的參考價(jià)值,。

　　關(guān)鍵詞：RFID；確定性防碰撞算法,；BS,；QT

　　中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.08.021

　　引用格式：楊曉嬌，吳必造.射頻識(shí)別中確定性防碰撞算法研究［J］.微型機(jī)與應(yīng)用,，2017,36（8）：67-69.

0引言

　　射頻識(shí)別(Radio Frequency Identification, RFID)是一種新興的無(wú)線通信技術(shù),，它可以利用無(wú)線電信號(hào)來(lái)實(shí)現(xiàn)目標(biāo)的非接觸式自動(dòng)識(shí)別，是物聯(lián)網(wǎng)底層關(guān)鍵支撐技術(shù)之一［1］,。在眾多RFID應(yīng)用場(chǎng)景中,，讀寫器往往需要同時(shí)與多個(gè)標(biāo)簽進(jìn)行通信。由于讀寫器與標(biāo)簽之間的通信信道是共享的,，當(dāng)多個(gè)標(biāo)簽同時(shí)向讀寫器發(fā)送數(shù)據(jù)時(shí)會(huì)產(chǎn)生多標(biāo)簽碰撞,，進(jìn)而引發(fā)帶寬浪費(fèi)、能量耗損和增加系統(tǒng)識(shí)別時(shí)延等一系列問題［23］,。為了解決多標(biāo)簽碰撞問題,，讀寫器需要采用防碰撞算法來(lái)協(xié)調(diào)讀寫器與多標(biāo)簽之間的通信,。防碰撞算法主要有兩類：確定性防碰撞算法和概率性防碰撞算法［4］。

　　概率性防碰撞算法即不確定性防碰撞算法（ALOHA）及其改進(jìn)算法的優(yōu)點(diǎn)是算法復(fù)雜度較低,，工程實(shí)現(xiàn)難度較低,；缺點(diǎn)是存在標(biāo)簽餓死等情況。確定性防碰撞算法的優(yōu)點(diǎn)是不存在標(biāo)簽餓死的情況,，即對(duì)標(biāo)簽的識(shí)別率能達(dá)到100%,，算法穩(wěn)定可靠；缺點(diǎn)是算法的時(shí)間復(fù)雜度和實(shí)現(xiàn)難度相對(duì)較高,，其應(yīng)用于對(duì)安全性要求較高的RFID系統(tǒng),。確定性標(biāo)簽防碰撞算法也是本文研究的重點(diǎn)，本文首先介紹了BS算法及其較好的改進(jìn)算法的流程,，然后介紹了QT類改進(jìn)算法的工作流程,，并結(jié)合作者的經(jīng)驗(yàn)說(shuō)明了未來(lái)改進(jìn)防碰撞算法的研究方向。

1BS算法及其衍生防碰撞算法

　　圖1BS算法流程圖確定性防碰撞算法主要包括二進(jìn)制搜索(Binary Search, BS)和查詢樹(Query Tree, QT)兩種算法,。下面分別介紹這兩類算法,。

　　1.1BS算法

　　BS算法的實(shí)現(xiàn)需要標(biāo)簽和閱讀器之間有嚴(yán)格的時(shí)間同步［5］，算法基本流程如圖1所示,，閱讀器先通過命令Request(N)廣播一個(gè)初始化的二進(jìn)制部分ID串號(hào)給其工作域內(nèi)的標(biāo)簽,。當(dāng)標(biāo)簽收到閱讀器的查詢命令后，將自身的ID同接收到的串號(hào)相比較,，那些ID小于等于串號(hào)的標(biāo)簽會(huì)發(fā)送自身的ID給閱讀器,。當(dāng)多個(gè)標(biāo)簽同時(shí)向閱讀器發(fā)送ID時(shí)，利用曼徹斯特編碼,，閱讀器就可以準(zhǔn)確地檢測(cè)到碰撞ID的具體位置［6］,，然后根據(jù)最高碰撞位重新調(diào)整Request(N)中ID串即N的值對(duì)標(biāo)簽。

　　繼續(xù)進(jìn)行分組,。當(dāng)某組中只存在一個(gè)標(biāo)簽時(shí)，閱讀器就可以成功識(shí)別標(biāo)簽,。讀寫器成功識(shí)別到一個(gè)標(biāo)簽后,，會(huì)發(fā)送初始化串號(hào)來(lái)重啟識(shí)別過程。

　　1.2增強(qiáng)型的二進(jìn)制搜索算法

　　余松森等人在BS算法的基礎(chǔ)上引入了回退機(jī)制［7］,，即每當(dāng)閱讀器成功識(shí)別一個(gè)標(biāo)簽后,，不會(huì)發(fā)送初始的串號(hào)來(lái)重啟識(shí)別過程，而是發(fā)送當(dāng)前節(jié)點(diǎn)的上一級(jí)碰撞位的數(shù)據(jù),。這種算法又稱為增強(qiáng)型的二進(jìn)制搜索算法(Enhanced Binary Splitting Algorithm, EBSA),，由于每次識(shí)別結(jié)束后EBSA算法不需要返回根節(jié)點(diǎn)，因此相對(duì)于BS算法,，EBSA算法中閱讀器的尋呼次數(shù)較少,。

　　1.3動(dòng)態(tài)二進(jìn)制搜索算法

　　由于BS算法要求標(biāo)簽每次都傳輸完整的ID,，造成了帶寬的浪費(fèi)，增加了識(shí)別延遲,。為了降低傳輸延遲,，又有學(xué)者提出了動(dòng)態(tài)二進(jìn)制搜索算法(Dynamic Binary Search Algorithm, DBSA)。在DBSA算法中,，標(biāo)簽只需要向閱讀器回復(fù)與查詢前綴匹配后的剩余ID即可,。例如，假設(shè)閱讀器接收到標(biāo)簽回復(fù)的數(shù)據(jù)為“1011x1x1”,，那么在下一個(gè)時(shí)隙,，標(biāo)簽只需要傳輸1011之后的最后四位ID即可，因?yàn)殚喿x器已經(jīng)將成功識(shí)別部分的ID進(jìn)行存儲(chǔ),，并會(huì)將正確識(shí)別的部分ID作為下一次查詢命令Request(N)的參數(shù)N,。相比于BS算法和EBSA算法，DBSA有效地減少了閱讀器與標(biāo)簽通信過程中的傳輸數(shù)據(jù)量,。

2QT算法及其衍生算法

　　目前,，QT類算法是應(yīng)用和研究最廣泛的一種確定性算法。QT算法最早由LAW C提出［6］,。下面分別介紹QT算法及其改進(jìn)算法,。

　　2.1QT算法

　　QT算法規(guī)定閱讀器使用一個(gè)堆棧來(lái)存儲(chǔ)查詢前綴。在每一次尋呼過程中,，讀寫器都會(huì)向其工作域內(nèi)的標(biāo)簽廣播攜帶標(biāo)簽部分ID前綴的查詢命令,，與BS算法的區(qū)別是只有和查詢前綴相匹配的標(biāo)簽會(huì)回復(fù)閱讀器。如果有多個(gè)標(biāo)簽同時(shí)請(qǐng)求通信,，此時(shí)就會(huì)產(chǎn)生碰撞,，閱讀器先將當(dāng)前的查詢前綴壓入堆棧，然后根據(jù)接收到的碰撞位來(lái)更新查詢前綴,。如果正確識(shí)別標(biāo)簽則閱讀器將重堆棧中取出查詢前綴作為查詢命令的參數(shù),，直到堆棧為空時(shí)，整個(gè)識(shí)別過程才會(huì)結(jié)束,，算法流程如圖2所示,。

　　2.2基于QT的改進(jìn)算法

　　下面有針對(duì)性地介紹幾類不同的基于QT的改進(jìn)算法。

　　(1)SQT(Shortcutting QT)算法

　　該算法的主要改進(jìn)之處是在原始QT算法的基礎(chǔ)上通過減少Q(mào)T算法的冗余查詢次數(shù),，從而減少了算法的識(shí)別時(shí)間［8］,。SQT的工作流程為：首先閱讀器發(fā)送一個(gè)帶有前綴N的Request(N)查詢命令，若檢測(cè)到碰撞,，閱讀器會(huì)將N0和N1壓入堆棧,；閱讀器先發(fā)送帶有前綴N0的查詢命令，若檢測(cè)到空閑,，那么讀寫器就說(shuō)明至少有2個(gè)標(biāo)簽與前綴N1匹配,；若閱讀器在下一個(gè)時(shí)隙發(fā)送帶有前綴N1的查詢命令,，必然會(huì)引起碰撞，于是閱讀器會(huì)先將N1前綴從堆棧中移除,，然后將N10和N11壓入堆棧,。

　　（2）AQT(Aggressive advancement QT)算法

　　該算法的核心是通過一次對(duì)多比特?cái)?shù)據(jù)入棧的形式來(lái)更新查詢前綴,，因此相較于QT算法的每次單比特查詢數(shù)據(jù)入棧,，在標(biāo)簽數(shù)量較多時(shí)可減少閱讀器的尋呼次數(shù)［9］。AQT算法的流程為：首先閱讀器發(fā)送一個(gè)帶有前綴N的Request(N)查詢命令,，若發(fā)送查詢前綴N后,，標(biāo)簽回復(fù)有碰撞，閱讀器會(huì)直接將前綴更新為N00,、N01,、N10和N11并壓入堆棧；閱讀器依次發(fā)送帶有前綴的查詢命令,。

　?。?）QTsl（QT short-long）算法

　　該算法改進(jìn)之處在于將閱讀器的查詢命令分為“長(zhǎng)查詢”和“短查詢”，這樣長(zhǎng)短結(jié)合的查詢命令有效減少了閱讀器的冗余數(shù)據(jù)傳輸量,。算法在識(shí)別中如遇碰撞則采用短查詢命令讓標(biāo)簽只返回1 bit數(shù)據(jù),，在匹配到的標(biāo)簽沒有碰撞時(shí)則采用長(zhǎng)查詢命令讓標(biāo)簽返回完整ID。即當(dāng)讀寫器知道僅有一個(gè)標(biāo)簽與當(dāng)前的查詢前綴匹配時(shí)才會(huì)發(fā)送“長(zhǎng)查詢”命令,。因此QTsl算法相較于QT數(shù)據(jù)量較少,。

　　2.3基于QT改進(jìn)算法研究展望

　　早期QT類算法都是采用單比特碰撞仲裁機(jī)制即類似二叉樹的查詢方法，現(xiàn)在研究者提出的許多QT算法都是基于多比特碰撞仲裁的,，采用多比特入棧查詢的方法,，即多叉樹查詢的方式，主要包括：提高型四叉樹查詢樹算法(Improved 4ary Query Tree Algorithm, I4QTA),、混合查詢樹(Hybrid Query Tree, HQT)算法,、自適應(yīng)多叉樹(Adaptive Multitree Search, AMS)算法、自調(diào)整混合樹(Adjustive Hybrid Tree, AHT)算法,、多進(jìn)制查詢樹(Mary Query Tree, MQT)算法,、基于碰撞位跟蹤的分組N叉跟蹤樹形算法(Collision bit Tracking Tree Algorithm based on Grouping Nary, CBGN)等［10］。

　　而未來(lái)的研究可以從如下幾個(gè)方面著手：第一,，可以沿用當(dāng)前尋呼命令，通過多比特仲裁的方式減少尋呼次數(shù)令,，從而提高算法性能,；其次，可以改進(jìn)尋呼命令來(lái)減少冗余數(shù)據(jù)的傳輸,，從而提高算法效率,；再者,，也可以結(jié)合不確定性算法的優(yōu)點(diǎn)從而減少算法的復(fù)雜度，進(jìn)而提高效率,。

3結(jié)論

　　確定性算法的優(yōu)點(diǎn)是不存在標(biāo)簽餓死的問題,，即在一定的時(shí)間內(nèi)算法對(duì)閱讀器作用域內(nèi)標(biāo)簽的識(shí)別率能達(dá)到100%，且相較于不確定性算法吞吐率較高,，因此適用于對(duì)標(biāo)簽讀取準(zhǔn)確性研究較高的情況,。其不足是算法的時(shí)間復(fù)雜度較高、需要硬件支持曼側(cè)斯特編碼和嚴(yán)格的時(shí)間同步,，要求閱讀器內(nèi)部設(shè)計(jì)一個(gè)堆棧來(lái)記錄查詢前綴信息,，標(biāo)簽內(nèi)部設(shè)計(jì)一個(gè)前綴匹配電路來(lái)配合閱讀器的查詢。因此系統(tǒng)的硬件成本和工程實(shí)現(xiàn)的復(fù)雜度較不確定性算法高,。

　　確定性算法的基本算法是BS算法,，而現(xiàn)在針對(duì)確定性算法的研究主要集中在QT算法上。QT算法基本是基于二叉樹的算法,，現(xiàn)在的研究通過查詢前綴將算法進(jìn)行改進(jìn),，主要集中在多叉樹以及二叉樹與多叉樹動(dòng)態(tài)結(jié)合來(lái)減少查詢命令的次數(shù)，從而提高算法效率,。本文介紹了多種比較好的基于QT的改進(jìn)算法,，為防碰撞算法的后續(xù)研究提供參考，并結(jié)合作者的個(gè)人經(jīng)驗(yàn),，建議針對(duì)確定性算法接下來(lái)可以繼續(xù)研究的方向,，對(duì)確定性算法的研究具有一定的參考價(jià)值。

參考文獻(xiàn)

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

　?。?］ 黃玉蘭.物聯(lián)網(wǎng)射頻識(shí)別(RFID)核心技術(shù)詳解［M］. 北京：人民郵電出版社，2012.

　?。?］ 王曉華,，周曉光，王偉. 射頻識(shí)別（RFID）系統(tǒng)設(shè)計(jì),，仿真與應(yīng)用［M］. 北京：人民郵電出版社,，2008.

　　［4］ LANDT J. The history of RFID［J］. IEEE Potentials, 2005, 24(4): 811.

　?。?］ FINKENZELLER K. RFID handbook: fundaments and application in contactless smart card and identification［M］. Hoboken: John Wiley & Sons, 2003.

　?。?］ LAW C, LEE K, SIU K Y. Efficient memoryless protocol for tag identification［C］. Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM for Mobility), Boston, 2000, 12(5): 32-38.

　　［7］ 余松森,，詹宜巨,，王志平，等. 跳躍式動(dòng)態(tài)樹形反碰撞算法及其分析［J］. 計(jì)算機(jī)工程，2005,，31(9): 19-20.

　?。?］ 丁治國(guó)，朱學(xué)永,，郭立,，等. 自適應(yīng)多叉樹防碰撞算法研究［J］. 自動(dòng)化學(xué)報(bào)，2010,，36(2): 237-341.

　?。?］ DJEDDOU M, KHELLADI R, BENSSALAH M. Improved RFID anticollision algorithm［J］. AEUInternational Journal of Electronics and Communications, 2013, 67(3): 256262.

　　［10］ 王鑫,，賈慶軒,，高欣，等. 分組N叉跟蹤樹形RFID防碰撞算法研究［J］. 電子學(xué)報(bào),，2016,，44(2): 437-444.