桂衛(wèi)華　肖又正

[摘要]針對(duì)動(dòng)態(tài)幀時(shí)隙ALOHA算法(DFSA)不適用于有大量標(biāo)簽的情況,參考Binary Tree算法,提出一種新的解決方案,先將標(biāo)簽分組,使每組只含有少量標(biāo)簽,然后針對(duì)每組標(biāo)簽再分別采用DFSA算法進(jìn)行讀取,這樣就可以解決DFSA算法讀取大量標(biāo)簽的問題。并對(duì)其進(jìn)行仿真試驗(yàn),經(jīng)過仿真驗(yàn)證,該算法在保證正確選擇分組數(shù)的條件下,比DFSA算法有所改進(jìn),能夠提高讀卡器的讀取效率。

[關(guān)鍵詞]射頻識(shí)別 防碰撞算法 RFID系統(tǒng) ALOHA算法

中圖分類號(hào):TN92文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1671-7597(2009)0920049-02

一、引言

射頻識(shí)別技術(shù)(Radio Frequency Identification,RFID)是一種非接觸式的自動(dòng)識(shí)別技術(shù)[1]。一般由閱讀器(Reader)和電子標(biāo)簽(Tag)兩部分構(gòu)成。對(duì)于一個(gè)RFID系統(tǒng),同一時(shí)間可能有多個(gè)電子標(biāo)簽進(jìn)入射頻區(qū),在與讀寫器進(jìn)行通訊時(shí)將產(chǎn)生通常所說的碰撞。防碰撞研究主要解決如何快速和準(zhǔn)確地從多個(gè)電子標(biāo)簽中選出一個(gè)與閱讀器進(jìn)行數(shù)據(jù)交流,而其他未被選中的標(biāo)簽則在此后的防碰撞循環(huán)中被選出與閱讀器通訊[2]?，F(xiàn)有的解決此問題的方法有二進(jìn)制搜索算法、ALOHA算法、Q-選擇算法等[3]。其中二進(jìn)制搜索算法經(jīng)部分學(xué)者改進(jìn)后產(chǎn)生了返回式二進(jìn)制樹型搜索算法,并在較大程度上改進(jìn)了算法的性能,但二進(jìn)制算法并不適用于標(biāo)簽內(nèi)EPC位數(shù)較多的情況[4]。Q-選擇算法是由EPCglobal制定的最新的RFID通信標(biāo)準(zhǔn),它不受標(biāo)簽EPC位數(shù)的影響。對(duì)本標(biāo)準(zhǔn)的研究,業(yè)界還處于起步階段[5]。

ALOHA算法基于TDMA思想,是一種概率算法,屬于電子標(biāo)簽控制算法。當(dāng)電子標(biāo)簽進(jìn)入讀寫器的作用范圍內(nèi),就自動(dòng)向閱讀器發(fā)送自身的序列號(hào),隨即與閱讀器開始通信。在一個(gè)電子標(biāo)簽向讀寫器發(fā)送信息的過程中,如果另外一個(gè)電子標(biāo)簽也在發(fā)送數(shù)據(jù),就會(huì)產(chǎn)生信息碰撞。ALOHA算法分為純ALOHA算法、時(shí)隙ALOHA算法、幀時(shí)隙ALOHA算法和動(dòng)態(tài)幀時(shí)隙ALOHA算法(DFSA)[6]。由于DFSA算法實(shí)現(xiàn)起來比較簡(jiǎn)單,因此目前大量產(chǎn)品都采用DFSA的算法,但是DFSA不適用于有大量標(biāo)簽的情況[7],為了解決這一問題,本文參考Binary Tree算法,提出一種新的解決方案,先將標(biāo)簽分組,使每組只含有少量標(biāo)簽,然后針對(duì)每組標(biāo)簽再分別采用DFSA算法進(jìn)行讀取,這樣就可以解決DFSA算法讀取大量標(biāo)簽的問題。并對(duì)其進(jìn)行了仿真試驗(yàn),經(jīng)過仿真驗(yàn)證,該算法在保證正確選擇分組數(shù)的條件下,比DFSA算法有所改進(jìn),能夠提高讀卡器的讀取效率。

