張莉涓，范明秋，雷磊，王勇，袁代數(shù)

（1.南京航空航天大學(xué)電子信息工程學(xué)院，江蘇 南京 211106；2.西南交通大學(xué)物理科學(xué)與技術(shù)學(xué)院，四川 成都 610031；3.中興通訊股份有限公司，江蘇 南京 210012）

1 引言

射頻識(shí)別（RFID,radio frequency identification,）技術(shù)作為物聯(lián)網(wǎng)感知層獲取物品信息的重要關(guān)鍵技術(shù)之一，被廣泛應(yīng)用于各行各業(yè)，如倉(cāng)儲(chǔ)管理、物流追蹤、藥品監(jiān)管和食品鏈監(jiān)察等[1]。RFID 系統(tǒng)主要由一個(gè)或多個(gè)閱讀器以及大量附著在物品上的電子標(biāo)簽組成，且每個(gè)標(biāo)簽擁有一個(gè)全球唯一的ID 信息（即EPC（electronic product code））。閱讀器和標(biāo)簽通過(guò)詢(xún)問(wèn)應(yīng)答方式通信，當(dāng)有多個(gè)標(biāo)簽同時(shí)響應(yīng)閱讀器的詢(xún)問(wèn)請(qǐng)求時(shí)，標(biāo)簽信號(hào)發(fā)生碰撞，嚴(yán)重影響閱讀器的識(shí)別性能[1-4]。合理的標(biāo)簽防碰撞協(xié)議可以有效提高識(shí)別性能，然而傳統(tǒng)研究較少考慮捕獲效應(yīng)對(duì)識(shí)別過(guò)程的影響。

在被動(dòng)式RFID 系統(tǒng)中，標(biāo)簽通過(guò)電感耦合或電磁反向散射方式獲取能量并反饋?lái)憫?yīng)信息。受信道衰落的影響，標(biāo)簽反饋信號(hào)強(qiáng)度差異較大。當(dāng)有多個(gè)標(biāo)簽同時(shí)回復(fù)信息時(shí)，某一標(biāo)簽的信號(hào)強(qiáng)度可能遠(yuǎn)大于其他所有標(biāo)簽的信號(hào)強(qiáng)度之和，此時(shí)閱讀器可以成功解碼該標(biāo)簽的響應(yīng)信息，該現(xiàn)象被稱(chēng)為捕獲效應(yīng)[5]。當(dāng)捕獲效應(yīng)發(fā)生時(shí)，原本的碰撞時(shí)隙將轉(zhuǎn)換為成功時(shí)隙，閱讀器可以成功解碼信號(hào)最強(qiáng)的標(biāo)簽信息，而其他強(qiáng)度較弱的標(biāo)簽信號(hào)將被覆蓋，造成標(biāo)簽漏讀，嚴(yán)重影響識(shí)別過(guò)程。

傳統(tǒng)研究主要考慮捕獲效應(yīng)下Aloha 類(lèi)標(biāo)簽防碰撞算法的識(shí)別性能優(yōu)化問(wèn)題。王陽(yáng)等[6-8]提出的最大后驗(yàn)概率估計(jì)（CMAP,capture-aware maximum posterior probability estimate）算法采用貝葉斯對(duì)捕獲概率和標(biāo)簽數(shù)量進(jìn)行估計(jì)，并以此設(shè)置動(dòng)態(tài)幀時(shí)隙Aloha 算法的最優(yōu)幀長(zhǎng)。Salah 等[9]則根據(jù)丟包率和捕獲效應(yīng)發(fā)生概率之間的關(guān)系獲得不同信噪比條件下的捕獲概率，并給出不同時(shí)隙長(zhǎng)度和捕獲概率影響下的最優(yōu)幀長(zhǎng)設(shè)置表達(dá)式。Nguyen 等[10]通過(guò)估計(jì)捕獲概率和誤檢率來(lái)提高Aloha 算法的識(shí)別性能?？傮w來(lái)說(shuō)，這類(lèi)方法主要通過(guò)估計(jì)捕獲效應(yīng)發(fā)生的概率，調(diào)整幀長(zhǎng)參數(shù)，增加成功時(shí)隙的比例，但沒(méi)有考慮由捕獲效應(yīng)造成的標(biāo)簽漏讀問(wèn)題。

近年來(lái)，捕獲效應(yīng)下RFID 系統(tǒng)的可靠識(shí)別性能受到越來(lái)越多的關(guān)注。Wu 等[11]提出了捕獲效應(yīng)下基于查詢(xún)樹(shù)（QT,query tree）協(xié)議的隱藏標(biāo)簽處理方法，即通用查詢(xún)樹(shù)（GQT,general query tree）協(xié)議。該方法通過(guò)重復(fù)添加成功時(shí)隙相對(duì)應(yīng)的查詢(xún)前綴，獲取隱藏標(biāo)簽的信息。但由于每個(gè)成功時(shí)隙所對(duì)應(yīng)的查詢(xún)前綴都執(zhí)行了兩次，識(shí)別效率較低。Lai 等[12]提出了通用樹(shù)分裂（GBT,general binary tree）協(xié)議，通過(guò)閱讀器發(fā)送確認(rèn)信息靜默已識(shí)別的標(biāo)簽，標(biāo)記相應(yīng)的隱藏標(biāo)簽便于下一輪識(shí)別，并通過(guò)多次執(zhí)行該識(shí)別過(guò)程，解決標(biāo)簽漏讀問(wèn)題。采用類(lèi)似的靜默和標(biāo)記方法，Choi 等[13]提出了捕獲感知 CA-CRB（capture-aware couple-resolution blocking）協(xié)議識(shí)別隱藏標(biāo)簽，但是重復(fù)發(fā)送完整的ID 信息對(duì)標(biāo)簽進(jìn)行靜默和標(biāo)記，增加了較多額外開(kāi)銷(xiāo)，識(shí)別時(shí)間長(zhǎng)。Wu 等[14]結(jié)合Q 協(xié)議和二叉樹(shù)協(xié)議提出自適應(yīng)的ABTSA（adaptive binary tree slotted Aloha）協(xié)議，通過(guò)在成功時(shí)隙中回復(fù)隨機(jī)數(shù)確認(rèn)信息標(biāo)記隱藏標(biāo)簽以減少通信開(kāi)銷(xiāo)，提高識(shí)別效率。

