大規模RFID 系統中未知標簽的快速可靠識別

郭凱敏，謝 鑫，馬一杰，齊 恒，李克秋

（1.大連理工大學 計算機科學與技術學院，遼寧 大連 116024；2.香港理工大學 計算機系，香港 100872；3.河南財經政法大學 民商經濟法學院，鄭州 450016）

0 概述

射頻識別（Radio Frequency Identification，RFID）對于已經裝備RFID 標簽且有物品盤點、商品追蹤、供應鏈管理等業務需求的公司及機構具有重要的應用價值［1-3］。相比于二維碼一次識別單個目標的功能，RFID 技術具有識別效率高、長距離/多目標識別、非視距通信等優點［4-6］。未知標簽識別是RFID 領域的基礎問題之一。物品位置的錯誤放置可能帶來難以預測的經濟損失或安全隱患［7-8］，比如有毒有害物品不慎混入食品儲藏區，或由于溫度、濕度、光照、人員管理疏忽等因素影響，導致有毒有害物品的揮發，給食品安全帶來重大威脅。因此及時發現危險物品顯得尤為重要，未知標簽識別問題具有重要研究價值。

傳統的未知標簽識別協議的設計大多基于Aloha 協議［9-11］。閱讀器向標簽發送一個由多時隙組成的時間幀，標簽隨機選擇其中一個時隙回應閱讀器問詢［12］。當有多個標簽選擇同一個時隙回應時，該時隙為沖突時隙，閱讀器收到的信息是多個標簽回應的纏繞信息，而閱讀器不能從纏繞信息中提取任何一個標簽回應信息。因此，在未知標簽識別信息中，沖突時隙會被直接廢棄［13-15］。但廢棄的沖突時隙同樣需要時間來驗證沖突，導致沖突時隙的產生降低了未知標簽的識別效率與時隙利用率。

在含有未知標簽的RFID 系統中，已知標簽的存在會影響未知標簽的識別效率［16］。在未知標簽識別協議執行前，每個已知標簽所選響應時隙可以通過幀長、標簽ID 以及哈希種子預測得到。如果預測一個時隙沒有標簽響應，但在協議執行時該時隙有標簽響應，則可斷定該響應標簽為未知標簽，且當該響應標簽只有一個時，則該標簽ID 可以被順利讀取。未知標簽選擇一個有已知標簽響應的時隙時，未知標簽不能被識別。因此，已知標簽的存在嚴重制約未知標簽的識別效率［17］。在傳統未知標簽識別協議中，已知標簽滅活效率同樣也是協議執行效率的重要衡量標準。

本文提出沖突分解法（Conflict Resolution Method，CRM）協議，通過引入區分碼改進傳統16 位隨機數（16 bit Random Number，RN16），使RN16 不僅具備傳統的沖突檢測功能，而且具備沖突時隙內沖突標簽區分功能。同時采用多哈希的方式，使沖突時隙內的標簽得到區分的概率更大。

1 相關工作

現有的未知標簽識別協議可以分為標簽識別［18-19］、未知標簽檢測［20］、未知標簽識別［21］3 類。這3類協議目前主要存在以下3 個不足：

1）標簽識別旨在收集RFID 系統中標簽ID 信息，通過對比收集到的標簽ID 與服務器中存儲的已知標簽ID，即可發現未知標簽。雖然這種協議可以實現未知標簽識別，但需要收集所有RFID 系統中標簽ID 信息，因此時效性較低。

2）未知標簽檢測協議意在檢測RFID 系統是否存在未知標簽，不必獲取未知標簽ID 信息，因此通常使用概率的方法來優化協議參數設置，但在檢測中會出現假陰性錯誤，即未知標簽的反饋信息被已知標簽覆蓋，導致未知標簽檢測失敗。

3）未知標簽識別協議旨在收集RFID 系統中未知標簽ID 信息，但為了減少已知標簽干擾，通常會把已知標簽滅活，由于假陰性錯誤存在，未知標簽可能會被誤認為已知標簽而被滅活。因此，減少假陰性出現概率成為未知標簽識別協議中不可忽略的問題。

