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

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

0 概述

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2.1 問題描述

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

2.2 系統(tǒng)模型

一個(gè)典型的RFID 系統(tǒng)包含標(biāo)簽、閱讀器和后臺(tái)服務(wù)器3 個(gè)部分。每個(gè)標(biāo)簽擁有一個(gè)獨(dú)一無二的識(shí)別ID（可被讀/寫），ID 的長度一般為96 位，且系統(tǒng)內(nèi)所有標(biāo)簽均存儲(chǔ)一個(gè)相同的哈希函數(shù)H(·)。后臺(tái)服務(wù)器存儲(chǔ)標(biāo)簽ID 信息，并可根據(jù)ID 信息實(shí)現(xiàn)多樣化的業(yè)務(wù)需求。因此，標(biāo)簽根據(jù)其ID 是否被收錄可分為已知標(biāo)簽和未知標(biāo)簽。閱讀器可獲取標(biāo)簽ID，是鏈接標(biāo)簽與后臺(tái)服務(wù)器的高速通道，閱讀器與后臺(tái)服務(wù)器可統(tǒng)稱為閱讀器。單個(gè)閱讀器的讀取距離為5～12 m，因此，一個(gè)較大范圍內(nèi)的標(biāo)簽識(shí)別監(jiān)控需要多臺(tái)閱讀器交叉協(xié)同工作，而每個(gè)閱讀器都會(huì)收到1 個(gè)標(biāo)簽反饋數(shù)組，后臺(tái)服務(wù)器對(duì)所有反饋數(shù)組進(jìn)行位或運(yùn)算，即可獲取1 個(gè)融合反饋數(shù)組［6］。RFID 系統(tǒng)中所有閱讀器均可以被看作1 個(gè)超強(qiáng)閱讀器，如圖1所示。所有標(biāo)簽均在此超強(qiáng)閱讀器識(shí)別范圍內(nèi)，閱讀器周期地詢問、識(shí)別范圍內(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)簽檢測(cè)過程包含多個(gè)時(shí)間幀，每個(gè)時(shí)間幀含有多個(gè)時(shí)隙。在每個(gè)時(shí)間幀開始時(shí)，閱讀器向每個(gè)標(biāo)簽發(fā)送詢問命令Query，并廣播參數(shù)，其中f是每個(gè)時(shí)間幀中時(shí)隙的數(shù)量，r是一個(gè)隨機(jī)的哈希種子。在接收到Query 命令后，每個(gè)標(biāo)簽依照哈希函數(shù)隨機(jī)選擇一個(gè)時(shí)隙響應(yīng)，哈希函數(shù)為sc=H(ID，r)modf，其中sc為時(shí)隙計(jì)數(shù)器，H(·)為一個(gè)預(yù)先存儲(chǔ)在標(biāo)簽中的哈希函數(shù)，ID 為標(biāo)簽識(shí)別碼。因此sc∈[0，f)。此后，閱讀器逐個(gè)詢問時(shí)間幀中的時(shí)隙，當(dāng)一個(gè)時(shí)隙詢問結(jié)束時(shí)，閱讀器向當(dāng)前時(shí)隙發(fā)送slot end 命令結(jié)束訪問并初始化下一個(gè)時(shí)隙，而當(dāng)標(biāo)簽的時(shí)隙計(jì)數(shù)器sc收到命令后自動(dòng)減1，當(dāng)sc為0時(shí)，標(biāo)簽在接下來的時(shí)隙中向閱讀器發(fā)送預(yù)定信息。

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

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

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

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

本文假設(shè)閱讀器與標(biāo)簽通信是在無干擾的條件下進(jìn)行。根據(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ù)所用的時(shí)間為12.5 μs，而標(biāo)簽向閱讀器發(fā)送1 bit數(shù)據(jù)所用時(shí)間為6.25 μs。閱讀器與標(biāo)簽通信的參數(shù)設(shè)定如表1 所示，文中變量所表示的含義如表2所示。

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

表2 主要符號(hào)及其注釋Table 2 The main notations and their annotations

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

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

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

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

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

