基于映射序列碼的自適應(yīng)查詢樹防碰撞算法

薛偉蓮，陳 杰，李雪嬌，沈 陽

（遼寧師范大學(xué)政府管理學(xué)院，遼寧大連 116029）

0 引言

射頻識別（Radio Frequency Identification，RFID）是一種利用射頻信號通過空間電磁耦合實(shí)現(xiàn)無接觸式自動(dòng)識別技術(shù)。識別系統(tǒng)由3 部分組成：應(yīng)用系統(tǒng)、閱讀器和電子標(biāo)簽，其中應(yīng)用系統(tǒng)主要包括RFID 中間件和應(yīng)用系統(tǒng)軟件，如圖1 所示。其工作原理是閱讀器通過天線發(fā)射一特定頻率的射頻信號，當(dāng)閱讀器進(jìn)入有效識別區(qū)時(shí)就會(huì)產(chǎn)生感應(yīng)電流，從而獲得能量并被激活，再將自身編碼信息通過天線發(fā)出，此時(shí)閱讀器便依序接收解讀信息，送給應(yīng)用程序作相應(yīng)處理。與傳統(tǒng)的識別技術(shù)相比，RFID 具有非接觸式讀寫、環(huán)境適應(yīng)強(qiáng)、數(shù)據(jù)容量大、可重復(fù)使用、安全性高等優(yōu)點(diǎn)，被廣泛應(yīng)用于物流盤點(diǎn)、倉庫管理、跟蹤定位等領(lǐng)域。

Fig.1 Radio frequency identification system圖1 無線射頻識別系統(tǒng)

目前，RFID 防碰撞算法主要分為兩大類：一是基于ALOHA 的隨機(jī)性算法，主要包括時(shí)隙ALOHA（SA）、幀時(shí)隙ALOHA（FSA）、動(dòng)態(tài)幀時(shí)隙ALOHA（DFSA）等；二是基于樹的確定性算法，主要包括基本二進(jìn)制搜索樹（BS）算法、查詢樹（QT）算法、碰撞樹（CT）算法、樹分裂（TS）算法等。基于ALOHA 的隨機(jī)性算法執(zhí)行過程相對簡單，易于實(shí)現(xiàn)，但存在標(biāo)簽“餓死”問題?；跇涞拇_定性算法雖然能解決標(biāo)簽“餓死”問題，但存在識別周期長、標(biāo)簽?zāi)芎拇蟮膯栴}。

QT算法是一種無記憶算法，閱讀器首先初始化查詢前綴堆棧為0 和1，閱讀器不斷發(fā)出和更新查詢前綴，如果只有一個(gè)標(biāo)簽響應(yīng)則識別該標(biāo)簽；如果多個(gè)標(biāo)簽同時(shí)響應(yīng)，即發(fā)生標(biāo)簽碰撞，則在該查詢前綴后加上0 和1 生成新的查詢前綴并入棧；不斷循環(huán)以上過程直到堆棧為空。QT算法能夠識別所有標(biāo)簽但產(chǎn)生大量空閑時(shí)隙和碰撞時(shí)隙，導(dǎo)致識別效率過低。

為改善QT算法性能，有學(xué)者依據(jù)碰撞位的特點(diǎn)對四叉樹進(jìn)行改善并提出了自適應(yīng)四叉修剪查詢樹（A4PQT）算法。A4PQT算法原理如下：假如閱讀器接收到的碰撞譯碼為

p

p

…

p p

…

p

，

p

為首位碰撞位，當(dāng)

p

不為碰撞位時(shí)產(chǎn)生兩條新的查詢前綴，這就避免了兩個(gè)空閑時(shí)隙；當(dāng)

p

也為碰撞位時(shí)，則產(chǎn)生4 條新的查詢前綴，這就有可能包括空閑時(shí)隙。因此，A4PQT算法能夠有效減少空閑時(shí)隙，但不能避免空閑時(shí)隙。

為進(jìn)一步提升查詢樹性能，文獻(xiàn)［12］提出了一種基于分組機(jī)制的位仲裁查詢樹（GBAQT）算法。該算法根據(jù)標(biāo)簽信息特征進(jìn)行分組，采用3 位仲裁位取代傳統(tǒng)1 位仲裁位，將待識別標(biāo)簽分為兩組（G=0 和G=1），閱讀器根據(jù)各組標(biāo)簽特點(diǎn)和接收數(shù)據(jù)的碰撞位信息得到傳輸數(shù)據(jù)，能夠避免一些空閑時(shí)隙。

