基于并行匹配的RFID自適應(yīng)碰撞樹(shù)算法

賀曉霞，賈小林

(西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽(yáng) 621000)

0 引 言

射頻識(shí)別(radio frequency identification，RFID)技術(shù)是實(shí)現(xiàn)物聯(lián)網(wǎng)(IoT)對(duì)象感知的關(guān)鍵。在RFID系統(tǒng)中當(dāng)多個(gè)標(biāo)簽試圖同時(shí)響應(yīng)閱讀器的詢問(wèn)時(shí)，就會(huì)發(fā)生標(biāo)簽碰撞，即閱讀器無(wú)法識(shí)別任何標(biāo)簽[1]。這種碰撞不僅延長(zhǎng)了標(biāo)簽識(shí)別的時(shí)間，而且增加了閱讀器的能耗。因此有效地解決標(biāo)簽碰撞的防碰撞算法對(duì)于大規(guī)模物聯(lián)網(wǎng)RFID系統(tǒng)的開(kāi)發(fā)具有重要意義。標(biāo)簽防碰撞算法主要可以分為3大類：基于ALOHA的算法[2]、基于樹(shù)的算法[3]和混合算法[4]。基于ALOHA的算法在標(biāo)簽數(shù)量相對(duì)較少的情況下表現(xiàn)較好的性能，但是隨機(jī)機(jī)制又會(huì)導(dǎo)致“標(biāo)簽饑餓”[5]?；跇?shù)的算法的優(yōu)點(diǎn)是即使在標(biāo)簽密集的RFID系統(tǒng)中也能成功識(shí)別出所有的標(biāo)簽。

基于Manchester code的位跟蹤技術(shù)在基于樹(shù)的算法中得到了廣泛的應(yīng)用，如碰撞樹(shù)算法(CT)[6]、雙時(shí)隙碰撞跟蹤樹(shù)算法(BSCTTA)[7]、雙前綴探針?biāo)惴?DPPS)[8]等。BSCTTA的設(shè)計(jì)使得前綴開(kāi)銷和迭代開(kāi)銷可以通過(guò)時(shí)間分割響應(yīng)[7]來(lái)減少，但標(biāo)簽數(shù)量非常大時(shí)，該算法性能會(huì)降低，因?yàn)樗粫?huì)在發(fā)生碰撞時(shí)分成兩個(gè)子組來(lái)避免標(biāo)簽沖突[9]。自適應(yīng)碰撞樹(shù)算法(ACT)[10]是一種基于碰撞樹(shù)算法(CT)和改進(jìn)的碰撞樹(shù)算法(ICT)[11]的防碰撞算法。ACT在一定程度上縮短了標(biāo)簽識(shí)別時(shí)間，提高了系統(tǒng)性能，但在使用四叉樹(shù)搜索時(shí)，它增加了空閑周期的數(shù)量，對(duì)系統(tǒng)性能產(chǎn)生了影響。類似，AdATSA[12]和OBTT[13]在識(shí)別過(guò)程中仍然存在空閑時(shí)隙，不可避免地也降低了系統(tǒng)性能。

基于上述問(wèn)題，本文提出了一種基于并行匹配方案的自適應(yīng)碰撞樹(shù)(PACT)算法，通過(guò)引入并行匹配機(jī)制來(lái)減少空閑的查詢周期，同時(shí)利用碰撞標(biāo)簽的數(shù)量自適應(yīng)地選擇搜索模式(2-branchCT還是8-branchCT)，大大降低搜索深度，減少碰撞周期和延遲。

1 PACT算法

(1)并行匹配與系統(tǒng)傳輸模型

