基于映射序列碼的自適應查詢樹防碰撞算法

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

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

0 引言

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

Fig.1 Radio frequency identification system圖1 無線射頻識別系統

目前，RFID 防碰撞算法主要分為兩大類：一是基于ALOHA 的隨機性算法，主要包括時隙ALOHA（SA）、幀時隙ALOHA（FSA）、動態幀時隙ALOHA（DFSA）等；二是基于樹的確定性算法，主要包括基本二進制搜索樹（BS）算法、查詢樹（QT）算法、碰撞樹（CT）算法、樹分裂（TS）算法等。基于ALOHA 的隨機性算法執行過程相對簡單，易于實現，但存在標簽“餓死”問題。基于樹的確定性算法雖然能解決標簽“餓死”問題，但存在識別周期長、標簽能耗大的問題。

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

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

p

p

…

p p

…

p

，

p

為首位碰撞位，當

p

不為碰撞位時產生兩條新的查詢前綴，這就避免了兩個空閑時隙；當

p

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

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

A4PQT算法和GBAQT算法都只能達到減少空閑時隙的效果，而并不能完全消除空閑時隙。針對上述研究存在的問題，提出一種基于映射序列碼的自適應查詢樹（Adaptive Query Tree Based on Mapping Sequence Code，MAQT）算法，MAQT算法只關注最高碰撞位為首的連續3個比特位，根據碰撞發生的位數選擇不同方法確定精確的查詢前綴，能夠實現無空閑時隙，且減少碰撞時隙。

假設有7個標簽A（000001）、B（000101）、C（011011）、D（011101）、E（010101）、F（111011）、G（100101），則QT算法、A4PQT算法及GBAQT算法查詢樹結構如圖2 所示。

Fig.2 QT algorithm，A4PQT algorithm and GBAQT algorithm tree structure圖2 QT算法、A4PQT算法及GBAQT算法樹結構

1 算法描述

1.1 基本思想

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

p

p

…

p p

p

…

p

，

p

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

p

為碰撞位，但

p

與

p

都不是碰撞位，這時閱讀器直接將

p

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

p

為碰撞位，但

p

與

p

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

Table 1 Mapping relationship表1 映射關系

（3）K=3。即

p

、

p

和

p

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

1.2 算法相關指令

Request（ε）：請求指令，用于初始階段的第一次查詢工作，閱讀器作用范圍內的所有標簽作出響應。

Request（PRE）：請求指令，PRE 為查詢前綴，符合查詢前綴的標簽作出響應。

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

Table 2 Mapping relationship表2 映射關系

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

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

Read：讀取指令，處于激活狀態的唯一標簽收到命令后將自身信息發送給閱讀器。

Unselect：屏蔽指令，對已經進行讀取操作的標簽發送屏蔽指令，使其不再響應后續指令。

1.3 算法流程

MAQT算法流程如圖3 所示。

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

Step1：初始化查詢前綴堆棧，閱讀器發送Request（ε）請求指令，閱讀器作用范圍內的所有標簽作出響應。

Step2：符合當前查詢指令的標簽響應。

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

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

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

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

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

Table 3 Reader queries and tag responses表3 閱讀器查詢和標簽響應情況

Fig.4 MAQT algorithm tree structure圖4 MAQT算法樹結構

2 算法性能分析

假設待識別標簽個數為

m

，對于一棵完整的B 叉樹，在第L 層的節點個數為8（設定根節點為第0 層）。由于每個標簽的分配相對獨立，則

k

個標簽選擇同一個節點的概率為：

由此可得某節點為空閑節點的概率為：

某節點為成功節點的概率為：

某節點為碰撞節點的概率為：

假設

q

為第L 層的第

i

個節點被查詢到的概率；

β

為第L 層的第

i

個節點為碰撞節點的概率。則：

識別所有標簽的總時隙數為：

結合式（5）可得：

同理可求得碰撞時隙為：

空閑時隙為：

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

根據式（9）可知一棵完整八叉樹的碰撞時隙數為：

根據式（10）可知一棵完整八叉樹的空閑時隙數為：

如果碰撞位僅一位，即K=1，則樹的結構為二叉樹，此時碰撞節點的子節點總數為八叉樹的1∕4，假設該碰撞節點有

N

個標簽，則沒有標簽選擇兩個子節點中一個的概率為：

則在第L 層的碰撞節點執行K=1 的概率為：

根據以上信息可求得總時隙數：

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

根據式（10）可知，多余的空閑時隙數：

綜上所述，MAQT算法的總時隙數為：

吞吐率就是識別效率，為待識別標簽總數與總時隙的比值，有：

3 仿真及分析

利用MATLAB 平臺對QT算法、A4PQT算法、GBAQT算法和MAQT算法進行仿真與比較。標簽ID 均勻分布，長度固定為96bit，標簽數量為100～1000 區間動態變化，取50 次仿真實驗結果的平均值作為最終仿真結果。

圖6 為MAQT算法、QT算法、A4PQT算法和GBAQT算法總時隙數的比較，可以看出MAQT算法在識別m個標簽時所需的總時隙數明顯小于其它3 種算法。當標簽數量達到1 000 時，MAQT算法需要1 639個總時隙，比QT算法減少43.8%的總時隙數，比A4PQT算法減少21.5%的總時隙數，比GBAQT算法減少10.8%的總時隙數。MAQT算法根據最高碰撞位為首的連續3個比特位發生碰撞的位數動態選擇產生前綴的方法，并通過映射序列碼消除空閑時隙從而減少總時隙數。

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

Fig.6 Comparison of total number of slots圖6 總時隙數比較

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

4 結語

本文提出了一種基于映射序列碼的自適應查詢樹防碰撞算法（MAQT），根據最高碰撞位為首的連續3個比特位發生碰撞的位數動態選擇產生前綴的方法。當以最高碰撞位為首的3個連續比特位中僅有一個碰撞位（K=1）時，直接產生兩條查詢前綴，采用二叉樹方式搜索；當以最高碰撞位為首的3個連續比特位中有2個或3個碰撞位（K=2 或K=3）時，根據唯一的映射關系確定存在的查詢前綴，從而消除多叉樹的空閑時隙，減少了碰撞時隙。仿真結果表明，MAQT算法在總時隙數和吞吐率方面都有著較好的表現。當待識別標簽的ID 過長時，查詢樹算法的深度會相應增加?；陔S機數的查詢樹算法能夠有效降低查詢樹深度，是未來的一個研究方向。