大規(guī)模RFID 系統(tǒng)中未知標(biāo)簽的快速可靠識別

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

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

0 概述

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

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

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

本文提出沖突分解法（Conflict Resolution Method，CRM）協(xié)議，通過引入?yún)^(qū)分碼改進傳統(tǒng)16 位隨機數(shù)（16 bit Random Number，RN16），使RN16 不僅具備傳統(tǒng)的沖突檢測功能，而且具備沖突時隙內(nèi)沖突標(biāo)簽區(qū)分功能。同時采用多哈希的方式，使沖突時隙內(nèi)的標(biāo)簽得到區(qū)分的概率更大。

1 相關(guān)工作

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

1）標(biāo)簽識別旨在收集RFID 系統(tǒng)中標(biāo)簽ID 信息，通過對比收集到的標(biāo)簽ID 與服務(wù)器中存儲的已知標(biāo)簽ID，即可發(fā)現(xiàn)未知標(biāo)簽。雖然這種協(xié)議可以實現(xiàn)未知標(biāo)簽識別，但需要收集所有RFID 系統(tǒng)中標(biāo)簽ID 信息，因此時效性較低。

2）未知標(biāo)簽檢測協(xié)議意在檢測RFID 系統(tǒng)是否存在未知標(biāo)簽，不必獲取未知標(biāo)簽ID 信息，因此通常使用概率的方法來優(yōu)化協(xié)議參數(shù)設(shè)置，但在檢測中會出現(xiàn)假陰性錯誤，即未知標(biāo)簽的反饋信息被已知標(biāo)簽覆蓋，導(dǎo)致未知標(biāo)簽檢測失敗。

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

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

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

2 問題描述與系統(tǒng)模型

2.1 問題描述

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

2.2 系統(tǒng)模型

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

圖1 RFID 系統(tǒng)模型Fig.1 RFID system model

2.3 標(biāo)準(zhǔn)ALOHA 協(xié)議

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

圖2 CRM 協(xié)議的執(zhí)行流程Fig.2 Implementation process of CRM protocol

當(dāng)協(xié)議執(zhí)行完畢后，所有的時隙可以分為3 種狀態(tài)：1）空時隙，沒有標(biāo)簽選擇該時隙；2）單一時隙，僅有一個標(biāo)簽選擇該時隙并回復(fù)閱讀器詢問；3）沖突時隙，有且多于一個標(biāo)簽選擇該時隙并回復(fù)閱讀器詢問。

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

圖3 標(biāo)準(zhǔn)ALOHA 協(xié)議與CRM 協(xié)議的對比Fig.3 Comparison between standard ALOHA protocol and CRM protocol

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

表1 基于C1G2 的仿真參數(shù)設(shè)定Table 1 Simulation parameter setting based on C1G2

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

3 協(xié)議設(shè)計

在標(biāo)準(zhǔn)Aloha協(xié)議中，沖突時隙以及空時隙被廢棄，直接降低了時隙利用率，導(dǎo)致未知標(biāo)簽識別效率較低。為解決該問題，本文設(shè)計了CRM 協(xié)議，其不僅能有效滅活沖突時隙中的已知標(biāo)簽，而且能識別沖突時隙中的未知標(biāo)簽，把沖突時隙變?yōu)榭捎脮r隙，大幅提高已知標(biāo)簽滅活效率及未知標(biāo)簽識別效率。

本節(jié)將詳細(xì)介紹CRM 協(xié)議的執(zhí)行過程，并具體分析CRM 協(xié)議的執(zhí)行優(yōu)勢，介紹區(qū)分碼的設(shè)計以及區(qū)分碼在未知標(biāo)簽識別中發(fā)揮的作用。

3.1 V-RNx 的設(shè)計與引入

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

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

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

