雙時隙二進制樹堆棧式RFID防碰撞算法

魏紹蓉， 王曉英， 劉志強， 賈續涵

(青海大學 計算機技術與應用系，青海 西寧 810016)

?

雙時隙二進制樹堆棧式RFID防碰撞算法

魏紹蓉， 王曉英， 劉志強， 賈續涵

(青海大學 計算機技術與應用系，青海 西寧 810016)

隨著射頻識別系統的廣泛應用，標簽數量不斷增加,導致了系統通信性能下降。文章通過分析和比較查詢樹算法(QT)、二進制樹算法(BT)的優缺點，提出一種雙時隙二進制樹堆棧式標簽防碰撞算法。該算法利用曼徹斯特編碼的特性來確定標簽識別過程中的ID碰撞位置，并且利用堆棧形成進一步搜索命令，逐一識別標簽。通過仿真比較幾個相關的算法，結果表明，雙時隙二進制樹堆棧式標簽防碰撞算法在減少數據傳輸量、減少識別標簽所需響應比特數及時隙數上明顯優于現有QT和BT算法。

RFID; 多標簽; 防碰撞; 堆棧

0 引 言

射頻識別技術(Radio Frequency Identification, RFID)[1]利用無線電波來傳輸閱讀器(reader)和標簽(tag)之間的信息，該項技術已經在身份識別、生產制造、軍隊事務、醫藥、交通以及動物跟蹤等許多領域應用。RFID技術被認為是21世紀的十大重要技術之一，讓人類的日常生活最終實現U(Ubiquitous)化,即信息無所不在。RFID系統是由讀寫器、標簽、中間件及信息系統四者構成。然而在實際應用中，會出現一個讀寫器同時收到多個標簽發出的信息，而此時將會發生標簽的信號碰撞(Collision)，導致閱讀器無法準確讀寫標簽[2]。針對標簽碰撞問題，目前有3類較成熟的標簽防碰撞算法：幀時隙 ALOHA 算法(Framed Slotted Aloha, FSA)、基于樹的算法和綜合算法[3-5]。目前，ISO/IEC、EPCglobal等國際組織制定的國際標準主要采用查詢樹算法(Query Tree Algorithm，QT)、二進制樹算法(Binary Tree Algorithm，BT)、二進制搜索算法(BS)等樹型算法，以及時隙類ALOHA算法進行多標簽識別防碰撞處理[6]。這些算法的識別效率只能達到34%～36.8%左右，且識別性能不穩定，不能滿足RFID多標簽識別應用系統的實際需要。通過分析比較目前典型的標簽防碰撞算法，研究并實現一種基于二進制樹的雙時隙堆棧式 RFID 標簽防碰撞算法。該算法目的是減少識別延時并改進二進制樹算法。通過仿真測試，算法比目前使用的基于時隙和二進制樹的防碰撞算法具有更少的響應比特數和時隙，有效地提高RFID系統的通信性能[7-9]。

1 典型標簽防碰撞算法研究

1.1 BT算法

BT算法是基于樹的標簽防碰撞算法[10-11]，通過標簽的唯一身份(ID)對標簽進行識別，標簽有3個狀態：活動、靜默和休眠。標簽被識別，則標簽進入休眠狀態直到識別過程結束。每個標簽使用指針定位其 ID 中當前被查詢的比特。閱讀器每次只發送一個比特的查詢，當指針指向的比特與查詢信息相等，活動標簽就發送下一個比特，然后將指針指向該比特，否則，標簽保持靜默，直到有一個標簽被識別。如果在標簽響應時發生碰撞，閱讀器首先詢問“0”，如果閱讀器收到的是某個特定的二進制比特，它將用這個比特作為下一次查詢。標簽被識別后，轉入休眠狀態，而未被識別的標簽被激活，指針重新指向最高位。

1.2 QT算法

