基于Walsh碼的RFID并行識別碰撞樹算法

駱萱 賈小林 顧婭軍

摘 要：針對大規模標簽場景下，改進碰撞樹 （ICT）算法中碰撞時隙較多且有多個碰撞位時無法并行識別多標簽的問題，提出一種基于Walsh碼的RFID并行識別碰撞樹（PICT）算法。PICT算法引入Walsh同步正交碼與碰撞樹協議相結合，對ICT算法中發生多位碰撞時的標簽使用Walsh碼進行擴頻，具有唯一Walsh碼的標簽通過不同的子信道與閱讀器通信，實現多標簽并行識別。理論與實驗分析表明，PICT算法相比同類算法所需系統總時隙數更少，并且具有更高的系統識別率，適合大規模標簽的快速識別。

關鍵詞：射頻識別；Walsh同步正交碼；碰撞樹協議；并行識別；防碰撞

中圖分類號：TP391?? 文獻標志碼：A?? 文章編號：1001-3695（2023）12-019-3651-04

doi：10.19734/j.issn.10013695.2023.04.0138

Collision tree algorithm of RFID parallel identification based on Walsh code

Abstract：In order to address the problem of inability to parallelly identify multiple tags in the ICT algorithm when there are multiple collision slots and collisions at multiple positions in largescale tag scenarios，this paper developed a PICT algorithm based on Walsh codes for RFID.The PICT algorithm combined Walsh synchronization orthogonal codes with the collision tree protocol.It used Walsh codes to spread the tags involved in multiple collisions in the ICT algorithm，and tags with unique Walsh codes communicate with the reader through different subchannels，enabling parallel identification of multiple tags.Theoretical and experimental analyses demonstrate that the PICT algorithm requires fewer total system time slots compared to similar algorithms，and it achieves higher system identification efficiency，making it suitable for fast identification of largescale tags.

Key words：radio frequency identification；Walsh synchronous orthogonal code；collision tree protocol；parallel recognition；anticollision

0 引言

射頻識別技術（radio frequency identification，RFID）因其自動識別特點在大規模標簽場景中應用廣泛。多標簽同時使用公共信道與閱讀器進行通信時難免會出現標簽碰撞問題，該問題會導致RFID系統通信質量受損。目前存在的多標簽防碰撞算法主要采用時分多址技術，可將其分為基于ALOHA的防碰撞算法［1］和基于樹的防碰撞算法［2］。

基于ALOHA的防碰撞算法是一種隨機接入算法，適合標簽規模較小的場景。基于樹的防碰撞算法可分為三大類，即查詢樹（query tree，QT）算法［3］、二進制樹（binary tree，BT）算法［4］、碰撞樹（collision tree，CT）算法［5］。碰撞樹算法根據曼徹斯特編碼［6］獲取首位碰撞位生成查詢前綴對標簽進行查詢和識別，消除空閑時隙，是一種高效穩定的防碰撞算法，但識別過程仍然存在碰撞時隙多、系統效率低的問題。改進的碰撞樹（improved collision tree，ICT）算法［7］引入二元確定性原理，在標簽編號連續時能達到很好的效果。在此基礎上結合自適應策略調整改進碰撞樹分支結構的自適應碰撞樹（adaptive collision tree，ACT）算法［8］，減少了RFID多標簽識別過程中的碰撞時隙數，但在采用四分支結構時形成了空周期。因此，基于并行匹配的自適應碰撞樹（parallel adaptive collision tree，PACT）算法［9］在ACT 算法基礎上引入并行匹配機制來減少識別過程中的空閑周期，PACT 算法在一定程度上提高了系統識別效率。MDPM（modified dual prefixes matching）算法［3］提出一種改進的雙前綴匹配機制，允許多個標簽在同一查詢中響應，以達到并行識別多個標簽的目的。除此之外，動態碰撞樹（dynamic collision tree，DCT）算法［10］考慮了RFID系統的動態模型，識別過程中的碰撞樹會隨著標簽的進入和識別動態地調整。