其中：c為標(biāo)簽標(biāo)志位，也就是區(qū)分位，當(dāng)運算完成后，區(qū)分碼中第c+1 位變?yōu)?，其余位仍然保持為0。這樣，在沖突時隙中，每個沖突標(biāo)簽都有自己的標(biāo)志位，當(dāng)沖突標(biāo)簽標(biāo)志位不同時，沖突標(biāo)簽就能得到區(qū)分。當(dāng)區(qū)分位只有一個標(biāo)簽選擇時，稱之為單一區(qū)分位，當(dāng)沒有標(biāo)簽選擇時，稱之為空區(qū)分位，當(dāng)有多個標(biāo)簽選擇時稱之為沖突位。假設(shè)在V-RNx 中k的值為8，當(dāng)有2 個標(biāo)簽選擇同一時隙時，兩個標(biāo)簽?zāi)軌騾^(qū)分的概率為87.5%，當(dāng)有3 個標(biāo)簽選擇同一時隙響應(yīng)時，至少一個標(biāo)簽?zāi)鼙粎^(qū)分的概率為98.4%，也就是說，當(dāng)有w個標(biāo)簽選擇同一時隙時，任意一個沖突標(biāo)簽?zāi)鼙粎^(qū)分的概率為，w個沖突標(biāo)簽?zāi)鼙环纸獬鰜淼臉?biāo)簽數(shù)量為。

3.2 CRM 協(xié)議的執(zhí)行過程

單輪的協(xié)議執(zhí)行無法滿足系統(tǒng)需求，因此，CRM 協(xié)議需要執(zhí)行多輪，且每一輪CRM 的執(zhí)行過程都包括已知標(biāo)簽響應(yīng)時隙選擇以及區(qū)分位預(yù)測、未知標(biāo)簽識別、已知標(biāo)簽滅活共3 個部分。CRM 協(xié)議的執(zhí)行過程如圖2 所示。

3.2.1 已知標(biāo)簽響應(yīng)時隙選擇以及區(qū)分位預(yù)測

3.2.2 未知標(biāo)簽識別

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

圖4 區(qū)分碼識別未知標(biāo)簽的示意圖Fig.4 Schematic diagram of discriminant code identifying unknown tags

在CRM 協(xié)議中，時隙的狀態(tài)包括空時隙、單一時隙、沖突時隙3 種。

1）空時隙中沒有任何標(biāo)簽回應(yīng)閱讀器的Query指令。

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

3）沖突時隙有多個標(biāo)簽同時選擇同一時隙。

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

在CRM 協(xié)議中，被識別的未知標(biāo)簽不參與下一輪協(xié)議執(zhí)行，以下4 種情況的未知標(biāo)簽?zāi)鼙蛔R別：

1）當(dāng)期望映射中的空時隙轉(zhuǎn)變?yōu)閱我粫r隙時，說明有且僅有一個未知標(biāo)簽響應(yīng)閱讀器詢問命令，未知標(biāo)簽可以在reply 中回復(fù)標(biāo)簽ID。

2）當(dāng)期望映射中的空時隙轉(zhuǎn)變?yōu)闆_突時隙時，說明有多個未知標(biāo)簽選擇同一時隙回應(yīng)閱讀器詢問命令，當(dāng)CRM 協(xié)議分解沖突時，如果有單一區(qū)分位，即有且僅有一個標(biāo)簽選擇該區(qū)分位，則該標(biāo)簽?zāi)軌虮蛔R別，否則對應(yīng)的未知標(biāo)簽不能被識別，不能被識別的未知標(biāo)簽將參與下一輪未知標(biāo)簽識別。

3）當(dāng)期望映射中的單一時隙在實際映射中變?yōu)闆_突時隙時，可以確定該時隙有未知標(biāo)簽，如果λ個哈希種子生成的區(qū)分碼A～Q不全為0，且存在單一區(qū)分位，則對應(yīng)的未知標(biāo)簽?zāi)鼙蛔R別。

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

3.2.3 已知標(biāo)簽滅活

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

在CRM 協(xié)議中，被滅活的已知標(biāo)簽不參與下一輪未知標(biāo)簽檢測，減小下一輪協(xié)議執(zhí)行時已知標(biāo)簽對未知標(biāo)簽識別的干擾，有兩種情況已知標(biāo)簽?zāi)鼙粶缁睿鐖D3 中已知標(biāo)簽滅活部分：

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

2）當(dāng)期望映射中為沖突時隙，在實際映射中仍為沖突時隙，且當(dāng)λ個哈希種子產(chǎn)生的區(qū)分碼A-Q中各位全為0 時，則表明該時隙中的標(biāo)簽全為已知標(biāo)簽，則直接執(zhí)行kill 命令。

4 參數(shù)優(yōu)化

4.1 參數(shù)k 的優(yōu)化

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

4.2 哈希種子數(shù)量λ 及幀長f 的優(yōu)化

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

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

