基于映射分組的改進(jìn)型碰撞跟蹤樹(shù)算法

劉本超，楊恒新，張 昀

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

0 引 言

射頻識(shí)別(RFID)是一種以無(wú)線電技術(shù)為基礎(chǔ)，以對(duì)目標(biāo)物體的自動(dòng)識(shí)別為目的非接觸式識(shí)別技術(shù)，主要由閱讀器、標(biāo)簽和中央信息處理系統(tǒng)組成[1]。識(shí)別距離較遠(yuǎn)的超高頻射頻識(shí)別是利用空間電磁反向散射耦合實(shí)現(xiàn)無(wú)線雙向數(shù)據(jù)傳輸，從而實(shí)現(xiàn)對(duì)目標(biāo)的自動(dòng)識(shí)別[2]。標(biāo)簽與閱讀器進(jìn)行通信時(shí)主要有兩種形式的碰撞，分別是標(biāo)簽碰撞和閱讀器碰撞。閱讀器碰撞可通過(guò)閱讀器間建立的工作協(xié)調(diào)機(jī)制解決沖突問(wèn)題[3]。由于受成本制約，標(biāo)簽的功能單一、功率低，標(biāo)簽碰撞問(wèn)題成為制約RFID系統(tǒng)的關(guān)鍵因素。

為解決標(biāo)簽碰撞問(wèn)題，研究人員提出了許多有效的防碰撞算法。目前，標(biāo)簽防碰撞算法大體可分為兩類(lèi)：確定性防碰撞算法和隨機(jī)性防碰撞算法。

隨機(jī)性算法主要是基于ALOHA的算法，這種算法設(shè)備簡(jiǎn)單，花費(fèi)低，識(shí)別速度快?；贏LOHA的算法，包括純ALOHA算法、時(shí)隙ALOHA算法、幀時(shí)隙ALOHA算法、動(dòng)態(tài)幀時(shí)隙ALOHA算法以及基于ALOHA的各種改進(jìn)算法[4-5]。但由于ALOHA類(lèi)算法標(biāo)簽隨機(jī)選擇時(shí)隙，因而造成識(shí)別的不確定性，即可能出現(xiàn)大量標(biāo)簽“扎堆”碰撞或者出現(xiàn)大量空閑時(shí)隙的情況，即“標(biāo)簽饑餓”問(wèn)題[6]。

確定性算法主要是基于樹(shù)的算法，它采用了分離的思想，將碰撞的標(biāo)簽連續(xù)分為不同的子集，直至成功識(shí)別所有標(biāo)簽，所以它避免了“標(biāo)簽饑餓”問(wèn)題，識(shí)別效率高[7]。最基本的基于樹(shù)的防碰撞算法是二進(jìn)制防碰撞算法，但其吞吐率較低。查詢樹(shù)(QT)算法[8]是一種無(wú)記憶防碰撞算法，極大地促進(jìn)了樹(shù)型防碰撞算法的發(fā)展。人們?cè)诓樵儤?shù)算法的基礎(chǔ)上又提出了許多改進(jìn)算法，例如基于前綴檢測(cè)的算法[9]，提高了RFID系統(tǒng)工作效率。碰撞跟蹤樹(shù)(collision tracking tree，CTT)[10]算法的核心思想是在查詢樹(shù)算法的基礎(chǔ)上通過(guò)曼徹斯特編碼(Manchester encoding)方式來(lái)檢測(cè)具體的碰撞位，通過(guò)只查詢非碰撞位來(lái)提高查詢速度。其改進(jìn)算法[11]在檢測(cè)碰撞位的基礎(chǔ)上引入多位查詢前綴，降低了查詢深度。

文中在碰撞跟蹤樹(shù)算法的基礎(chǔ)上，通過(guò)曼徹斯特編碼鎖定碰撞位，將碰撞位每3比特為一組進(jìn)行分組，并進(jìn)行重新編碼，引入映射碼。標(biāo)簽端發(fā)送第i組映射碼，閱讀器根據(jù)收到的映射碼有效地識(shí)別標(biāo)簽ID，設(shè)置合理的查詢前綴。

1 碰撞跟蹤樹(shù)算法