二、RFID簡(jiǎn)介

RFID是無線射頻識(shí)別技術(shù)(Radio Frequency Identification)的簡(jiǎn)稱,是一種從20世紀(jì)90年代興起的,通過電磁感應(yīng)或電磁傳播方式,對(duì)目標(biāo)進(jìn)行非接觸識(shí)別跟蹤和雙向數(shù)據(jù)通信的新型自動(dòng)識(shí)別技術(shù)。相比于條碼、磁條、磁卡、指紋、光學(xué)字符等自動(dòng)識(shí)別技術(shù),RFID具有可無線讀/寫、信號(hào)穿透能力強(qiáng)、識(shí)別距離遠(yuǎn)、使用壽命長(zhǎng)、環(huán)境適應(yīng)性好、可多標(biāo)簽同時(shí)識(shí)別、信息存儲(chǔ)容量大和數(shù)據(jù)可改寫等優(yōu)點(diǎn)[8]。RFID在交通與配送管理、生產(chǎn)制造管理、資產(chǎn)管理、人員門禁與防偽等領(lǐng)域獲得了越來越廣泛的應(yīng)用,其中尤以商品零售和物流管理領(lǐng)域?yàn)樯酢?003年年底,全球最大的商品零售商沃爾瑪宣布其將有計(jì)劃地全面實(shí)施其RFID技術(shù),從而在全球范圍內(nèi)進(jìn)一步掀起了RFID熱潮。

圖1是RFID系統(tǒng)的主要組成框圖,RFID系統(tǒng)主要包括讀卡器(Reade動(dòng)、標(biāo)簽(Tag)兩部分[9]。讀卡器通常包含一個(gè)射頻收發(fā)模塊,一個(gè)控制模塊。另外,某些讀卡器還包含其他數(shù)據(jù)接口系統(tǒng)(RS232,RS 485,以太網(wǎng)接口等),以便將數(shù)據(jù)轉(zhuǎn)發(fā)到其他計(jì)算機(jī)系統(tǒng)。

電子標(biāo)簽是射頻識(shí)別系統(tǒng)的核心,用于保存被標(biāo)識(shí)物體的屬性、狀態(tài)、編號(hào)等信息。一般電子標(biāo)簽由標(biāo)簽天線和標(biāo)簽專用芯片(IC)組成,該標(biāo)簽芯片相當(dāng)于一個(gè)片上系統(tǒng)soc(system on chip),具有能量接收、信息收發(fā)和存儲(chǔ)功能。讀卡器是用于閱讀以及向標(biāo)簽寫入數(shù)據(jù)的裝置,一般讀卡器是針對(duì)特定的電子標(biāo)簽而設(shè)計(jì)的,其主要功能是:查閱電子標(biāo)簽中當(dāng)前貯存的數(shù)據(jù)信息;向電子標(biāo)簽中寫入欲貯存的數(shù)據(jù)信息;修改電子標(biāo)簽中的數(shù)據(jù)信息。

三、防碰撞算法簡(jiǎn)述

(一)ALOHAT算法

ALOHA算法是最簡(jiǎn)單最基本的一種防碰撞算法,它是基于TDMA的思想,是一種基于概率的算法。該算法是指標(biāo)簽在進(jìn)入讀卡器的讀取范田會(huì)隨即向讀卡器發(fā)送其消息,當(dāng)讀卡器準(zhǔn)確分辨出唯一的標(biāo)簽時(shí)與該標(biāo)簽開始通信。采用ALOHA算法的基本思想是在標(biāo)簽發(fā)送數(shù)據(jù)的過程中,若有其他標(biāo)簽也在發(fā)送數(shù)據(jù),那么發(fā)生信號(hào)重疊從而導(dǎo)致完全沖突或部分沖突。圖2給出了Aloha算法標(biāo)簽發(fā)送數(shù)據(jù)部分沖突和完全沖突情況的示意圖。讀卡器檢測(cè)接收到的信號(hào)來判斷有無沖突。一旦發(fā)生沖突,讀卡器就發(fā)送命令讓標(biāo)簽停止發(fā)送,隨機(jī)等待一段時(shí)間后再重新發(fā)送以減少?zèng)_突。純ALOHA算法存在的一個(gè)嚴(yán)重問題是存在錯(cuò)誤判決的問題,即對(duì)同一個(gè)標(biāo)簽,如果連續(xù)多次發(fā)生沖突,這將導(dǎo)致讀卡器出現(xiàn)錯(cuò)誤判斷,認(rèn)為這個(gè)標(biāo)簽不在自己的作用范圍。純Aloha存在的另一個(gè)問題是數(shù)據(jù)幀的發(fā)送過程中發(fā)生沖突的概率很大。

