伍繼雄,江 岸,黃生葉?,何怡剛

(1.中國(guó)電子科技集團(tuán)公司第七研究所,廣東廣州 510310,2.湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南長(zhǎng)沙 410082)

RFID系統(tǒng)中二叉樹防碰撞算法性能的提升*

伍繼雄1,江 岸2,黃生葉2?,何怡剛2

(1.中國(guó)電子科技集團(tuán)公司第七研究所,廣東廣州 510310,2.湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南長(zhǎng)沙 410082)

針對(duì)RFID系統(tǒng)中的標(biāo)簽碰撞問題,提出了一種改進(jìn)的二叉搜索樹防碰撞算法.通過劃分標(biāo)簽子集、動(dòng)態(tài)調(diào)整沖突檢測(cè)過程,以減少標(biāo)簽沖突和系統(tǒng)開銷,提高識(shí)別效率.仿真結(jié)果表明,相比于目前的二叉樹搜索算法,本文方法在待識(shí)別標(biāo)簽數(shù)量較大的情況下提高了識(shí)別效率,減少了搜索次數(shù)及閱讀器與標(biāo)簽之間的通信量.

防碰撞;RFID;子集劃分;動(dòng)態(tài)調(diào)整

在RFID技術(shù)的發(fā)展過程中,防碰撞技術(shù)是信號(hào)識(shí)別與處理的關(guān)鍵技術(shù)之一.當(dāng)在讀寫器的作用區(qū)域中有多個(gè)標(biāo)簽同時(shí)發(fā)送信號(hào)而產(chǎn)生信道爭(zhēng)用問題時(shí),信號(hào)互相干擾,即發(fā)生了碰撞.因此,如何使用防碰撞技術(shù)識(shí)別多個(gè)目標(biāo)以及如何在保證識(shí)別精度的同時(shí)提高效率具有重要意義.

當(dāng)前廣泛使用的防碰撞算法有兩類:基于樹分叉的算法和基于A loha的算法[1-2].A loha算法實(shí)現(xiàn)相對(duì)簡(jiǎn)單,效率也較低[3].樹分叉算法采用了確定性搜索的防碰撞策略,其核心思想是讀寫器根據(jù)沖突的信號(hào),按照二叉樹深度優(yōu)先搜索的思想,逐步縮小搜索范圍,直到找到符合指定條件的標(biāo)簽.這類算法主要有跳躍式動(dòng)態(tài)樹形防碰撞算法(Jumping Dynam ic Search JDS)[4],查詢樹算法(Query T ree QT)[5]、ABS 算法(Adap tive Binary Sp litting)以及文獻(xiàn)[6]中的改進(jìn)動(dòng)態(tài)二分搜索算法IDBS(imp roved dynamic binary search)等[1].樹分叉算法有更好的識(shí)別精度和信道利用率.但目前的樹分叉算法仍有較長(zhǎng)的識(shí)別延時(shí)和較大的通信復(fù)雜度,需進(jìn)一步改進(jìn).

本文提出的標(biāo)簽防碰撞算法在文獻(xiàn)[6]中算法的基礎(chǔ)上,通過劃分標(biāo)簽子集、動(dòng)態(tài)調(diào)整沖突檢測(cè)過程,旨在大幅度地減少標(biāo)簽沖突和讀寫器與標(biāo)簽之間的通信量.并通過仿真檢驗(yàn)算法的性能.

1 算法的幾點(diǎn)約定

1)本算法基于樹分叉搜索算法,要求閱讀器能夠準(zhǔn)確地識(shí)別出數(shù)據(jù)碰撞位的位置,采用了曼徹斯特編碼[7].該編碼約定邏輯“1”對(duì)應(yīng)信號(hào)含下降沿跳變,而邏輯“0”對(duì)應(yīng)信號(hào)含上升沿跳變.若無狀態(tài)跳變,視為錯(cuò)誤被識(shí)別.當(dāng)兩個(gè)或多個(gè)標(biāo)簽同時(shí)返回的某一數(shù)位有不同的值,則接收到的上升沿和下降沿相互抵消,以致出現(xiàn)“沒有變化”或變化被明顯削弱的狀態(tài),閱讀器由此可判斷該位出現(xiàn)了碰撞.假設(shè)標(biāo)簽1和標(biāo)簽2的ID分別是01010011和00110011,利用曼徹斯特編碼能按位識(shí)別出碰撞位的示意圖如圖1所示.由于標(biāo)簽1和2是同時(shí)傳送其數(shù)據(jù),利用曼徹斯特編碼閱讀器解碼為0XX 1X0X1,于是閱讀器檢測(cè)出第1,2,4和6比特出現(xiàn)碰撞.

