基于分組處理的RFID防碰撞算法＊

田旺蘭，李夢(mèng)醒，譚 躍

（湖南城市學(xué)院通信與電子工程學(xué)院，湖南益陽(yáng) 413000）

基于分組處理的RFID防碰撞算法＊

田旺蘭，李夢(mèng)醒，譚 躍

（湖南城市學(xué)院通信與電子工程學(xué)院，湖南益陽(yáng) 413000）

防碰撞算法是射頻識(shí)別系統(tǒng)實(shí)現(xiàn)多目標(biāo)識(shí)別的關(guān)鍵技術(shù).針對(duì)基于二叉樹的標(biāo)簽防碰撞算法存在識(shí)別次數(shù)較多和通信數(shù)據(jù)量較大的問題，提出一種新的基于分組處理的防碰撞算法.該算法將標(biāo)簽進(jìn)行分組處理，直接用4個(gè)2位長(zhǎng)的查詢前綴去分裂標(biāo)簽集，讀寫器檢測(cè)到數(shù)據(jù)中有2個(gè)碰撞位后不再接收后續(xù)數(shù)據(jù)，整個(gè)識(shí)別過程采用后退策略.仿真結(jié)果表明，該算法在查詢次數(shù)和數(shù)據(jù)傳輸量均有較大提高.

射頻識(shí)別；防碰撞；二叉樹；分組處理；后退策略

1 NTA算法

1.1 相關(guān)命令

（1）查詢命令：REQUEST（p，m）.當(dāng)m＝0時(shí)，p為2位長(zhǎng)的查詢前綴，標(biāo)簽把查詢前綴p與ID進(jìn)行比較，如果兩者匹配，則發(fā)送ID剩余的部分.m＝1時(shí)，p為最高碰撞位的位置，ID第p位為‘0’的標(biāo)簽應(yīng)答ID第p位以后的數(shù)據(jù).

（2）分組處理命令：GROUPING（Group＿num）.標(biāo)簽接收到此命令后，隨機(jī)產(chǎn)生一個(gè)0～Group＿num之間的數(shù)，并存于存儲(chǔ)器TG中，TG中值相等的標(biāo)簽在同一組.

（3）分組選擇命令：SELECT＿GROUP（GN）.TG中與GN相等的分組被選中.讀寫器在算法開始時(shí)或識(shí)別完一個(gè)組中的標(biāo)簽后發(fā)送此命令.

（4）有效標(biāo)簽：TAG-ACTIVE.讀寫器識(shí)別一個(gè)標(biāo)簽后，發(fā)送此命令，如果標(biāo)簽中計(jì)數(shù)器TC＞0，則進(jìn)行TC減1操作.

（5）停止命令：STOP.讀寫器檢測(cè)到接收的數(shù)據(jù)中有2個(gè)碰撞位后，發(fā)送此命令，標(biāo)簽立即停止發(fā)送數(shù)據(jù).

（6）選擇標(biāo)簽：SELECT（P）.

（7）讀出標(biāo)簽數(shù)據(jù)：READ-DATA（P）.

（8）標(biāo)簽去選擇：UNSELECT（P）.

1.2 NTA算法

圖1 NTA算法防碰撞處理流程

文中算法把讀寫器作用區(qū)域內(nèi)所有標(biāo)簽進(jìn)行分組，從小到大依次識(shí)別每個(gè)標(biāo)簽分組就可以識(shí)別所有標(biāo)簽.讀寫器根據(jù)標(biāo)簽ID的前2位，可以生成4個(gè)查詢前綴“00”、“01”，“10”，“11”.讀寫器根據(jù)這4個(gè)查詢前綴可以把每個(gè)分組中的標(biāo)簽分裂成4個(gè)子集.讀寫器發(fā)送2位長(zhǎng)的查詢前綴，直接選中那些與查詢前綴匹配的標(biāo)簽進(jìn)行識(shí)別.每個(gè)標(biāo)簽分組經(jīng)過這樣處理，能縮短每次從根節(jié)點(diǎn)開始識(shí)別的分解延遲.讀寫器對(duì)整個(gè)標(biāo)簽分組的識(shí)別過程采用后退策略，以減少查詢次數(shù).圖1為NTA算法的防碰撞處理流程.

NTA算法的主要步驟如下：

（1）讀寫器發(fā)送分組命令GROUPING（Group＿num）進(jìn)行標(biāo)簽分組處理，所有標(biāo)簽產(chǎn)生［0～Group＿num）之間隨機(jī)數(shù)并存入TG.

