RFID系統(tǒng)中一種改良的防沖突算法的研究

　　引言 

　　無(wú)線(xiàn)射頻識(shí)別（RFID）技術(shù)是一種非接觸式的自動(dòng)識(shí)別技術(shù)，其原理是利用射頻信號(hào)的傳輸特性，對(duì)貼有標(biāo)簽的目標(biāo)加以識(shí)別并獲取相關(guān)信息。它成功地將射頻識(shí)別技術(shù)和IC卡技術(shù)結(jié)合起來(lái)，解決了無(wú)源和免接觸信號(hào)獲取這一難題。由于目前對(duì)識(shí)別距離的要求越來(lái)越高，高頻系統(tǒng)的研究已經(jīng)成為一個(gè)熱點(diǎn)。但在提供遠(yuǎn)距離多目標(biāo)識(shí)別優(yōu)點(diǎn)的同時(shí)，多個(gè)標(biāo)簽同時(shí)應(yīng)答一個(gè)閱讀器，或者多個(gè)閱讀器同時(shí)對(duì)一個(gè)標(biāo)簽進(jìn)行識(shí)別的數(shù)據(jù)沖突的情況也凸顯出來(lái)，本文中，將重點(diǎn)討論一種針對(duì)于UHF頻段的改良動(dòng)態(tài)二進(jìn)制搜索算法，用于解決這種沖突問(wèn)題。

　　1 目前基本的防沖突方法

　　RFID系統(tǒng)的防沖突問(wèn)題屬于多址通信問(wèn)題，在目前的射頻識(shí)別系統(tǒng)中，主要是采用TDMA技術(shù)，使每個(gè)電子標(biāo)簽在單獨(dú)的某個(gè)時(shí)隙內(nèi)占用信道與讀卡器進(jìn)行通信，防止碰撞的產(chǎn)生，數(shù)據(jù)能夠準(zhǔn)確地在讀卡器和電子標(biāo)簽之間進(jìn)行傳輸。實(shí)際的射頻識(shí)別系統(tǒng)常用的防沖突算法主要有ALOHA算法、時(shí)隙ALOHA算法、二進(jìn)制搜索算法和動(dòng)態(tài)二進(jìn)制搜索算法等。由于二進(jìn)制搜索算法對(duì)于標(biāo)簽硬件要求較低，實(shí)現(xiàn)靈活等特點(diǎn)，下面主要介紹基于二進(jìn)制搜索算法的一些防沖突算法及改良算法。

　　2 基于二進(jìn)制搜索算法改良的防沖突算法

　　2．1 二進(jìn)制搜索算法 

　　實(shí)際應(yīng)用中，使用較多的防沖突算法是“二進(jìn)制搜索算法”，二進(jìn)制搜索算法系統(tǒng)是由在一個(gè)讀寫(xiě)器和多個(gè)電子標(biāo)簽之間規(guī)定的相互作用順序構(gòu)成的，從同時(shí)進(jìn)入讀卡器作用范圍的標(biāo)簽中選出一個(gè)電子標(biāo)簽進(jìn)行通信。實(shí)現(xiàn)二進(jìn)制算法需要三個(gè)必要條件。

　　A 讀卡器能定位出在讀卡器中數(shù)據(jù)碰撞比特的準(zhǔn)確位置，這需要使用Manchester編碼。
　　B 標(biāo)識(shí)電子標(biāo)簽身份的序列號(hào)必須是唯一的。
　　C 需要一組指令，這組指令由讀卡器和標(biāo)簽交互之用。

　　二進(jìn)制搜索算法的工作流程如下：

　　①當(dāng)射頻卡進(jìn)入讀寫(xiě)器的工作范圍時(shí)，讀寫(xiě)器使用REQUEST（N）命令發(fā)出一個(gè)最大序列號(hào)讓所有射頻卡響應(yīng)；同一時(shí)刻開(kāi)始傳輸它們各自的序列號(hào)到讀寫(xiě)器。
　?、谧x寫(xiě)器對(duì)比射頻卡響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)，如果出現(xiàn)不一致的現(xiàn)象，根據(jù)Manchester編碼規(guī)則，在此位上的混合電平無(wú)法判斷—既不是上升沿也不是下降沿，由此可判斷出此Bit位有碰撞。
　?、郛?dāng)確定有碰撞后，把不一致比特位的數(shù)從最高位到次低次依次置1，再發(fā)送序列號(hào)，即依次排除序列號(hào)大的標(biāo)簽，直到讀寫(xiě)器對(duì)比射頻卡響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)完全一致時(shí)，說(shuō)明無(wú)碰撞。這時(shí)使用選擇命令(SELECT)就選出了一個(gè)唯一的標(biāo)簽。
　?、苓x出唯一的標(biāo)簽后，對(duì)該標(biāo)簽進(jìn)行數(shù)據(jù)交換，然后使用去選擇命令(UNSELECT)使該卡進(jìn)入“無(wú)聲”狀態(tài)，則在讀出器范圍也不再響應(yīng)(移動(dòng)該范圍后移入可再次響應(yīng))。
　?、葜貜?fù)步驟①，選擇剩余的射頻卡進(jìn)行數(shù)據(jù)交換。多次循環(huán)后即可完成所有射頻卡的讀取。

