紡織物資管理中的RFID標簽防碰撞算法研究

陳青　陳永當　程云飛　閔渭興

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

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

中圖分類號： TP391 文獻標識碼： A 文章編號： 2095-2457（2019）31-0069-002

DOI：10.19694/j.cnki.issn2095-2457.2019.31.031

0 引言

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

1 基于位隙分組的動態退避式二進制搜索（BGDRBS）算法

1.1 算法原理

本文算法旨在減少閱讀器查詢次數和數據傳輸量，提高系統的識別效率。因此，在退避式二進制搜索算法的基礎上結合動態查詢思想，并且引入標簽分組：

假定待識別標簽數為n，標簽位隙長度為L，p=1L，通過位隙分組后：

一組內有r個標簽的概率為：

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

可知，含有r個標簽的組的期望值為：

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

則，分組后的平均標簽個數為：

n■■=■（3）

由公式（3）可知，位隙長度L取值越大，平均分到各組的標簽數就越少，從而提高了識別效率，但同時也提高了標簽成本，所以位隙長度要根據RFID系統的實際應用情景來設置。

1.2 算法實現流程

本算法需要建立新的查詢指令：Request（R+B）——初始查詢，閱讀器發送查詢命令，所有序列號小于或等于查詢序列號的標簽響應，并隨機選擇自己的位隙;Request（R+BR）——組內查詢，只有位隙值等于BR的標簽才會響應。其中R參數為查詢序列號，B參數為位隙值，BR參數為查詢位隙值。

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

（2）如果B為0，則說明無標簽存在，跳轉至（8）。否則，找到B中為1的最低位，讓BR對應的值為1，其他位為0，形成該組的查詢BR，并將B的最低位清零。

（3）閱讀器發送組內查詢指令Request（R+BR），R的初始值為全1，所有B等于BR的標簽響應，將各自的序列號傳送回閱讀器，若沒有收到響應信號，則說明本組內已無未識別的標簽，跳轉至（2）。否則，繼續。

（4）閱讀器檢查標簽返回的序列號，如果能識別，則跳轉至（6）。如果出現碰撞位，繼續下一步。

（5）閱讀器將當前查詢序列號壓棧，把碰撞的最高比特位置0，高于最高碰撞比特位不變，再輸出查詢前綴碼，跳轉至（4）。

（6）根據識別出的標簽序列號，執行選取指令Select（R），使該標簽進入讀取狀態，隨后閱讀器再發送讀取指令Read-data，對處于讀取狀態的標簽進行數據讀取，數據讀取完成后，發送去選擇指令Unselect，使該標簽轉為去激活狀態，對此后閱讀器的指令不再響應。

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

（8）回到流程（3）。

（9）結束。

其中步驟（1）、（2）是通過位隙分組實現標簽的分組查詢，步驟（3）～（8）是通過動態查詢與節點退避實現標簽的組內識別。

2 算法仿真與分析

應用MATLAB軟件分別對DBS算法、RBS算法和本文算法進行實驗仿真，實驗的標簽數目范圍為[1，100]，標簽ID為16位，位隙長度為16。為了確保實驗的準確性，取100次仿真結果的平均值。系統的數據傳輸量與吞吐率是衡量RFID系統識別效率的重要指標。如圖1和2，標簽分組使得各組平均識別標簽數較總標簽數少了很多，從而降低了數據傳輸量，提高了系統吞吐率。

圖1 數據傳輸量的比較

圖2 吞吐率的比較

3 結語

針對紡織物資管理系統中RFID標簽碰撞問題，設計了一種基于位隙分組的動態退避式二進制搜索（BGDRBS）算法。在閱讀器識別前，先對標簽進行分組處理，再運用動態查詢和節點退避的查詢思想逐組識別所有標簽。仿真結果顯示，BGDRBS算法的識別效率有了明顯的改進，且算法簡單易實現，能進一步推動紡織行業企業信息化的發展。

【參考文獻】

[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]楊衡亮.紡織企業倉庫管理系統的設計及應用[J].棉紡織技術，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]張小紅，張佳琦.基于幀時隙的RFID系統迫零預編碼防碰撞算法研究[J].信息網絡安全，2018（02）：34-39.

[5]王丹，趙凱.基于距離預測分組的ALOHA算法[J].南京理工大學學報，2018，42（01）：102-106.

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