一種基于分組的混合查詢防碰撞算法

董昌+熊衛(wèi)華

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

關鍵詞：射頻識別；防碰撞；標簽預處理；異或分組；改進HQT算法

中圖分類號：TP301.6 文獻標識碼：A 文章編號：2095-1302（2017）02-00-04

0 引 言

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

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

（1）基于TDMA思想的非確定性ALOHA算法。該算法又分為純ALOHA算法（存在嚴重的錯判問題）、時隙ALOHA算法（將ALOHA算法中時間分成多個離散的時隙）、幀時隙ALOHA算法（將多個時隙組成一幀，標簽在每個幀內隨機選擇一個時隙）等算法。

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

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

1 基本的確定性算法

1.1 曼切斯特編碼

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

1.2 查詢樹算法

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

1.3 HQT算法

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

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

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

（3）“1”的個數(shù)與slotn相同時電子標簽才響應；

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

閱讀器端口進行的算法如下：

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

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

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

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

2 改進算法的具體描述

2.1 算法改進思想

通過分析QT算法和HQT算法得出，在QT算法過程中會產生大量無用的前綴，HQT算法會產生大量的空閑時隙。

分組混合算法約定：

（1）在閱讀器范圍內每個電子標簽的ID唯一。

（2） 每個電子標簽應含有一個響應計數(shù)器C和2個寄存器，分別為R和G。C用來存儲等待的時隙數(shù)，R和G用于保存分組標號。

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

本文先將標簽所有的碰撞位提取出來組成一個新的標簽NEW ID，根據(jù)新標簽中“1”的奇偶個數(shù)進行分組。定義標簽的長度為n，任意連續(xù)的3個標簽位為Wn、Wn+1、Wn+2，定義符號☉為異或運算符，如果符合式（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四種形式。此時若有兩位碰撞位則可以直接識別出標簽，若有3位碰撞位則將前2位用十進制表示，并分別存入延遲寄存器C中。

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

2.2.1 標簽端

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

（2）接收到閱讀器識別出來的碰撞位，標簽將碰撞位按順序組成一個新的標簽ID；

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

（4）對標簽的前3位進行異或分組處理，將相應的標簽計數(shù)器G置“0”或“1”；

（5）若沒響應則為空時隙，查看堆棧Q是否為空，否則返回標簽最高碰撞位之后的信息給閱讀器。

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

（7）當C=slot時響應；

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

2.2.2 閱讀器端

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

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

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

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

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

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

（5）閱讀器發(fā)送Request（Q，G）令分組號相同的標簽都響應，同時清空標簽中G的值；

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

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

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

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

（10）對同個slot時隙的碰撞標簽根據(jù)連續(xù)的前3位轉到步驟（5）；

（11）識別該標簽。

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

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

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

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

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

（4）以第三步中R=0的標簽前3位進行異或分組，相應的置內部存儲器G為0、1，此時G={1，0}。標簽的異或分組見表3所列；

（5）經分析R=0且G=0標簽的前2位可知，C分別為3、2、2，可直接識別出110101；

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

（7）符合前綴的標簽進行異或分組后在同一組且有2個碰撞位可以直接識別；

（8）同（5），對R=0，G=1的標簽的前2位分析可直接識別出所有的標簽；

（9）對R=1，G=0和R=1，G=1的組經（5）～（8）可以正確識別；

（10）堆棧隊列Q為空，標簽識別完后結束。

算法流程如圖3所示。

3 算法仿真結果及分析

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

使用Matlab軟件對其仿真。先假設標簽均在可讀取范圍內，其ID長度為96 b且隨機生成一定的標簽。設系統(tǒng)的通信速率為100 b/s，標簽響應時長和單一時隙為20 μs。我們在實驗中對QT、HQT和分組混合算法進行比較。

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

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

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

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

4 結 語

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

參考文獻

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

[2]郭建華，楊海東，鄧飛其.基于免疫網絡的RFID入侵檢測模型研究[J].計算機應用，2008，28（10）：2481-2484.

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

[4]姜麗芬，盧桂章，辛運帷.射頻識別系統(tǒng)中的防碰撞算法研究[J].計算機工程與應用，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].射頻世界，2007，23（5）：27-30.

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

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

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

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