董昌+熊衛(wèi)華

摘 要：傳統(tǒng)的射頻識(shí)別防碰撞算法查詢次數(shù)多、數(shù)據(jù)傳輸量大，而一般的混合查詢樹算法會(huì)產(chǎn)生大量的查詢前綴和空閑時(shí)隙。因此，文中針對(duì)這些問題提出了基于分組的混合查詢樹法。該方法先對(duì)標(biāo)簽預(yù)處理組成一個(gè)新標(biāo)簽，然后將標(biāo)簽二次分組與改進(jìn)的HQT算法結(jié)合使用，通過不斷使用異或分組結(jié)合碰撞位前2位組合信息對(duì)標(biāo)簽進(jìn)行處理。實(shí)驗(yàn)表明，此舉減少了標(biāo)簽的查詢前綴、空閑時(shí)隙和傳輸數(shù)據(jù)，從而提高了系統(tǒng)的工作效率。

關(guān)鍵詞：射頻識(shí)別；防碰撞；標(biāo)簽預(yù)處理；異或分組；改進(jìn)HQT算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2017）02-00-04

0 引 言

無線射頻識(shí)別技術(shù)（Radio Frequency Identification，RFID）[1]作為物聯(lián)網(wǎng)應(yīng)用系統(tǒng)的核心技術(shù)，對(duì)推動(dòng)物聯(lián)網(wǎng)的發(fā)展起著不可估量的作用。它利用射頻信號(hào)的電磁（電感）耦合原理進(jìn)行目標(biāo)自動(dòng)識(shí)別，已廣泛應(yīng)用于物流、資產(chǎn)管理、軍事、交通以及醫(yī)療等領(lǐng)域[2]。RFID系統(tǒng)主要由電子閱讀器、標(biāo)簽、RFID應(yīng)用系統(tǒng)3部分組成。閱讀器主要負(fù)責(zé)與電子標(biāo)簽的雙向通信，同時(shí)還會(huì)受到主機(jī)系統(tǒng)的控制。電子標(biāo)簽是射頻識(shí)別系統(tǒng)真正的數(shù)據(jù)載體。應(yīng)用系統(tǒng)是RFID的系統(tǒng)軟件或者服務(wù)程序，也是整個(gè)RFID系統(tǒng)的后臺(tái)系統(tǒng)[3]。在RFID中，數(shù)據(jù)的完整性和正確性決定了整個(gè)系統(tǒng)是否可行。但應(yīng)用上時(shí)常面臨多個(gè)標(biāo)簽、多個(gè)閱讀器相互干擾的問題，這使得閱讀器不能正確或者完全識(shí)別閱讀范圍內(nèi)的所有電子標(biāo)簽。因此可通過改進(jìn)信道傳輸?shù)臄?shù)據(jù)算法來解決此問題，而防碰撞算法也由此而來。

如今最基本的4種通信防碰撞算法有空分多址（SDMA）法、頻分多址（FDMA）法、碼分多址（CDMA）法和時(shí)分多址（TDMA）法。在RFID中主流的防碰撞算法主要分為以下2大類：

（1）基于TDMA思想的非確定性ALOHA算法。該算法又分為純ALOHA算法（存在嚴(yán)重的錯(cuò)判問題）、時(shí)隙ALOHA算法（將ALOHA算法中時(shí)間分成多個(gè)離散的時(shí)隙）、幀時(shí)隙ALOHA算法（將多個(gè)時(shí)隙組成一幀，標(biāo)簽在每個(gè)幀內(nèi)隨機(jī)選擇一個(gè)時(shí)隙）等算法。

（2）基于輪詢的按照樹模型搜索確定性算法[4]。該方法包括二進(jìn)制防碰撞算法、查詢樹（Query Tree，QT）算法[5-7]等多種基于樹的圖形算法。

當(dāng)存在大量碰撞標(biāo)簽，并在碰撞位較多時(shí)直接使用QT算法，但該算法的查詢前綴較多且存在大量的空閑時(shí)隙。而一般混合算法的查詢次數(shù)過多[8]。本文采用分組思想結(jié)合HQT算法提出了一種基于分組的混合查詢樹算法，以減少大量的查詢前綴并在一定程度上減少空閑時(shí)隙和數(shù)據(jù)的查詢量，大大提高了工作效率。

1 基本的確定性算法

1.1 曼切斯特編碼

