一種改進(jìn)的融合型RFID防碰撞算法研究

湖南科技大學(xué)信息與電氣工程學(xué)院 郭 艷 唐志軍 劉 權(quán)

1 引言

RFID技術(shù)主要是通過無(wú)線電通信，自動(dòng)識(shí)別并讀取相關(guān)射頻信息，UHF(無(wú)源超高頻)RFID系統(tǒng)自身的優(yōu)點(diǎn)很多：成本小，掃描卡反應(yīng)快，識(shí)別時(shí)間短，使用壽命長(zhǎng)，重量輕，體積小，一般無(wú)磨損，不需要保養(yǎng)維護(hù)[1]。

目前很多國(guó)家都關(guān)注物聯(lián)網(wǎng)RFID防碰撞技術(shù)，改進(jìn)算法也層出不窮。從工程應(yīng)用角度出發(fā)，防碰撞算法有很多，目前普遍使用得有以下三種：基于二進(jìn)制樹的確定型算法、基于Aloha的概率型算法和基于Aloha和二進(jìn)制樹的融合型算法[2]，本文主要分析和改進(jìn)基于ALOHA和二叉樹的融合型防碰撞算法的優(yōu)缺點(diǎn)、性能穩(wěn)定性及其適用條件。

2 改進(jìn)算法基礎(chǔ)

RFID防碰撞算法最常用TDMA（時(shí)頻多址）方式，它簡(jiǎn)單、高效，按時(shí)間把所有通信容量分給多個(gè)用戶，所以RFID系統(tǒng)防碰撞算法中使用最頻繁[3]。

電子標(biāo)簽通過無(wú)線電識(shí)別后進(jìn)行通信，同時(shí)確認(rèn)讀寫器的讀寫或“睡眠”狀態(tài)，整個(gè)識(shí)別過程中為了避免多目標(biāo)識(shí)別產(chǎn)生碰撞形成了防碰撞算法[4]。

二叉樹算法是根據(jù)估算的幀長(zhǎng)進(jìn)行分組，因?yàn)楫?dāng)大量標(biāo)簽同時(shí)出現(xiàn)時(shí)，采用鎖位后退二叉樹搜索算法[4]，當(dāng)幀長(zhǎng)相應(yīng)增大，標(biāo)簽識(shí)別時(shí)間將明顯縮短，并占用較少的存儲(chǔ)空間；而實(shí)際應(yīng)用時(shí)，標(biāo)簽中的寄存器所占位數(shù)都是8位[5]，采用具有唯一性的UID編碼方式，按實(shí)物標(biāo)簽代碼、序列號(hào)最高位進(jìn)行分組，可以有效實(shí)現(xiàn)。

動(dòng)態(tài)幀時(shí)隙算法中標(biāo)簽數(shù)據(jù)傳送時(shí)，將多個(gè)時(shí)間段組成一個(gè)時(shí)隙，又將若干個(gè)時(shí)隙組合成一幀，幀的大小由RFID系統(tǒng)動(dòng)態(tài)調(diào)整，讀寫器隨機(jī)產(chǎn)生一個(gè)時(shí)隙并發(fā)送給標(biāo)簽，同時(shí)，標(biāo)簽內(nèi)的時(shí)隙計(jì)數(shù)器會(huì)根據(jù)具體情況進(jìn)行加1，直到時(shí)隙計(jì)數(shù)值與幀內(nèi)時(shí)隙數(shù)相等時(shí)，標(biāo)簽開始發(fā)送數(shù)據(jù)信息，在此過程中有效避免了碰撞現(xiàn)象的發(fā)生。

3 BTDFSA算法分析

本文提出的改進(jìn)算法，是在二叉樹和動(dòng)態(tài)幀時(shí)隙Aloha算法的基礎(chǔ)上改進(jìn)的融合型（BTDFSA）算法,思路是先確定估算幀長(zhǎng)，再采用動(dòng)態(tài)幀時(shí)隙Aloha區(qū)分空閑時(shí)隙和碰撞時(shí)隙，同時(shí)用二叉樹算法按位識(shí)別標(biāo)簽信息，詳細(xì)步驟為：

步驟1：在RFID系統(tǒng)查詢范圍內(nèi)初始化幀長(zhǎng)，用估算法預(yù)設(shè)標(biāo)簽數(shù)，采用二叉樹算法根據(jù)某一實(shí)物標(biāo)簽代碼、序列號(hào)最高位，即電子標(biāo)簽到讀寫器方向的數(shù)據(jù)傳輸采用曼徹斯特 (Machester) 編碼方式實(shí)現(xiàn)估算幀長(zhǎng)[5]，因其具有較強(qiáng)的編碼檢錯(cuò)能力，所以數(shù)據(jù)傳輸過程中容易找到標(biāo)簽碰撞位；

