沈 平 袁 瑛 周 潘

1(湖北職業(yè)技術(shù)學(xué)院計算機中心 湖北 孝感 432000)2(湖北職業(yè)技術(shù)學(xué)院信息技術(shù)學(xué)院 湖北 孝感 432000)3(華中科技大學(xué)電子信息與通信學(xué)院 湖北 武漢 430074)

0 引 言

RFID技術(shù)是物聯(lián)網(wǎng)領(lǐng)域中極為重要的一部分[1]，目前已廣泛應(yīng)用于目標(biāo)追蹤、室內(nèi)定位、倉儲管理等社會生產(chǎn)與人類生活的諸多領(lǐng)域中[2]。在實際的RFID應(yīng)用中，一個典型的RFID系統(tǒng)主要由后端服務(wù)器、RFID閱讀器與一系列的電子標(biāo)簽組成。當(dāng)標(biāo)簽處于閱讀器的識別范圍內(nèi)時，閱讀器識別標(biāo)簽并通知后端服務(wù)器，如果同一個閱讀器的識別范圍內(nèi)存在多個標(biāo)簽[3]，那么多個標(biāo)簽會競爭同一個信道，導(dǎo)致信號干擾與標(biāo)簽之間的碰撞[4]。目前解決標(biāo)簽之間碰撞問題的方案主要有兩種[5]：基于分叉樹的確定性算法[6]，基于ALOHA的非確定性算法[7]。ALOHA算法的效率較高，該算法根據(jù)標(biāo)簽的實際數(shù)量動態(tài)地調(diào)節(jié)幀長，從而保持系統(tǒng)效率的最大化，因此，準(zhǔn)確估計標(biāo)簽的數(shù)量是RFID系統(tǒng)防碰撞重要的預(yù)處理步驟[8]。此外，許多應(yīng)用場景(倉儲系統(tǒng)等)也需要統(tǒng)計電子標(biāo)簽的數(shù)量，因此，RFID的標(biāo)簽估計是RFID領(lǐng)域一個重要的基礎(chǔ)研究課題[9]。

目前主流的電子標(biāo)簽估計算法主要有Low Bond估計算法[5]、碰撞率估計算法[5]與概率估計算法[10]等，其中概率估計算法具有較高的估計準(zhǔn)確率，傳統(tǒng)的概率估計算法為單階段估計協(xié)議，其計算復(fù)雜度較高。文獻(xiàn)[11]對傳統(tǒng)概率估計算法進(jìn)行了改進(jìn)，將估計分為兩個階段，第一階段粗略地估計，第二階段再提高估計的準(zhǔn)確率，但該算法的時間效率為O(1/2+logN)(其中為置信區(qū)間，N為電子標(biāo)簽的數(shù)量)，對于大規(guī)模RFID系統(tǒng)的時間效率較低。

為了解決大規(guī)模RFID系統(tǒng)中標(biāo)簽估計時間效率較低的問題，提出一種高效率的大規(guī)模RFID標(biāo)簽估計算法。算法在滿足期望的準(zhǔn)確率前提下，實現(xiàn)了O((1/log2)2)的時間復(fù)雜度?，F(xiàn)有的標(biāo)簽估計方案利用各個時隙的信息極少(例如：是否為空閑時隙)，本文算法則利用較多的時隙信息。此外，被動型RFID標(biāo)簽的計算能力有限，難以生成幾何分布的隨機數(shù)，為此本文設(shè)計了一種簡單的幾何分布隨機數(shù)生成機制。

1 系統(tǒng)模型

圖1所示是移動互聯(lián)網(wǎng)場景的RFID系統(tǒng)模型，一個普通的RFID系統(tǒng)則包含一個后端服務(wù)器、若干RFID閱讀器與大量的RFID電子標(biāo)簽。每個閱讀器與后端服務(wù)器連接，后端服務(wù)器控制各個RFID閱讀器，初始化標(biāo)簽數(shù)量估計的程序，然后，RFID閱讀器發(fā)送標(biāo)簽估計命令至RFID標(biāo)簽，標(biāo)簽響應(yīng)閱讀器，最終，閱讀器將標(biāo)簽響應(yīng)上報至服務(wù)器。

