一種自調整多叉樹RFID 多標簽防碰撞算法

張娜，王志勇*

（浙江理工大學信息學院，浙江杭州，310018）

一種自調整多叉樹RFID 多標簽防碰撞算法

張娜，王志勇*

（浙江理工大學信息學院，浙江杭州，310018）

隨著RFID技術應用領域的拓寬，有效地解決多標簽碰撞問題是提高RFID系統性能的關鍵。在樹型搜索防碰撞算法分析的基礎上，提出一種自調整多叉樹防碰撞算法。該算法利用曼徹斯特編碼提取標簽碰撞位，組合成新的標簽序列號，然后閱讀器選取兩位序列號進行異或運算，并根據運算結果自調整搜索樹的叉數搜索標簽。該算法增加檢測命令，可以減少空時隙的數目，仿真實驗表明，自調整多叉樹算法在閱讀器查詢次數、系統吞吐率和傳輸比特數上比QT算法和改進的四叉樹算法都有所提升，在多標簽識別中更有競爭力。

RFID；防碰撞；多叉樹；自調整

引言

近年來，自動識別方法在貨物銷售、企業生產和材料流通領域得到了快速的普及和推廣，射頻識別(Radio Frequency Identification，RFID)技術是一種先進的自動識別和數據采集技術。RFID技術具有讀取方便、識別速度快和安全性高等眾多優點，對物聯網領域的進步具有重要意義[1]。RFID系統一般有閱讀器、電子標簽和天線組成。在RFID系統數據通信的過程中，經常會有多個閱讀器或多個標簽在同一場合中，就會造成標簽之間或者閱讀器之間相互干擾，這種干擾被稱為碰撞[2],閱讀器自身解決碰撞性能強，多個閱讀器之間產生的碰撞相對多個標簽之間產生的碰撞要容易解決。本文討論的是多個標簽之間產生碰撞的問題，當有多個標簽在同一時間響應閱讀器的信號，就會導致標簽的信號相互干擾，不能被閱讀器成功識別，造成閱讀器和標簽通信失敗。

目前解決標簽碰撞問題主要采用時分多路法，該方法分為確定性算法和非確定性算法。ALOHA算法屬于非確定性算法[3]，純 ALOHA算法實現原理簡單，但是標簽獲得處理時間不能掌控，如果一個標簽連續發生碰撞，就會導致該標簽處于一種“休眠”狀態[4]。王勇等[5]采用動態自適應的方式，根據標簽估計算法得到預測因子，使幀長和未識別的標簽數量相等，從而提高系統吞吐率，但是每次重新計算預測因子的過程比較繁瑣。文獻[6]中閱讀器對時隙進行掃描之后，發送給每個標簽，略去空時隙和碰撞時隙，加快識別標簽的速度。二進制樹搜索算法屬于典型的確定性算法[7]，閱讀器逐位劃分碰撞標簽，縮小識別標簽的數量，該算法識別成功率很高，但應用起來比較慢。張學軍等[8]通過計算碰撞因子動態的選擇搜索樹的叉數，從而減少產生空時隙，提高了標簽識別效率。文獻[9]在QT算法的基礎進行改進，動態地改變查詢前綴，減少碰撞次數和傳輸位數。

針對目前大部分防碰撞算法識別周期過長，存在過多的空時隙的問題，本文提出一種自調整多叉樹防碰撞方法，根據標簽序列號異或運算結果動態地選擇二叉或四叉搜索樹識別標簽，增加檢測指令，可以減少空時隙的數量和縮減閱讀器平均查詢次數，從而提高了系統的效率。

1 自調整多叉樹防碰撞算法

實現該算法需要能準確地定位到發生碰撞位的位置,本文選用曼徹斯特編碼法，此編碼法時通過半個周期的電平變化來得到的，在半個位周期時的負跳變(即電平由1變為0)表示二進制“1”，正跳變(即電平由0變為1)表示二進制“0”。當兩個標簽同時發送的比特位不相同時，上升沿和下降沿會相互抵消，造成電平未發生變化，會被系統當作錯誤處理，所以閱讀器利用該錯誤就可以判斷發生的具體位置。閱讀器利用曼徹斯特編碼檢測標簽1和標簽2碰撞位的示意圖如圖1所示，檢測出位置3和4為碰撞位。