設(shè)閱讀器端有一堆棧Q，閱讀器發(fā)送查詢指令，查詢范圍內(nèi)所有標(biāo)簽；標(biāo)簽返回自身唯一ID信息，閱讀器根據(jù)曼徹斯特編碼的特點(diǎn)得到碰撞信息即具體碰撞位。設(shè)標(biāo)簽ID長(zhǎng)度為k，首位碰撞位為第i位，閱讀器首先將第i位之前的信息r1…ri-1添加0和1組成r1…ri-10和r1…ri-11前綴壓入堆棧，閱讀器再次發(fā)送查詢命令，所有匹配查詢序列的標(biāo)簽將返回長(zhǎng)度為k-r的標(biāo)簽剩余ID。閱讀器收到信息后再次檢測(cè)碰撞位，將碰撞位之前的ID添加0和1再次作為查詢前綴壓入堆棧，直到?jīng)]有標(biāo)簽未被識(shí)別。當(dāng)堆棧為空時(shí)，閱讀器可判定所有標(biāo)簽已被成功識(shí)別，結(jié)束查詢。因?yàn)镃TT算法是在碰撞位基礎(chǔ)上進(jìn)行的查詢，所以避免了空時(shí)隙，極大地提高了識(shí)別速率。

2 基于映射分組的改進(jìn)型碰撞跟蹤樹(shù)算法

CTT算法雖然能去除空閑時(shí)隙，但由于每次查詢?nèi)匀徊捎枚鏄?shù)的形式，因此查詢次數(shù)仍然很多。文獻(xiàn)[12]提出了一種基于分組碼的改進(jìn)型防碰撞算法(IABC算法)，該算法令標(biāo)簽ID每3比特為一組，以0和1的分布情況進(jìn)行分類(lèi)，得到四種類(lèi)型的分組碼。由于分組碼01和001分別對(duì)應(yīng)三種標(biāo)簽識(shí)別碼，因此需要二次發(fā)送確定準(zhǔn)確的標(biāo)簽識(shí)別碼。因此，提出一種基于映射分組的改進(jìn)型碰撞跟蹤樹(shù)算法(improved collision tracking tree algorithm based on mapping grouping，ICTTMG)。該算法可以建立標(biāo)簽識(shí)別碼與映射碼的一一對(duì)應(yīng)關(guān)系，因此可以準(zhǔn)確地判定所需要的查詢前綴，避免了二次發(fā)送，提高了識(shí)別速率，又降低了系統(tǒng)通信量。

2.1 算法描述

ICTTMG算法主要分為兩個(gè)階段：鎖定碰撞位和映射識(shí)別。

(1)鎖定碰撞位。

算法首先利用曼徹斯特編碼鎖定碰撞位。曼徹斯特編碼采用電平的跳變表示信息，從高電平跳變到低電平表示“1”，從低電平跳變到高電平表示“0”，采用該編碼方案的優(yōu)點(diǎn)是當(dāng)有碰撞發(fā)生時(shí)，閱讀器接收到的信號(hào)全為高電平，可確定此時(shí)發(fā)生碰撞。

(2)映射識(shí)別。

首先將標(biāo)簽碰撞ID按每3比特為一組分為k組，因?yàn)镃TT算法可得到具體碰撞位數(shù)，所以我們可確定最后一組的具體位數(shù)，不足3比特的按照最高位添加0處理。閱讀器發(fā)送查詢指令，標(biāo)簽返回第i組ID的映射碼，映射規(guī)則如表1所示。

表1 映射碼

為了減少通信量同時(shí)能方便地識(shí)別映射碼，閱讀器端設(shè)有5個(gè)堆棧S1、S2、S3、S4、S5。閱讀器根據(jù)第i組映射碼位數(shù)的不同壓入不同的查詢堆棧：映射碼位數(shù)為1、2、3、4位的響應(yīng)信息分別壓入堆棧S1、S2、S3、S4。例如：ID為001和101對(duì)應(yīng)的映射碼分別為01和10，將其存入堆棧S2，則根據(jù)曼徹斯特編碼，得到信息xx，x表示無(wú)法確定0和1，那么可以很容易地確定出標(biāo)簽返回的信息是10和01，即存在ID為001和101的標(biāo)簽，并將10和01前綴壓入堆棧S5，同時(shí)記錄分組編號(hào)i。每個(gè)標(biāo)簽都附帶一個(gè)計(jì)數(shù)器和存儲(chǔ)器RC，用來(lái)記錄映射碼信息。

