楊茜，吳海鋒，曾玉

（云南民族大學(xué) 電氣信息工程學(xué)院，云南 昆明 650500）

1 引言

在物聯(lián)網(wǎng)[1]中，大量 RFID標(biāo)簽需被閱讀器快速識(shí)別，為提高識(shí)別效率，閱讀器通常一次識(shí)別多個(gè)標(biāo)簽。由于閱讀器識(shí)別標(biāo)簽采用共享的無線信道，標(biāo)簽沖突不可避免[2]。通常閱讀器采用防沖突協(xié)議來解決標(biāo)簽間沖突[3]，所以標(biāo)簽的防沖突協(xié)議在物聯(lián)網(wǎng)中起到了重要作用。

在被動(dòng)式RFID系統(tǒng)中，2個(gè)以上的標(biāo)簽同時(shí)發(fā)射信號(hào)并不一定導(dǎo)致沖突。在閱讀器磁場范圍內(nèi)，標(biāo)簽距閱讀器的位置遠(yuǎn)近不一，因此發(fā)射的信號(hào)也有強(qiáng)弱差別，而捕獲效應(yīng)可使信號(hào)較強(qiáng)的標(biāo)簽被閱讀器識(shí)別，而信號(hào)較弱的標(biāo)簽將被捕獲效應(yīng)隱藏。由于許多傳統(tǒng)的防沖突協(xié)議[3～17]均假設(shè)捕獲效應(yīng)不存在，但捕獲效應(yīng)恰恰在RFID系統(tǒng)中又是一個(gè)普遍現(xiàn)象。因此近幾年，如何在捕獲效應(yīng)的情況下解決標(biāo)簽沖突問題得到越來越多的關(guān)注[18～21]。

在被動(dòng)式RFID標(biāo)簽防沖突協(xié)議中，動(dòng)態(tài)幀時(shí)隙 ALOHA 類協(xié)議應(yīng)用非常廣泛[4～10,20～24]。該協(xié)議的基本思想是每個(gè)幀的長度動(dòng)態(tài)變化，即每個(gè)幀中的時(shí)隙數(shù)應(yīng)為每個(gè)幀中待識(shí)別的標(biāo)簽數(shù)[5～8]。然而，當(dāng)捕獲效應(yīng)發(fā)生時(shí)，該方法并不能使效率達(dá)到最優(yōu)，因?yàn)榇藭r(shí)的幀長不僅與標(biāo)簽數(shù)相關(guān)，還與捕獲效應(yīng)的概率相關(guān)[24]。由于標(biāo)簽數(shù)和概率值未知，因此需要估計(jì)它們。現(xiàn)有的算法雖然估計(jì)了這2個(gè)值，但是其復(fù)雜度較高。另外，現(xiàn)有算法均假定空時(shí)隙、成功時(shí)隙以及沖突時(shí)隙占用時(shí)間等長，以此設(shè)置最優(yōu)幀長，而在實(shí)際的 RFID系統(tǒng)中，各時(shí)隙并不相同，如EPC C1 Gen2[21]標(biāo)準(zhǔn)中規(guī)定了各時(shí)隙不等長，因此該設(shè)置并不能使識(shí)別效率達(dá)到最優(yōu)。

為優(yōu)化識(shí)別效率，本文針對(duì)RFID動(dòng)態(tài)幀時(shí)隙ALOHA防沖突協(xié)議提出了一種在捕獲效應(yīng)下的CATPE (capture-aware and tag-population estimation)協(xié)議。該協(xié)議通過空時(shí)隙數(shù)的觀測值來估計(jì)標(biāo)簽數(shù)和捕獲效應(yīng)發(fā)生的概率值，然后再設(shè)置最優(yōu)幀長。該算法降低了計(jì)算復(fù)雜度，并給出了兼容于EPC C1 Gen2 的非等時(shí)隙長下的最優(yōu)幀長設(shè)置，從而提高了系統(tǒng)的識(shí)別效率。

2 相關(guān)工作

