無線射頻識別系統中的標簽防碰撞算法綜述

摘 要：由于應用環境的要求，閱讀器或標簽必須要進行防碰撞處理。同時防碰撞算法的優劣直接關系到標簽與閱讀器通信性能的好壞。所以防碰撞算法的研究對擴展物聯網的應用非常必要。本文講述了現今存在的標簽防碰撞算法，包括二進制樹系列算法、ALOHA系列算法和標簽估計算法，并指出算法的研究方向。

關鍵詞：標簽；二進制數；ALOHA；標簽估計

中圖分類號：TP391.44 文獻標識碼：A 文章編號：1674-7712 （2014） 18-0000-02

RFID（Radio Frequency Identification），即射頻身份鑒別，由閱讀器和標簽組成。利用無線電波在無人工干預條件下能夠實現多目標自動識別，已被廣泛用于生產銷售、物流配置、交通運輸、醫療器具、國防科技等各個行業。

由于單個閱讀器讀取范圍有限，所以很多應用中使用多個閱讀器來識別目標區域中的多個標簽。碰撞是指多個標簽或多個閱讀器間相互干擾，使得標簽或閱讀器無法正確接收到閱讀器或標簽發送來的信號，可分為由多個閱讀器同時發送信息給標簽引起標簽無法正確與閱讀器通信的閱讀器碰撞和由多個標簽同時與閱讀器通信引起的閱讀器無法正確識別標簽的標簽碰撞兩大類。而針對這兩種碰撞所采取的應對措施，分別稱為閱讀器防碰撞算法和標簽防碰撞算法。本文主要介紹無線射頻識別系統中的標簽防碰撞算法。

一、標簽防碰撞算法

按照碰撞時標簽響應方式，防碰撞算法可分為確定性算法和不確定性算法。目前，確定性算法大多基于樹結構算法，而不確定性算法大多是基于ALOHA算法。

（一）基于樹結構算法

系統識別的可靠性較高，大多基于二進制樹。當閱讀器接收到標簽發送的ID信息遇到碰撞時，將標簽分支成兩個子集進行通信，如再遇碰撞再分支成兩個子集，這些子集分支會越來越小，一直到分支下面只有一個標簽與其通信時，完成一次識別，再返回最近的另一個子集與標簽通信，如此遞歸完成所有標簽的識別。

1.基本二進制樹算法

基本二進制樹搜索算法中閱讀器首先發送指令給標簽，標簽通過比較接收序列號與自身序列號，如果小于等于，則發送自己的ID給閱讀器，否則等待。直到識別某個標簽后讓其進入休眠狀態，又重新搜索。此算法是所有二進制樹搜索算法的基礎，閱讀器與標簽的每次通信時間受標簽ID的長短的控制。

基本的樹分裂算法也為閱讀器先說型，即閱讀器首先向其作用場內標簽發送查詢指令，然后標簽做出響應。當標簽響應信息產生沖突時，閱讀器會命令標簽生成一位二進制數（“0”或“1”），將場內標簽分為兩個子集，其中一個子集先響應。若碰撞，再分子集。子集分支越來越小，一直到分支下面只有一個標簽與其通信時，完成一次識別，再返回最近的另一個子集與標簽通信，如此遞歸完成所有標簽的識別。

2.改進二進制搜索算法

現有的二進制防碰撞搜索算法選用曼徹斯特編碼以確定碰撞位的準確信息，進而閱讀器可以根據碰撞的位置，重新搜索標簽。

返回式二進制防碰撞算法規定閱讀器在收到標簽返回信息檢查碰撞位，下次通信時尋找第一位碰撞位上為0的標簽，并讓其響應；閱讀器如果收到標簽返回信息又有碰撞，那么又搜索此次返回信息第一碰撞位為0的標簽，直到識別到標簽，然后將搜索最開始一次碰撞位為1的標簽；若遇碰撞，則搜索此次第一碰撞位為0的標簽，直到所有位碰撞位都搜索完，再搜索第二碰撞位上為1的標簽，如此，直至所有標簽都被識別。此算法不會在每次識別到標簽后就又開始新一輪的搜索，而是基于其父節點進行搜索，故而系統的識別效率有所提高。修剪枝二進制搜索算法利用二進制搜索法順利讀出第一個標簽后，并不返回第一個碰撞位，而是采用就近原則，返回到最近一級的碰撞位，將碰撞位取反獲得新的ID進行搜索，等搜索成功后再返回更上一級碰撞位[1]。修剪枝二進制搜索算法由于返回就近，并非返回父節點，故而所需時間更短，但程序較為復雜，適用于標簽數量較多且ID較長的場合。文獻[2]提出一種基于后退式二進制防碰撞搜索算法：在原有后退式二進制防碰撞搜索算法的基礎上增加了休眠狀態，并將不參與發送數據的標簽轉為休眠狀態，減少了標簽不必要的信息比對。

動態二進制樹防碰撞算法在基本二進制搜索算法的基礎上，規定標簽不需要每次都返回完整的信息，而是返回碰撞位以后部分。由于標簽與閱讀器的通信位數變少，使得此算法中閱讀器與標簽的通信時間少于基本的二進制搜索算法。

文獻[3]中提出了一種四叉樹RFID防碰撞算法，將碰撞位兩位為一組，由于兩位二進制具有四種組合，所以可使其構成一個四叉樹進行搜索。

3.改進的二進制分裂算法

自適應二進制分裂算法要求閱讀器和標簽都有計數器，分別用于對進展時隙數計數和對分配時隙數計數。相對于基本的樹分裂算法，當碰撞時，分組不再是兩組，而是標簽產生一個隨機數，當當前時隙與隨機數相同時標簽響應，否則標簽不響應。利用此算法識別完標簽后，理論上場內所有標簽都有唯一的分配時隙與其對應，但是此算法識別標簽的能力受閱讀器最大分配時隙數的限制。