（2）讀寫器把4個(gè)查詢前綴入棧RS.發(fā)送SELECT-GROUP（GN）命令，選中第GN組標(biāo)簽.當(dāng)?shù)?次發(fā)送分組選擇命令時(shí)，GN＝0，選擇第0組標(biāo)簽.

（3）讀寫器發(fā)送查詢命令REQUEST（p，m）命令.第1次發(fā)送REQUEST命令時(shí)，p為查詢前綴“00”，m＝0.

（4）讀寫器對(duì)標(biāo)簽發(fā)送的數(shù)據(jù)進(jìn)行譯碼，根據(jù)譯碼結(jié)果判斷是否有碰撞發(fā)生.如果沒有碰撞發(fā)生，讀寫器可以識(shí)別1個(gè)標(biāo)簽.如果只有1個(gè)碰撞位，讀寫器可以用‘0’和‘1’代替此碰撞位，同時(shí)識(shí)別2個(gè)標(biāo)簽.讀寫器識(shí)別標(biāo)簽后，依次發(fā)送SELECT和READ-DATE命令，讀出標(biāo)簽中存儲(chǔ)的數(shù)據(jù)信息.之后，讀寫器發(fā)出UNSELECT命令，讓成功讀寫的標(biāo)簽進(jìn)入休眠狀態(tài).接著，讀寫器發(fā)送TAG-ACTIVE命令，那些TC＞0的標(biāo)簽進(jìn)行TC減1操作.讀寫器對(duì)RS進(jìn)行出棧操作，獲得新的查詢命令.

如果檢測(cè)到接收的數(shù)據(jù)中有2個(gè)碰撞，讀寫器發(fā)送STOP命令，停止接收后續(xù)數(shù)據(jù).讀寫器檢測(cè)最高碰撞位位置p，并把m設(shè)置成1，生成新的查詢命令參數(shù).算法跳至步驟（3），繼續(xù)查詢過程.

（5）當(dāng)被選中分組中所有標(biāo)簽都被識(shí)別完時(shí)，GN＋＋，選中下一個(gè)標(biāo)簽分組進(jìn)行識(shí)別，算法跳至步驟（2）.當(dāng)GN＝Group＿num－1時(shí)，為最后1個(gè)標(biāo)簽分組，并且該分組中的所有標(biāo)簽都被識(shí)別完時(shí)，整個(gè)算法識(shí)別過程結(jié)束.

2 算法分析

2.1 算法分析

假設(shè)讀寫器作用區(qū)域內(nèi)存在N個(gè)標(biāo)簽，標(biāo)簽被劃分成Group＿num組.識(shí)別這N個(gè)標(biāo)簽所需的總查詢次數(shù)為識(shí)別每個(gè)分組所需的查詢次數(shù)之和.假設(shè)識(shí)別第i個(gè)分組中的標(biāo)簽所需的查詢次數(shù)為Q（i），傳輸?shù)臄?shù)據(jù)為D（i）（其中0≤i＜Group＿num）.那么識(shí)別N個(gè)標(biāo)簽總的通信次數(shù)為

數(shù)據(jù)通信量為

由此可知，NTA算法識(shí)別N個(gè)標(biāo)簽的整體性能由識(shí)別每個(gè)分組的性能決定，優(yōu)化NTA算法必須從每個(gè)標(biāo)簽分組著手.如果標(biāo)簽產(chǎn)生的隨機(jī)數(shù)絕對(duì)隨機(jī)，每個(gè)分組中標(biāo)簽的數(shù)量都是N／Group＿num，那么優(yōu)化1個(gè)標(biāo)簽分組的性能就能使整個(gè)算法達(dá)到最大效率.

2.2 標(biāo)簽分組分析

以1個(gè)標(biāo)簽分組為實(shí)驗(yàn)，標(biāo)簽ID為96bit，隨機(jī)生成，標(biāo)簽數(shù)量從2個(gè)逐漸增加到15個(gè)，在理想信道下進(jìn)行仿真.觀察識(shí)別該分組標(biāo)簽所需的平均查詢次數(shù)和平均傳輸?shù)臄?shù)據(jù)量這2個(gè)方面的性能，程序連續(xù)運(yùn)行5 000次取平均值.

圖2為識(shí)別每個(gè)標(biāo)簽所需的平均查詢次數(shù).當(dāng)標(biāo)簽數(shù)量大于5時(shí)，平均查詢次數(shù)隨著標(biāo)簽數(shù)量的增加而增大.當(dāng)標(biāo)簽數(shù)量小于5時(shí)，平均查詢次數(shù)會(huì)隨著標(biāo)簽數(shù)量的下降會(huì)快速上升.