A4PQT算法和GBAQT算法都只能達(dá)到減少空閑時(shí)隙的效果，而并不能完全消除空閑時(shí)隙。針對上述研究存在的問題，提出一種基于映射序列碼的自適應(yīng)查詢樹（Adaptive Query Tree Based on Mapping Sequence Code，MAQT）算法，MAQT算法只關(guān)注最高碰撞位為首的連續(xù)3個(gè)比特位，根據(jù)碰撞發(fā)生的位數(shù)選擇不同方法確定精確的查詢前綴，能夠?qū)崿F(xiàn)無空閑時(shí)隙，且減少碰撞時(shí)隙。

假設(shè)有7個(gè)標(biāo)簽A（000001）、B（000101）、C（011011）、D（011101）、E（010101）、F（111011）、G（100101），則QT算法、A4PQT算法及GBAQT算法查詢樹結(jié)構(gòu)如圖2 所示。

Fig.2 QT algorithm，A4PQT algorithm and GBAQT algorithm tree structure圖2 QT算法、A4PQT算法及GBAQT算法樹結(jié)構(gòu)

1 算法描述

1.1 基本思想

假設(shè)在某次查詢中，閱讀器接收到的碰撞譯碼為

p

p

…

p p

p

…

p

，

p

為首位碰撞位，則會(huì)存在以下3種情況：（1）K=1。即

p

為碰撞位，但

p

與

p

都不是碰撞位，這時(shí)閱讀器直接將

p

令為0 和1，生成兩條新的查詢前綴并壓入堆棧。如閱讀器收到碰撞譯碼為PRE+X0011X，則可直接生成PRE+00011 和PRE+10011 這兩條新的查詢前綴。（2）K=2。即

p

為碰撞位，但

p

與

p

中有一位是碰撞位，此時(shí)閱讀器將Query（PRE，SEQ）指令發(fā)送給發(fā)生碰撞的標(biāo)簽，要求返回碰撞比特位組成的比特串對應(yīng)的映射序列碼，閱讀器根據(jù)接收到的信息判斷前綴組合。如兩個(gè)標(biāo)簽A（10101010）和B（10100000）發(fā)生碰撞，閱讀器接收到碰撞譯碼為1010X0X0，屬于K=2 這種情況，此時(shí)閱讀器發(fā)送Query（1010，101）指令，要求前綴為1010 的標(biāo)簽將D1和D3 比特位組成的比特串對應(yīng)的映射序列碼發(fā)送給閱讀器，標(biāo)簽A 和B 分別發(fā)送1000 和0001，閱讀器得到譯碼結(jié)果為X00X，可推斷出兩位碰撞位為11 和00，即可確定兩條新的查詢前綴10101010 和10100000。K=2 的映射關(guān)系如表1 所示。

Table 1 Mapping relationship表1 映射關(guān)系

（3）K=3。即

p

、

p

和

p

都是碰撞位，此時(shí)閱讀器發(fā)送Query（PRE，111）指令，獲取該時(shí)隙所有可能存在的碰撞前綴的組合。如標(biāo)簽A（10101110）和B（10100001）發(fā)生碰撞，閱讀器接收到配置譯碼1010XXXX，屬于K=3 這種情況，隨即發(fā)送Query（1010，111）指令，要求前綴為1010 的標(biāo)簽將D1、D2 及D3 比特位組成的比特串對應(yīng)的映射序列碼發(fā)送給閱讀器，標(biāo)簽A 和B 分別發(fā)送10000000 和00000001，閱讀器得到譯碼結(jié)果為X000000X，可推斷出3位碰撞位為111 和000，即可確定兩條新的查詢前綴1010111 和1010000。K=3 的映射關(guān)系如表2 所示。

1.2 算法相關(guān)指令

Request（ε）：請求指令，用于初始階段的第一次查詢工作，閱讀器作用范圍內(nèi)的所有標(biāo)簽作出響應(yīng)。

Request（PRE）：請求指令，PRE 為查詢前綴，符合查詢前綴的標(biāo)簽作出響應(yīng)。

Query（PRE，SEQ）：映射識別指令，PRE為查詢前綴，SEQ為0和1組成的序列，如標(biāo)簽A（110101）和標(biāo)簽B（110000）同時(shí)響應(yīng)閱讀器發(fā)生碰撞，閱讀器收到碰撞譯碼110X0X，為確定準(zhǔn)確查詢前綴，發(fā)送Query（110，101）指令，標(biāo)簽A 和B 作出響應(yīng)，標(biāo)簽A 將自己的D0 和D2 比特位組成的比特串（11）轉(zhuǎn)化為對應(yīng)的映射序列碼（1000）并發(fā)送給閱讀器，同理標(biāo)簽B 將00 對應(yīng)的映射序列碼0001 發(fā)送給閱讀器，閱讀器得到譯碼結(jié)果為X00X，即可推斷出碰撞位為00 和11，沒有01 和10，從而確定兩條新的查詢前綴，消除空閑時(shí)隙。以上是兩位碰撞位的情況（K=2），當(dāng)出現(xiàn)三位碰撞位（K=3）時(shí)，閱讀器發(fā)送Query（PRE，111）指令獲取碰撞位準(zhǔn)確信息。