（二）ALOHA系列算法

總體而言，基于樹的算法硬件設計較為復雜。故而，在考慮低成本時，RFID標簽一般是基于ALOHA系列算法設計。而如何提高該防碰撞算法系統識別的可靠性便成為目前低成本RFID標簽應用系統的一個研究重點。

1.基本ALOHA算法

基本ALOHA算法采用標簽先發言，即一旦標簽進入閱讀器場內，便向閱讀器發送自身ID?？赡軙霈F標簽完全碰撞和標簽部分碰撞。若碰撞，閱讀器命令標簽隨機等待一段時間再次發送信息。此算法實現簡單，但在標簽數量少或閱讀器與標簽之間信息較小時，傳輸信道大部分時間都處于空閑狀態；而在標簽數量多或閱讀器與標簽之間信息較大時，標簽群之間的碰撞嚴重。故而，ALOHA在多標簽環境下的標簽碰撞往往會造成鏈路的吞吐率較低，最高可為18.4%。

2.時隙ALOHA算法和幀時隙ALOHA算法

時隙ALOHA算法是在純ALOHA算法的基礎上，規定標簽只能在每個時隙開始的時候才能夠向讀寫器發送自己的信息，這樣避免了多標簽環境下的部分碰撞，使吞吐率提高一倍，但此算法在標簽數量比較大的時候系統的效率還是很低。幀時隙ALOHA算法將信道分成m個幀，標簽選擇一幀當中的一個時隙來與讀寫器進行通信。

3.動態幀時隙ALOHA算法

時隙ALOHA算法和幀時隙ALOHA算法，由于標簽處于流動狀態而數目不定，所以從始至終固定時隙會使效率低下，從而有了動態幀時隙ALOHA算法。

動態幀時隙ALOHA算法是在幀時隙ALOHA算法的基礎上，為了避免鏈路中空時隙太多而影響整個鏈路中的讀取延遲，根據每次讀取過程中時隙的類型（分為空時隙、碰撞時隙和單標簽時隙），對讀寫器射頻場內的標簽估計，從而設定每幀中時隙總數。

現存的標簽估算中分為三種：有利用碰撞時隙總數乘以2的最小剩余標簽預測法、的利用實際各種時隙數和預測的各種時隙數的來估計剩余標簽和Schout提出的利用碰撞時隙乘以2.39來估算剩余標簽。

4.隨機槽時隙防碰撞算法

ISO18000-6C協議中閱讀器與標簽通信時采用隨機槽時隙防碰撞算法（Random-slotted collision arbitration），即標簽根據閱讀器向標簽發送的Q值（時隙因子）產生隨機數，并由隨機數決定在哪個時隙向閱讀器發送信息；而Q值初值為4，然后根據標簽的響應情況，動態改變時隙因子的值。

Q值的調整過程中需要注意調整因子的取值問題，即C值取值偏大會使Q值變化太快，進而時隙總數變化過快；C值取值偏小會使Q值變化會遲鈍，進而時隙總數變化過慢。Q值的調整過程中需要注意調整因子的取值問題，即C值取值偏大會使Q值變化太快，進而時隙總數變化過快；C值取值偏小會使Q值變化會遲鈍，進而時隙總數變化過慢。如果能動態調整C值，C值又根據當前Q值來確定，那么時隙總數變化也將由Q值的大小而決定，即Q值較小時C大，時隙調整的快；Q值較大時C小，調整地慢。文獻[4]中C取0.8/Q；文獻[5]中規定碰撞時C為0.14122～0.49992，空閑時C為0.100～0.354，且碰撞時的C是空閑時的1.4122倍；文獻[6]中Q與C的關系為：

Q=1時：C=0.5；Q=2時：0.33≤C<0.5；Q=3時：0.25≤C<0.33；Q=4或時：0.2≤C<0.25；Q=6或7時：0.167≤C<0.2；Q=8或9時：0.143≤C<0.167；Q=10或11時：0.125≤C<0.143；Q=12時：0.111≤C<0.125；Q>12時：0.1≤C<0.1115；

二、結束語

對于現存的兩種算法來說，二進制樹系列算法具有確定性，但是這種算法實現比較復雜；而ALOHA系列算法存在著標簽“餓死”狀況，即標簽始終沒能夠與閱讀器通信。所以在以后的研究中既要考慮算法時隙的難易性和消滅標簽的“餓死”狀況。

參考文獻：

[1]余松森，詹宜巨.基于修剪枝的二進制樹形搜索反碰撞算法與實現[J].計算機工程，2005（31）：217-219.

[2]李秉璋，景征駿，羅燁.基于后退式二進制的RFID防碰撞搜索算法[J].計算機應用與軟件，2009（26）：96-98.

[3]孫耀磊，吳曉波，陳元文.一種改進的四叉樹RFID防碰撞算法[J].計算機工程與應用，2014（04）：93-98.

[4]Behzad Razavi.Design of analog CMOS integrated circuits[M].New York，USA：McGraw-Hill，2011.

[5]吳淼，劉德盟，張釗鋒.基于EPCGen2防碰撞機制的研究與優化[J].微電子學與計算機，2013（30）：100-107.

[6]王曉梅，張英梅.基于Q值的RFID防碰撞改進算法的研究[J].太原理工大學學報，2014（45）：339-342.

[作者簡介]肖菊蘭，女，專職教師，助教，碩士研究生，研究方向：電子科學技術。