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