基于RFID的二進(jìn)制防碰撞算法的改進(jìn)

　　1. 引言

　　無線射頻識別技術(shù)(Radio Frequency Identific -ation RFID)是從二十世紀(jì)90 年代興起的一項(xiàng)非接觸式自動識別技術(shù)。它是利用電磁原理進(jìn)行非接觸式雙向通信，以達(dá)到自動識別目標(biāo)對象并獲取相關(guān)數(shù)據(jù)的目的。RFID 己被廣泛應(yīng)用于工業(yè)自動化、商業(yè)自動化、交通運(yùn)輸控制管理等眾多領(lǐng)域[１]。隨著成本的下降和標(biāo)準(zhǔn)化的實(shí)施，RFID 技術(shù)的全面推廣和普遍應(yīng)用將是不可逆轉(zhuǎn)的趨勢．

　　但 RFID 技術(shù)也存在著很多關(guān)鍵問題需要解決，例如RFID 技術(shù)的操作距離問題，安全和隱私問題，數(shù)據(jù)存儲問題，碰撞問題等[2]。本文是論述有關(guān)RFID 的防碰撞問題。在很多情況下，閱讀器射頻區(qū)可能會有多個(gè)標(biāo)簽存在，面對閱讀器發(fā)出的指令，每個(gè)標(biāo)簽都會響應(yīng)，所以標(biāo)簽的響應(yīng)信息會產(chǎn)生疊混的現(xiàn)象，在RFID 技術(shù)中這種現(xiàn)象被稱為標(biāo)簽碰撞問題[3]。RFID 系統(tǒng)會采用一定的策略或算法來避免標(biāo)簽碰撞現(xiàn)象的發(fā)生，控制標(biāo)簽的響應(yīng)信息逐個(gè)通過射頻信道被閱讀器接收。防碰撞問題的研究主要解決如何快速和準(zhǔn)確地從多個(gè)標(biāo)簽中選出一個(gè)與閱讀器進(jìn)行數(shù)據(jù)交流，而其他的標(biāo)簽同樣可以從接下來的防碰撞循環(huán)中選出與閱讀器通信。

　　2 傳統(tǒng)二進(jìn)制算法

　　2.1 傳統(tǒng)二進(jìn)制算法的基本原理

　　在二進(jìn)制搜索算法中，要能夠檢測出多張卡的存在，卡片的返回?cái)?shù)據(jù)必須具有唯一性，且卡片在傳輸其UID(Ubiquitous Identifications，身份識別標(biāo)簽)時(shí)必須準(zhǔn)確、快速、同步，這是防碰撞檢測的關(guān)鍵。

　　傳統(tǒng)二進(jìn)制算法流程是，當(dāng)閱讀器發(fā)出的序列號大于標(biāo)簽序列號時(shí)，則閱讀器作出響應(yīng)。根據(jù)這一特點(diǎn)，傳統(tǒng)二進(jìn)制算法[4]的工作流程是:

　　①標(biāo)簽進(jìn)入閱讀器的工作范圍，閱讀器發(fā)出一個(gè)最大序列號讓所有標(biāo)簽響應(yīng);同一時(shí)刻開始傳輸它們的序列號到閱讀器的接收模塊。
　　②閱讀器對比標(biāo)簽響應(yīng)的序列號的相同位數(shù)上的數(shù)，如果出現(xiàn)不一致的現(xiàn)象，則可判斷出該位有碰撞。
　?、鄞_定有碰撞后，把有不一致位的數(shù)從最高位到最低位依次置0 再輸出系列號，即依次排除序列號大的數(shù)，循環(huán)至閱讀器對比標(biāo)簽響應(yīng)的序列號的相同位數(shù)上的數(shù)完全一致時(shí)，說明無碰撞。這時(shí)就選出序列號最小的數(shù)。
　　④選出序列號最小的數(shù)后，對該卡進(jìn)行數(shù)據(jù)交換，然后使該卡進(jìn)入“無聲”狀態(tài)，則在閱讀器范圍也不再響應(yīng)(重新移入該標(biāo)簽才可再次響應(yīng))。
　?、葜貜?fù)流程①，選出序列號倒數(shù)第二的標(biāo)簽進(jìn)行數(shù)據(jù)交換。
　?、薅啻窝h(huán)后可完成所有標(biāo)簽的讀取。

