雙時(shí)隙二進(jìn)制樹堆棧式RFID防碰撞算法

魏紹蓉， 王曉英， 劉志強(qiáng)， 賈續(xù)涵

(青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系，青海 西寧 810016)

?

雙時(shí)隙二進(jìn)制樹堆棧式RFID防碰撞算法

魏紹蓉， 王曉英， 劉志強(qiáng)， 賈續(xù)涵

(青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系，青海 西寧 810016)

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

RFID; 多標(biāo)簽; 防碰撞; 堆棧

0 引 言

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

1 典型標(biāo)簽防碰撞算法研究

1.1 BT算法

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

1.2 QT算法

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

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

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

2 BSBTA設(shè)計(jì)與實(shí)現(xiàn)

2.1 BSBTA 采用曼徹斯特編碼

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

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

2.2 BSBTA算法總體描述

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

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

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

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

(3) 第一個(gè)時(shí)隙

① 沒有響應(yīng)，不做任何事情。

② 收到某個(gè)比特b0：

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

如果p

③ 碰撞：

如果p==m-4，則當(dāng)前碰撞是由標(biāo)簽ID的最后一位引起的，因?yàn)槭褂玫氖锹鼜厮固鼐幋a，碰撞表明最后一位為“0”和“1”的標(biāo)簽都存在，所以閱讀器同時(shí)識別兩個(gè)標(biāo)簽，其ID分別為prefix||00和prefix||01，prefix后面的“0”表示這是第一個(gè)時(shí)隙。

如果p

圖2 BSBTA算法流程圖

(4) 第二個(gè)時(shí)隙

① 沒有響應(yīng)，不做任何事情。

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

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

如果p

③ 碰撞：

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

如果p

(5) 算法結(jié)束判斷

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

② 如果stack為空，識別過程結(jié)束。

每個(gè)標(biāo)簽使用一個(gè)二進(jìn)制變量P來記錄標(biāo)簽ID中被查詢的比特的位置。P的初始值為0，表示標(biāo)簽未被閱讀器查詢，只有當(dāng)標(biāo)簽將它ID中的比特發(fā)送給閱讀器之后，P才會(huì)向低一位比特移動(dòng)。

3 系統(tǒng)仿真及性能評估

3.1 識別一個(gè)標(biāo)簽的平均響應(yīng)比特?cái)?shù)

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

圖3 標(biāo)簽的平均響應(yīng)比特?cái)?shù)

3.2 識別一個(gè)標(biāo)簽的平均時(shí)隙數(shù)

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

圖4 識別一個(gè)標(biāo)簽的平均時(shí)隙數(shù)

4 結(jié) 語

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

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

[2] 夏 宏,吳濟(jì)文.超高頻RFID讀寫器系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2012,32(8): 2369-2373.

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

[4] 孫文勝,金陳敏.新型的RFID動(dòng)態(tài)幀時(shí)隙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] 史長瓊,肖瑞強(qiáng),吳 丹.改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA防碰撞算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(6):1897-1901.

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

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

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

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

[11] 石封茶,崔 琛,余 劍.基于標(biāo)簽運(yùn)動(dòng)的一種新型RFID防碰撞算法[J].計(jì)算機(jī)科學(xué),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

國家自然科學(xué)基金項(xiàng)目(61363019); Google人才引進(jìn)勵(lì)教金科研培育項(xiàng)目(2014)

魏紹蓉(1973-)，女，甘肅蘭州人，碩士，副教授，研究方向?yàn)镽FID技術(shù)與應(yīng)用，Tel．：13897410098；E-mail: wsr8808@163.com

TP 391

A

1006-7167(2015)11-0082-04