1. 引言

　　無線射頻識別技術(Radio Frequency Identific -ation RFID)是從二十世紀90 年代興起的一項非接觸式自動識別技術。它是利用電磁原理進行非接觸式雙向通信，以達到自動識別目標對象并獲取相關數據的目的。RFID 己被廣泛應用于工業自動化、商業自動化、交通運輸控制管理等眾多領域[１]。隨著成本的下降和標準化的實施，RFID 技術的全面推廣和普遍應用將是不可逆轉的趨勢．

　　但 RFID 技術也存在著很多關鍵問題需要解決，例如RFID 技術的操作距離問題，安全和隱私問題，數據存儲問題，碰撞問題等[2]。本文是論述有關RFID 的防碰撞問題。在很多情況下，閱讀器射頻區可能會有多個標簽存在，面對閱讀器發出的指令，每個標簽都會響應，所以標簽的響應信息會產生疊混的現象，在RFID 技術中這種現象被稱為標簽碰撞問題[3]。RFID 系統會采用一定的策略或算法來避免標簽碰撞現象的發生，控制標簽的響應信息逐個通過射頻信道被閱讀器接收。防碰撞問題的研究主要解決如何快速和準確地從多個標簽中選出一個與閱讀器進行數據交流，而其他的標簽同樣可以從接下來的防碰撞循環中選出與閱讀器通信。

　　2 傳統二進制算法

　　2.1 傳統二進制算法的基本原理

　　在二進制搜索算法中，要能夠檢測出多張卡的存在，卡片的返回數據必須具有唯一性，且卡片在傳輸其UID(Ubiquitous Identifications，身份識別標簽)時必須準確、快速、同步，這是防碰撞檢測的關鍵。

　　傳統二進制算法流程是，當閱讀器發出的序列號大于標簽序列號時，則閱讀器作出響應。根據這一特點，傳統二進制算法[4]的工作流程是:

　?、贅撕炦M入閱讀器的工作范圍，閱讀器發出一個最大序列號讓所有標簽響應;同一時刻開始傳輸它們的序列號到閱讀器的接收模塊。
　?、陂喿x器對比標簽響應的序列號的相同位數上的數，如果出現不一致的現象，則可判斷出該位有碰撞。
　?、鄞_定有碰撞后，把有不一致位的數從最高位到最低位依次置0 再輸出系列號，即依次排除序列號大的數，循環至閱讀器對比標簽響應的序列號的相同位數上的數完全一致時，說明無碰撞。這時就選出序列號最小的數。
　　④選出序列號最小的數后，對該卡進行數據交換，然后使該卡進入“無聲”狀態，則在閱讀器范圍也不再響應(重新移入該標簽才可再次響應)。
　?、葜貜土鞒挞伲x出序列號倒數第二的標簽進行數據交換。
　　⑥多次循環后可完成所有標簽的讀取。

　　2.2 傳統二進制算法的傳輸時間

　　由傳統二進制算法的工作流程可知，防碰撞處理是在確認有碰撞的情況下，根據高低位不斷降值的序列號一次次進行篩選出某一射頻卡，從而可知標簽的數量越多，防碰撞執行時間就將越長。查詢的次數N 可用下式來計算:N=Integ(logM/log2)+l 式中:M 是終端作用范圍內射頻卡片數目;Integ 表示數值取整。UID 的位數越多(如ICODE 達64 位[5])，每次傳送的時間加長，數據傳送的時間就會增大。如每次都傳輸完整的UID，時間為T，則用于傳輸UID 的通信時間為:t=T×N 即終端作用范圍內射頻卡片數越多，UID 位數越多，傳送時間越長，總的防碰撞執行時間肯定也就越長。

　　3. 改進的二進制算法

　　針對采用傳統二進制搜索算法時終端射頻卡片數越多，UID 位數越長，傳送時間越長的缺點，目前提出了很多改良防碰撞算法，如：ALOHA 算法[6]， EPC 動態二進制算法[7]，跳躍式二進制算法[8]等，歸納一下基本采用兩種方法改良算法的性能，一是減少傳輸數據的字節數，二是減少查詢次數，本算法，試圖將此兩種方法應用到同一種防碰撞算法中。

