射頻識別中確定性防碰撞算法研究

楊曉嬌，吳必造

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

射頻識別中確定性防碰撞算法研究

楊曉嬌1，吳必造2

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

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

RFID；確定性防碰撞算法；BS；QT

0 引言

射頻識別(Radio Frequency Identification, RFID)是一種新興的無線通信技術(shù)，它可以利用無線電信號來實(shí)現(xiàn)目標(biāo)的非接觸式自動(dòng)識別，是物聯(lián)網(wǎng)底層關(guān)鍵支撐技術(shù)之一[1]。在眾多RFID應(yī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í)延等一系列問題[2-3]。為了解決多標(biāo)簽碰撞問題，讀寫器需要采用防碰撞算法來協(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)簽餓死的情況，即對標(biāo)簽的識別率能達(dá)到100%，算法穩(wěn)定可靠；缺點(diǎn)是算法的時(shí)間復(fù)雜度和實(shí)現(xiàn)難度相對較高，其應(yīng)用于對安全性要求較高的RFID系統(tǒng)。確定性標(biāo)簽防碰撞算法也是本文研究的重點(diǎn)，本文首先介紹了BS算法及其較好的改進(jìn)算法的流程，然后介紹了QT類改進(jìn)算法的工作流程，并結(jié)合作者的經(jīng)驗(yàn)說明了未來改進(jìn)防碰撞算法的研究方向。

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

圖1 BS算法流程圖

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

1.1 BS算法

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

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

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

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

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

由于BS算法要求標(biāo)簽每次都傳輸完整的ID，造成了帶寬的浪費(fèi)，增加了識別延遲。為了降低傳輸延遲，又有學(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)將成功識別部分的ID進(jìn)行存儲(chǔ)，并會(huì)將正確識別的部分ID作為下一次查詢命令Request(N)的參數(shù)N。相比于BS算法和EBSA算法，DBSA有效地減少了閱讀器與標(biāo)簽通信過程中的傳輸數(shù)據(jù)量。

2 QT算法及其衍生算法

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

2.1 QT算法

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

圖2 QT算法的程序流程圖

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

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

(1)SQT(Shortcutting QT)算法

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

(2)AQT(Aggressive advancement QT)算法

該算法的核心是通過一次對多比特?cái)?shù)據(jù)入棧的形式來更新查詢前綴，因此相較于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ā)送帶有前綴的查詢命令。

(3)QT-sl(QT short-long)算法

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

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

3 結(jié)論

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

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

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

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

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

[4] LANDT J. The history of RFID[J]. IEEE Potentials, 2005, 24(4): 8-11.

[5] FINKENZELLER K. RFID handbook: fundaments and application in contactless smart card and identification[M]. Hoboken: John Wiley & Sons, 2003.

[6] 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.

[8] 丁治國，朱學(xué)永，郭立，等. 自適應(yīng)多叉樹防碰撞算法研究[J]. 自動(dòng)化學(xué)報(bào)，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.

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

西門子TIA博途工程軟件平臺(tái)更開放且支持端到端工作流程

西門子近日擴(kuò)展了其TIA博途工程軟件平臺(tái)，發(fā)布了TIA博途V14 SP1，融入一系列全新實(shí)用功能，顯著縮短工程組態(tài)時(shí)間。TIA博途V14 SP1的一大創(chuàng)新亮點(diǎn)是對其他系統(tǒng)更具開放性，可利用Eplan、TIA Selection Tool或其他CAE(計(jì)算機(jī)輔助工程)系統(tǒng)等工程軟件，通過AutomationML(自動(dòng)化標(biāo)記語言)來實(shí)現(xiàn)標(biāo)準(zhǔn)化雙向工程數(shù)據(jù)交換。利用TIA博途Openness編程界面的全新功能，可實(shí)現(xiàn)對包括故障安全對象等硬件組態(tài)的自動(dòng)處理。這樣，用戶可以對冗余功能進(jìn)行自動(dòng)工程組態(tài)，大幅縮短開發(fā)時(shí)間，減少錯(cuò)誤率。

