陳青　陳永當(dāng)　程云飛　閔渭興

【摘 要】目的：優(yōu)化RFID標(biāo)簽防碰撞算法從而提高紡織物資管理效率。方法：針對(duì)確定性防碰撞算法存在識(shí)別效率不高等問(wèn)題，設(shè)計(jì)一種基于位隙分組的動(dòng)態(tài)退避式二進(jìn)制搜索（BGDRBS）算法。該算法先讓標(biāo)簽隨機(jī)選擇各自的位隙，閱讀器根據(jù)標(biāo)簽返回的位隙值實(shí)現(xiàn)標(biāo)簽分組，在組內(nèi)識(shí)別中，每次查詢只發(fā)送和返回部分序列號(hào)，且無(wú)須從頭開(kāi)始。結(jié)果：仿真實(shí)驗(yàn)表明，與DBS算法和RBS算法相比，當(dāng)標(biāo)簽數(shù)達(dá)到100時(shí)，BGDRBS算法的數(shù)據(jù)傳輸量分別降低了70.55%、53.77%，吞吐率分別提高了239.41%、8.14%。結(jié)論 BGDRBS算法提高了系統(tǒng)識(shí)別效率，且簡(jiǎn)單易實(shí)現(xiàn)，在紡織物資管理中應(yīng)用前景良好。

【關(guān)鍵詞】RFID;位隙分組;防碰撞算法;MATLAB仿真;物資管理

中圖分類號(hào)： TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2019）31-0069-002

DOI：10.19694/j.cnki.issn2095-2457.2019.31.031

0 引言

無(wú)線射頻識(shí)別（radio frequency identification，RFID）是一種高效、非接觸式的自動(dòng)識(shí)別技術(shù)[1]。將RFID技術(shù)應(yīng)用到紡織物資管理中，能消除很多人為差錯(cuò)，提高工作效率，降低人力和物力的開(kāi)銷[2]。由于在閱讀器識(shí)別多個(gè)信息的過(guò)程中會(huì)發(fā)生標(biāo)簽碰撞問(wèn)題，使閱讀器不能對(duì)標(biāo)簽進(jìn)行識(shí)別，從而導(dǎo)致標(biāo)簽數(shù)據(jù)傳送失敗[3]。目前，主要的標(biāo)簽防碰撞算法有ALOHA類隨機(jī)性防碰撞算法和二進(jìn)制樹(shù)確定性防碰撞算法兩大類[4]，ALOHA類算法簡(jiǎn)單，但存在讀取率低、部分標(biāo)簽被“遺忘”等問(wèn)題，而確定性防碰撞算法可以完全讀取[5]。因此，基于RFID紡織物資管理系統(tǒng)，本文提出了一種基于位隙分組的動(dòng)態(tài)退避式二進(jìn)制搜索（BGDRBS）算法，其思想是在識(shí)別前先讓全部標(biāo)簽隨機(jī)選擇各自的位隙，閱讀器根據(jù)標(biāo)簽返回的位隙值實(shí)現(xiàn)分組識(shí)別，在組內(nèi)識(shí)別中，每次查詢只發(fā)送和返回部分序列號(hào)，且無(wú)須從頭開(kāi)始，降低識(shí)別過(guò)程的查詢次數(shù)與數(shù)據(jù)傳輸量，進(jìn)一步提高系統(tǒng)的識(shí)別效率。

1 基于位隙分組的動(dòng)態(tài)退避式二進(jìn)制搜索（BGDRBS）算法

1.1 算法原理

本文算法旨在減少閱讀器查詢次數(shù)和數(shù)據(jù)傳輸量，提高系統(tǒng)的識(shí)別效率。因此，在退避式二進(jìn)制搜索算法的基礎(chǔ)上結(jié)合動(dòng)態(tài)查詢思想，并且引入標(biāo)簽分組：

假定待識(shí)別標(biāo)簽數(shù)為n，標(biāo)簽位隙長(zhǎng)度為L(zhǎng)，p=1L，通過(guò)位隙分組后：

一組內(nèi)有r個(gè)標(biāo)簽的概率為：

P（r）=C■■p■（1-p）■（1）

可知，含有r個(gè)標(biāo)簽的組的期望值為：

E（r）=L*P（r）（2）

則，分組后的平均標(biāo)簽個(gè)數(shù)為：

n■■=■（3）

由公式（3）可知，位隙長(zhǎng)度L取值越大，平均分到各組的標(biāo)簽數(shù)就越少，從而提高了識(shí)別效率，但同時(shí)也提高了標(biāo)簽成本，所以位隙長(zhǎng)度要根據(jù)RFID系統(tǒng)的實(shí)際應(yīng)用情景來(lái)設(shè)置。

1.2 算法實(shí)現(xiàn)流程

本算法需要建立新的查詢指令：Request（R+B）——初始查詢，閱讀器發(fā)送查詢命令，所有序列號(hào)小于或等于查詢序列號(hào)的標(biāo)簽響應(yīng)，并隨機(jī)選擇自己的位隙;Request（R+BR）——組內(nèi)查詢，只有位隙值等于BR的標(biāo)簽才會(huì)響應(yīng)。其中R參數(shù)為查詢序列號(hào)，B參數(shù)為位隙值，BR參數(shù)為查詢位隙值。

（1）閱讀器向周邊標(biāo)簽發(fā)送初始查詢指令Request（R+B），R的初始值為全1，B的初始值為0、長(zhǎng)度為位隙長(zhǎng)度L，所有標(biāo)簽響應(yīng)并隨機(jī)選擇自己的位隙。假如某個(gè)標(biāo)簽選擇的位隙為n，則該標(biāo)簽位隙標(biāo)志位的第n位為1，其他位為0。隨后標(biāo)簽將生成的位隙值B傳送回閱讀器。

