基于碰撞位特征值的RFID標(biāo)簽識別算法研究

收稿日期：2023-06-29

基金項(xiàng)目：廣州市基礎(chǔ)與應(yīng)用基礎(chǔ)研究項(xiàng)目（2023A04J0379）；廣東省教育廳特色創(chuàng)新項(xiàng)目（2022KTSCX253）；廣東省教育廳青年創(chuàng)新人才項(xiàng)目（2022WQNCX145）；廣東省繼續(xù)教育質(zhì)量提升工程項(xiàng)目（JXJYGC2021KY0631）；2023年全國高等院校計(jì)算機(jī)基礎(chǔ)教育研究會“計(jì)算機(jī)基礎(chǔ)教育教學(xué)研究項(xiàng)目”（2023AFCEC204）

DOI：10.19850/j.cnki.2096-4706.2024.03.037

摘" 要：“萬物智聯(lián)”網(wǎng)絡(luò)中系統(tǒng)感知層將部署海量標(biāo)簽，為快速獲取粘貼標(biāo)簽的物品信息，設(shè)計(jì)一種基于特征值策略的標(biāo)簽防碰撞算法，結(jié)合電子標(biāo)簽ID識別碼的二進(jìn)制特性和異或運(yùn)算，可準(zhǔn)確地推斷出任意兩位碰撞位，以此消除對無效節(jié)點(diǎn)的查詢，加快查詢進(jìn)程。仿真實(shí)驗(yàn)結(jié)果表明，所提算法可有效減少空閑時(shí)隙和總查詢次數(shù)，提高系統(tǒng)效率，當(dāng)標(biāo)簽數(shù)量為20 000時(shí)，算法的系統(tǒng)效率達(dá)0.43，對比經(jīng)典的查詢樹算法提高了24%，總查詢次數(shù)減少了10 905。

關(guān)鍵詞：射頻識別；標(biāo)簽防碰撞；特征值；樹算法

中圖分類號：TP301.6" " 文獻(xiàn)標(biāo)識碼：A" 文章編號：2096-4706（2024）03-0176-06

Research on RFID Label Identification Algorithm Based on Collision Bit Eigenvalue

FU Yu1， ZHU Hongxu1， LIU Xin2， WEN Congmin1

（1.Computer Engineering Technical College （Artificial Intelligence College）， Guangdong Polytechnic of Science and Technology， Zhuhai" 519090， China; 2.Noncommissioned Officer Institute Army Academy of Armored Forces， Changchun" 130000， China）

Abstract： Massive labels will be deployed in the system perceptive layer of“Artificial Intelligence amp; Internet of Things （AIoT）”network. To quickly obtain information about items with pasted labels， a label anti-collision algorithm based on eigenvalue strategy is designed. By combining the binary characteristics of electronic label ID identification codes and exclusive or operation， any two collision bits can be accurately inferred， thereby eliminating queries for invalid nodes and accelerating the query process. The simulation results show that the proposed algorithm reduces the idle time slot and the total number of queries effectively， and improves the system efficiency. When the number of labels is 20 000， the system efficiency of the proposed algorithm reaches 0.43， which is 24% higher than that of the classical query tree algorithm， and the total number of queries decreased by 10 905.

Keywords： RFID; label anti-collision; eigenvalue; tree algorithm

0" 引" 言

2021年12月27日，中央網(wǎng)絡(luò)安全和信息化委員會印發(fā)的《“十四五”國家信息化規(guī)劃》中部署了10項(xiàng)重大任務(wù)，第一項(xiàng)即是建設(shè)泛在智聯(lián)的數(shù)字基礎(chǔ)設(shè)施體系，涵蓋了以物聯(lián)網(wǎng)、大數(shù)據(jù)、5G等新一代信息技術(shù)演化生成的新型基礎(chǔ)設(shè)施。“萬物智聯(lián)”即“人工智能+物聯(lián)網(wǎng)”，為實(shí)現(xiàn)更全面的聯(lián)接和更透徹的感知，在物聯(lián)網(wǎng)感知層射頻識別（Radio Frequency Identification， RFID）系統(tǒng)中部署海量標(biāo)簽，從而達(dá)到定位、監(jiān)控、追蹤等目的。射頻識別技術(shù)作為感知層的關(guān)鍵技術(shù)之一，是一種低功耗、無接觸式、自動識別技術(shù)。

