精選自適應(yīng)多叉樹防碰撞算法研究

1、PAGE 2_高等學(xué)校博士學(xué)科點專向科研基金(20230358033)資助課題自適應(yīng)多叉樹防碰撞算法研究摘 要 該文提出了一種自適應(yīng)多叉樹防碰撞算法。新算法在動態(tài)二叉樹和四叉樹搜索算法的根底上，利用曼徹斯特編碼可以準(zhǔn)確識別碰撞位的特性，通過計算碰撞因子，估計標(biāo)簽數(shù)量，從而自適應(yīng)地調(diào)整搜索叉數(shù)，即在標(biāo)簽數(shù)較多的節(jié)點上選擇動態(tài)四叉樹搜索，而在標(biāo)簽數(shù)較少時選擇動態(tài)二叉樹搜索。理論和仿真分析說明：新算法克服了動態(tài)二叉樹和四叉樹搜索算法的缺點，在減少碰撞時隙數(shù)的根底上，又減少了空閑時隙數(shù)，大幅度地提高了搜索效率和時隙的吞吐量，具有一定的創(chuàng)新性和適用性。關(guān)鍵詞 射頻識別；防碰撞算法；多叉樹搜索；中圖分類號

2、 TP301.6 文章標(biāo)識碼 AAn Adaptive Anti-collision Algorithm Based on Multi-tree SearchAbstract A new adaptive anti-collision algorithm based on multi-tree search is proposed in this paper. Because Manchester code can identify the position of collision, the new algorithm can adjust the number of search tree

3、 adaptively by using the information of probability of collision. That is to say ，when the number of tags is large，the new algorithm use four-tree search. Conversely, the new algorithm use binary-tree search. Theory and computer simulations show that the new anti-collision algorithm which overcomes

4、the disadvantages of binary-tree and four-tree algorithms can decrease effectively collision timeslots and idle timeslots and improve the throughput of timeslots.Key words Radio Frequency Identification (RFID)；Anti-collision algorithm；Multi-tree search；1 引言射頻識別RFID是20世紀(jì)90年代興起并逐漸走向成熟的一種非接觸式的自動識別技術(shù)，在物

5、流、跟蹤、定位等領(lǐng)域已得到廣泛應(yīng)用。其中，用于解決讀寫器作用范圍內(nèi)多標(biāo)簽識別問題的防碰撞算法已成為該領(lǐng)域研究的熱點之一。標(biāo)簽防碰撞算法主要解決在讀寫器有效通信范圍內(nèi)，多個標(biāo)簽同時與讀寫器進行通信的問題。常用的防碰撞算法一般可以分為兩類，一種是基于時隙隨機分配的ALOHA算法1，包括動態(tài)時隙ALOHA(DSA)算法1，分群時隙ALOHA算法(GSA)2和標(biāo)簽估計算法(TEM)3等。其特點是，算法簡單，便于實現(xiàn)，適用于低本錢RFID系統(tǒng)。但由于該類算法的時隙是隨機分配的，即存在一定的可能性，某一標(biāo)簽在相當(dāng)長一段時間內(nèi)無法識別，即“Tag starvation問題，所以這類方法被稱為可能性方法。另一

6、類是基于二叉樹搜索(BS)算法1，包括動態(tài)二叉樹搜索(DBS)算法1，自適應(yīng)二叉樹搜索算法(ABS)4-6和自適應(yīng)查詢樹算法(AQS)7等。該類算法比擬復(fù)雜，識別時間較長，但不存在“Tag starvation問題，故被稱為確定性方法。值得注意的是，當(dāng)待識別標(biāo)簽數(shù)量較多時，基于二叉樹的搜索算法由于頻頻出現(xiàn)碰撞，且每次碰撞只產(chǎn)生兩個分支，搜索效率較低。文獻8為此提出了一種基于四叉樹的搜索算法。雖然該算法在搜索的初期可以有效地減少碰撞，但隨著搜索范圍和標(biāo)簽的數(shù)量的減小，會產(chǎn)生大量的空閑時隙，因此搜索效率并沒有得到提高。本文在動態(tài)二叉樹DBS和四叉樹DFS搜索算法的根底上，利用曼徹斯特編碼可以準(zhǔn)確的