本文旨在提升未知標簽識別的時隙利用率以及識別效率。現有未知標簽識別協議有UTI-SBF［9］、HUTI［10］、PUTI［11］、FUTI［16］、MUIP［17］、TIP［21］等，都 是基于標準Aloha 設計，均面臨著沖突時隙不能被利用的問題。且由于已知標簽滅活效率低，導致未知標簽識別效率過低。ZHU 等［9］利用標簽反饋的物理層信息判斷一個時隙內標簽響應的個數，再利用二次哈希的方式讓沖突標簽重新選擇時隙，雖然這種方式將部分沖突時隙轉化為有用時隙，但一個沒有未知標簽響應的沖突時隙不能被有效滅活，已知標簽的干擾仍然是造成未知標簽識別效率低的主要原因。未知標簽識別效率仍有提升的空間，且在實驗中利用USRP 獲取標簽響應的物理層信息，此種信息在商業RFID 設備中無法獲取。LIU 等［16］利用多哈希方式構建過濾數組，過濾數組能高速過濾已知標簽，使未知標簽被識別的概率增大，然而針對全局的多次哈希運算要消耗大量的時間，沖突時隙也不可避免且無法被利用。LIU 等［17］基于標準Aloha 協議，快速滅活單一時隙中的已知標簽，識別預測空時隙轉變為沖突時隙的未知標簽，但沖突時隙仍然無法被利用，這降低了未知標簽的識別效率。總之，沖突時隙不能被有效利用仍是造成未知標簽識別效率低的主要原因。

針對現有未知標簽協議仍然存在的已知標簽滅活效率較低及沖突時隙無法有效利用的問題，本文提出沖突分解法。CRM 協議能把大部分廢棄的沖突時隙變為有用時隙，從而增大時隙利用率。通過多哈希的方式可以確定沖突時隙內是否有未知標簽存在，如果不存在未知標簽，則該時隙內的標簽被全部滅活，這樣不僅能提高已知標簽的滅活效率，而且能減少已知標簽對未知標簽識別的干擾。此外，還可以有效檢測沖突時隙內的未知標簽，并提取未知標簽ID，提高未知標簽識別成功率與效率。

2 問題描述與系統模型

2.1 問題描述

假設已知的標簽組為S=(a1，a2，…，an)，待檢測標簽組為T=(t1，t2，…，tN)。S和T的數量分別為n和N。n已知且S中的所有標簽ID 均存儲在后臺服務器，閱讀器可以訪問后臺數據庫中已知標簽ID 信息。N未知且N≥n，因此未知系統中出現的未知標簽數量為u(u=N-n)。未知標簽識別的目的是找出待測標簽組T中包含的未知標簽，并讀取其ID 信息。在一個識別可靠度為ω∈[0，1)的RFID 系統中，至少需要識別出的未知標簽數量為ω×u，也就是說未被識別的未知標簽數量為m，且m≤(1-ω)×u。此CRM 協議的目的是最小化執行時間。

2.2 系統模型

一個典型的RFID 系統包含標簽、閱讀器和后臺服務器3 個部分。每個標簽擁有一個獨一無二的識別ID（可被讀/寫），ID 的長度一般為96 位，且系統內所有標簽均存儲一個相同的哈希函數H(·)。后臺服務器存儲標簽ID 信息，并可根據ID 信息實現多樣化的業務需求。因此，標簽根據其ID 是否被收錄可分為已知標簽和未知標簽。閱讀器可獲取標簽ID，是鏈接標簽與后臺服務器的高速通道，閱讀器與后臺服務器可統稱為閱讀器。單個閱讀器的讀取距離為5～12 m，因此，一個較大范圍內的標簽識別監控需要多臺閱讀器交叉協同工作，而每個閱讀器都會收到1 個標簽反饋數組，后臺服務器對所有反饋數組進行位或運算，即可獲取1 個融合反饋數組［6］。RFID 系統中所有閱讀器均可以被看作1 個超強閱讀器，如圖1所示。所有標簽均在此超強閱讀器識別范圍內，閱讀器周期地詢問、識別范圍內的標簽，并搜集標簽反饋信息。

圖1 RFID 系統模型Fig.1 RFID system model

2.3 標準ALOHA 協議

閱讀器與標簽的通信依然遵照標準幀槽Aloha協議設定［22］，CRM 協議執行過程如圖2 所示，其中未知標簽檢測過程包含多個時間幀，每個時間幀含有多個時隙。在每個時間幀開始時，閱讀器向每個標簽發送詢問命令Query，并廣播參數，其中f是每個時間幀中時隙的數量，r是一個隨機的哈希種子。在接收到Query 命令后，每個標簽依照哈希函數隨機選擇一個時隙響應，哈希函數為sc=H(ID，r)modf，其中sc為時隙計數器，H(·)為一個預先存儲在標簽中的哈希函數，ID 為標簽識別碼。因此sc∈[0，f)。此后，閱讀器逐個詢問時間幀中的時隙，當一個時隙詢問結束時，閱讀器向當前時隙發送slot end 命令結束訪問并初始化下一個時隙，而當標簽的時隙計數器sc收到命令后自動減1，當sc為0時，標簽在接下來的時隙中向閱讀器發送預定信息。