GBT 協(xié)議[18]是為解決捕獲效應(yīng)而提出的一種二進(jìn)制樹（BT）類協(xié)議[11]，該協(xié)議解決了傳統(tǒng)BT類協(xié)議無法識(shí)別隱藏標(biāo)簽的問題，它讓閱讀器把識(shí)別的標(biāo)簽 ID返回給標(biāo)簽，那么隱藏的標(biāo)簽將會(huì)發(fā)現(xiàn)其自身的ID與閱讀器返回的ID不符，然后再進(jìn)入下一個(gè)識(shí)別循環(huán)再被識(shí)別。然而，GBT協(xié)議實(shí)質(zhì)上將幀長設(shè)置為2，當(dāng)捕獲效應(yīng)的概率較小時(shí)，其識(shí)別效率并不能達(dá)到最優(yōu)。

最優(yōu)Q算法[19]是EPC C1 Gen2標(biāo)準(zhǔn)中Q算法的改進(jìn)算法，它假定標(biāo)簽數(shù)已知，讓幀長等于標(biāo)簽數(shù)，這在無捕獲效應(yīng)的情況下識(shí)別效率能達(dá)到最優(yōu)。然而，當(dāng)捕獲效應(yīng)生時(shí)，最優(yōu)效率卻無法保證，因?yàn)榇藭r(shí)的幀長不僅與標(biāo)簽數(shù)還與捕獲效應(yīng)發(fā)生的概率相關(guān)[24]。另外，在標(biāo)簽數(shù)未知的應(yīng)用環(huán)境中，該方法也不適用。

CMEBE協(xié)議[24]通過二維搜索得到標(biāo)簽數(shù)和捕獲效應(yīng)概率值，然而其計(jì)算復(fù)雜度較高。并且，雖然該協(xié)議推導(dǎo)了最優(yōu)幀長表達(dá)式，但是它假定各時(shí)隙等長，這與實(shí)際RFID并不相符。

3 捕獲效應(yīng)下的最優(yōu)識(shí)別效率問題

在被動(dòng)式RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議中，識(shí)別效率定義為成功識(shí)別的時(shí)隙時(shí)間與總的時(shí)隙時(shí)間的比值。由于以下原因，捕獲效應(yīng)下與沒有捕獲效應(yīng)下的識(shí)別效率有所不同。第一，捕獲效應(yīng)使原先假定為沖突的時(shí)隙變?yōu)槌晒r(shí)隙，因此識(shí)別效率得到了提高；第二，被捕獲效應(yīng)隱藏的標(biāo)簽[18]會(huì)與其他未識(shí)別標(biāo)簽沖突。圖1分別給出了捕獲效應(yīng)下RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議中2種幀長設(shè)置方式的識(shí)別效率隨捕獲效應(yīng)概率值的變化曲線。方式1為傳統(tǒng)方式，即幀長等于標(biāo)簽數(shù)，該方式已經(jīng)被證明在無捕獲效應(yīng)條件下能夠使標(biāo)簽識(shí)別效率達(dá)到最優(yōu)[6～10]；方式2的幀長設(shè)置是關(guān)于標(biāo)簽數(shù)和捕獲效應(yīng)概率的函數(shù)，該方式在5.4節(jié)中被證明是捕獲效應(yīng)下的最優(yōu)幀長。

從圖1得知，當(dāng)系統(tǒng)存在捕獲效應(yīng)時(shí)，方式1所得到的識(shí)別效率低于方式 2。為使識(shí)別效率得到提高，需采用方式 2幀長設(shè)置方式，而這種方式不僅需要標(biāo)簽數(shù)的信息還需要捕獲效應(yīng)發(fā)生概率的信息，因此必須要對(duì)標(biāo)簽數(shù)和捕獲效應(yīng)概率進(jìn)行估計(jì)。

圖1 捕獲效應(yīng)下的系統(tǒng)識(shí)別效率

4 系統(tǒng)描述

在RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議中，標(biāo)簽的識(shí)別過程被分為若干幀，每幀又被分為若干時(shí)隙。標(biāo)簽在每個(gè)幀中只能隨機(jī)選擇一個(gè)時(shí)隙向閱讀器發(fā)送信息。對(duì)于一個(gè)給定的時(shí)隙只能產(chǎn)生3種情況：沒有標(biāo)簽、有一個(gè)標(biāo)簽或有2個(gè)以上的標(biāo)簽發(fā)射信號(hào)。若沒發(fā)生捕獲效應(yīng)，這3種情況分別對(duì)應(yīng)于空、可讀和沖突時(shí)隙；若發(fā)生捕獲效應(yīng)，那么即使有 2個(gè)標(biāo)簽發(fā)送信息，也可產(chǎn)生可讀時(shí)隙。在該協(xié)議中，當(dāng)前幀中發(fā)生沖突的標(biāo)簽和被隱藏的標(biāo)簽將進(jìn)入下一幀中繼續(xù)被識(shí)別，當(dāng)所有標(biāo)簽均被閱讀器識(shí)別，整個(gè)識(shí)別結(jié)束。RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議中每個(gè)幀的長度動(dòng)態(tài)變化，該值與待識(shí)別的標(biāo)簽數(shù)和捕獲效應(yīng)概率保持一定比例以保證較高的識(shí)別效率。給出定義如下。

定義1 l表示RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議的第i個(gè)閱讀幀長，可定義為

其中，c0、c1和ck分別表示第i幀中的空時(shí)隙數(shù)、成功時(shí)隙數(shù)和沖突時(shí)隙數(shù)的觀測值，那么閱讀器成功閱讀所有標(biāo)簽所需要的總時(shí)隙數(shù)定義為

其中，m為成功閱讀所有標(biāo)簽所需要的幀個(gè)數(shù)。

定義2 第i幀中發(fā)生捕獲效應(yīng)的概率p定義為

其中，s表示第i幀中發(fā)生捕獲效應(yīng)的時(shí)隙數(shù)的期望值，ak′為第i幀中有2個(gè)或2個(gè)以上的標(biāo)簽選擇同一個(gè)時(shí)隙個(gè)數(shù)的期望值。

定義3 第i幀中閱讀器識(shí)別效率P定義為

其中，t0、t1和tk分別表示第i幀中空時(shí)隙、成功時(shí)隙和沖突時(shí)隙所占用的時(shí)間。

5 捕獲效應(yīng)下的CATPE 協(xié)議

5.1 低復(fù)雜度標(biāo)簽數(shù)和捕獲效應(yīng)概率估計(jì)

由于標(biāo)簽選擇時(shí)隙相互獨(dú)立，且標(biāo)簽每次選擇某個(gè)時(shí)隙結(jié)果只有2種情況，即選擇或不選擇，則標(biāo)簽選擇時(shí)隙是一個(gè)二次項(xiàng)伯努利試驗(yàn)。因此，當(dāng)系統(tǒng)存在n個(gè)標(biāo)簽，第i幀長為l時(shí)，有r個(gè)標(biāo)簽同時(shí)選擇一個(gè)時(shí)隙的概率為[6～11]

那么，被r個(gè)標(biāo)簽同時(shí)選中的時(shí)隙數(shù)的期望值為

在RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議中，若第i個(gè)幀中發(fā)生捕獲效應(yīng)的概率為p，那么在該幀中空時(shí)隙數(shù)、成功時(shí)隙數(shù)和沖突時(shí)隙數(shù)的期望值分別為

把 a0=c0代入式(8)中，那么該幀中標(biāo)簽數(shù)可估計(jì)為

同時(shí)，由式(6)、式(7)可得

5.2 bit-slot分組及幀長調(diào)整系數(shù)

在RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議中，用式(9)估計(jì)標(biāo)簽數(shù)需滿足c0≠0。然而當(dāng)初始時(shí)刻的待識(shí)別標(biāo)簽數(shù)n0＞＞l0時(shí)，c0將趨近于 0。此時(shí)為保證c0≠0可重新調(diào)整幀長，使其增大M倍，即