RFID系統(tǒng)主要由閱讀器和電子標(biāo)簽組成[1]，二者之間利用空間的射頻信號空間耦合實(shí)現(xiàn)雙向數(shù)據(jù)的無線通信[2]。每個(gè)電子標(biāo)簽具有全球唯一的ID標(biāo)識[3]，其體積小、成本低、抗污染能力強(qiáng)，通常粘貼于物體表面，可重復(fù)使用；閱讀器通過發(fā)送指令控制與標(biāo)簽的通信，用于讀取標(biāo)簽ID，以此達(dá)到識別物的目的。通過RFID技術(shù)能夠?qū)崿F(xiàn)數(shù)字基礎(chǔ)設(shè)施終端獲取海量數(shù)據(jù)信息的功能。

RFID技術(shù)已廣泛應(yīng)用于供應(yīng)鏈管理、庫存管理、物流運(yùn)輸?shù)阮I(lǐng)域[4]。如2022年北京冬奧會期間運(yùn)用RFID技術(shù)，將所有食物全部配備標(biāo)簽實(shí)現(xiàn)全程監(jiān)控溯源；冬奧版行李條嵌入RFID芯片，支持行李全流程跟蹤功能。在這些過程中，RFID的無接觸式識別能力發(fā)揮了至關(guān)重要的作用。在數(shù)字基礎(chǔ)設(shè)施體系終端加快部署RFID系統(tǒng)有助于數(shù)字化發(fā)展，推動數(shù)字中國建設(shè)。

RFID標(biāo)簽識別算法的研究能為國家數(shù)字化轉(zhuǎn)型提供關(guān)鍵技術(shù)支撐。RFID閱讀器和標(biāo)簽通信使用單一通信信道，而標(biāo)簽自身無法感知其他標(biāo)簽的存在，只能根據(jù)閱讀器指令傳輸信息，當(dāng)多個(gè)標(biāo)簽同時(shí)發(fā)送ID給閱讀器時(shí)會發(fā)生信號干擾，出現(xiàn)多標(biāo)簽碰撞問題，影響閱讀器獲取標(biāo)簽數(shù)據(jù)[5，6]。在未來的泛在智聯(lián)的數(shù)字基礎(chǔ)設(shè)施體系中，勢必存在高密集度標(biāo)簽，出現(xiàn)的碰撞問題將導(dǎo)致識別標(biāo)簽消耗的時(shí)間過長，大大降低系統(tǒng)的識別效率。本文提出的基于碰撞位特征值的RFID標(biāo)簽識別算法，結(jié)合了電子標(biāo)簽ID識別碼的二進(jìn)制特性和異或運(yùn)算，設(shè)計(jì)一種特征值策略，準(zhǔn)確地判斷出非相鄰兩個(gè)碰撞位的數(shù)據(jù)，減少無效時(shí)隙數(shù)量，加快系統(tǒng)識別標(biāo)簽的查詢進(jìn)程。

1" 傳統(tǒng)基于樹的確定性算法

傳統(tǒng)樹算法不存在標(biāo)簽長時(shí)間不被閱讀器識別的問題，是一種確定性算法。基于樹的經(jīng)典算法有二進(jìn)制搜索樹（Binary Search， BS）算法[7]和查詢樹（Query Tree， QT）算法[8]等。

在BS算法中標(biāo)簽接收來自閱讀器的一串搜索ID后，與自身ID對比，不大于搜索ID的標(biāo)簽響應(yīng)閱讀器的查詢。如果發(fā)生碰撞，則先查詢0分支再查詢1分支。查詢0分支，如果不發(fā)生碰撞，則識別該標(biāo)簽，如果發(fā)生碰撞則查詢00分支和01分支，先查詢00分支，由此遞歸性地分成小分支，直到分支內(nèi)只有一個(gè)標(biāo)簽可被識別。每識別標(biāo)簽后返回起始點(diǎn)重新開始搜索，當(dāng)所有標(biāo)簽均被識別后算法結(jié)束[9]。

為提高識別進(jìn)程效率，BC-SBT算法[10]對BS算法進(jìn)行了改進(jìn)，設(shè)計(jì)一種轉(zhuǎn)碼規(guī)則，將標(biāo)簽ID中的00、01、10和11通過轉(zhuǎn)碼相應(yīng)地變?yōu)?000、0100、0010和0001，如果發(fā)生碰撞則根據(jù)碰撞位置和算法約定，分時(shí)隙響應(yīng)閱讀器查詢，最后反向轉(zhuǎn)碼，還原標(biāo)簽ID。如果系統(tǒng)中待識別標(biāo)簽數(shù)為n，那么總查詢次數(shù)為Log4（n/2）！+n/2。

