蔡彬元,宋依青,王海龍,駱 華

(1.曲阜師范大學(xué),山東曲阜273165;2.常州工學(xué)院,江蘇常州213002)

一種改進(jìn)的位競爭式RFID防碰撞算法*

蔡彬元1,宋依青2,王海龍1,駱 華1

(1.曲阜師范大學(xué),山東曲阜273165;2.常州工學(xué)院,江蘇常州213002)

為解決射頻識別系統(tǒng)中的標(biāo)簽防碰撞問題,在基于位競爭算法的基礎(chǔ)上提出一種改進(jìn)的防碰撞算法(IBCA)。改進(jìn)的算法首先加入鎖位機制,使閱讀器通過鎖位的方法將標(biāo)簽的碰撞比特位提取出來,之后和標(biāo)簽僅通信這些碰撞位,再按位進(jìn)行“或”運算。然后再通過設(shè)置堆棧,使得每次識別完一個標(biāo)簽后返回上一個碰撞位。算法考慮了碰撞時隙數(shù)和閱讀器問詢次數(shù)兩個性能指標(biāo),仿真結(jié)果表明,IBCA算法較BCA算法性能有很大提高。

位競爭 鎖位 堆棧

0 引 言

在當(dāng)前研究熱門的物聯(lián)網(wǎng)領(lǐng)域中,射頻識別技術(shù)(RFID,Radio Frequency Identification)是底層關(guān)鍵技術(shù)之一,它是一種非接觸式的自動識別技術(shù),可以實現(xiàn)對目標(biāo)信息的自動采集,能夠在惡劣、無人的環(huán)境中工作[1]。RFID系統(tǒng)主要包括電子標(biāo)簽與閱讀器,它們之間通過射頻信號進(jìn)行數(shù)據(jù)傳遞與交互。

標(biāo)簽碰撞問題是RFID系統(tǒng)需要解決的主要問題,它是指同一時刻在閱讀器范圍內(nèi)有多個標(biāo)簽發(fā)送響應(yīng)信號,此時閱讀器在同一時刻收到的數(shù)據(jù)之間發(fā)生干擾,由于這種干擾而無法正確識別任何標(biāo)簽。標(biāo)簽碰撞問題極大惡化了RFID的系統(tǒng)效率,目前主要利用TDMA防碰撞算法[2]來改善這一問題,其中包含兩種主要算法:ALOHA[3]算法和二叉樹算法[4]。ALOHA算法是一種不確定性的算法,因此會出現(xiàn)某些標(biāo)簽不能被識別的可能,通常稱為“餓死”現(xiàn)象。二叉樹算法是一種確定性算法,它可以解決標(biāo)簽“餓死”現(xiàn)象,但是由此卻產(chǎn)生了高延時和高功耗的問題。

1 位競爭式防碰撞算法

如果閱讀器范圍內(nèi)標(biāo)簽的數(shù)量進(jìn)一步增大,標(biāo)簽的碰撞問題就會變得更加嚴(yán)重,系統(tǒng)效率急劇降低,采用上述的防碰撞算法產(chǎn)生大量碰撞時隙和空閑時隙,不能很好解決這一情況。文獻(xiàn)[5]提出了一種基于位競爭(Bit Competed Algorithm)的防碰撞算法來提高系統(tǒng)的性能。

算法如圖1所示,4個標(biāo)簽A,B,C,D的UID (唯一識別碼)分別為0010,0101,1100,1110,閱讀器首先發(fā)送請求信號給所有標(biāo)簽,標(biāo)簽據(jù)此發(fā)送自己的UID給閱讀器,這時發(fā)生碰撞,閱讀器便從高位到低位利用“或”運算篩選識別標(biāo)簽。

圖1 BCA算法Fig.1 BCA algorithm

圖1中先從第3位開始進(jìn)行“或”運算,如果結(jié)果為0,直接開始下一位的運算,此時結(jié)果為1,第3位為0的標(biāo)簽A,B退出競爭,剩下的C,D由于第3位都是1,無法確定優(yōu)先級,閱讀器開始對C,D的第2位進(jìn)行“或”運算。第2位的運算結(jié)果仍然是1,此位上沒有比特為0的標(biāo)簽,閱讀器則繼續(xù)對第1位做“或”運算。第1位運算結(jié)果為1且只有唯一一個標(biāo)簽此位上比特值為1,閱讀器選中D而C退出競爭。識別出標(biāo)簽D后閱讀器從頭開始從第3位開始識別標(biāo)簽,重復(fù)運算和識別直到識別出所有響應(yīng)標(biāo)簽。