　　2.2 傳統(tǒng)二進(jìn)制算法的傳輸時(shí)間

　　由傳統(tǒng)二進(jìn)制算法的工作流程可知，防碰撞處理是在確認(rèn)有碰撞的情況下，根據(jù)高低位不斷降值的序列號一次次進(jìn)行篩選出某一射頻卡，從而可知標(biāo)簽的數(shù)量越多，防碰撞執(zhí)行時(shí)間就將越長。查詢的次數(shù)N 可用下式來計(jì)算:N=Integ(logM/log2)+l 式中:M 是終端作用范圍內(nèi)射頻卡片數(shù)目;Integ 表示數(shù)值取整。UID 的位數(shù)越多(如ICODE 達(dá)64 位[5])，每次傳送的時(shí)間加長，數(shù)據(jù)傳送的時(shí)間就會增大。如每次都傳輸完整的UID，時(shí)間為T，則用于傳輸U(kuò)ID 的通信時(shí)間為:t=T×N 即終端作用范圍內(nèi)射頻卡片數(shù)越多，UID 位數(shù)越多，傳送時(shí)間越長，總的防碰撞執(zhí)行時(shí)間肯定也就越長。

　　3. 改進(jìn)的二進(jìn)制算法

　　針對采用傳統(tǒng)二進(jìn)制搜索算法時(shí)終端射頻卡片數(shù)越多，UID 位數(shù)越長，傳送時(shí)間越長的缺點(diǎn)，目前提出了很多改良防碰撞算法，如：ALOHA 算法[6]， EPC 動態(tài)二進(jìn)制算法[7]，跳躍式二進(jìn)制算法[8]等，歸納一下基本采用兩種方法改良算法的性能，一是減少傳輸數(shù)據(jù)的字節(jié)數(shù)，二是減少查詢次數(shù)，本算法，試圖將此兩種方法應(yīng)用到同一種防碰撞算法中。

　　3.1 改進(jìn)的二進(jìn)制算法的基本原理

　　本算法首先是標(biāo)簽閱讀器發(fā)出請求指令，等待閱讀器接收范圍內(nèi)所有標(biāo)簽第一位回應(yīng)，標(biāo)簽回應(yīng)完畢，程序檢查是否碰撞，如果沒有碰撞則轉(zhuǎn)到讀取各標(biāo)簽下一位，如果有碰撞則記錄碰撞位，并優(yōu)先選取各標(biāo)簽同樣位上數(shù)據(jù)是0 的標(biāo)簽，選取完畢后，再將所選標(biāo)簽繼續(xù)讀取判斷，直到所讀取標(biāo)簽只有一個(gè)的時(shí)候，不論后面還有多少位，都不再讀取，選定，并將標(biāo)簽代碼完整讀取并識別，然后屏蔽；之后返回離選取該標(biāo)簽最近的碰撞位，改變原來選取的0 值，現(xiàn)改為讀取這一位上標(biāo)簽值為1 的標(biāo)簽繼續(xù)進(jìn)行選取判斷，直到解決所有碰撞位并讀取完閱讀器閱讀范圍內(nèi)所有標(biāo)簽為止，程序結(jié)束。

　　3.2 改進(jìn)的二進(jìn)制算法實(shí)例解析

　　以上是我的改進(jìn)的二進(jìn)制算法的基本原理介紹，為了解釋的更加清楚，我通過五個(gè)標(biāo)簽的實(shí)例作進(jìn)一步解析如表1：

　　3.3 改進(jìn)的二進(jìn)制算法性能分析