步驟2：發(fā)送問詢命令，查詢序列號(hào)前綴長(zhǎng)度，并判定前綴后加0的標(biāo)簽是否響應(yīng)，如果響應(yīng)繼續(xù)下一個(gè)操作步驟，否則判定前綴最后一位為1的標(biāo)簽是否響應(yīng)，不響應(yīng)標(biāo)簽則進(jìn)入休眠狀態(tài)；

步驟3：時(shí)隙位隙按位匹配，對(duì)標(biāo)簽進(jìn)行動(dòng)態(tài)幀時(shí)隙識(shí)別，發(fā)送問詢命令，選擇時(shí)隙，并按位查詢,確認(rèn)有無(wú)碰撞發(fā)生，有則開始下一步問詢，無(wú)則進(jìn)入步驟4；

步驟4：應(yīng)答器時(shí)隙計(jì)數(shù)器加1，碰撞時(shí)隙計(jì)數(shù)器減1，進(jìn)入下一輪問詢；

步驟5：發(fā)送確認(rèn)信息和循環(huán)指令，直至所有標(biāo)簽識(shí)別完成，即空閑時(shí)隙和碰撞時(shí)隙數(shù)均為0，再根據(jù)標(biāo)簽信息處理讀寫器，結(jié)束。

4 仿真分析

仿真實(shí)驗(yàn)得出以下結(jié)論：

（1）當(dāng)標(biāo)簽數(shù)N為68時(shí)，獲得吞吐率最大值0.693，標(biāo)簽數(shù)取其它值時(shí)也能使預(yù)測(cè)檢驗(yàn)算法吞吐率穩(wěn)定在0.36左右。

（2）解調(diào)RFID信號(hào)時(shí)，隨著信噪比的降低，正確估計(jì)概率會(huì)有所下降，估計(jì)性能也逐漸變差， 跳周期的正確估計(jì)概率隨信噪比的變化趨勢(shì)明顯增大。

（3）經(jīng)對(duì)照分析，改進(jìn)的融合型算法性能有所提升，可以有效解決RFID系統(tǒng)標(biāo)簽防碰撞問題。與其它三種算法（DFSA：動(dòng)態(tài)幀時(shí)隙算法，GDFSA：分組動(dòng)態(tài)幀時(shí)隙算法，F(xiàn)GDFSA：預(yù)測(cè)校驗(yàn)動(dòng)態(tài)幀時(shí)隙Aloha算法）相比,改進(jìn)的融合型算法(BTDFSA)的標(biāo)簽數(shù)據(jù)通信量比較高，如表1所示，通信復(fù)雜度比較低，如表2所示：

表1 四種算法的通信量比較值（bps）

表2 四種算法的通信復(fù)雜度比較值

5 結(jié)束語(yǔ)

UHF RFID系統(tǒng)實(shí)際應(yīng)用射頻卡時(shí)，成功識(shí)別實(shí)物多標(biāo)簽并解決其碰撞問題，是RFID系統(tǒng)的關(guān)鍵技術(shù)之一，也是物聯(lián)網(wǎng)發(fā)展的核心環(huán)節(jié)。本文提出的改進(jìn)型融合算法，識(shí)別標(biāo)簽的有效編碼，利用二叉樹算法對(duì)標(biāo)簽進(jìn)行時(shí)隙按位匹配，在硬件方面比較容易實(shí)現(xiàn)。在后續(xù)工作中，將探尋如何進(jìn)一步優(yōu)化RFID系統(tǒng)標(biāo)簽防碰撞不確定型算法的性能。

[1]王倩.物聯(lián)網(wǎng)+傳統(tǒng)產(chǎn)業(yè)是如何被改造的[J].商學(xué)院,2015(12):50-52.

[2]周少珂,鄧淼磊.ALOHA標(biāo)簽防碰撞算法綜述[J].計(jì)算機(jī)工程與應(yīng)用,2017,53(14):9-17.

[3]陳春明,馮玉田,付良成.RFID動(dòng)態(tài)幀時(shí)隙防碰撞改進(jìn)算法研究[J].電子技術(shù)應(yīng)用,2013,39(1):86-92.

[4]He Y,Wang X.An ALOHA-based improved anti-collision algorithm for RFID systems[J].IEEE Wireless Communications,2013,20(5):152-158.

[5]Xu Y,Chen Y.An improved dynamic framed slotted ALOHA Anti-collision algorithm based on estimation method for RFID systems[C].Proceedings of the IEEE International Conference on RFID,2015.

[6]董昌.RFID閱讀器的軟件設(shè)計(jì)及防碰撞算法研究[D].浙江理工大學(xué),2016.

[7]嚴(yán)利輝,史長(zhǎng)瓊,陳蓉等.基于奇偶分組的多周期RFID標(biāo)簽防碰撞算法[J].計(jì)算機(jī)工程,2016,42(2):312-315.

[8]袁開國(guó),郝昱文,李爭(zhēng)平等.RFID網(wǎng)絡(luò)中基于Aloha防碰撞的標(biāo)簽數(shù)目的聯(lián)合估計(jì)算法[J].北京郵電大學(xué)學(xué)報(bào),2014,37(4):72-76.