QT[12]算法標簽不記錄當前狀態或查詢的比特位置。標簽收到閱讀器的查詢后，比較其ID前綴與查詢信息，相等則標簽把ID傳輸給閱讀器。當多個標簽響應閱讀器時，閱讀器就會知道至少有兩個相同前綴標簽，因此，閱讀器會在之前的查詢信息后面加上0或1，并用這2個新的前綴分別對標簽進行查詢。直到查詢信息和某個標簽的ID唯一匹配，這個標簽就可以被識別。因此，QT算法是通過擴充查詢信息的前綴，直到只有和一個標簽的ID匹配，才識別該標簽。QT算法是無記憶的基于樹的RFID防碰撞算法。QT算法的改進算法，雙時隙查詢樹算法(Bi-Slotted Query Tree Algorithm，BSQTA)。BSQTA算法通過在每次閱讀器的查詢信息之后引入雙時隙來改進QT 算法，BSQTA 在每識別一個標簽所需的迭代次數和平均所需比特數方面的表現優于QT 算法[13]。

1.3 BT算法及QT算法分析與比較

BT算法，當一個標簽被識別后，閱讀器重新從最高比特開始對其他標簽進行查詢，因為閱讀器在新的查詢中并沒有利用之前查詢中獲取的碰撞位置或其他可能的前綴等信息，所以增加了識別過程的時延。 QT算法，標簽是無記憶的，所以閱讀器和標簽在識別的過程中都必須傳輸更多的比特，導致了大量時延。鑒于分析比較BT與QT算法所存在的問題，結合兩者優勢，提出雙時隙二進制樹堆棧式防碰撞(Bi-Slotted Binary Tree Algorithm，BSBTA)算法。該算法利用曼徹斯特編碼的特性來確定標簽識別過程中的ID碰撞位置，并且利用堆棧記錄碰撞的前綴，形成進一步搜索命令，閱讀器就可以利用之前所獲取的信息進行查詢，并在一個標簽被識別之后，從最近一次發生碰撞的位置對其他標簽進行查詢。同時也引入雙時隙來減少標簽需要發送的比特數。

2 BSBTA設計與實現

2.1 BSBTA 采用曼徹斯特編碼

曼徹斯特編碼通過上升或下降的變化來描述邏輯 0或邏輯 1[14]，如果多個標簽同時傳輸不同的二進制序列，那么 0或1的覆蓋在編碼中將始終保持上升或下降的變化，如果發生碰撞，那么就沒有上升或下降的變化，因此閱讀器無法識別。

圖1 曼徹斯特編碼碰撞例子

2.2 BSBTA算法總體描述

假設標簽的ID是一個m比特的字符串，記為t0,t1,…,tm-1，其中ti∈{0,1}(i=0,1,…,m-1)。定義一個堆棧stack，stack的初始值為{00,01, 10, 11}代表所有標簽的最高兩位，閱讀器通過堆棧stack記錄碰撞的前綴，閱讀器利用變量p跟蹤被查詢的標簽。

其流程如圖2所示，具體步驟如下：

(1) 初始化堆棧。stack = {00, 01, 10, 11}。初始化階段每個標簽的指針P都指向標簽的最高位，記為第0比特，P=0。

(2) 閱讀器發送查詢。prefix =POP(stack)。假設 prefix=a0,a1,…,an-2,an-1，其中prefix的長度是n，n是標簽的ID長度m減2，其中ai∈{0,1} (i= 0, 1, …,n-1)。定義Q=an-2an-1，p=n-3。傳輸Q||p，為標簽響應預留兩個時隙。

(3) 第一個時隙

① 沒有響應，不做任何事情。

② 收到某個比特b0：

如果p==m-4，則當前接收到的是標簽ID中的最后一位，因此，閱讀器能夠識別這個標簽，其ID為prefix||0b0，b0前面的“0”表示是第一個時隙。

如果p

③ 碰撞：

如果p==m-4，則當前碰撞是由標簽ID的最后一位引起的，因為使用的是曼徹斯特編碼，碰撞表明最后一位為“0”和“1”的標簽都存在，所以閱讀器同時識別兩個標簽，其ID分別為prefix||00和prefix||01，prefix后面的“0”表示這是第一個時隙。