ICT算法提出二元確定性原理［7］，即只有一位碰撞位時，閱讀器能根據曼徹斯特編碼鎖定碰撞位，同時識別兩個標簽，而當閱讀器檢測碰撞位多于兩個時，則產生碰撞。針對 ICT 算法在多位碰撞時不能實現多個標簽并行識別的情況，引入Walsh同步正交碼，提出一種基于碰撞樹的并行識別RFID防碰撞（parallel improved collision tree，PICT）算法。PICT算法使用Walsh擴頻碼對標簽ID進行擴頻，將碰撞時隙內的標簽使用不同的子信道與閱讀器通信，以此實現單個時隙內同時識別多個標簽，減少標簽碰撞概率，在大規模標簽場景下減少識別大量標簽所需時間，提高系統識別效率。

1 并行識別碰撞樹算法（PICT）

1.1 Walsh同步正交碼擴頻原理

在基于時分多址方式的同步傳輸情況下，利用Walsh碼作為擴頻碼，將標簽信息與Walsh碼相乘進行擴頻生成混合信號傳輸給閱讀器。其閱讀器與標簽擴頻通信原理如圖1所示。

Walsh碼由哈德碼矩陣H（Hadamard）生成，是一種同步正交碼。H矩陣與Walsh 碼的對應關系如式（1）所示，碼長為m時能生成m個互不相關的Walsh碼［11］ 。

wnm=［Hm］n+1（1）

假設標簽1和標簽2的信息分別用t1和t2表示，生成兩個Walsh碼分別為w1和w2，對標簽信息進行擴頻后產生的混合信號為

Signal=t1×w1+t2×w2（2）

閱讀器接收到混合信號后對標簽1進行解調，得到

∫Signal=∫t1×w1dt=∫t1×w1×w2dt +∫t2×w1×w2dt（3）

由于不同Walsh碼之間互相關為零，即w1×w2的值為0，所以得到標簽1的ID信息。同理可據此使多個標簽的信息通過不同的子信道同時進行傳輸，實現多標簽的并行識別。

1.2 PICT算法原理及流程

PICT在ICT算法的基礎上設置 SPRESAD（m） 擴頻指令，在標簽中增加生成擴頻碼的硬件模塊并在閱讀器硬件模塊預存碼表信息。 SPRESAD（m）擴頻指令的參數為Walsh碼長m的值。接收到 SPRESAD（m）指令的標簽獲取m的值后在自身硬件模塊中隨機生成一個長度為m的Walsh碼與自身編號相結合進行擴頻。選擇不同Walsh碼的標簽會與閱讀器通過不同的子信道進行通信。由于ICT算法在識別過程中是不存在空閑時隙的，在PICT算法中，碰撞時隙內的標簽通過不同子信道與閱讀器通信從而轉換為可讀時隙，標簽再根據其首位碰撞位生成查詢前綴進行查詢識別，所以PICT算法中同樣不存在空閑時隙。在PICT算法中可能會出現的時隙狀態為

1）可讀時隙

a）閱讀器接收到的標簽信息中沒有發生碰撞時，只有一個標簽響應，閱讀器成功識別該標簽。

b）閱讀器收到的標簽信息中只有一個碰撞位，則根據ICT算法的二元確定性原理成功識別兩個標簽。

c）閱讀器收到的標簽信息中有多個碰撞位，但是存在具有唯一的Walsh碼的標簽，即該標簽能通過單獨的子信道與閱讀器通信避免碰撞，成功識別Walsh碼唯一的標簽。

2）碰撞時隙

閱讀器收到的標簽信息中有多個碰撞位并且沒有標簽的 Walsh碼是唯一的，則此時隙為碰撞時隙，標簽無法被閱讀器成功識別。因此，PICT算法的閱讀器操作流程如圖2所示，標簽操作流程如圖3所示。