在QT算法[11]采用逐位查詢方式，閱讀器會產(chǎn)生一個(gè)查詢前綴，與查詢前綴相同的標(biāo)簽處于活躍狀態(tài)，當(dāng)發(fā)生標(biāo)簽碰撞時(shí)閱讀器將先查詢0分支再查詢1分支，即在查詢前綴后分別添加0和1，放入查詢堆棧中，直到?jīng)]有任何小分支發(fā)生碰撞為止。每次識別分支內(nèi)的標(biāo)簽后，不需要像BS算法返回至起始點(diǎn)。4aryQT算法以QT算法為基礎(chǔ)[12]，改變了查詢位數(shù)，由逐位查詢變?yōu)槎辔徊樵儯l(fā)生標(biāo)簽碰撞時(shí)將產(chǎn)生四種分支：00、01、10和11。當(dāng)標(biāo)簽數(shù)量增加時(shí)，4aryQT與QT相比，增加了查詢步長，碰撞時(shí)隙數(shù)降低。

以上提到的算法一定程度上提高了系統(tǒng)吞吐率，但仍然存在查詢次數(shù)多、識別效率較低的問題，因此本文提出了一種基于碰撞位特征值的樹算法（Protocol based on Collision Bit Eigenvalue， TCBE），結(jié)合了查詢樹算法，可準(zhǔn)確推斷出任意兩個(gè)碰撞位，大大地減少對無效節(jié)點(diǎn)的查詢，縮短查詢進(jìn)程。

2" 算法描述

依據(jù)RFID標(biāo)簽ID識別碼全球唯一性且編碼僅由0、1組成，利用數(shù)學(xué)中異或運(yùn)算特點(diǎn)，設(shè)計(jì)一種特征值策略。RFID閱讀器通過和標(biāo)簽交互信息，告知接收的響應(yīng)數(shù)據(jù)中兩個(gè)碰撞位（可非連續(xù)的碰撞位）位置，標(biāo)簽基于碰撞位的特征值策略返回組號，使得閱讀器可直接判斷碰撞位，通過算法設(shè)計(jì)大幅減少空閑時(shí)隙影響，解決傳統(tǒng)確定性樹算法標(biāo)簽識別效率低的問題。

2.1" 特征值策略

假設(shè)閱讀器有一個(gè)記錄存儲查詢前綴的堆棧S，符合先進(jìn)先出原則，即先進(jìn)入S中的查詢前綴其優(yōu)先級最高，將被優(yōu)先彈出堆棧進(jìn)行查詢。對于標(biāo)簽ID的第m位和第n位分別表示為qm和qn。如果qm和qn經(jīng)異或運(yùn)算后等于1，則特征值E為1；如果qm和qn經(jīng)異或運(yùn)算后等于0，則特征值E為0。由此基于特征值策略的分組情況如下：E = 1組中qm、qn分別為0和1或者1和0；E = 0組中qm、qn分別為0和0或者1和1，如表1所示。

表1" 特征值策略的分組情況

特征值 qm qn

E = 1 0 1

1 0

E = 0 0 0

1 1

如果閱讀器接收到來自E = 1組中碰撞標(biāo)簽響應(yīng)字符串的第a位和第b位分別是碰撞位即Xa、Xb，根據(jù)表1可判斷Xa和Xb一定是互異的兩個(gè)值，即為0和1，由此推斷碰撞位的數(shù)據(jù)組合應(yīng)為Xa = 1、Xb = 0和Xa = 0、Xb = 1。如果Xa、Xb來自E = 0組，那么可判斷Xa和Xb是相同的值，推斷出碰撞位的數(shù)據(jù)組合為Xa = 0、Xb = 0和Xa = 1、Xb = 1。如果利用傳統(tǒng)的四叉查詢樹算法識別這兩個(gè)標(biāo)簽，將會額外增加兩個(gè)空閑時(shí)隙。可見，本文提出的特征值策略推斷傳輸數(shù)據(jù)可減少無效時(shí)隙。

2.2" 基于碰撞位特征值的RFID標(biāo)簽識別算法

以特征值策略為基礎(chǔ)，研究一種基于碰撞位特征值的RFID標(biāo)簽識別算法。閱讀器接收標(biāo)簽響應(yīng)的數(shù)據(jù)，直到接收到第三位碰撞位為止。然后閱讀器發(fā)送指令給標(biāo)簽指示碰撞位的具體位置，用“1”表示碰撞位，“0”表示非碰撞位置，如果閱讀器發(fā)送1010，表示第一位和第三位是碰撞位。標(biāo)簽接收后，根據(jù)特征值策略向閱讀器返回組號信息。如果組號不發(fā)生碰撞，那么可準(zhǔn)確地推斷出兩種碰撞位的組合方式，如果組號發(fā)生碰撞，那么可直接推斷出四種碰撞位的組合方式。