　　2．2 動(dòng)態(tài)二進(jìn)制搜索算法

    在二進(jìn)制搜索法中，電子標(biāo)簽的序列號(hào)總是一次次完整地傳輸，然而，在實(shí)際應(yīng)用中，電子標(biāo)簽的序列號(hào)一般在8個(gè)字節(jié)以上，僅僅為了選擇一個(gè)單獨(dú)的電子標(biāo)簽就不得不傳輸大量的數(shù)據(jù)。仔細(xì)的研究讀卡器和單個(gè)電子標(biāo)簽之間的數(shù)據(jù)流可以得出以下結(jié)論：

　　用X表示序列號(hào)的最高位置，當(dāng)判斷出碰撞位P后，讀卡器在REQUEST（請(qǐng)求）命令時(shí)，只需發(fā)送要搜索的序列號(hào)的已知部分（P—X）作為搜索的依據(jù)就可以了，所有在（P—X）位中的序列號(hào)與搜索依據(jù)相符的電子標(biāo)簽傳輸它們的序列號(hào)的剩余部分（0—P）即可。根據(jù)這樣的思想，把數(shù)據(jù)分成兩部分，收發(fā)雙方各自傳送其中一部分?jǐn)?shù)據(jù)，可把傳輸?shù)臄?shù)據(jù)量減小到一半，達(dá)到縮短傳送時(shí)間的目的。

　　2．3 改良的動(dòng)態(tài)二進(jìn)制搜索算法 

    從以上介紹中可以看出，無(wú)論是二進(jìn)制搜索算法還是動(dòng)態(tài)二進(jìn)制搜索算法，在發(fā)送請(qǐng)求命令給電子標(biāo)簽時(shí)，其參數(shù)傳遞的都是標(biāo)簽的序列號(hào)，沿著動(dòng)態(tài)二進(jìn)制搜索算法改進(jìn)的思路：可以再減少讀卡器每次傳輸?shù)臅r(shí)間，不直接傳送標(biāo)簽的序列號(hào)或部分序列號(hào)，而是傳送其序列號(hào)的位數(shù)。論文檢測(cè)。同時(shí)注意到每次排除一部分標(biāo)簽后，當(dāng)下次讀卡器再次請(qǐng)求時(shí)，被排除在外的標(biāo)簽同樣還會(huì)做出響應(yīng)，這些響應(yīng)是已知資源的浪費(fèi)，我們可以設(shè)計(jì)一組休眠命令（REST），使每次排除在外的標(biāo)簽處于休眠狀態(tài)，下次不再響應(yīng)。直到一輪搜索結(jié)束后再發(fā)送喚醒命令（WAKE），使休眠命令的標(biāo)簽再次參與新的搜索。

　　本改良方案主要設(shè)計(jì)了一組新的用于讀卡器與卡交互的命令來(lái)實(shí)現(xiàn)上述目的，下面對(duì)這些命令進(jìn)行說(shuō)明：

　　REQUEST(N) – 請(qǐng)求命令。該命令帶一個(gè)參數(shù)N，N表示標(biāo)簽序列號(hào)的位數(shù)。當(dāng)標(biāo)簽收到此命令后，將小于等于N位的序列號(hào)回傳給讀卡器。 
　　REST(P) – 休眠命令。該命令帶有一個(gè)參數(shù)P，P表示以0為基位的卡的序列號(hào)的第P位。當(dāng)標(biāo)簽收到此命令后，如果其序列號(hào)第P位為0，則將自身置為休眠狀態(tài)，即不再對(duì)REQUEST命令作出響應(yīng)。
　　WAKE – 喚醒命令。該命令沒(méi)有參數(shù)，當(dāng)處于休眠狀態(tài)的標(biāo)簽收到此命令后，將自身設(shè)置為正常等待狀態(tài)。
　　SELECT（S）選擇命令。該命令帶有一個(gè)參數(shù)S，S表示具體的一個(gè)卡的序列號(hào)。當(dāng)序列號(hào)為S的標(biāo)簽收到此命令后，即被選擇。
　　 　　RD—DATA（）讀卡命令。該命令沒(méi)有參數(shù)，當(dāng)被選擇的標(biāo)簽收到此命令后可以通信。
　　UNSELECT（）去選擇命令。該命令沒(méi)有參數(shù)，當(dāng)通信完成后，將標(biāo)簽去活。

