基于分組映射的防碰撞查詢樹算法

董軒江,李世寶,蔡麗萍,袁 靜

(中國石油大學(華東) 計算機與通信工程學院,山東 青島 266580)

0 概述

物聯(lián)網(wǎng)是遵循既定規(guī)定使用射頻識別(Radio Frequency Identification,RFID)等信息傳感儀器,在任意物品與互聯(lián)網(wǎng)之間建立聯(lián)系進行信息傳輸,以完成對所關(guān)聯(lián)物品識別定位等操作的網(wǎng)絡(luò)。隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展,射頻識別技術(shù)作為物聯(lián)網(wǎng)的關(guān)鍵技術(shù)得到廣泛應(yīng)用并成為研究熱點[1]。傳統(tǒng)的射頻識別系統(tǒng)主要由閱讀器、識別標簽和處理器構(gòu)成[2]。如果多個標簽同時處于同一閱讀器的識別范圍,當該閱讀器發(fā)送識別請求時,會出現(xiàn)多個標簽同時響應(yīng)該閱讀器的現(xiàn)象,這種現(xiàn)象稱為標簽碰撞[3]。

標簽碰撞問題通常用標簽防碰撞算法進行處理。標簽防碰撞算法分為兩種:一種是基于ALOHA算法的不確定性算法[4-6],包括ALOHA算法[7]、時隙ALOHA算法等;另一種是基于樹的確定性算法[8-9],包括二進制搜索樹算法、查詢樹(Query Tree,QT)算法[10]、碰撞樹算法[11]等?；贏LOHA算法的防碰撞算法無法解決某些標簽不能被讀取的“標簽饑餓”現(xiàn)象,特別是當標簽數(shù)量增加時系統(tǒng)識別效率表現(xiàn)較差[12]?；跇涞姆琅鲎菜惴ㄓ捎谑谴_定性算法,不存在“標簽饑餓”問題。查詢樹算法是基于樹的防碰撞算法的重要組成部分。目前基于查詢樹算法的系統(tǒng)效率較低,且通信復(fù)雜度較高[13]。

本文提出一種基于雙重分組和對位映射的防碰撞查詢樹算法(DGMQT算法)。根據(jù)標簽識別碼特征進行雙重分組操作和識別碼對位映射操作,對碰撞信息分組解碼并準確定位查詢信息,以消除空閑時隙和減少碰撞時隙,提升系統(tǒng)識別效率。

1 相關(guān)工作

1.1 比特追蹤技術(shù)

在RFID防碰撞算法設(shè)計中,為了定位碰撞信息通常會使用比特追蹤技術(shù),該技術(shù)以曼徹斯特編碼為基礎(chǔ)[14-16]。曼徹斯特編碼將單比特數(shù)據(jù)編碼為電平跳變,即數(shù)據(jù)“0”被編碼為上升沿,數(shù)據(jù)“1”被編碼為下降沿。曼徹斯特編碼機制不允許出現(xiàn)“無跳變”現(xiàn)象,這是因為讀寫器需要借此判斷傳遞的信號是否發(fā)生碰撞。采用基于曼徹斯特編碼方式的RFID防碰撞算法,可在閱讀器端對碰撞情況進行處理。DGMQT算法采用曼徹斯特編碼方式對碰撞信息進行跟蹤與解析,進而得到準確的查詢前綴。例如,Tag1和Tag2兩個標簽的識別碼分別為1010和1100,當兩個標簽在同一時刻開始傳送識別碼信息時,閱讀器接收到的信息為1XX0(X為碰撞位),這表示碰撞位的位置為第2位和第3位,其中比特追蹤技術(shù)的響應(yīng)過程如圖1所示。出現(xiàn)標簽碰撞后閱讀器將無法識別標簽,采用有效的防碰撞算法可解決該問題[17]。

圖1 比特追蹤技術(shù)響應(yīng)過程示意圖Fig.1 Schematic diagram of response process of bit tracking technology

1.2 查詢樹算法