(二)時(shí)隙ALOHA算法

時(shí)隙ALOHA(Slotted Aloha)算法是ALOHA算法的改進(jìn)算法。這種算法在ALOHA算法的基礎(chǔ)上把時(shí)間分成多個(gè)離散時(shí)隙,并且每個(gè)時(shí)隙長(zhǎng)度要大于標(biāo)簽回復(fù)的數(shù)據(jù)長(zhǎng)度,標(biāo)簽只能在每個(gè)時(shí)隙內(nèi)發(fā)送數(shù)據(jù)。每個(gè)時(shí)隙存在下面3種情況:

1.無標(biāo)簽響應(yīng):在此時(shí)隙內(nèi)沒有標(biāo)簽發(fā)送;

2.一個(gè)標(biāo)簽響應(yīng):在此時(shí)隙內(nèi)只有一個(gè)標(biāo)簽發(fā)送,標(biāo)簽?zāi)軌虮徽_識(shí)別;

3.多個(gè)標(biāo)簽響應(yīng):在此時(shí)隙內(nèi)多個(gè)標(biāo)簽發(fā)送,產(chǎn)生沖突。

這樣標(biāo)簽或成功發(fā)送或完全沖突,避免了原Aloha算法中的部分沖突,提高了信道的利用率。但是這種方法需要一個(gè)同步時(shí)鐘以使讀卡器閱讀區(qū)域內(nèi)的所有標(biāo)簽的時(shí)隙同步。

(三)FSA算法

ALOHA算法的另一種擴(kuò)展算法是Framed Slotted Aloha算法,簡(jiǎn)稱FSA算法。它是在時(shí)隙ALOHA算法的基礎(chǔ)上把N個(gè)時(shí)隙組成一幀,標(biāo)簽在每個(gè)幀內(nèi)隨機(jī)選擇一個(gè)時(shí)隙發(fā)送數(shù)據(jù)。這種算法適于傳輸信息量較大的場(chǎng)合,與時(shí)隙ALOHA算法相同,FSA算法也需要一個(gè)同步開銷。一個(gè)幀包含多個(gè)時(shí)隙,N個(gè)時(shí)隙的長(zhǎng)度要足夠讓一個(gè)標(biāo)簽回答完,其體時(shí)間山讀卡器定義。在讀卡器發(fā)送讀取命令后,要等待一定時(shí)間等待標(biāo)簽的回答。在一個(gè)時(shí)隙中只有一個(gè)標(biāo)簽回答時(shí),讀卡器可以分辨出標(biāo)簽;在一個(gè)時(shí)隙中沒有標(biāo)簽回答時(shí),跳過此時(shí)隙:當(dāng)在一個(gè)時(shí)隙中有多個(gè)標(biāo)簽回答時(shí),發(fā)生沖突,需要重新開始讀取過程。FSA算法存在一個(gè)缺點(diǎn),當(dāng)標(biāo)簽數(shù)量遠(yuǎn)大于時(shí)隙個(gè)數(shù)時(shí),讀取標(biāo)簽的時(shí)間將會(huì)大大增加,而在標(biāo)簽個(gè)數(shù)遠(yuǎn)小于時(shí)隙個(gè)數(shù)時(shí),會(huì)造成時(shí)隙的浪費(fèi)。

(四)一種改進(jìn)的DFSA算法