閱讀器操作過程描述如下：

a）初始化查詢堆棧，將堆棧內置空并壓入空串。

b）若標簽集為空，則結束；若標簽集不為空，閱讀器從查詢堆棧中彈出一個查詢前綴（prefix），同時向閱讀器讀寫范圍內的標簽廣播擴頻指令SPRESAD（m），并以prefix和m的值作為參數向閱讀器識別范圍內的標簽廣播查詢指令。

c）閱讀器內部對接收到的標簽剩余ID信息和擴頻碼正交調制的信號進行解擴操作，根據解碼的結果判斷時隙狀態。

d）若沒有發生碰撞，則此時為可讀時隙，成功識別一個標簽，其ID為查詢前綴加上除查詢前綴外的剩余ID信息。

e）若閱讀器判斷響應的標簽信息中只有一位碰撞，將響應的標簽信息記作received_ID，碰撞位記作c，則閱讀器成功識別兩個標簽，其ID為prefix串接received_ID的正確位，并將碰撞位的值設置為0和1。

f）若閱讀器判斷響應的標簽信息中有多個碰撞位，閱讀器則根據步驟c）中接收到的混合信號的解擴結果判斷該時隙內是否存在Walsh碼是唯一的標簽。若存在，則該標簽將通過單獨的子信道與閱讀器通信；若不存在，則該時隙為碰撞時隙，此外如果除去Walsh碼是唯一的標簽之后還有剩余待識別標簽，則閱讀器將該時隙認作碰撞時隙進行碰撞處理。記首位碰撞位為fc，此時生成兩個新前綴并壓入堆棧，其新前綴的生成規則為Newprefix=prefix+received_ID［1，…，fc］，其中第fc位分別置0和置1。

g）重復上述操作直至標簽集為空。

標簽操作過程描述如下：

a）若標簽接收到閱讀器的前綴查詢指令，則將自身 ID與 prefix 進行逐位比較，若ID的前k位與prefix匹配，則根據閱讀器發送的SPRESAD（m）擴頻指令獲取參數m，標簽隨機選擇Walsh碼與除去查詢前綴外的剩余ID部分進行正交調制，隨后將調制后的信號發送給閱讀器。

b）若標簽自身ID與接收到閱讀器的前綴查詢指令不匹配，則返回等待閱讀器下一輪的查詢指令。

1.3 PICT算法實例

采用PICT算法識別標簽集{10001010，00010010，00101010，10110110，10010011，10011011，01011111}的過程實例如表1所示。首先，閱讀器根據標簽首位碰撞生成查詢前綴0和1壓入堆棧，隨后從堆棧中彈出查詢前綴，同時發送Walsh碼長m=4的擴頻指令SPRESAD（m）。在響應閱讀器查詢前綴為0的標簽子集中，接收到擴頻指令的標簽根據m的值生成一個長度為4的Walsh碼與自身ID相結合后將擴頻后的混合數據發送給閱讀器。此時標簽2、3和7具有唯一的Walsh碼，因此這三個標簽與閱讀器通過不同子信道通信從而被成功識別，至此前綴為0的標簽子集識別完成。在與前綴為1相匹配的標簽子集中，標簽1和4在此時隙內Walsh碼唯一，閱讀器成功識別，而標簽5和6的Walsh碼相同，此時為碰撞時隙，進入碰撞處理。閱讀器根據曼徹斯特編碼檢測標簽信息中只有一個碰撞位，則根據二元確定性原理成功識別這兩個標簽。由此得到，采用PICT算法識別這七個標簽僅經過三個查詢周期。

2 算法理論分析

在 RFID 系統中，通常以系統總時隙數和系統識別效率作為評價防碰撞算法性能的重要指標。假設射頻場內的待識別標簽數量為N，搜索深度為l，搜索分支數為L。由文獻［9］可知標簽的識別概率為

p（l）=p（1）［1-p（1）］l-1（4）

平均搜索深度為