查詢樹算法的使用較簡單,只需由系統(tǒng)記錄識別標簽自身識別碼[18],其查詢過程類似于樹形結(jié)構(gòu)中尋找二叉樹的葉子結(jié)點:閱讀器對功能區(qū)域內(nèi)全部標簽發(fā)送查詢信號,標簽識別碼前綴與查詢信號一致的標簽會產(chǎn)生反饋,把自身的識別碼返回傳遞給閱讀器。閱讀器接收到反饋后,根據(jù)信息碰撞情況進行處理:如果無碰撞,則識別該信號后出棧剩余查詢碼,發(fā)送下一輪查詢信號;如果發(fā)生碰撞,則在上一輪發(fā)送的查詢信息后添加一位0或1再次發(fā)送查詢信息,添加1或0的查詢碼進行入棧操作。以上操作將循環(huán)執(zhí)行直到完成全部標簽的識別。

由上述查詢過程可知,隨著標簽識別碼長度和標簽數(shù)量的增加,查詢樹算法進行識別所需查詢碼長度增加,標簽碰撞的概率增大,識別標簽所需時間增長,系統(tǒng)識別效率降低。

1.3 基于查詢樹算法研究

針對查詢樹算法存在的上述問題,研究者們提出許多改進算法。文獻[19]在A4PQT算法[20]的空閑時隙問題基礎(chǔ)上提出基于分組機制的位仲裁查詢樹防碰撞算法(GBAQT算法),根據(jù)標簽識別碼自身特征將未識別標簽分為兩組,分組情況如表1所示。

表1 未識別標簽分組情況Table 1 Grouping situation of unrecognized labels

閱讀器通過分析返回的碰撞信息發(fā)送查詢碼進行下一輪識別,當標簽識別碼發(fā)生碰撞時,閱讀器接收到的同組標簽識別碼存在以下4種情況:

1)該組有1列識別碼,如果為G=0組,則返回識別碼000(或者011/101/110);如果為G=1組,則返回識別碼001(或者010/100/111)。在該情況下,識別碼可直接被識別,不需進行下一步處理。

2)該組有2列識別碼,例如G=0組返回的識別碼為000和011,閱讀器接收的碰撞信息為0XX,閱讀器在下一輪發(fā)送000和011作為前綴進行查詢。

3)該組含有3列識別碼,例如G=0組返回的識別碼為000、011和101,閱讀器接收的碰撞信息為XXX,全碰撞情況下閱讀器在下一輪只能選擇發(fā)送G=0組的全部識別碼作為前綴進行查詢,從而產(chǎn)生1組空閑時隙。

4)該組含有4列識別碼,在該情況下標簽返回的為全碰撞信息,閱讀器在下一輪將發(fā)送全部該組識別碼作為前綴,不會產(chǎn)生空閑時隙。

在上述4種情況中,只有第3種情況產(chǎn)生空閑時隙,其發(fā)生概率為4/15。GBAQT算法雖然采用分組思想改進A4PQT算法,但是沒有避免產(chǎn)生空閑時隙,導(dǎo)致算法效率仍較低。

針對上述問題,本文基于分組思想和映射機制,提出一種雙重分組的對位映射防碰撞查詢樹DGMQT算法。首先根據(jù)標簽特征進行分組,然后利用對位映射機制將分組后的標簽識別碼映射為唯一且清晰可辨的映射數(shù)據(jù),閱讀器根據(jù)該映射機制將碰撞后的映射信息直接解碼出查詢前綴,從而避免在下一輪查詢過程中產(chǎn)生空閑時隙。

2 雙重分組對位映射防碰撞查詢樹算法

2.1 設(shè)計思想

DGMQT算法是在標簽分組的基礎(chǔ)上加入對位映射機制,使用映射碼代替標簽識別碼進行信息傳輸,經(jīng)過分組映射后的數(shù)據(jù)在閱讀器端可以進行分組解碼。由于映射數(shù)據(jù)具有清晰可識別的特點,因此在解碼過程中可以準確定位碰撞信息,不需進行下一輪模糊查詢,從而避免產(chǎn)生空閑時隙。

