單閱讀器移動RFID系統下改進的標簽防碰撞算法

李欣怡 李曉武 游進國 賈連印 丁家滿 李潤鑫

（昆明理工大學信息工程與自動化學院）

隨著社會的發展，物聯網技術已逐步滲透到人們的生活中，它使物體和機械能夠互聯并共享收集到的信息［1］。 射頻識別技術（RFID）作為物聯網技術的感知層，發揮著重要的作用。在RFID 識別過程中，閱讀器識別區域內有若干標簽隨機分布， 當一個以上的標簽同時與閱讀器進行通信時，它們的反向散射信號相互抵消，導致閱讀器不能獲取任何信息，這被稱為碰撞。 在沒有任何機制或措施協調閱讀器和標簽之間通信過程的情況下，閱讀器將無法正確讀取標簽ID 號，那么此次識別過程失敗，進入再次識別過程，一直重復以上步驟，直到閱讀器識別范圍內的所有標簽都被成功識別為止［2］。

目前常用的標簽防碰撞算法主要分為兩類，分別是基于樹的確定性防碰撞算法和基于ALOHA 的隨機性防碰撞算法［3］。基于樹的確定性防碰撞算法識別效率較高，但由于要遍歷所有標簽，所花時間較長；基于ALOHA 的隨機性防碰撞算法雖然簡單，但是容易產生“標簽饑餓”現象，隨著標簽數量的增多，系統吞吐率也逐步下降。

筆者提出一種將兩類算法相結合的方法，整合了兩類算法各自的優勢，同時使用尾碼應答機制減少傳輸所需的時間成本，將該方法應用于單閱讀器移動RFID 系統中， 通過理論分析和MATLAB 仿真實驗驗證，改進后的算法能降低時間成本，使系統性能有一定提高。

1 單閱讀器移動RFID 系統

單閱讀器移動RFID 系統是單個閱讀器采用移動方法去識別一個區域內標簽的系統［4］。 這種單閱讀器移動RFID 系統只適用于中小型區域的標簽識別，因為如果待識別區域過大，那么通過移動閱讀器讓大區域內的標簽都能進入閱讀器信號區并被識別需要花費較多的時間［5］。 該系統的模型如圖1 所示，待識別區域A 內隨機分布著若干待識別的標簽，閱讀器識別區域為P，使用者手持單閱讀器沿固定路徑移動識別標簽。

圖1 單閱讀器移動RFID 系統場景

在本文的識別過程中，采用尾碼應答機制可以減少傳輸時間成本，標簽不需要發送完整的ID號給閱讀器，只需要發送小長度尾碼即可。

2 RFID 系統中傳統的標簽防碰撞算法

2.1 幀時隙ALOHA（FSA）算法

幀時隙ALOHA 算法在時隙ALOHA 算法的基礎上引入了幀的概念，其主要思想是：將若干個時隙組成一個幀，幀指的是閱讀器兩次請求操作之間的時間間隔， 標簽只能隨機在0-L-1 內選擇一個時隙和閱讀器進行通信。 該協議的時隙存在3 種情況：空閑時隙,即沒有標簽進行響應；碰撞時隙， 在某個時隙有大于一個的標簽同時對閱讀器進行響應，就會產生標簽信息的碰撞［6］；成功時隙，有且僅有一個標簽響應，閱讀器能成功讀取到標簽信息。 未被成功識別的標簽，需要在下一輪中重新進行識別。

下面舉例對該算法進行說明，設幀長L 為3，待識別區域內有5 個標簽。 表1 是幀時隙ALOHA 算法的工作過程。

表1 幀時隙ALOHA 算法工作過程

2.2 動態幀時隙ALOHA（DFSA）算法

動態幀時隙ALOHA 算法是在幀時隙ALOHA 算法上改進得來的，幀時隙ALOHA 算法中，由于幀長固定不變，當標簽數量和幀長相差較大時，系統性能很差。動態幀時隙ALOHA 算法中，如果使幀長和標簽數量近似相等，系統吞吐率能維持在最大值。 具體解決辦法是根據預估標簽數量動態調整下一幀幀長，如果該幀中碰撞時隙較多，那么增加下一幀的幀長，反之減小下一幀的幀長。

2.3 二進制搜索（BS）算法

二進制搜索算法采用比特沖突檢測協議作為防碰撞方案［7］。 閱讀器以二進制序號為參數向標簽發送請求命令，收到命令的標簽將自己的序號與閱讀器發送的序號作比較，如果自己的序號小于等于閱讀器發送的序號，就將自己的編碼發送給閱讀器，閱讀器逐位識別相應的標簽［8］。如果標簽之間發生碰撞，閱讀器根據碰撞位減小序號繼續搜索；如果標簽之間沒發生碰撞，則成功識別到一個標簽，閱讀器以初始序號為參數重新開始搜索，直至所有標簽搜索完畢。

2.4 后退式二進制搜索（BBS）算法

后退式二進制搜索算法是二進制搜索算法的一種改進。 改進的思路是：當一個標簽成功被識別后，閱讀器不會返回到原始的碰撞節點繼續搜索，它將退回到節點的上層，即父節點［9］。

假 設 有 4 個 標 簽:Tag1 10110010，Tag2 10100011，Tag3 10110011，Tag4 11100011。后退式二進制搜索算法識別流程如圖2 所示。

圖2 后退式二進制搜索算法識別流程