Table 2 Mapping relationship表2 映射關(guān)系

Push（PRE）：入棧指令，PRE 為查詢前綴，發(fā)出此指令后，閱讀器將此前綴壓入堆棧。

Pop（PRE）：出棧指令，PRE 為當(dāng)前棧頂前綴，發(fā)出此指令后，閱讀器將此查詢前綴彈出堆棧。

Read：讀取指令，處于激活狀態(tài)的唯一標(biāo)簽收到命令后將自身信息發(fā)送給閱讀器。

Unselect：屏蔽指令，對已經(jīng)進(jìn)行讀取操作的標(biāo)簽發(fā)送屏蔽指令，使其不再響應(yīng)后續(xù)指令。

1.3 算法流程

MAQT算法流程如圖3 所示。

Fig.3 MAQT algorithm flow圖3 MAQT算法流程

Step1：初始化查詢前綴堆棧，閱讀器發(fā)送Request（ε）請求指令，閱讀器作用范圍內(nèi)的所有標(biāo)簽作出響應(yīng)。

Step2：符合當(dāng)前查詢指令的標(biāo)簽響應(yīng)。

Step3：判斷時(shí)隙狀態(tài)，如果只有一個(gè)標(biāo)簽響應(yīng)，則識別并屏蔽該標(biāo)簽，跳轉(zhuǎn)到Step6；如果多個(gè)標(biāo)簽同時(shí)響應(yīng)，則針對碰撞位的位數(shù)K 分以下2 種情況：①K=1 時(shí)，直接產(chǎn)生兩條新的查詢前綴，轉(zhuǎn)到Step4；②K=2 或3 時(shí)，需要閱讀器發(fā)送Query（PRE，SEQ）指令，響應(yīng)的標(biāo)簽將碰撞比特位組成的比特串對應(yīng)的映射序列碼發(fā)送給閱讀器，閱讀器對接收到的映射序列碼進(jìn)行解碼以確定新的查詢前綴，轉(zhuǎn)到Step4。

Step4：將新的查詢前綴壓入堆棧。

Step5：閱讀器由棧頂至棧底的順序依次將Request（PRE）指令發(fā)送給標(biāo)簽，并返回至Step2。

Step6：判斷堆棧是否為空：若堆棧不為空，返回至Step5；若堆棧為空，說明所有標(biāo)簽都被識別，識別過程結(jié)束。

本文將舉例說明MAQT算法識別標(biāo)簽具體步驟。假設(shè)待識別標(biāo)簽仍為上文舉例的7個(gè)標(biāo)簽，分別為A（000001）、B（000101）、C（011011）、D（011101）、E（010101）、F（111011）、G（100101）。MAQT算法閱讀器查詢和標(biāo)簽響應(yīng)情況如表3 所示，對應(yīng)的查詢樹結(jié)構(gòu)如圖4 所示。

Table 3 Reader queries and tag responses表3 閱讀器查詢和標(biāo)簽響應(yīng)情況

Fig.4 MAQT algorithm tree structure圖4 MAQT算法樹結(jié)構(gòu)

2 算法性能分析

假設(shè)待識別標(biāo)簽個(gè)數(shù)為

m

，對于一棵完整的B 叉樹，在第L 層的節(jié)點(diǎn)個(gè)數(shù)為8（設(shè)定根節(jié)點(diǎn)為第0 層）。由于每個(gè)標(biāo)簽的分配相對獨(dú)立，則

k

個(gè)標(biāo)簽選擇同一個(gè)節(jié)點(diǎn)的概率為：

由此可得某節(jié)點(diǎn)為空閑節(jié)點(diǎn)的概率為：

某節(jié)點(diǎn)為成功節(jié)點(diǎn)的概率為：

某節(jié)點(diǎn)為碰撞節(jié)點(diǎn)的概率為：

假設(shè)

q

為第L 層的第

i

個(gè)節(jié)點(diǎn)被查詢到的概率；

β

為第L 層的第

i

個(gè)節(jié)點(diǎn)為碰撞節(jié)點(diǎn)的概率。則：

識別所有標(biāo)簽的總時(shí)隙數(shù)為：

結(jié)合式（5）可得：

同理可求得碰撞時(shí)隙為：

空閑時(shí)隙為：

本文是基于八叉樹算法的改進(jìn)，根據(jù)式（8）可知一棵完整八叉樹的總時(shí)隙數(shù)為：