該算法對標簽進行雙重分組,從橫向按標簽識別碼位數(shù)進行分組,每3位歸為1組;從縱向每組根據(jù)識別碼特征再進行分組,同組的3個識別碼異或運算(運算符號為⊙)結(jié)果為1則歸為一個小組,同或運算(運算符號為⊕)結(jié)果為1則歸為另一個小組,并為該組附加組標簽G[G∈(0,1)],具體分組情況如圖2所示。TagA與TagB代表兩個長度為n的RFID標簽,按照識別碼編號表示為P1P2…Pn,首先從橫向分組:將P1P2P3作為第1組識別碼,將P4P5P6作為第2組識別碼,以此類推;其次從縱向分組:TagA中第1組識別碼有P1⊕P2=P3,則P1P2P3組為G=0組,TagB中第1組P1⊙P2=P3,則該組為G=1組;P4P5P6的情況與之相反。按照雙重分組規(guī)則不斷進行分組直到最后3位識別碼分組完畢。

圖2 雙重分組示意圖Fig.2 Schematic diagram of double grouping

在雙重分組的基礎(chǔ)上,DGMQT算法的映射數(shù)據(jù)根據(jù)組標簽和識別碼特征按照對位映射規(guī)則進行定制。對位映射規(guī)則為:3位識別碼表示為XXX,對位映射表示為GXXX或者GTTT(其中G為組標簽號,TTT是由XXX按位取反得到的識別碼)。例如,對于G=0組識別碼中含有識別碼1的標簽(011、101、110),映射數(shù)據(jù)取首位置組標簽號0,后接識別碼按位取反(100、010、001),不含1的標簽(000)則首位置1接識別碼(1000);G=1組識別碼中含有0的標簽(001、010、100),其映射數(shù)據(jù)取首位置組標簽號1,后接識別碼為001、010、100;不含0的標簽(111),則首位置1后接的識別碼按位取反(1000),具體識別碼分組和映射關(guān)系如表2所示。例如,有6位標簽識別碼為000101,則其按對位映射規(guī)則后的映射數(shù)據(jù)為10000010。

表2 識別碼分組和映射關(guān)系Table 2 Identification code grouping and mappingrelationship

經(jīng)過對位映射后,3位識別碼對應(yīng)4位映射數(shù)據(jù),在同組內(nèi)可實現(xiàn)準確識別碰撞信息,不同組間可通過組標簽號進行區(qū)分,從而完全避免產(chǎn)生空閑時隙,最終傳輸給閱讀器的數(shù)據(jù)為1位組標簽號G加上4位映射數(shù)據(jù)GXXX或者GTTT。

在閱讀器端利用對位映射機制反解出碰撞信息可得到準確的查詢碼,不同組碰撞信息將分開解碼并進入不同堆棧,為下一時隙查詢做準備。例如,某時隙響應(yīng)的識別碼有000、011、010和100,則向閱讀器返回的數(shù)據(jù)為0/1000,0/0100,1/0010和1/0100,閱讀器中收到的G0組數(shù)據(jù)為XX00,G1組數(shù)據(jù)為0XX0,解析后查詢碼000和011進入G0查詢堆棧,查詢碼010與100進入G1堆棧。

2.2 相關(guān)指令

DGMQT算法中使用的具體指令如下:

1)REQ(*):閱讀器請求命令,用于在初始階段完成第1次查詢工作,閱讀器發(fā)送REQ(*)命令,工作范圍內(nèi)的全部標簽將第1組的組標簽和對位映射碼同時發(fā)回閱讀器。

2)REQ(pre):閱讀器請求命令,閱讀器發(fā)出此指令,待識別標簽中與該查詢前綴相同的標簽被激活,并在同一時隙返回該查詢前綴下一組識別碼相應(yīng)的組標簽號和對位映射碼。

3)Decode:閱讀器對標簽反饋的映射碰撞信息進行分析,得出該組標簽所包含的查詢前綴pre。