編碼即用不同形式的碼型來表示“1”和“0”。RFID系統(tǒng)常用的編碼方式有差分雙相（DBP）碼、密勒（Miller）碼、曼切斯特（Manchester）碼等。其中，曼切斯特碼是最常用的編碼方式，它采用電平的上升、下降沿來表示邏輯“0”和“1”。從低電平到高電平的上升沿跳變表示邏輯“0”，反之表示邏輯“1”。當(dāng)閱讀器同時(shí)接收到不同的邏輯“1”和“0”時(shí)，則無法識(shí)別該位置的信息產(chǎn)生碰撞，而曼切斯特碼能夠以此確定該位是碰撞位。因?yàn)樾枰獪?zhǔn)確檢測(cè)出碰撞位，所以采用曼切斯特編碼方式。分別有2個(gè)標(biāo)簽Tag1（10010）和Tag2（00111）處于閱讀器的識(shí)別范圍內(nèi)，當(dāng)Tag1、Tag2同時(shí)發(fā)送ID信息給閱讀器時(shí)，閱讀器接收到的信號(hào)是 “X0X1X”（X表示碰撞位）。圖1所示為上述標(biāo)簽的曼切斯特編碼響應(yīng)過程。

1.2 查詢樹算法

查詢樹（Query Tree，QT）算法是一種常見典型的樹結(jié)構(gòu)算法。在算法中需要開辟堆棧保存閱讀器的數(shù)據(jù)。開辟一個(gè)棧data用來保存閱讀器的查詢前綴，每次閱讀器都將長(zhǎng)度為K的前綴數(shù)據(jù)發(fā)送給標(biāo)簽，n位標(biāo)簽的前K位與前綴相同則響應(yīng)，標(biāo)簽將剩下的n-k位發(fā)送給閱讀器。閱讀器接收到的標(biāo)簽繼續(xù)碰撞時(shí)后面用二進(jìn)制搜索查詢法進(jìn)行識(shí)別。例如有四個(gè)標(biāo)簽分別為0010、1001、0101、0110，圖2所示為QT算法的查詢樹結(jié)構(gòu)。

1.3 HQT算法

由于QT算法是在二進(jìn)制算法的基礎(chǔ)上進(jìn)行改進(jìn)，而且還要擴(kuò)展前綴，因此會(huì)產(chǎn)生一些沒用的前綴信號(hào)，增加了系統(tǒng)的通信量，延長(zhǎng)了通訊時(shí)間。為此提出了一種HQT算法，它由原來的擴(kuò)展一位增加到三位，同時(shí)引入了時(shí)隙延長(zhǎng)機(jī)制。當(dāng)符合前綴的電子標(biāo)簽并不立即響應(yīng)時(shí)，通過計(jì)算標(biāo)簽前綴后三位中“1”的個(gè)數(shù)來決定延長(zhǎng)的時(shí)隙數(shù)[9，10]。先設(shè)電子標(biāo)簽的ID長(zhǎng)度為n，用P表示首位碰撞位，K表示發(fā)送前綴的位數(shù)，用slotn表示時(shí)隙數(shù)。那么標(biāo)簽的計(jì)算思想為：

（1）先用QT算法判斷閱讀器發(fā)送的前綴與標(biāo)簽ID的前k位是否匹配，若不同不響應(yīng)，相同則進(jìn)行下一步：

（2）計(jì)算p到p+2位中“1”的個(gè)數(shù)；

（3）“1”的個(gè)數(shù)與slotn相同時(shí)電子標(biāo)簽才響應(yīng)；

（4）將查詢前綴后所有的n-p+1位信息發(fā)送給閱讀器。

閱讀器端口進(jìn)行的算法如下：

（1）閱讀器將查詢前綴K發(fā)給標(biāo)簽并實(shí)時(shí)更新查詢棧；

（2）通過接收標(biāo)簽發(fā)送的最高碰撞位的后三位判斷slotn是否碰撞，若無則進(jìn)行（4）；

（3）上一步有碰撞則在上次查詢前綴的基礎(chǔ)上擴(kuò)充一位 “0”或“1”添入查詢棧data的末尾，返回（2）；

（4）在同一個(gè)slotn內(nèi)若無碰撞發(fā)生，則說明只有一個(gè)標(biāo)簽，可以直接識(shí)別。

2 改進(jìn)算法的具體描述

