楊曉嬌1，吳必造2

　?。?． 重慶交通大學 信息技術中心，重慶 400074；2. 中移物聯網有限公司 解決方案中心， 重慶 401336）

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

　　關鍵詞：RFID；確定性防碰撞算法；BS；QT

　　中圖分類號：TP312文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.08.021

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

0引言

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

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

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

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

　　1.1BS算法

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

　　繼續進行分組。當某組中只存在一個標簽時，閱讀器就可以成功識別標簽。讀寫器成功識別到一個標簽后，會發送初始化串號來重啟識別過程。

　　1.2增強型的二進制搜索算法

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

　　1.3動態二進制搜索算法

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

2QT算法及其衍生算法

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

　　2.1QT算法

　　QT算法規定閱讀器使用一個堆棧來存儲查詢前綴。在每一次尋呼過程中，讀寫器都會向其工作域內的標簽廣播攜帶標簽部分ID前綴的查詢命令，與BS算法的區別是只有和查詢前綴相匹配的標簽會回復閱讀器。如果有多個標簽同時請求通信，此時就會產生碰撞，閱讀器先將當前的查詢前綴壓入堆棧，然后根據接收到的碰撞位來更新查詢前綴。如果正確識別標簽則閱讀器將重堆棧中取出查詢前綴作為查詢命令的參數，直到堆棧為空時，整個識別過程才會結束，算法流程如圖2所示。

　　2.2基于QT的改進算法

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

　　(1)SQT(Shortcutting QT)算法

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

　　（2）AQT(Aggressive advancement QT)算法

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

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

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

　　2.3基于QT改進算法研究展望

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

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

3結論

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

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

參考文獻

　?。?］ 寧煥生, 王炳輝. RFID重大工程與國家物聯網［M］. 北京：機械工業出版社, 2009.

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

　　［3］ 王曉華，周曉光，王偉. 射頻識別（RFID）系統設計，仿真與應用［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.

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

　?。?］ 丁治國，朱學永，郭立，等. 自適應多叉樹防碰撞算法研究［J］. 自動化學報，2010，36(2): 237-341.

　　［9］ 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］. 電子學報，2016，44(2): 437-444.