其中，M可選大于2的整數(shù)。當(dāng)然如果多次調(diào)整幀長才產(chǎn)生空時(shí)隙數(shù)，會(huì)產(chǎn)生過多的沖突時(shí)隙，從而增加識(shí)別時(shí)間。因此，可采用 bit-slot方法[25]來檢測是否調(diào)整后的幀中產(chǎn)生了空時(shí)隙，如圖2所示。閱讀器在設(shè)置初始幀長時(shí)可先發(fā)送帶有參數(shù)l0的命令給標(biāo)簽，標(biāo)簽接收到命令后在l0個(gè)時(shí)隙中隨機(jī)選擇一個(gè)時(shí)隙發(fā)送1個(gè)bit的信息。如果某個(gè)時(shí)隙中沒有檢測到bit，則該時(shí)隙為空時(shí)隙，那么幀長調(diào)整結(jié)束。在此方法中，由于標(biāo)簽只發(fā)送1個(gè)bit，而不是其ID信息，因此可減少調(diào)整幀長的時(shí)間。

圖2 bit-slot協(xié)議

下面將確定幀長調(diào)整系數(shù)M的取值。首先，把一小概率事件的概率閾值表示為Δ(0＜Δ≤1)，那么，當(dāng)空時(shí)隙概率小于或等于Δ時(shí)，一個(gè)幀中空時(shí)隙數(shù)接近于 0。假定系統(tǒng)中標(biāo)簽數(shù)與幀長為線性關(guān)系，即li=kni，則由式（7）可得

因此，若要使得空時(shí)隙數(shù)不為零，則應(yīng)使

5.3 估計(jì)復(fù)雜度分析

一些用來估計(jì)標(biāo)簽數(shù)的傳統(tǒng)估計(jì)方法，如VOGT估計(jì)[5]需搜索來找到極值，CMEBE[24]則需要進(jìn)行二維搜索來時(shí)估計(jì)標(biāo)簽數(shù)和捕獲效應(yīng)概率值。在文獻(xiàn)[4]中所提出的CMEBE方法通過下式估計(jì)標(biāo)簽數(shù)和捕獲效應(yīng)概率

VOGT估計(jì)僅對(duì)標(biāo)簽數(shù)進(jìn)行估計(jì)，所以窮盡搜索次數(shù)為v。相反，本文 CATPE 協(xié)議的估計(jì)算法不需要進(jìn)行搜索，它只需通過式(13)一步計(jì)算即可得到標(biāo)簽數(shù)，捕獲效應(yīng)概率值估計(jì)也不需要通過搜索算法，僅通過式(15)的求偽逆即可得到。表 1中給出了VOGT、CMEBE以及CATPE 3種方法的搜索次數(shù)比較。

表1 VOGT、CMEBE以及CATPE 算法的搜索次數(shù)

5.4 最優(yōu)幀長設(shè)置

5.4.1 等時(shí)隙時(shí)長的最優(yōu)幀長

等時(shí)隙時(shí)長下，由于t0=t1=tk，根據(jù)定義3可得第i幀識(shí)別效率為

為了獲得最優(yōu)幀長，將式(7)代入式(17)，對(duì)l求導(dǎo)，并使式(17)等于零，可得最優(yōu)幀長為

5.4.2 非等時(shí)隙時(shí)長的最優(yōu)幀長

在實(shí)際的RFID系統(tǒng)中空、成功和沖突時(shí)隙所占用的時(shí)間不一定相等，例如在EPC C1 Gen2標(biāo)準(zhǔn)[21]中，這些時(shí)隙所占用的時(shí)間就不一樣，空時(shí)隙數(shù)的時(shí)間最短，其次是沖突時(shí)隙，而成功時(shí)隙所用時(shí)間最長[8]。下面將推導(dǎo)非等時(shí)隙時(shí)長的最優(yōu)幀長。

首先，考慮一種線性模型，第i幀長l與標(biāo)簽數(shù)n具有線性關(guān)系l=rn，那么

將式(19)、式(20)代入定義3，并令α=t0t1，β=tk/t1，有

若

其中，R為r的取值集合，那么最優(yōu)幀長為

5.5 協(xié)議描述