2.1 算法改進(jìn)思想

通過分析QT算法和HQT算法得出，在QT算法過程中會(huì)產(chǎn)生大量無用的前綴，HQT算法會(huì)產(chǎn)生大量的空閑時(shí)隙。

分組混合算法約定：

（1）在閱讀器范圍內(nèi)每個(gè)電子標(biāo)簽的ID唯一。

（2） 每個(gè)電子標(biāo)簽應(yīng)含有一個(gè)響應(yīng)計(jì)數(shù)器C和2個(gè)寄存器，分別為R和G。C用來存儲(chǔ)等待的時(shí)隙數(shù)，R和G用于保存分組標(biāo)號(hào)。

（3）每個(gè)電子標(biāo)簽中都有一個(gè)靜默計(jì)數(shù)器N，N=0時(shí)處于激活狀態(tài)，接收閱讀器的信號(hào)；N>0時(shí)為失活狀態(tài)，對(duì)閱讀器不反映；N<0時(shí)處于無聲狀態(tài)。

本文先將標(biāo)簽所有的碰撞位提取出來組成一個(gè)新的標(biāo)簽NEW ID，根據(jù)新標(biāo)簽中“1”的奇偶個(gè)數(shù)進(jìn)行分組。定義標(biāo)簽的長(zhǎng)度為n，任意連續(xù)的3個(gè)標(biāo)簽位為Wn、Wn+1、Wn+2，定義符號(hào)☉為異或運(yùn)算符，如果符合式（1），則Wn、Wn+1、Wn+2為第0組，表示G=0；如果符合式（2），則Wn、Wn+1、Wn+2為第1組，表示G=1。若G=0，從Wn到Wn+2最多有000、011、101、110四種形式。此時(shí)若有兩位碰撞位則可以直接識(shí)別出標(biāo)簽，若有3位碰撞位則將前2位用十進(jìn)制表示，并分別存入延遲寄存器C中。

2.2 分組混合算法的基本步驟

2.2.1 標(biāo)簽端

（1）接收“#”，所有的電子標(biāo)簽都發(fā)送自己的ID；

（2）接收到閱讀器識(shí)別出來的碰撞位，標(biāo)簽將碰撞位按順序組成一個(gè)新的標(biāo)簽ID；

（3）接收前綴，根據(jù)閱讀器第一次發(fā)送“0”與標(biāo)簽中R是否相等響應(yīng)可知，若不等，則標(biāo)簽靜默，此時(shí)N=1， 直到閱讀器發(fā)送“1”才被激活，否則繼續(xù)；

（4）對(duì)標(biāo)簽的前3位進(jìn)行異或分組處理，將相應(yīng)的標(biāo)簽計(jì)數(shù)器G置“0”或“1”；

（5）若沒響應(yīng)則為空時(shí)隙，查看堆棧Q是否為空，否則返回標(biāo)簽最高碰撞位之后的信息給閱讀器。

（6）標(biāo)簽的最高碰撞位開始的2位用十進(jìn)制表示，存入計(jì)數(shù)器C中。這里C=0、1、2、3、4；

（7）當(dāng)C=slot時(shí)響應(yīng)；

（8）將碰撞信息（K+1）到n位發(fā)送給閱讀器。

2.2.2 閱讀器端