基于碰撞位特征值的RFID標(biāo)簽識別算法中閱讀器和標(biāo)簽之間的通信指令如下：

QUERY（ε）是查詢指令，閱讀器廣播該指令，其讀取范圍內(nèi)的全部標(biāo)簽響應(yīng)閱讀器的查詢。

QUERY（prefix， CI）是查詢指令，其中CI是碰撞位指示器，CI ∈ （0，1），用“1”表示碰撞位，“0”表示非碰撞位。ID符合前綴為prefix的標(biāo)簽處于激活狀態(tài)，根據(jù)CI獲得碰撞位的具體位置，基于特征值策略返回組號信息給閱讀器。

POP（prefix）是讀寫指令，從查詢前綴堆棧S頂部中彈出prefix作為新一輪識別進(jìn)程的查詢前綴。

PUSH（prefix）是讀寫指令，將新增的查詢前綴prefix存儲在查詢堆棧S底部。

2.2.1" 算法工作流程

下面對基于碰撞位特征值的RFID標(biāo)簽識別算法的實(shí)施步驟進(jìn)行詳細(xì)描述，TCBE算法流程圖如圖1所示。

圖1" TCBE算法流程圖

流程具體描述如下：

1）閱讀器發(fā)送QUERY（ε）查詢指令，其讀取范圍內(nèi)所有的活躍標(biāo)簽均響應(yīng)閱讀器的查詢，發(fā)送自身ID給閱讀器。

2）閱讀器查看是否有標(biāo)簽響應(yīng)查詢。如果沒有標(biāo)簽響應(yīng)，表明當(dāng)前沒有活躍標(biāo)簽，則該時(shí)隙為空閑時(shí)隙，執(zhí)行步驟3）。如果有標(biāo)簽響應(yīng)，執(zhí)行步驟4）。

3）閱讀器查看當(dāng)前的查詢堆棧S是否為空。如果堆棧S為空，表明沒有任何需要查詢的標(biāo)簽ID前綴，算法結(jié)束。如果堆棧S不為空，則表明存在未查詢的標(biāo)簽ID前綴，需要在下一輪輪詢中使用，以獲取系統(tǒng)中待識別標(biāo)簽信息，繼續(xù)執(zhí)行步驟8）。

4）利用曼徹斯特編碼原理，閱讀器查看響應(yīng)的標(biāo)簽ID是否發(fā)生了碰撞。如果沒有標(biāo)簽碰撞，表示只有一個(gè)標(biāo)簽響應(yīng)查詢，該時(shí)隙為可讀時(shí)隙，那么閱讀器可以直接識別該標(biāo)簽，將被識別的標(biāo)簽置于靜默狀態(tài)，繼續(xù)執(zhí)行步驟3）。如果系統(tǒng)發(fā)生了標(biāo)簽碰撞，表示至少有兩個(gè)標(biāo)簽同時(shí)傳輸信號給閱讀器，則該時(shí)隙為碰撞時(shí)隙，繼續(xù)執(zhí)行步驟5）。

5）閱讀器接收標(biāo)簽響應(yīng)的數(shù)據(jù)直到第三位碰撞位為止，然后發(fā)送QUERY（prefix， CI）給標(biāo)簽指示碰撞位的具體位置。假設(shè)第a位和第b位是標(biāo)簽的碰撞位，分別用Xa、Xb表示。標(biāo)簽接收后，根據(jù)特征值策略向閱讀器返回特征值E。

6）閱讀器接收特征值E，判斷其是否發(fā)生碰撞。閱讀器根據(jù)特征值E和特征值策略可推斷出碰撞位的組合方式。如果E不發(fā)生碰撞，可準(zhǔn)確地推斷出兩種碰撞位的組合方式。當(dāng)E = 0時(shí)，則標(biāo)簽的碰撞位為Xa = 0、Xb = 0和Xa = 1、Xb = 1的兩種組合；當(dāng)E = 1時(shí)，則標(biāo)簽的碰撞位為Xa = 0、Xb = 1和Xa = 1、Xb = 0的兩種組合。如果E發(fā)生碰撞，那么可直接推斷出四種碰撞位的組合方式，則標(biāo)簽的碰撞位為Xa = 0、Xb = 0，Xa = 0、Xb = 1，Xa = 1、Xb = 0，Xa = 1、Xb = 1。執(zhí)行步驟7）。

