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

董昌+熊衛華

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

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

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

0 引 言

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

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

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

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

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

1 基本的確定性算法

1.1 曼切斯特編碼

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

1.2 查詢樹算法

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

1.3 HQT算法

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

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

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

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

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

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

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

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

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

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

2 改進算法的具體描述

2.1 算法改進思想

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

分組混合算法約定：

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

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

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

本文先將標簽所有的碰撞位提取出來組成一個新的標簽NEW ID，根據新標簽中“1”的奇偶個數進行分組。定義標簽的長度為n，任意連續的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）接收“#”，所有的電子標簽都發送自己的ID；

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

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

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

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

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

（7）當C=slot時響應；

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

2.2.2 閱讀器端

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

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

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

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

（3）發送隊首前綴Prefix給標簽；

（4）根據標簽的前3位發送異或分組命令Request（G）；

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

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

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

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

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

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

（11）識別該標簽。

標簽識別最后只可能出現碰撞位為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）閱讀器發送Request（#），此時Q={0、1，G}，閱讀器統計碰撞位并向標簽發送碰撞位信息，標簽內部提取碰撞位，組成一個新的標簽；

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

（3）對將要識別的16個標簽進行第一次分組，統計“1”的奇偶個數。奇數時R=1，偶數時R=0，計入標簽內部計數器。標簽的奇偶分組見表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標簽發生碰撞，101作為前綴發送給閱讀器；

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

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

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

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

算法流程如圖3所示。

3 算法仿真結果及分析

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

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

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

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

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

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

4 結 語

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

參考文獻

[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）核心技術與典型應用開發案例[M].北京：人民郵電出版社，2008.

[4]姜麗芬，盧桂章，辛運帷.射頻識別系統中的防碰撞算法研究[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系統中的跳躍式類二進制搜索法[J].射頻世界，2007，23（5）：27-30.

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

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

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

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