圖1 用曼徹斯特編碼的碰撞情況Fig.1 Co llision cases with M anchester codes

2)標(biāo)簽內(nèi)部設(shè)置了一個(gè)計(jì)數(shù)器R用于存儲(chǔ)標(biāo)簽ID中所有比特位的按位異或的結(jié)果,例如標(biāo)簽ID:01001001,則標(biāo)簽中計(jì)數(shù)器R的值為1,這個(gè)計(jì)數(shù)器的值可以在標(biāo)簽制造時(shí)由工廠固化寫入.因?yàn)樵撚?jì)數(shù)器值可以是0或者1,分別代表標(biāo)簽ID中‘1'的個(gè)數(shù)是偶數(shù)和奇數(shù)的情況,所以增加該計(jì)數(shù)器R是為了將標(biāo)簽劃分為更小的兩個(gè)子集.

為了動(dòng)態(tài)傳輸標(biāo)簽ID數(shù)據(jù),標(biāo)簽中計(jì)數(shù)器flag是表示標(biāo)簽是否被屏蔽的標(biāo)志位,為0表示沒有被屏蔽,可以響應(yīng)閱讀器的命令,傳送從計(jì)數(shù)器count指向的對(duì)應(yīng)位開始的ID數(shù)據(jù),該標(biāo)志非零表示標(biāo)簽被屏蔽,不響應(yīng)閱讀器的命令.

3)為了便于描述算法,引入以下有關(guān)指令:

a)Request(m,n)請(qǐng)求命令:m為上一次搜索過程中標(biāo)簽第1次碰撞的位置,n為劃分標(biāo)簽子集的標(biāo)識(shí)位.標(biāo)簽收到這個(gè)請(qǐng)求命令后,只有其計(jì)數(shù)器R的值與子集標(biāo)識(shí)位n相匹配的標(biāo)簽響應(yīng)請(qǐng)求命令.若匹配,當(dāng)m+1的值大于計(jì)數(shù)器count值時(shí),令count=m+1.檢查此m指定的自己ID對(duì)應(yīng)的比特位,若為0,則從計(jì)數(shù)器count指向的比特位開始傳送自己的ID數(shù)據(jù),若為1,則將計(jì)數(shù)器flag值加一,即將標(biāo)簽屏蔽.閱讀器第1次搜索時(shí)發(fā)送Request(L-1,n),L為標(biāo)簽ID的長(zhǎng)度,要求區(qū)域內(nèi)所有匹配子集標(biāo)識(shí)位n的標(biāo)簽應(yīng)答.

b)Select(ID)選擇命令:把某個(gè)事先確定的ID作為參數(shù)發(fā)送給標(biāo)簽.具有指定ID的標(biāo)簽將以此作為執(zhí)行后續(xù)命令(例如讀寫和寫入數(shù)據(jù))的切入開關(guān),即選擇這個(gè)標(biāo)簽.具有其它ID的標(biāo)簽將自己的計(jì)數(shù)器flag值減一.

c)Read-Data讀出數(shù)據(jù):選中的標(biāo)簽將存儲(chǔ)的數(shù)據(jù)發(fā)送給閱讀器.

d)Unselect去選擇:取消一個(gè)事先選中的標(biāo)簽,標(biāo)簽進(jìn)入“無聲狀態(tài)”.

2 算法要點(diǎn)和實(shí)現(xiàn)

2.1 算法要點(diǎn)

1)閱讀器每次發(fā)送的Request指令指出了上1次搜索過程中標(biāo)簽第1次碰撞的位置,減少了指令長(zhǎng)度.

2)由于一次搜索過程中所有響應(yīng)的標(biāo)簽的計(jì)數(shù)器值R都相等,則說明每個(gè)標(biāo)簽ID的按位異或結(jié)果相等,等效于每個(gè)響應(yīng)標(biāo)簽ID中‘1'的個(gè)數(shù)有相同的奇偶性.因此一次搜索過程中不可能出現(xiàn)只有一次沖突的情況.

3)一次搜索過程中只有兩次比特位發(fā)生沖突時(shí),可以直接識(shí)別出兩個(gè)標(biāo)簽.例如對(duì)計(jì)數(shù)器值R為1的標(biāo)簽識(shí)別過程如下.

ID1:01001001 ID2:11000001