7）閱讀器執(zhí)行PUSH（prefix）讀寫指令，將新產(chǎn)生的查詢前綴壓入堆棧S底部。繼續(xù)執(zhí)行步驟8）。

8）閱讀器執(zhí)行POP（prefix）讀寫指令，從查詢前綴堆棧頂部中彈出prefix作為新一輪輪詢進(jìn)程的查詢前綴。繼續(xù)執(zhí)行步驟2）。

TCBE算法中閱讀器僅接收標(biāo)簽傳輸信息中第三位碰撞位前的數(shù)據(jù)，能節(jié)約傳輸無用比特所消耗的時(shí)間。并且利用碰撞位的特征值策略能有效判斷出傳輸數(shù)據(jù)的組合方式，達(dá)到獲取標(biāo)簽ID的目的，提高了系統(tǒng)的識別效率。

2.2.2" 算法舉例

下面舉例說明RFID系統(tǒng)中采用TCBE算法識別標(biāo)簽的流程步驟。假設(shè)系統(tǒng)中存在5個(gè)待識別標(biāo)簽，分別為標(biāo)簽a：0010001、標(biāo)簽b：1001110、標(biāo)簽c：1000011、標(biāo)簽d：1001101、標(biāo)簽e：1001100。

在第1個(gè)時(shí)隙閱讀器發(fā)送QUERY（ε）指令，標(biāo)簽a、b、c、d、e響應(yīng)查詢，發(fā)送各自ID給閱讀器，閱讀器接收到傳輸信息發(fā)生了碰撞XXX；在第2個(gè)時(shí)隙中閱讀器發(fā)送QUERY（ε， 1011），通過指示的碰撞位和特征值策略標(biāo)簽發(fā)送特征值E，閱讀器收到E = 0，推斷查詢前綴為001和110；由于查詢堆棧S符合先進(jìn)先出的規(guī)則，在第3個(gè)時(shí)隙堆棧S頂部彈出查詢前綴001，僅有標(biāo)簽a響應(yīng)，那么標(biāo)簽a被閱讀器識別后將被置為靜默狀態(tài)，當(dāng)前堆棧S不為空，算法繼續(xù)執(zhí)行；在第4個(gè)時(shí)隙內(nèi)，閱讀器發(fā)送POP（100），符合查詢前綴為100的標(biāo)簽b、c、d、e回復(fù)余下ID信息，發(fā)生了碰撞，閱讀器接收到XXX；在第5個(gè)時(shí)隙中閱讀器發(fā)送查詢指令QUERY（100， 111）后收到來自標(biāo)簽傳輸信息E = 1，可推斷兩個(gè)碰撞位是0、1或者1、0，將10000和10011存儲于堆棧S；在第6個(gè)時(shí)隙內(nèi)閱讀器發(fā)送POP（10000），標(biāo)簽c被查詢；在第7個(gè)時(shí)隙內(nèi)閱讀器廣播POP（10011），標(biāo)簽b、d、e發(fā)生了碰撞，閱讀器端收到信息XX；在第8個(gè)時(shí)隙閱讀器向標(biāo)簽指示碰撞位位置發(fā)送QUERY（10011， 11），然后接收到特征值E發(fā)生了碰撞，推斷存在兩組標(biāo)簽，執(zhí)行PUSH（1001100， 1001101， 1001110， 1001111），在接下來的第9、10、11個(gè)時(shí)隙分別從堆棧S頂部彈出查詢前綴識別標(biāo)簽e、d、b；在第12個(gè)時(shí)隙內(nèi)閱讀器執(zhí)行POP（1001111），沒有任何標(biāo)簽響應(yīng)，該時(shí)隙為空閑時(shí)隙，由于堆棧S為空，因此算法結(jié)束。如表2所示為TCBE算法舉例識別進(jìn)程。

表2" 算法舉例識別進(jìn)程

時(shí)隙 閱讀器發(fā)送指令 接收信息 響應(yīng)標(biāo)簽 查詢堆棧S序列

狀態(tài)

1 QUERY（ε） XXX a、b、c、d、e 空

2 QUERY（ε， 1011） E = 0 a、b、c、d、e （001，100）

3 POP（001） 識別 a （100）

4 POP（100） XXX b、c、d、e 空

5 QUERY（100， 111） E = 1 b、c、d、e （10000，10011）

6 POP（10000） 識別 c （10011）

7 POP（10011） XX b、d、e 空

