一種改進的RFID標簽防碰撞算法*

王　彬，李俊杰，張海鵬，陳紫菱，王利丹

（杭州電子科技大學電子信息學院，杭州 310018）

一種改進的RFID標簽防碰撞算法*

王彬，李俊杰，張海鵬，陳紫菱，王利丹

（杭州電子科技大學電子信息學院，杭州 310018）

在已有RFID標簽防碰撞ALOHA算法基礎(chǔ)上，提出了一種改進的帶中斷機制的動態(tài)幀時隙ALOHA（ⅡDFSA）算法，一方面通過優(yōu)化設置系統(tǒng)效率臨界因子和參考碰撞時空比，比較系統(tǒng)效率判斷是否改變幀的大?。涣硪环矫嫱ㄟ^比較碰撞時空比來判斷幀大小的改變方向，從而有效降低標簽識別時間，提高識別效率。計算機仿真結(jié)果表明，與傳統(tǒng)的動態(tài)幀時隙ALOHA算法相比，當標簽數(shù)低于200和高于800時，采用ⅡDFSA算法可以有效降低系統(tǒng)總識別時間，提高系統(tǒng)效率。當標簽數(shù)介于200～800之間時，與傳統(tǒng)的動態(tài)幀時隙ALOHA算法相當。

射頻識別； ALOHA算法；系統(tǒng)效率臨界因子；碰撞時空比

1　引言

近年來，射頻識別技術(shù)由于其無接觸、數(shù)據(jù)容量大、傳輸速度快而得到廣泛應用。同時也引入了新的問題，例如系統(tǒng)中標簽共享無線信道，當多個標簽同時發(fā)送信號時，會引起信號之間相互碰撞，使閱讀器無法正確識別標簽。

目前，主要有兩類方法解決標簽沖突問題：一類為基于二進制搜索的確定性標簽防碰撞算法；另一類為基于ALOHA算法的隨機標簽防沖突算法。由于隨機標簽防碰撞算法具有實現(xiàn)簡單、識別速度快、受系統(tǒng)中標簽數(shù)目影響小等優(yōu)點，得到了廣泛應用。

隨機標簽防碰撞算法分為純ALOHA算法、時隙ALOHA算法（SA）、幀時隙ALOHA算法（FSA）和動態(tài)幀時隙ALOHA算法（DFSA）［1］。基于幀時隙ALOHA算法的隨機標簽防碰撞算法的工作機制如下：標簽隨機選擇一個時隙發(fā)送數(shù)據(jù)給閱讀器，當在一個時隙中有兩個或多個標簽時，閱讀器無法正確識別，等待下一幀識別過程，在下一幀中，標簽重復上述過程，直到被閱讀器成功識別。

在標簽識別的迭代過程中，當幀長度等于未識別的標簽數(shù)目時，系統(tǒng)達到最大效率，約為0.368。因此在識別過程中要估算未被識別的標簽數(shù)目，根據(jù)估算值動態(tài)改變幀的長度。目前，所使用的幾種標簽估計方法（TEM）多應用于對標簽數(shù)目與幀長相近時進行估算并且未考慮捕獲效應［2］，而對于標簽數(shù)目與幀長相差很大時，估算方法復雜、錯誤率高。為此提出了帶中斷的動態(tài)幀時隙ALOHA防碰撞算法（ⅠDFSA）［3］，較好地處理了標簽數(shù)目與幀長度相差很大的情況。本文提出的估計算法是基于帶中斷的動態(tài)幀時隙ALOHA防碰撞算法的改進算法（ⅡDFSA），在標簽識別迭代過程中，閱讀器不斷判斷成功識別率、碰撞時隙與空時隙的比值，根據(jù)判斷結(jié)果改變下一個幀長，能明顯改善系統(tǒng)的標簽識別效率。

2　最優(yōu)幀長證明

對于動態(tài)幀時隙ALOHA算法，最關(guān)鍵的問題是如何確定最優(yōu)的幀長度。假設處于閱讀器識別域內(nèi)的標簽數(shù)目為n，幀長為N，標簽在一幀中對閱讀器的響應服從二項分布［4］，即一個時隙中有r個標簽的概率為：

則一幀中成功識別標簽的時隙數(shù)為：

根據(jù)式（1）～（3）可得系統(tǒng)的效率為：

由以上分析可知，當幀長等于閱讀器讀寫范圍內(nèi)的標簽數(shù)目時，系統(tǒng)可獲得最大效率。因此，當前主要任務是在標簽數(shù)目未知的情況下如何估算標簽數(shù)目，分配幀長。

3　標簽估計算法

在DFSA算法中，閱讀器每次發(fā)送的幀長度要隨閱讀器識別區(qū)域內(nèi)標簽數(shù)目的變化而變化，所以如何估計標簽數(shù)目對于DFSA算法至關(guān)重要。在此介紹兩種估計算法。

