改進(jìn)的FRID防碰撞算法仿真研究

姚友德 馬 寧 高偉龍

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

0 引言

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

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

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

本文提出了一種動(dòng)態(tài)二進(jìn)制樹(shù)防碰撞的改進(jìn)算法，并對(duì)其進(jìn)行了仿真研究。

1 基本二進(jìn)制樹(shù)防碰撞算法原理

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

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

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

基本二進(jìn)制樹(shù)防碰撞算法流程如圖1 所示：

圖1 基本二進(jìn)制樹(shù)算法流程

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

2 防碰撞算法的改進(jìn)研究

下面對(duì)二進(jìn)制防碰撞算進(jìn)行改進(jìn)，改進(jìn)后的算法步驟為：

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

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

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

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

Step5：返回Step2，直到成功識(shí)別出所有

3 仿真實(shí)驗(yàn)

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

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

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

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

4 結(jié)論

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

［1］蕭耀友,等.基于二進(jìn)制樹(shù)分解的動(dòng)態(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］孫耀磊,等.一種改進(jìn)的四叉樹(shù)RFID 防碰撞算法[J].計(jì)算機(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ìn)的二進(jìn)制防碰撞算法[J].常州大學(xué)學(xué)報(bào),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］夏小勤,胡佳佳.基于動(dòng)態(tài)樹(shù)形RFID 防碰撞算法的研究[J].科技廣場(chǎng),2014(03).