8 QUERY（10011， 11） E = X b、d、e （1001100，1001101，

1001110，1001111）

9 POP（1001100） 識別 e （1001101，1001110，

1001111）

10 POP（1001101） 識別 d （1001110，1001111）

11 POP（1001110） 識別 b （1001111）

12 POP（1001111） 空閑 無 空

3" 算法性能分析

在RFID標(biāo)簽識別算法中，總查詢次數(shù)是一個(gè)非常重要的性能參數(shù)。閱讀器的總查詢次數(shù)越少，RFID系統(tǒng)識別效率越高。下面從理論角度分析TCBE算法的總查詢次數(shù)和系統(tǒng)識別效率。假設(shè)RFID系統(tǒng)中共有N個(gè)待識別標(biāo)簽，對于一個(gè)滿四叉樹第i層有4i個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)均可包含兩組標(biāo)簽，那么在第i層有2×4i個(gè)組，如圖2所示。

圖2" 滿四叉樹特征值分組結(jié)構(gòu)示意圖

由于每個(gè)標(biāo)簽的響應(yīng)情況相互獨(dú)立，那么在第i層中k個(gè)標(biāo)簽被分配到同一組的概率遵循二項(xiàng)式分布：

（1）

其中，p = 1/（2×4i）表示選擇其中一組的概率。如果沒有任何標(biāo)簽選擇，那么該組空閑的概率是：

（2）

如果只有一個(gè)標(biāo)簽選擇，那么該組能被成功識別的概率是：

（3）

如果超過一個(gè)標(biāo)簽選擇，那么該組發(fā)生標(biāo)簽碰撞的概率是：

（4）

假設(shè)第i層的時(shí)隙總數(shù)用mi表示：

（5）

其中，n0，i表示空閑時(shí)隙數(shù)，當(dāng)?shù)趇-1層的特征值發(fā)生碰撞且至少一組只有一個(gè)標(biāo)簽選擇時(shí)才會在第i層出現(xiàn)空閑時(shí)隙，那么：

（6）

其中，n1，i表示可讀時(shí)隙數(shù)，即第i-1層的特征值不發(fā)生碰撞，且一個(gè)組是空閑、另一組只有一個(gè)標(biāo)簽選擇時(shí)第i層產(chǎn)生可讀時(shí)隙，那么：

（7）

n2，i表示碰撞時(shí)隙數(shù)。即當(dāng)?shù)趇-1層特征值碰撞且兩組內(nèi)均發(fā)生標(biāo)簽碰撞，或特征值不發(fā)生碰撞一組空閑另一組發(fā)生標(biāo)簽碰撞時(shí)，第i層只存在碰撞時(shí)隙。那么：

（8）

根據(jù)式（5）至式（8）得到：

（9）

當(dāng)i = 0時(shí)，根節(jié)點(diǎn)必發(fā)生碰撞，且僅有一個(gè)時(shí)隙是碰撞時(shí)隙，即n2，0 = 1，那么根據(jù)式（9）得到：

（10）

對于每一層的P（N，0）i和P（N，1）i都可以通過式（2）和式（3）計(jì)算得到。通過式（9）和式（10）可知m2、m3、m4等各層時(shí)隙總數(shù)，那么系統(tǒng)總查詢次數(shù)Q（m）表示為：

（11）

系統(tǒng)效率E表示RFID系統(tǒng)中待讀標(biāo)簽數(shù)與總查詢次數(shù)之比，即E = N/Q（m），當(dāng)標(biāo)簽數(shù)一定時(shí)，總查詢次數(shù)越少，系統(tǒng)的識別效率越高。

4" 實(shí)驗(yàn)分析

為了分析和評價(jià)算法性能指標(biāo)，本文根據(jù)算法工作流程使用MATLAB 2021B仿真平臺進(jìn)行驗(yàn)證，實(shí)驗(yàn)環(huán)境為理想的通信信道，不考慮路徑損耗和捕獲效應(yīng)。本實(shí)驗(yàn)?zāi)M為物聯(lián)網(wǎng)大規(guī)模標(biāo)簽環(huán)境下均勻分布，標(biāo)簽數(shù)量從10 000到20 000范圍內(nèi)變化，標(biāo)簽ID長度為96比特，每次模擬是通過隨機(jī)數(shù)動態(tài)生成，閱讀器遍歷10次并計(jì)算平均值。將QT算法、4aryQT算法、BS算法和BC-SBT算法在空閑時(shí)隙、總查詢次數(shù)、系統(tǒng)效率三個(gè)方面進(jìn)行對比。