綜上，已有研究主要基于傳統(tǒng)的Aloha 或分支樹(shù)協(xié)議解決捕獲效應(yīng)下的標(biāo)簽識(shí)別問(wèn)題，識(shí)別過(guò)程中產(chǎn)生了較多的空閑時(shí)隙和碰撞時(shí)隙，且對(duì)隱藏標(biāo)簽的處理，增加的通信開(kāi)銷(xiāo)較多，整體識(shí)別效率低。本文通過(guò)設(shè)計(jì)合理的標(biāo)簽數(shù)量估計(jì)和高效可靠的標(biāo)簽識(shí)別算法來(lái)提高捕獲效應(yīng)下的標(biāo)簽識(shí)別效率。

在多數(shù)RFID 系統(tǒng)中，標(biāo)簽數(shù)量通常未知，合理的標(biāo)簽數(shù)量估計(jì)可以有效提高識(shí)別效率。傳統(tǒng)的標(biāo)簽數(shù)量估計(jì)算法采用每幀中的時(shí)隙統(tǒng)計(jì)信息與理論預(yù)期值之間的關(guān)系對(duì)標(biāo)簽數(shù)量進(jìn)行估計(jì)，時(shí)隙開(kāi)銷(xiāo)較大。為此，Chen 等[15]提出提前中斷的估計(jì)方法，即在每幀中采用逐時(shí)隙估計(jì)的方式，提前結(jié)束幀長(zhǎng)設(shè)置不合理的幀，減少時(shí)隙開(kāi)銷(xiāo)。隨后Su等[16]提出設(shè)置固定檢查點(diǎn)和離線表格方式，進(jìn)一步降低計(jì)算復(fù)雜度。由于這類(lèi)算法在前期獲得的統(tǒng)計(jì)信息較少，估計(jì)不準(zhǔn)確，所需時(shí)隙數(shù)較多。

在標(biāo)簽識(shí)別算法中，基于比特檢測(cè)的樹(shù)分支類(lèi)算法具有較高的識(shí)別效率。Jia 等[17]提出的碰撞樹(shù)（CT,collision tree）算法將發(fā)生碰撞的標(biāo)簽分成不相交的2 個(gè)子集，并通過(guò)比特檢測(cè)技術(shù)獲得每個(gè)子集中標(biāo)簽的最長(zhǎng)共同前綴，從而消除空閑時(shí)隙。隨后，Landaluce 等[18]提出的碰撞窗口樹(shù)（CwT,collision window tree）協(xié)議采用啟發(fā)式方法加速識(shí)別過(guò)程。Zhang 等[19]提出的多分支樹(shù)碰撞（MCT,M-ary collision tree）協(xié)議將發(fā)生碰撞的標(biāo)簽分裂成多個(gè)子集，進(jìn)一步縮短識(shí)別時(shí)延。但是，這些協(xié)議并沒(méi)有考慮捕獲效應(yīng)對(duì)識(shí)別過(guò)程的影響。

為了有效提高捕獲效應(yīng)下標(biāo)簽可靠識(shí)別的效率，本文提出基于比特檢測(cè)的多分支樹(shù)標(biāo)簽識(shí)別（BMT,bit-detectingM-ary tree）協(xié)議，主要貢獻(xiàn)如下。

1) 提出基于比特檢測(cè)的快速標(biāo)簽估計(jì)算法，初步估計(jì)待識(shí)別標(biāo)簽的數(shù)量。通過(guò)將標(biāo)簽的隨機(jī)選擇信息融入標(biāo)簽回復(fù)信息中，提供標(biāo)簽數(shù)量估計(jì)統(tǒng)計(jì)信息，減少估計(jì)階段的時(shí)隙開(kāi)銷(xiāo)。

2) 提出基于比特檢測(cè)的多分支樹(shù)標(biāo)簽識(shí)別協(xié)議。閱讀器利用比特檢測(cè)技術(shù)從標(biāo)簽回復(fù)信息中獲取標(biāo)簽的時(shí)隙選擇情況，有效消除空閑時(shí)隙，提高識(shí)別效率。并提出基于哈希靜默的方法減少對(duì)隱藏標(biāo)簽處理的通信開(kāi)銷(xiāo)。

3) 建立多分支樹(shù)概率模型分析BMT 的時(shí)隙開(kāi)銷(xiāo)和系統(tǒng)效率，并通過(guò)仿真對(duì)比從多方面驗(yàn)證BMT協(xié)議的有效性。

理論分析和實(shí)驗(yàn)結(jié)果充分證明了BMT 協(xié)議能夠有效解決捕獲效應(yīng)造成的標(biāo)簽漏讀情況，且相較于已有協(xié)議，BMT 協(xié)議的識(shí)別時(shí)間縮短了至少15%。

2 系統(tǒng)模型

考慮一個(gè)典型的靜態(tài)RFID 系統(tǒng)，如圖1 所示，該系統(tǒng)由閱讀器、后端數(shù)據(jù)庫(kù)和大量被動(dòng)式標(biāo)簽組成。閱讀器和所有標(biāo)簽共享無(wú)線信道，且在識(shí)別之前閱讀器沒(méi)有任何關(guān)于標(biāo)簽數(shù)量和ID 的先驗(yàn)信息。閱讀器和標(biāo)簽之間采用詢(xún)問(wèn)應(yīng)答模式進(jìn)行通信，標(biāo)簽只有簡(jiǎn)單的計(jì)算、存儲(chǔ)和通信能力，標(biāo)簽之間互不通信。與大多文獻(xiàn)[6-14]中給定捕獲概率的固定值不同，本文定義了被動(dòng)式RFID 系統(tǒng)中的級(jí)聯(lián)信道模型，以獲取不同信道環(huán)境影響下捕獲效應(yīng)發(fā)生的概率，有效分析捕獲效應(yīng)對(duì)識(shí)別算法的性能影響。