BCA防碰撞算法,使用“或”運算競爭出優(yōu)先識別的標(biāo)簽,是一種新的防碰撞算法,保證閱讀器每次詢問至少可識別一個標(biāo)簽,且它所產(chǎn)生的問詢次數(shù),碰撞次數(shù),復(fù)雜程度與其他算法相比有很大的競爭力。但是BCA算法也有很多不足之處,如每次成功識別一個標(biāo)簽之后要從頭開始詢問標(biāo)簽UID,這使閱讀器的詢問次數(shù)和傳輸?shù)臄?shù)據(jù)量大幅增加,導(dǎo)致整體系統(tǒng)效率降低,因此,將對這些問題提出解決方法。

2 改進(jìn)的位競爭式防碰撞算法

針對上述對BCA防碰撞算法存在的一些問題,提出一種改進(jìn)的位競爭式防碰撞算法(Improved Bit Compete Anti-Collision Algorithm)。在IBCA算法中,首先將碰撞標(biāo)簽的碰撞位取出,在通信過程中只傳輸比較這些碰撞位,降低系統(tǒng)傳輸數(shù)據(jù)量。接著閱讀器會記錄下此次競爭失敗的比特位置和標(biāo)簽數(shù)量,當(dāng)成功識別一次的標(biāo)簽后,只要從堆棧中取得之前競爭失敗的標(biāo)簽信息,從當(dāng)時競爭失敗的下個位比特位置繼續(xù)競爭,不需要從第一位比特重新競爭,這樣可以減少問詢次數(shù)并有效減少與標(biāo)簽通信的信息量傳輸,進(jìn)而提升系統(tǒng)效率。

2.1 曼徹斯特編碼

系統(tǒng)通過曼徹斯特編碼方式來標(biāo)記具體碰撞位。標(biāo)簽首先通過曼徹斯特編碼自己的UID,將其中的“1”表示為由高電平跳變的低電平,“0”表示由低電平跳變的高電平。標(biāo)簽將自己的UID同步發(fā)給閱讀器,閱讀器檢測某段同步時間內(nèi)的電平,如果沒有發(fā)生變化則判斷出此位發(fā)生了碰撞,如圖2所示。

圖2 曼徹斯特編碼Fig.2 Manchester encoding

2.2 鎖位

閱讀器判斷出發(fā)生碰撞的比特位后,通過譯碼將碰撞位置1,其他位置0,生成新的請求信號發(fā)送給標(biāo)簽。標(biāo)簽收到請求信號后與自身UID作對比,將未發(fā)生碰撞的位鎖住,下一輪通信過程中只發(fā)送發(fā)生碰撞的位,這樣就降低了系統(tǒng)傳輸?shù)臄?shù)據(jù)量,如圖3所示。

圖3 鎖位過程Fig.3 Bit-locking process

2.3 設(shè)置堆棧后退

為了減少傳輸過程中的通信次數(shù),通過設(shè)置堆棧使閱讀器在成功識別完一個標(biāo)簽后不必從頭開始識別下一標(biāo)簽。閱讀器收到標(biāo)簽發(fā)送的碰撞位,使用位競爭算法篩選位,將每次競爭失敗的標(biāo)簽信息放入堆棧中,標(biāo)簽信息包括競爭失敗的比特位位置和這一步中競爭失敗的標(biāo)簽數(shù),在堆棧中存儲形式為(失敗比特位置,失敗標(biāo)簽個數(shù))。當(dāng)成功識別完一個標(biāo)簽后閱讀器獲取堆棧信息,如果是空就結(jié)束,如果非空就取出棧頂元素信息,此時如果只有一個標(biāo)簽則直接識別,如果多于一個則繼續(xù)往下判斷。如圖4所示。

圖4 堆棧后退算法Fig.4 Stack back-off algorithm

2.4 IBCA算法步驟

圖5為IBCA算法流程圖,圖中主要符號意義如下:

REQ:請求命令。閱讀器發(fā)送請求信號給標(biāo)簽,標(biāo)簽收到命令后與自身UID作比較,若小于等于這個值則發(fā)送UID給閱讀器。

REQ(UID,0):鎖定指令。閱讀器發(fā)送鎖定信號給標(biāo)簽,標(biāo)簽收到信號后將未碰撞比特位鎖住,以后只發(fā)送發(fā)生碰撞的位。

P:進(jìn)行運算的比特位。

MSB:碰撞位的最高位。

N:棧頂標(biāo)簽競爭失敗比特位的下一位。

圖5 IBCA算法流程Fig.5 IBCA algorithm flow chart

算法的主要步驟如下:

1)閱讀器發(fā)送REQ(111···111)命令,所有ID碼值小于或者等于(111···111)的電子標(biāo)簽將自己的UID發(fā)送給閱讀器。

2)閱讀器檢測接收到的信號并進(jìn)行譯碼,判斷是否發(fā)生碰撞,如果有,轉(zhuǎn)到步驟3),如果沒有,直接識別該標(biāo)簽。

3)閱讀器判斷發(fā)生碰撞的具體位,生成新的請求信號REQ(UID,0)并發(fā)送給標(biāo)簽,其中置碰撞位“1”,未碰撞位“0”。標(biāo)簽收到信號后與自身UID比較,將未碰撞位鎖住,進(jìn)行步驟4)。

4)標(biāo)簽發(fā)送最高碰撞位比特給閱讀器,閱讀器進(jìn)行“或”運算,①如果運算結(jié)果是0,表示此次參與位比特競爭的標(biāo)簽優(yōu)先權(quán)都是相同的,故無法區(qū)分需進(jìn)行下一個位比特競爭;②如果“或”運算結(jié)果為1,存在唯一一個比特位為1的標(biāo)簽,那么該標(biāo)簽將取得所有參與競爭標(biāo)簽的最高優(yōu)先權(quán),此次運算位值是0的標(biāo)簽放棄此輪競爭,閱讀器將失敗標(biāo)簽的信息放入堆棧中,然后轉(zhuǎn)到步驟5;③如果“或”運算結(jié)果是1但是比特位為1的標(biāo)簽不止一個,那么比特位為1的標(biāo)簽將進(jìn)入下一比特位的競爭,此次比特位為0的標(biāo)簽放棄此輪競爭,閱讀器將失敗標(biāo)簽信息放入堆棧中,然后轉(zhuǎn)到步驟6)。

5)閱讀器成功識別標(biāo)簽。

6)成功識別完一個標(biāo)簽后,閱讀器檢查堆棧里有沒有競爭失敗標(biāo)簽的信息。若為空代表所有標(biāo)簽已經(jīng)全部識別完,如果堆棧中還有待識別標(biāo)簽,那么取出堆棧中優(yōu)先權(quán)最高標(biāo)簽的信息,如果取出的標(biāo)簽。

2.5 算法舉例說明

設(shè)有如下5個標(biāo)簽待識別:A1010010100,B 1010110110,C1010110100,D1010111110,E1001111110,識別過程如下:

1)閱讀器發(fā)送REQ(1111111111)信號給標(biāo)簽, 5個標(biāo)簽收到后全部返回發(fā)送自己的UID。

2)閱讀器檢測到標(biāo)簽發(fā)生碰撞,譯碼生成新請求信號REQ(0011101010)給標(biāo)簽。

3)標(biāo)簽收到鎖位信號,將未發(fā)生碰撞位鎖住,將碰撞位重新排序發(fā)送。這時為A 10000,B 10101, C 10100,D 10111,E 01111。

4)閱讀器將第5位做“或”運算,結(jié)果為1,E退出競爭,第5位為0的標(biāo)簽有1個,將(5,1)推入堆棧。然后第4位做“或”運算,結(jié)果是0,對A,B,C, D的第三位進(jìn)行操作。這時A退出競爭,第3位為0的標(biāo)簽有1個,將(3,1)推入堆棧。對剩下的標(biāo)簽第2位做“或”運算,結(jié)果為1且為1的標(biāo)簽只有一個D,直接識別。有兩個第2位為0的標(biāo)簽,將(2, 2)推入堆棧。

5)從棧頂取出(2,2)對下一位也就是第1位做“或”運算,結(jié)果為1且只有一個為1的標(biāo)簽B,直接識別,同時將標(biāo)簽C也識別。再取出棧頂?shù)?3,1),識別出A,同理識別出E。

3 仿真結(jié)果

采用MATLAB仿真平臺對BCA,IBCA及同樣基于比特位的二叉樹算法BTA(Bit Tree Algorithm)[6]進(jìn)行仿真對比,標(biāo)簽數(shù)量從0變化到1 000,仿真結(jié)果如圖6和圖7所示。

圖6 標(biāo)簽數(shù)量與碰撞時隙數(shù)關(guān)系Fig.6 Relationship between tag number and collision-slot number

圖6可以看出IBCA算法比BTA,BCA算法所產(chǎn)生的碰撞時隙要少的多,改進(jìn)的算法有明顯的優(yōu)勢。

圖7 標(biāo)簽數(shù)量與通信次數(shù)關(guān)系Fig.7 Relationship between tag the number and communication number

