RFID系統(tǒng)中一種改良的防沖突算法的研究
EEworld
EEworld
摘要: 摘要:無線射頻識別(RFID)技術是一種非接觸式的自動識別技術。多個標簽同時應答一個閱讀器。將重點討論一種針對...
Abstract:
Key words :
關鍵字:RFID系統(tǒng) 防沖突算法
引言
無線射頻識別(RFID)技術是一種非接觸式的自動識別技術,其原理是利用射頻信號的傳輸特性,對貼有標簽的目標加以識別并獲取相關信息。它成功地將射頻識別技術和IC卡技術結(jié)合起來,解決了無源和免接觸信號獲取這一難題。由于目前對識別距離的要求越來越高,高頻系統(tǒng)的研究已經(jīng)成為一個熱點。但在提供遠距離多目標識別優(yōu)點的同時,多個標簽同時應答一個閱讀器,或者多個閱讀器同時對一個標簽進行識別的數(shù)據(jù)沖突的情況也凸顯出來,本文中,將重點討論一種針對于UHF頻段的改良動態(tài)二進制搜索算法,用于解決這種沖突問題。
1 目前基本的防沖突方法
RFID系統(tǒng)的防沖突問題屬于多址通信問題,在目前的射頻識別系統(tǒng)中,主要是采用TDMA技術,使每個電子標簽在單獨的某個時隙內(nèi)占用信道與讀卡器進行通信,防止碰撞的產(chǎn)生,數(shù)據(jù)能夠準確地在讀卡器和電子標簽之間進行傳輸。實際的射頻識別系統(tǒng)常用的防沖突算法主要有ALOHA算法、時隙ALOHA算法、二進制搜索算法和動態(tài)二進制搜索算法等。由于二進制搜索算法對于標簽硬件要求較低,實現(xiàn)靈活等特點,下面主要介紹基于二進制搜索算法的一些防沖突算法及改良算法。
2 基于二進制搜索算法改良的防沖突算法
2.1 二進制搜索算法
實際應用中,使用較多的防沖突算法是“二進制搜索算法”,二進制搜索算法系統(tǒng)是由在一個讀寫器和多個電子標簽之間規(guī)定的相互作用順序構(gòu)成的,從同時進入讀卡器作用范圍的標簽中選出一個電子標簽進行通信。實現(xiàn)二進制算法需要三個必要條件。
A 讀卡器能定位出在讀卡器中數(shù)據(jù)碰撞比特的準確位置,這需要使用Manchester編碼。
B 標識電子標簽身份的序列號必須是唯一的。
C 需要一組指令,這組指令由讀卡器和標簽交互之用。
二進制搜索算法的工作流程如下:
①當射頻卡進入讀寫器的工作范圍時,讀寫器使用REQUEST(N)命令發(fā)出一個最大序列號讓所有射頻卡響應;同一時刻開始傳輸它們各自的序列號到讀寫器。
?、谧x寫器對比射頻卡響應的序列號的相同位數(shù)上的數(shù),如果出現(xiàn)不一致的現(xiàn)象,根據(jù)Manchester編碼規(guī)則,在此位上的混合電平無法判斷—既不是上升沿也不是下降沿,由此可判斷出此Bit位有碰撞。
?、郛敶_定有碰撞后,把不一致比特位的數(shù)從最高位到次低次依次置1,再發(fā)送序列號,即依次排除序列號大的標簽,直到讀寫器對比射頻卡響應的序列號的相同位數(shù)上的數(shù)完全一致時,說明無碰撞。這時使用選擇命令(SELECT)就選出了一個唯一的標簽。
?、苓x出唯一的標簽后,對該標簽進行數(shù)據(jù)交換,然后使用去選擇命令(UNSELECT)使該卡進入“無聲”狀態(tài),則在讀出器范圍也不再響應(移動該范圍后移入可再次響應)。
?、葜貜筒襟E①,選擇剩余的射頻卡進行數(shù)據(jù)交換。多次循環(huán)后即可完成所有射頻卡的讀取。
2.2 動態(tài)二進制搜索算法
在二進制搜索法中,電子標簽的序列號總是一次次完整地傳輸,然而,在實際應用中,電子標簽的序列號一般在8個字節(jié)以上,僅僅為了選擇一個單獨的電子標簽就不得不傳輸大量的數(shù)據(jù)。仔細的研究讀卡器和單個電子標簽之間的數(shù)據(jù)流可以得出以下結(jié)論:
用X表示序列號的最高位置,當判斷出碰撞位P后,讀卡器在REQUEST(請求)命令時,只需發(fā)送要搜索的序列號的已知部分(P—X)作為搜索的依據(jù)就可以了,所有在(P—X)位中的序列號與搜索依據(jù)相符的電子標簽傳輸它們的序列號的剩余部分(0—P)即可。根據(jù)這樣的思想,把數(shù)據(jù)分成兩部分,收發(fā)雙方各自傳送其中一部分數(shù)據(jù),可把傳輸?shù)臄?shù)據(jù)量減小到一半,達到縮短傳送時間的目的。
2.3 改良的動態(tài)二進制搜索算法
從以上介紹中可以看出,無論是二進制搜索算法還是動態(tài)二進制搜索算法,在發(fā)送請求命令給電子標簽時,其參數(shù)傳遞的都是標簽的序列號,沿著動態(tài)二進制搜索算法改進的思路:可以再減少讀卡器每次傳輸?shù)臅r間,不直接傳送標簽的序列號或部分序列號,而是傳送其序列號的位數(shù)。論文檢測。同時注意到每次排除一部分標簽后,當下次讀卡器再次請求時,被排除在外的標簽同樣還會做出響應,這些響應是已知資源的浪費,我們可以設計一組休眠命令(REST),使每次排除在外的標簽處于休眠狀態(tài),下次不再響應。直到一輪搜索結(jié)束后再發(fā)送喚醒命令(WAKE),使休眠命令的標簽再次參與新的搜索。
本改良方案主要設計了一組新的用于讀卡器與卡交互的命令來實現(xiàn)上述目的,下面對這些命令進行說明:
REQUEST(N) – 請求命令。該命令帶一個參數(shù)N,N表示標簽序列號的位數(shù)。當標簽收到此命令后,將小于等于N位的序列號回傳給讀卡器。
REST(P) – 休眠命令。該命令帶有一個參數(shù)P,P表示以0為基位的卡的序列號的第P位。當標簽收到此命令后,如果其序列號第P位為0,則將自身置為休眠狀態(tài),即不再對REQUEST命令作出響應。
WAKE – 喚醒命令。該命令沒有參數(shù),當處于休眠狀態(tài)的標簽收到此命令后,將自身設置為正常等待狀態(tài)。
SELECT(S)選擇命令。該命令帶有一個參數(shù)S,S表示具體的一個卡的序列號。當序列號為S的標簽收到此命令后,即被選擇。
RD—DATA()讀卡命令。該命令沒有參數(shù),當被選擇的標簽收到此命令后可以通信。
UNSELECT()去選擇命令。該命令沒有參數(shù),當通信完成后,將標簽去活。
該改良算法的工作流程如下:
①讀卡器發(fā)送REQUEST命令,參數(shù)N為序列號的位數(shù)。第一次發(fā)送序列號的最高位數(shù),這時讀卡器內(nèi)所有的標簽都滿足條件,將自身的序列號回傳給讀卡器。
② 如果讀卡器判斷出第P位發(fā)生沖突時,發(fā)送REST(P)命令,序列號第P位為0的標簽處于休眠狀態(tài)。讀卡器再次發(fā)送REQUEST命令,參數(shù)為P-1,這時讀卡器內(nèi)排除處休眠態(tài)的其它標簽回傳其序列號。當讀卡器判斷出第P位發(fā)生沖突時,則再次發(fā)送REST命令,如果沒有沖突,則發(fā)送SELECT命令選擇唯一的一個標簽進行通信。
③通信完成后發(fā)送WAKE命令,喚醒處于休眠狀態(tài)的標簽,重復1,2操作,直到所有的標簽被識別完。
2.4 改良的動態(tài)二進制搜索算法的仿真分析
●可行性分析:該改良算法經(jīng)過了C++語言仿真,為簡化起見,在仿真過程中,我們假設標簽序列號為8位。為了模擬3個標簽同時進入讀卡器的情況,我們在主線程中新建了3個標簽線程來實現(xiàn)這種同步,標簽向讀卡器發(fā)送其序列號的過程由3個標簽線程來完成,讀卡器發(fā)送的一系列命令由主線程來實現(xiàn),由仿真結(jié)果(仿真結(jié)果圖)可以看出,這種改良的動態(tài)二進制搜索算法可以實現(xiàn)。
由二進制搜索算法的工作流程可知,防碰撞處理是在確認有碰撞的情況下,根據(jù)高低位不斷降值的序列號一次次進行篩選出某一射頻卡,從而可知射頻卡的數(shù)量越多,防碰撞執(zhí)行時間就將越長。平均搜索的次數(shù)N 可用下式來計算:
N=Integ(logM/log2) + 1 (1)
式中:M是讀卡器作用范圍內(nèi)標簽的數(shù)目;Integ 表示數(shù)值取整。序列號的位數(shù)越多,每次傳送的時間加長,數(shù)據(jù)傳送的時間就會增大。如每次都傳輸完整的序列號,每次時間為T,則用于傳輸序列號的通信時間為:
t=T×N (2)
動態(tài)二進制搜索算法在標簽序列號位數(shù)不變的情況下,把數(shù)據(jù)分成兩部分,收發(fā)雙方各自傳送其中一部分數(shù)據(jù),可把傳輸?shù)臄?shù)據(jù)量減小到一半,其較二進制搜索算法而言效率提高了50%。
其用于傳輸序列號的通信時間為:
T=1/2×T×N (3)
改良型動態(tài)二進制搜索算法每次請求時不傳送序列號,而是傳送序列號的位數(shù),其代價是每排除一次碰撞就多傳送了一個休眠指令,其平均搜索次數(shù)N可用下式來計算:
N=Integ(logM/log2)+ Integ(logM/log2) = 2*Integ(logM/log2); (4)
其用于傳輸序列號的通信時間為:
T=1/SER×T×N (SER為序列號位數(shù))(5)
由此可見,當序列號位數(shù)SER大于2時,其效率就高于動態(tài)二進制算法,SER越大,改良型算法提高的效率越高。
● 安全性分析:
由于讀卡器不直接發(fā)送標簽的序列號,而是發(fā)送序列號的位數(shù),所以對比二進制及動態(tài)二進制搜索算法有較好的安全性。
由于本算法只是在原理層面上仿真研究,沒有考慮到現(xiàn)實中不可避免的躁聲等因素,這方面的研究還須日后討論。
無線射頻識別(RFID)技術是一種非接觸式的自動識別技術,其原理是利用射頻信號的傳輸特性,對貼有標簽的目標加以識別并獲取相關信息。它成功地將射頻識別技術和IC卡技術結(jié)合起來,解決了無源和免接觸信號獲取這一難題。由于目前對識別距離的要求越來越高,高頻系統(tǒng)的研究已經(jīng)成為一個熱點。但在提供遠距離多目標識別優(yōu)點的同時,多個標簽同時應答一個閱讀器,或者多個閱讀器同時對一個標簽進行識別的數(shù)據(jù)沖突的情況也凸顯出來,本文中,將重點討論一種針對于UHF頻段的改良動態(tài)二進制搜索算法,用于解決這種沖突問題。
1 目前基本的防沖突方法
RFID系統(tǒng)的防沖突問題屬于多址通信問題,在目前的射頻識別系統(tǒng)中,主要是采用TDMA技術,使每個電子標簽在單獨的某個時隙內(nèi)占用信道與讀卡器進行通信,防止碰撞的產(chǎn)生,數(shù)據(jù)能夠準確地在讀卡器和電子標簽之間進行傳輸。實際的射頻識別系統(tǒng)常用的防沖突算法主要有ALOHA算法、時隙ALOHA算法、二進制搜索算法和動態(tài)二進制搜索算法等。由于二進制搜索算法對于標簽硬件要求較低,實現(xiàn)靈活等特點,下面主要介紹基于二進制搜索算法的一些防沖突算法及改良算法。
2 基于二進制搜索算法改良的防沖突算法
2.1 二進制搜索算法
實際應用中,使用較多的防沖突算法是“二進制搜索算法”,二進制搜索算法系統(tǒng)是由在一個讀寫器和多個電子標簽之間規(guī)定的相互作用順序構(gòu)成的,從同時進入讀卡器作用范圍的標簽中選出一個電子標簽進行通信。實現(xiàn)二進制算法需要三個必要條件。
A 讀卡器能定位出在讀卡器中數(shù)據(jù)碰撞比特的準確位置,這需要使用Manchester編碼。
B 標識電子標簽身份的序列號必須是唯一的。
C 需要一組指令,這組指令由讀卡器和標簽交互之用。
二進制搜索算法的工作流程如下:
①當射頻卡進入讀寫器的工作范圍時,讀寫器使用REQUEST(N)命令發(fā)出一個最大序列號讓所有射頻卡響應;同一時刻開始傳輸它們各自的序列號到讀寫器。
?、谧x寫器對比射頻卡響應的序列號的相同位數(shù)上的數(shù),如果出現(xiàn)不一致的現(xiàn)象,根據(jù)Manchester編碼規(guī)則,在此位上的混合電平無法判斷—既不是上升沿也不是下降沿,由此可判斷出此Bit位有碰撞。
?、郛敶_定有碰撞后,把不一致比特位的數(shù)從最高位到次低次依次置1,再發(fā)送序列號,即依次排除序列號大的標簽,直到讀寫器對比射頻卡響應的序列號的相同位數(shù)上的數(shù)完全一致時,說明無碰撞。這時使用選擇命令(SELECT)就選出了一個唯一的標簽。
?、苓x出唯一的標簽后,對該標簽進行數(shù)據(jù)交換,然后使用去選擇命令(UNSELECT)使該卡進入“無聲”狀態(tài),則在讀出器范圍也不再響應(移動該范圍后移入可再次響應)。
?、葜貜筒襟E①,選擇剩余的射頻卡進行數(shù)據(jù)交換。多次循環(huán)后即可完成所有射頻卡的讀取。
2.2 動態(tài)二進制搜索算法
在二進制搜索法中,電子標簽的序列號總是一次次完整地傳輸,然而,在實際應用中,電子標簽的序列號一般在8個字節(jié)以上,僅僅為了選擇一個單獨的電子標簽就不得不傳輸大量的數(shù)據(jù)。仔細的研究讀卡器和單個電子標簽之間的數(shù)據(jù)流可以得出以下結(jié)論:
用X表示序列號的最高位置,當判斷出碰撞位P后,讀卡器在REQUEST(請求)命令時,只需發(fā)送要搜索的序列號的已知部分(P—X)作為搜索的依據(jù)就可以了,所有在(P—X)位中的序列號與搜索依據(jù)相符的電子標簽傳輸它們的序列號的剩余部分(0—P)即可。根據(jù)這樣的思想,把數(shù)據(jù)分成兩部分,收發(fā)雙方各自傳送其中一部分數(shù)據(jù),可把傳輸?shù)臄?shù)據(jù)量減小到一半,達到縮短傳送時間的目的。
2.3 改良的動態(tài)二進制搜索算法
從以上介紹中可以看出,無論是二進制搜索算法還是動態(tài)二進制搜索算法,在發(fā)送請求命令給電子標簽時,其參數(shù)傳遞的都是標簽的序列號,沿著動態(tài)二進制搜索算法改進的思路:可以再減少讀卡器每次傳輸?shù)臅r間,不直接傳送標簽的序列號或部分序列號,而是傳送其序列號的位數(shù)。論文檢測。同時注意到每次排除一部分標簽后,當下次讀卡器再次請求時,被排除在外的標簽同樣還會做出響應,這些響應是已知資源的浪費,我們可以設計一組休眠命令(REST),使每次排除在外的標簽處于休眠狀態(tài),下次不再響應。直到一輪搜索結(jié)束后再發(fā)送喚醒命令(WAKE),使休眠命令的標簽再次參與新的搜索。
本改良方案主要設計了一組新的用于讀卡器與卡交互的命令來實現(xiàn)上述目的,下面對這些命令進行說明:
REQUEST(N) – 請求命令。該命令帶一個參數(shù)N,N表示標簽序列號的位數(shù)。當標簽收到此命令后,將小于等于N位的序列號回傳給讀卡器。
REST(P) – 休眠命令。該命令帶有一個參數(shù)P,P表示以0為基位的卡的序列號的第P位。當標簽收到此命令后,如果其序列號第P位為0,則將自身置為休眠狀態(tài),即不再對REQUEST命令作出響應。
WAKE – 喚醒命令。該命令沒有參數(shù),當處于休眠狀態(tài)的標簽收到此命令后,將自身設置為正常等待狀態(tài)。
SELECT(S)選擇命令。該命令帶有一個參數(shù)S,S表示具體的一個卡的序列號。當序列號為S的標簽收到此命令后,即被選擇。
RD—DATA()讀卡命令。該命令沒有參數(shù),當被選擇的標簽收到此命令后可以通信。
UNSELECT()去選擇命令。該命令沒有參數(shù),當通信完成后,將標簽去活。
該改良算法的工作流程如下:
①讀卡器發(fā)送REQUEST命令,參數(shù)N為序列號的位數(shù)。第一次發(fā)送序列號的最高位數(shù),這時讀卡器內(nèi)所有的標簽都滿足條件,將自身的序列號回傳給讀卡器。
② 如果讀卡器判斷出第P位發(fā)生沖突時,發(fā)送REST(P)命令,序列號第P位為0的標簽處于休眠狀態(tài)。讀卡器再次發(fā)送REQUEST命令,參數(shù)為P-1,這時讀卡器內(nèi)排除處休眠態(tài)的其它標簽回傳其序列號。當讀卡器判斷出第P位發(fā)生沖突時,則再次發(fā)送REST命令,如果沒有沖突,則發(fā)送SELECT命令選擇唯一的一個標簽進行通信。
③通信完成后發(fā)送WAKE命令,喚醒處于休眠狀態(tài)的標簽,重復1,2操作,直到所有的標簽被識別完。
2.4 改良的動態(tài)二進制搜索算法的仿真分析
●可行性分析:該改良算法經(jīng)過了C++語言仿真,為簡化起見,在仿真過程中,我們假設標簽序列號為8位。為了模擬3個標簽同時進入讀卡器的情況,我們在主線程中新建了3個標簽線程來實現(xiàn)這種同步,標簽向讀卡器發(fā)送其序列號的過程由3個標簽線程來完成,讀卡器發(fā)送的一系列命令由主線程來實現(xiàn),由仿真結(jié)果(仿真結(jié)果圖)可以看出,這種改良的動態(tài)二進制搜索算法可以實現(xiàn)。
●執(zhí)行效率分析:
由二進制搜索算法的工作流程可知,防碰撞處理是在確認有碰撞的情況下,根據(jù)高低位不斷降值的序列號一次次進行篩選出某一射頻卡,從而可知射頻卡的數(shù)量越多,防碰撞執(zhí)行時間就將越長。平均搜索的次數(shù)N 可用下式來計算:
N=Integ(logM/log2) + 1 (1)
式中:M是讀卡器作用范圍內(nèi)標簽的數(shù)目;Integ 表示數(shù)值取整。序列號的位數(shù)越多,每次傳送的時間加長,數(shù)據(jù)傳送的時間就會增大。如每次都傳輸完整的序列號,每次時間為T,則用于傳輸序列號的通信時間為:
t=T×N (2)
動態(tài)二進制搜索算法在標簽序列號位數(shù)不變的情況下,把數(shù)據(jù)分成兩部分,收發(fā)雙方各自傳送其中一部分數(shù)據(jù),可把傳輸?shù)臄?shù)據(jù)量減小到一半,其較二進制搜索算法而言效率提高了50%。
其用于傳輸序列號的通信時間為:
T=1/2×T×N (3)
改良型動態(tài)二進制搜索算法每次請求時不傳送序列號,而是傳送序列號的位數(shù),其代價是每排除一次碰撞就多傳送了一個休眠指令,其平均搜索次數(shù)N可用下式來計算:
N=Integ(logM/log2)+ Integ(logM/log2) = 2*Integ(logM/log2); (4)
其用于傳輸序列號的通信時間為:
T=1/SER×T×N (SER為序列號位數(shù))(5)
由此可見,當序列號位數(shù)SER大于2時,其效率就高于動態(tài)二進制算法,SER越大,改良型算法提高的效率越高。
● 安全性分析:
由于讀卡器不直接發(fā)送標簽的序列號,而是發(fā)送序列號的位數(shù),所以對比二進制及動態(tài)二進制搜索算法有較好的安全性。
由于本算法只是在原理層面上仿真研究,沒有考慮到現(xiàn)實中不可避免的躁聲等因素,這方面的研究還須日后討論。
此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權禁止轉(zhuǎn)載。