圖1 移動RFID系統(tǒng)的網(wǎng)絡(luò)模型

假設(shè)N為RFID標(biāo)簽的數(shù)量，N′為估計的標(biāo)簽數(shù)量，那么標(biāo)簽估計算法的期望準(zhǔn)確率可表示為Pr(|N′-N|≤N)≥1-δ，其中為置信區(qū)間，δ為誤差率，與δ決定了期望的估計準(zhǔn)確率。例如：標(biāo)簽的實際數(shù)量為100 000，期望的=0.05，δ=0.01，那么估計結(jié)果的區(qū)間為[95 000,105 000]，最低準(zhǔn)確率為99%。

2 標(biāo)簽數(shù)量估計

2.1 RFID標(biāo)簽估計的算法

本算法基于Aloha協(xié)議[12]，但是每幀僅包含一個時隙。圖2(a)、圖2(b)、圖2 (c)分別為服務(wù)器、RFID閱讀器與RFID標(biāo)簽的算法流程框圖。閱讀器發(fā)出一條標(biāo)簽估計命令，所有的RFID標(biāo)簽同時響應(yīng)該命令，響應(yīng)報文的大小相同，每個報文僅有一個比特為“1”，其他比特均為“0”，基于概率為1/(2i)的幾何分布選出“1”的比特位。最終共有N/(2i)個標(biāo)簽在各自響應(yīng)報文的第i比特設(shè)置“1”。在協(xié)議每輪的標(biāo)簽估計中，服務(wù)器搜索所有響應(yīng)的第一個“0”比特位j，將j作為標(biāo)簽估計算法的輸入變量。

根據(jù)文獻(xiàn)[13]，幾何hash的結(jié)果與數(shù)量N之間存在一定的關(guān)系，文獻(xiàn)[14]設(shè)計了LoF機制，將該理論應(yīng)用于RFID標(biāo)簽估計算法中。本算法基于LoF算法，因為LoF算法在每輪協(xié)議中需要多個時隙參與處理，而本算法為了提高計算的效率，僅需要一個時隙，所以需要對LoF算法進(jìn)行修改。

下文描述了使用幾何分布的屬性估計標(biāo)簽數(shù)量的方法：假設(shè)j是響應(yīng)報文中第一個“0”比特的比特位，j的期望值應(yīng)當(dāng)滿足下式：

E(j)≈log2(φ×N)

(1)

將式(1)的N與E(j)替換為估計值N′與j，其中φ=0.775 351，N′為標(biāo)簽數(shù)量N的估計值，可得下式：

j≈log2(φ×N′)

(2)

根據(jù)式(2)可推導(dǎo)出N′：

N′=1/φ×2j=1.289 7×2j

(3)

因為估計的結(jié)果是漸近無偏估計，所以本算法通過進(jìn)行幾次獨立的估計，將幾次估計的平均值作為最終的結(jié)果。假設(shè)共進(jìn)行m輪的標(biāo)簽估計，那么最終結(jié)果定義為下式：

j′=(j1+j2+…+jm)/m

(4)

式中:j′為平均值，jk為第k輪估計、第一個“0”的比特位。修改后的估計結(jié)果變化為下式：

(5)

下文描述了實現(xiàn)期望估計準(zhǔn)確率的方法，即Pr(|N′-N|≤N)≥1-δ，其中是置信區(qū)間，δ是誤差率。假設(shè)根據(jù)中心極限定理，可得下式：

X=(j′-μ)/σ～N(0,1)

(6)

假設(shè)X是均值為0、方差為1的高斯函數(shù)，累積分布函數(shù)定義為：

(7)

假設(shè)一個常量c滿足式(8)，其中erf是高斯誤差函數(shù)，通過求解式(8)可獲得c：