初始時(shí)，閱讀器設(shè)置初始幀長為l0，標(biāo)簽在該幀中選擇時(shí)隙，閱讀器通過bit-slot方法檢測是否存在空時(shí)隙，若空時(shí)隙為0，則重新設(shè)置初始幀長；否則，閱讀器將記錄標(biāo)簽選擇的空、成功和沖突時(shí)隙數(shù)，以此估計(jì)標(biāo)簽數(shù)和捕獲效應(yīng)概率。得到標(biāo)簽數(shù)和概率值估計(jì)值后，將以估計(jì)的結(jié)果來設(shè)置下一個(gè)幀的最優(yōu)幀長。由于第i幀的標(biāo)簽數(shù)

且假定該幀的捕獲效應(yīng)概率pi+1是關(guān)于pi的函數(shù)，即

通常，函數(shù)f(·)并不能輕易獲得，該函數(shù)不僅與選取的幀長相關(guān)，而且與標(biāo)簽的實(shí)際識(shí)別環(huán)境相關(guān)，例如標(biāo)簽與閱讀器距離的遠(yuǎn)近，標(biāo)簽散射信號(hào)的強(qiáng)弱[5,18]。為便于驗(yàn)證最優(yōu)幀長的選取，采用文獻(xiàn)[19,24]實(shí)驗(yàn)中所采用的捕獲效應(yīng)模型，pi+1=f(pi)=pi，即捕獲效應(yīng)的概率是一個(gè)恒值。

將式(24)和式(25)代入式(18)，等時(shí)隙時(shí)長第i+1幀的最優(yōu)幀長可設(shè)置為

同理，將式(24)和式(25)代入式(23)～式(25)，非等時(shí)隙時(shí)長第i+1幀的最優(yōu)幀長可設(shè)置為

圖3給出了閱讀器端CATPE 協(xié)議的流程。初始時(shí)，閱讀器通過觀測值c0調(diào)整幀長，采用bit-slot方法來統(tǒng)計(jì)空時(shí)隙數(shù)。如果空時(shí)隙數(shù)為0，則通過式(13)重新設(shè)置初始幀長。然后，閱讀器將執(zhí)行動(dòng)態(tài)幀Aloha算法。首先，統(tǒng)計(jì)當(dāng)前幀中空、成功和沖突時(shí)隙數(shù)；然后據(jù)此通過式(9)和式(12)來估計(jì)標(biāo)簽數(shù)和捕獲效應(yīng)概率；判斷（c1!=0或ck!=0）是否為真，如果為真則通過式(26)或式(27)設(shè)置最優(yōu)幀長，并繼續(xù)閱讀標(biāo)簽直到（c1!=0或ck!=0）為假。

圖3 閱讀器端CATPE協(xié)議流程

6 計(jì)算機(jī)仿真結(jié)果

6.1 仿真系統(tǒng)設(shè)置

本部分通過計(jì)算機(jī)仿真的實(shí)驗(yàn)結(jié)果驗(yàn)證本文提出的 CATPE協(xié)議，在仿真實(shí)驗(yàn)中，采用一個(gè)閱讀器識(shí)別多個(gè)標(biāo)簽的情況，并且假定在識(shí)別過程中標(biāo)簽不會(huì)離開閱讀器的磁場范圍，也不會(huì)有新的標(biāo)簽進(jìn)入閱讀器磁場。使用以下指標(biāo)來評(píng)價(jià)標(biāo)簽識(shí)別的性能。

1)估計(jì)誤差：觀測在一個(gè)幀內(nèi)估計(jì)的標(biāo)簽數(shù)及捕獲效應(yīng)發(fā)生概率的估計(jì)相對(duì)誤差，定義為

2)搜索次數(shù)：觀測在一個(gè)幀內(nèi)估計(jì)標(biāo)簽數(shù)和捕獲效應(yīng)概率值所需要的搜索次數(shù)，較少的搜索次數(shù)將具有較低的計(jì)算復(fù)雜度。

3)總識(shí)別效率：該效率定義為在m幀內(nèi)識(shí)別完所有標(biāo)簽的識(shí)別效率，表示為

