王碩 孫知信

摘? 要：射頻識別技術(shù)目前在生活中被廣泛使用，其具有識別質(zhì)量高、適應度強且成本較低的優(yōu)點。但是，目前在多目標環(huán)境下，會出現(xiàn)識別沖突的現(xiàn)象，降低識別效率。為此，該文提出一種基于多叉樹動態(tài)分裂機制的防碰撞算法，在二叉樹確定性防碰撞算法的基礎(chǔ)上，引入多叉樹分裂機制，并對插槽結(jié)點碰撞機制進行優(yōu)化，對重復結(jié)點進行跨越式讀取，減少插槽使用個數(shù)，提高標簽命中幾率。通過仿真測試可以看出，該文所提出的算法在多標簽讀取速度上有所提高，在實際的使用中有著重大的意義。

關(guān)鍵詞：RFID 防碰撞算法? 多叉樹? 分裂? 動態(tài)

中圖分類號：TP3? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A文章編號：1672-3791（2021）04（b）-0048-04

Research on Multi Tree Anti-Collision Algorithm Based on RFID

WANG Shuo? SUN Zhixin

（School of Modern Posts， Nanjing University of Posts and Telecommunications， Nanjing， Jiangsu Province， 210003? China）

Abstract： Radio frequency identification technology is widely used in our daily life， which has the advantages of high identification quality， strong adaptability and low cost. However， in the current multi-target environment， there will be recognition conflicts， which will reduce the recognition efficiency. Therefore， this paper proposes an anti-collision algorithm based on multi tree dynamic splitting mechanism. On the basis of binary tree deterministic anti-collision algorithm， the multi tree splitting mechanism is introduced， and the slot node collision mechanism is optimized. The repeated nodes are read by leaps and bounds to reduce the number of slots and improve the tag hit probability. Through the simulation test， we can see that the algorithm proposed in this paper has improved the speed of multi tag reading， which has great significance in practical use.

Key Words： RFID; Anti-collision algorithm; More tree; Division; dynamic

隨著物聯(lián)網(wǎng)時代的到來，射頻識別技術(shù)（Radio Frequency Identification，RFID）[1-2]的普及使得在我們的生活中相應的技術(shù)應用的場景越來越多，如：商品售賣、貨物運輸、食品溯源等多方面進行應用。RFID系統(tǒng)的使用不單單是一個電子標簽，而是多種物聯(lián)網(wǎng)技術(shù)的結(jié)合。一個RFID系統(tǒng)主要包括電子標簽、讀取器和數(shù)據(jù)處理系統(tǒng)。當使用閱讀器對電子標簽進行讀取時，其會通過數(shù)據(jù)傳輸通道讀取數(shù)據(jù)到達數(shù)據(jù)處理系統(tǒng)。但是，當在閱讀器的掃描區(qū)域內(nèi)出現(xiàn)多個標簽時，由于其閱讀器只存在一個數(shù)據(jù)傳輸通道，這時，多標簽之間產(chǎn)生了相互干擾，如果產(chǎn)生碰撞則會導致識別時間的增加且影響系統(tǒng)的效率，導致閱讀器無法識別標簽。這就是RFID系統(tǒng)中標簽碰撞問題。

1? 相關(guān)技術(shù)研究

RFID防沖突算法可以分為確定性算法和不確定性算法。不確定性算法主要是ALOHA算法[3]。其基本思想是：當多個標簽同時進入到掃描器中，則掃描器命令其作用范圍內(nèi)的所有標簽延遲一段時間再進行響應，其延遲時間是隨機選擇的。但是由于ALOHA算法容易發(fā)生碰撞問題，尤其是部分沖突易于發(fā)生。不確定性算法的優(yōu)點在于簡單、快速，但是識別性能不夠穩(wěn)定，處理大量標簽時會出現(xiàn)處理時間較長的問題。確定性算法主要基于二叉樹進行實現(xiàn)的算法。確定性防碰撞算法雖然對RFID系統(tǒng)的要求更高，但是其算法不存在不穩(wěn)定的情況，在處理大量標簽時其性能較不確定防碰撞算法更有優(yōu)勢。

