1. 引言
無(wú)線(xiàn)射頻識(shí)別技術(shù)(Radio Frequency Identific -ation RFID)是從二十世紀(jì)90 年代興起的一項(xiàng)非接觸式自動(dòng)識(shí)別技術(shù)。它是利用電磁原理進(jìn)行非接觸式雙向通信，以達(dá)到自動(dòng)識(shí)別目標(biāo)對(duì)象并獲取相關(guān)數(shù)據(jù)的目的。RFID 己被廣泛應(yīng)用于工業(yè)自動(dòng)化、商業(yè)自動(dòng)化、交通運(yùn)輸控制管理等眾多領(lǐng)域[１]。隨著成本的下降和標(biāo)準(zhǔn)化的實(shí)施，RFID 技術(shù)的全面推廣和普遍應(yīng)用將是不可逆轉(zhuǎn)的趨勢(shì)．
但 RFID 技術(shù)也存在著很多關(guān)鍵問(wèn)題需要解決，例如RFID 技術(shù)的操作距離問(wèn)題，安全和隱私問(wèn)題，數(shù)據(jù)存儲(chǔ)問(wèn)題，碰撞問(wèn)題等[2]。本文是論述有關(guān)RFID 的防碰撞問(wèn)題。在很多情況下，閱讀器射頻區(qū)可能會(huì)有多個(gè)標(biāo)簽存在，面對(duì)閱讀器發(fā)出的指令，每個(gè)標(biāo)簽都會(huì)響應(yīng)，所以標(biāo)簽的響應(yīng)信息會(huì)產(chǎn)生疊混的現(xiàn)象，在RFID 技術(shù)中這種現(xiàn)象被稱(chēng)為標(biāo)簽碰撞問(wèn)題[3]。RFID 系統(tǒng)會(huì)采用一定的策略或算法來(lái)避免標(biāo)簽碰撞現(xiàn)象的發(fā)生，控制標(biāo)簽的響應(yīng)信息逐個(gè)通過(guò)射頻信道被閱讀器接收。防碰撞問(wèn)題的研究主要解決如何快速和準(zhǔn)確地從多個(gè)標(biāo)簽中選出一個(gè)與閱讀器進(jìn)行數(shù)據(jù)交流，而其他的標(biāo)簽同樣可以從接下來(lái)的防碰撞循環(huán)中選出與閱讀器通信。
2 傳統(tǒng)二進(jìn)制算法
2.1 傳統(tǒng)二進(jìn)制算法的基本原理
在二進(jìn)制搜索算法中，要能夠檢測(cè)出多張卡的存在，卡片的返回?cái)?shù)據(jù)必須具有唯一性，且卡片在傳輸其UID(Ubiquitous Identifications，身份識(shí)別標(biāo)簽)時(shí)必須準(zhǔn)確、快速、同步，這是防碰撞檢測(cè)的關(guān)鍵。
傳統(tǒng)二進(jìn)制算法流程是，當(dāng)閱讀器發(fā)出的序列號(hào)大于標(biāo)簽序列號(hào)時(shí)，則閱讀器作出響應(yīng)。根據(jù)這一特點(diǎn)，傳統(tǒng)二進(jìn)制算法[4]的工作流程是:
①標(biāo)簽進(jìn)入閱讀器的工作范圍，閱讀器發(fā)出一個(gè)最大序列號(hào)讓所有標(biāo)簽響應(yīng);同一時(shí)刻開(kāi)始傳輸它們的序列號(hào)到閱讀器的接收模塊。
②閱讀器對(duì)比標(biāo)簽響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)，如果出現(xiàn)不一致的現(xiàn)象，則可判斷出該位有碰撞。
③確定有碰撞后，把有不一致位的數(shù)從最高位到最低位依次置0 再輸出系列號(hào)，即依次排除序列號(hào)大的數(shù)，循環(huán)至閱讀器對(duì)比標(biāo)簽響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)完全一致時(shí)，說(shuō)明無(wú)碰撞。這時(shí)就選出序列號(hào)最小的數(shù)。
④選出序列號(hào)最小的數(shù)后，對(duì)該卡進(jìn)行數(shù)據(jù)交換，然后使該卡進(jìn)入“無(wú)聲”狀態(tài)，則在閱讀器范圍也不再響應(yīng)(重新移入該標(biāo)簽才可再次響應(yīng))。
⑤重復(fù)流程①，選出序列號(hào)倒數(shù)第二的標(biāo)簽進(jìn)行數(shù)據(jù)交換。
⑥多次循環(huán)后可完成所有標(biāo)簽的讀取。
2.2 傳統(tǒng)二進(jìn)制算法的傳輸時(shí)間
由傳統(tǒng)二進(jìn)制算法的工作流程可知，防碰撞處理是在確認(rèn)有碰撞的情況下，根據(jù)高低位不斷降值的序列號(hào)一次次進(jìn)行篩選出某一射頻卡，從而可知標(biāo)簽的數(shù)量越多，防碰撞執(zhí)行時(shí)間就將越長(zhǎng)。查詢(xún)的次數(shù)N 可用下式來(lái)計(jì)算:N=Integ(logM/log2)+l 式中:M 是終端作用范圍內(nèi)射頻卡片數(shù)目;Integ 表示數(shù)值取整。UID 的位數(shù)越多(如ICODE 達(dá)64 位[5])，每次傳送的時(shí)間加長(zhǎng)，數(shù)據(jù)傳送的時(shí)間就會(huì)增大。如每次都傳輸完整的UID，時(shí)間為T(mén)，則用于傳輸U(kuò)ID 的通信時(shí)間為:t=T×N 即終端作用范圍內(nèi)射頻卡片數(shù)越多，UID 位數(shù)越多，傳送時(shí)間越長(zhǎng)，總的防碰撞執(zhí)行時(shí)間肯定也就越長(zhǎng)。
3. 改進(jìn)的二進(jìn)制算法
針對(duì)采用傳統(tǒng)二進(jìn)制搜索算法時(shí)終端射頻卡片數(shù)越多，UID 位數(shù)越長(zhǎng)，傳送時(shí)間越長(zhǎng)的缺點(diǎn)，目前提出了很多改良防碰撞算法，如：ALOHA 算法[6]， EPC 動(dòng)態(tài)二進(jìn)制算法[7]，跳躍式二進(jìn)制算法[8]等，歸納一下基本采用兩種方法改良算法的性能，一是減少傳輸數(shù)據(jù)的字節(jié)數(shù)，二是減少查詢(xún)次數(shù)，本算法，試圖將此兩種方法應(yīng)用到同一種防碰撞算法中。
3.1 改進(jìn)的二進(jìn)制算法的基本原理
本算法首先是標(biāo)簽閱讀器發(fā)出請(qǐng)求指令，等待閱讀器接收范圍內(nèi)所有標(biāo)簽第一位回應(yīng)，標(biāo)簽回應(yīng)完畢，程序檢查是否碰撞，如果沒(méi)有碰撞則轉(zhuǎn)到讀取各標(biāo)簽下一位，如果有碰撞則記錄碰撞位，并優(yōu)先選取各標(biāo)簽同樣位上數(shù)據(jù)是0 的標(biāo)簽，選取完畢后，再將所選標(biāo)簽繼續(xù)讀取判斷，直到所讀取標(biāo)簽只有一個(gè)的時(shí)候，不論后面還有多少位，都不再讀取，選定，并將標(biāo)簽代碼完整讀取并識(shí)別，然后屏蔽；之后返回離選取該標(biāo)簽最近的碰撞位，改變?cè)瓉?lái)選取的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)制算法的基本原理介紹，為了解釋的更加清楚，我通過(guò)五個(gè)標(biāo)簽的實(shí)例作進(jìn)一步解析如表1：
3.3 改進(jìn)的二進(jìn)制算法性能分析
本算法首先閱讀器每次只接收 lbit 的數(shù)據(jù)，因此可以避開(kāi)閱讀器必須能夠確定碰撞的準(zhǔn)確的bit 位置這一困難，或者說(shuō)可以避開(kāi)閱讀器必須對(duì)所有標(biāo)簽準(zhǔn)確地同步這一困難，因而編碼方式更加自由，實(shí)現(xiàn)起來(lái)更加容易。另外，在標(biāo)簽的序列號(hào)較短的情況下，用此種方法的算法在時(shí)間復(fù)雜度方面也優(yōu)于二進(jìn)制搜索算法。
3.4 仿真
下面使用 Matlab 仿真來(lái)對(duì)上述算法作進(jìn)一步說(shuō)明：其中n 為標(biāo)簽位數(shù)，m 為查詢(xún)次數(shù)，m 和n 均取正整數(shù)(下同)。仿真結(jié)果如圖1 所示：
圖1 兩種算法查詢(xún)次數(shù)比較
圖 1 中，紅色曲線(xiàn)表示傳統(tǒng)算法，藍(lán)色曲線(xiàn)表示改進(jìn)算法。從圖1 中可以明顯看出，在同等條件下，本文改進(jìn)算法標(biāo)簽的查詢(xún)次數(shù)相對(duì)于傳統(tǒng)二進(jìn)制算法查詢(xún)次數(shù)，其在標(biāo)簽數(shù)量大、標(biāo)簽ID 相似度高、碰撞位多的情況下，查詢(xún)次數(shù)增加速度明顯減慢。
4 結(jié)束語(yǔ)
在 RFID 系統(tǒng)的應(yīng)用中，有效地解決標(biāo)簽的碰撞問(wèn)題和如何提高標(biāo)簽的識(shí)別速率對(duì)整個(gè)RFID 系統(tǒng)的應(yīng)用是至關(guān)重要的。尤其是在物流領(lǐng)域、倉(cāng)庫(kù)管理中，標(biāo)簽數(shù)量多、標(biāo)簽ID相似度高的場(chǎng)合中。本文提出了一種改進(jìn)的RFID 防碰撞算法，與其他常用的防碰撞算法相比，如目前應(yīng)用比較廣泛的傳統(tǒng)二進(jìn)制算法，在有大量的標(biāo)簽存在、標(biāo)簽ID 度相似極高的環(huán)境中，顯示出了明顯的優(yōu)勢(shì)。
本文作者創(chuàng)新點(diǎn):本文主要通過(guò)閱讀古今中外的有關(guān)基于射頻識(shí)別技術(shù)的防碰撞算法，結(jié)合自己的實(shí)踐探索，從理論上分析了防碰撞的根本原理，針對(duì)傳統(tǒng)防碰撞算法中存在的終端射頻卡數(shù)量越多，UID(Ubiquitous Identifications，身份識(shí)別標(biāo)簽)位數(shù)越多，傳送時(shí)間越長(zhǎng)的缺點(diǎn)，提出了從低層二進(jìn)制入手，運(yùn)用計(jì)算機(jī)中查找二查樹(shù)原理和路徑最優(yōu)化原理，對(duì)標(biāo)簽的選擇實(shí)行最優(yōu)化最快速的讀取算法，本文最后對(duì)改進(jìn)算法和傳統(tǒng)算法進(jìn)行仿真，從仿真結(jié)果可以看到改進(jìn)算法明顯優(yōu)于傳統(tǒng)算法，這個(gè)改進(jìn)可以有效解決防碰撞問(wèn)題。
參考文獻(xiàn)
[1] FinkenzellerK 著，陳大譯，射頻識(shí)別技術(shù).清華大學(xué)出版社，2000
[2] 游戰(zhàn)清.無(wú)線(xiàn)射頻識(shí)別技術(shù)(RFID)理論與應(yīng)用[M].北京:電子工業(yè)出版社, 2004
[3] 張暉，王東輝．PLC 技術(shù)應(yīng)用200 例．微計(jì)算機(jī)信息，2007，4-2：253-254。
[4] 陳博．一種類(lèi)二進(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]吳春華、陳軍，動(dòng)態(tài)ALoHA 法在解決RFID 反碰撞問(wèn)題中的應(yīng)用【J].電子器件，2003 年第2 期:173 一176.
1
