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

　　引言

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

　　1目前基本的防沖突方法

　　RFID系統(tǒng)的防沖突問題屬于多址通信問題，在目前的射頻識別系統(tǒng)中，主要是采用TDMA技術(shù)，使每個電子標(biāo)簽在單獨(dú)的某個時隙內(nèi)占用信道與讀卡器進(jìn)行通信，防止碰撞的產(chǎn)生，數(shù)據(jù)能夠準(zhǔn)確地在讀卡器和電子標(biāo)簽之間進(jìn)行傳輸。實(shí)際的射頻識別系統(tǒng)常用的防沖突算法主要有ALOHA算法、時隙ALOHA算法、二進(jìn)制搜索算法和動態(tài)二進(jìn)制搜索算法等。由于二進(jìn)制搜索算法對于標(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)是由在一個讀寫器和多個電子標(biāo)簽之間規(guī)定的相互作用順序構(gòu)成的，從同時進(jìn)入讀卡器作用范圍的標(biāo)簽中選出一個電子標(biāo)簽進(jìn)行通信。實(shí)現(xiàn)二進(jìn)制算法需要三個必要條件。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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