金迪[4]對RFID沖突的問題提出了一種并發(fā)執(zhí)行的后退式二進制RFID防沖突算法，通過并發(fā)執(zhí)行多線程技術(shù)同步運行多個獨立的程序片段，解決沖入問題，提高系統(tǒng)效率。江岸、羅小平[5]則提出一種基于時隙沖突判斷的RFID防碰撞的算法，該算法在時隙前就對碰撞探測碼進行判斷，判斷是否會產(chǎn)生碰撞，以此為根據(jù)消除空閑的時隙。當發(fā)生探測碼碰撞時，結(jié)合沖突位置和時隙規(guī)避機制可以有效地降低碰撞時隙的概率。陳清等人[6]對于木制品多目標掃描時出現(xiàn)的沖突問題，在動態(tài)幀時隙ALOHA防沖突算法的基礎(chǔ)上，采用概率學方法進行研究，提出一種智慧防沖突算法。張榮華等人[7]針對樹的防碰撞算法效率較低的問題，利用在樹型結(jié)構(gòu)中的沖突位分布信息，提出一種基于沖突分段的動態(tài)樹型防沖突算法。蘇健、溫廣軍等人[8]提出了一種基于二進制搜索算法的IACA算法。在RFID標簽發(fā)生碰撞時，閱讀器會根據(jù)曼徹斯特代碼的特點確定碰撞的位置，并分別查詢最高的兩位碰撞位，查詢命令位設置為1。當電子標簽ID小于或等于查詢命令時，電子標簽向讀取器返回響應命令以發(fā)送自己的ID信息，從而減少碰撞概率，減少閱讀標簽時間。LAIYC等[9]提出了一種最佳的二進制跟蹤樹協(xié)議，在這種算法中，標簽被一次次地拆分成更小的分組進行識別。

在該文中，針對確定性算法所存在的缺點提出一種基于分裂樹的防沖突算法。稱為多叉樹動態(tài)防碰撞算法（Multi-tree Dynamic Anti-Collision Algorithm，MDACA）。

2? 相關(guān)算法研究

2.1 二叉樹算法

確定性防碰撞算法主要是基于樹形結(jié)構(gòu)思想發(fā)展而來，之所以被稱為確定性算法，是因為根據(jù)樹的節(jié)點不斷衍生子節(jié)點的原因，無論怎么樣都可以最終都會被查詢到，也就是說，在確定性防碰撞算法的閱讀器掃描區(qū)域中，每一個RFID標簽最終都可以被掃描到。圖1二叉樹防碰撞算法樹形結(jié)構(gòu)圖。

從圖1中可以看出，在第一層的一個節(jié)點會分成兩個節(jié)點，可以看出第二層的兩個節(jié)點依然沖突，所以還會再次分裂，直到節(jié)點不再有沖突發(fā)生。

我們可以根據(jù)不同的遍歷樹的方法得到多種，但在解決沖突所需的插槽個數(shù)方面，它們本質(zhì)上是相同的。在這個例子中，它們需要相同數(shù)量的插槽來解決初始結(jié)點5個標簽的沖突，即10個插槽。

2.2 改進二叉樹防碰撞算法

在二叉樹中，每一個節(jié)點都可以在下一級分成兩個新的節(jié)點。通過這個機制，可以對沖突的節(jié)點進行分割?？梢詫_突的插槽分成兩個子插槽，如果第一個子組是空閑的，則可以確定第二個子組是沖突。因此，通過假裝已經(jīng)發(fā)生碰撞，僅通過將第二子組分成兩個子組就可以減少時隙浪費，具體見圖2。

從圖2可以看到在對碰撞標簽進行處理時，相對于原始二叉樹防碰撞算法的效率更高。

3? 多叉樹動態(tài)防碰撞算法

3.1 算法改進

改進二叉樹算法雖然解決了二叉樹算法的一些插槽浪費的問題，但是在實際的使用中，其分裂節(jié)點的效率仍然較低。為此，在此基礎(chǔ)上再次改進，引入多叉樹分裂機制進行碰撞標簽分裂。提出了一種多叉樹動態(tài)防碰撞算法（MDACA）。該算法具有以下改進方向。

（1）該算法在基于樹的防碰撞算法的基礎(chǔ)上進行改進，提出使用多叉樹分裂機制對防碰撞標簽進行分裂，提高標簽讀取效率。

（2）為了減少時隙的浪費，針對碰撞標簽，如果此標簽左插槽為空閑插槽，則通過改進二叉樹防碰撞算法思想，對重復父插槽的子插槽進行不讀取機制。

（3）多叉樹中沖突插槽分裂處理問題，針對其插槽中標簽個數(shù)按照（n/2）+1的機制對插槽進行分裂。其中n為該次標簽沖突時標簽的個數(shù)。

（4）在多叉樹動態(tài)防碰撞算法中，對插槽分裂后的子插槽分裂順序進行左分支優(yōu)先處理原則，在進行分裂處理時先對左分子插槽處理，直至只包含一個節(jié)點或者0個節(jié)點。這樣保證標簽碰撞處理的順序和有效性。