(8)

Pr[|N′-N|≤N]=Pr[(1-)N≤N′≤(1+)N]=

Pr[log2((1-)φN)]≤j′≤

log2((1+)φN)

(9)

從式(9)可看出，如果-c≥-(log2((1-)φN)-μ)/σ，c≤(log2((1+)φN)-μ)/σ，即可保證Pr(|N′-N|≤N)≥1-δ成立。求解該不等式，可得滿足目標(biāo)估計準(zhǔn)確率所需的最小輪數(shù)m，如下式所示：

m≥max{[(-σ∞c)/(log2(1-))]2·

[(σ∞c)/(log2(1+))]2}

(10)

綜上所述，為了滿足給定的標(biāo)簽估計準(zhǔn)確率需求，標(biāo)簽估計算法需要運行m輪(每輪需要一個時隙)，因此，本算法的時間復(fù)雜度為O((1/(log2))2)個時隙。

(a) 后端服務(wù)器算法

(b) 閱讀器的算法

(c) 標(biāo)簽的算法圖2 本算法服務(wù)器、閱讀器與標(biāo)簽的算法

2.2 標(biāo)簽響應(yīng)的累加

本算法需分析標(biāo)簽響應(yīng)報文的信息，為此，引入了響應(yīng)累加的概念，如果多個信號使用相同的頻率與相位，那么產(chǎn)生了一個強化的信號，信號的幅度為多個信號之和。在無線網(wǎng)絡(luò)中，許多研究[15]使用該思想實現(xiàn)數(shù)據(jù)的洪泛傳輸。

響應(yīng)累加需要兩個條件：一是多個閱讀器同時發(fā)送認(rèn)證報文，另一個是標(biāo)簽響應(yīng)報文之間的時間偏移應(yīng)當(dāng)小于半個脈沖的時長，否則干擾報文之間無法同步。本文的響應(yīng)累加機制需要多標(biāo)簽的報文為同步傳輸，在圖3中，標(biāo)簽1與標(biāo)簽2的第一個比特為“1”，標(biāo)簽2的第二個比特為“1”。將“1”比特定義為ON信號，閱讀器接收同步信號后，獲得一個比特序列，其中第三比特是第一個“0”比特，因此，第三比特的信息作為估計的RFID數(shù)量。圖4所示是標(biāo)簽1、2、3響應(yīng)比特流累加的信號示意圖。標(biāo)簽1與標(biāo)簽2的第1比特位為“ON”信號，標(biāo)簽3的第2比特位為“ON”信號，閱讀器的解碼結(jié)果為“11…”。

圖3 EPC C1G2規(guī)范的基本處理過程

圖4 標(biāo)簽1、2、3響應(yīng)比特流累加的信號示意圖

3 本算法的效率分析

本算法在每輪中僅需要一個時隙，輪數(shù)m與期望的估計準(zhǔn)確率直接相關(guān)，式(10)所需的時隙數(shù)量為O((1/(log2))2)，優(yōu)于其他已有的標(biāo)簽估計算法。此外，本算法的時間復(fù)雜度主要由誤差率決定，與標(biāo)簽數(shù)量無關(guān)，因此本算法對于大規(guī)模的RFID系統(tǒng)具有較高的時間效率。

3.1 標(biāo)簽響應(yīng)報文的大小

標(biāo)簽響應(yīng)報文的大小對標(biāo)簽估計的性能具有影響，現(xiàn)有的協(xié)議大多采用16比特的響應(yīng)報文。本協(xié)議采用幾何分布，因此32比特的報文足以估計232個標(biāo)簽。在開始階段，標(biāo)簽的數(shù)量是未知的，因此本算法將標(biāo)簽響應(yīng)報文的比特數(shù)初始化為32位。在運行階段，計算各輪j值的平均值，然后將響應(yīng)報文的比特數(shù)調(diào)節(jié)為j的平均值。例如：RFID系統(tǒng)的標(biāo)簽數(shù)量為100 000，那么本算法的響應(yīng)報文比特數(shù)約為16。