根據(jù)式（9）可知一棵完整八叉樹的碰撞時(shí)隙數(shù)為：

根據(jù)式（10）可知一棵完整八叉樹的空閑時(shí)隙數(shù)為：

如果碰撞位僅一位，即K=1，則樹的結(jié)構(gòu)為二叉樹，此時(shí)碰撞節(jié)點(diǎn)的子節(jié)點(diǎn)總數(shù)為八叉樹的1∕4，假設(shè)該碰撞節(jié)點(diǎn)有

N

個(gè)標(biāo)簽，則沒有標(biāo)簽選擇兩個(gè)子節(jié)點(diǎn)中一個(gè)的概率為：

則在第L 層的碰撞節(jié)點(diǎn)執(zhí)行K=1 的概率為：

根據(jù)以上信息可求得總時(shí)隙數(shù)：

由于MAQT算法能夠完全避免空閑時(shí)隙，且以最高碰撞位為首的連續(xù)3個(gè)比特位發(fā)生2 位（K=2）或3 位（K=3）碰撞時(shí)，閱讀器需要發(fā)送額外指令以獲取碰撞位的準(zhǔn)確信息。

根據(jù)式（10）可知，多余的空閑時(shí)隙數(shù)：

綜上所述，MAQT算法的總時(shí)隙數(shù)為：

吞吐率就是識別效率，為待識別標(biāo)簽總數(shù)與總時(shí)隙的比值，有：

3 仿真及分析

利用MATLAB 平臺對QT算法、A4PQT算法、GBAQT算法和MAQT算法進(jìn)行仿真與比較。標(biāo)簽ID 均勻分布，長度固定為96bit，標(biāo)簽數(shù)量為100～1000 區(qū)間動(dòng)態(tài)變化，取50 次仿真實(shí)驗(yàn)結(jié)果的平均值作為最終仿真結(jié)果。

圖6 為MAQT算法、QT算法、A4PQT算法和GBAQT算法總時(shí)隙數(shù)的比較，可以看出MAQT算法在識別m個(gè)標(biāo)簽時(shí)所需的總時(shí)隙數(shù)明顯小于其它3 種算法。當(dāng)標(biāo)簽數(shù)量達(dá)到1 000 時(shí)，MAQT算法需要1 639個(gè)總時(shí)隙，比QT算法減少43.8%的總時(shí)隙數(shù)，比A4PQT算法減少21.5%的總時(shí)隙數(shù)，比GBAQT算法減少10.8%的總時(shí)隙數(shù)。MAQT算法根據(jù)最高碰撞位為首的連續(xù)3個(gè)比特位發(fā)生碰撞的位數(shù)動(dòng)態(tài)選擇產(chǎn)生前綴的方法，并通過映射序列碼消除空閑時(shí)隙從而減少總時(shí)隙數(shù)。

圖7 為MAQT算法、QT算法、A4PQT算法和GBAQT算法吞吐率比較?？梢钥闯觯琈AQT算法吞吐率明顯優(yōu)于其它3 種算法，可維持在0.61 左右；QT算法的吞吐率維持在0.35 左右，在4 種算法中表現(xiàn)最差；A4PQT算法的吞吐率不超過0.49，GBAQT算法的吞吐率在0.48 左右。

Fig.6 Comparison of total number of slots圖6 總時(shí)隙數(shù)比較

Fig.7 Throughput rate comparison圖7 吞吐率比較

4 結(jié)語

本文提出了一種基于映射序列碼的自適應(yīng)查詢樹防碰撞算法（MAQT），根據(jù)最高碰撞位為首的連續(xù)3個(gè)比特位發(fā)生碰撞的位數(shù)動(dòng)態(tài)選擇產(chǎn)生前綴的方法。當(dāng)以最高碰撞位為首的3個(gè)連續(xù)比特位中僅有一個(gè)碰撞位（K=1）時(shí)，直接產(chǎn)生兩條查詢前綴，采用二叉樹方式搜索；當(dāng)以最高碰撞位為首的3個(gè)連續(xù)比特位中有2個(gè)或3個(gè)碰撞位（K=2 或K=3）時(shí)，根據(jù)唯一的映射關(guān)系確定存在的查詢前綴，從而消除多叉樹的空閑時(shí)隙，減少了碰撞時(shí)隙。仿真結(jié)果表明，MAQT算法在總時(shí)隙數(shù)和吞吐率方面都有著較好的表現(xiàn)。當(dāng)待識別標(biāo)簽的ID 過長時(shí)，查詢樹算法的深度會(huì)相應(yīng)增加。基于隨機(jī)數(shù)的查詢樹算法能夠有效降低查詢樹深度，是未來的一個(gè)研究方向。