系統(tǒng)的通信鏈路包括前向信道和反向信道2 個(gè)部分，閱讀器通過(guò)前向信道發(fā)送查詢(xún)命令并提供連續(xù)載波信號(hào)，標(biāo)簽通過(guò)反向散射方式從閱讀器的載波信號(hào)中獲取能量，并反饋回復(fù)信息[20-21]。閱讀器收到的標(biāo)簽回復(fù)信號(hào)功率需綜合考慮級(jí)聯(lián)信道中前向和反向鏈路損耗。令Ptx為閱讀器的發(fā)射功率，標(biāo)簽接收到閱讀器信號(hào)的功率Pr,T為[20-21]

其中，ρL為閱讀器與標(biāo)簽天線匹配的極化損耗因子（PLF,polarization loss factor），GR和GT分別為閱讀器和標(biāo)簽的天線增益，L(df)為閱讀器與標(biāo)簽相距df時(shí)前向信道的大尺度路徑損耗，|hf|為前向信道的小尺度衰落隨機(jī)系數(shù)。標(biāo)簽通過(guò)反向散射方式獲取能量并回復(fù)，故閱讀器收到某一標(biāo)簽的回復(fù)信號(hào)功率Pr,R為[20-21]

其中，τ為歸一化系數(shù)，表示由編碼和調(diào)制方法所導(dǎo)致的閱讀器接收功率差異；μT為標(biāo)簽芯片與天線間的功率傳輸效率；上標(biāo)和下標(biāo)中的f 和b分別表示前向和反向鏈路，下標(biāo)中的R 和T 分別表示閱讀器和標(biāo)簽；Γ為標(biāo)簽反射系數(shù)差值?？紤]自由空間路徑損耗模型可得L(d)=[λ/(4πd)]2，鏈路衰落系數(shù)|h|可由Rician 分布或Rayleigh 分布模型獲得。

根據(jù)功率模型，定義RFID 系統(tǒng)中的標(biāo)簽捕獲效應(yīng)如下：當(dāng)有k個(gè)標(biāo)簽同時(shí)發(fā)送信號(hào)時(shí)，如果某一標(biāo)簽的信號(hào)強(qiáng)度遠(yuǎn)大于其他所有標(biāo)簽的信號(hào)強(qiáng)度之和，捕獲效應(yīng)發(fā)生，即

其中，Z為功率比門(mén)限（PRT,power ratio threshold）[5]，是閱讀器成功接收信號(hào)所需要的最小載波干擾比，其值與調(diào)制方式和編解碼方法有關(guān)，對(duì)于一般的窄帶系統(tǒng)，1

由式(1)～式(4)可得，當(dāng)有k個(gè)標(biāo)簽同時(shí)發(fā)送信息時(shí)捕獲效應(yīng)發(fā)生的概率qk。采用文獻(xiàn)[20-21]中的射頻參數(shù)設(shè)置，圖2 給出了當(dāng)閱讀器的讀取范圍為3 m 時(shí)，不同參數(shù)條件下2 個(gè)標(biāo)簽同時(shí)發(fā)送信息的捕獲概率。從圖2 中可以看出，當(dāng)Kf=Kb=?∞時(shí)，傳輸鏈路中缺乏可視通路，捕獲效應(yīng)發(fā)生概率較高；當(dāng)Kf=Kb=10 dB 時(shí)，傳輸鏈路處于強(qiáng)可視環(huán)境，此時(shí)發(fā)生捕獲效應(yīng)的概率有所降低。

此外，從圖2 還可以看到，隨著功率比門(mén)限的增加捕獲概率下降顯著，因此本文主要分析功率比門(mén)限對(duì)捕獲概率和識(shí)別算法的影響?？紤]典型室內(nèi)RFID 應(yīng)用場(chǎng)景，圖3 給出了當(dāng)Rician 分布參數(shù)Kf=Kb=10 dB 時(shí)，捕獲概率的理論值和指數(shù)擬合情況。

通過(guò)曲線擬合，可得捕獲概率的近似表達(dá)式為qk=eaz+b，各參數(shù)如表1 所示。

表1 捕獲概率擬合曲線參數(shù)

3 算法設(shè)計(jì)

本文提出的BMT 協(xié)議包括2 個(gè)階段：基于比特檢測(cè)的標(biāo)簽數(shù)量快速估計(jì)和多分支樹(shù)可靠識(shí)別。在估計(jì)階段，閱讀器采用少量時(shí)隙對(duì)標(biāo)簽進(jìn)行初步估計(jì)和預(yù)分組，該階段采用幀時(shí)隙方式將時(shí)間分為幀，每一幀包括多個(gè)時(shí)隙。閱讀器在每一幀開(kāi)始時(shí)廣播Qest(L)命令，告知所有標(biāo)簽當(dāng)前幀參數(shù)L，該幀中的第一個(gè)時(shí)隙在該命令之后自動(dòng)開(kāi)始，其余時(shí)隙由閱讀器的QRep 命令開(kāi)啟。在識(shí)別階段，閱讀器構(gòu)造多分支樹(shù)結(jié)構(gòu)提高識(shí)別效率，該階段通過(guò)逐時(shí)隙的方式進(jìn)行識(shí)別，閱讀器在每個(gè)時(shí)隙開(kāi)始時(shí)廣播Query(fds)命令通過(guò)fds 字符串反饋所有標(biāo)簽的時(shí)隙選擇情況。表2 給出了BMT 協(xié)議用到的命令和定義。

表2 命令和定義

3.1 比特檢測(cè)技術(shù)

在BMT 識(shí)別過(guò)程中，標(biāo)簽將其時(shí)隙選擇信息融入回復(fù)信息中，閱讀器通過(guò)比特檢測(cè)技術(shù)從碰撞信息中獲悉標(biāo)簽選擇情況，以此對(duì)標(biāo)簽進(jìn)行估計(jì)和識(shí)別。比特檢測(cè)技術(shù)被廣泛應(yīng)用于RFID 標(biāo)簽防碰撞協(xié)議設(shè)計(jì)[17-19,22-26]，閱讀器通過(guò)比特檢測(cè)技術(shù)可以有效定位碰撞時(shí)隙中發(fā)生碰撞的比特位置。