圖3為平均識(shí)別1個(gè)標(biāo)簽產(chǎn)生的空查詢數(shù).當(dāng)標(biāo)簽數(shù)量小于7時(shí)，空時(shí)隙數(shù)隨著標(biāo)簽數(shù)目的減少會(huì)急劇增加.當(dāng)標(biāo)簽數(shù)量大于7時(shí)，空查詢次數(shù)逐漸降低，并趨于0.

圖4為識(shí)別每個(gè)標(biāo)簽所傳輸?shù)钠骄鶖?shù)據(jù)量，平均傳輸?shù)臄?shù)據(jù)量隨著標(biāo)簽數(shù)量的增加呈上升趨勢(shì).分組中標(biāo)簽越多，平均傳輸?shù)臄?shù)據(jù)就會(huì)越多.

圖2 平均查詢次數(shù)與標(biāo)簽數(shù)量關(guān)系曲線

圖3 平均空查詢數(shù)與標(biāo)簽數(shù)量關(guān)系曲線

圖4 平均傳輸?shù)臄?shù)據(jù)與標(biāo)簽數(shù)量關(guān)系曲線

綜合考慮查詢次數(shù)、傳輸?shù)臄?shù)據(jù)量、空時(shí)隙等因素，并且考慮到實(shí)際應(yīng)用中標(biāo)簽產(chǎn)生的隨機(jī)數(shù)并不是絕對(duì)隨機(jī)，文中每個(gè)分組中標(biāo)簽數(shù)量的期望值為7，即總的分組數(shù)為N／7

3 仿真分析

文中提出的算法（NTA）與二叉樹搜索算法（BS）、動(dòng)態(tài)二叉樹搜索算法（DBS）、后退式二叉樹搜索算法（RBS）、陳炳才等［10］提出的RDS算法與王雪等［11］提出的BLBO算法進(jìn)行比較，標(biāo)簽數(shù)量從50取到1 000，間隔50.通過對(duì)比不同標(biāo)簽數(shù)目下讀寫器成功識(shí)別所有標(biāo)簽所需的總查詢次數(shù)和傳輸?shù)目倲?shù)據(jù)量來(lái)比較算法效率.不計(jì)控制、前后綴、校驗(yàn)冗余等開銷，在理想信道下進(jìn)行仿真.假設(shè)標(biāo)簽ID長(zhǎng)96bit，ID隨機(jī)生成.為提高數(shù)據(jù)精度，連續(xù)仿真100次取平均值.

圖5為各算法識(shí)別標(biāo)簽所需的查詢次數(shù)比較.從圖中可以看出，BS算法和DBS算法所需的查詢次數(shù)最多.RBS算法平均每識(shí)別1個(gè)標(biāo)簽需要查詢2次.RDS算法和BLBO算法所需的查詢次數(shù)與RBS算法相等.由于NTA算法采用分組策略，減少了每次應(yīng)答標(biāo)簽的數(shù)量，并且采用2位長(zhǎng)的查詢前綴代替從根節(jié)點(diǎn)開始識(shí)別，故而能夠減少查詢次數(shù).在這幾種算法中，NTA算法所需的查詢次數(shù)最少，平均識(shí)別1個(gè)標(biāo)簽約需要查詢1.6次.

圖6為各算法數(shù)據(jù)傳輸量的比較.這幾種算法中，BS算法識(shí)別標(biāo)簽所傳輸?shù)臄?shù)據(jù)最多，DBS算法有所提高，為BS的50%.由于RBS算法所需的查詢次數(shù)遠(yuǎn)遠(yuǎn)少于BS和DBS，RBS算法的數(shù)據(jù)傳輸量比BS和DBS都要少.RDS算法和BLBO算法都是基于后退機(jī)制的改進(jìn)算法，它們的數(shù)據(jù)傳輸量相對(duì)RBS算法都有不同程度的改善.由于NTA算法減少了讀寫器的查詢次數(shù)，并且標(biāo)簽只應(yīng)答最高碰撞位以后的數(shù)據(jù).所以，NTA算法能夠降低數(shù)據(jù)傳輸量，約為DBS算法的1／6，優(yōu)于RBS、RDS和BLBO等算法.

圖5 不同算法識(shí)別標(biāo)簽的查詢次數(shù)的比較

圖6 不同算法數(shù)據(jù)傳輸量的比較

4 結(jié)語(yǔ)