在問詢階段，從查詢隊(duì)列Q中取隊(duì)首元素，發(fā)送給所有的標(biāo)簽。查詢隊(duì)列Q的初始值為{#、0、1}，且得出的數(shù)值都按次序置于“1”之前，直到發(fā)送“1”之后Q的值才添加到隊(duì)尾，每次發(fā)送查詢碼后都將其刪除。Request（Q，G）則表示Q為查詢前綴，G為組號(hào)的標(biāo)簽處于激活狀態(tài)。

閱讀器端的具體工作流程如下：

（1）閱讀器發(fā)送“#”，令所有標(biāo)簽都響應(yīng)；

（2）閱讀器的堆棧隊(duì)列Q不為空時(shí)，讀取并刪除Q中的隊(duì)首元素；

（3）發(fā)送隊(duì)首前綴Prefix給標(biāo)簽；

（4）根據(jù)標(biāo)簽的前3位發(fā)送異或分組命令Request（G）；

（5）閱讀器發(fā)送Request（Q，G）令分組號(hào)相同的標(biāo)簽都響應(yīng)，同時(shí)清空標(biāo)簽中G的值；

（6）若前3位中有兩個(gè)碰撞位，則根據(jù)異或分組原理可以直接識(shí)別前3位，將識(shí)別出的前3位作為前綴Prefix放入Q中置于隊(duì)尾。轉(zhuǎn)向步驟（5）；

（7）當(dāng)前slot與收到的前2位信息是否有碰撞發(fā)生擴(kuò)展，查詢前綴Q，沒有則跳轉(zhuǎn)到（9），否則繼續(xù)；

（8）查詢閱讀器是否發(fā)送“1”，有則下次將前綴Prefix放于隊(duì)尾，否則置于“1”前；

（9）繼續(xù)掃描收到的信息，沒有發(fā)生碰撞則轉(zhuǎn)移到（11），否則繼續(xù)；

（10）對(duì)同個(gè)slot時(shí)隙的碰撞標(biāo)簽根據(jù)連續(xù)的前3位轉(zhuǎn)到步驟（5）；

（11）識(shí)別該標(biāo)簽。

標(biāo)簽識(shí)別最后只可能出現(xiàn)碰撞位為2或3的情況，2位則直接識(shí)別，3位則通過再次異或分組后識(shí)別。

假設(shè)有16個(gè)8位的待識(shí)別標(biāo)簽tag1～tag16，依次為10101010、00110100、10011110、00100010、10011100、00010010、00101100、10110110、10000010、00001000、10010110、10100110、00111110、00000100、00000010、00110010。

（1）閱讀器發(fā)送Request（#），此時(shí)Q={0、1，G}，閱讀器統(tǒng)計(jì)碰撞位并向標(biāo)簽發(fā)送碰撞位信息，標(biāo)簽內(nèi)部提取碰撞位，組成一個(gè)新的標(biāo)簽；

（2）閱讀器返回的碰撞位信息為X0XXXXX0，則組成的新標(biāo)簽見表1所列。

（3）對(duì)將要識(shí)別的16個(gè)標(biāo)簽進(jìn)行第一次分組，統(tǒng)計(jì)“1”的奇偶個(gè)數(shù)。奇數(shù)時(shí)R=1，偶數(shù)時(shí)R=0，計(jì)入標(biāo)簽內(nèi)部計(jì)數(shù)器。標(biāo)簽的奇偶分組見表2所列；

（4）以第三步中R=0的標(biāo)簽前3位進(jìn)行異或分組，相應(yīng)的置內(nèi)部存儲(chǔ)器G為0、1，此時(shí)G={1，0}。標(biāo)簽的異或分組見表3所列；

（5）經(jīng)分析R=0且G=0標(biāo)簽的前2位可知，C分別為3、2、2，可直接識(shí)別出110101；

（6）被識(shí)別標(biāo)簽靜默，101110、101011標(biāo)簽發(fā)生碰撞，101作為前綴發(fā)送給閱讀器；

（7）符合前綴的標(biāo)簽進(jìn)行異或分組后在同一組且有2個(gè)碰撞位可以直接識(shí)別；

（8）同（5），對(duì)R=0，G=1的標(biāo)簽的前2位分析可直接識(shí)別出所有的標(biāo)簽；

（9）對(duì)R=1，G=0和R=1，G=1的組經(jīng)（5）～（8）可以正確識(shí)別；

（10）堆棧隊(duì)列Q為空，標(biāo)簽識(shí)別完后結(jié)束。

算法流程如圖3所示。

3 算法仿真結(jié)果及分析

上述算法通過分組后發(fā)送組號(hào)作為每一輪的開始，在本次識(shí)別過程中，閱讀器的次數(shù)為堆棧Q中的查詢次數(shù)，傳輸數(shù)據(jù)量與查詢次數(shù)及識(shí)別時(shí)間成正比。一般產(chǎn)生空閑時(shí)隙也會(huì)影響識(shí)別速度。就查詢次數(shù)與識(shí)別效率進(jìn)行對(duì)比。

使用Matlab軟件對(duì)其仿真。先假設(shè)標(biāo)簽均在可讀取范圍內(nèi)，其ID長(zhǎng)度為96 b且隨機(jī)生成一定的標(biāo)簽。設(shè)系統(tǒng)的通信速率為100 b/s，標(biāo)簽響應(yīng)時(shí)長(zhǎng)和單一時(shí)隙為20 μs。我們?cè)趯?shí)驗(yàn)中對(duì)QT、HQT和分組混合算法進(jìn)行比較。