比特檢測(cè)技術(shù)可以通過(guò)曼徹斯特編碼實(shí)現(xiàn)，該編碼采用電平的跳變來(lái)表示“0”或“1”，即每個(gè)碼元均用兩個(gè)不同相位的電平信號(hào)表示[1]。如圖4所示，采用電平下降沿表示“0”，上升沿表示“1”。當(dāng)有多個(gè)標(biāo)簽同時(shí)回復(fù)信息時(shí)，閱讀器可以定位到發(fā)生碰撞的比特位置[17-19,22-26]。圖4 中標(biāo)簽A、B和C 分別回復(fù)字符串“10110010”“10100110”和“10000011”，通過(guò)曼徹斯特解碼規(guī)則閱讀器得到的字符串為“10XX0X1X”，其中“X”代表無(wú)效碼元。閱讀器可以有效解碼全“0”和全“1”位的信息，但當(dāng)有標(biāo)簽同時(shí)回復(fù)“0”和“1”時(shí)，閱讀器判斷該位置為碰撞位。

本文利用比特檢測(cè)技術(shù)，設(shè)計(jì)標(biāo)簽回復(fù)信息和閱讀器讀取策略，有效提高識(shí)別效率。需要注意的是，比特檢測(cè)技術(shù)主要用于碰撞時(shí)隙中碰撞信息位的獲取，當(dāng)某一時(shí)隙發(fā)生捕獲效應(yīng)后，該時(shí)隙變?yōu)槌晒r(shí)隙，閱讀器可以成功解碼接收到的信號(hào)，此時(shí)不會(huì)檢測(cè)到碰撞位信息。

3.2 基于比特檢測(cè)的標(biāo)簽數(shù)量快速估計(jì)

鑒于傳統(tǒng)的估計(jì)方法所需時(shí)隙數(shù)較多、效率低，本文采用比特檢測(cè)技術(shù)從標(biāo)簽回復(fù)信息中獲取標(biāo)簽數(shù)量估計(jì)所需統(tǒng)計(jì)信息，減少通信開(kāi)銷(xiāo)。該過(guò)程采用幀時(shí)隙方式，閱讀器在每一幀中估計(jì)標(biāo)簽數(shù)量和調(diào)整下一幀的幀參數(shù)，通過(guò)多個(gè)幀的調(diào)整和估計(jì)提高估計(jì)準(zhǔn)確度。

在每一幀開(kāi)始時(shí)，閱讀器廣播Qest(L)命令，其中初始幀的幀參數(shù)為L(zhǎng)0。標(biāo)簽收到該查詢(xún)命令后，產(chǎn)生1～L的隨機(jī)數(shù)RN，然后設(shè)置時(shí)隙計(jì)數(shù)器tc和回復(fù)字符串str，其中，str 為B比特長(zhǎng)字符串，且第 [(RN?1)modB]+1 位為“1”，其余位為“0”。其中，mod 為求模運(yùn)算，為向上取整運(yùn)算，B為標(biāo)簽在每個(gè)時(shí)隙中的回復(fù)信息長(zhǎng)度，如圖5(a) 中B=6。若tc=0，標(biāo)簽在當(dāng)前時(shí)隙回復(fù)字符串str；否則，標(biāo)簽在收到閱讀器的Qrep 命令時(shí)設(shè)置tc=tc?1。

閱讀器接收標(biāo)簽回復(fù)信息并記錄估計(jì)統(tǒng)計(jì)參數(shù)c0，直到當(dāng)前幀中所有個(gè)時(shí)隙都執(zhí)行完成。由于每個(gè)標(biāo)簽的回復(fù)信息中只有一位值為“1”，其他位都是“0”。結(jié)合比特檢測(cè)技術(shù)，當(dāng)閱讀器檢測(cè)到當(dāng)前位為“0”時(shí)，表明沒(méi)有標(biāo)簽選擇當(dāng)前位置。通過(guò)統(tǒng)計(jì)解碼信息中“0”比特的數(shù)量，并將其與理論值相比，可得標(biāo)簽數(shù)量的初步估計(jì)。如果閱讀器沒(méi)有收到任何標(biāo)簽回復(fù)信息，如圖5(a)中“時(shí)隙3”所示，該時(shí)隙為空閑時(shí)隙，閱讀器設(shè)置c0=c0+B。如果閱讀器收到標(biāo)簽的回復(fù)信息，則統(tǒng)計(jì)接收信息中“0”比特的數(shù)量，并設(shè)置c0=c0+。如圖5(a)中“時(shí)隙1”為碰撞時(shí)隙，閱讀器通過(guò)比特檢測(cè)技術(shù)得到解碼信息“0XX00X”，其中“X”為碰撞位，此時(shí)c0=c0+3；“時(shí)隙2”為成功時(shí)隙，閱讀器接收信息為“000001”，故c0=c0+5。此外，圖5 中t1和t2分別為閱讀器和標(biāo)簽發(fā)送信息的傳輸時(shí)間，t3為空閑時(shí)隙中閱讀器的等待時(shí)間。相較于傳統(tǒng)標(biāo)簽數(shù)量估計(jì)算法在每個(gè)時(shí)隙只能獲取單一的標(biāo)簽選擇信息，本文算法在每個(gè)時(shí)隙可以獲得較多標(biāo)簽選擇信息，時(shí)隙利用率高。

在每幀結(jié)束時(shí)，閱讀器根據(jù)c0值估計(jì)標(biāo)簽數(shù)量。每一幀中標(biāo)簽隨機(jī)選擇RN 值，與傳統(tǒng)標(biāo)簽估計(jì)算法[6-10]類(lèi)似，假定每個(gè)標(biāo)簽設(shè)置L比特中某位置為“1”的事件相互獨(dú)立。則沒(méi)有標(biāo)簽選擇某一特定位置（即閱讀器檢測(cè)到比特“0”）的概率為P0=(1?1/L)n。實(shí)際統(tǒng)計(jì)中P0=c0/L，由此可得標(biāo)簽數(shù)量的估計(jì)值為

閱讀器計(jì)算估計(jì)結(jié)果?與幀參數(shù)L的偏差|，并以此判斷是否結(jié)束估計(jì)階段。若未結(jié)束，閱讀器調(diào)整下一幀的幀參數(shù)為當(dāng)前估計(jì)值。