圖2 CRM 協議的執行流程Fig.2 Implementation process of CRM protocol

當協議執行完畢后，所有的時隙可以分為3 種狀態：1）空時隙，沒有標簽選擇該時隙；2）單一時隙，僅有一個標簽選擇該時隙并回復閱讀器詢問；3）沖突時隙，有且多于一個標簽選擇該時隙并回復閱讀器詢問。

圖3 所示為標準ALOHA 協議與CRM 協議的對比結果，其中圖3（a）是標準Aloha 協議中，閱讀器對于不同狀態的時隙采用不同的執行過程。對于空時隙，閱讀器發送Query 命令后，等待T1+T3，當沒有標簽響應時，閱讀器終止該詢問并訪問下一個時隙。對于單一時隙，當閱讀器發送Query 命令后，標簽回復一個16 位的隨機數RN16，閱讀器返回標簽一個包含該RN16 信息的ACK 命令，當標簽收到ACK 命令中的RN16 與自己發送的RN16 信息一致時，此標簽回復預設信息并返回閱讀器，閱讀器接收信息完畢。如果此單一時隙的標簽為已知標簽，則閱讀器發送kill 命令，并開始訪問下一個時隙，如果此單一時隙為未知標簽，則閱讀器收集標簽ID，收集結束后開始詢問下一個時隙。對于沖突時隙，標簽向閱讀器發送RN16，RN16 中包含循環冗余校驗碼（Cyclic Redundancy Check，CRC），然而此時閱讀器接收到的RN16 是多個RN16 的融合，CRC 校驗錯誤，則認為此時隙為沖突時隙。在標準Aloha協議中，一個單一時隙、空時隙、以及沖突時隙所消耗的時間分別如下：

圖3 標準ALOHA 協議與CRM 協議的對比Fig.3 Comparison between standard ALOHA protocol and CRM protocol

本文假設閱讀器與標簽通信是在無干擾的條件下進行。根據C1G2 協議［22］，閱讀器向標簽發送數據的速率為26.5 Kb/s，而標簽向閱讀器發送數據的速率為53 Kb/s，即閱讀器向標簽發送1 bit 數據所用的時間為12.5 μs，而標簽向閱讀器發送1 bit數據所用時間為6.25 μs。閱讀器與標簽通信的參數設定如表1 所示，文中變量所表示的含義如表2所示。

表1 基于C1G2 的仿真參數設定Table 1 Simulation parameter setting based on C1G2

表2 主要符號及其注釋Table 2 The main notations and their annotations

3 協議設計

在標準Aloha協議中，沖突時隙以及空時隙被廢棄，直接降低了時隙利用率，導致未知標簽識別效率較低。為解決該問題，本文設計了CRM 協議，其不僅能有效滅活沖突時隙中的已知標簽，而且能識別沖突時隙中的未知標簽，把沖突時隙變為可用時隙，大幅提高已知標簽滅活效率及未知標簽識別效率。

本節將詳細介紹CRM 協議的執行過程，并具體分析CRM 協議的執行優勢，介紹區分碼的設計以及區分碼在未知標簽識別中發揮的作用。

3.1 V-RNx 的設計與引入

在CRM 協議中，本文引入了V-RNx 的規則，與傳 統的RN16 相 比，V-RNx 由Vk以及RNx 組成，其中Vk被稱為區分碼，RNx 被稱為隨機碼。為盡可能地減少對標準Aloha 協議的改變，V-RNx 與傳統RN16都由16 位數據構成，因此k+x=16。RN16 是標簽內部隨機數生成器生成的16 位偽二進制隨機數，具有沖突檢測功能，隨機數個數為216，假如有兩個標簽選擇同一個時隙，沖突被檢測出來的概率為1-16/（216）2，數值接近于1。

