孔凡鳳，龍林德，朱永平

(湖南郵電職業(yè)技術學院移動通信系, 湖南 長沙410015)

基于QT算法的RFID跨層查詢反碰撞改進算法

孔凡鳳，龍林德，朱永平

(湖南郵電職業(yè)技術學院移動通信系, 湖南 長沙410015)

現有RFID系統(tǒng)的QT算法在電子標簽數量和密度增加及EPC較長時會造成查詢次數過多、碰撞次數增加、系統(tǒng)效率低等問題.針對QT算法的缺點，提出了改進型的跨層查詢算法，包括SQT算法和MQSQT算法.SQT算法通過改進QT算法將查詢電子標簽位元串方式改為跨層查詢方式，MQSQT算法通過詢問EPC字串的下2個位元值并進行異或邏輯運算，以求出包含跨層查詢所必需的字串最小集合.仿真結果表明改進型算法減少了碰撞次數，平均查詢次數有較大改善，提高了RFID系統(tǒng)的效率.

RFID; 電子標簽; 反碰撞; QT

RFID即射頻識別，是一種非接觸式的無線通信識別技術，通過射頻信號來自動識別特定目標并讀取其相關信息，具有防水、防磁、耐高溫、使用壽命長、讀取距離大、非可視穿透、電子標簽上數據可加密[1]、存儲數據容量大、存儲信息方便等優(yōu)點.因此，近年來RFID系統(tǒng)被廣泛應用于門禁系統(tǒng)、物流倉儲、交通運輸等方面[2].

RFID系統(tǒng)由閱讀器、電子標簽和天線組成.每個電子標簽都有一個唯一的電子產品代碼EPC，閱讀器通過射頻信號來識別電子標簽的EPC及標簽中其他各種有用信息.RFID系統(tǒng)常用的工作頻率包含低頻的135KHz、高頻的13.56MHz及超高頻的433MHz、860MHz～930MHz、2.45GHz.

通常，RFID系統(tǒng)閱讀器在一個時間內只能跟一個電子標簽通信.因此，RFID在識別電子標簽時可能發(fā)生各種碰撞[3]，如電子標簽-電子標簽[4]的碰撞、電子標簽-閱讀器的碰撞、閱讀器-閱讀器的碰撞.針對電子標簽-電子標簽碰撞，通常的反碰撞算法有AHOHA算法、Binary Tree算法、Query Tree查詢樹算法(簡稱QT算法)等.

1 QT 算法

QT算法是按照隊列先進先出的詢問方式進行的.其基本原理是：閱讀器廣播一個查詢字串前綴，與查詢字串前綴匹配的標簽響應閱讀器.如果發(fā)生碰撞，則在此查詢字串前綴后面分別加上一個0或者1，從而生成新的查詢字串前綴，閱讀器以此再進行查詢，依次下去[5].

如圖1所示，共有6個RFID電子標簽，其EPC分別為：000、001、100、101、110、111，閱讀器首先廣播查詢字串前綴0，由于與查詢字串前綴0相符的電子標簽EPC有000、001兩個，因而閱讀器發(fā)生了000、001兩個電子標簽的碰撞.此時在查詢字串前綴0后面分別加上一個0和1，生成00和01兩個新的查詢字串前綴，并加入查詢字串前綴隊列1后面.閱讀器再次廣播查詢字串前綴1，由于與查詢字串前綴1相符的電子標簽EPC有100、101、110、111四個，因而閱讀器發(fā)生了100、101、110、111四個電子標簽的碰撞.于是在查詢字串前綴1后面分別加上一個0和1，生成10和11兩個新的查詢字串前綴，并加入查詢字串前綴隊列11的后面.閱讀器再廣播查詢字串前綴00，又發(fā)生000、001兩個電子標簽的碰撞，此時又在查詢字串前綴00后面分別加上一個0和1，生成000和001兩個新的查詢字串前綴，并分別加入查詢字串前綴隊列11后面，閱讀器再次廣播查詢字串前綴000，依此下去[6].

圖1 QT算法詢問方式

表1為此例的查詢步驟及狀態(tài)，由表1可看出圖1的電子標簽查詢步驟數量、電子標簽空閑數量和電子標簽碰撞數量.

表1 QT算法運作流程

2 跨層查詢SQT算法

由于傳統(tǒng)QT算法僅在電子標簽數量少、電子標簽密度較小及EPC長度較短的情況下使用才能發(fā)揮較佳效率.隨著電子標簽數量、密度及EPC長度增加，將造成查詢次數和碰撞次數增多，從而使得系統(tǒng)的效率降低[7].為此，這里提出了一種改進的跳躍式查詢算法，即跨層查詢SQT算法.該算法以QT算法為基礎，改進傳統(tǒng)QT算法原有的逐層查詢方式為跨層查詢方式，以避免過多的碰撞數量.SQT算法的步驟如下：