圖1 曼徹斯特編碼檢測沖突示意圖

1.1 算法約定指令

為了便于描述算法，引入以下指令：

Request(prefix)請求指令，查詢前綴prefix由多個x組成，x∈{0,1}，滿足條件的標簽響應閱讀器的請求。

XOR(S)異或運算指令，S為進行異或運算比特的位置，閱讀器發送XOR(S)命令，同一個標簽的S和S+1位上的比特進行異或運算。

Push(prefix)入棧命令，將查詢前綴prefix放入堆棧中。

Pop出棧命令，將查詢前綴prefix從棧中取出。

Check(S)檢測命令，選取標簽的S和S+1位的比特分別進行異或運算。

Choose(S)選擇指令，選取兩個查詢前綴。Verify(V)確認指令，查看值為V的位置。

Read_Data讀取數據指令，讀取標簽內存儲的信息。

Select(UID)選擇指令，UID為每個標簽擁有唯一的序列號，閱讀器發送選擇指令，序列號為SNR的標簽將被選中。

Unselect(UID)取消指令，將序列號為 UID的標簽舍去，讓標簽進入“休眠”狀態。

1.2 算法設計

首先，將閱讀器中的堆棧初始化為空，閱讀器發送查詢請求Request(111…111)，范圍內標簽響應請求，如果沒有響應，算法運行結束，否則，標簽將返回自身的序列號作為回應。閱讀器根據曼徹斯特編碼將碰撞位置1，其他位置0，形成查詢序列號ID，并發送給標簽，例如，a標簽(10110101)、b標簽(11010111)、c標簽(10100111)、d標簽(11000011)，閱讀器譯碼結果為1XXX0XX1，得到的查詢序列號ID為01110110，將查詢序列號發送給標簽，標簽接收到ID，與自身序列號進行比對，提取出1對應位的值，組合成標簽新的 UID號。如上例，閱讀器發送ID(01110110)后，a、b、c和d標簽分別得到新的序列號a(01110)、b(10111)、c(01011)、d(10001)。

得到新的標簽后，閱讀器發送異或指令 XOR(S),標簽的序列號S和S+1位上的比特進行異或運算，運算結果如下：

a）如果只有0，閱讀器發送Push(00)和Push(11)命令。

b）如果只有1，閱讀器發送Push(01)和Push(10)命令。

c）如果即有1又有0，閱讀器發送Check(S)指令。

對于 a和 b種情況，閱讀器從堆棧中取出查詢前綴，發送Request(prefix)，如果只有一個標簽響應，說明在傳輸中沒有發生標簽碰撞，則閱讀器選擇該標簽，讀取標簽內的信息之后，發送Unselect命令，讓標簽“睡眠”，不再響應閱讀器的請求。如果發生碰撞，異或運算位S后移兩位，閱讀器先判斷S和S+1位是否相等，如果相等，繼續后移兩位，如果不相等，讓其繼續進行異或運算，一直循環，直到堆棧為空，標簽識別完成。

對于c種情況，算法增加了檢測機制，因為出現既有1和0的有很多種組合，例如11、10、01的組合，00、01、11的組合，11、01的組合等等，經過異或運算得到的值既有0又有1。為了避免此種情況的發生，閱讀器先發送Check(S)命令，讓標簽的S和S+1位上的比特分別進行異或運算。如果運算結果都為1，則將查詢前綴 00、01、10、11全部壓入堆棧。如果運算結果兩個值不相等，則發送Choose(S)確認指令，查看Check(S)運算結果為0位上的值等于多少，

a）如果為0，發送Push(00)命令。

b）如果為1，發送Push(11)命令。發送 Verify(V)確認指令，查看 Check(S)運算得到的值為 1的位置，

a）如果在S位，發送Push(10)命令。

