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

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

一種改進的位競爭式RFID防碰撞算法*

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

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

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

位競爭 鎖位 堆棧

0 引 言

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

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

1 位競爭式防碰撞算法

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

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

圖1 BCA算法Fig.1 BCA algorithm

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

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

2 改進的位競爭式防碰撞算法

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

2.1 曼徹斯特編碼

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

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

2.2 鎖位

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

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

2.3 設置堆棧后退

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

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

2.4 IBCA算法步驟

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

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

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

P:進行運算的比特位。

MSB:碰撞位的最高位。

N:棧頂標簽競爭失敗比特位的下一位。

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

算法的主要步驟如下:

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

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

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

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

5)閱讀器成功識別標簽。

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

2.5 算法舉例說明

設有如下5個標簽待識別:A1010010100,B 1010110110,C1010110100,D1010111110,E1001111110,識別過程如下:

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

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

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

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

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

3 仿真結果

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

圖6 標簽數量與碰撞時隙數關系Fig.6 Relationship between tag number and collision-slot number

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

圖7 標簽數量與通信次數關系Fig.7 Relationship between tag the number and communication number

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

4 結 語

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

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

[1] 高飛,薛艷明,王愛華.RFID原理與應用[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].通信技術,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] 侯勝宇,馮鋒.一種改進的二叉樹型RFID防碰撞算法[J].計算機工程與應用,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].合肥工業(yè)大學學報:自然科學版,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—),男,教授,主要研究方向為光通信技術;

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—),男,碩士研究生,主要研究方向為無線通信技術;

2014-07-24;

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