第一步：閱讀器選擇查詢字串前綴信息，向讀取范圍內的電子標簽發(fā)出識別請求信息，并等待電子標簽的響應.

第二步：判斷電子標簽響應狀態(tài)，如果電子標簽響應發(fā)生碰撞，則跳至第三步；如果只有一個電子標簽響應，則代表該電子標簽成功識別，則跳至第四步；反之，如沒有電子標簽響應，則表示為空閑狀態(tài)，則跳至第五步.

第三步：將目前的查詢字串前綴分別與00、01、10、11合并組成新的查詢字串前綴，加入查詢字串前綴隊列中，并跳回第一步，閱讀器繼續(xù)進行識別動作，直至所有電子標簽辨識完成.

第四步：成功辨識，則進行電子標簽信息的的讀取，成功辨識的電子標簽暫時進入睡眠狀態(tài)，不進入下次競爭隊列，信息讀取完后則跳回第一步，直到電子標簽全被辨識完畢為止.

第五步：結束電子標簽的識別讀取.

仍然以圖1為例，閱讀器首先廣播查詢字串前綴0，由于電子標簽000、001同時滿足查詢條件，發(fā)生了兩個電子標簽的碰撞，于是閱讀器將下面跨層的四個查詢字串前綴000、001、010、011依次加入到查詢字串隊列1后面；同樣的，當閱讀器廣播查詢字串前綴1時，由于電子標簽100、101、110、111同時滿足新的查詢條件，發(fā)生了新的四個電子標簽的碰撞，于是閱讀器將下面跨層的四個查詢字串前綴100、101、110、111依次加入到查詢字串隊列011的后面.

下表2為圖1為例的SQT算法查詢步驟及狀態(tài)，由表2可看出圖1的電子標簽SQT算法查詢步驟數量、電子標簽空閑數量和電子標簽碰撞數量.

表2 SQT算法運作流程

對比表2和表1可知，SQT算法在碰撞次數和詢問次數上都比QT算法要少，但空閑數量增加了，會影響到RFID系統(tǒng)整體的運行效率.因此，下面將介紹一種相對于QT算法，既能減少碰撞次數和詢問次數，也能降低空閑數量的MQSQT防碰撞算法.

3 最小查詢字串集跨層MQSQT算法

MQSQT算法即利用或邏輯運算來協(xié)助過濾掉重復的查詢字串，并計算出查詢位元串信息的最小集，將求得的最小查詢字串集存入到查詢隊列里，以提升運作效率.

MQSQT算法步驟如下：

第一步：閱讀器獲取當前查詢隊列中字串信息，并發(fā)出查詢請求信息給讀取范圍內參與競爭的電子標簽，然后等待電子標簽的回應.

首先閱讀器會取出隊列中的第一筆查詢信息并發(fā)出查詢信息，然后等待電子標簽的回應信息.

第二步：判斷電子標簽回應狀態(tài).如果信息發(fā)生碰撞，則跳至第三步，若只有一個電子標簽回應即為成功識別，則跳至第五步；反之，若非以上兩個狀態(tài)即為空閑狀態(tài)，則跳至第六步.

依電子標簽的回應狀態(tài)，可將閱讀器的識別狀態(tài)分為：空閑、成功識別和碰撞三種狀態(tài).若在有效時限內沒有收到電子標簽的回應信息，表示無任何電子標簽需要傳輸信息，則為空閑狀態(tài)，閱讀器將空閑次數Idle值加1(參數Idle用以記錄系統(tǒng)的空閑次數，數值類型為整數，其起始值為0)；若僅收到一個電子標簽的回應信息即為成功識別電子標簽，閱讀器可順利讀取電子標簽中的信息并讀完信息后讓此電子標簽進入睡眠狀態(tài).

第三步：閱讀器將發(fā)生碰撞的電子標簽當前查詢位置之后的兩個EPC位元記錄于陣列LO(參數LO用以記錄欲進行邏輯運算的EPC信息字串,數值類型為字串，其起始值為空字串)中，并進行XOR邏輯運算，如圖2所示.

圖2 記錄回應電子標簽目前詢問位置下的兩個EPC位元