7、識別碰撞位的特性，通過計算碰撞因子，估計標(biāo)簽數(shù)量，從而自適應(yīng)地調(diào)整搜索叉PAGE 2數(shù)，即在標(biāo)簽數(shù)量較多時選擇動態(tài)四叉樹搜索，而在標(biāo)簽數(shù)量較少時選擇動態(tài)二叉樹搜索。理論和仿真分析說明：新算法克服了動態(tài)二叉樹和四叉樹搜索算法的缺點，在減少碰撞時隙數(shù)的根底上，又減少了空閑時隙數(shù)，大幅度地提高了搜索效率和時隙的吞吐量，具有一定的創(chuàng)新性和適用性。 PAGE 72 防碰撞算法原理及相關(guān)的研究成果對于一個特定的RFID系統(tǒng)來說，任意一個RFID標(biāo)簽都有一個唯一確定的EPC電子產(chǎn)品代碼，讀寫器通過獲取標(biāo)簽的EPC來確認(rèn)標(biāo)簽的身份。當(dāng)讀寫器作用范圍內(nèi)有多個未識別的標(biāo)簽時，每個標(biāo)簽都會響應(yīng)讀寫器的查詢命令，發(fā)送

8、自己的EPC，這樣就不可防止會出現(xiàn)相互干擾,即產(chǎn)生碰撞。而防碰撞算法就是要提出相應(yīng)策略，使讀寫器能逐一對標(biāo)簽進行識別。目前，很多RFID系統(tǒng)都采用國際標(biāo)準(zhǔn)ISO/IEC1800026中的二叉數(shù)搜索(BS)算法，它采用曼徹斯特(Manchester)的編碼方法，可以有效地識別碰撞比特出現(xiàn)的位置。BS算法的實質(zhì)就是通過屢次比擬，不斷縮小響應(yīng)標(biāo)簽的范圍，直至對唯一的標(biāo)簽進行識別，并通過循環(huán)操作，依次識別所有標(biāo)簽。但該算法始終是自上而下進行的，搜索的過程中會出現(xiàn)許多重復(fù)路徑，搜索效率比擬低。且讀寫器的查詢和標(biāo)簽的應(yīng)答，都是完整地傳輸EPC序列，這就需要讀寫器和標(biāo)簽之間進行大量的數(shù)據(jù)傳輸。在動態(tài)二叉樹搜

9、索算法中，讀寫器的查詢命令僅傳輸EPC序列的一局部，標(biāo)簽的應(yīng)答那么傳輸EPC序列的剩余局部，當(dāng)發(fā)生碰撞時，閱讀器根據(jù)第一次碰撞出現(xiàn)的位置，產(chǎn)生兩個新的查詢碼分別進行搜索。隨著搜索深度的增加，子叉數(shù)上的標(biāo)簽越來越少，直至對唯一的標(biāo)簽進行識別。而在動態(tài)四叉樹搜索算法中，當(dāng)標(biāo)簽發(fā)生碰撞后，讀寫器根據(jù)前兩次碰撞出現(xiàn)的位置，產(chǎn)生四個新的查詢碼分別進行搜索。圖1 動態(tài)二叉樹搜索流程值得注意的是，當(dāng)待識別標(biāo)簽數(shù)量較多時，動態(tài)二叉樹搜索算法由于頻頻出現(xiàn)碰撞，且每次碰撞只產(chǎn)生兩個分支，搜索效率較低。如圖1所示，完成上述RFID系統(tǒng)內(nèi)5個標(biāo)簽的搜索共需要9個時隙，其中4個是碰撞時隙。圖2 動態(tài)四叉樹搜索流程動態(tài)四

10、叉樹搜索算法雖然可以減少碰撞時隙數(shù)，但隨著搜索范圍和標(biāo)簽的數(shù)量的減小，會增加空閑時隙數(shù)。如圖2所示，完成所有標(biāo)簽的搜索仍然需要9個時隙，即在減少2個碰撞時隙的同時增加了兩個空閑時隙。圖3 四-二叉樹的搜索流程值得注意的是，在上述的系統(tǒng)中，如果在搜索深度1時，采用四叉樹搜索，而在搜索深度2時，采用二叉樹搜索，就可以有效地減少搜索的時隙數(shù)，提高搜索效率。如圖3所示，四-二叉樹搜索僅需要7個時隙，其中只有2個碰撞時隙，且不產(chǎn)生空閑時隙。3 自適應(yīng)多叉樹防碰撞算法 上述簡單的例子說明如果防碰撞算法能根據(jù)搜索的深度和標(biāo)簽的數(shù)量，自適應(yīng)地選擇搜索叉數(shù)，就可以有效地提高算法的效率。值得注意的是，在RFID系