（2）如果B為0，則說(shuō)明無(wú)標(biāo)簽存在，跳轉(zhuǎn)至（8）。否則，找到B中為1的最低位，讓BR對(duì)應(yīng)的值為1，其他位為0，形成該組的查詢BR，并將B的最低位清零。

（3）閱讀器發(fā)送組內(nèi)查詢指令Request（R+BR），R的初始值為全1，所有B等于BR的標(biāo)簽響應(yīng)，將各自的序列號(hào)傳送回閱讀器，若沒(méi)有收到響應(yīng)信號(hào)，則說(shuō)明本組內(nèi)已無(wú)未識(shí)別的標(biāo)簽，跳轉(zhuǎn)至（2）。否則，繼續(xù)。

（4）閱讀器檢查標(biāo)簽返回的序列號(hào)，如果能識(shí)別，則跳轉(zhuǎn)至（6）。如果出現(xiàn)碰撞位，繼續(xù)下一步。

（5）閱讀器將當(dāng)前查詢序列號(hào)壓棧，把碰撞的最高比特位置0，高于最高碰撞比特位不變，再輸出查詢前綴碼，跳轉(zhuǎn)至（4）。

（6）根據(jù)識(shí)別出的標(biāo)簽序列號(hào)，執(zhí)行選取指令Select（R），使該標(biāo)簽進(jìn)入讀取狀態(tài)，隨后閱讀器再發(fā)送讀取指令Read-data，對(duì)處于讀取狀態(tài)的標(biāo)簽進(jìn)行數(shù)據(jù)讀取，數(shù)據(jù)讀取完成后，發(fā)送去選擇指令Unselect，使該標(biāo)簽轉(zhuǎn)為去激活狀態(tài)，對(duì)此后閱讀器的指令不再響應(yīng)。

（7）壓棧的序列號(hào)從堆棧中彈出[6]，作為查詢序列號(hào)，如果序列號(hào)為全1，跳轉(zhuǎn)至（3）。否則，跳轉(zhuǎn)至（4）。

（8）回到流程（3）。

（9）結(jié)束。

其中步驟（1）、（2）是通過(guò)位隙分組實(shí)現(xiàn)標(biāo)簽的分組查詢，步驟（3）～（8）是通過(guò)動(dòng)態(tài)查詢與節(jié)點(diǎn)退避實(shí)現(xiàn)標(biāo)簽的組內(nèi)識(shí)別。

2 算法仿真與分析

應(yīng)用MATLAB軟件分別對(duì)DBS算法、RBS算法和本文算法進(jìn)行實(shí)驗(yàn)仿真，實(shí)驗(yàn)的標(biāo)簽數(shù)目范圍為[1，100]，標(biāo)簽ID為16位，位隙長(zhǎng)度為16。為了確保實(shí)驗(yàn)的準(zhǔn)確性，取100次仿真結(jié)果的平均值。系統(tǒng)的數(shù)據(jù)傳輸量與吞吐率是衡量RFID系統(tǒng)識(shí)別效率的重要指標(biāo)。如圖1和2，標(biāo)簽分組使得各組平均識(shí)別標(biāo)簽數(shù)較總標(biāo)簽數(shù)少了很多，從而降低了數(shù)據(jù)傳輸量，提高了系統(tǒng)吞吐率。

圖1 數(shù)據(jù)傳輸量的比較

圖2 吞吐率的比較

3 結(jié)語(yǔ)

針對(duì)紡織物資管理系統(tǒng)中RFID標(biāo)簽碰撞問(wèn)題，設(shè)計(jì)了一種基于位隙分組的動(dòng)態(tài)退避式二進(jìn)制搜索（BGDRBS）算法。在閱讀器識(shí)別前，先對(duì)標(biāo)簽進(jìn)行分組處理，再運(yùn)用動(dòng)態(tài)查詢和節(jié)點(diǎn)退避的查詢思想逐組識(shí)別所有標(biāo)簽。仿真結(jié)果顯示，BGDRBS算法的識(shí)別效率有了明顯的改進(jìn)，且算法簡(jiǎn)單易實(shí)現(xiàn)，能進(jìn)一步推動(dòng)紡織行業(yè)企業(yè)信息化的發(fā)展。

【參考文獻(xiàn)】

[1]A.EL ALAMI，Y.GHAZAOUI，S.DAS，S.D.BENNANI，M.EL GHZAOUI.Design and Simulation of RFID Array Antenna 2x1 for Detection System of Objects or Living Things in Motion[J].Procedia Computer Science，2019，151.

[2]楊衡亮.紡織企業(yè)倉(cāng)庫(kù)管理系統(tǒng)的設(shè)計(jì)及應(yīng)用[J].棉紡織技術(shù)，2015，43（05）：29-32.

[3]Nasour Bagheri，Parvin Alenaby，Masoumeh Safkhani.A new anti‐collision protocol based on information of collided tags in RFID systems[J].International Journal of Communication Systems，2017，30（3）.

[4]張小紅，張佳琦.基于幀時(shí)隙的RFID系統(tǒng)迫零預(yù)編碼防碰撞算法研究[J].信息網(wǎng)絡(luò)安全，2018（02）：34-39.

[5]王丹，趙凱.基于距離預(yù)測(cè)分組的ALOHA算法[J].南京理工大學(xué)學(xué)報(bào)，2018，42（01）：102-106.

[6]李鋒，南敬昌，李蕾，等.后退鎖位式RFID自適應(yīng)多叉樹(shù)防碰撞算法[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（08）：102-105+164.