閱讀器端接收到解碼為:×100×001,發(fā)現(xiàn)有兩個(gè)沖突位.對(duì)閱讀器正確接收部分×100×001進(jìn)行按位異或結(jié)果為0,表示正確接收部分ID中‘1'的個(gè)數(shù)為偶數(shù),而這兩個(gè)標(biāo)簽的計(jì)數(shù)器值R都為1,說明這兩個(gè)標(biāo)簽ID中‘1'的個(gè)數(shù)為奇數(shù),可以判斷兩個(gè)沖突標(biāo)簽在這兩個(gè)沖突位中有且僅有一個(gè)比特位值為1,因此可以快速的識(shí)別出標(biāo)簽 01001001和11000001.

4)閱讀器檢測(cè)到有3次比特位發(fā)生沖突時(shí),即停止接受標(biāo)簽傳送的后續(xù)數(shù)據(jù),進(jìn)入下一次搜索過程,這樣有效地減少了標(biāo)簽的識(shí)別延時(shí)和閱讀器與標(biāo)簽之間的通信量.需要強(qiáng)調(diào)的是,目前的信號(hào)處理技術(shù)和半導(dǎo)體工藝水平已能為這種處理提供支持.例如,主流的數(shù)字信號(hào)處理器(DSP)的指令速度已達(dá)到400 MIPs以上,UHF頻段的 RFID標(biāo)準(zhǔn)中規(guī)定的信息速率為640 kbps,在傳送一bit信息的時(shí)間內(nèi),DSP可以執(zhí)行約700條指令,因此一旦比特沖突(碰撞)發(fā)生,讀寫器內(nèi)處理器在標(biāo)簽傳輸一個(gè)比特的時(shí)間后發(fā)起新一輪標(biāo)簽搜索過程是容易實(shí)現(xiàn)的.

2.2 算法實(shí)現(xiàn):

本算法的實(shí)施依賴于閱讀器與標(biāo)簽,因此下面分兩部分描述算法的詳細(xì)流程.閱讀器中初始狀態(tài)棧stack和string均為空,標(biāo)簽的ID為L(zhǎng)位,每個(gè)標(biāo)簽的計(jì)數(shù)器flag和count均為0.算法中符號(hào)ID (i,j)表示標(biāo)簽傳送從第i～第j比特的ID數(shù)據(jù)位.‘+'表示連接操作,例如‘0010'+‘1000'=‘00101000'.表達(dá)式XOR(ID識(shí)別)表示對(duì)已經(jīng)識(shí)別的部分ID進(jìn)行按位異或.標(biāo)簽的算法描述如下:

假設(shè)ID代碼為8位,閱讀器作用范圍內(nèi)有5個(gè)標(biāo)簽,它們?cè)谖闹械拇?hào)及ID碼見表1,閱讀器如何利用該算法來識(shí)別它們,如表2所示.由于簡(jiǎn)化了閱讀器命令,當(dāng)閱讀器檢測(cè)到3次比特位發(fā)生沖突時(shí)即停止接受標(biāo)簽傳送的數(shù)據(jù),因?yàn)榇撕髽?biāo)簽發(fā)送的比特?cái)?shù)據(jù)是沒有意義的,這樣可節(jié)省數(shù)據(jù)傳輸時(shí)間.除此之外,該算法根據(jù)計(jì)數(shù)器R將標(biāo)簽分成兩個(gè)子集分類進(jìn)行識(shí)別,若一次搜索完畢只檢測(cè)出二次比特位發(fā)生沖突可以直接識(shí)別兩個(gè)標(biāo)簽,提高了標(biāo)簽識(shí)別的效率.從表2可知,識(shí)別5個(gè)標(biāo)簽只用了4次搜索過程,標(biāo)簽與閱讀器的直接通信量為41.

表1 幾個(gè)8位ID碼標(biāo)簽舉例Tab.1 An examp le of several tagswith 8-bit identifying codes

表2 標(biāo)簽識(shí)讀過程例Tab.2 An examp le of identifying tags

3 算法的分析與比較

采用本算法,識(shí)別完閱讀器作用范圍內(nèi)的 N個(gè)標(biāo)簽所需的搜索次數(shù)記為S(N),N個(gè)標(biāo)簽中有N 1個(gè)標(biāo)簽的計(jì)數(shù)器R值為1,N2個(gè)標(biāo)簽的計(jì)數(shù)器R值為0,參照跳躍式動(dòng)態(tài)樹形防碰撞算法的有關(guān)方法進(jìn)行對(duì)比分析[4],可推出本文算法的時(shí)間復(fù)雜度為:

本算法相對(duì)于已有的二叉樹搜索算法有如下一些優(yōu)勢(shì):