b）如果在S+1位，發送Push(01)命令。

例如a(01110)和c(01011)在查詢前綴01節點發生了碰撞，S和 S + 1(S=2)位的數值為11和01，異或運算得到的結果既有0又有1，執行Check(S)指令之后，發現S和S+1位上的值不相等，則繼續發送Choose (S)指令和Verify(V)指令，發現0位上的值為1且在S+1位上，則只將查詢前綴11和10壓入堆棧中，舍棄00和 01，這樣可以避免多產生兩個空時隙，提高了系統識別準確率。算法流程如圖2所示。

圖2 算法流程圖

2 算法性能分析

本文從閱讀器查詢次數、吞吐率和通信復雜度三個方面分析算法的性能。

2.1 閱讀器查詢次數

閱讀器查詢次數的多少可以反映算法識別標簽的效率的高低，對閱讀器范圍內的n個標簽的查詢過程可以用一棵二叉和四叉組合樹的方式來表示，成功識別的標簽對應組合樹的葉子節點，發生碰撞的標簽對應組合樹的內部節點(除去葉子節點的其他節點)，對標簽的搜索類似于對組合樹的遍歷過程。閱讀器每次選取標簽序列號的兩位進行異或運算，根據運算結果選擇二叉樹或者四叉樹搜索標簽。

（a）當進行異或運算的比特位為00、01、10、11中的任意三個組合時，共有種情況；

（b）當異或運算為00、01、10、11時，此時產生0個空節點，共1種情況；

在（a）和（b）種情形下，閱讀器會選擇四叉樹進行搜索標簽，但（a）情況會產生一個空節點。

（c） 當進行異或運算的查詢前綴為00和11的組合或者01和10的組合，經過閱讀器的異或運算之后，選擇二叉樹查詢；

（d）當00與10、00與01、11與01、11與10的組合，經過閱讀器運算之后，會出現既有0又有1的情況，開始會選擇四叉樹查詢，但是經過檢測命令(check)檢測之后，最終還是選擇二叉樹搜索。

所以（c）和（d）共有六種情況會選擇二叉樹搜索。所以選擇二叉樹查詢的概率為6/11，選擇四叉樹查詢的概率為5/11，設總的查詢次數為N，產生四叉樹的節點為n4，產生二叉樹的節點為 n2，葉子節點(標簽被成功識別)為 n0，空節點為 nk。則N=n4+n2+n0+nk,即得到

2.2 吞吐率

RFID系統的吞吐率為標簽的數量比上閱讀器發送的查詢命令次數[10]，即

依照這個吞吐率的標準，自調整多叉樹RFID多標簽防碰撞算法吞吐率的表達式為

2.3 通信復雜度

通信復雜度是系統執行效率的另一個重要指標，是完成所有標簽的識別，閱讀器和標簽之間傳輸的總比特數，用C(n)表示，n為標簽的個數，閱讀器在獲得標簽新的序列號之前，信道傳輸的比特數用 L1表示，閱讀器獲得標簽新的序列號之后，信道傳輸的比特數用L2表示，則

為了將標簽的碰撞位提取出來，組合成新的標簽序列號，閱讀器首先發送一個和標簽序列號長度相等的查詢命令，范圍內的n個標簽返回自身的序列號，長度為k，閱讀器收到標簽的序列號之后，將碰撞位置“1”，其他位置“0”，形成和標簽長度k相等的查詢序列號，標簽接收到查詢序列號，提取自身序列號和查詢序列號為“1”對應的標簽位，并返回給閱讀器，假設新標簽的長度用 knew表示，在最優的情況下knew為Integ(lbn)位(n代表標簽的個數)，最差的情況和原來長度 k相等，所以形成新標簽位數的區間為[Integ(lbn),k][11]，此時在信道上傳輸的比特長度為L1，則

提取標簽碰撞位完成之后，閱讀器發送異或運算指令，根據運算結果選擇二叉樹或者四叉樹搜索，閱讀器發送的查詢前綴和標簽返回的序列號之和等于新的標簽序列號長度knew，