若閱讀器同時收到多個電子標簽的回應信息，即表示電子標簽發(fā)生碰撞無法成功識別，此時，讀取器會將碰撞次數Col值加1(參數Col用以記錄系統(tǒng)的碰撞次數，數值類型為整數，其起始值為0).同時，閱讀器將會記錄所有回應碰撞電子標簽此次查詢位置之后的兩個EPC位元，然后將所記錄EPC位元進行XOR邏輯運算以求出此次可能新增位串的最小集合，其做法是閱讀器會取出先前所記錄的電子標簽后兩位元進行XOR運算.

第四步：合并目前查詢字串及邏輯運算后之結果，產生新查詢字串并將結果存入查詢隊列中，并跳回第一步，閱讀器將會持續(xù)進行識別動作，直到電子標簽被識別完畢為止.

經過XOR邏輯運算后得到無重復的字串信息，最后再將當前的查詢字串信息與XOR邏輯運算后的結果合并存入查詢字串信息隊列中.整個系統(tǒng)會反復執(zhí)行上述步驟，直到所有電子標簽均被成功識別完成為止.

第五步：成功識別，進行電子標簽信息的讀取，成功識別的電子標簽進入睡眠狀態(tài)，不進入下一次的競爭，信息讀取完畢后則跳回第一步，直到電子標簽全被識別完畢為止.

第六步：結束.

以圖3為例說明MQSQT算法與SQT算法的比較：假設閱讀器一開始發(fā)出查詢字串為0時，因電子標簽1、2、3、4的第一位元值均為“0”，所以此四個電子標簽均會回應信息給閱讀器，在SQT算法里此時閱讀器會分別將“000”、“001”、“010”及“011”四筆字串分別存入查詢隊列中；若采用MQSQT算法，則只需將“000”和“001”兩筆字串加入查詢隊列中，其余兩筆為重復多余的查詢字串則會被擯棄，所以MQSQT算法的空閑次數會較SQT算法少.在MQSQT算法中，當閱讀器收到電子標簽回復后，會記錄所有回應電子標簽此次詢問位置之后兩個EPC位元值，分別為“00”、“01”、“00”與“01”；然后閱讀器對“00”、“01”的第一個位元與第二個位元分別進行XOR運算，算出“00”、“01”第一個位元XOR運算后的結果為“0”，第二個位元XOR運算后的結果為“1”，由此可知此四個電子標簽用于XOR運算的兩位元中的第一位元值必完全相同，而第二位元必有不同的值，即必含有“0”與“1”.因此，可取出第一位元的值“0” 分別與第二位元必有的“0”及“1”組合出所有可能的位元串“00”與“01”，最后，再將目前的查詢位元“0”分別與邏輯運算得出的結果“00”與“01”合并后，即可分別組合出兩個新的查詢字串“000” 和“001”，將之存入隊列中以供下次查詢之用.

圖3 邏輯運算運作流程

表3 MQSQT算法運作流程

查詢步驟閱讀器廣播的查詢字串前綴響應電子標簽電子標簽狀態(tài)第一步0標簽1、標簽2標簽3、標簽4碰撞第二步1標簽5、標簽6碰撞第三步000標簽1、標簽3碰撞第四步001標簽2、標簽4碰撞第五步101標簽5識別第六步111標簽6識別第七步0000標簽1識別第八步0001標簽3識別第九步0010標簽4識別第十步0011標簽2識別

表3為MQSQT算法的運作流程.由表3可看出經過XOR邏輯運算后，并沒有產生任何的空閑狀態(tài).因此，通過MQSQT算法可降低采用SQT算法查詢過程中所產生的空閑次數過多的問題.

4 仿真參數設置

各種模擬參數設置如表4所示，且假設在模擬仿真環(huán)境中無任何干擾，電子標簽數量范圍為50～500個，每次增加50個，EPC的長度為15bits，所有模擬數據為對每種電子標簽數量進行100次模擬所得數據的平均值.

表4 模擬參數設置表

5 模擬結果分析

QT算法與SQT算法其運作的差別在于每次查詢位元串所新增加的bit數，前者以每次增加1個bit的方式組成新的查詢位元串，而后者以每次增加2bits的方式，仿真結果如圖4所示.從圖5可知采用QT算法的碰撞次數遠多于采用SQT算法時，而MQSQT算法則是在SQT算法上增加了邏輯運算，其查詢的方式與SQT算法相同，因此，在碰撞次數上與采用SQT算法差不多.

圖4 電子標簽數量與碰撞次數的關系圖