　　3.1 改進的二進制算法的基本原理

　　本算法首先是標簽閱讀器發出請求指令，等待閱讀器接收范圍內所有標簽第一位回應，標簽回應完畢，程序檢查是否碰撞，如果沒有碰撞則轉到讀取各標簽下一位，如果有碰撞則記錄碰撞位，并優先選取各標簽同樣位上數據是0 的標簽，選取完畢后，再將所選標簽繼續讀取判斷，直到所讀取標簽只有一個的時候，不論后面還有多少位，都不再讀取，選定，并將標簽代碼完整讀取并識別，然后屏蔽；之后返回離選取該標簽最近的碰撞位，改變原來選取的0 值，現改為讀取這一位上標簽值為1 的標簽繼續進行選取判斷，直到解決所有碰撞位并讀取完閱讀器閱讀范圍內所有標簽為止，程序結束。

　　3.2 改進的二進制算法實例解析

　　以上是我的改進的二進制算法的基本原理介紹，為了解釋的更加清楚，我通過五個標簽的實例作進一步解析如表1：

　　3.3 改進的二進制算法性能分析

　　本算法首先閱讀器每次只接收 lbit 的數據，因此可以避開閱讀器必須能夠確定碰撞的準確的bit 位置這一困難，或者說可以避開閱讀器必須對所有標簽準確地同步這一困難，因而編碼方式更加自由，實現起來更加容易。另外，在標簽的序列號較短的情況下，用此種方法的算法在時間復雜度方面也優于二進制搜索算法。

　　3.4 仿真

　　下面使用 Matlab 仿真來對上述算法作進一步說明：其中n 為標簽位數，m 為查詢次數，m 和n 均取正整數(下同)。仿真結果如圖1 所示：

圖1 兩種算法查詢次數比較

　　圖 1 中，紅色曲線表示傳統算法，藍色曲線表示改進算法。從圖1 中可以明顯看出，在同等條件下，本文改進算法標簽的查詢次數相對于傳統二進制算法查詢次數，其在標簽數量大、標簽ID 相似度高、碰撞位多的情況下，查詢次數增加速度明顯減慢。

　　4 結束語

　　在 RFID 系統的應用中，有效地解決標簽的碰撞問題和如何提高標簽的識別速率對整個RFID 系統的應用是至關重要的。尤其是在物流領域、倉庫管理中，標簽數量多、標簽ID相似度高的場合中。本文提出了一種改進的RFID 防碰撞算法，與其他常用的防碰撞算法相比，如目前應用比較廣泛的傳統二進制算法，在有大量的標簽存在、標簽ID 度相似極高的環境中，顯示出了明顯的優勢。

　　本文作者創新點:本文主要通過閱讀古今中外的有關基于射頻識別技術的防碰撞算法，結合自己的實踐探索，從理論上分析了防碰撞的根本原理，針對傳統防碰撞算法中存在的終端射頻卡數量越多，UID(Ubiquitous Identifications，身份識別標簽)位數越多，傳送時間越長的缺點，提出了從低層二進制入手，運用計算機中查找二查樹原理和路徑最優化原理，對標簽的選擇實行最優化最快速的讀取算法，本文最后對改進算法和傳統算法進行仿真，從仿真結果可以看到改進算法明顯優于傳統算法，這個改進可以有效解決防碰撞問題。

    參考文獻
    [1] FinkenzellerK 著，陳大譯，射頻識別技術.清華大學出版社，2000
    [2] 游戰清.無線射頻識別技術(RFID)理論與應用[M].北京:電子工業出版社, 2004
    [3] 張暉，王東輝．PLC 技術應用200 例．微計算機信息，2007，4-2：253-254。
    [4] 陳博．一種類二進制搜索的RFID 系統反碰撞算法及其實現.電子器件，2006 年3 月，29 卷第一期
    [5] Draft protocol specification for a 900 MHz Class 0 Radio Frequency IdentificationTag[Z],Auto-ID Certer,2003.
    [6]吳春華、陳軍，動態ALoHA 法在解決RFID 反碰撞問題中的應用【J].電子器件，2003 年第2 期:173 一176.

1