1)由于將標(biāo)簽劃分為兩個(gè)子集分類識(shí)別,減小了沖突的概率.當(dāng)標(biāo)簽ID號(hào)相對(duì)集中時(shí),探測(cè)到只有兩次比特位發(fā)生沖突的機(jī)率比較大,能減少搜索的次數(shù).

2)簡(jiǎn)化了閱讀器發(fā)送的指令,同時(shí)當(dāng)檢測(cè)到有3次比特位發(fā)生沖突時(shí)即停止接受標(biāo)簽傳送的數(shù)據(jù),立刻對(duì)標(biāo)簽作出沖突處理,有效地減少了標(biāo)簽的識(shí)別延時(shí)和閱讀器與標(biāo)簽之間的通信量.

3)閱讀器利用棧stack和字符串string來保存已經(jīng)被閱讀器接收到的標(biāo)簽ID數(shù)據(jù),因此每次搜索中標(biāo)簽只需傳送部分?jǐn)?shù)據(jù),在文獻(xiàn)[6]IDBS算法的基礎(chǔ)上減少了傳輸時(shí)間.

閱讀器的搜索次數(shù)和閱讀器與標(biāo)簽之間的通信量直接影響到標(biāo)簽的識(shí)別速度.若閱讀器需要M次搜索才能識(shí)別N個(gè)標(biāo)簽,每次搜索時(shí)間t是由閱讀器命令傳輸時(shí)間treader,標(biāo)簽ID數(shù)據(jù)傳輸時(shí)間ttag,標(biāo)簽對(duì)閱讀器命令的響應(yīng)時(shí)間DE tag,閱讀器的沖突檢測(cè)時(shí)間 DE reader組成.閱讀器的數(shù)據(jù)發(fā)送速率為DR reader,標(biāo)簽的數(shù)據(jù)發(fā)送速率為DR tag.RL i為第i次搜索中閱讀器的指令長(zhǎng)度,TLi為第i次搜索中標(biāo)簽發(fā)送的數(shù)據(jù)比特長(zhǎng)度,ti為第 i次搜索時(shí)間, t delay為一次搜索中的響應(yīng)延遲.識(shí)別N個(gè)標(biāo)簽需要的總時(shí)間為:

從式(5)可知閱讀器識(shí)別完N個(gè)標(biāo)簽的時(shí)間T主要由通信量NUM,和搜索次數(shù)M決定.

由于本文算法是基于標(biāo)簽ID碼的奇偶性進(jìn)行預(yù)分集的動(dòng)態(tài)二分搜索算法,因此簡(jiǎn)記為PDBS(parity -based dynamic binary search).設(shè)標(biāo)簽ID長(zhǎng)度是64位,

標(biāo)簽ID隨機(jī)分配,DR reader和DR tag均為40 kbps,t delay為20μs,一個(gè)空閑時(shí)隙為40μs,通過編程并運(yùn)行本算法與文獻(xiàn)[6]的IDBS算法、跳躍式動(dòng)態(tài)樹形防碰撞算法JDS、查詢樹算法QT、ABS算法進(jìn)行仿真.搜索次數(shù)的比較見表3.

表3 各算法搜索次數(shù)比較Tab.3 Comparison of the searching times of different algorithms

可以看出,隨著標(biāo)簽的增多,本文算法中閱讀器搜索次數(shù)相對(duì)于其它算法最少,這是因?yàn)槎鄻?biāo)簽時(shí),發(fā)生兩次比特位沖突的概率增大,導(dǎo)致本算法優(yōu)勢(shì)更明顯.本算法采取了簡(jiǎn)化閱讀器指令、動(dòng)態(tài)傳輸ID數(shù)據(jù)策略,使得閱讀器與標(biāo)簽之間的通信量明顯少于JDS和QT算法.

表4為各算法識(shí)別同樣數(shù)量標(biāo)簽條件下不同算法讀寫器所發(fā)出的信息量的比較.由于本算法減少了閱讀器的搜索次數(shù)并通過硬件配合減少了閱讀器與標(biāo)簽之間一些不必要的通信量,根據(jù)式(5)可知標(biāo)簽的識(shí)別延時(shí)也將隨之減少,這與我們的仿真結(jié)果一致.識(shí)別延時(shí)的比較如表5所示.在待識(shí)別標(biāo)簽數(shù)較大時(shí),本算法識(shí)別標(biāo)簽的耗時(shí)小于所有其它算法,有更高的識(shí)別速率.表3～5所列的每項(xiàng)數(shù)據(jù),都是10次運(yùn)行結(jié)果的平均,每次所用標(biāo)簽的ID編號(hào)是隨機(jī)產(chǎn)生的.