假如有w個標簽選擇同一個時隙，沖突被檢測出來的概率為1-16/（216）w，數值無限接近于1。然而在已知標簽識別協議以及未知標簽檢測/識別協議中，在識別效率最高時f=N，此時空時隙的概率為36.8%，單一時隙在f個時隙中所占比例為36.8%，有2 個標簽選擇同一時隙的概率為18.4%，有3 個標簽選擇同一時隙的概率為6.13%，因此，在一個時隙中標簽數量少于4 個的概率為98.13%。也就是說，在優化后的識別協議中，選擇同一個時隙的標簽數量很少，利用16 位隨機數來檢測沖突會造成很大的資源浪費，過多的數據量發送也會導致識別效率下降。V-RNx 把RN16 分成兩部分，長度分別為k和x，長度為k的部分為區分碼且全部初始化為0，長度為x的部分為隨機碼，由標簽內部隨機數生成器生成長度為x的二進制隨機數。假設x的數值為8，如果有2 個標簽選擇同一時隙，則沖突能被檢測出來的概率為1-8/（28）2，其值接近于99.99%，當有w個標簽選擇同一時隙響應時，沖突能被檢測出來的概率為1-8/（28）w，該值無限接近于1。剩余的8 位區分碼數據可以用作分解沖突標簽。

V-RNx 中長度為k的部分用于分解沖突標簽。在CRM 協議執行過程中，假設標簽已經接收到閱讀器的Query 命令以及參數，其中哈希種子統稱為r，此時，標簽除了選擇自己所在時隙外，還要生成自己的區分碼以及隨機數。區分碼初始化為k位0 二進制字符串，標簽利用接收的哈希種子ri(i≤λ)再次進行哈希運算，計算式如式（4）所示：

其中：c為標簽標志位，也就是區分位，當運算完成后，區分碼中第c+1 位變為1，其余位仍然保持為0。這樣，在沖突時隙中，每個沖突標簽都有自己的標志位，當沖突標簽標志位不同時，沖突標簽就能得到區分。當區分位只有一個標簽選擇時，稱之為單一區分位，當沒有標簽選擇時，稱之為空區分位，當有多個標簽選擇時稱之為沖突位。假設在V-RNx 中k的值為8，當有2 個標簽選擇同一時隙時，兩個標簽能夠區分的概率為87.5%，當有3 個標簽選擇同一時隙響應時，至少一個標簽能被區分的概率為98.4%，也就是說，當有w個標簽選擇同一時隙時，任意一個沖突標簽能被區分的概率為，w個沖突標簽能被分解出來的標簽數量為。

3.2 CRM 協議的執行過程

單輪的協議執行無法滿足系統需求，因此，CRM 協議需要執行多輪，且每一輪CRM 的執行過程都包括已知標簽響應時隙選擇以及區分位預測、未知標簽識別、已知標簽滅活共3 個部分。CRM 協議的執行過程如圖2 所示。

3.2.1 已知標簽響應時隙選擇以及區分位預測

3.2.2 未知標簽識別

使用CRM 協議識別未知標簽時，在單一時隙和空時隙上的處理與標準Aloha 協議相同，然而，在沖突時隙的處理上與標準Aloha 協議差別較大。期望映射中區分碼表示為Q。在CRM 協議中，閱讀器首先發布參數，在標簽收到參數后，根據函數sc=H(ID，r1)modf選擇自己所在時隙，并依據函數c=H(ID，ri)modk，(i≤λ)生成自己的區分碼，將實際映射中的區分碼表示為A，如圖4 所示。多哈希種子的使用目的是盡可能把未知標簽從沖突位中區分出來。

圖4 區分碼識別未知標簽的示意圖Fig.4 Schematic diagram of discriminant code identifying unknown tags

在CRM 協議中，時隙的狀態包括空時隙、單一時隙、沖突時隙3 種。

1）空時隙中沒有任何標簽回應閱讀器的Query指令。

2）單一時隙有且僅有一個標簽回復閱讀命令，且在V-RNx 驗證通過后，標簽可以向閱讀器發送特定數據，如果單一時隙是已知標簽，則該標簽會被滅活，不會參與下一輪的未知標簽識別過程。如果該時隙的標簽為未知標簽，則向閱讀器發送標簽ID。

3）沖突時隙有多個標簽同時選擇同一時隙。