較少的空時(shí)隙和沖突時(shí)隙將得到較高的總識(shí)別效率。

4)標(biāo)簽平均識(shí)別時(shí)間：觀測在一個(gè)幀內(nèi)識(shí)別每個(gè)標(biāo)簽所花費(fèi)的時(shí)間，定義為

較少的平均識(shí)別時(shí)間所得到總的識(shí)別時(shí)間也較少。

在仿真中，對(duì)每個(gè)實(shí)驗(yàn)重復(fù)執(zhí)行500次，最后的實(shí)驗(yàn)結(jié)果為500次結(jié)果的平均值。把本文提出的CATPE 協(xié)議與現(xiàn)有的Optimal Q、GBT和CMEBE協(xié)議進(jìn)行對(duì)比，這些協(xié)議的參數(shù)如下。

1)Optimal Q：Q0取4.0，同時(shí)根據(jù)文獻(xiàn)[19]，假定第n個(gè)幀長的標(biāo)簽數(shù)Tn已知，那么第n個(gè)幀長的Qn為。

2)GBT協(xié)議：初始時(shí)，所有標(biāo)簽的計(jì)數(shù)器均為0。被捕獲效應(yīng)隱藏的標(biāo)簽將進(jìn)入下一個(gè)二進(jìn)制樹循環(huán)[18]，其中，一個(gè)二進(jìn)制樹循環(huán)定義為在這個(gè)循環(huán)中所有沖突時(shí)隙均被分解為可讀時(shí)隙或空時(shí)隙。

3)CMEBE協(xié)議：標(biāo)簽值及捕獲效應(yīng)概率值搜索范圍分別設(shè)置為Ni={c1i+2cki≤n≤Nmax|n∈Z}，其中Nmax=500，P={0,0.1,…,1.0}。

4)Bayes方法：采用非等長時(shí)隙參數(shù)，即t0≠t1≠tk。

本部分的仿真結(jié)果將分為以下幾部分：第一部分給出CATPE 協(xié)議與現(xiàn)有協(xié)議在估計(jì)誤差的對(duì)比結(jié)果，第二部分給出 CATPE 與現(xiàn)有協(xié)議在估計(jì)復(fù)雜度的對(duì)比結(jié)果，最后一部分給出協(xié)議的總識(shí)別效率。本仿真系統(tǒng)所涉及到的其他參數(shù)如下。

1)待識(shí)別標(biāo)簽數(shù)：n0=300。

2)初始幀長：l0=128。

3)時(shí)隙時(shí)長：等時(shí)隙時(shí)長時(shí)，t0=t1=tk；非等時(shí)隙時(shí)長時(shí)，t0=50μs，t1=400μs，tk=200μs[8]。

4)捕獲效應(yīng)概率模型：采用文獻(xiàn)[19,24]中的模型，即pi=p。

5)幀長調(diào)整系數(shù)：設(shè)置小概率事件閾值Δ=2×10-2，則取M=4。

6.2 估計(jì)誤差

給出CATPE 和CMEBE對(duì)標(biāo)簽數(shù)以及捕獲效應(yīng)概率的估計(jì)相對(duì)誤差隨捕獲效應(yīng)概率值pi的變化曲線。圖4給出了在第一幀中的估計(jì)結(jié)果，從圖4可以看到，4條曲線的估計(jì)誤差基本都在0～3%之間，這一結(jié)果表明，CATPE 和 CMEBE的估計(jì)誤差很接近。

6.3 計(jì)算復(fù)雜度

給出 CATPE 及 CMEBE的搜索次數(shù)，以搜索次數(shù)來評(píng)價(jià)估計(jì)的計(jì)算復(fù)雜度。圖5給出了在不同標(biāo)簽數(shù)條件下，第一幀中搜索次數(shù)隨捕獲效應(yīng)概率值變化的曲線。從圖5可以看出，CMEBE算法的搜索次數(shù)遠(yuǎn)大于 CATPE 算法的，其原因在于，CATPE 算法無需進(jìn)行搜索，其搜索次數(shù)始終為1。