假如有w個(gè)標(biāo)簽選擇同一個(gè)時(shí)隙，沖突被檢測(cè)出來的概率為1-16/（216）w，數(shù)值無限接近于1。然而在已知標(biāo)簽識(shí)別協(xié)議以及未知標(biāo)簽檢測(cè)/識(shí)別協(xié)議中，在識(shí)別效率最高時(shí)f=N，此時(shí)空時(shí)隙的概率為36.8%，單一時(shí)隙在f個(gè)時(shí)隙中所占比例為36.8%，有2 個(gè)標(biāo)簽選擇同一時(shí)隙的概率為18.4%，有3 個(gè)標(biāo)簽選擇同一時(shí)隙的概率為6.13%，因此，在一個(gè)時(shí)隙中標(biāo)簽數(shù)量少于4 個(gè)的概率為98.13%。也就是說，在優(yōu)化后的識(shí)別協(xié)議中，選擇同一個(gè)時(shí)隙的標(biāo)簽數(shù)量很少，利用16 位隨機(jī)數(shù)來檢測(cè)沖突會(huì)造成很大的資源浪費(fèi)，過多的數(shù)據(jù)量發(fā)送也會(huì)導(dǎo)致識(shí)別效率下降。V-RNx 把RN16 分成兩部分，長度分別為k和x，長度為k的部分為區(qū)分碼且全部初始化為0，長度為x的部分為隨機(jī)碼，由標(biāo)簽內(nèi)部隨機(jī)數(shù)生成器生成長度為x的二進(jìn)制隨機(jī)數(shù)。假設(shè)x的數(shù)值為8，如果有2 個(gè)標(biāo)簽選擇同一時(shí)隙，則沖突能被檢測(cè)出來的概率為1-8/（28）2，其值接近于99.99%，當(dāng)有w個(gè)標(biāo)簽選擇同一時(shí)隙響應(yīng)時(shí)，沖突能被檢測(cè)出來的概率為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，此時(shí)，標(biāo)簽除了選擇自己所在時(shí)隙外，還要生成自己的區(qū)分碼以及隨機(jī)數(shù)。區(qū)分碼初始化為k位0 二進(jìn)制字符串，標(biāo)簽利用接收的哈希種子ri(i≤λ)再次進(jìn)行哈希運(yùn)算，計(jì)算式如式（4）所示：