在空時隙與單一時隙的執行效率上，CRM 協議與標準Aloha 協議沒有任何區別。然而標準Aloha協議無法解決多標簽信號重疊問題。因此為提高Aloha 協議識別未知標簽的效率，沖突時隙會被直接跳過。但在CRM 協議中，由于區分碼的引入，CRM協議能夠把絕大部分沖突時隙轉變為可用時隙，從而增大時隙利用率，提升已知標簽滅活效率及未知標簽的識別效率。沖突時隙的分解過程如圖3（b）所示，假如k值為4，在期望映射中，標簽區分碼為1000，而在實際映射中標簽區分碼為1001，也就是說Q為1000，A為1001。該沖突時隙里既有已知標簽，也有未知標簽。CRM 協議執行時首先檢測期望映射中該時隙區分碼的A～Q中各位是否全為0，如果全為0，則計算中A～Q中各位的情況，如圖3 所示，此時標簽只回復閱讀器DACK 命令，其中DACK 的長度為k，RNx2 的總長度為k×(λ-1)。如果A～Q位不全為0，則表明未知標簽被區分出來，只需檢測對應非零位的未知標簽是否為單一標簽。如圖3（b）中的（2）～（3）所示，如果該標簽是單一標簽，則該未知標簽ID 可以被順利收集，否則，該區分位不作處理，將繼續檢測下一非零區分位。

在CRM 協議中，被識別的未知標簽不參與下一輪協議執行，以下4 種情況的未知標簽能被識別：

1）當期望映射中的空時隙轉變為單一時隙時，說明有且僅有一個未知標簽響應閱讀器詢問命令，未知標簽可以在reply 中回復標簽ID。

2）當期望映射中的空時隙轉變為沖突時隙時，說明有多個未知標簽選擇同一時隙回應閱讀器詢問命令，當CRM 協議分解沖突時，如果有單一區分位，即有且僅有一個標簽選擇該區分位，則該標簽能夠被識別，否則對應的未知標簽不能被識別，不能被識別的未知標簽將參與下一輪未知標簽識別。

3）當期望映射中的單一時隙在實際映射中變為沖突時隙時，可以確定該時隙有未知標簽，如果λ個哈希種子生成的區分碼A～Q不全為0，且存在單一區分位，則對應的未知標簽能被識別。

4）當期望映射中的沖突時隙在實際映射中仍然為沖突時隙，但兩個沖突時隙區分碼不同時，則未知標簽分布在A～Q中，如果在A～Q中有單一區分位，則該區分位所對應的標簽為能夠被識別的未知標簽，否則為不能被識別的未知標簽。

3.2.3 已知標簽滅活

已知標簽的存在嚴重干擾未知標簽的識別，當已知標簽與未知標簽選擇同一時隙時，會造成未知標簽的假陰性，而區分碼可以降低假陰性的概率。因此在實際映射的沖突時隙中，如果λ個哈希種子A～Q中各位全部為0，則可斷定此時隙中的標簽全為已知標簽，閱讀器發送kill 命令將其直接滅活。

在CRM 協議中，被滅活的已知標簽不參與下一輪未知標簽檢測，減小下一輪協議執行時已知標簽對未知標簽識別的干擾，有兩種情況已知標簽能被滅活，如圖3 中已知標簽滅活部分：

1）當期望映射中的單一時隙在實際映射中仍為單一時隙時，說明有且僅有一個已知標簽選擇該時隙，閱讀器可以向標簽發送kill 指令，直接滅活該標簽。

2）當期望映射中為沖突時隙，在實際映射中仍為沖突時隙，且當λ個哈希種子產生的區分碼A-Q中各位全為0 時，則表明該時隙中的標簽全為已知標簽，則直接執行kill 命令。

4 參數優化

4.1 參數k 的優化

V-RNx 的長度與標準RN16 保持一致，在協議執行過程中V-RNx 的長度不會對未知標簽識別協議的執行效率產生影響。但V-RNx 由區分碼和隨機碼兩部分構成，區分碼的長度為k，隨機碼的長度為(16-k)，區分碼的長度決定了沖突標簽能被區分的概率大小，而隨機碼的長度決定了閱讀器是否能夠準確識別沖突時隙，如果把沖突時隙辨認為單一時隙，閱讀器就會收到錯誤的未知標簽ID，或者把未知標簽誤認為已知標簽滅活。在標準Aloha 協議中，如果有w(w＞1)個標簽選擇同一個時隙，沖突被檢測出來的概率為1-16/(216)w，即同一時隙標簽越多，沖突檢測越容易。因此，至少要保證2 個標簽的沖突時隙能夠被準確識別。在V-RNx 中，此種沖突時隙能被準確識別的概率為1-(16-k)/(216-k)2，2 個標簽能被區分的概率為(k-1)/k。當k=8 時，兩個標簽的時隙能被準確識別為沖突的概率為99.99%，兩個標簽能被區分的概率為87.5%。為滿足沖突檢測以及沖突標簽區分的需要，本文在優化f時將k值設為8。