標簽所需的平均時隙數為平均搜索深度乘以搜索分支數。由于ICT算法的碰撞樹結構為二叉樹，即分支數量為2。C（1）代表ICT算法中只有一個碰撞位時的時隙數。代入L=2可以得到ICT算法的平均時隙數表示為

當Walsh碼的碼長為m，即有m個互相關性為零的Walsh碼時，在單個時隙內，有n個標簽分配到不同的Walsh擴頻碼的概率為P（n，m）［12］，將其表示為

假設標簽響應信息的位串長度為r，標簽響應的情況包括無碰撞、一位碰撞以及多位碰撞。響應中沒有發生碰撞的概率為

得到的標簽響應中只有一個碰撞位，即根據碰撞位成功識別兩個標簽的概率為

因此，根據標簽的碰撞情況可知響應中發生多位碰撞的概率為

進而可知，在發生多位碰撞時同一個時隙內n個標簽可以被成功識別的概率為

在PICT算法中，根據曼徹斯特編碼檢測到產生碰撞時的標簽有多個碰撞位時，標簽將采用不同子信道與閱讀器進行通信，那么其所需總時隙數為 ICT 算法中發生多位碰撞時除去能使用單一子信道與閱讀器通信，即Walsh碼是唯一的標簽數量。因此PICT所需時隙數為

系統識別率表示一個時隙內能成功識別的標簽數量的期望值。碰撞時隙內，閱讀器最多可以識別的標簽數量表示為min（m，N）個，因此PICT算法的系統識別效率S為

3 仿真實驗分析

假設閱讀器范圍內標簽均勻分布且Walsh碼隨機分布，標簽數量初始值為200，逐漸增加標簽數量。

對Walsh碼長m的值取2s（s的值為0，1，2，…，7）時，識別定量標簽消耗的總時隙數對比如圖4所示。當s=0時，識別過程等同于ICT算法。其識別2 000個標簽的總時隙為4 000，隨著m值的增大消耗的總時隙減少。當s=7即m值取128時，識別2 000個標簽消耗的時隙數為457。相比m=1時消耗的總時隙減少了3 543個，識別總時隙數減少了88.58%，識別時間顯著降低。由此可知，當標簽數量一定時，Walsh 碼長m越大，PICT 算法所需總時隙數越少，但硬件系統復雜度會有所增加。

下面將Walsh碼的碼長設置為128，在識別一定數量標簽所需的總時隙數和系統識別效率上，將PICT與ACT、PACT以及MDPM算法進行對比與分析。圖5為不同算法之間的標簽數量與總時隙數對比。相比ACT、PACT以及MDPM算法，PICT算法識別定量標簽所需的總時隙數分別減少了89%、87.5%和80%。

圖6為不同算法的系統識別率對比。當Walsh碼長為m=128時，PICT算法的系統平均識別效率為4.421 8，而ACT算法的平均系統識別效率為0.521 2，PACT算法的平均系統識別效率為0.609 2，MDPM算法的平均系統識別效率為0.960 8。

根據以上仿真實驗結果可知，ICT算法根據二元確定性原理只在標簽ID連續時僅用一次查詢識別標簽，所需系統總時隙數較多，系統識別率低。PACT在ICT算法基礎上采用并行匹配機制動態調整叉樹識別標簽，減少了RFID系統的總時隙數，一定程度上提高了系統識別效率。MDPM算法采用的雙前綴匹配機制進一步減少系統總時隙數，提升系統識別率。這三種算法局限于單個時隙內只能識別一個標簽，而PICT算法對產生多位碰撞的多個標簽進行擴頻，實現單個時隙內多個標簽的并行識別，因此系統總時隙數與系統識別率都要優于ACT、PACT以及MDPM算法。

4 結束語