用Lcom表示閱讀器發送的平均指令長度，由上文對閱讀器查詢次數的分析，傳輸的比特數L2為，

由公式(4)、(5)和(6)可得，

3 實驗仿真與分析

實驗選取自調整多叉樹算法、查詢樹算法、一種改進的四叉樹RFID防碰撞算法[12]在軟件Matlab上進行仿真，標簽序列號由16位二進制數組成，標簽的數量n從0增加到2000，實驗結果取 50次的均值。分別取標簽序列號長度 k的值為Integ(lbn)、(Integ(lbn)+k)/2和k時，閱讀器查詢次數、吞吐率、傳輸的比特數和標簽個數的關系圖。

三種算法的閱讀器查詢次數隨著標簽數量的變化如圖3所示，從圖中可知，隨著標簽數量從 0增加到2000，三種算法的閱讀器查詢次數也都相應地在增多，QT算法增長的幅度尤為明顯，改進的四叉樹算法所需的平均搜索次數始終多于自調整多叉樹算法。當圖(a)中標簽數量等于400時，QT算法的搜索次數約是本算法查詢次數的三倍，改進的四叉樹算法也比本算法多200多次查詢，產生此結果的原因很可能是由于改進的四叉樹RFID算法每次都是通過匹配對比矩陣中的四個比特數(00、01、10、11)，來選擇搜索路徑，隨著標簽數目的減少，產生的空時隙的數目就會增多，而本算法通過檢測指令，成功避免了產生2個及以上的空時隙，提高了搜索的準確性。

圖3 本算法與QT算法、改進的四叉樹算法閱讀器查詢次數的比較

圖4是自調整多叉樹算法和QT算法以及改進的四叉樹算法吞吐率的比較，從圖中可以看出，本算法在吞吐率上明顯優于其他兩種算法，在圖(a)中隨著標簽數目的增多，自調整多叉樹算法吞吐率維持在0.55左右，而改進的四叉樹算法在0.5左右，當標簽的數量達到 1000左右時候，吞吐率下降較為明顯。其中 QT算法的吞吐率最低，這很可能是由于QT算法中閱讀器每次收到標簽碰撞，就將查詢前綴分別加上“0”和“1”，繼續查詢，直到沒有發生碰撞，才成功識別標簽。隨標簽的數目增多，逐位的查詢，發生碰撞的概率很高，導致QT算法的吞吐率較低。

圖4 本算法與FSA、改進的四叉樹算法吞吐率的比較

圖5是自調整多叉樹算法和QT算法以及改進四叉樹算法傳輸總比特數的比較，從圖(a)中可以發現，當標簽的序列號長度為Integ(lbn)時，自調整多叉樹算法傳輸的比特數要少于另外兩種算法，這是因為本算法通過曼徹斯特編碼提取標簽的碰撞位，組合成新的標簽序列號，在識別過程中，減少傳輸的比特數的位數。當標簽的序列號長度等于k時，傳輸的比特數和改進的四叉樹算法相當，但在一般情況下，經過曼徹斯特編碼之后，得到新的標簽序列號長度要少于原標簽序列號的長度，所以傳輸的比特數也會相應的減少。

圖5 本算法與QT算法、改進的四叉樹算法傳輸比特數的比較

通過對實驗結果進行分析比較，自調整多叉樹防碰撞算法在閱讀器查詢次數、系統吞吐率和傳輸的比特數上都要優于另外兩種算法，在解決標簽防碰撞問題更有優勢。

4 結束語

本文在以多叉樹搜索標簽為基礎，通過提取標簽序列號中發生碰撞的比特位，組合成新的標簽序列號，舍去多余的比特位，減少了閱讀器和標簽通信時傳輸比特的位數。執行 XOR(S)和Check(S)指令，動態的選擇多叉樹識別標簽，減少了空時隙的數目，提高系統的識別效率。通過實驗仿真和性能分析，該算法在系統吞吐率、閱讀器比較次數和傳輸比特數上更有優勢。在后續的研究中，可以根據標簽序列號的特征進行動態地分組，降低發生標簽碰撞的概率，使系統性能更加優越。