假陰性產(chǎn)生的概率隨z值增大而遞增，當(dāng)z為3時，假陰性的概率為33%；當(dāng)z為8 時，假陰性的概率為66%。

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

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

當(dāng)假陰性概率為0 時，未知標(biāo)簽被識別的數(shù)量最多，則能被識別的未知標(biāo)簽數(shù)量最大值的表達(dá)式如式（8）所示：

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

4.3 執(zhí)行時間T 的優(yōu)化

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

在未知標(biāo)簽選擇時隙時，同樣會產(chǎn)生空時隙、單一時隙以及沖突時隙3 種時隙狀態(tài)，它們出現(xiàn)的概率分別如下：

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

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

當(dāng)預(yù)測時隙為沖突時隙時，經(jīng)過CRM 協(xié)議分解，A～Q中各位全部為0，則可判定在該時隙內(nèi)無未知標(biāo)簽，標(biāo)簽可以被滅活，該類時隙所占比例的計算式如下：

當(dāng)z值設(shè)為3 時，執(zhí)行一次沖突分解法，能夠滅活的已知標(biāo)簽數(shù)量如下：

滅活這些已知標(biāo)簽所用時間如下：

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

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

能被識別的未知標(biāo)簽數(shù)量如下：

所需要的執(zhí)行時間如下：

如果空時隙轉(zhuǎn)變?yōu)榉强諘r隙，則可說明該時隙所對應(yīng)的標(biāo)簽全為未知標(biāo)簽，則該時隙的概率計算式如下：

能被識別的未知標(biāo)簽數(shù)量如下：

所需執(zhí)行時間如下：

從沖突時隙中分解出未知標(biāo)簽，則相應(yīng)的時隙所占比例分別如下：

則被識別的未知標(biāo)簽的數(shù)量如式（36）所示：

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

則在CRM 協(xié)議執(zhí)行時，未知標(biāo)簽被識別的總數(shù)如式（38）所示：

CRM 協(xié)議執(zhí)行一輪的時間如下：

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

4.4 未知標(biāo)簽數(shù)量的估計

5 CRM 協(xié)議的其他應(yīng)用

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

5.1 標(biāo)簽識別

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

5.2 丟失標(biāo)簽檢測與識別

傳統(tǒng)丟失標(biāo)簽檢測/識別的工作大多依據(jù)時間幀中期望時隙狀態(tài)與真實時隙狀態(tài)的差別，以判斷是否存在丟失標(biāo)簽。當(dāng)期望中的單一時隙變?yōu)檎鎸嵉目諘r隙，沖突時隙變?yōu)榭諘r隙，沖突時隙變?yōu)閱我粫r隙時，可斷定RFID 系統(tǒng)中存在丟失標(biāo)簽。然而對于丟失標(biāo)簽的識別只能依據(jù)期望中的單一時隙和沖突時隙，如果他們對應(yīng)的真實映射為空時隙，就可斷定此時隙所對應(yīng)的標(biāo)簽已丟失，從后臺服務(wù)器中可以查詢對應(yīng)標(biāo)簽ID，完成丟失標(biāo)簽識別。

CRM 協(xié)議也可以實現(xiàn)丟失標(biāo)簽的檢測與識別，且CRM 協(xié)議中的標(biāo)簽不僅能夠依據(jù)期望的單一時隙和沖突時隙轉(zhuǎn)變?yōu)榭諘r隙，從而判斷識別丟失標(biāo)簽，而且映射入沖突時隙的沖突標(biāo)簽可以選擇自己的區(qū)分位進行二次判斷，以識別丟失標(biāo)簽。當(dāng)某一區(qū)分位期望狀態(tài)為（1）2，而實際狀態(tài)為（0）2時，則可斷定對應(yīng)標(biāo)簽丟失。CRM 協(xié)議不僅能使時隙利用率提高，而且可以有效避免假陽性問題，提高丟失標(biāo)簽檢測/識別效率。

6 CRM 協(xié)議性能的評估

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

6.1 已知標(biāo)簽數(shù)量對未知標(biāo)簽識別效率的影響

為研究已知標(biāo)簽數(shù)量對未知標(biāo)簽識別效率的影響，仿真設(shè)置已知標(biāo)簽的數(shù)量從10 000 到20 000，間隔為1 000。圖5 所示為已知標(biāo)簽數(shù)量與未知標(biāo)簽識別效率的關(guān)系。