　　本算法首先閱讀器每次只接收 lbit 的數(shù)據(jù)，因此可以避開閱讀器必須能夠確定碰撞的準(zhǔn)確的bit 位置這一困難，或者說可以避開閱讀器必須對所有標(biāo)簽準(zhǔn)確地同步這一困難，因而編碼方式更加自由，實(shí)現(xiàn)起來更加容易。另外，在標(biāo)簽的序列號較短的情況下，用此種方法的算法在時(shí)間復(fù)雜度方面也優(yōu)于二進(jìn)制搜索算法。

　　3.4 仿真

　　下面使用 Matlab 仿真來對上述算法作進(jìn)一步說明：其中n 為標(biāo)簽位數(shù)，m 為查詢次數(shù)，m 和n 均取正整數(shù)(下同)。仿真結(jié)果如圖1 所示：

圖1 兩種算法查詢次數(shù)比較

　　圖 1 中，紅色曲線表示傳統(tǒng)算法，藍(lán)色曲線表示改進(jìn)算法。從圖1 中可以明顯看出，在同等條件下，本文改進(jìn)算法標(biāo)簽的查詢次數(shù)相對于傳統(tǒng)二進(jìn)制算法查詢次數(shù)，其在標(biāo)簽數(shù)量大、標(biāo)簽ID 相似度高、碰撞位多的情況下，查詢次數(shù)增加速度明顯減慢。

　　4 結(jié)束語

　　在 RFID 系統(tǒng)的應(yīng)用中，有效地解決標(biāo)簽的碰撞問題和如何提高標(biāo)簽的識別速率對整個(gè)RFID 系統(tǒng)的應(yīng)用是至關(guān)重要的。尤其是在物流領(lǐng)域、倉庫管理中，標(biāo)簽數(shù)量多、標(biāo)簽ID相似度高的場合中。本文提出了一種改進(jìn)的RFID 防碰撞算法，與其他常用的防碰撞算法相比，如目前應(yīng)用比較廣泛的傳統(tǒng)二進(jìn)制算法，在有大量的標(biāo)簽存在、標(biāo)簽ID 度相似極高的環(huán)境中，顯示出了明顯的優(yōu)勢。

　　本文作者創(chuàng)新點(diǎn):本文主要通過閱讀古今中外的有關(guān)基于射頻識別技術(shù)的防碰撞算法，結(jié)合自己的實(shí)踐探索，從理論上分析了防碰撞的根本原理，針對傳統(tǒng)防碰撞算法中存在的終端射頻卡數(shù)量越多，UID(Ubiquitous Identifications，身份識別標(biāo)簽)位數(shù)越多，傳送時(shí)間越長的缺點(diǎn)，提出了從低層二進(jìn)制入手，運(yùn)用計(jì)算機(jī)中查找二查樹原理和路徑最優(yōu)化原理，對標(biāo)簽的選擇實(shí)行最優(yōu)化最快速的讀取算法，本文最后對改進(jìn)算法和傳統(tǒng)算法進(jìn)行仿真，從仿真結(jié)果可以看到改進(jìn)算法明顯優(yōu)于傳統(tǒng)算法，這個(gè)改進(jìn)可以有效解決防碰撞問題。

    參考文獻(xiàn)
    [1] FinkenzellerK 著，陳大譯，射頻識別技術(shù).清華大學(xué)出版社，2000
    [2] 游戰(zhàn)清.無線射頻識別技術(shù)(RFID)理論與應(yīng)用[M].北京:電子工業(yè)出版社, 2004
    [3] 張暉，王東輝．PLC 技術(shù)應(yīng)用200 例．微計(jì)算機(jī)信息，2007，4-2：253-254。
    [4] 陳博．一種類二進(jìn)制搜索的RFID 系統(tǒng)反碰撞算法及其實(shí)現(xiàn).電子器件，2006 年3 月，29 卷第一期
    [5] Draft protocol specification for a 900 MHz Class 0 Radio Frequency IdentificationTag[Z],Auto-ID Certer,2003.
    [6]吳春華、陳軍，動態(tài)ALoHA 法在解決RFID 反碰撞問題中的應(yīng)用【J].電子器件，2003 年第2 期:173 一176.