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

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

0 概述

物聯(lián)網(wǎng)是遵循既定規(guī)定使用射頻識別(Radio Frequency Identification,RFID)等信息傳感儀器,在任意物品與互聯(lián)網(wǎng)之間建立聯(lián)系進(jì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)主要由閱讀器、識別標(biāo)簽和處理器構(gòu)成[2]。如果多個標(biāo)簽同時處于同一閱讀器的識別范圍,當(dāng)該閱讀器發(fā)送識別請求時,會出現(xiàn)多個標(biāo)簽同時響應(yīng)該閱讀器的現(xiàn)象,這種現(xiàn)象稱為標(biāo)簽碰撞[3]。

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

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

1 相關(guān)工作

1.1 比特追蹤技術(shù)

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

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

1.2 查詢樹算法

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

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

1.3 基于查詢樹算法研究

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

表1 未識別標(biāo)簽分組情況Table 1 Grouping situation of unrecognized labels

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

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

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

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

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

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

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

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

2.1 設(shè)計思想

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

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

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

在雙重分組的基礎(chǔ)上,DGMQT算法的映射數(shù)據(jù)根據(jù)組標(biāo)簽和識別碼特征按照對位映射規(guī)則進(jìn)行定制。對位映射規(guī)則為:3位識別碼表示為XXX,對位映射表示為GXXX或者GTTT(其中G為組標(biāo)簽號,TTT是由XXX按位取反得到的識別碼)。例如,對于G=0組識別碼中含有識別碼1的標(biāo)簽(011、101、110),映射數(shù)據(jù)取首位置組標(biāo)簽號0,后接識別碼按位取反(100、010、001),不含1的標(biāo)簽(000)則首位置1接識別碼(1000);G=1組識別碼中含有0的標(biāo)簽(001、010、100),其映射數(shù)據(jù)取首位置組標(biāo)簽號1,后接識別碼為001、010、100;不含0的標(biāo)簽(111),則首位置1后接的識別碼按位取反(1000),具體識別碼分組和映射關(guān)系如表2所示。例如,有6位標(biāo)簽識別碼為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)準(zhǔn)確識別碰撞信息,不同組間可通過組標(biāo)簽號進(jìn)行區(qū)分,從而完全避免產(chǎn)生空閑時隙,最終傳輸給閱讀器的數(shù)據(jù)為1位組標(biāo)簽號G加上4位映射數(shù)據(jù)GXXX或者GTTT。

在閱讀器端利用對位映射機(jī)制反解出碰撞信息可得到準(zhǔn)確的查詢碼,不同組碰撞信息將分開解碼并進(jìn)入不同堆棧,為下一時隙查詢做準(zhǔn)備。例如,某時隙響應(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進(jìn)入G0查詢堆棧,查詢碼010與100進(jìn)入G1堆棧。

2.2 相關(guān)指令

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

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

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

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

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

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

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

2.3 算法流程

DGMQT算法流程如圖3所示。

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

DGMQT算法包括以下4步:

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

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

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

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

2.4 算法識別示例

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

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

表4 DGMQT算法中閱讀器查詢和標(biāo)簽響應(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)生空閑時隙,且分組方式相當(dāng)于大量減少搜索所用的層數(shù),即在最差情況下(即待識別標(biāo)簽的每一位識別碼都進(jìn)行了碰撞)DGMQT算法識別的時隙數(shù)Tn≈Nnc,因而以Nnc作為DGMQT算法的識別時隙數(shù)來進(jìn)行識別時隙數(shù)、系統(tǒng)效率、時隙利用率和通信復(fù)雜度的分析。

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

(8)

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

時隙利用率為:

(9)

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

(10)

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

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

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

由圖5可以看出,隨著標(biāo)簽數(shù)的增加,各種算法所用的總時隙數(shù)均逐漸增加;和八叉樹算法、QT算法相比,DGMQT算法所用的總時隙數(shù)增幅更小;當(dāng)標(biāo)簽數(shù)為1 000時,DGMQT算法所用總時隙數(shù)為1 388,比八叉樹算法、QT算法所用的總時隙數(shù)分別減少64%、50.4%;和A4PQT算法、GBAQT算法相比,DGMQT算法所用的總時隙數(shù)增幅較小,隨著標(biāo)簽數(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以上,遠(yuǎn)高于其他算法的系統(tǒng)效率。

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

由圖7可以看出,DGMQT算法的時隙利用率最大達(dá)到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個標(biāo)簽僅需300 bit。

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

5 結(jié)束語

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