圖4 估計(jì)誤差

圖5 CATPE 和CMEBE搜索次數(shù)

6.4 系統(tǒng)總識(shí)別效率和識(shí)別時(shí)間

本節(jié)首先給出等時(shí)隙時(shí)長下的總的識(shí)別效率比較結(jié)果。圖6給出了Optimal Q、GBT、CATPE 和CMEBE 4種協(xié)議在捕獲效應(yīng)概率從0變化到1.0的識(shí)別效率曲線。從圖中可以看到，CATPE 的識(shí)別效率優(yōu)于GBT和Optimal Q算法，其曲線與CMEBE的曲線基本重合。

下面再給出非等時(shí)隙時(shí)長的仿真結(jié)果。由于t0=50μs， t1=400μs，tk=200μs，相應(yīng)地，α=0.125，β=0.2。由Bayes方法[8]可知，當(dāng)不存在捕獲效應(yīng)時(shí)，最優(yōu)幀長r*=1.7，因此給出本文的最優(yōu)幀長與Bayes和CMEBE的對(duì)比結(jié)果。圖7給出了第二幀中的標(biāo)簽平均識(shí)別時(shí)間隨捕獲效應(yīng)概率變化的曲線圖，其中之所以沒有給出初始幀結(jié)果的原因是，初始幀中l(wèi)0=128，n0=300，它并不滿足最優(yōu)幀長設(shè)置的條件。從圖 7中可以看到，當(dāng) r*設(shè)置為1.7或按照 l=p+(1-p)n時(shí)，即Bayes和CMEBE的方法，其識(shí)別時(shí)間均比設(shè)置最優(yōu)幀長的識(shí)別時(shí)間更長。表2還給出了在 α=0.125，β=0.2的情況下的系統(tǒng)識(shí)別效率P以及最優(yōu)幀長線性系數(shù) r*的值。

圖6 系統(tǒng)識(shí)別效率

圖7 標(biāo)簽平均識(shí)別時(shí)間

表2 α=0.125,β=0.5條件下 r*與 P

7 結(jié)束語

本文針對(duì)RFID動(dòng)態(tài)幀時(shí)隙ALOHA協(xié)議，提出了一種在捕獲效應(yīng)下的RFID標(biāo)簽防沖突協(xié)議，實(shí)驗(yàn)仿真結(jié)果說明，該協(xié)議系統(tǒng)識(shí)別效率要高于現(xiàn)有的GBT和Optimal Q協(xié)議算法，與CMEBE協(xié)議相接近，但其計(jì)算復(fù)雜度卻低于 CMEBE。另外，本文還推導(dǎo)出了在非等時(shí)隙時(shí)長下的線性最優(yōu)幀長設(shè)置，仿真結(jié)果顯示，在滿足該最優(yōu)幀長條件下，標(biāo)簽的平均識(shí)別時(shí)間要少于傳統(tǒng)的 Bayes和CMEBE方法。

[1]WELBOURNE E,BATTLE L,COLE G. Building the Internet of things using RFID: the RFID ecosystem experience[J]. IEEE Internet Computing,2009,13(3):48-55.

[2]FINKENZELLER K. RFID Handbook: Radio-frequency Identification Fundamentals and Applications[M]. England: John Wiley and Sons,2003.

[3]SHIN D H,SUN P L,YEN D C. Taxonomy and survey of RFID anti-collision protocols[J]. Computer Communications,2006,29(11):2150-2166.

[4]SCHOUTE F C. Dynamic frame length aloha[J]. IEEE Transaction on Communication,1983,31(4):565-568.

[5]VOGT H. Efficient object identification with passive RFID tags[A].Proceedings of International Conference on Pervasive Computing[C].Zurich,Switzerland,2002. 98-113.

[6]LEE S R,JOO S D,LEE C W. An enhanced dynamic framed ALOHA algorithm for RFID tag identification[A]. Proceedings International Conference Mobile and Ubiquitous Systems[C]. San Diego,USA,2005. 1-5.

