基于RFID的多叉樹防沖撞算法研究

王碩 孫知信

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

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

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

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

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

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

在該文中，針對確定性算法所存在的缺點(diǎn)提出一種基于分裂樹的防沖突算法。稱為多叉樹動態(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)的原因，無論怎么樣都可以最終都會被查詢到，也就是說，在確定性防碰撞算法的閱讀器掃描區(qū)域中，每一個RFID標(biāo)簽最終都可以被掃描到。圖1二叉樹防碰撞算法樹形結(jié)構(gòu)圖。

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

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

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

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

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

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

3.1 算法改進(jìn)

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

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

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

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

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

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

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

則其Lk的公式為：

（1）

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

（2）

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

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

（3）

（4）

（5）

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

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

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

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

4? 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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