3 單閱讀器移動RFID 系統下FSA 和BBS 結合的標簽防碰撞算法

3.1 算法流程

工作原理為：在待識別區域內，手持單閱讀器沿固定路徑對標簽進行識別。 閱讀器發送讀取標簽尾碼指令，在應答區域內的標簽生成一個小于等于幀大小的隨機數，隨機時隙數為0 的標簽將自己的尾碼發給閱讀器。

RFID 閱讀器以幀時隙ALOHA 算法接收標簽發送過來的尾碼，閱讀器有3 種響應情況：

a. 空閑時隙（slot_idle）。 信號區內沒有標簽尾碼選擇該時隙與閱讀器進行通信，閱讀器讀取不到任何信息。

b. 成功時隙（slot_succ）。 信號區內只有一個標簽尾碼選擇該時隙與閱讀器進行通信，閱讀器能成功讀取到該標簽尾碼信息。 閱讀器將該尾碼與尾碼表進行比較， 如果該尾碼未在尾碼表中，則該標簽為全新標簽，閱讀器發送讀取剩余信息的指令， 收到剩余信息后進行整合并置靜默；若該尾碼已出現在尾碼表中，則將該標簽判定為已識別標簽，不作任何處理。

c. 碰撞時隙（slot_coll）。 信號區內多個標簽尾碼選擇該時隙與閱讀器進行通信，標簽尾碼之間發生碰撞，此時閱讀器采用BBS 算法對碰撞時隙的各個標簽進行處理，閱讀器通過對尾碼的編號進行按位搜索，收到命令的標簽尾碼將自己的序號與閱讀器發送的序號進行對比，如果小于等于閱讀器發送的序號，則將自己的尾碼序號發給閱讀器，若繼續發生碰撞，閱讀器減小序號繼續搜索；若沒發生碰撞，閱讀器成功識別一個標簽尾碼，對成功識別的標簽尾碼處理步驟和成功時隙一樣， 直至碰撞時隙的所有標簽處理完畢，進入下一個時隙，碰撞時隙處理流程如圖3 所示。

圖3 改進算法碰撞時隙處理流程

3.2 系統性能分析

3.2.1 幀時隙ALOHA 算法性能分析

在幀長為64 的一幀中，各時隙的概率如圖4所示。

圖4 各時隙概率圖

系統效率為：

系統所需時隙數為：

對式（5）求導可得，當待識別標簽n 與幀長N 近似相等時，系統獲得最大吞吐率。 這意味著可以通過設置幀長來優化瞬時吞吐率［10］。

3.2.2 后退式二進制搜索算法性能分析

在BBS 算法中，假設待識別區域內有n 個標簽，算法完成對n 個標簽的搜索需要的次數為S（n），計算如下：

成功識別所有標簽的系統效率為：

3.2.3 改進算法性能分析

整個標簽的產品電子代碼 （EPC 碼） 為64位，傳輸識別整個標簽需要1 時隙，文中取16 位的尾碼，則傳輸識別標簽尾碼只需0.25 個時隙。

設待識別區域內的標簽數量為n，幀長為N，尾碼長為L_suffix，尾碼重復出現的概率為：

計算可得， 當尾碼長16 位、 標簽數為100時，尾碼重復出現的概率僅0.072 78%。 在本文中一個尾碼傳輸并識別只需要花費0.25 個時隙，為了更直觀地比較系統性能，在改進算法中由于重復識別而浪費的時間忽略不計。 而重復出現的尾碼中為不同標簽的概率更低，因此在文中重復出現的標簽判定為已識別標簽。

每次成功時隙識別一個標簽，則碰撞時隙處理的標簽數為：

其中，n_coll 為碰撞時隙處理的標簽數，n_succ 為成功時隙處理的標簽數。

碰撞時隙的標簽用后退式二進制搜索算法進行處理， 處理所有碰撞時隙標簽所需的時間為：

則改進算法所需要的時間成本為：

改進算法的系統效率為：

3.3 改進算法仿真結果分析

采用MATLAB 進行仿真實驗， 標簽數為500，標簽EPC 碼為64 位，每次傳輸識別一個標簽需要1 個時隙。 DFSA 算法中初始幀長為256，用Schoute 估算法預估標簽數量； 改進算法中采用固定幀時隙幀長為256，尾碼為16 位，每次傳輸識別一個標簽尾碼需0.25 個時隙。

不同算法時間成本對比如圖5 所示。

圖5 不同算法時間成本對比

由圖5 可以看出， 識別相同數量的標簽，改進算法所需的時間成本比傳統單一算法低很多。

不同算法系統效率對比如圖6 所示。

圖6 不同算法系統效率對比

由圖6 可以看出， 識別相同數量的標簽，動態幀時隙ALOHA 算法的系統效率僅為30%左右， 后退式二進制搜索算法的系統效率保持為50%左右， 而改進算法的系統效率最高可達60%，且一直保持在50%以上。

4 結束語

在分析幀時隙ALOHA 算法和后退式二進制搜索算法的基礎上，將兩類算法結合在單閱讀器移動RFID 系統中使用。 改進算法吸取了幀時隙ALOHA 算法識別時間較短和后退式二進制搜索算法標簽識別率高的優勢，使用尾碼應答機制減少時間成本。 通過對改進算法的仿真，單閱讀器移動RFID 系統所花費的時間成本有所下降，而系統效率有一定提升。