由于DFSA算法實(shí)現(xiàn)起來比較簡(jiǎn)單,因此目前大量產(chǎn)品都采用DFSA的算法,但通過上面分析可知,DFSA不適用于有大量標(biāo)簽的情況,為了解決這一問題,本文參考Binary Tree算法,可以先將標(biāo)簽分組,使每組只含有少量標(biāo)簽,然后針對(duì)每組標(biāo)簽再分別采用DFSA算法進(jìn)行讀取,這樣就可以解決DFSA算法讀取大量標(biāo)簽的問題。具體實(shí)現(xiàn)過程為:

1.標(biāo)簽有一個(gè)隨機(jī)數(shù)生成器,可生成0到N之間的隨機(jī)數(shù),這個(gè)隨機(jī)數(shù)代表著分組的組數(shù),在讀卡器發(fā)送分組命令時(shí),標(biāo)簽隨機(jī)選擇一個(gè)數(shù)字即選擇一個(gè)組組內(nèi)進(jìn)行回答。

2.讀卡器從第0組開始讀取標(biāo)簽,在組內(nèi)采用DFSA算法解決標(biāo)簽碰撞問題,當(dāng)讀取完該組內(nèi)所有標(biāo)簽后,將組數(shù)加1,重復(fù)這一步驟。

根據(jù)表1我們可以看出,采用了分組的方法后,隨著分組數(shù)目的增加所用的總時(shí)隙數(shù)不斷減少,但是分組數(shù)過大時(shí),所用時(shí)隙卻有所增加,產(chǎn)生了大量的余,當(dāng)分組后每組的標(biāo)簽數(shù)目在50左右的時(shí)候,所得的總體效果較好。實(shí)驗(yàn)表明本文算法在保證正確選擇分組數(shù)的條件下,比DFSA算法有所改進(jìn),能夠提高讀卡器的讀取效率。

四、結(jié)論

由于DFSA算法實(shí)現(xiàn)起來比較簡(jiǎn)單,因此目前大量產(chǎn)品都采用DFSA的算法,但是DFSA不適用于有大量標(biāo)簽的情況,為了解決這一問題,本文參考Binary Tree算法,提出一種新的解決方案,先將標(biāo)簽分組,使每組只含有少量標(biāo)簽,然后針對(duì)每組標(biāo)簽再分別采用DFSA算法進(jìn)行讀取,這樣就可以解決DFSA算法讀取大量標(biāo)簽的問題。并對(duì)其進(jìn)行了仿真試驗(yàn),經(jīng)過仿真驗(yàn)證,該算法在保證正確選擇分組數(shù)的條件下,比DFSA算法有所改進(jìn),能夠提高讀卡器的讀取效率。

參考文獻(xiàn):

[1]Law C,Lee K,KaiYeung S.Eficient memoryless protocol for tag identification[C].Proceeding of ACM DI-ALM'00.2000:75-84.

[2]Sangjun Kim.Euiho Suh and Keedong Yoo.A study of context inference for Web based information systems.Electronic Commerce Research and Applications,In Press,Uncorrected Proof,Available online 21 December 2006.

[3]劉冬生、鄒雪城、李泳生等,射頻識(shí)別系統(tǒng)中的防碰撞算法[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2006,34(9):57-59.

[4]梁彪、胡愛群、秦中元,一種新的RFID防碰撞算法設(shè)計(jì)[J].電子與信息學(xué)報(bào),2007,29(9):2158-2160.

[5]呂炳赟、潘劍俠、馬琪等,RFID防碰撞算法的研究進(jìn)展與應(yīng)用[J].電訊技術(shù),2008,48(7):124-128.

[6]丁治國、郭立、劉琦,一種基于搜索矩陣的自適應(yīng)防碰撞算法[J].模式識(shí)別與人工智能,2008,21(4):476-481.

[7]劉佳、張有光,基于時(shí)隙的RFID防碰撞算法分析[J].電子技術(shù)應(yīng)用,2007(5):94-100.

[8]李世煜、馮全源、魯飛,基于BIBD(4,2,1)的RFID防碰撞算法[J].計(jì)算機(jī)工程,2009,35(3):279-281.

[9]彭木根、王文博、張倩倩,異構(gòu)無線通信系統(tǒng)的協(xié)同分集性能研究[J].電子學(xué)報(bào),2009,37(1):21-25.