表4 各算法讀寫器發(fā)送信息量比較Tab.4 Comparison of the traffic transferred by the reader of different algorithms bit

表5 各算法耗時(shí)比較Tab.5 Execution time comparison of different algorithms ms

4 結(jié) 語(yǔ)

標(biāo)簽防碰撞算法對(duì)RFID系統(tǒng)識(shí)別效率至關(guān)重要,本文提出的防碰撞算法相對(duì)于目前的二叉樹搜索算法,能夠在保證識(shí)別精度的前提下,明顯提高RFID系統(tǒng)的識(shí)別速率.所提出的算法涉及了對(duì)讀寫器的指令進(jìn)行改進(jìn),并需要硬件系統(tǒng)的支持.設(shè)計(jì)并實(shí)現(xiàn)支持本算法的讀寫器以將本文算法付諸實(shí)踐是作者下一步要開展的主要工作之一.

[1] M YUNG J,LEEW,SRIVASTA VA J,eta l.Tag-splitting:adaptive collision arbitration p rotocols for RFID tag identification[J].IEEE Transactions on Parallel and Distribu ted System s,2007,18(6):763-775.

[2] VOGT H.E fficient ob ject identification with passive RFID tags[C]//Proceedings of International Conference on Pervasive Com puting.Berlin:Springer,2002.98-113.

[3] A IBERTO LG,INDRA W.Comm unication netw ork s fundamental concep ts and key architectures[M].New York:M c-Graw-H ill,1999:354-365.

[4] 余松森,詹宜巨,王志平,等.跳躍式動(dòng)態(tài)樹形反碰撞算法及其分析[J].計(jì)算機(jī)工程,2005,31(9):19-26.

YU Song-sen,ZHAN Yi-ju,WANG Zhi-ping,et a l.A nti-collision algorithm based on jumping and dynamic searching and its analy sis[J].Compu ter Engineering,2005,31(9):19-26.(In Chinese)

[5] LAW C,LEE K,SIU K Y.Efficient mem ory less protocol for tag Identification[C]//Proceedings of the 4th International W orkshop on Discrete A lgorithm s and Methods for Mobile Compu ting and Comm unications.Boston:ACM,2000:75-84.

[6] 江岸,伍繼雄,黃生葉,等.一種改進(jìn)的RFID二進(jìn)制搜索防碰撞算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,35(5):229-235.

JIANG Aan,WU Ji-xiong,HUANG Sheng-yie,et al.Improved RFID binary search anti-collision algorithm[J].Computer Engineering,2009,35(5):229-235.(In Chinese)

[7] FINKENZELLERK.RFID handbook:radio-frequency identification fundamen tals and applications[M].John Wiley and Sons,2003:187-193.

[8] The International Standard Organization.ISO/IEC FDIS 18000-6-2003 Information technology automatic identification and data capture techniques-radio frequency identification for item management air interface-part 6[S].Parameters for Air Interface Communications at 860-960MHz,USA:ISOPress,2003.

Imp rovement of the Binary-searching-based Anti-collision A lgorithm of RFID System s

WU Ji-xiong1,JIANG An2,HUANG Sheng-ye2?,HE Yi-gang2

(1.NO.7th Research Institute,China Electronics Techno logy G roup Corporation,Guangzhou,Guangdong 510310,China; 2.College of Computer and Communication,Hunan Univ,Changsha,H unan 410082,China)

To address the tag collision problem in Radio Frequency Identification(RFID)system,an improved binary-tree anti-collision algorithm was p roposed.By dividing the tags into different subsets and ad justing dynamically the process of collision detection,the collision probabilities and power consum ption were reduced.The simulation resultshave show n that,com pared w ith other binary-tree anti-collision algorithm s,the p roposed algorithm enhances the identifying efficiency,and both the num ber of searching times and the bits transferred between the reader and the tags are relatively low when the number of tags is large.

collision avoidance;radio frequency identification;subset-division;dynamic ad justm ent

TN914.3

A

1674-2974(2010)12-0082-05 *

2009-11-16

國(guó)家863計(jì)劃先進(jìn)制造技術(shù)領(lǐng)域重大資助項(xiàng)目(2006AA 04A 104)

伍繼雄(1970-),男,廣東臺(tái)山人,湖南大學(xué)博士,中國(guó)電子科技集團(tuán)公司高級(jí)工程師

?通訊聯(lián)系人,E-mail:sheryl_huang@163.com