　　 該改良算法的工作流程如下：
　?、僮x卡器發(fā)送REQUEST命令，參數(shù)N為序列號(hào)的位數(shù)。第一次發(fā)送序列號(hào)的最高位數(shù)，這時(shí)讀卡器內(nèi)所有的標(biāo)簽都滿(mǎn)足條件，將自身的序列號(hào)回傳給讀卡器。
　　 ② 如果讀卡器判斷出第P位發(fā)生沖突時(shí)，發(fā)送REST（P）命令，序列號(hào)第P位為0的標(biāo)簽處于休眠狀態(tài)。讀卡器再次發(fā)送REQUEST命令，參數(shù)為P-1，這時(shí)讀卡器內(nèi)排除處休眠態(tài)的其它標(biāo)簽回傳其序列號(hào)。當(dāng)讀卡器判斷出第P位發(fā)生沖突時(shí)，則再次發(fā)送REST命令，如果沒(méi)有沖突，則發(fā)送SELECT命令選擇唯一的一個(gè)標(biāo)簽進(jìn)行通信。
　　 ③通信完成后發(fā)送WAKE命令，喚醒處于休眠狀態(tài)的標(biāo)簽，重復(fù)1，2操作，直到所有的標(biāo)簽被識(shí)別完。

　　2．4 改良的動(dòng)態(tài)二進(jìn)制搜索算法的仿真分析

    ●可行性分析：該改良算法經(jīng)過(guò)了C++語(yǔ)言仿真，為簡(jiǎn)化起見(jiàn)，在仿真過(guò)程中，我們假設(shè)標(biāo)簽序列號(hào)為8位。為了模擬3個(gè)標(biāo)簽同時(shí)進(jìn)入讀卡器的情況，我們?cè)谥骶€(xiàn)程中新建了3個(gè)標(biāo)簽線(xiàn)程來(lái)實(shí)現(xiàn)這種同步，標(biāo)簽向讀卡器發(fā)送其序列號(hào)的過(guò)程由3個(gè)標(biāo)簽線(xiàn)程來(lái)完成，讀卡器發(fā)送的一系列命令由主線(xiàn)程來(lái)實(shí)現(xiàn)，由仿真結(jié)果（仿真結(jié)果圖）可以看出，這種改良的動(dòng)態(tài)二進(jìn)制搜索算法可以實(shí)現(xiàn)。

　　●執(zhí)行效率分析：
　　由二進(jìn)制搜索算法的工作流程可知，防碰撞處理是在確認(rèn)有碰撞的情況下，根據(jù)高低位不斷降值的序列號(hào)一次次進(jìn)行篩選出某一射頻卡，從而可知射頻卡的數(shù)量越多，防碰撞執(zhí)行時(shí)間就將越長(zhǎng)。平均搜索的次數(shù)N 可用下式來(lái)計(jì)算：
　　N=Integ(logM/log2) + 1 (1)
　　式中：M是讀卡器作用范圍內(nèi)標(biāo)簽的數(shù)目；Integ 表示數(shù)值取整。序列號(hào)的位數(shù)越多，每次傳送的時(shí)間加長(zhǎng)，數(shù)據(jù)傳送的時(shí)間就會(huì)增大。如每次都傳輸完整的序列號(hào)，每次時(shí)間為T(mén)，則用于傳輸序列號(hào)的通信時(shí)間為：
　　t=T×N (2)
　　動(dòng)態(tài)二進(jìn)制搜索算法在標(biāo)簽序列號(hào)位數(shù)不變的情況下，把數(shù)據(jù)分成兩部分，收發(fā)雙方各自傳送其中一部分?jǐn)?shù)據(jù)，可把傳輸?shù)臄?shù)據(jù)量減小到一半，其較二進(jìn)制搜索算法而言效率提高了50%。
　　其用于傳輸序列號(hào)的通信時(shí)間為：
　　T=1/2×T×N (3)
　　 改良型動(dòng)態(tài)二進(jìn)制搜索算法每次請(qǐng)求時(shí)不傳送序列號(hào)，而是傳送序列號(hào)的位數(shù)，其代價(jià)是每排除一次碰撞就多傳送了一個(gè)休眠指令，其平均搜索次數(shù)N可用下式來(lái)計(jì)算：
　　N=Integ(logM/log2)+ Integ(logM/log2) = 2*Integ(logM/log2)； (4)
　　其用于傳輸序列號(hào)的通信時(shí)間為：
　　T=1/SER×T×N （SER為序列號(hào)位數(shù)）(5)
　　由此可見(jiàn)，當(dāng)序列號(hào)位數(shù)SER大于2時(shí)，其效率就高于動(dòng)態(tài)二進(jìn)制算法，SER越大，改良型算法提高的效率越高。

　　● 安全性分析：
　　由于讀卡器不直接發(fā)送標(biāo)簽的序列號(hào)，而是發(fā)送序列號(hào)的位數(shù)，所以對(duì)比二進(jìn)制及動(dòng)態(tài)二進(jìn)制搜索算法有較好的安全性。
　　由于本算法只是在原理層面上仿真研究，沒(méi)有考慮到現(xiàn)實(shí)中不可避免的躁聲等因素，這方面的研究還須日后討論。