4.2 哈希種子數量λ 及幀長f 的優化

幀長f過大將產生過多的空時隙，影響未知標簽識別的效率，然而當f值過小時，會產生大量的沖突時隙。在沖突時隙中，當未知標簽與已知標簽產生相同的區分碼，則未知標簽會被認為是已知標簽而被滅活，產生假陰性的問題。為提高未知標簽的識別效率及降低假陰性產生的概率，選擇合適的f值至關重要。為此，要保證沖突時隙足夠多，且沖突時隙中標簽數量足夠少。

假設一個沖突時隙中有z個已知標簽，y個未知標簽，則當y值為1 時，產生假陰性的概率最大；當y值變大時，假陰性反而變小。因此，當y值為1 時，假陰性的概率如式（5）所示：

假陰性產生的概率隨z值增大而遞增，當z為3時，假陰性的概率為33%；當z為8 時，假陰性的概率為66%。

如果設z的值為3，也就是說，在絕大部分的單個實際時隙中，已知標簽的數量小于等于3。然而，此時單個時隙的假陰性概率仍然無法滿足系統需求，多次區分碼的哈希運算可以增大已知標簽的滅活效率及未知標簽識別概率。沖突時隙中的未知標簽被識別的概率如式（6）所示：

其中：當λ值為3 時，z值為3；當y值為1 時，假陰性的概率為3.6%。則在一次實際的沖突分解法執行未知標簽識別協議中，有z個已知標簽，1 個未知標簽選擇同一時隙的概率表達式如式（7）所示：

當假陰性概率為0 時，未知標簽被識別的數量最多，則能被識別的未知標簽數量最大值的表達式如式（8）所示：

其中：max 為實際映射中z的最大值，設為3；k值為8；pzy為時隙中有z個已知標簽，y個未知標簽發生的概率，當y值為1 時，假陰性發生的概率計算式如式（9）所示：

4.3 執行時間T 的優化

為保證CRM 協議識別未知標簽的可靠度，協議需要執行多輪。在保證未知標簽識別效率的前提下，優化的參數fop可以有效降低假陰性的比例。在每一輪協議執行中，預測時隙包含空時隙、單一時隙、以及沖突時隙，它們的概率計算式分別如下：

在未知標簽選擇時隙時，同樣會產生空時隙、單一時隙以及沖突時隙3 種時隙狀態，它們出現的概率分別如下：

在實際時隙中，空時隙的概率如下：

當某一時隙預測為單一時隙，而在實際映射中該時隙仍是單一時隙時，說明該時隙所對應的標簽為已知標簽，此類時隙的概率計算式如式（17）所示：

當預測時隙為沖突時隙時，經過CRM 協議分解，A～Q中各位全部為0，則可判定在該時隙內無未知標簽，標簽可以被滅活，該類時隙所占比例的計算式如下：

當z值設為3 時，執行一次沖突分解法，能夠滅活的已知標簽數量如下：

滅活這些已知標簽所用時間如下：

空時隙檢測所用的時間如下：

如果某一時隙在預測時隙中是單一時隙，而在實際時隙中變為沖突時隙，則可斷定有未知標簽選擇該時隙，此類時隙的概率(0 ＜y≤2)計算式如下：

能被識別的未知標簽數量如下：

所需要的執行時間如下：

如果空時隙轉變為非空時隙，則可說明該時隙所對應的標簽全為未知標簽，則該時隙的概率計算式如下：

能被識別的未知標簽數量如下：

所需執行時間如下：

從沖突時隙中分解出未知標簽，則相應的時隙所占比例分別如下：

則被識別的未知標簽的數量如式（36）所示：

分解此部分時隙所需時間如下：

則在CRM 協議執行時，未知標簽被識別的總數如式（38）所示：

CRM 協議執行一輪的時間如下：

T0為上述未包含的時隙執行所需要的時間，此類時隙包括z＞3，y＞2 的時隙，以及其他沖突分解失敗的時隙，由于此部分時隙所占比重較小，在以上表述中未提及，但在實際仿真實驗時，總的執行時間包括此類時隙執行所需時間。因此，滅活一個已知標簽及識別一個未知標簽所用時間分別如下：

4.4 未知標簽數量的估計

5 CRM 協議的其他應用

