改進的FRID防碰撞算法仿真研究

姚友德 馬 寧 高偉龍

（陜西省廣電網(wǎng)絡(luò)傳媒白水支公司，陜西 渭南715600）

0 引言

近年來，射頻識別（Radio Frequency Identification）這一自動識別技術(shù)在制造、物流、交通運輸[1-2]、防偽、醫(yī)療和跟蹤等應(yīng)用方面獲得了廣泛的應(yīng)用[2-3]。

RFID 技術(shù)具有多目標(biāo)識別顯著優(yōu)點，但與此同時，多目標(biāo)識別勢必造成多標(biāo)簽上行信號的數(shù)據(jù)沖突，從而給FRID 系統(tǒng)的數(shù)據(jù)完整性帶來極大威脅[4-5]。 研究表明，合適的防碰撞算法能夠有效地減緩數(shù)據(jù)沖突對系統(tǒng)數(shù)據(jù)完整性的威脅[6]。

針對RFID 技術(shù)中的數(shù)據(jù)沖突及其碰撞現(xiàn)象，文獻[7,8]提出了各種各樣的改進算法。

本文提出了一種動態(tài)二進制樹防碰撞的改進算法，并對其進行了仿真研究。

1 基本二進制樹防碰撞算法原理

為實現(xiàn)此算法，在此規(guī)定兩個將要使用的指令：

1）請求指令Request(SN)：此指令自帶有一個參數(shù)SN，當(dāng)電子標(biāo)簽（ET）接收到閱讀器發(fā)出的Request 指令后，自動將其序列號與接收到的SN 值進行比較。若自身序列號的值不大于閱讀器發(fā)出的SN 值，ET便將自己的序列號饋送給閱讀器。

2）休眠指令Sleep(SN)：該指令亦帶一個參數(shù)SN，當(dāng)ET 接收到閱讀器發(fā)送的此指令后， 迅速將自己的序列號與接收到的SN 值比較。如自己序列號與接收到的SN 值相等，則該ET 被識別出來，開啟休眠模式，從此不再響應(yīng)系統(tǒng)發(fā)出的Request 指令，除非重新上電。

基本二進制樹防碰撞算法流程如圖1 所示：

圖1 基本二進制樹算法流程

根據(jù)圖1 所示流程，閱讀器即可按照序列號從小到大的順序挨個識別出所有在閱讀器識別范圍內(nèi)的所有電子標(biāo)簽(ET)。

2 防碰撞算法的改進研究

下面對二進制防碰撞算進行改進，改進后的算法步驟為：

Step1： 初始化SN，使SN 值最大。

Step2：閱讀器發(fā)送Request 指令，此指令附帶一個參數(shù)SN，設(shè)該參數(shù)的長度x，ET 在接收到指令后， 首先將自己序列號中的高1～x 位與接收到的Request 指令中參數(shù)SN 的大小進行比較， 若不大于接收到的參數(shù)SN，則將該ET 剩余位發(fā)送至閱讀器。

Step3：閱讀器依據(jù)曼徹斯特編碼法則檢測出最高及次高碰撞位。若發(fā)生碰撞， 找出最高及次高碰撞位， 將最高及次高碰撞位分別置00、10、01、11，然后依次執(zhí)行Step2；否則讀取該標(biāo)簽信息，而后執(zhí)行Step4。

Step4：閱讀器向成功識別的標(biāo)簽發(fā)送休眠指令sleep，使ET 進入休眠模式，直至重新上電。然后，采取后退策略從上一層碰撞節(jié)點取得下一次Request 所需參數(shù)。

Step5：返回Step2，直到成功識別出所有

3 仿真實驗

運用MATLAB 分別對各種算法的搜索次數(shù)、 搜索時間進行仿真研究，仿真結(jié)果如圖2 所示。

圖2 各種算法搜索次數(shù)的比較（標(biāo)簽為8 位）

從圖2 可以看出，就搜索次數(shù)而言，基本二進制樹算法與動態(tài)二進制樹算法基本相同，而改進算法比基本二進制樹算法、動態(tài)二進制樹算法和后退式算法均要少點些，但其優(yōu)勢并不顯著。

各種算法搜索時間與搜索次數(shù)的對比基本一致，由于搜索次數(shù)要少一些，所以改進算法的耗時要比后退式算法短一些，但后退式算法的耗時與改進算法的耗時差異很小。

4 結(jié)論

分析了動態(tài)二進制樹防碰撞算法的基本原理，提出了動態(tài)二進制樹防碰撞的改進算法。 運用MATLAB 對不同防碰撞算法的搜索時間及搜索次數(shù)進行了仿真，仿真結(jié)果表明，改進算法縮短了搜索時間、減少了搜索次數(shù)。

［1］蕭耀友,等.基于二進制樹分解的動態(tài)防碰撞算法[J].通信技術(shù),2011,1(44)：99-108.

［2］Myung, Jihoon Lee, Wonjun, Srivastava, Jaideep. Adaptive binary splitting for efficient RFID tag anti-collision[Z]. IEEE Communications Letters. 2006.

［3］孫耀磊,等.一種改進的四叉樹RFID 防碰撞算法[J].計算機工程與應(yīng)用,2014,50(4)：63-68.

［4］RYU J, LEE H, SEOK Y, etal. A hybrid query treeprotocol for tag collision arbitration in RFID systems[Z]. Proceedings of IEEE InternationalConference on Communications. 2007.

［5］周紅妹,等.一種改進的二進制防碰撞算法[J].常州大學(xué)學(xué)報,2013,25(4)：48-51.

［6］KIM Y, KIM S, LEE S, etal. Improved 4-ary query tree algorithm for anticollision in RFID system [Z]. International Conference on Advanced Information Networking and Applications. 2009.

［7］SEOL J H, KIM S W. Collision-resilient multi-state query tree protocol for fast RFID tag identification[Z]. Computational Intelligence and Security . 2006.

［8］夏小勤,胡佳佳.基于動態(tài)樹形RFID 防碰撞算法的研究[J].科技廣場,2014(03).