為了減少時(shí)隙開(kāi)銷(xiāo)，該階段的結(jié)束條件由時(shí)隙開(kāi)銷(xiāo)和估計(jì)偏差之間的關(guān)系決定。圖6 給出了當(dāng)標(biāo)簽數(shù)量從100 變化到1 000 時(shí)估計(jì)階段的時(shí)隙開(kāi)銷(xiāo)。從圖6 中可以看到，隨著標(biāo)簽數(shù)量和估計(jì)偏差的增加，估計(jì)階段的時(shí)隙開(kāi)銷(xiāo)相應(yīng)增加。當(dāng)估計(jì)誤差低于0.1 時(shí)，時(shí)隙開(kāi)銷(xiāo)的增加幅度變大，特別是當(dāng)ε=0.01 時(shí)，時(shí)隙開(kāi)銷(xiāo)較大。為平衡時(shí)隙開(kāi)銷(xiāo)和估計(jì)準(zhǔn)確度，設(shè)置估計(jì)階段的結(jié)束條件為ε<10%。注意，該階段主要給出標(biāo)簽數(shù)量的初步估計(jì)，為了降低算法復(fù)雜度，由捕獲效應(yīng)造成的估計(jì)偏差不作考慮。標(biāo)簽估計(jì)過(guò)程的偽代碼如算法1 所示。

算法1基于比特檢測(cè)的標(biāo)簽數(shù)量快速估計(jì)

閱讀器端：

標(biāo)簽端：

3.3 基于比特檢測(cè)的多分支樹(shù)可靠識(shí)別

該階段采用多分支樹(shù)方法對(duì)標(biāo)簽進(jìn)行識(shí)別，由于傳統(tǒng)多分支樹(shù)結(jié)構(gòu)隨分支數(shù)量的增加碰撞時(shí)隙數(shù)逐漸減少，而空閑時(shí)隙數(shù)急劇增加，整體識(shí)別效率低。本文通過(guò)比特檢測(cè)技術(shù)將標(biāo)簽時(shí)隙選擇信息融入回復(fù)信息中，通過(guò)反饋調(diào)整的方式消除多分支樹(shù)結(jié)構(gòu)中的空閑時(shí)隙，提高識(shí)別效率。

識(shí)別過(guò)程中，標(biāo)簽根據(jù)閱讀器的Query(fds)命令調(diào)整時(shí)隙計(jì)數(shù)器tc。估計(jì)階段結(jié)束時(shí)，閱讀器根據(jù)最后一幀所有時(shí)隙中收到的標(biāo)簽回復(fù)信息構(gòu)建L比特長(zhǎng)反饋?zhàn)址甪ds，在fds 中用“1”表示有標(biāo)簽選擇的位置（包括閱讀器接收信息中所有碰撞位和“1”比特位），“0”表示沒(méi)有標(biāo)簽選擇該位置。如圖5(b)中，假設(shè)估計(jì)階段最后一幀中標(biāo)簽A～H選擇的RN 分別為3,2,2,8,3,8,5,9，閱讀器獲得的fds=011010011。標(biāo)簽收到該反饋信息后更新其tc 值，即標(biāo)簽統(tǒng)計(jì)fds 中第RN 位之前的“0”比特?cái)?shù)量b0，并設(shè)置時(shí)隙計(jì)數(shù)器值tc=RN?b0?1。圖5(b)中，標(biāo)簽設(shè)置tc(A)=1,tc(B)=0,tc(C)=0,tc(D)=3,tc(E)=1,tc(F)=3,tc(G)=2,tc(H)=4。

若tc=0，標(biāo)簽產(chǎn)生新的隨機(jī)數(shù)RN（RN∈[1,M]）和Mbit 全零字符串str，并將第RN 位設(shè)為“1”。該標(biāo)簽在當(dāng)前時(shí)隙回復(fù)字符串str，其他標(biāo)簽等待閱讀器的查詢(xún)命令。圖5(b)“時(shí)隙1”中標(biāo)簽B 和C的計(jì)數(shù)器值為0，于是在該時(shí)隙進(jìn)行回復(fù)，回復(fù)字符串分別為“010000”和“000100”。閱讀器收到標(biāo)簽回復(fù)信息后，若當(dāng)前時(shí)隙為沖突時(shí)隙，則根據(jù)解碼信息重新構(gòu)建新的反饋?zhàn)址?。圖5(b)“時(shí)隙1”中閱讀器接收到標(biāo)簽B 和C 的回復(fù)信息后，構(gòu)建反饋?zhàn)址甪ds=010100。圖5(b)“時(shí)隙2”中標(biāo)簽收到閱讀器的Query(fds)命令后，按如下方式調(diào)整計(jì)數(shù)器值，

1) 若tc=0，標(biāo)簽統(tǒng)計(jì)fds 中第RN 位之前的“0”比特?cái)?shù)量b0，并設(shè)置時(shí)隙計(jì)數(shù)器值tc=RN?b0?1。

2) 若tc>0，標(biāo)簽統(tǒng)計(jì)fds 中所有“1”比特?cái)?shù)量b1，并設(shè)置時(shí)隙計(jì)數(shù)器值tc=tc+b1?1。

若當(dāng)前時(shí)隙為成功時(shí)隙，閱讀器接著發(fā)送Collect 命令獲取相應(yīng)標(biāo)簽的ID 信息。如圖5(b)“時(shí)隙2”中在收到Collect 命令時(shí)，只有標(biāo)簽B 的時(shí)隙計(jì)數(shù)器值為0，此時(shí)標(biāo)簽B 回復(fù)其ID 信息，使閱讀器可以成功識(shí)別該標(biāo)簽。

由于識(shí)別過(guò)程中可能發(fā)生捕獲效應(yīng)，閱讀器無(wú)法判斷成功時(shí)隙中有一個(gè)標(biāo)簽回復(fù)還是有捕獲效應(yīng)發(fā)生。為了解決由捕獲效應(yīng)造成的隱藏標(biāo)簽問(wèn)題，閱讀器在成功獲取標(biāo)簽ID 后廣播ACK(H16)信息，其中H16為已識(shí)別標(biāo)簽ID 的前16 bit 哈希值。收到該確認(rèn)消息后，標(biāo)簽進(jìn)行如下調(diào)整。