在查詢樹(shù)算法(QT)中，當(dāng)閱讀器在識(shí)別過(guò)程中檢測(cè)到了碰撞時(shí)，通過(guò)將0和1附加到之前的前綴生成一個(gè)新的前綴并入棧，然后逐個(gè)發(fā)送兩個(gè)查詢。具有與前綴匹配的ID的標(biāo)簽將響應(yīng)除了其ID的匹配部分之外的完整部分。在本文中，將這種查詢類型稱為串行匹配查詢，指定為SMQ(sequential matching query)。與之相比，本文提出的算法只需要發(fā)送一個(gè)查詢，但是并行執(zhí)行標(biāo)簽匹配。這種沖突仲裁稱為并行匹配方案，使用的查詢稱為并行匹配查詢，簡(jiǎn)稱PMQ(parallel matching query)。具體來(lái)講，由于標(biāo)簽ID的二元確定性原則[11]，與前綴匹配的標(biāo)簽肯定會(huì)在兩個(gè)時(shí)隙中的一個(gè)中響應(yīng)。在識(shí)別過(guò)程中，與前綴匹配的標(biāo)簽將在兩個(gè)連續(xù)時(shí)隙之一中發(fā)送它們的ID，標(biāo)簽通過(guò)其ID的第(L+1)位的值是0還是1來(lái)確定應(yīng)響應(yīng)的時(shí)隙數(shù)量，其中L是所接收的前綴的長(zhǎng)度。在第一個(gè)時(shí)隙中分配的標(biāo)簽先發(fā)送其ID，然后在第二個(gè)時(shí)隙中分配的標(biāo)簽將在第一個(gè)時(shí)隙上的傳輸完成后再發(fā)送其ID。使用這種機(jī)制不僅有效地減少了查詢周期的數(shù)量，而且減少了閱讀器發(fā)送的查詢前綴的長(zhǎng)度。如圖1所示，是傳統(tǒng)基于樹(shù)的算法和并行匹配方案的鏈路時(shí)序。閱讀器在時(shí)間TR中發(fā)送CW信號(hào)和查詢命令。標(biāo)簽從射頻信號(hào)中獲取工作能量并傳輸信息。在接收到閱讀器的命令之后，標(biāo)簽在時(shí)間T1中生成它們的響應(yīng)。

圖1 基于傳統(tǒng)的樹(shù)算法和并行匹配方案的鏈路時(shí)序

根據(jù)上述傳輸模型，時(shí)間模型描述如式(1)所示。在詢問(wèn)區(qū)中識(shí)別n個(gè)標(biāo)簽所花費(fèi)的總時(shí)間為每個(gè)循環(huán)中閱讀器發(fā)送查詢的時(shí)間加上標(biāo)簽響應(yīng)所需的時(shí)間。令CPMQ和CSMQ分別表示PMQ和SMQ的個(gè)數(shù)。識(shí)別時(shí)間可以表示為下式：其中TRi和Ttagi分別表示在第i個(gè)周期中閱讀器傳輸查詢和標(biāo)簽響應(yīng)所花費(fèi)的時(shí)間

(1)

(2)自適應(yīng)分割機(jī)制

所提出的算法采用自適應(yīng)分割機(jī)制來(lái)根據(jù)碰撞條件決定CT的選擇為8分支碰撞樹(shù)或2分支碰撞樹(shù)。假設(shè)在系統(tǒng)中有N個(gè)標(biāo)簽待識(shí)別，分布的子分支的數(shù)量是L，搜索深度是k。則識(shí)別概率可以計(jì)算為

p(k)=p(1)*(1-p(1))k-1

(2)

p(1)=(1-1/L)N-1

(3)

然后我們可以得到搜索深度的數(shù)學(xué)期望，即

(4)

因此，標(biāo)簽識(shí)別所需的平均時(shí)隙數(shù)是

(5)

對(duì)于式(5)中的L進(jìn)行部分推導(dǎo)，可以得到

(6)

從式(6)可以觀察到，當(dāng)分布的子分支的數(shù)量L等于標(biāo)簽的數(shù)量N時(shí)，系統(tǒng)所需的時(shí)隙數(shù)最少。因此，當(dāng)標(biāo)簽數(shù)量很多時(shí)，為了減少識(shí)別所需的時(shí)隙，可以分配更多子分支。