11、統(tǒng)中，采用曼徹斯特(Manchester)編碼，讀寫器可以識別所有碰撞位的信息。現(xiàn)階段大多數(shù)二叉樹搜索算法僅利用了碰撞位的首位信息動態(tài)四叉樹搜索算法利用碰撞位的前兩位信息，而其余位碰撞信息并沒有充分的得到利用。一般來說，當(dāng)分支內(nèi)標(biāo)簽的數(shù)量越多時，出現(xiàn)碰撞的位數(shù)越多，碰撞位占總比特位的概率越大。例如在上述的RFID系統(tǒng)中，讀寫器發(fā)出查詢命令，所有的標(biāo)簽響應(yīng)，讀寫器檢測到碰撞，且碰撞在每一位都發(fā)生，即XXXXX表示發(fā)生碰撞的比特位，碰撞率為100%，說明系統(tǒng)中未識別的標(biāo)簽數(shù)量較多，所以在搜索深度為1時，采用四叉樹。當(dāng)時隙2檢測到碰撞時，標(biāo)簽的響應(yīng)為0X，碰撞率為50%，說明在該時隙內(nèi)未識別的標(biāo)簽數(shù)

12、量較少，在搜索深度為2時就可以采用二叉樹搜索了。為了有效的利用碰撞位信息，定義了碰撞因子。定義一：碰撞因子為在碰撞時隙內(nèi)碰撞比特占標(biāo)簽響應(yīng)比特位的比值： (1)定理一：碰撞因子包含了待識別標(biāo)簽的數(shù)量信息。證明：假設(shè)系統(tǒng)內(nèi)有個符合查詢條件的待識別標(biāo)簽，標(biāo)簽響應(yīng)的長度為比特，任意一位比特不發(fā)生碰撞的概率為，故： (2)可見，標(biāo)簽數(shù)量越大時，碰撞因子越高。反之，碰撞因子越低。說明碰撞因子包含了待識別標(biāo)簽的數(shù)量信息。如何確定碰撞因子的值呢？假設(shè)系統(tǒng)內(nèi)有個符合查詢條件的待識別標(biāo)簽，系統(tǒng)分配的叉數(shù)為,搜索深度為1時，標(biāo)簽的識別概率為：，在搜索深度為時，識別概率：，那么所需搜索深度的均值為： 33式兩邊同乘

13、以，可得： 4將3式減去4式得到： 5因為，根據(jù)等比數(shù)列的求和公式： 6所需的平均時隙數(shù)為： 7對于二叉樹搜索，所需的平均時隙數(shù)為：。對于四叉樹搜索，所需的平均時隙數(shù)為：。 比擬兩式，可得當(dāng)3時，四叉樹優(yōu)于二叉樹搜索，反之，二叉樹優(yōu)于四叉樹。根據(jù)式2，碰撞因子應(yīng)選擇： 8由于新算法是根據(jù)碰撞因子自適應(yīng)得選擇搜索叉數(shù)，所以被稱為自適應(yīng)多叉數(shù)防碰撞算法Adaptive multi-tree search anti-collision algorithm, 簡稱AMS算法。圖4 AMS算法的搜索流程框圖如圖4所示，算法的一般性描述如下：步驟1、讀寫器初始化查詢堆棧S，使之為空，并發(fā)出搜索命令。步驟2

14、、符合查詢條件的標(biāo)簽進行響應(yīng)。讀寫器根據(jù)標(biāo)簽響應(yīng)，確定時隙狀態(tài)。步驟3、讀寫器根據(jù)時隙狀態(tài)，自適應(yīng)地選擇搜索叉數(shù)和查詢碼。3.1、碰撞時隙：計算碰撞因子，如果，說明待識別的標(biāo)簽數(shù)較少，選擇動態(tài)二叉樹搜索，并根據(jù)碰撞首位信息，確定兩條新的查詢碼，將其寫入查詢堆棧S。如果，說明待識別的標(biāo)簽數(shù)較多，選擇動態(tài)四叉樹搜索，并根據(jù)碰撞前兩位的信息，確定四條新的查詢碼，將其寫入查詢堆棧S。3.2、空閑時隙：說明沒有標(biāo)簽存在，在該分叉內(nèi)無需繼續(xù)搜索。3.3、可讀時隙：說明有且僅有一個標(biāo)簽存在，讀寫器完成對該標(biāo)簽的識別。步驟4、判斷堆棧的內(nèi)容是否為空，如果不是，讀寫器讀取查詢堆棧內(nèi)的第一條查詢碼繼續(xù)搜索，并返回