1) 若tc=0，對(duì)比其H16值是否與接收到的哈希值相等，若相等該標(biāo)簽轉(zhuǎn)為靜默狀態(tài)，否則標(biāo)記自己為隱藏標(biāo)簽，并等待下一輪識(shí)別。

2) 若tc>0，設(shè)置tc=tc?1，等待閱讀器的查詢(xún)命令。

閱讀器重復(fù)后續(xù)時(shí)隙的識(shí)別過(guò)程，直到?jīng)]有標(biāo)簽回復(fù)。采用閱讀器回復(fù)ACK(H16)命令靜默已識(shí)別標(biāo)簽和標(biāo)記隱藏標(biāo)簽，可有效減少傳統(tǒng)方法中需要傳輸完整ID 信息的時(shí)間開(kāi)銷(xiāo)。

閱讀器在重復(fù)多輪該識(shí)別過(guò)程，讀取所有標(biāo)簽的ID 信息。注意在后續(xù)每輪開(kāi)始時(shí)閱讀器廣播第一個(gè)Query(fds)命令中fds 為空串，所有未被識(shí)別的標(biāo)簽收到該命令后設(shè)置tc=0，產(chǎn)生并回復(fù)字符串str。如果閱讀器沒(méi)有收到任何標(biāo)簽回復(fù)，則表明所有標(biāo)簽都被識(shí)別，便結(jié)束整個(gè)識(shí)別過(guò)程，該過(guò)程偽代碼如算法2 所示?？梢钥吹?，標(biāo)簽在回復(fù)信息時(shí)需要產(chǎn)生特定的回復(fù)字符串，相較于傳統(tǒng)算法中直接產(chǎn)生隨機(jī)字符串，本算法會(huì)增加少量的計(jì)算開(kāi)銷(xiāo)。其次，在哈希靜默過(guò)程中，標(biāo)簽需要進(jìn)行哈希運(yùn)算，但該過(guò)程只在已識(shí)別標(biāo)簽和隱藏標(biāo)簽中產(chǎn)生，故增加的計(jì)算開(kāi)銷(xiāo)在可接受范圍內(nèi)。

算法2基于比特檢測(cè)的多分支樹(shù)可靠識(shí)別

閱讀器端：

標(biāo)簽端：

4 性能分析

本文提出的BMT 協(xié)議主要包括2 個(gè)階段，標(biāo)簽數(shù)量估計(jì)和標(biāo)簽識(shí)別。標(biāo)簽數(shù)量估計(jì)階段需要的時(shí)隙數(shù)較少，其時(shí)間開(kāi)銷(xiāo)占比將通過(guò)仿真結(jié)果給出，本節(jié)主要對(duì)標(biāo)簽識(shí)別階段的時(shí)隙開(kāi)銷(xiāo)進(jìn)行分析。對(duì)于捕獲效應(yīng)造成的隱藏標(biāo)簽，BMT 采用靜默已識(shí)別標(biāo)簽的同時(shí)對(duì)其進(jìn)行標(biāo)記，以及多輪識(shí)別的方式保證可靠性。每一輪的識(shí)別過(guò)程基本相同，通過(guò)分析一輪中所需時(shí)隙數(shù)和識(shí)別標(biāo)簽數(shù)量之間的關(guān)系，可得所提協(xié)議的系統(tǒng)效率為

其中，n為標(biāo)簽數(shù)量，Thide(n)為單輪識(shí)別過(guò)程中由于捕獲效應(yīng)被隱藏的標(biāo)簽數(shù)量，S(n)為單輪識(shí)別過(guò)程所需總時(shí)隙數(shù)。

在識(shí)別階段，閱讀器首先根據(jù)估計(jì)結(jié)果對(duì)標(biāo)簽進(jìn)行初步分組，令L1為標(biāo)簽初始分組數(shù)。依據(jù)相關(guān)文獻(xiàn)[19,24,27]假定標(biāo)簽選擇時(shí)隙服從均勻分布，n個(gè)標(biāo)簽中有k個(gè)標(biāo)簽被分配到L1個(gè)組中某一組的概率Pk可以由二項(xiàng)分布公式得到，即

在初始分組后，每一個(gè)發(fā)生碰撞的小組按照M分支的方式持續(xù)分裂。整個(gè)過(guò)程可以表示為如圖7所示的多分支樹(shù)結(jié)構(gòu)，其中第一層的時(shí)隙數(shù)為初始分組數(shù)L1，第一層中每個(gè)碰撞時(shí)隙都將延伸為一棵M分支樹(shù)。

在BMT 中，標(biāo)簽通過(guò)閱讀器的反饋信息調(diào)整其時(shí)隙計(jì)數(shù)器值，及時(shí)消除即將產(chǎn)生的空閑時(shí)隙。故在單輪識(shí)別中所需時(shí)隙數(shù)即圖7 中所有成功時(shí)隙和碰撞時(shí)隙數(shù)之和，即

其中，等號(hào)右邊第一項(xiàng)為成功時(shí)隙數(shù)，第二項(xiàng)為由捕獲效應(yīng)產(chǎn)生的成功時(shí)隙數(shù)，第三項(xiàng)為碰撞時(shí)隙數(shù)，SA(k)為由初始分組中發(fā)生碰撞的時(shí)隙衍生出的多分支樹(shù)所包含時(shí)隙數(shù)。采用遞歸方法可以得到SA(k)的表達(dá)式為

其中，等號(hào)右邊第一項(xiàng)為該層中原本的成功時(shí)隙數(shù)，第二項(xiàng)為由捕獲效應(yīng)產(chǎn)生的成功時(shí)隙數(shù)，第三項(xiàng)為碰撞時(shí)隙數(shù)，每個(gè)碰撞時(shí)隙又將衍生出一個(gè)M分支的子樹(shù)。由式(7)～式(9)可得每一輪中識(shí)別階段所需時(shí)隙數(shù)。

接下來(lái)，分析單輪識(shí)別過(guò)程中的隱藏標(biāo)簽數(shù)。當(dāng)k個(gè)標(biāo)簽同時(shí)回復(fù)發(fā)生捕獲效應(yīng)時(shí)，有k?1 個(gè)標(biāo)簽被隱藏和標(biāo)記，并進(jìn)入下一輪的識(shí)別過(guò)程。結(jié)合捕獲效應(yīng)概率模型，可得每一輪中被隱藏的標(biāo)簽數(shù)量Thide(n)為