根據(jù)式(5)，將L=2代入到式中，則2-branch樹(shù)中識(shí)別過(guò)程所需的平均時(shí)隙數(shù)可以表示為

T2branch=2/(1-1/2)N-1=2N

(7)

在8-branch樹(shù)中，所需的平均時(shí)隙數(shù)為

T8branch=8/(1-1/8)N-1=8N/7N-1

(8)

通過(guò)等式(7)和式(8)可以看到，當(dāng)N≥4時(shí)，T8branchT2branch。 總而言之，當(dāng)識(shí)別范圍內(nèi)存在的標(biāo)簽數(shù)量大于等于4時(shí)，使用8分支碰撞樹(shù)更有效。當(dāng)標(biāo)簽數(shù)量小于4時(shí)，2-branch CT比8-branch CT具有更好的性能。因此，當(dāng)N≥4時(shí)，PACT算法選擇使用8-branch CT，在N<4時(shí)使用2-branch CT。

(3)識(shí)別過(guò)程

PACT算法使用兩種類型的查詢，SMQ和PMQ，初始化查詢類型為PMQ，前綴為‘ε’。標(biāo)簽響應(yīng)的長(zhǎng)度由查詢類型決定，其中k為標(biāo)簽ID的長(zhǎng)度，L為接收前綴的長(zhǎng)度，如式(9)

(9)

PACT算法描述如下：具體來(lái)說(shuō)，Prefix是前綴堆棧。M和N分別是碰撞比特的數(shù)量和碰撞標(biāo)簽的數(shù)量。Request(ε)要求所有在閱讀器查詢范圍內(nèi)的標(biāo)簽響應(yīng)。Request(prefix)要求標(biāo)簽將自己的ID與閱讀器發(fā)送的前綴進(jìn)行比較，如果滿足查詢條件(假設(shè)前綴和標(biāo)簽ID的長(zhǎng)度分別為L(zhǎng)和k)，則將剩余的(k-L)位返回給閱讀器。PACT算法詳細(xì)過(guò)程的偽代碼見(jiàn)表1。

表1 PACT算法詳細(xì)描述

2 性能分析

在本節(jié)中，通過(guò)理論分析，從時(shí)間復(fù)雜度和系統(tǒng)效率兩個(gè)方面對(duì)PACT的性能進(jìn)行了評(píng)估，通過(guò)測(cè)量所需的時(shí)隙來(lái)評(píng)估系統(tǒng)的時(shí)間復(fù)雜度。

設(shè)n是讀取器天線范圍內(nèi)的標(biāo)簽數(shù)量，d是標(biāo)簽ID的長(zhǎng)度。C8branch(n) 表示在8-branch樹(shù)搜索中產(chǎn)生的碰撞時(shí)隙的數(shù)量，C2branch(n) 表示在2-branch樹(shù)搜索中產(chǎn)生的碰撞時(shí)隙的數(shù)量?？紤]到自動(dòng)識(shí)別的思想，當(dāng)一個(gè)比特發(fā)生N1次碰撞時(shí)，系統(tǒng)可以減少2N1時(shí)隙。

因此，總時(shí)隙數(shù)可以計(jì)算為

T(n)=C8branch(n)+C2branch(n)+n-2N1

(10)

在文獻(xiàn)[14]中，給出了完全二進(jìn)制樹(shù)中碰撞時(shí)隙數(shù)的理論期望

(11)

其中，L為樹(shù)的搜索深度，B為樹(shù)的維數(shù)。因此，當(dāng)L=k+1時(shí)，8分支樹(shù)搜索的碰撞時(shí)隙為

(12)

根據(jù)文獻(xiàn)[4]，2分支樹(shù)搜索中的碰撞時(shí)隙數(shù)與B分支樹(shù)搜索中的碰撞時(shí)隙數(shù)之比約為1/log2B。 由于2-branch CT中的碰撞節(jié)點(diǎn)數(shù)是(n-1)[11]，完全8-branch CT中的碰撞節(jié)點(diǎn)數(shù)應(yīng)該是 (n-1)/3， 假設(shè)要識(shí)別的系統(tǒng)中有n個(gè)標(biāo)簽?？梢缘玫皆赑ACT中8-branch樹(shù)搜索中產(chǎn)生的碰撞周期的數(shù)量為

