楊曉嬌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

　　中圖分類(lèi)號(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)景中，讀寫(xiě)器往往需要同時(shí)與多個(gè)標(biāo)簽進(jìn)行通信。由于讀寫(xiě)器與標(biāo)簽之間的通信信道是共享的，當(dāng)多個(gè)標(biāo)簽同時(shí)向讀寫(xiě)器發(fā)送數(shù)據(jù)時(shí)會(huì)產(chǎn)生多標(biāo)簽碰撞，進(jìn)而引發(fā)帶寬浪費(fèi)、能量耗損和增加系統(tǒng)識(shí)別時(shí)延等一系列問(wèn)題［23］。為了解決多標(biāo)簽碰撞問(wèn)題，讀寫(xiě)器需要采用防碰撞算法來(lái)協(xié)調(diào)讀寫(xiě)器與多標(biāo)簽之間的通信。防碰撞算法主要有兩類(lèi)：確定性防碰撞算法和概率性防碰撞算法［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類(lèi)改進(jìn)算法的工作流程，并結(jié)合作者的經(jīng)驗(yàn)說(shuō)明了未來(lái)改進(jìn)防碰撞算法的研究方向。

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

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

　　1.1BS算法

　　BS算法的實(shí)現(xiàn)需要標(biāo)簽和閱讀器之間有嚴(yán)格的時(shí)間同步［5］，算法基本流程如圖1所示，閱讀器先通過(guò)命令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)簽。讀寫(xiě)器成功識(shí)別到一個(gè)標(biāo)簽后，會(huì)發(fā)送初始化串號(hào)來(lái)重啟識(shí)別過(guò)程。

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

　　余松森等人在BS算法的基礎(chǔ)上引入了回退機(jī)制［7］，即每當(dāng)閱讀器成功識(shí)別一個(gè)標(biāo)簽后，不會(huì)發(fā)送初始的串號(hào)來(lái)重啟識(shí)別過(guò)程，而是發(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)簽通信過(guò)程中的傳輸數(shù)據(jù)量。

2QT算法及其衍生算法

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

　　2.1QT算法

　　QT算法規(guī)定閱讀器使用一個(gè)堆棧來(lái)存儲(chǔ)查詢前綴。在每一次尋呼過(guò)程中，讀寫(xiě)器都會(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í)別過(guò)程才會(huì)結(jié)束，算法流程如圖2所示。

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

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

　　(1)SQT(Shortcutting QT)算法

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

　　（2）AQT(Aggressive advancement QT)算法

　　該算法的核心是通過(guò)一次對(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)簽沒(méi)有碰撞時(shí)則采用長(zhǎng)查詢命令讓標(biāo)簽返回完整ID。即當(dāng)讀寫(xiě)器知道僅有一個(gè)標(biāo)簽與當(dāng)前的查詢前綴匹配時(shí)才會(huì)發(fā)送“長(zhǎng)查詢”命令。因此QTsl算法相較于QT數(shù)據(jù)量較少。

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

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

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

3結(jié)論

　　確定性算法的優(yōu)點(diǎn)是不存在標(biāo)簽餓死的問(wèn)題，即在一定的時(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算法基本是基于二叉樹(shù)的算法，現(xiàn)在的研究通過(guò)查詢前綴將算法進(jìn)行改進(jìn)，主要集中在多叉樹(shù)以及二叉樹(shù)與多叉樹(shù)動(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)

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

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

　　［3］ 王曉華，周曉光，王偉. 射頻識(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.

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

　　［8］ 丁治國(guó)，朱學(xué)永，郭立，等. 自適應(yīng)多叉樹(shù)防碰撞算法研究［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.

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