物聯(lián)網(wǎng)中大規(guī)模無(wú)線射頻識(shí)別標(biāo)簽的容錯(cuò)估計(jì)算法

沈 平 袁 瑛 周 潘

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

E(j)≈log2(φ×N)

(1)

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

j≈log2(φ×N′)

(2)

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

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

(3)

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

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

(4)

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

(5)

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

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

(6)

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

(7)

假設(shè)一個(gè)常量c滿足式(8)，其中erf是高斯誤差函數(shù)，通過(guò)求解式(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)估計(jì)準(zhǔn)確率所需的最小輪數(shù)m，如下式所示：

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

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

(10)

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

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

(b) 閱讀器的算法

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

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

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

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

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

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

3 本算法的效率分析

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

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

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

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

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

4 非理想信道的容錯(cuò)機(jī)制

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

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

(11)

(12)

(13)

5 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

(a) 無(wú)軟件延遲的時(shí)序

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

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

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

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

6 對(duì)比實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

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

6.3 時(shí)間效率比較

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

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

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

6.4 不可靠信道的估計(jì)性能

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

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

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

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

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

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

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

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

7 結(jié) 語(yǔ)

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