在傳統基于時隙的Aloha協議中，沖突時隙不可避免，CRM 協議不僅可以用于解決未知標簽識別問題，而且可以提高多種基于時隙的Aloha 協議的應用效率，包括標簽識別效率、丟失標簽檢測/識別效率等。

5.1 標簽識別

傳統的標簽識別協議只是利用時間幀中單一時隙搜集標簽ID，沖突時隙被直接廢棄。然而，CRM協議可以使沖突的標簽再次選擇自己的區分位，通過區分位辨別沖突標簽，有效減少沖突標簽的數量，提高時隙利用率和標簽識別效率。

5.2 丟失標簽檢測與識別

傳統丟失標簽檢測/識別的工作大多依據時間幀中期望時隙狀態與真實時隙狀態的差別，以判斷是否存在丟失標簽。當期望中的單一時隙變為真實的空時隙，沖突時隙變為空時隙，沖突時隙變為單一時隙時，可斷定RFID 系統中存在丟失標簽。然而對于丟失標簽的識別只能依據期望中的單一時隙和沖突時隙，如果他們對應的真實映射為空時隙，就可斷定此時隙所對應的標簽已丟失，從后臺服務器中可以查詢對應標簽ID，完成丟失標簽識別。

CRM 協議也可以實現丟失標簽的檢測與識別，且CRM 協議中的標簽不僅能夠依據期望的單一時隙和沖突時隙轉變為空時隙，從而判斷識別丟失標簽，而且映射入沖突時隙的沖突標簽可以選擇自己的區分位進行二次判斷，以識別丟失標簽。當某一區分位期望狀態為（1）2，而實際狀態為（0）2時，則可斷定對應標簽丟失。CRM 協議不僅能使時隙利用率提高，而且可以有效避免假陽性問題，提高丟失標簽檢測/識別效率。

6 CRM 協議性能的評估

為凸顯CRM 協議在未知標簽識別中的優越性能，本文引入對比協議UTI-SBF［9］、HUTI［10］、PTI［12］、FUTI［16］，從5 個方面分析各個協議的性能表現，分別為已知標簽數量對未知標簽識別效率的影響、未知標簽數量對未知標簽識別效率的影響、單個已知標簽滅活效率、單個未知標簽識別效率以及時隙利用率。在仿真實驗中，默認已知標簽的數量為10 000，未知標簽的數量為1 000，ω的值為0.95。由于PTI［12］是標簽識別協議，默認需要搜集所有標簽ID，但為了突出對比效果，因此本文只搜集未知標簽ID，已知標簽同樣被滅活處理。

6.1 已知標簽數量對未知標簽識別效率的影響

為研究已知標簽數量對未知標簽識別效率的影響，仿真設置已知標簽的數量從10 000 到20 000，間隔為1 000。圖5 所示為已知標簽數量與未知標簽識別效率的關系。

圖5 已知標簽數量與未知標簽識別效率的關系Fig.5 Relationship between the number of known tags and recognition efficiency of unknow tags

由圖5 可知：

1）已知標簽數量越多，達到實驗要求所需的時間越長，協議對未知標簽的識別效率越低。

2）UTI-SBF 協議的性能最差，因為該協議把未知標簽的識別分為已知標簽滅活和未知標簽識別2 個過程，已知標簽滅活階段造成時隙浪費，降低了未知標簽識別效率。

3）PTI 協議與FUTI 協議的性能接 近，PTI 協議雖然能夠把沖突時隙變為有用時隙，提高時隙利用率，但已知標簽滅活效率仍然很低，且在解決沖突時隙時，造成時間延時。

4）CRM 協議的性能最優，當n值為20 000，u值為1 000 時，CRM 協議所耗費的時間為51.6 s，而HUTI、FUTI、UTI-SBF 以 及PTI 協議所用時間分別為118.8 s、85.8 s、124.9 s、85.2 s。CRM 協議的時間效率分別是HUTI、PTI 協議的2.3 倍、1.6 倍。

6.2 未知標簽數量對未知標簽識別效率的影響

未知標簽數量也是影響未知標簽識別效率的關鍵因素之一。在仿真實驗中，未知標簽數量從1 000到2 000，間隔100，圖6 所示為未知標簽數量與未知標簽識別效率的關系。

圖6 未知標簽數量與未知標簽識別效率的關系Fig.6 Relationship between the number of unknown tags and recognition efficiency of unknown tags

由圖6 可知：

1）未知標簽數量越多，未知標簽的識別效率越低。

