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

（杭州電子科技大學(xué)電子信息學(xué)院，杭州 310018）

一種改進(jìn)的RFID標(biāo)簽防碰撞算法*

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

（杭州電子科技大學(xué)電子信息學(xué)院，杭州 310018）

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

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

1　引言

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

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

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

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

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

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

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

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

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

3　標(biāo)簽估計(jì)算法

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

3.1標(biāo)簽估計(jì)算法一

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

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

F=2.39C （9）

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

3.2標(biāo)簽估計(jì)算法二

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

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

4　改進(jìn)算法（ⅡDFSA）

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

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

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

圖1?、駾FSA算法流程圖

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

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

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

可得交點(diǎn)處的標(biāo)簽數(shù)目為：

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

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

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

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

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

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

5　系統(tǒng)仿真

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

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

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

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

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

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

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

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

6　結(jié)論

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

［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標(biāo)簽及閱讀器防沖突算法研究［D］. 成都：電子科技大學(xué)，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年獲美國馬里蘭大學(xué)微電子可靠性工程博士學(xué)位，主要研究方向?yàn)殡娮哟鎯?chǔ)器及無線射頻識(shí)別（RFID）技術(shù)。

2014-11-04

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