其中：c為標(biāo)簽標(biāo)志位，也就是區(qū)分位，當(dāng)運(yùn)算完成后，區(qū)分碼中第c+1 位變?yōu)?，其余位仍然保持為0。這樣，在沖突時(shí)隙中，每個(gè)沖突標(biāo)簽都有自己的標(biāo)志位，當(dāng)沖突標(biāo)簽標(biāo)志位不同時(shí)，沖突標(biāo)簽就能得到區(qū)分。當(dāng)區(qū)分位只有一個(gè)標(biāo)簽選擇時(shí)，稱之為單一區(qū)分位，當(dāng)沒有標(biāo)簽選擇時(shí)，稱之為空區(qū)分位，當(dāng)有多個(gè)標(biāo)簽選擇時(shí)稱之為沖突位。假設(shè)在V-RNx 中k的值為8，當(dāng)有2 個(gè)標(biāo)簽選擇同一時(shí)隙時(shí)，兩個(gè)標(biāo)簽?zāi)軌騾^(qū)分的概率為87.5%，當(dāng)有3 個(gè)標(biāo)簽選擇同一時(shí)隙響應(yīng)時(shí)，至少一個(gè)標(biāo)簽?zāi)鼙粎^(qū)分的概率為98.4%，也就是說，當(dāng)有w個(gè)標(biāo)簽選擇同一時(shí)隙時(shí)，任意一個(gè)沖突標(biāo)簽?zāi)鼙粎^(qū)分的概率為，w個(gè)沖突標(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)時(shí)隙選擇以及區(qū)分位預(yù)測(cè)、未知標(biāo)簽識(shí)別、已知標(biāo)簽滅活共3 個(gè)部分。CRM 協(xié)議的執(zhí)行過程如圖2 所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）當(dāng)期望映射中為沖突時(shí)隙，在實(shí)際映射中仍為沖突時(shí)隙，且當(dāng)λ個(gè)哈希種子產(chǎn)生的區(qū)分碼A-Q中各位全為0 時(shí)，則表明該時(shí)隙中的標(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 的長度不會(huì)對(duì)未知標(biāo)簽識(shí)別協(xié)議的執(zhí)行效率產(chǎn)生影響。但V-RNx 由區(qū)分碼和隨機(jī)碼兩部分構(gòu)成，區(qū)分碼的長度為k，隨機(jī)碼的長度為(16-k)，區(qū)分碼的長度決定了沖突標(biāo)簽?zāi)鼙粎^(qū)分的概率大小，而隨機(jī)碼的長度決定了閱讀器是否能夠準(zhǔn)確識(shí)別沖突時(shí)隙，如果把沖突時(shí)隙辨認(rèn)為單一時(shí)隙，閱讀器就會(huì)收到錯(cuò)誤的未知標(biāo)簽ID，或者把未知標(biāo)簽誤認(rèn)為已知標(biāo)簽滅活。在標(biāo)準(zhǔn)Aloha 協(xié)議中，如果有w(w＞1)個(gè)標(biāo)簽選擇同一個(gè)時(shí)隙，沖突被檢測(cè)出來的概率為1-16/(216)w，即同一時(shí)隙標(biāo)簽越多，沖突檢測(cè)越容易。因此，至少要保證2 個(gè)標(biāo)簽的沖突時(shí)隙能夠被準(zhǔn)確識(shí)別。在V-RNx 中，此種沖突時(shí)隙能被準(zhǔn)確識(shí)別的概率為1-(16-k)/(216-k)2，2 個(gè)標(biāo)簽?zāi)鼙粎^(qū)分的概率為(k-1)/k。當(dāng)k=8 時(shí)，兩個(gè)標(biāo)簽的時(shí)隙能被準(zhǔn)確識(shí)別為沖突的概率為99.99%，兩個(gè)標(biāo)簽?zāi)鼙粎^(qū)分的概率為87.5%。為滿足沖突檢測(cè)以及沖突標(biāo)簽區(qū)分的需要，本文在優(yōu)化f時(shí)將k值設(shè)為8。

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

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

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

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

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

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

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

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

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

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

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

在實(shí)際時(shí)隙中，空時(shí)隙的概率如下：

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

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

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

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

空時(shí)隙檢測(cè)所用的時(shí)間如下：

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

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

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

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

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

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

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

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

分解此部分時(shí)隙所需時(shí)間如下：

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

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

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

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

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

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

5.1 標(biāo)簽識(shí)別

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

5.2 丟失標(biāo)簽檢測(cè)與識(shí)別

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

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

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

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

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

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

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

由圖5 可知：

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

2）UTI-SBF 協(xié)議的性能最差，因?yàn)樵搮f(xié)議把未知標(biāo)簽的識(shí)別分為已知標(biāo)簽滅活和未知標(biāo)簽識(shí)別2 個(gè)過程，已知標(biāo)簽滅活階段造成時(shí)隙浪費(fèi)，降低了未知標(biāo)簽識(shí)別效率。

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

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

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

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

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

由圖6 可知：

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

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

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

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

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

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

由圖7 可知：

1）在未知標(biāo)簽數(shù)量一定的前提下，已知標(biāo)簽數(shù)量增多，單個(gè)已知標(biāo)簽滅活時(shí)間減小，因?yàn)殡S著已知標(biāo)簽數(shù)量增多，未知標(biāo)簽所占比重減小，未知標(biāo)簽對(duì)已知標(biāo)簽滅活影響減小。

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

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

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

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

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

由圖8 可知：

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

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

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

6.5 時(shí)隙利用率

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

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

由圖9 可知：

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

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

7 結(jié)束語

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