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

1. 引言

無線射頻識(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)鍵問題需要解決，例如RFID 技術(shù)的操作距離問題，安全和隱私問題，數(shù)據(jù)存儲(chǔ)問題，碰撞問題等［2］。本文是論述有關(guān)RFID 的防碰撞問題。在很多情況下，閱讀器射頻區(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)象被稱為標(biāo)簽碰撞問題［3］。RFID 系統(tǒng)會(huì)采用一定的策略或算法來避免標(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è)出多張卡的存在，卡片的返回?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í)刻開始傳輸它們的序列號(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í)，說明無碰撞。這時(shí)就選出序列號(hào)最小的數(shù)。

④選出序列號(hào)最小的數(shù)后，對(duì)該卡進(jìn)行數(shù)據(jù)交換，然后使該卡進(jìn)入“無聲”狀態(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)。查詢的次數(shù)N 可用下式來計(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，則用于傳輸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ù)，二是減少查詢次數(shù)，本算法，試圖將此兩種方法應(yīng)用到同一種防碰撞算法中。

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

本算法首先是標(biāo)簽閱讀器發(fā)出請(qǐng)求指令，等待閱讀器接收范圍內(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)簽代碼完整讀取并識(shí)別，然后屏蔽；之后返回離選取該標(biāo)簽最近的碰撞位，改變?cè)瓉磉x取的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 位置這一困難，或者說可以避開閱讀器必須對(duì)所有標(biāo)簽準(zhǔn)確地同步這一困難，因而編碼方式更加自由，實(shí)現(xiàn)起來更加容易。另外，在標(biāo)簽的序列號(hào)較短的情況下，用此種方法的算法在時(shí)間復(fù)雜度方面也優(yōu)于二進(jìn)制搜索算法。

3.4 仿真

下面使用 Matlab 仿真來對(duì)上述算法作進(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ù)相對(duì)于傳統(tǒng)二進(jìn)制算法查詢次數(shù)，其在標(biāo)簽數(shù)量大、標(biāo)簽ID 相似度高、碰撞位多的情況下，查詢次數(shù)增加速度明顯減慢。

4 結(jié)束語(yǔ)

在 RFID 系統(tǒng)的應(yīng)用中，有效地解決標(biāo)簽的碰撞問題和如何提高標(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ì)。

責(zé)任編輯：ct