本文提出一種基于Walsh碼的RFID并行識別碰撞算法（PICT），PICT算法根據曼徹斯特編碼檢測標簽發生多位碰撞時，將碰撞時隙內Walsh碼是唯一的標簽通過單獨的子信道與閱讀器通信，從而轉換為可讀時隙，減少碰撞時隙數，實現多位碰撞時多標簽的并行識別。目前在閱讀器硬件資源豐富的條件下，實驗結果表明，當Walsh碼的碼長設置為128時，PICT算法快速識別大量標簽時能達到很好的效果，其所需總時隙數與ACT、PACT以及MDPM算法所需總時隙數相比分別減少了89%、87.5%和80%，同時PICT算法系統識別率達到了4.4218，遠高于其余三種算法的系統識別效率。由于PICT算法增加了一定的系統硬件復雜度，更適用于快速識別大規模標簽的應用場景。由于m的值越大，系統硬件復雜度越高，后續研究工作可根據碰撞標簽數對m的值進行動態設置。

參考文獻：

［1］魏福祿，劉攀，李志斌，等.基于動態幀時隙ALOHA的危險品運輸RFID防碰撞算法 ［J］.沈陽工業大學學報，2020，42（5）：540544.（Wei Fulu，Liu Pan，Li Zhibin，et al. RFID anticollision algorithm for dangerous goods transportation based on dynamic frame slotted ALOHA［J］.Journal of Shenyang University of Technology，2020，42（5）：540-544.）

［2］Yaacob M，Daud S M，Azizan A.A review of deterministic anticollision algorithm of passive RFID systems［J］.Open International Journal of Informatics，2019，7（1）：8-25.

［3］Su Jian，Chen Yongrui，Sheng Zhengguo，et al. From Mary query to bit query：a new strategy for efficient largescale RFID identification［J］.IEEE Trans on Communications，2020，68（4）：2381-2393.

［4］李勇，王瓊.多電子標簽識別的RFID防碰撞方法［J］.南京郵電大學學報：自然科學版，2019，39（4）：3338.（Li Yong，Wang Qiong.RFID anticollision method based on multiple electronic tags identification［J］.Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition，2019，39（4）： 33-38.）

［5］Jia Xiaolin，Feng Quanyuan，Yu Lishan.Stability analysis of an efficient anticollision protocol for RFID tag identification［J］.IEEE Trans on Communications，2012，60（8）：2285-2294.

［6］Jia Xiaolin，Feng Quanyuan，Ma Chengzhen.An efficient anticollision protocol for RFID tag identification［J］.IEEE Communications Letters，2010，14（11）： 10141016.

［7］Jia Xiaolin，Feng Quanyuan.An improved anticollision protocol for radio frequency identification tag［J］.International Journal of Communication Systems，2015，28（3）： 401-413.

［8］Liu Xiaohui，Qian Zhihong，Zhao Yanhang，et al. An adaptive tag anticollision protocol in RFID wireless systems ［J］.China Communications，2014，11（7）： 117127.

［9］賀曉霞，賈小林.基于并行匹配的RFID自適應碰撞樹算法［J］.計算機工程與設計，2020，41（8）：2190-2194.（He Xiaoxia，Jia Xiaolin.RFID adaptive collision tree algorithm based on parallel matching ［J］.Computer Engineering and Design，2020，41（8）：2190-2194.）

［10］Jia Xiaolin，Bolic M，Feng Yuhao，et al.An efficient dynamic anticollision protocol for mobile RFID tags identification［J］.IEEE Communications Letters，2019，23（4）：620-623.

［11］Singhal K.Walsh codes，PN sequences and their role in CDMA technology［EB/OL］.（2012）.https：//api.semanticscholar.org/CorpusID：9269739.

［12］何怡剛，佘培亮，佐磊，等.可并行識別的UHF RFID防碰撞算法研究［J］.計算機應用研究，2020，37（2）：493-497.（He Yigang，She Peiliang，Zuo Lei，et al.Research on UHF RFID anticollision algorithm with parallel identification［J］.Application Research of Computers，2020，37（2）：493-497.）