圖5 已知標(biāo)簽數(shù)量與未知標(biāo)簽識別效率的關(guān)系Fig.5 Relationship between the number of known tags and recognition efficiency of unknow tags

由圖5 可知：

1）已知標(biāo)簽數(shù)量越多，達(dá)到實驗要求所需的時間越長，協(xié)議對未知標(biāo)簽的識別效率越低。

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

3）PTI 協(xié)議與FUTI 協(xié)議的性能接 近，PTI 協(xié)議雖然能夠把沖突時隙變?yōu)橛杏脮r隙，提高時隙利用率，但已知標(biāo)簽滅活效率仍然很低，且在解決沖突時隙時，造成時間延時。

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

6.2 未知標(biāo)簽數(shù)量對未知標(biāo)簽識別效率的影響

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

圖6 未知標(biāo)簽數(shù)量與未知標(biāo)簽識別效率的關(guān)系Fig.6 Relationship between the number of unknown tags and recognition efficiency of unknown tags

由圖6 可知：

1）未知標(biāo)簽數(shù)量越多，未知標(biāo)簽的識別效率越低。

2）UTI-SBF 協(xié)議的效率最差，隨著未知標(biāo)簽數(shù)量增多，UTI-SBF 協(xié)議所用時間增幅最快。

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

6.3 單個已知標(biāo)簽滅活效率

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

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

由圖7 可知：

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

2）除了CRM 協(xié)議，其余協(xié)議單個標(biāo)簽的滅活時間都比理想標(biāo)準(zhǔn)Aloha 協(xié)議上單個標(biāo)簽的滅活時間長，比如當(dāng)已知標(biāo)簽數(shù)量為20 000 時，PTI 協(xié)議的單個已知標(biāo)簽滅活時間為4.4 ms，而理想狀態(tài)下滅活單個標(biāo)簽的時間為3.6 ms，CRM 協(xié)議平均滅活一個標(biāo)簽的時間為2.6 ms。

3）CRM 協(xié)議的表現(xiàn)最優(yōu)，因為該協(xié)議可以滅活沒有未知標(biāo)簽響應(yīng)的沖突時隙內(nèi)的已知標(biāo)簽，當(dāng)已知標(biāo)簽數(shù)量為2 000 時，CRM 協(xié)議的單個已知標(biāo)簽的滅活效率是PTI 協(xié)議的1.6 倍，是UTI-SBF 協(xié)議的2.3 倍。

6.4 單個未知標(biāo)簽識別效率

單個未知標(biāo)簽識別效率是未知標(biāo)簽識別效率的直接體現(xiàn)。圖8 為單個未知標(biāo)簽的平均識別時間。

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

由圖8 可知：

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

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

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

6.5 時隙利用率

時隙利用率也是衡量協(xié)議性能的關(guān)鍵因素之一。圖9 為當(dāng)未知標(biāo)簽數(shù)量一定，已知標(biāo)簽數(shù)量對時隙利用率的影響。

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

由圖9 可知：

1）已知標(biāo)簽數(shù)量對時隙利用率的影響較小，當(dāng)已知標(biāo)簽數(shù)量從10 000 增加到20 000 時，各協(xié)議的時隙利用率基本保持不變。

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

7 結(jié)束語

現(xiàn)有的未知標(biāo)簽識別協(xié)議大多存在沖突時隙被直接廢棄、時隙利用率低的問題，本文提出一種CRM 協(xié)議，通過引入?yún)^(qū)分碼把沖突時隙轉(zhuǎn)變?yōu)榭勺R別未知標(biāo)簽的時隙，提高時隙利用率及未知標(biāo)簽的識別效率。實驗結(jié)果表明，CRM 協(xié)議的未知標(biāo)簽識別效率是UTI-SBF 協(xié)議的2.3 倍。雖然CRM 協(xié)議的性能得到很大提升，但CRM 協(xié)議在解決沖突時隙時只對未知標(biāo)簽進行識別，無法滅活混合沖突時隙中的已知標(biāo)簽，因此下一步將研究快速分離混合沖突時隙中的已知標(biāo)簽問題，實現(xiàn)已知標(biāo)簽的快速滅活，提高未知標(biāo)簽的識別效率。