3.2 低計算復(fù)雜度的幾何分布隨機數(shù)生成機制

本算法需要選擇“1”的比特位，該比特位服從幾何分布，每輪的估計算法均需要生成該隨機數(shù)，計算成本較大。本算法的后端服務(wù)器生成一個均勻隨機分布的隨機數(shù)，每輪估計程序中，服務(wù)器均廣播一個新的隨機數(shù)(表示為Rserver)，每個標(biāo)簽中均預(yù)置一個獨立、隨機的隨機數(shù)(表示為Ri)，標(biāo)簽估計程序每輪將Rserver與Ri進(jìn)行異或操作，生成一個新的隨機數(shù)，由此既降低了標(biāo)簽生成隨機數(shù)的計算成本，也生成了滿足幾何分布需求的隨機數(shù)。

4 非理想信道的容錯機制

大多數(shù)文獻(xiàn)均假設(shè)信道為理想信道，然而，無線信道一般會發(fā)生錯誤。理想信道說明標(biāo)簽響應(yīng)、閱讀器命令與信道檢測的成功率均為100%，而非理想信道則說明標(biāo)簽響應(yīng)、閱讀器命令與信道檢測的成功率不是100%。跟標(biāo)簽估計過程相關(guān)的錯誤可能有三種情況：(1) 標(biāo)簽響應(yīng)發(fā)生丟包；(2) 噪聲或者干擾導(dǎo)致閱讀器將一個空閑信道誤檢為忙信道；(3) 閱讀器命令發(fā)生丟包。

現(xiàn)有的大多數(shù)標(biāo)簽估計算法依賴時隙的模式，因此，它們的估計準(zhǔn)確率受信道故障的影響較大。本協(xié)議中沒有空閑時隙，因為所有的標(biāo)簽均假設(shè)在每個時隙中同時地傳輸響應(yīng)報文，因此，如果閱讀器檢測到空閑時隙，則作為第3種錯誤情況。在第2種錯誤情況中，干擾與噪聲對尋找第一個“0”比特產(chǎn)生影響，如果該輪的j值過大或過小，則忽略該j值。

(11)

(12)

(13)

5 仿真實驗與結(jié)果分析

仿真實驗的標(biāo)簽使用TP-WISP 5.0標(biāo)簽，閱讀器則使用USRP N210閱讀器，圖5(a)所示是USRP N210的實物圖，閱讀器使用RFX900子版，工作頻率為900 MHz，各有兩個ALR-8696-C天線。USRP N210通過以太網(wǎng)與一臺PC機連接，PC機為Ubuntu Linux操作系統(tǒng)，圖5(b)為實驗環(huán)境圖。使用可編程的WISP 5.0硬件與固件仿真電子標(biāo)簽，WISP標(biāo)簽可以無線地吸收能量并具有返回響應(yīng)的能力，WISP固件則實現(xiàn)了EPC Global C1G2協(xié)議[16]。

(a) USRP N210的實物圖 (b) 實驗環(huán)境圖圖5 實驗環(huán)境

本文設(shè)計的標(biāo)簽響應(yīng)累加機制需要標(biāo)簽響應(yīng)時間嚴(yán)格的同步，所以采用三個電子標(biāo)簽來評估標(biāo)簽響應(yīng)累加機制的效果，圖6所示是本協(xié)議中閱讀器與三個標(biāo)簽之間的通信波形圖。在USRP閱讀器中增加標(biāo)簽估計命令，閱讀器周期地發(fā)出標(biāo)簽估計命令，每個標(biāo)簽估計命令包含一個32比特的隨機數(shù)，每個標(biāo)簽收到標(biāo)簽估計命令后使用收到的隨機數(shù)生成響應(yīng)報文，然后將響應(yīng)報文發(fā)送至閱讀器。

圖6 本協(xié)議中閱讀器與三個標(biāo)簽之間的通信波形

