王碩 孫知信

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

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

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

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

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

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

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

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

2.1 二叉樹算法

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

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

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

2.2 改進(jìn)二叉樹防碰撞算法

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

從圖2可以看到在對(duì)碰撞標(biāo)簽進(jìn)行處理時(shí)，相對(duì)于原始二叉樹防碰撞算法的效率更高。

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

3.1 算法改進(jìn)

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

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

（2）為了減少時(shí)隙的浪費(fèi)，針對(duì)碰撞標(biāo)簽，如果此標(biāo)簽左插槽為空閑插槽，則通過改進(jìn)二叉樹防碰撞算法思想，對(duì)重復(fù)父插槽的子插槽進(jìn)行不讀取機(jī)制。

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

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

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

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

則其Lk的公式為：

（1）

通過對(duì)所提出算法所需要的平均時(shí)隙進(jìn)行分析，其效率公式為：

（2）

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

對(duì)MDACA算法中使用的平均時(shí)隙公式進(jìn)行推導(dǎo)，可得出：

（3）

（4）

（5）

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

3.2 算法實(shí)現(xiàn)

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

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

4? 結(jié)語

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

參考文獻(xiàn)

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

[2] 馬宗正，馬海舒，馬濤.基于射頻識(shí)別技術(shù)的工件定位系統(tǒng)設(shè)計(jì)與實(shí)現(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] 江岸，羅小平.基于時(shí)隙沖突預(yù)判的RFID防碰撞算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2017，38（7）：7-13.

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

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

[8] 蘇健，溫廣軍，韓佳麗.一種基于ISO18000-6B標(biāo)準(zhǔn)的RFID防碰撞算法[J].電子學(xué)報(bào)，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.