15、到步驟2。否那么，算法結(jié)束。4 算法性能分析 通過時隙數(shù)和吞吐量計算，對AMS算法的性能進行分析。假設(shè)系統(tǒng)內(nèi)有個待識別標(biāo)簽，且標(biāo)簽的分布是均勻的。根據(jù)算法描述，可知當(dāng)碰撞因子子節(jié)點內(nèi)的標(biāo)簽數(shù)小于3時，采用動態(tài)二叉數(shù)搜索，反之那么采用動態(tài)四叉數(shù)搜索。所以，AMS算法的總時隙數(shù)為二叉數(shù)搜索的時隙數(shù)和四叉樹搜索的時隙數(shù)之和： 9假設(shè)當(dāng)搜索深度為時，子節(jié)點的標(biāo)簽數(shù)量平均為3。搜索深度小于，算法采用的是動態(tài)四叉數(shù)搜索，即：，表示取小于該值的最大整數(shù)。 10搜索深度大于等于，算法采用的是動態(tài)二叉數(shù)搜索，根據(jù)1； 11將1011式帶入9式可得： 12根據(jù)吞吐量的定義，可得： 13由于非整數(shù)時，所以和滿足：，

16、。5 實驗仿真與分析下面通過計算機對上述算法進行仿真，結(jié)果取20次實驗的平均值。a空閑時隙 b碰撞時隙c總時隙 d吞吐量 圖5 三種算法的性能比擬a總時隙 b吞吐量圖6 碰撞因子的選擇對AMS算法性能的影響圖5abcd分別為AMS、DBS和DFS三種算法所需空閑時隙、碰撞時隙、總時隙和吞吐量的比擬。當(dāng)標(biāo)簽數(shù)為500時，根據(jù)1213式，918，與仿真結(jié)果的誤差小于1%。說明仿真與理論分析一致，雖然DBS算法所需的空閑時隙最少為零，DFS算法所需的碰撞時隙最少，但AMS算法在減少碰撞時隙的根底上又降低空閑時隙數(shù)，從總時隙和吞吐量來看，具有更高的搜索效率和性能。圖6ab分別為選擇不同的碰撞因子對AM

17、S算法性能的影響。仿真與理論分析一致，說明選擇=0.75作為選擇二叉樹和四叉數(shù)的依據(jù)是正確的，比選擇其它值具有更好的搜索效率和性能。6 結(jié)束語本文提出了一種自適應(yīng)多叉樹防碰撞算法。新算法在動態(tài)二叉樹和四叉樹搜索算法的根底上，利用曼徹斯特編碼可以準(zhǔn)確識別碰撞位的特性，通過計算碰撞因子，估計標(biāo)簽數(shù)量，從而自適應(yīng)地調(diào)整搜索叉數(shù)，即在標(biāo)簽數(shù)較多的節(jié)點上選擇動態(tài)四叉樹搜索，而在標(biāo)簽數(shù)較少時選擇動態(tài)二叉樹搜索。理論和仿真分析說明：新算法克服了動態(tài)二叉樹和四叉樹搜索算法的缺點，在減少碰撞時隙數(shù)的根底上，又減少了空閑時隙數(shù)，大幅度地提高了搜索效率和時隙的吞吐量，具有一定的創(chuàng)新性和適用性。參考文獻1 Finke

18、nzeller K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification. John Wiley & Sons. 2023.2 Hwang Tae-Wook, Lee Byong-Gyo, Kim Young-Soo. Improved anti-collision scheme for high speed identification in RFID system. First International Conference on Innovative Com

19、puting, Information and Control, Beijing, China, 2023, vol.2:449452.3 Cha Jae-Ryong, Kim Jae-Hyun. Novel anti-collision algorithms for fast object identification in RFID system., 11th International Conference on Parallel and Distributed Systems Workshops, Fukuoka, Japan, 2023, vol.2:6367.4 Myung Jih

20、oon, Lee Wonjun, Srivastava J. Adaptive binary splitting for efficient RFID tag anti-collision. IEEE Communications Letters, 2023, 10(3):144146.5 Lai Yuan-Cheng, Lin Chih-Chung. A pair-resolution blocking algorithm on adaptive binary splitting for RFID tag identification. IEEE Communications Letters, 2023, 12(6):432434.6 Myung Jihoon, L