圖5為三種算法的空閑數量的比較圖，圖中顯示SQT算法比QT算法在空閑數量部分有較差的性能且差異非常大，這是因為QT算法是以每次增加1bit方式來得到新的查詢字串，而SQT算法則是以每次增加2bits的方式來得到新的查詢字串.因此，采用QT算法會比采用SQT算法較早且較上層就發(fā)現空閑狀況，整體的空閑數量也相對較低，而MQSQT算法由于部分修改了增加查詢字串信息的限制，利用邏輯XOR運算求出最符合的2bit查詢字串信息，改善了采用SQT算法時空閑次數過多的問題.由圖6可清楚看出MQSQT算法所表現出的性能有較明顯的改善.

圖5 電子標簽數量與空閑次數的關系圖

因此，QT算法雖然在碰撞次數上多于SQT算法，但在空閑次數上要少于SQT算法.MQSQT算法不僅解決了QT算法碰撞次數過多的問題，同時也解決了SQT算法空閑狀態(tài)過多的問題.圖6中，比較了三種算法所執(zhí)行的總查詢次數，即成功識別次數、碰撞次數、空閑次數的總和.

圖6 電子標簽數量與總查詢次數的關系圖

從圖6可看出，QT算法與SQT算法因為各有碰撞次數或空閑次數的優(yōu)缺點，所以在整體的查詢總次數上并沒有太大的差異，而MQSQT算法則是因改善了SQT算法的缺點并保留了其優(yōu)點，所以在總查詢次數上有明顯的改善.MQSQT算法提升了系統(tǒng)的整體性能.

6 總結

RFID系統(tǒng)中的標簽碰撞與空閑的問題關系到系統(tǒng)的效率，文章針對兩個問題所提出的SQT算法和MQSQT算法都是以QT算法為基礎改進而來.SQT算法改進了QT算法，增加查詢位元串的方式為跨層方式，降低了標簽碰撞次數.但帶來了空閑次數過多的弊端.針對SQT算法問題而改進的MQSQT算法，利用符合EPC當前查詢字串后2個位元值進行邏輯運算，以求出包含下一層必需查詢節(jié)點的所有可能的字串最小集合，達到了降低空閑次數的目的.由電腦模擬仿真結果顯示，SQT與MQSQT算法在避免碰撞的能力上均比QT算法有更好的結果，在空閑模擬的部分，MQSQT算法顯示有很好的效果，在整體性能上有明顯的改善.

[1] Kim J, Lee W, Yu J, et al. Effect of localized optimal clustering for reader anti-collision in RFID networks: Fairness aspects to the readers[A]. Proceedings of 14th International Conference on Computer Communications and Networks[C]. 2005:497-502.

[2] Li B, Jing Z, Luo Y. A RFID anti-collision searching algorithm based on regressive style binary system[J].Computer Applications and Software, 2009, (12):96-98.

[3] Yang Z, Chen J, Mao Z. Study on the performance of tag-tag collision avoidance algorithms in RFID system[A].Proceedings of Third Asia International Conference on Modeling & Simulation.2012:757-760.

[4] Yeh M, Jiang J, Huang S. Adaptive splitting and pre-signing for RFID tag anti-collision[J].Computer Communications, 2009, (1):1862-1870

[5] Myung J, Lee W, Srivastava J. Adaptive binary splitting for efficient RFID tag anti-collision[J]. IEEE Communications Letter, 2006, (3):144-146.

[6] 高金輝, 鄭曉彥.新型混合防碰撞算法[J].電子技術應用, 2011, (12):130-136.

[7] 王中祥, 王俊宇，劉丹，等.一種降低空時隙開銷的防碰撞算法[J].通信學報, 2009, (9):1-6.

(責任編校：晴川)

RFID Anti-collision Algorithm of Cross Layer Query Based on QT

KONG Fanfeng, LONG Linde, ZHU Yongping

(Department of Mobile Communication, Hunan Post and Telecommunication College, Changsha Hunan 410115, China)

QT algorithm of current RFID system could result in increased query numbers, high collision frequency and low efficiency of the system when the number and density of EPC electronic label increase. In allusion to these shortcomings, this paper proposed a cross layer algorithm, including the SQT algorithm and MQSQT algorithm. SQT algorithm became cross layer query mode through improving the bit string mode of QT algorithm querying for electronic tag, and MQSQT algorithm conducted XOR logic operation based on 2 bits of EPC string of current query, so as to find the minimal set of query string needed for the cross layer search. The simulation results showed that the improved algorithm reduced the number of collisions, average numbers of queries had been greatly improved, and it improved the efficiency of RFID system.

RFID; electronic tag; anti-collision; QT

2015-04-29

湖南省教育廳科學研究項目(批準號：12C0963).

孔凡鳳(1979— )，女，山東萊蕪人，湖南郵電職業(yè)技術學院移動通信系講師，碩士．研究方向：無線傳感網絡.

TP393

A

1008-4681(2015)05-0042-05