(13)

綜上所述，當(dāng)搜索深度等于k+1時(shí)，每個(gè)2-branch CT中剩余的碰撞時(shí)隙中只有兩個(gè)或3個(gè)標(biāo)簽1

(14)

因此，PACT中所需的總時(shí)隙數(shù)可以計(jì)算為

(15)

系統(tǒng)效率定義為標(biāo)簽數(shù)量與在系統(tǒng)中識(shí)別它們所需的總時(shí)隙數(shù)量之比。因此，我們可以獲得系統(tǒng)效率為

(16)

3 仿真結(jié)果

本文利用MATLAB仿真平臺(tái)，選擇理想信道，將本文提出的PACT算法與自適應(yīng)碰撞樹(shù)算法(ACT)、改進(jìn)的碰撞樹(shù)算法(ICT)以及最優(yōu)的跟蹤樹(shù)算法(OBTT)分別在所需時(shí)隙的數(shù)量、碰撞時(shí)隙的數(shù)量以及系統(tǒng)效率方面進(jìn)行分析比較。假設(shè)系統(tǒng)內(nèi)標(biāo)簽均勻分布，遵循ISO18000-6標(biāo)準(zhǔn)，隨機(jī)生成編號(hào)長(zhǎng)度為96位的電子標(biāo)簽，標(biāo)簽數(shù)量從100增加到2000。

圖2顯示了標(biāo)簽數(shù)量與識(shí)別過(guò)程中所需的總時(shí)隙數(shù)之間的關(guān)系。可以看出，在相同數(shù)量的標(biāo)簽下，本文提出的PACT算法所需的時(shí)隙數(shù)小于其它3種算法(ACT，ICT和OBTT)所需的時(shí)隙數(shù)。

圖2 總時(shí)隙數(shù)與標(biāo)簽數(shù)關(guān)系

圖3描繪了碰撞時(shí)隙數(shù)與標(biāo)簽的關(guān)系圖。當(dāng)標(biāo)簽的數(shù)量小于200時(shí)，OBTT和PACT生成的碰撞時(shí)隙的數(shù)量是相似的，但是隨著標(biāo)簽數(shù)量增加，PACT生成的碰撞時(shí)隙的數(shù)量明顯低于其它3種算法。主要是因?yàn)樵赑ACT中使用了并行匹配方案使得8分支樹(shù)搜索階段減少了大量的碰撞時(shí)隙。

圖3 碰撞時(shí)隙數(shù)與標(biāo)簽數(shù)關(guān)系

圖4為4種算法的系統(tǒng)效率對(duì)比。很明顯，PACT的系統(tǒng)效率約為0.609，高于其它3種算法。ICT，ACT和OBTT的平均系統(tǒng)效率分別為0.521,0.559和0.601。

圖4 系統(tǒng)效率與標(biāo)簽數(shù)關(guān)系

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

本文提出一種基于并行匹配方案的RFID自適應(yīng)碰撞樹(shù)算法(PACT)，該算法使用并行匹配方案來(lái)減少查詢周期的數(shù)量，同時(shí)利用沖突標(biāo)簽的數(shù)量來(lái)自適應(yīng)地選擇搜索模式，當(dāng)標(biāo)簽數(shù)大于等于4時(shí)，PACT算法選擇使用8-branch CT，在標(biāo)簽數(shù)小于4時(shí)則使用2-branch CT。PACT的系統(tǒng)效率約為0.6092，也表現(xiàn)出了較好的穩(wěn)定性。仿真結(jié)果表明，所提出的算法與現(xiàn)有的基于樹(shù)的算法相比，不僅提高了系統(tǒng)的效率和標(biāo)簽識(shí)別的速度，而且降低了時(shí)間復(fù)雜度，特別是在大規(guī)模標(biāo)簽情況下。