4)PUSH(pre):閱讀器操作命令,pre為當前需要壓棧的查詢前綴,發(fā)出命令后,閱讀器將此查詢前綴壓入堆棧。

5)POP(pre):閱讀器操作命令,pre默認為當前查詢堆棧棧頂?shù)牟樵兦熬Y,發(fā)出命令后,閱讀器將此查詢前綴彈出堆棧。

6)READ:閱讀器讀取命令,處于激活狀態(tài)的唯一標簽收到命令后將識別碼發(fā)回閱讀器。

2.3 算法流程

DGMQT算法流程如圖3所示。

圖3 DGMQT算法流程Fig.3 DGMQT algorithm flow path

DGMQT算法包括以下4步:

1)閱讀器將組標簽G0和G1初始化為空并發(fā)出命令REQ(*)后,工作范圍內(nèi)全部標簽響應(yīng)并將自身識別碼中第1組的組標簽和對位映射碼發(fā)送返回到閱讀器。

2)閱讀器確認返回標簽中映射信息碰撞情況,如果未發(fā)生碰撞,則發(fā)送READ讀取命令完成標簽數(shù)據(jù)讀取操作,然后直接執(zhí)行第4步;如果發(fā)生碰撞,則執(zhí)行第3步。

3)閱讀器對組標簽G=0的對位映射碼進行Decode操作,將碰撞的映射碼進行解碼,對解碼后得到的查詢碼進行PUSH(pre)操作入G0棧;閱讀器對組標簽G=1的映射碼執(zhí)行相同操作,對解碼后得到的查詢碼進行PUSH(pre)操作入G1棧。若此時隙沒有返回組標簽G=0(或G=1)的映射碼,則忽略與其對應(yīng)的操作。

4)判斷查詢堆棧G0是否為空,如果不為空,執(zhí)行POP(pre)操作,彈出棧頂查詢前綴,閱讀器進行REQ(pre)操作,請求相同前綴的標簽發(fā)送組標簽和對位映射碼,然后執(zhí)行第2步;若堆棧G0為空則對堆棧G1進行上述操作;若堆棧G1也為空,則識別完成,識別過程終止。

2.4 算法識別示例

假設(shè)有8個待識別標簽,其識別碼分別為A(000101)、B(000001)、C(101000)、D(101011)、E(101010)、F(001110)、G(111011)、H(111110)。DGMQT算法中標簽返回的組標簽和對位映射碼如表3所示,閱讀器查詢和標簽響應(yīng)過程如表4所示,對應(yīng)的查詢樹結(jié)構(gòu)如圖4所示。

表3 DGMQT算法中標簽返回的組標簽和對位映射碼Table 3 Group labels and pair mapping codes returned by labels in DGMQT algorithm

表4 DGMQT算法中閱讀器查詢和標簽響應(yīng)過程Table 4 Reader query and tag response process in DGMQT algorithm

圖4 DGMQT算法樹結(jié)構(gòu)示意圖Fig.4 Schematic diagram of DGMQT algorithm tree structure

3 算法性能分析

(1)

空閑時隙的概率為:

(2)

非空閑時隙的概率為:

(3)

第l層空閑時隙數(shù)為:

(4)

第l層非空閑時隙數(shù)為:

(5)

總的空閑時隙數(shù)為:

(6)

總的非空閑時隙數(shù)為:

(7)

DGMQT算法中對位映射編碼使識別過程中避免產(chǎn)生空閑時隙,且分組方式相當于大量減少搜索所用的層數(shù),即在最差情況下(即待識別標簽的每一位識別碼都進行了碰撞)DGMQT算法識別的時隙數(shù)Tn≈Nnc,因而以Nnc作為DGMQT算法的識別時隙數(shù)來進行識別時隙數(shù)、系統(tǒng)效率、時隙利用率和通信復(fù)雜度的分析。

系統(tǒng)識別效率為:

(8)

其中,Tn為總時隙數(shù)。

時隙利用率為:

(9)

通信復(fù)雜度定義位標簽成功被閱讀器讀取所傳輸?shù)目偙忍財?shù)為:

(10)

其中,Fn為DGMQT算法成功識別n個標簽所需要的通信復(fù)雜度,Li為后續(xù)識別過程中每次查詢的傳輸位數(shù),L為第1次查詢的傳輸位數(shù)。

4 仿真與結(jié)果分析

RFID防碰撞系統(tǒng)應(yīng)用算法的性能指標包括查詢時隙數(shù)、系統(tǒng)效率、時隙利用率和通信復(fù)雜度。使用Matlab_2018b平臺對DGMQT算法、QT算法、八叉樹算法、A4PQT算法、GBAQT算法進行仿真實驗,標簽數(shù)最大為1 000,標簽識別碼的位數(shù)為96 bit,分別對上述算法的總時隙數(shù)、系統(tǒng)效率、時隙利用率和通信復(fù)雜度進行對比分析。

由圖5可以看出,隨著標簽數(shù)的增加,各種算法所用的總時隙數(shù)均逐漸增加;和八叉樹算法、QT算法相比,DGMQT算法所用的總時隙數(shù)增幅更小;當標簽數(shù)為1 000時,DGMQT算法所用總時隙數(shù)為1 388,比八叉樹算法、QT算法所用的總時隙數(shù)分別減少64%、50.4%;和A4PQT算法、GBAQT算法相比,DGMQT算法所用的總時隙數(shù)增幅較小,隨著標簽數(shù)的增加,GBAQT算法的優(yōu)勢更明顯。這是因為GBAQT算法中的雙重分組提高了碰撞信息處理效率,而對位映射使該算法可通過避免產(chǎn)生空閑時隙減小總時隙數(shù)。

圖5 不同算法所用總時隙數(shù)Fig.5 Total number of time slots of different algorithms

由圖6可以看出,DGMQT算法的系統(tǒng)效率保持在0.7以上,遠高于其他算法的系統(tǒng)效率。

圖6 不同算法的系統(tǒng)效率Fig.6 System efficiency of different algorithms

由圖7可以看出,DGMQT算法的時隙利用率最大達到1.0,其他算法的時隙利用率由大到小依次為GBAQT算法>QT算法>A4PQT算法>八叉樹算法。這是因為DGMQT算法避免產(chǎn)生空閑時隙,所以識別過程中產(chǎn)生的時隙均為碰撞時隙,而通過碰撞時隙可有效地得到碰撞位置信息,得到的時隙利用率較高。

圖7 不同算法的時隙利用率Fig.7 Slot utilization of different algorithms

由圖8可以看出,QT算法和八叉樹算法的通信復(fù)雜度較高;A4PQT算法采用了剔除分支策略,因而其通信復(fù)雜度有所下降;GBAQT算法和DGMQT算法的分組思想使其通信復(fù)雜度較低,其中DGMQT算法的通信復(fù)雜度最低,識別1個標簽僅需300 bit。

圖8 不同算法的通信復(fù)雜度Fig.8 Communication complexity of different algorithms

5 結(jié)束語

本文基于查詢樹的樹形結(jié)構(gòu),結(jié)合映射機制設(shè)計對位映射方案,提出一種基于雙重分組和對位映射機制的查詢樹算法。采用雙重分組的方式將標簽識別碼分為兩組,每一組賦予不同的組標簽,設(shè)計對位映射的規(guī)則,將識別碼數(shù)據(jù)映射為識別度極高的映射數(shù)據(jù),通過對識別碼細粒度的劃分消除識別過程中的空閑時隙,從而提升算法識別效率。仿真結(jié)果表明,本文算法可以消除查詢空閑時隙,具有較好的系統(tǒng)效率、時隙利用率和良好的通信復(fù)雜度,在多標簽的情況下其各項性能顯著優(yōu)于其他算法。下一步將使用硬件技術(shù)對閱讀器端與天線端進行更細致地分組,以提升系統(tǒng)的性能。