如果p

圖2 BSBTA算法流程圖

(4) 第二個時隙

① 沒有響應，不做任何事情。

② 收到了某個比特b1(0 或 1)：

如果p==m-4，表明當前接收到的是標簽ID中的最后一位，因此，閱讀器能夠識別這個標簽，其ID為prefix||1b1，b1前面的“1”表示這是第二個時隙。

如果p

③ 碰撞：

如果p==m-4，表明當前碰撞是由標簽ID的最后一位引起的，由于這里使用的是曼徹斯特編碼，碰撞表明最后一位為“0”和最后一位為“1”的標簽都存在，所以，閱讀器同時識別兩個標簽，其ID分別為prefix||10和prefix||11，prefix后面的“1”表示這是第二個時隙。

如果p

(5) 算法結束判斷

① 如果stack非空，回到2)。

② 如果stack為空，識別過程結束。

每個標簽使用一個二進制變量P來記錄標簽ID中被查詢的比特的位置。P的初始值為0，表示標簽未被閱讀器查詢，只有當標簽將它ID中的比特發送給閱讀器之后，P才會向低一位比特移動。

3 系統仿真及性能評估

3.1 識別一個標簽的平均響應比特數

系統吞吐率是衡量系統性能的重要指標，在Matlab平臺下，通過計算機仿真比較 BSBTA 、 BT[15]和QT[16]算法的性能。仿真程序由 Java 語言編寫，假設在查詢范圍內只有一個閱讀器，標簽的數量從 5 個遞增到800 個，標簽 ID 的長度為 96 比特，且 ID 值呈一致分布。圖3描述了每識別一個標簽的平均響應比特數。在 BT 算法中每個標簽在被識別之前需發送 除了最高比特之外，標簽需要傳輸所有 ID，95 比特。因為BSBTA算法使用雙時隙，所以每個雙時隙都表示一個比特，這樣至少節約了兩個響應比特，BSBTA算法中的響應比特數約為 BT 的一半。因為QT算法是無記憶的，每個標簽都需要用剩余的所有比特響應閱讀器，QT算法則需要更多的比特來識別標簽，而不像 BSBTA 算法，每次只要響應 1 比特，BSBTA 中的響應比特數只約為QT 的1/4左右。

圖3 標簽的平均響應比特數

3.2 識別一個標簽的平均時隙數

一個時隙表示一次對話，包括閱讀器的查詢和標簽的響應。圖4描述了每識別一個標簽的平均時隙數。 QT需要很少的時隙識別標簽，但是算法的無記憶性使得每個時隙中必須完整地傳輸至少 96 比特，所以每個時隙時間段都很長。BT 和 BSBTA每個時隙只傳輸幾個比特，所以每個時隙的時長相對短。 BSBTA是雙時隙，每次查詢之后會有兩個時隙，缺點是如果在沒有標簽與該時隙匹配時，雙時隙會導致空余時隙，但是BSBTA的時隙仍然比 BT 要少。最主要的原因是BSBTA 中，閱讀器利用堆棧記錄了碰撞位置，所以，當一個標簽被識別之后，下一次查詢將直接從碰撞位置開始，而在 BT 中需要從頭開始查詢。

圖4 識別一個標簽的平均時隙數

4 結 語

本文通過分析典型的BT及QT標簽防碰撞算法，提出利用曼徹斯特編碼的特性來確定標簽識別過程中的ID碰撞位置，利用堆棧記錄碰撞前綴的BSBTA算法。該算法利用堆棧，改進了BT算法中閱讀器在新的查詢中沒有利用之前查詢獲取的碰撞位置或其他可能的前綴等信息的缺陷；同時也改進了QT算法中標簽的無記憶性，閱讀器和標簽在識別的過程中都必須傳輸更多的比特、導致大量時延的缺陷。仿真實驗證明 BSBTA 在識別標簽時所需的響應比特數和時隙數少于 BT和QT算法，由此提高了標簽的識別速度，有效地改善了RFID系統的通信性能。