其中，等號(hào)右邊第一項(xiàng)為該層中發(fā)生捕獲效應(yīng)時(shí)被隱藏的標(biāo)簽數(shù)量，第二項(xiàng)為由該層碰撞時(shí)隙衍生出的M分支樹(shù)中的隱藏標(biāo)簽數(shù)。采用類(lèi)似方法可得

由此可得單輪識(shí)別過(guò)程中被隱藏的標(biāo)簽數(shù)量。綜上，將式(8)和式(10)代入式(6)中可得識(shí)別階段的系統(tǒng)效率。

5 仿真分析

仿真環(huán)境包括一個(gè)閱讀器和多個(gè)被動(dòng)式標(biāo)簽，且每個(gè)標(biāo)簽都有唯一的128 bit ID。閱讀器和標(biāo)簽之間的數(shù)據(jù)傳輸率為160 kbit/s；表2 中的每個(gè)命令都用4 bit 表示；幀參數(shù)L，反饋?zhàn)址甪ds 以及哈希確認(rèn)消息H16的長(zhǎng)度都為16 bit；t1=t2=25 μs，t3=12.5 μs。采用MATLAB 2018a 進(jìn)行仿真，且每個(gè)仿真結(jié)果都是500 次仿真的平均值。

在仿真分析中，首先對(duì)BMT 協(xié)議估計(jì)階段的時(shí)間開(kāi)銷(xiāo)和總識(shí)別時(shí)間進(jìn)行對(duì)比分析，其次給出功率門(mén)限比對(duì)BMT 協(xié)議識(shí)別性能的影響，最后分別對(duì)BMT 識(shí)別所有標(biāo)簽所需的碰撞時(shí)隙數(shù)和空閑時(shí)隙數(shù)以及平均識(shí)別時(shí)間進(jìn)行分析。與捕獲效應(yīng)下標(biāo)簽識(shí)別最相關(guān)的同類(lèi)協(xié)議進(jìn)行比較，包括CMAP[8]、GQT[12]、GBT[13]和ASTSA[20]。其中，CMAP 是對(duì)捕獲概率進(jìn)行估計(jì)并優(yōu)化動(dòng)態(tài)幀時(shí)隙Aloha 識(shí)別過(guò)程的最優(yōu)協(xié)議；GQT、GBT 和ASTSA 是考慮捕獲效應(yīng)下標(biāo)簽可靠識(shí)別的代表性協(xié)議。由于CMAP 只考慮單輪識(shí)別的情況，為了仿真對(duì)比的公平性，考慮將ASTSA 中的靜默標(biāo)記方法應(yīng)用到CMAP 中，實(shí)現(xiàn)可靠識(shí)別。考慮識(shí)別性能在標(biāo)簽數(shù)量變化情況下的穩(wěn)定性，本文給出Z=5 dB，標(biāo)簽數(shù)量從100 變化到1 000 時(shí)各協(xié)議的仿真結(jié)果。

5.1 估計(jì)階段的時(shí)間開(kāi)銷(xiāo)

表3 給出了Z分別為3 dB 和5 dB 時(shí)BMT 協(xié)議在估計(jì)階段和整個(gè)識(shí)別過(guò)程的時(shí)間開(kāi)銷(xiāo)對(duì)比情況。

表3 BMT 協(xié)議估計(jì)階段的時(shí)間占比

表3 中估計(jì)時(shí)間和總時(shí)間隨標(biāo)簽數(shù)量的增加而增加，而估計(jì)階段的時(shí)間占比隨標(biāo)簽數(shù)量的增加而減少。在BMT 識(shí)別過(guò)程中，標(biāo)簽估計(jì)階段的時(shí)間開(kāi)銷(xiāo)非常少，且時(shí)間占比不超過(guò)6%。隨著標(biāo)簽數(shù)量的增加，識(shí)別階段的時(shí)間開(kāi)銷(xiāo)增加較多，而估計(jì)階段增加的時(shí)間相對(duì)較少。因此隨著標(biāo)簽數(shù)量的增加，估計(jì)階段的時(shí)間占比有所下降。此外，隨著Z的增加，估計(jì)階段的時(shí)間占比隨之降低。這主要是因?yàn)榘l(fā)生捕獲效應(yīng)的概率隨Z的增加而降低，Z越大，發(fā)生捕獲效應(yīng)的情況越少；Z越小，捕獲效應(yīng)發(fā)生的情況越多，所以估計(jì)時(shí)間略長(zhǎng)。

5.2 捕獲效應(yīng)對(duì)識(shí)別性能的影響

由系統(tǒng)模型分析可知，捕獲效應(yīng)發(fā)生的概率隨Z值的增加而降低?？紤]該門(mén)限值對(duì)算法識(shí)別性能的整體影響，圖8 給出了BMT 協(xié)議識(shí)別500 個(gè)標(biāo)簽所需各類(lèi)時(shí)隙數(shù)的變化情況。從圖8 中可以看到，隨著Z值增大，發(fā)生捕獲效應(yīng)的時(shí)隙數(shù)逐漸減少，這與圖3 中捕獲效應(yīng)發(fā)生概率的變化趨勢(shì)一致。其次，隨捕獲效應(yīng)時(shí)隙數(shù)的減少，由碰撞時(shí)隙轉(zhuǎn)化為成功時(shí)隙的數(shù)量隨之減少，使碰撞時(shí)隙數(shù)相應(yīng)增加。最后，由圖8 可知隨功率比門(mén)限的增大，識(shí)別所有標(biāo)簽所需總時(shí)隙數(shù)有增加趨勢(shì)。

5.3 碰撞時(shí)隙數(shù)

當(dāng)Z=5 dB 時(shí)，各協(xié)議碰撞時(shí)隙數(shù)隨標(biāo)簽數(shù)量變化的仿真結(jié)果如圖9 所示。