3.1標簽估計算法一

根據(jù)Schoute提出的理論［5～7］，假設某一幀中某一時隙有傳送數(shù)據(jù)的標簽數(shù)目服從均值為1的泊松分布，則在一幀中第i個時隙有k個標簽的概率為：

所以，根據(jù)上一幀的碰撞時隙個數(shù)C，可以計算未識別的標簽數(shù)目，進而改變下一幀幀長：

F=2.39C （9）

然而，當初始幀長與標簽數(shù)目相差很大時，識別出所有標簽所需的總時隙數(shù)較大，系統(tǒng)效率低。

3.2標簽估計算法二

針對估計算法一中初始幀長與標簽數(shù)目相差很大時系統(tǒng)效率低的情況，文獻［3］提出了一種帶中斷機制的動態(tài)幀時隙ALOHA算法，利用抽樣定理，根據(jù)部分時隙的統(tǒng)計特性，決定是否繼續(xù)對剩余時隙進行識別。文獻［3］指出，當碰撞時隙數(shù)占抽取部分

時隙的75%以上時產(chǎn)生中斷，幀長倍乘2，若空時隙數(shù)占抽取部分時隙的75%以上，則幀長減半，否則按標簽估計算法一進行估計。根據(jù)文獻［3］中所示，選取初始幀長F=256、中斷因子β=0.25，即抽樣時隙數(shù)為f=F×β時，系統(tǒng)效率最高。但判定條件定義不甚合理，且在標簽數(shù)目很低時，所需總的時隙數(shù)仍然很大，效果改善不明顯。

4　改進算法（ⅡDFSA）

根據(jù)標簽估計算法二，本文提出了一種改進的帶中斷機制的標簽碰撞算法（ⅡDFSA）。我們定義系統(tǒng)效率因子E為抽樣時隙中成功時隙與抽樣時隙的比值

定義碰撞時空比R為抽樣時隙中碰撞時隙與空時隙的比值，即：

我們?nèi)圆捎贸跏紟LF=256，中斷因子β=0.25。改進算法描述如圖1。當抽樣時隙中E大于系統(tǒng)效率臨界值E0時，繼續(xù)完成剩余幀長的識別，標簽估計算法采用估計算法一，否則產(chǎn)生中斷，改變幀長；幀長改變方向由R決定，若R大于臨界值R0，則幀長倍乘2，否則幀長減半。

圖1?、駾FSA算法流程圖

首先，我們討論臨界值E0、R0的取值。圖2所示為系統(tǒng)效率隨標簽數(shù)的變化情況。

圖2　在不同幀長時系統(tǒng)效率隨標簽數(shù)的變化情況

為了使系統(tǒng)效率最高，E0采用幀長F=256與F=512交點處的E值，而將F=256與F=512交點處的R值作為臨界值R0。根據(jù)式（4），交點處的系統(tǒng)效率相等，即：

可得交點處的標簽數(shù)目為：

由于在標簽識別過程中，第二次甚至以后的迭代，F(xiàn)可能不為256或2n，所以需要適當調(diào)整E0和R0的值。我們分別取E0為0.25、0.3、0.35，R0為1、1.5、2，對標簽數(shù)為0～1300進行仿真，計算識別所有標簽所需的總時隙數(shù)。仿真結(jié)果如圖3～圖5。

圖3　當E0=0.25時，R0對系統(tǒng)效率的影響

圖4　當E0=0.3時，R0對系統(tǒng)效率的影響

圖5　當E0=0.35時，R0對系統(tǒng)效率的影響

由圖3可知，在R0=1和1.5時，系統(tǒng)效率相近且優(yōu)于R0=2。由圖3和圖4可以看出，隨著標簽數(shù)的增加，在R0=1.5時，系統(tǒng)效率稍高且平坦性比較好，由此確定參數(shù)R0為1.5。然后通過固定臨界值R0=1.5， 分別對E0為0.25、0.3、0.35進行仿真，仿真結(jié)果如圖6所示。由圖6可知，在E0=0.3的情況下，系統(tǒng)效率比較平穩(wěn)，相對比較理想，因此確定參數(shù)E0=0.3和R0=1.5。

圖6　當R0=1.5時，E0對系統(tǒng)效率的影響

5　系統(tǒng)仿真

通過MATLAB仿真，得出標簽數(shù)為10～1300之間時所需的總時隙數(shù)。三種算法的幀初始值都為256，中斷因子為0.25，仿真結(jié)果分別如圖7～圖9所示。

圖7　標簽數(shù)為0～200時，讀標簽所需總時隙數(shù)

圖8　標簽數(shù)為200～800時，讀標簽所需總時隙數(shù)

圖9　標簽數(shù)為800～1 300時，讀標簽所需總時隙數(shù)