2）UTI-SBF 協議的效率最差，隨著未知標簽數量增多，UTI-SBF 協議所用時間增幅最快。

3）CRM 協議的性能最優，當u值為2 000 時，CRM 協議所用時間為33.1 s，而HUTI、FUTI、UTI-SBF以及PTI 協議所用時間分別為71.2 s、50.5 s、84.2 s、48.2 s。CRM 協議的識別效率是UTI-SBF 協議的2.5 倍，是PTI 協議的1.4 倍。

6.3 單個已知標簽滅活效率

已知標簽滅活效率是未知標簽識別效率的間接體現，且標簽越少對未知標簽識別效率的影響越小。圖7 所示為不同協議對單個已知標簽的平均滅活時間。

圖7 單個已知標簽的平均滅活時間Fig.7 Average inactivation time of a single known tag

由圖7 可知：

1）在未知標簽數量一定的前提下，已知標簽數量增多，單個已知標簽滅活時間減小，因為隨著已知標簽數量增多，未知標簽所占比重減小，未知標簽對已知標簽滅活影響減小。

2）除了CRM 協議，其余協議單個標簽的滅活時間都比理想標準Aloha 協議上單個標簽的滅活時間長，比如當已知標簽數量為20 000 時，PTI 協議的單個已知標簽滅活時間為4.4 ms，而理想狀態下滅活單個標簽的時間為3.6 ms，CRM 協議平均滅活一個標簽的時間為2.6 ms。

3）CRM 協議的表現最優，因為該協議可以滅活沒有未知標簽響應的沖突時隙內的已知標簽，當已知標簽數量為2 000 時，CRM 協議的單個已知標簽的滅活效率是PTI 協議的1.6 倍，是UTI-SBF 協議的2.3 倍。

6.4 單個未知標簽識別效率

單個未知標簽識別效率是未知標簽識別效率的直接體現。圖8 為單個未知標簽的平均識別時間。

圖8 單個未知標簽的平均識別時間Fig.8 Average recognition time of a single unknown tag

由圖8 可知：

1）隨著未知標簽數量增多，單個未知標簽識別所需的時間變短。因為當已知標簽數量一定，未知標簽數量增多時，未知標簽占總標簽的比重增大，相對來說，已知標簽對未知標簽識別影響減小。

2）所有未知標簽識別協議對單個未知標簽識別所用時間都比理論時間長，比如當未知標簽數量為2 000 時，CRM 協議識別單個未知標簽的時間為16.8 ms，而理想的識別時間為3.19 ms，已知標簽對未知標簽的識別造成了巨大延遲。

3）CRM 協議的性能最優，當未知標簽數量為2 000，已知標簽數量為10 000 時，CRM 協議識別一個未知標簽所用時間為16.8 ms，而HUTI、FUTI、UTI-SBF 及PTI 協議所用時間分別為37.4 ms、26.3 ms、42.1 ms、24.9 ms，也就是說CRM 協議的單個未知標簽識別效率是PTI 協議的1.4 倍，是UTI-SBF 協議的2.5 倍。

6.5 時隙利用率

時隙利用率也是衡量協議性能的關鍵因素之一。圖9 為當未知標簽數量一定，已知標簽數量對時隙利用率的影響。

圖9 已知標簽數量對時隙利用率的影響Fig.9 Influence of number of known tags on utilization rate of slots

由圖9 可知：

1）已知標簽數量對時隙利用率的影響較小，當已知標簽數量從10 000 增加到20 000 時，各協議的時隙利用率基本保持不變。

2）CRM 協議的時隙利用率最高，為86.5%，而HUTI、FUTI、UTI-SBF 及PTI 協議的時隙利用率分別為37.2%、36.7%、25%、68.8%。

7 結束語

現有的未知標簽識別協議大多存在沖突時隙被直接廢棄、時隙利用率低的問題，本文提出一種CRM 協議，通過引入區分碼把沖突時隙轉變為可識別未知標簽的時隙，提高時隙利用率及未知標簽的識別效率。實驗結果表明，CRM 協議的未知標簽識別效率是UTI-SBF 協議的2.3 倍。雖然CRM 協議的性能得到很大提升，但CRM 協議在解決沖突時隙時只對未知標簽進行識別，無法滅活混合沖突時隙中的已知標簽，因此下一步將研究快速分離混合沖突時隙中的已知標簽問題，實現已知標簽的快速滅活，提高未知標簽的識別效率。