圖7仿真了標(biāo)簽數(shù)量與閱讀器詢問次數(shù)的關(guān)系,從中可見IBCA算法較前兩種詢問次數(shù)也大量減少,從而減少了系統(tǒng)的通信量,提高了系統(tǒng)的效率。

4 結(jié) 語

文中介紹了RFID系統(tǒng)中的碰撞問題和對應(yīng)的防碰撞算法,重點分析了基于位競爭的算法原理,當(dāng)閱讀器識別大量標(biāo)簽時,其雖然在系統(tǒng)性能上有了

很大改進(jìn),但還是不夠理想。本文提出的改進(jìn)算法通過引入鎖位機制和設(shè)置堆棧后退的方法,與位競爭算法相結(jié)合,使得系統(tǒng)所需的碰撞時隙數(shù)和詢問次數(shù)進(jìn)一步降低,有效地提高了閱讀器的識別效率,增強了系統(tǒng)的性能。經(jīng)過對改進(jìn)后的算法進(jìn)行仿真實驗分析,結(jié)果表明算法可以工作并改善了系統(tǒng)性能,證明了可行性。

[1] 高飛,薛艷明,王愛華.RFID原理與應(yīng)用[M].北京:人民郵電出版社,2010.

GAO Fei,XUE Yan-ming,WANG Ai-hua.RFID Principles and Applications[M].BeiJing:People Post Press, 2010.

[2] NEMAI Chandra Karmakar.Handbook of Smart Antennas for RFID Systems[M].New York:Wiley and Sons, 2010.

[3] 宋瑞玲,高仲合.基于分組動態(tài)幀時隙ALOHA防碰撞算法研究[J].通信技術(shù),2013,46(07):37-39.

SONG Rui-ling,GAO Zhong-he.Tag Anti-collision Algorithm based on Dynamic Frame Slotted ALOHA[J]. Communications Technology,2013,46(07):37-39.

[4] 侯勝宇,馮鋒.一種改進(jìn)的二叉樹型RFID防碰撞算法[J].計算機工程與應(yīng)用,2013,49(04):129-233.

HOU Sheng-yu,FENG Feng.Improved binary tree anticollision algorithm in RFID system[J].Computer Engineering and Applications,2013,49(4):129-133.

[5] TZAY-FARN Shih,and WEN-LI Hsu.An efficient Anti -Collision Algorithm for RFID System[C]//Proceedings of the 8th WSEAS International Conference on Applied Computer and Applied Computational Science(ACACOS'09).Athens:WSEAS Press,2009:488-494.

[6] 單承贛,孫明.基于后退策略的位傳輸二進(jìn)制搜索算法[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版,2010, 33(01):68-72.

SHAN Cheng-gan,SUN Ming.An algorithm based on bit -by-bit binary-tree ofbacktracking[J].Journal of Hefei University of Technology(Natural Science),2010,33 (01):68-72.

CAI Bin-yuan(1990-),male,graduate student,mainly engaged in wireless communication technology.

宋依青(1960—),男,教授,主要研究方向為電子信息與通信系統(tǒng);

SONG Yi-qing(1960-),male,professor,mainly engaged in electronic information and communication system.

王海龍(1971—),男,教授,主要研究方向為光通信技術(shù);

WANG Hai-long(1971-),male,professor,mainly engaged in optical communication technology.

駱 華(1989—),男,碩士,主要研究方向為電路與系統(tǒng)。

LUO Hua(1989-),male,M.Sci.,mainly engaged in circuits and systems.

An Improved Bit-Competition RFID Anti-Collision Algorithm

CAI Bin-yuan1,SONG Yi-qing2,WANG Hai-long1,LUO Hua1
(1.Qufu Normal University,Qufu Shandong 273165,China;2.Changzhou Institute of Technology,Changzhou Jiangsu 213003,China)

The improved bit-competition algorithm(IBCA)based on BCA algorithm is proposed to solve the problem of tag collision in RFID system.Firstly,bit-locking mechanism is introduced into the improved algorithm,thus the readers could extract collision bits among tags via bit-locking method.Then only the collision bits are communicated and OR operations done by bit.The improved algorithm makes the tag get back to the pervious collision bit via setting a stack after identifying a tag.This algorithm takes number of collision slot and times of the request into account.Simulation results indicate that this IBCA algorithm is highly improved in performance as compared with BCA algorithm.

bit competition;bit-locking;stack

TP301.6

A

1002-0802(2014)10-1227-05

10.3969/j.issn.1002-0802.2014.10.024

蔡彬元(1990—),男,碩士研究生,主要研究方向為無線通信技術(shù);

2014-07-24;

2014-09-01 Received date：2014-07-24;Revised date：2014-09-01