如圖3所示為TCBE算法、QT算法和4aryQT算法在標(biāo)簽數(shù)和識別過程中產(chǎn)生的空閑時(shí)隙數(shù)的對比。從圖中可以看出，整體趨勢上空閑時(shí)隙數(shù)都隨著標(biāo)簽數(shù)的增加而增多，而TCBE算法在識別過程中所需的空閑時(shí)隙數(shù)最少，且隨著標(biāo)簽數(shù)的增加空閑時(shí)隙數(shù)的上升趨勢也低于其他兩種算法。這是因?yàn)門CBE算法中采用了碰撞位特征值策略，能有效判斷出傳輸數(shù)據(jù)的組合方式，從而減少無效時(shí)隙。

圖3" 三種算法空閑時(shí)隙數(shù)對比

圖4為TCBE、QT、4aryQT、BC-SBT四種算法在標(biāo)簽數(shù)量和閱讀器識別標(biāo)簽過程中產(chǎn)生的查詢次數(shù)的對比。從實(shí)驗(yàn)結(jié)果中可以看出四種算法的總查詢次數(shù)都隨著標(biāo)簽數(shù)量的增多而增加，而本文所提的TCBE算法的總查詢次數(shù)最低。其中QT算法是經(jīng)典的查詢樹算法，逐位查詢，發(fā)生碰撞時(shí)僅需要在查詢前綴后自動添加0和1，不需要像BS算法一樣每次成功識別標(biāo)簽后返回到起始點(diǎn)。BC-SBT算法以BS算法為基礎(chǔ)進(jìn)行改進(jìn)，性能上優(yōu)于BS算法，但是在大規(guī)模標(biāo)簽環(huán)境下劣于QT算法。在面向萬物智聯(lián)應(yīng)用場景下當(dāng)存在大量標(biāo)簽時(shí)碰撞次數(shù)增多，BC-SBT算法將原兩位碰撞位轉(zhuǎn)碼成四位進(jìn)行尋呼，每次發(fā)生碰撞轉(zhuǎn)碼后至少消耗3個(gè)時(shí)隙，分別是確定碰撞位的響應(yīng)時(shí)隙和算法規(guī)定在碰撞位第1位分別為“0”和“1”時(shí)2個(gè)響應(yīng)時(shí)隙，而后續(xù)還為進(jìn)一步識別出標(biāo)簽可能還需要額外的2個(gè)可讀時(shí)隙，所以識別過程中所需要的總查詢次數(shù)最多。4aryQT算法是QT算法的優(yōu)化，是一個(gè)四叉樹結(jié)構(gòu)，查詢前綴為2個(gè)比特位，當(dāng)2個(gè)比特位均發(fā)生碰撞時(shí)有可能產(chǎn)生空閑時(shí)隙，當(dāng)標(biāo)簽數(shù)量成千上萬時(shí)4aryQT算法的總時(shí)隙數(shù)略少于QT算法。本文所提的TCBE算法所需的總裁查詢次數(shù)最少，性能最優(yōu)。與4aryQT算法相似，都采用四叉樹結(jié)構(gòu)，但當(dāng)出現(xiàn)2個(gè)碰撞位時(shí)4aryQT算法不能剔除任何分支，可能產(chǎn)生額外的2個(gè)空閑時(shí)隙，而TCBE算法僅根據(jù)碰撞位的有效信息進(jìn)行傳輸和判斷，不發(fā)生碰撞的比特位直接進(jìn)入到查詢前綴中減少了查詢次數(shù)，且TCBE算法采用基于特征值策略，即使出現(xiàn)2個(gè)碰撞位也可以準(zhǔn)確的推斷其組合，由此減少識別過程中的總查詢次數(shù)。

圖5所示為TCBE、QT、4aryQT、BC-SBT四種算法在標(biāo)簽數(shù)量和系統(tǒng)識別效率的對比。當(dāng)標(biāo)簽數(shù)量是20 000時(shí)，TCBE算法的系統(tǒng)效率為0.43，比QT、4aryQT、BC-SBT算法識別相同數(shù)量標(biāo)簽時(shí)的識別效率各提高24%、23%、48%。從圖中可以看到，當(dāng)存在海量標(biāo)簽時(shí)，4aryQT算法略優(yōu)于QT算法的系統(tǒng)效率，效果不明顯。BC-SBT算法的識別效率最低，且隨著標(biāo)簽數(shù)量的增多系統(tǒng)識別效率呈下降的趨勢。TCBE算法的系統(tǒng)識別效率最優(yōu)，原因在于識別過程中消耗的總時(shí)隙數(shù)最少。當(dāng)標(biāo)簽數(shù)量保持不變時(shí)，算法所需的總查詢次數(shù)越少，系統(tǒng)的識別效率越高。