TIA博途工程軟件平臺(tái)是西門子的一個(gè)“中央接入點(diǎn)”，以實(shí)現(xiàn)數(shù)字化企業(yè)概念下的自動(dòng)化，以及設(shè)計(jì)數(shù)字化進(jìn)程中的自動(dòng)化解決方案。在TIA博途V14 SP1版本中，對Openness功能進(jìn)行了擴(kuò)展，以實(shí)現(xiàn)工作流程的全面數(shù)字化。例如，使用虛擬控制器Simatic S7-PLCSIM Advanced，即可在開發(fā)的早期階段對控制器功能進(jìn)行測試，并結(jié)合仿真機(jī)器模型，進(jìn)行虛擬調(diào)試。

從V14 SP1和V13 SP2版本起，TIA博途工程軟件平臺(tái)都支持Windows 10操作系統(tǒng)，從滿足了用戶對操作系統(tǒng)的多樣化要求。利用TIA博途V14 SP1中的全新密碼API接口，可保護(hù)針對專有知識、寫入和復(fù)制操作的密碼，以進(jìn)行簡便的集中管理。通過該接口，還可使用加密狗，實(shí)現(xiàn)專有應(yīng)用軟件或安全認(rèn)證概念的密碼管理系統(tǒng)。用于機(jī)器和工廠診斷的軟件選件Simatic ProDiag也進(jìn)行了擴(kuò)展，融入了條件分析功能以進(jìn)行有的放矢地故障排查。這樣，可使用HMI PLC代碼查看器，可視化顯示故障的狀態(tài)，從而更高效地確定故障根本原因。Step 7工程工具中，機(jī)器制造商現(xiàn)在可使用全新的單塊比較功能來進(jìn)行快速編輯，例如，可在離線/離線或在線/離線操作中直接從項(xiàng)目導(dǎo)航區(qū)域?qū)Ω鱾€(gè)塊進(jìn)行詳細(xì)比較。

使用西門子TIA博途工程軟件平臺(tái)，用戶可通過高效組態(tài)，快速、直觀地執(zhí)行自動(dòng)化和驅(qū)動(dòng)任務(wù)。與數(shù)字企業(yè)軟件套件中的PLM(產(chǎn)品生命周期管理)和MES(制造執(zhí)行系統(tǒng))一起，TIA博途工程軟件平臺(tái)完善了西門子工業(yè)軟件系列，助力客戶闊步邁向“工業(yè)4.0”。

(西門子(中國)有限公司 供稿)

Research on the certainty anti-collision algorithm of radio frequency identification system

Yang Xiaojiao1， Wu Bizao2

(1. Information Technology Centre, Chongqing Jiaotong University, Chongqing 400074, China;2. Solutions Center, China Mobile IOT Company Limited, Chongqing 401336, China)

This paper mainly focuses on the certainty anti-collision algorithm in Radio Frequency Identification (RFID) system. Firstly it presents the basic working principles of Binary Search (BS) algorithm and introduces some improved algorithms on the basis of BS. Then it discusses the basic working principles of Query Tree (QT) algorithm and introduces some improved algorithms on the basis of QT. Finally, combined with the author’s own experience, the directions for future research are proposed. So the work done in this paper will provide some reference for the follow-up study of certainty anti-collision.

RFID; certainty anti-collision algorithm; BS; QT

TP312

A

10.19358/j.issn.1674- 7720.2017.08.021

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

2016-10-31)

楊曉嬌(1988-)，通信作者，女，碩士，助理工程師，主要研究方向：無線傳感網(wǎng)、RFID。E-mail:yangxiaojiao@cqjtu.edu.cn。

吳必造(1985-)，男，碩士，軟件工程師，主要研究方向：物聯(lián)網(wǎng)安全、物聯(lián)網(wǎng)傳輸、RFID。

________________________