本文設(shè)計的標(biāo)簽響應(yīng)累加機制需要標(biāo)簽響應(yīng)時間嚴(yán)格的同步。在圖7(a)中，閱讀器在發(fā)送CE命令之后測量了標(biāo)簽響應(yīng)的時間延遲，響應(yīng)的時間延遲范圍為71 μs～74 μs，響應(yīng)的延遲偏差主要由標(biāo)簽的計算能力(例如：生成響應(yīng)的時間)引起。為了使標(biāo)簽響應(yīng)同步，必須最小化標(biāo)簽響應(yīng)延遲的偏差，因此在標(biāo)簽響應(yīng)之前設(shè)置一個軟件延遲，該軟件延遲根據(jù)每個標(biāo)簽的計算能力設(shè)置不同的時長。圖7(b)所示是增加軟件延遲之后的波形，可看出99.9%的響應(yīng)時間均在1 μs的時間段內(nèi)，所以將響應(yīng)報文的一比特時長設(shè)為2 μs，頻率為500 kHz。

(a) 無軟件延遲的時序

(b) 增加軟件延遲的時序圖7 閱讀器發(fā)出命令與收到標(biāo)簽響應(yīng)的時間延遲

為了評估本文集體干擾的有效性，將三個WISP標(biāo)簽的響應(yīng)設(shè)為不同比特流：標(biāo)簽1與標(biāo)簽2的比特流均為“1000…”，標(biāo)簽3的比特流為“0010…”。圖8所示是閱讀器接收的信號，圖中在0.63 μs～0.65 μs之間的信號幅度最高，該時段兩個ON信號疊加，在0.65 μs～0.68 μs之間則無信號，在0.68 μs～0.70 μs之間則有信號，該信號的幅度低于第一比特，來自于第三標(biāo)簽的ON信號。閱讀器將接收的信號強度與閾值比較，決定最終聚集的比特流，該案例的比特流為“1010…”。

將3個WISP標(biāo)簽置于閱讀器約1米遠(yuǎn)的位置，進(jìn)行1 000次重復(fù)實驗，結(jié)果證明99%的結(jié)果均符合標(biāo)簽響應(yīng)累加機制的期望，由此證明了本算法標(biāo)簽響應(yīng)累加機制的有效性。

圖8 標(biāo)簽響應(yīng)累加機制實驗中閱讀器接收的信號

6 對比實驗與結(jié)果分析

為了評估本算法對大規(guī)模RFID系統(tǒng)的標(biāo)簽估計性能，在不同的場景下測試了本算法的性能?；赑ython 3.2編程實現(xiàn)了事件驅(qū)動仿真平臺，表1所示是本文仿真實驗的參數(shù)。將本算法與AAAS[17]、ZoE[18]與SRC[19]三個大規(guī)模標(biāo)簽估計算法進(jìn)行比較，其中AAAS與SRC兩個算法并未考慮非理想信道的場景，而ZOE算法則設(shè)計了容錯機制，ZOE考慮了第2、3種錯誤場景，但并未考慮第1種錯誤場景。

表1 仿真實驗的參數(shù)設(shè)置

6.1 性能度量指標(biāo)

使用估計誤差作為標(biāo)簽估計準(zhǔn)確率的度量指標(biāo)，估計誤差=|E(N′/N)-1.0|，式中N′是估計的標(biāo)簽數(shù)量，N是實際的標(biāo)簽數(shù)量，估計誤差越接近0，估計準(zhǔn)確率則越高。將各個估計算法使用的時隙數(shù)量作為時間效率的度量指標(biāo)。

6.2 本算法的準(zhǔn)確率

圖9所示是本算法不同的δ值所獲得的標(biāo)簽估計誤差，圖中δ值固定為0.01，滿足估計誤差的值變化范圍為0.01～0.32。值越低，為了滿足期望的估計誤差，則估計算法重復(fù)的輪數(shù)越多。

圖9 本算法不同的δ值所獲得的標(biāo)簽估計誤差