[1] 徐 燕. 基于RFID物聯網的研究[J].微型電腦應用,2011,27(5):47-48.

[2] 夏 宏,吳濟文.超高頻RFID讀寫器系統的設計與實現[J].計算機應用，2012,32(8): 2369-2373.

[3] 王春華.改進的RFID標簽防沖突算法[J].計算機工程與應用,2011，47(31):104-107.

[4] 孫文勝,金陳敏.新型的RFID動態幀時隙ALOHA防碰撞算法[J].信息與控制,2012,41(2)：233-237.

[5] Eom J ,Lee T. Accurate tag estimation for dynamic framed-slotted ALOHA in RFID system[J]．IEEE Communications Letters，2010,14 (1) : 60-62．

[6] 史長瓊,肖瑞強,吳 丹.改進的動態幀時隙ALOHA防碰撞算法[J].計算機工程與設計,2014,35(6):1897-1901.

[7] 劉 青,杜 江.RFID 防碰撞算法中ALOHA算法的研究[J].科技信息，2012，18: 112．

[8] 王云峰,張 斌.基于擴頻ALOHA的RFID防碰撞算法[J]. Computer Engineering and Design, 2014，40(3):2-5.

[9] 魏 靜,馮秀芳.基于自適應分組的幀時隙ALOHA算法在RF1D中的研究[J].計算機技術與發展,2012,22(11): 57-60.

[10] 王曉梅,張英梅.基于Q值的RFID防碰撞改進算法的研究[J].太原理工大學學報,2014,45(3):339-342.

[11] 石封茶,崔 琛,余 劍.基于標簽運動的一種新型RFID防碰撞算法[J].計算機科學,2013,40(6):76-79.

[12] Yang C, He J. An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision [J]. IEEE Communications Letters, 2011, 15(5): 539-541.

[13] Choi J H, Lee D, Lee H. Query tree-based reservation for efficient RFID tag anti-collision[J]. IEEE Communications Letters, 2007, 11(1), 85-87.

[14] Jia X, Feng Q, Ma C. An efficient anti-collision protocol for RFID tag identification [J]. IEEE Communications Letters, 2010, 14(11): 1014-1016.

[15] Zhu L., Yum T. S. P. The optimal reading strategy for EPC gen-2 RFID anti-collision systems [J]. IEEE Transactions on Communications, 2010, 58(9): 2725-2733.

[16] Law C., Lee K., Siu K. Y. Efficient memory less protocol for tag identification (extended abstract) [C]//In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2000: 75-84.

RFID Anti-collision Algorithm Based on Bi-slotted Binary Tree Stackable

WEIShao-rong,WANGXiao-ying,LIUZhi-qiang,JIAXu-han

(Department of Computer Technology and Application, Qinghai University, Xining 810016, China)

With the extensive application of radio frequency identification systems, increasing the number of tags can cause system performance degradation of communication. By analyzing and comparing the query tree algorithm (QT) and binary tree algorithm (BT), this paper proposes a RFID anti-collision algorithm based on stackable bi-slotted binary tree. The algorithm uses features of Manchester code to determine the collision position of an identification tag. Furthermore, the algorithm uses the stack to form a further search order to identify each tag. The simulation results compare the performance of several related anti-collision algorithms. It is shown that anti-collision algorithm based on stackable bi-slotted binary tree can effectively reduce the amount of data transmitted, reduce the average number of responded bits and timeslots for the tag identification. So it outperforms the QT and BT algorithm.

RFID; multi-tag; anti-collision; stack

2015-03-22

國家自然科學基金項目(61363019); Google人才引進勵教金科研培育項目(2014)

魏紹蓉(1973-)，女，甘肅蘭州人，碩士，副教授，研究方向為RFID技術與應用，Tel．：13897410098；E-mail: wsr8808@163.com

TP 391

A

1006-7167(2015)11-0082-04