圖4" 四種算法總查詢次數(shù)對比

圖5" 四種算法系統(tǒng)效率對比

5" 結(jié)" 論

本文針對智能物聯(lián)網(wǎng)絡(luò)RFID系統(tǒng)中大規(guī)模標(biāo)簽場景下的碰撞問題進(jìn)行了深入研究，設(shè)計(jì)一種特征值策略，提出基于碰撞位特征值的RFID標(biāo)簽識別算法。根據(jù)任意兩位碰撞位和特征值信息，閱讀器可直接推斷出碰撞標(biāo)簽傳輸?shù)腎D信息的組合，剔除無效節(jié)點(diǎn)，有效減少總查詢次數(shù)。在系統(tǒng)識別過程中以實(shí)現(xiàn)快速讀取標(biāo)簽信息，突破傳統(tǒng)的經(jīng)典樹防碰撞算法識別效率低的瓶頸。仿真實(shí)驗(yàn)表明，本文提出的算法能夠有效減少無效時(shí)隙數(shù)和總查詢次數(shù)，提高系統(tǒng)的識別效率。

參考文獻(xiàn)：

[1] 莫磊，陳偉，曾方.一種改進(jìn)的信息位編碼自適應(yīng)搜索防碰撞算法 [J].電訊技術(shù)，2018，58（9）：1091-1095.

[2] 張明乾.RFID技術(shù)在寧夏公共圖書館的應(yīng)用研究 [J].現(xiàn)代信息科技，2023，7（9）：146-148+153.

[3] 蘇建，許若鈺，姚永雷，等.基于比特查詢的多進(jìn)制樹標(biāo)簽防碰撞識別協(xié)議 [J].電子學(xué)報(bào)，2019，47（2）：422-427.

[4] 張莉涓，范明秋，雷磊，等.捕獲效應(yīng)下基于比特檢測的多分支樹RFID標(biāo)簽識別協(xié)議 [J].通信學(xué)報(bào)，2021，42（11）：205-216.

[5] JIA X L，F(xiàn)ENG Y H，GU Y J. A Simple and Fast Anti-collision Protocol for Large-Scale RFID Tags Identification [J].KSII Transactions on Internet and Information Systems，2020，14（4）：1460-1478.

[6] LIANG X Y，GUO Y J. A Probability-Based Anti-Collision Protocol for RFID Tag Identification [J].Wireless Personal Communications，2019，107（1）：57-79.

[7] FINKENZELLER K.RFID Handbook： Radio-Frequency Identification Fundamentals and Applications [M].New York：John Wiley and Sons，2003.

[8] SAMSAMI M M，YASREBI N. Novel RFID anti-collision algorithm based on the Monte–Carlo query tree search [J].Wireless Networks，2021，27（1）：621-634.

[9] 莫磊，唐斌，房夢旭.一種減少通信復(fù)雜度的RFID搜索樹防碰撞算法 [J].電訊技術(shù)，2021，61（10）：1297-1301.

[10] 史長瓊，夏廣偉，嚴(yán)利輝.分時(shí)隙的比特轉(zhuǎn)換RFID標(biāo)簽防碰撞算法 [J].計(jì)算機(jī)工程與應(yīng)用，2018，54（11）：91-96.

[11] SU J，SHENG Z G，LIU A X，et al. A Group-Based Binary Splitting Algorithm for UHF RFID Anti-Collision Systems [J].IEEE Transactions on Communications，2015，68（2）：998-1012.

[12] 周艷玲，曹晶，張?jiān)葡?單堆棧查詢碼遞增深度混合查詢樹防碰撞算法 [J].滄州師范學(xué)院學(xué)報(bào)，2022，38（1）：31-37.

作者簡介：付鈺（1990—），女，漢族，吉林吉林人，

教師，博士，研究方向：RFID技術(shù)、物聯(lián)網(wǎng)應(yīng)用；朱弘旭（1986—），女，山西大同人，講師，博士，研究方向：傳感技術(shù)、RFID和大數(shù)據(jù)；劉鑫（1990—），女，漢族，黑龍江大慶人，講師，博士，研究方向：無線通信與信號處理；文聰敏（1990—），女，漢族，湖南岳陽人，助教，碩士，研究方向：計(jì)算機(jī)應(yīng)用和通信。