[1]蘇忠根. 射頻識別天線蝕刻技術工藝流程及其精益化管理研究[J].科技管理研究,2014,34(1)： 218-223.

[2]康東. 射頻識別 (RFID) 核心技術與典型應用開發案例[M]. 人民郵電出版社,2008.

[3]邢志鵬,楊恒新,張昀. 分段式位隙分組幀時隙Aloha算法[J]. 計算機技術與發展,2016,26(4)： 31-35.

[4]Hwang T W,Lee B G,Kim Y S,et al. Improved Anti-collision Scheme for High Speed Identification in RFID System[C]// International Conference on Innovative Computing,Information and Control. IEEE Computer Society,2006： 449-452.

[5]王勇,李婷. 改進的基于ALOHA的RFID防碰撞算法[J]. 電信科學,2016,32(8)： 77-81.

[6]張小紅,胡應夢. 分組自適應分配時隙的 RFID防碰撞算法研究[J].電子學報,2016,44(6)： 1328-1335.

[7]Park J,Min Y C,Lee T J. Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection[J].Communications Letters IEEE,2007,11(5)： 452-454.

[8]張學軍,蔡文琦,王鎖萍. 改進型自適應多叉樹防碰撞算法研究[J].電子學報,2012,40(1)： 193-198.

[9]肖菲,楊恒新,劉蕾蕾. 一種改進的二進制查詢樹RFID標簽防碰撞算法[J]. 計算機技術與發展,2014(6)： 92-94.

[10]吳楠. 一種樹型結構的RFID防碰撞算法研究[D]. 吉林大學,2014.

[11]Cover T M,Thomas J A. Elements of information theory (2. ed.)[M]//Elements of information theory /. Wiley,2006： 1600-1601.

[12]孫耀磊,吳曉波,陳元文,等. 一種改進的四叉樹 RFID 防碰撞算法[J]. 計算機工程與應用,2014,50(4)： 63-68.

Anti-Collision Algorithm based on Self-adjusting Multi-tree For RFID Multi-Tag

ZHANG Na,WANG Zhiyong*
(School of Information Science and Technology,Zhejiang Sci-Tech University,Hangzhou 310018,China)

With the expansion of RFID technology applications,effectively solve the multi-label collision problem is to improve the performance of RFID system key. Based on the analysis of anti - collision algorithm of tree search,a self - adjusting multi - tree anti - collision algorithm is proposed. The algorithm uses the Manchester code to extract the label collision bits,and then combines the new tag serial number,and then the reader selects the two-bit serial number to XOR and transfers the data according to the result of the operation. By increasing the detection command,the system can achieve the effect of reducing the number of empty slots. The simulation results show that the self -adjusting multi - tree algorithm has improved the number of times of reader query,system throughput and transmission bits than QT algorithm and improved quadtree algorithm,and it is more competitive in multi - tag recognition.

RFID; collision; multi-tree; self-adjusting

TN92

A

1672-9129(2017)06-0004-04

10.19551/j.cnki.issn1672-9129.2017.06.002

張娜,王志勇. 一種自調整多叉樹RFID多標簽防碰撞算法[J]. 數碼設計,2017,6(6)： 4-7.

Cite：ZHANG Na,WANG Zhiyong. Anti-Collision Algorithm based on Self-adjusting Multi-tree For RFID Multi-Tag[J]. Peak Data Science,2017,6(6)： 4-7.

2017-02-11；

2017-03-06。

浙江省重大科技專項重點工業項目： 面向公共安全的智能監控平臺關鍵技術研究與示范(2014C01047)；國家自然科學基金（61502430）；浙江理工大學“521人才培養計劃”。

張娜(1977—)，女，浙江杭州人，副教授，碩士，主要從事自適應軟件、軟件測試與智能信息處理方面的研究。王志勇(1992—)，男，安徽池州人，碩士研究生，研究的方向為物聯網技術。

E-mail:wzystxk@163.com