提出了一種改進(jìn)的基于樹的防碰撞算法.新的算法把標(biāo)簽進(jìn)行分組處理以減少每次應(yīng)答標(biāo)簽的數(shù)量，用4個(gè)查詢前綴去分裂標(biāo)簽集以減少?gòu)母?jié)點(diǎn)開始識(shí)別的分解延時(shí)，算法整個(gè)識(shí)別過程采用后退策略.通過仿真分析得出了1個(gè)適當(dāng)?shù)臉?biāo)簽分組數(shù)，使算法的整體性能達(dá)到了最佳.仿真實(shí)驗(yàn)證明了算法的有效性，在標(biāo)簽密集的場(chǎng)合，可有效地減少查詢次數(shù)、降低數(shù)據(jù)傳輸量，提高識(shí)別效率.

［1］ 王中祥，王俊宇，劉 丹，等.BIS：一種降低空時(shí)隙開銷的RFID防碰撞算法［J］.通信學(xué)報(bào)，2009，30（9）：1－6.

［2］ KLAIR D K，CHIN K W，RAAD R.ASurvey and Tutorial of RFID Anti-Collision Protocols［J］.IEEE Communication Surveys and Tutorials，2010，12（3）：400－421.

［3］ MOESSNER M，GUL N K.Secure Authentication Scheme for Passive Class1Generation2RFID Tags［J］.Computer Networks，2011，51（6）：273－286.

［4］ 陳 章，廖明宏.快速RFID防沖突算法［J］.計(jì)算機(jī)應(yīng)用，2010，30（1）：18－20.

［5］ EOM J B，LEE T J.AnEfficient Framed-Slotted ALOHA Algorithm with Pilot Frame and Binary Selection for Anti-Collision for RFID Tags［J］.IEEE Communications Letters，2008，12（11）：861－863.

［6］ QUAN C H，HONG W K，LEE Y D，et al.A Study on the Tree Based Memoryless Anti-Collision Algorithm for RFID System［J］.Korean Information and Processing Society Transactions，2001，11（6）：851－862.

［7］ FINKENZELLER K.射頻識(shí)別技術(shù)［M］.第3版，吳曉峰，陳大才，譯.北京：電子工業(yè)出版社，2001.

［8］ 謝振華，賴聲禮，陳 鵬.RFID技術(shù)和防沖突算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（6）：223－226.

［9］ 余松森，詹宜巨，彭衛(wèi)東，等.基于后退式索引的二進(jìn)制樹形搜索反碰撞算法及其實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40（16）：26－28.

［10］ 陳炳才，徐東升，顧國(guó)昌，等.一種基于堆棧存儲(chǔ)的RFID防沖突算法［J］.計(jì)算機(jī)應(yīng)用，2009，29（6）：1 483－1 486.

［11］ 王 雪，錢志鴻，胡正超，等.基于二叉樹的RFID防碰撞算法的研究［J］.通信學(xué)報(bào)，2010，31（6）：49－57.

［12］ 王春華，許 靜，彭關(guān)超，等.改進(jìn)的RFID標(biāo)簽識(shí)別防沖突算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（31）：104－107.

（責(zé)任編輯 陳炳權(quán)）

Tree-Based Anti-Collision Algorithm Radio Frequency Identification System

TIAN Wang-lan，LI Meng-xing，TAN Yue
（College of Communication and Electron Engineering，Hunan City University，Yiyang 413000，Hunan China）

The anti-collision algorithm is the key technology of radio frequency identification system to achieve multi-target recognition.To solve the problem of too many identification times and transmitted bits in some binary tree based schemes，a new tree-based anti-collision algorithm is proposed.The algorithm divides tags into several groups.Four query prefixes which consist of two bits are directly used to split tag set，and the backtrack strategy is adopted to reduce identification times.The simulation results show that the algorithm significantly improves the query times and the data transmission.

radio frequency identification；anti-collision；binary Tree；grouping process；backtrack strategy

TP301.6

A

10.3969／j.issn.1007－2985.2013.05.016

1007－2985（2013）05－0066－04