首先將標(biāo)簽狀態(tài)分為激活態(tài)、等待態(tài)和睡眠態(tài)。激活態(tài)：標(biāo)簽處于激活態(tài)時(shí)，能夠接收閱讀器發(fā)送查詢指令并與之通信。等待態(tài)：標(biāo)簽處于等待態(tài)時(shí)，暫時(shí)無(wú)法與閱讀器通信，直到被激活。睡眠態(tài)：標(biāo)簽處于睡眠態(tài)，表示標(biāo)簽已經(jīng)被成功識(shí)別，并且不再響應(yīng)閱讀器。

為了更好地描述該算法，引入下列三條指令：

(1)Query_all：閱讀器發(fā)送該命令，查詢范圍內(nèi)所有標(biāo)簽，標(biāo)簽被激活并發(fā)送自身ID；

(2)Lock(TID)：標(biāo)簽收到該命令后鎖定碰撞位，轉(zhuǎn)換成映射碼并存儲(chǔ)到寄存器RC中；

(3)Query(prefix，i)：閱讀器發(fā)送該命令，prefix為查詢前綴序列，i表示分組編號(hào)。處于激活態(tài)的標(biāo)簽需將自己臨時(shí)ID號(hào)中第i組映射碼與prefix進(jìn)行比較，若匹配，響應(yīng)閱讀器；反之，標(biāo)簽轉(zhuǎn)為等待態(tài)。

2.2 算法具體步驟

以下為ICTTMG算法的具體執(zhí)行過(guò)程：

(1)初始化堆棧，閱讀器發(fā)送Query_all指令，所有標(biāo)簽響應(yīng)并返回ID信息。

(2)閱讀器記錄能正確識(shí)別的比特位，同時(shí)記錄發(fā)生碰撞的位置。假設(shè)有四個(gè)標(biāo)簽，其ID分別為：11010，10101，10001，11000，那么閱讀器收到的信息為：1xxxx，x表示發(fā)生碰撞。

(3)閱讀器發(fā)送Lock(TID)命令，其中碰撞位用1表示，非碰撞位用0表示，標(biāo)簽將收到的信息與自己的ID進(jìn)行匹配，得到碰撞位信息，根據(jù)映射關(guān)系表，每3比特為一組，進(jìn)行映射操作，將映射碼存入寄存器RC中，初始化標(biāo)簽計(jì)數(shù)器i為1。

(4)閱讀器發(fā)送Query(prefix,i)指令，標(biāo)簽被激活并響應(yīng)閱讀器，標(biāo)簽發(fā)送第i組映射碼加上剩余ID信息給閱讀器，同時(shí)標(biāo)簽計(jì)數(shù)器i值加1。

(5)閱讀器將不同位數(shù)的響應(yīng)信息分別壓入堆棧S1、S2、S3、S4，進(jìn)行譯碼后得到查詢前綴，并將前綴壓入堆棧S5中，同時(shí)記錄分組編號(hào)i。

(6)標(biāo)簽接收到前綴prefix和分組編號(hào)i，計(jì)數(shù)器值等于i的標(biāo)簽將前綴與自身映射碼做比對(duì)，具有相同前綴的標(biāo)簽激活并響應(yīng)閱讀器。若閱讀器未檢測(cè)到碰撞，則直接識(shí)別該標(biāo)簽，讀取數(shù)據(jù)并進(jìn)行滅活操作，堆棧S5彈出下一組前綴，返回步驟4；若檢測(cè)到碰撞，則令i=i+1，跳轉(zhuǎn)至步驟4。

(7)判斷堆棧S5是否為空或者全部標(biāo)簽被識(shí)別，結(jié)束識(shí)別過(guò)程。

2.3 算法實(shí)例

假設(shè)有8個(gè)待識(shí)別標(biāo)簽分別為：A(10110100)、B(10010110)、C(11010001)、D(11000100)、E(11000000)、F(10000110)、G(10000101)、H(11010110)。閱讀器根據(jù)標(biāo)簽返回的信息，確定碰撞位，可得1xxx0xxx，即有6個(gè)碰撞位，標(biāo)簽根據(jù)閱讀器發(fā)送的碰撞跟蹤信息，將自己的碰撞位取出，根據(jù)上面的編碼規(guī)則進(jìn)行編碼，如表2所示。

算法具體查詢過(guò)程如表3所示。

表2 標(biāo)簽ID映射

表3 ICTTMG算法查詢過(guò)程

3 算法仿真驗(yàn)證

3.1 時(shí)間復(fù)雜度

