基于ＲＦＩＤ無線通信系統的防碰撞算法設計與研究

桂衛華　肖又正

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

[關鍵詞]射頻識別 防碰撞算法 RFID系統 ALOHA算法

中圖分類號:TN92文獻標識碼:A文章編號:1671-7597(2009)0920049-02

一、引言

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

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

二、RFID簡介

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

圖1是RFID系統的主要組成框圖,RFID系統主要包括讀卡器(Reade動、標簽(Tag)兩部分[9]。讀卡器通常包含一個射頻收發模塊,一個控制模塊。另外,某些讀卡器還包含其他數據接口系統(RS232,RS 485,以太網接口等),以便將數據轉發到其他計算機系統。

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

三、防碰撞算法簡述

(一)ALOHAT算法

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

(二)時隙ALOHA算法

時隙ALOHA(Slotted Aloha)算法是ALOHA算法的改進算法。這種算法在ALOHA算法的基礎上把時間分成多個離散時隙,并且每個時隙長度要大于標簽回復的數據長度,標簽只能在每個時隙內發送數據。每個時隙存在下面3種情況:

1.無標簽響應:在此時隙內沒有標簽發送;

2.一個標簽響應:在此時隙內只有一個標簽發送,標簽能夠被正確識別;

3.多個標簽響應:在此時隙內多個標簽發送,產生沖突。

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

(三)FSA算法

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

(四)一種改進的DFSA算法

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

1.標簽有一個隨機數生成器,可生成0到N之間的隨機數,這個隨機數代表著分組的組數,在讀卡器發送分組命令時,標簽隨機選擇一個數字即選擇一個組組內進行回答。

2.讀卡器從第0組開始讀取標簽,在組內采用DFSA算法解決標簽碰撞問題,當讀取完該組內所有標簽后,將組數加1,重復這一步驟。

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

四、結論

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

參考文獻:

[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]劉冬生、鄒雪城、李泳生等,射頻識別系統中的防碰撞算法[J].華中科技大學學報:自然科學版,2006,34(9):57-59.

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

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

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

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

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

[9]彭木根、王文博、張倩倩,異構無線通信系統的協同分集性能研究[J].電子學報,2009,37(1):21-25.