由圖9 可知，碰撞時(shí)隙數(shù)隨標(biāo)簽數(shù)量的增加呈線性增長(zhǎng)，且本文提出的BMT 協(xié)議產(chǎn)生的碰撞時(shí)隙數(shù)最少，其次是CMAP 和ABTSA，而GBT 和GQT 產(chǎn)生的碰撞時(shí)隙數(shù)較多。相較于CMAP，BMT的碰撞時(shí)隙數(shù)減少了約40%。GBT 和GQT 通過(guò)傳統(tǒng)的二叉樹(shù)對(duì)標(biāo)簽進(jìn)行分組，分裂速度較慢，且前期識(shí)別過(guò)程大部分為碰撞時(shí)隙，因此產(chǎn)生的碰撞時(shí)隙數(shù)最多。ABTSA 采用樹(shù)時(shí)隙Aloha 的方式將標(biāo)簽分成多個(gè)組，適當(dāng)減少了前期識(shí)別過(guò)程中的碰撞時(shí)隙數(shù)。但由于初始幀長(zhǎng)與標(biāo)簽數(shù)量的不匹配，ABTSA 產(chǎn)生的碰撞時(shí)隙數(shù)仍然較多。CMAP 通過(guò)對(duì)標(biāo)簽數(shù)量和捕獲概率進(jìn)行估計(jì)，并以此調(diào)整幀長(zhǎng)，產(chǎn)生的碰撞時(shí)隙數(shù)相對(duì)較少。BMT 通過(guò)多分支樹(shù)的方式對(duì)標(biāo)簽進(jìn)行分組識(shí)別，減少標(biāo)簽發(fā)生碰撞的概率，進(jìn)一步減少碰撞時(shí)隙數(shù)。

5.4 空閑時(shí)隙數(shù)

各協(xié)議的空閑時(shí)隙數(shù)對(duì)比結(jié)果如圖10 所示。圖10 中，CMAP 產(chǎn)生的空閑時(shí)隙最多，GQT、ABTSA 和GBT 依次減少，BMT 協(xié)議幾乎不產(chǎn)生空閑時(shí)隙。BMT 協(xié)議只有在估計(jì)階段才產(chǎn)生空閑時(shí)隙，在識(shí)別階段不產(chǎn)生空閑時(shí)隙。在估計(jì)階段，如果沒(méi)有標(biāo)簽選擇當(dāng)前時(shí)隙所對(duì)應(yīng)的比特位，該時(shí)隙為空閑時(shí)隙。由表3 可知，估計(jì)階段的時(shí)間占比非常小，因此該階段產(chǎn)生的空閑時(shí)隙數(shù)也相對(duì)較少。在識(shí)別階段，標(biāo)簽將時(shí)隙選擇信息融入標(biāo)簽回復(fù)信息中，閱讀器通過(guò)反饋檢測(cè)到的標(biāo)簽時(shí)隙選擇信息，使標(biāo)簽重新調(diào)整時(shí)隙計(jì)數(shù)器，消除空閑時(shí)隙。因此，BMT 產(chǎn)生的空閑時(shí)隙非常少。

GBT 根據(jù)標(biāo)簽的時(shí)隙計(jì)數(shù)器進(jìn)行分組，產(chǎn)生的空閑時(shí)隙比其他協(xié)議少。ABTSA 根據(jù)估計(jì)結(jié)果動(dòng)態(tài)調(diào)整幀長(zhǎng)，產(chǎn)生的空閑時(shí)隙比GBT 略多。GQT受標(biāo)簽ID 分布影響較大，因此當(dāng)ID 長(zhǎng)度較長(zhǎng)，標(biāo)簽數(shù)量相對(duì)較少時(shí)產(chǎn)生的空閑時(shí)隙較多。CMAP 考慮到空閑時(shí)隙比碰撞時(shí)隙和成功時(shí)隙的時(shí)間短，通過(guò)增大幀長(zhǎng)設(shè)置減少碰撞時(shí)隙數(shù)，使空閑時(shí)隙數(shù)急劇增加，因此CMAP 產(chǎn)生的空閑時(shí)隙數(shù)較其他協(xié)議更多。

5.5 平均識(shí)別時(shí)間

最后，圖11 給出了各個(gè)協(xié)議平均識(shí)別一個(gè)標(biāo)簽所需時(shí)間。從圖11 中可以看到，本文提出的BMT協(xié)議平均識(shí)別一個(gè)標(biāo)簽所需時(shí)間最少，約為1.1 ms，ABTSA 其次，CMAP、GBT 和GQT 所需時(shí)間依次增加。由圖9 和圖10 可知，BMT 產(chǎn)生的碰撞和空閑時(shí)隙比其他相關(guān)協(xié)議都少，故平均識(shí)別時(shí)間最短。ABTSA 雖然比CMAP 產(chǎn)生的碰撞時(shí)隙多，但其產(chǎn)生的空閑時(shí)隙較CMAP 少得多，因此平均識(shí)別時(shí)間比CMAP 短。GBT 和GQT 產(chǎn)生了過(guò)多碰撞時(shí)隙，識(shí)別時(shí)間最長(zhǎng)。相較于ABTSA、CMAP、GBT和GQT，BMT 的識(shí)別時(shí)間分別縮短了約15%、37%、50%和63%。

6 結(jié)束語(yǔ)

本文提出了基于比特檢測(cè)的多分支樹(shù)標(biāo)簽識(shí)別BMT 協(xié)議，該協(xié)議通過(guò)比特檢測(cè)標(biāo)簽估計(jì)策略和多分支樹(shù)標(biāo)簽識(shí)別算法對(duì)捕獲效應(yīng)下的RFID 標(biāo)簽進(jìn)行高效可靠的識(shí)別，有效減少了標(biāo)簽估計(jì)和識(shí)別過(guò)程所需時(shí)隙數(shù)，縮短了識(shí)別時(shí)延。此外，本文還提出基于哈希靜默的方法來(lái)減少靜默已識(shí)別標(biāo)簽和標(biāo)記隱藏標(biāo)簽的通信開(kāi)銷(xiāo)，進(jìn)一步提高識(shí)別效率。理論分析和仿真對(duì)比表明，所提協(xié)議能有效提高識(shí)別效率，且相較于已有協(xié)議，所提協(xié)議將識(shí)別時(shí)間縮短了至少15%。在后續(xù)工作中，筆者將深入研究靜默已識(shí)別標(biāo)簽和標(biāo)記隱藏標(biāo)簽的有效方法，進(jìn)一步提高識(shí)別效率。