（5）在多叉樹動態(tài)防碰撞算法中，對碰撞插槽進行遍歷時，對各插槽標簽數(shù)進行計數(shù)。為了增加標簽命中率，在確保某個插槽（只包含2個插槽）為沖突插槽時，直接采取讀取這兩個插槽，提高RFID系統(tǒng)標簽讀取效率。

如圖3所示，對碰撞節(jié)點（A，B，C，D，E）進行處理，按照該章提出的MDACA算法思想，采用（n/2）+1公式計算，可得知在對初始插槽使用三分裂機制進行插槽分裂處理。按照所提出的左子集優(yōu)先處理原則，先對級別2中的（A，B）插槽進行處理，在對級別2中的（A，B）沖突插槽進行處理時，因其左子集插槽為空閑插槽，所以右子集必定為沖突插槽，為了減少時隙的浪費，不對級別3中的（A，B）進行掃描。最后對最右子集（D，E）進行處理時，因知道其子集個數(shù)，其必定為沖突插槽，所以直接掃描其D、E兩個插槽子集。這樣，在5個碰撞標簽的情況下，只需要7個插槽就可以解決。

則其Lk的公式為：

（1）

通過對所提出算法所需要的平均時隙進行分析，其效率公式為：

（2）

其中，T（N）是識別N個沖突標簽所需的平均時隙數(shù)。

對MDACA算法中使用的平均時隙公式進行推導，可得出：

（3）

（4）

（5）

其中p是隨機概率，且認為TMDACA（0）=TMDACA（1）=0，表示插槽中只包含0個或1個結(jié)點不再沖突，無需再次分割。q為多叉樹算法進行分裂的概率，該文提出的算法中使用隨機概率round。其中B（N，1/Li，0）表示初始第i層的標簽個數(shù)，B（N，1/Li，1）表示閱讀器掃描第i層時掃描成功的幾率。

3.2 算法實現(xiàn)

通過matlab對提出的MDACA算法進行仿真，與MTA算法、PNBA算法進行對比，由圖4可看出，在一定范圍內(nèi)多標簽存在的情況下，閱讀器一次性正確讀取的標簽個數(shù)，BTDCAA算法讀取的個數(shù)更多，其效率更高。

從實驗結(jié)果中可以看出，該文所提出的改進算法在進行碰撞標簽處理時讀取效率比原始的二叉樹防碰撞確定算法和改進二叉樹算法都有提高。

4? 結(jié)語

該文所提出的多叉樹動態(tài)防碰撞算法在改進二叉樹算法的基礎(chǔ)上引入多叉樹動態(tài)分裂機制，并對分支分裂進行改進，使其按照左子樹優(yōu)先分裂原則，遇到非碰撞結(jié)點結(jié)束，并在讀取時實現(xiàn)跨越式讀取，省去讀取重復插槽，減少插槽使用個數(shù)，從而提高讀取正確率和時間效率。其在實際的使用中有著深刻的意義。

參考文獻

[1] 王大偉.基于RFID的物流管理系統(tǒng)設計及應用[J].電子設計工程，2016，24（20）：66-68，71.

[2] 馬宗正，馬海舒，馬濤.基于射頻識別技術(shù)的工件定位系統(tǒng)設計與實現(xiàn)[J].現(xiàn)代制造工程，2017，50（7）：109-113.

[3] Hu haiyan，yan hui.Study on ALOHA Anti-Collision Algorithm Based on LoRa for Internet of Things[C]//2018 3rd International Conference on Smart City and Systems Engineering （ICSCSE）. IEEE，2018：652-654.

[4] 金迪.RFID包裝系統(tǒng)中防沖突算法研究[J].包裝工程，2018，39（1）：1-5.

[5] 江岸，羅小平.基于時隙沖突預判的RFID防碰撞算法[J].計算機工程與設計，2017，38（7）：7-13.

[6] 陳清耀，林宇洪，邱榮祖.基于RFID木制品物流多目標識別算法的優(yōu)化[J].福建農(nóng)林大學學報：自然科學版，2016，45（4）：476-480.

[7] 張榮華，張海周，楊大志，等.基于沖突分段的動態(tài)樹型RFID防碰撞算法[J].計算機工程與應用，2017，53（17）：117-121.

[8] 蘇健，溫廣軍，韓佳麗.一種基于ISO18000-6B標準的RFID防碰撞算法[J].電子學報，2014，42（12）： 2515-2519.

[9] LAI Y C，HSIAO L Y，LIN B S.Option slot assignment for binary tracking tree protocol in RFID tag identification[J].IEEE/ACM Transactions on Networking（TON），2015，23（1）：255-268.