楊曉嬌1，吳必造2

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

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

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

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

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

0引言

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

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

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

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

　　1.1BS算法

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

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

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

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

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

　　由于BS算法要求標(biāo)簽每次都傳輸完整的ID，造成了帶寬的浪費，增加了識別延遲。為了降低傳輸延遲，又有學(xué)者提出了動態(tài)二進(jìn)制搜索算法(Dynamic Binary Search Algorithm, DBSA)。在DBSA算法中，標(biāo)簽只需要向閱讀器回復(fù)與查詢前綴匹配后的剩余ID即可。例如，假設(shè)閱讀器接收到標(biāo)簽回復(fù)的數(shù)據(jù)為“1011x1x1”，那么在下一個時隙，標(biāo)簽只需要傳輸1011之后的最后四位ID即可，因為閱讀器已經(jīng)將成功識別部分的ID進(jìn)行存儲，并會將正確識別的部分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ī)定閱讀器使用一個堆棧來存儲查詢前綴。在每一次尋呼過程中，讀寫器都會向其工作域內(nèi)的標(biāo)簽廣播攜帶標(biāo)簽部分ID前綴的查詢命令，與BS算法的區(qū)別是只有和查詢前綴相匹配的標(biāo)簽會回復(fù)閱讀器。如果有多個標(biāo)簽同時請求通信，此時就會產(chǎn)生碰撞，閱讀器先將當(dāng)前的查詢前綴壓入堆棧，然后根據(jù)接收到的碰撞位來更新查詢前綴。如果正確識別標(biāo)簽則閱讀器將重堆棧中取出查詢前綴作為查詢命令的參數(shù)，直到堆棧為空時，整個識別過程才會結(jié)束，算法流程如圖2所示。

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

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

　　(1)SQT(Shortcutting QT)算法

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

　?。?）AQT(Aggressive advancement QT)算法

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

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

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

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

　　早期QT類算法都是采用單比特碰撞仲裁機制即類似二叉樹的查詢方法，現(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］。

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

3結(jié)論

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

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

參考文獻(xiàn)

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

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

　?。?］ 王曉華，周曉光，王偉. 射頻識別（RFID）系統(tǒng)設(shè)計，仿真與應(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］ 余松森，詹宜巨，王志平，等. 跳躍式動態(tài)樹形反碰撞算法及其分析［J］. 計算機工程，2005，31(9): 19-20.

　?。?］ 丁治國，朱學(xué)永，郭立，等. 自適應(yīng)多叉樹防碰撞算法研究［J］. 自動化學(xué)報，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.

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