由圖7可知，在標簽數(shù)小于初始幀長時，ⅡDFSA算法總體上所需總時隙數(shù)明顯減?。辉跇撕灁?shù)小于40時，ⅡDFSA算法與ⅠDFSA算法基本相當，但顯著優(yōu)于DFSA算法；標簽數(shù)在40～150之間時，ⅡDFSA算法優(yōu)于DFSA和ⅠDFSA算法；而當標簽數(shù)為150～200時，ⅡDFSA算法優(yōu)于ⅠDFSA算法，與DFSA算法相當。

由圖8可知，在標簽數(shù)近似等于或略大于初始幀長度的情況下，幀長基本未被倍乘或由于倍乘因子2.39與2相近，使得三種算法所需總時隙數(shù)相近。

在圖9中，隨著標簽數(shù)目的增加，ⅡDFSA算法略優(yōu)于前兩種。

由以上分析可知，ⅡDFSA算法在標簽數(shù)范圍很大時整體上具有較好的性能，與DFSA 和ⅠDFSA相比具有明顯改進。

6　結(jié)論

本文提出了一種改進的帶中斷機制的動態(tài)幀時隙ALOHA算法——ⅡDFSA。在該算法中，首先通過計算得出系統(tǒng)效率的臨界值E0=0.346和碰撞時空比參考值R0=1.68；然后，通過仿真，對E0、R0進行適當調(diào)整，根據(jù)仿真結(jié)果中系統(tǒng)效率高和波動性小的判決條件，確定了幀改變時的臨界值E0=0.3和幀長改變方向的臨界值R0=1.5；最后對算法性能進行仿真驗證。仿真實驗結(jié)果表明，改進算法的系統(tǒng)效率在標簽數(shù)較低時有明顯改善，較高時略有改善，介于中間區(qū)域時不劣于DFSA 和ⅠDFSA算法。故采用所提出的ⅡDFSA實現(xiàn)RFID標簽防碰撞系統(tǒng)可能有助于明顯改善系統(tǒng)的標簽識別效率。

［1］ W M Wong， P Yun. The Optimal Multicopy Aloha ［J］. IEEE Transaction on automatic control， 1994， 39（6）.

［2］ Sunwoong Choi， Jaehyuk Choi， Joon Yoo. An efficient anticollision protocol for tag identification in RFID systems with capture effect ［C］. 2012 Fourth International Conference on Ubiquitous and Future Networks（ICUFN）， 2012， 482-483.

［3］ Y Cui， H Wang. A New Anti-Collision Method for RFID System ［C］. 2011 IEEE 12th International Symposium on Computational Intelligence and Informatics（CINTI），2011， 51-55.

［4］ 魏欣. RFID標簽及閱讀器防沖突算法研究［D］. 成都：電子科技大學，2009.

［5］ F C Schoute. Dynamic frame length ALOHA ［J］. IEEE trans. Commun. 1983， 31（4）： 565-568.

［6］ J R Cha， J H Kim. Novel anti-collision algorithm for fast object identification in RFID system ［C］. The 11th Intl. Conference on Parallel and Distributed System， 2005. 63-67.

［7］ C Floerkemeier. Transmission control scheme for fast RFID object identification ［C］. Proceedings of the International Conference on Pervasive Computing Communication Workspaces， 2006. 457-462.

An Improved Anti-collision Method for Identification of RFID Tag

WANG Bin， LI Junjie， ZHANG Haipeng， CHEN Ziling， WANG Lidan
（School of Electronics and Information， Hangzhou Dianzi University， Hangzhou 310018， China）

In the paper， an Improved Dynamic Frame-Slotted ALOHA algorithm with Interrupt Mechanism（ⅡDFSA）was brought forward based on the previously reported ALOHA algorithms. The proposedⅡDFSA can be realized as follows. Firstly， the

ystem efficiency and ratio of the collision to empty slots have been optimized and then the frame size is adjusted by comparing the system efficiency with the reference system efficiency. On the other hand， the change direction of the frame size is determined by the ratio of the collision to empty slots. Thus， the proposedⅡDFSA is helpful to effectively reduce the recognition time and improve the system efficiency. Results obtained through computer simulation indicate thatⅡDFSA algorithm can effectively decrease the total recognition time and improve the system efficiency when the tag number less than 200 or more than 800 by comparing with the traditional DFSA andⅠDFSA， and the system efficiency of the proposedⅡDFSA is not worse than those of them while the tag number drops in between 200 and 800.

RFID； ALOHA algorithm； system efficiency； ratio of the collision to empty slots

TN402

A

1681-1070（2015）03-00018-04

王彬（1973—），男，江蘇儀征人，教授，2001年獲美國馬里蘭大學微電子可靠性工程博士學位，主要研究方向為電子存儲器及無線射頻識別（RFID）技術(shù)。

2014-11-04

浙江省智慧城市中心暨企業(yè)研究院人才培養(yǎng)項目（GK130902299002/007）