[7]CHEN W T. An accurate tag estimate method for improving the performance of an RFID anticollision algorithm based on dynamic frame length ALOHA[J]. IEEE Transactions on Automation Science and Engineering,2008,6(1):9-15.

[8]吳海鋒,曾玉. 自適應(yīng)幀ALOHA的RFID標(biāo)簽防沖突協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展,2011,48(5): 802-811.WU H F,ZENG Y. ADFA protocol for RFID tag collision arbitration[J]. Journal of Computer Research and Development,2011,48(5):802-811.

[9]BONUCCELLI M A,LONETTI F,MARTELLI F. Tree slotted ALOHA: a new protocol for tag identification in RFID networks[A].Proceedings of International Symposium on a World of Wireless[C].NY,USA,2006. 1-6.

[10]WU H F,ZENG Y,Efficient framed slotted aloha protocol RFID tag anti-collision[J]. IEEE Transactions on Automation Science and Engineering,2011,8(3):581-588.

[11]CAPETANAKIS J I. Tree algorithms for packet broadcast channels[J].IEEE Trans Information Theory,1979,25(5):505-515.

[12]HUSH D R,WOOD C. Analysis of tree algorithm for RFID arbitra-tion[A]. Proc IEEE International Symposium on Information Theory[C]. Cambridge,UK,1998. 107-117.

[13]馮波,李錦濤,鄭為民. 一種新的 RFID 標(biāo)簽識(shí)別防沖突算法[J].自動(dòng)化學(xué)報(bào),2008,34(6):632-638.FENG B,LI J T,ZHENG W M. A novel anti-collision algorithm for tag identification in RFID systems [J]. Acta Automatica Sinica,2008,34(6):632-638.

[14]MYUNG J,LEE W J,SRIVASTAVA. Tag-splitting: adaptive collision arbitration protocols for RFID tag identification[J]. IEEE Trans Parallel and Distributed Systems,2007,18(6):763-775.

[15]QIAN C,NGAN H,LIU Y. Cardinality estimation for large-scale RFID systems[J]. IEEE Trans Parallel and Distributed Systems,2011,22(9):1441-1454.

[16]WU H F,ZENG Y,FENG J. Binary tree slotted ALOHA for passive RFID tag anti-collision[J]. IEEE Trans Parallel and Distributed Systems,2012,99:1-14.

[17]ORTA L T,MASELLI G,PETRIOLI C. Anti-collision protocols for single-reader RFID systems: temporal analysis and optimization[J].IEEE Trans on Mobile Computing,2011,10(2):267-279.

[18]LAI Y,HSIAO L. General binary tree protocol for coping with the capture effect in RFID tag identification[J]. IEEE Comm,Letters,2010,14(3):208-210.

[19]MAGUIRE Y,PAPPU R. An optimal Q-algorithm for the ISO 18000-6C RFID protocol[J]. IEEE Trans Automation Science and Engineering,2009,6(1):16-24.

[20]ISO/IEC 18000-6. Information technology—radio frequency identification(RFID)for item management—Part 6: Parameters for air interface communications at 860MHz to 960MHz,Amendment1: extension with type C and update of types A and B[S].

[21]EPC radio-frequency identification protocols class-1 generation-2 UHF RFID protocol for communications at 860MHz-960MHz Version 1.1.0 Draft1[S]. EPCglobal Inc,2005.

[22]KHANDELWAL G,YENER A,LEE K. ASAP : A MAC protocol for dense and time constrained RFID systems[A]. Proc of IEEE International Conference on Communications[C]. Istanbul,Turkey,2006.4028-4033.

[23]ISO/IEC 18000-6. Information technology—radio frequency identification(RFID)for item management—Part 6: Parameters for air interface communications at 860 MHz to 960 MHz[S].

[24]LI B,WANG J Y. Efficient anti-collision algorithm utilizing the capture effect for ISO18000-6C RFID protocol[J]. IEEE Commun Lett,2011,15(3):352-354.

[25]WONG C P,FENG Q. Grouping based bit-slot ALOHA protocol for tag anti-collision in RFID systems[J]. IEEE Commun Lett,2007,11(12):946-948.