6.3 時間效率比較

圖10 四種標(biāo)簽估計算法的時間效率結(jié)果

圖11 四個算法的時間效率與估計誤差之間的關(guān)系

圖12 四個算法的時間效率與置信區(qū)間之間的關(guān)系

6.4 不可靠信道的估計性能

上述實驗評估了本算法對于理想信道的估計準(zhǔn)確率與時間效率，沒有考慮響應(yīng)丟包、命令丟包與噪聲等非理想場景。最終，測試了本算法在不同信道條件下的時間效率與估計準(zhǔn)確率。因為上述實驗中僅ZOE的性能與本算法最為接近，所以僅將ZOE與本算法進(jìn)行比較。

圖13所示是響應(yīng)丟包的實驗結(jié)果，圖13(a)表示估計的標(biāo)簽數(shù)量與標(biāo)簽響應(yīng)丟包率的關(guān)系，圖13(b)表示算法的時間效率與標(biāo)簽響應(yīng)丟包率的關(guān)系。第4節(jié)設(shè)計了容錯機制來解決該問題。圖13(a)的標(biāo)簽響應(yīng)丟包率設(shè)為0～32%，可看出隨著響應(yīng)報文丟包率的提高，ZOE算法估計的標(biāo)簽數(shù)量逐漸下降，而本算法則基本保持穩(wěn)定，由此證明了本算法容錯機制的有效性，而ZOE算法并未設(shè)計這種故障的容錯機制。

(a) 估計的標(biāo)簽數(shù)量與標(biāo)簽響應(yīng)丟包率的關(guān)系

(b) 算法的時間效率與標(biāo)簽響應(yīng)丟包率的關(guān)系圖13 標(biāo)簽響應(yīng)丟包情況的性能

圖14所示是命令丟包(噪聲或者干擾導(dǎo)致)對標(biāo)簽估計算法性能的影響。本文設(shè)計了閾值機制，篩選出合理的j值，如果j值不在預(yù)設(shè)的閾值范圍內(nèi)，則認(rèn)為該j值為異常值，并忽略該異常值，仿真實驗中將該閾值設(shè)為5，假設(shè)j的平均值為j′，如果j′-5

(a) 估計的標(biāo)簽數(shù)量與信道故障率的關(guān)系

(b) 算法的時間效率與信道故障率的關(guān)系圖14 信道噪聲或者干擾情況的性能

本算法不僅提高了標(biāo)簽估計的時間效率，并且實現(xiàn)了容錯能力，為了將本算法應(yīng)用于大規(guī)模的被動標(biāo)簽，而被動標(biāo)簽的能量與計算能力均十分有限，所以本算法主要在服務(wù)器上進(jìn)行計算處理，一方面為服務(wù)器帶來了計算負(fù)擔(dān)，另一方面也增加了服務(wù)器與閱讀器之間的帶寬負(fù)擔(dān)。如果采用分布式服務(wù)器與高速的有線網(wǎng)絡(luò)即可滿足本算法的應(yīng)用需求。

7 結(jié) 語

為了解決大規(guī)模RFID系統(tǒng)中標(biāo)簽估計時間效率較低的問題，提出一種高效率的大規(guī)模RFID標(biāo)簽估計算法，本算法在滿足期望的準(zhǔn)確率前提下，實現(xiàn)了O((1/log2)2)的時間復(fù)雜度。目前基于概率的標(biāo)簽估計算法一般為多時隙、多階段機制，而本算法則為單時隙、單階段機制，極大地提高了時間效率，此外，本算法在服務(wù)器中生成幾何隨機數(shù)，降低了電子標(biāo)簽的計算負(fù)擔(dān)。本文也考慮了非理想信道的容錯機制，對于標(biāo)簽響應(yīng)發(fā)生丟包、噪聲或者干擾導(dǎo)致閱讀器將一個空閑信道誤檢為忙信道、閱讀器命令發(fā)生丟包均取得了明顯的效果。