分組混合算法在每次分組識(shí)別前，先對(duì)標(biāo)簽進(jìn)行一次預(yù)處理，要求標(biāo)簽將自己的碰撞位提取組成一個(gè)新的ID。僅對(duì)此過程分析可知，會(huì)增加系統(tǒng)的數(shù)據(jù)傳輸，具體如下所示：

式中，K為增加的傳輸數(shù)據(jù)量，n為標(biāo)簽個(gè)數(shù)，l為標(biāo)簽長(zhǎng)度。只有標(biāo)簽每位都發(fā)生碰撞時(shí)等號(hào)才會(huì)成立。但對(duì)整個(gè)識(shí)別過程來說可大大減少問詢數(shù)目和碰撞數(shù)。

將由圖4所示的本文算法與QT和HQT算法所產(chǎn)生的空閑時(shí)隙進(jìn)行對(duì)比可得出，QT算法的空閑時(shí)隙為0；HQT算法在一般情況下引入的時(shí)隙數(shù)為4。而本文通過標(biāo)簽的處理可以減少空閑時(shí)隙，相比HQT算法，該算法不會(huì)隨標(biāo)簽數(shù)的增加而急劇增加空閑時(shí)隙，起到了一定的改善作用。

圖5所示為查詢前綴的個(gè)數(shù)?？梢钥闯鱿鄬?duì)于QT和HQT算法，本算法能夠大大減少查詢前綴。隨著標(biāo)簽數(shù)的增多，因QT算法沒有經(jīng)過處理，因此前綴數(shù)目隨著標(biāo)簽的增多，其長(zhǎng)度變化迅速增加。本文算法可以明顯看出前綴數(shù)增加的速度最為緩慢。

4 結(jié) 語

本文通過對(duì)QT算法標(biāo)簽、分組查詢樹算法的分析，經(jīng)過大量實(shí)驗(yàn)并仿真后，在對(duì)比QT、HQT算法的基礎(chǔ)上提出了二次分組的混合查詢樹法。本算法在最初情況下首先引入預(yù)處理以減少查詢前綴。通過第一次的奇偶分組和第二次的異或分組并通過采用“時(shí)隙延遲機(jī)制”計(jì)算碰撞位前2位化為十進(jìn)制的結(jié)果作為延時(shí)時(shí)隙。通過將異或分組和HQT算法結(jié)合可以有效減少空隙時(shí)隙。仿真結(jié)果表明，該算法在空閑時(shí)隙和查詢前綴上有了一定的改進(jìn)，提高了RFID系統(tǒng)的識(shí)別效率。

參考文獻(xiàn)

[1] Shepard S.RFID：radio frequency identification[M].New York：McGraw Hill，2005：55-61.

[2]郭建華，楊海東，鄧飛其.基于免疫網(wǎng)絡(luò)的RFID入侵檢測(cè)模型研究[J].計(jì)算機(jī)應(yīng)用，2008，28（10）：2481-2484.

[3]康東，石喜勤，李勇鵬，等.射頻識(shí)別（RFID）核心技術(shù)與典型應(yīng)用開發(fā)案例[M].北京：人民郵電出版社，2008.

[4]姜麗芬，盧桂章，辛運(yùn)帷.射頻識(shí)別系統(tǒng)中的防碰撞算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（15）：29-32.

[5] Wang T.Enhanced binary search with cut-through operation for anti-collision in RFID systems[J].IEEE Communications Letters，2006，10（4）：236-238.

[6]單承贛，張琦，焦宗東.RFID系統(tǒng)中的跳躍式類二進(jìn)制搜索法[J].射頻世界，2007，23（5）：27-30.

[7]姜武，楊恒新，張昀.一種改進(jìn)的查詢樹RFID標(biāo)簽防碰撞算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015（2）：86-89.

[8]付鈺，錢志鴻，程超，等.基于分組機(jī)制的位仲裁查詢樹防碰撞算法[J].通信學(xué)報(bào)，2016，37（1）：123-129.

[9]周清，蔡明.改進(jìn)的RFID混合查詢樹防碰撞算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（1）：209-213.

[10]曹潔，竇聰.一種改進(jìn)的混合查詢樹防碰撞算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（2）：322-326.