由文獻(xiàn)[13]可知，對(duì)于八叉樹(shù)算法識(shí)別n個(gè)標(biāo)簽所需要的總時(shí)隙數(shù)為：

n8-L(1-8-L)n-1]

(1)

其中，碰撞時(shí)隙數(shù)、空閑時(shí)隙數(shù)和識(shí)別效率分別如下：

(2)

(3)

(4)

對(duì)于提出的算法，時(shí)間復(fù)雜度主要由標(biāo)簽數(shù)量和非碰撞位數(shù)決定。設(shè)標(biāo)簽數(shù)量為n，非碰撞位數(shù)為m(取50)，則總時(shí)隙數(shù)TICTTMG和吞吐率E經(jīng)MATLAB[14]仿真驗(yàn)證的結(jié)果如圖1和圖2所示。

圖1 五種算法總時(shí)隙數(shù)比較

圖2 五種算法吞吐率比較

由圖1可以看出，提出的算法需要的時(shí)隙數(shù)最少，識(shí)別1 000個(gè)標(biāo)簽只需要1 416個(gè)時(shí)隙，比基本CTT算法少用了30%的時(shí)隙，比IABC算法也少用了約5%的時(shí)隙。由圖2可以看出，提出的算法具有最高的吞吐率，比基本CTT算法提高了約22%，明顯高于其他算法[15-16]。

3.2 通信復(fù)雜度

文中算法的通信復(fù)雜度涉及兩個(gè)階段。

(1)鎖定碰撞位。

閱讀器需要發(fā)送鎖定命令字Lock，標(biāo)簽返回ID信息，ID長(zhǎng)度為k，因此總通信量為:

Tra1=2k

(5)

(2)前綴查詢。

設(shè)標(biāo)簽非碰撞位為m，則碰撞ID長(zhǎng)度為k-m，根據(jù)表1的編碼方案，標(biāo)簽每3比特信息經(jīng)再編碼后平均長(zhǎng)度為2.5比特，比原來(lái)減少0.5比特，因此降低了系統(tǒng)通信復(fù)雜度。閱讀器發(fā)送查詢前綴和分組編號(hào)，而標(biāo)簽發(fā)送一組映射碼加臨時(shí)ID的剩余位比特信息，其數(shù)據(jù)位長(zhǎng)度取決于標(biāo)簽在八叉樹(shù)第幾層成功識(shí)別。假設(shè)標(biāo)簽在L層被識(shí)別的概率為Ps(L)，則

(6)

標(biāo)簽發(fā)送的比特位信息平均期望值為：

(7)

因此，第二階段標(biāo)簽和閱讀器總通信量為：

Tra2=2.5*TICTTMG+CT*TICTTMG

(8)

總通信量為：

Tra=Tra1+Tra2

(9)

根據(jù)EPC C1G2協(xié)議[17]的規(guī)定，標(biāo)簽ID長(zhǎng)度k取96位，其中唯一標(biāo)識(shí)序列號(hào)長(zhǎng)度為36位，非碰撞位數(shù)m取值50，據(jù)此計(jì)算通信量。對(duì)各種算法的通信量進(jìn)行仿真驗(yàn)證，如圖3所示。

圖3 五種算法通信量比較

因?yàn)樘岢龅母倪M(jìn)算法使用了合理的映射編碼方案，每3比特ID經(jīng)編碼后平均長(zhǎng)度變?yōu)?.5比特，而且每次查詢平均只需查詢2.5比特前綴，極大降低了系統(tǒng)的通信量。MATLAB仿真表明，該算法具有最低的通信復(fù)雜度，比CTT算法減少了約68%的通信量，隨著非碰撞位數(shù)m的增大，算法通信復(fù)雜度性能進(jìn)一步提升。

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

在傳統(tǒng)CTT算法的基礎(chǔ)上，提出的ICTTMG算法改變了傳統(tǒng)CTT算法每次只能識(shí)別一位比特的缺點(diǎn)，該算法結(jié)合映射識(shí)別碼，減少了整個(gè)識(shí)別過(guò)程中的查詢次數(shù)，利用一個(gè)查詢響應(yīng)周期對(duì)識(shí)別碼中碰撞位進(jìn)行鎖定，同時(shí)平均每次只需發(fā)送2.5比特查詢前綴，優(yōu)化了閱讀器命令。仿真結(jié)果表明，算法在時(shí)間復(fù)雜度和通信復(fù)雜度方面都有明顯改善。