射頻識(shí)別（Radio Frequency Identification，RFID）技術(shù)是近年來(lái)新興的一種非接觸自動(dòng)識(shí)別技術(shù).由于RFID具有識(shí)別距離遠(yuǎn)、數(shù)據(jù)容量大、可以非視距通信等特點(diǎn)［1］，被廣泛應(yīng)用在物流跟蹤、供應(yīng)鏈管理、電子支付等領(lǐng)域［2］.典型的RFID系統(tǒng)通常由讀寫器、電子標(biāo)簽和后臺(tái)計(jì)算機(jī)系統(tǒng)3個(gè)部分構(gòu)成［3］.RFID系統(tǒng)通過在讀寫器與電子標(biāo)簽之間構(gòu)建一個(gè)無(wú)線雙向信息傳輸通道來(lái)實(shí)現(xiàn)電子標(biāo)簽的自動(dòng)識(shí)別.當(dāng)多個(gè)標(biāo)簽同時(shí)響應(yīng)讀寫器時(shí)，標(biāo)簽信號(hào)會(huì)相互干擾，讀寫器不能正確識(shí)別標(biāo)簽信息，發(fā)生標(biāo)簽碰撞［4］.標(biāo)簽碰撞會(huì)減慢識(shí)別過程，甚至讀寫器無(wú)法識(shí)別標(biāo)簽.因此需要防碰撞算法去解決標(biāo)簽碰撞問題，以提高系統(tǒng)識(shí)別效率.

目前，大多數(shù)標(biāo)簽防碰撞算法都是基于時(shí)分多址技術(shù)，主要有2大類：基于ALOHA的概率性算法和基于樹的確定性算法［5－6］.由于基于樹的算法不存在“標(biāo)簽饑餓”問題，被得到廣泛應(yīng)用.二叉樹算法根據(jù)標(biāo)簽ID或者隨機(jī)產(chǎn)生的二進(jìn)制0和1把標(biāo)簽集劃分成2個(gè)子集.若有碰撞，繼續(xù)分裂子集，直到每個(gè)集合中只含有1個(gè)標(biāo)簽，讀寫器就能識(shí)別作用范圍內(nèi)所有標(biāo)簽.典型的基于樹的算法包括二叉樹搜索算法（Binary Search Tree，BS）［7］、動(dòng)態(tài)二叉樹搜索算法（Dynamic Binary Search Tree，DBS）［8］、后退式二叉樹搜索算法（Regressive Binary Search Tree，RBS）［9］等.陳炳才等［10］在結(jié)合DBS與RBS算法優(yōu)點(diǎn)的基礎(chǔ)上，提出了一種基于堆棧的動(dòng)態(tài)減位防沖突算法（Reduces Dynamic binary algorithm on Stack，RDS），RDS算法能夠減少讀寫器與標(biāo)簽的數(shù)據(jù)傳輸量，但是識(shí)別標(biāo)簽所需的查詢次數(shù)卻仍與RBS算法相當(dāng).王雪等［11］提出了一種鎖位后退防碰撞算法（Bit-locking backoff anti-collision algorithm，BLBO），BLBO算法采用后退機(jī)制，并且每輪查詢中，讀寫器和電子標(biāo)簽都只處理那些在第1輪查詢中發(fā)生碰撞的位.所以，BLBO算法能夠顯著地降低數(shù)據(jù)通信量，但是查詢次數(shù)卻沒有得到改善，與RBS算法相同.王春華等［12］提出了一種改進(jìn)的基于堆棧的二進(jìn)制樹防沖突算法（IBSTS），IBSTS算法用堆棧存儲(chǔ)識(shí)別過程產(chǎn)生的信息，讀寫器和標(biāo)簽只處理上一輪查詢中發(fā)生碰撞的位，算法采用后退機(jī)制，IBSTS算法在數(shù)據(jù)通信量方面有較大改善，但查詢次數(shù)還是與RBS算法相等.

同時(shí)考慮通信數(shù)據(jù)量與查詢次數(shù)2個(gè)方面，筆者提出一種新的基于樹的防碰撞算法（New tree-basedanti-collision Algorithm，NTA）.提出的算法對(duì)標(biāo)簽進(jìn)行分組處理，直接用4個(gè)2位長(zhǎng)的查詢前綴去分裂標(biāo)簽集，并且識(shí)別過程采用后退策略以提升系統(tǒng)的識(shí)別效率.

2013－06－11

湖南省教育廳科學(xué)研究資助項(xiàng)目（11C0249）

田旺蘭（1977－），女，湖南婁底人，湖南城市學(xué)院講師，碩士，主要從事RFID技術(shù)、無(wú)線傳感網(wǎng)絡(luò)研究；李

夢(mèng)醒（1972－），男，湖南寧鄉(xiāng)人，湖南城市學(xué)院副教授，博士，主要從事現(xiàn)代信號(hào)處理在通信系統(tǒng)中的應(yīng)用研究；譚躍（1974－），男，湖南安化人，湖南城市學(xué)院副教授，博士，主要從事自動(dòng)控制研究.