射頻識別技術（RFID" title="RFID" target="_blank">RFID）是一種非接觸、低功耗、無線通信技術，可通過無線電信號識別特定目標并讀寫相關數據。典型的RFID系統由電子標簽(Tags)和讀寫器(Reader)組成，電子標簽與讀寫器之間是通過耦合(天線)實現射頻信號的空間(無接觸）耦合。在耦合通道內，根據時序關系，實現能量的傳遞、數據的交換。其工作原理如圖1所示。

    隨著RFID技術的廣泛應用，存在的問題也越來越凸顯出來。目前RFID技術存在的主要問題有：安全問題、傳輸距離問題、碰撞問題等,其中碰撞問題嚴重制約著RFID的發展。目前,雖然已經有很多種防碰撞的算法，但是在算法執行效率和精確度方面各有缺陷。本文在研究大量防碰撞算法的基礎上,經過比較分析提出了一種新的基于樹搜索的防碰撞算法，該算法根據碰撞位的情況動態地選擇合適的搜索樹算法,大幅度提高了RFID的性能。
1 防碰撞算法簡介
    如果在RFID讀寫器可讀取范圍內有多個標簽,或是一個標簽同時接收到幾個讀寫器發出的信號就會發生沖突，即所謂的碰撞。一旦發生碰撞就會導致讀寫器不能讀取電子標簽信息或是無法讀到正確的標簽信息，所以防碰撞算法就顯得尤為重要。根據碰撞的產生原理可以將RFID的碰撞分為[1]：標簽碰撞、頻率干擾、標簽干擾。其中頻率干擾和標簽干擾統稱為讀寫器碰撞。
    由于讀寫器碰撞的發生概率較小且容易避免，所以本文主要研究對象是標簽碰撞。解決碰撞的算法就稱為防碰撞算法。防碰撞算法最常使用的方法[2]有空分多址(SDMA)、頻分多址(FDMA)、碼分多址(CDMA)和時分多址(TDMA)。目前較為流行的RFID的兩種防碰撞算法，基于ALOHA和基于樹的算法都是基于時分多址的。
2 基于多叉樹的RFID防碰撞算法
    二進制樹算法(BS)[3]的基本思想是將處于碰撞狀態的標簽分為0和1兩個子集,先查詢子集0,若沒有沖突，則正確識別；若仍有沖突,則再分裂，把子集0分為00和01兩個子集，依次類推，直到子集0中的所有標簽全部識別，再按照此步驟查詢子集1。使用BS算法的標簽要經過多次比較,并通過循環操作以達到識別所有標簽,搜索過程中會出現路徑的重復,搜索效率比較低[4]。為滿足RFID系統能耗低、速度快等要求，其防碰撞算法有如下特點[5]：(1)識別過程中查詢時間要短，查詢次數也要盡量少。(2)對于無源標簽來說必須是低能耗，要達到低能耗就要求算法中標簽與讀寫器之間傳輸的比特數要少。(3)標簽能夠被完全、正確地識別，要求讀寫器對其可讀取范圍內的所有標簽都要正確、完整地識別，不能出現錯誤識別和遺漏識別。本文提出的基于多叉樹搜索的防碰撞算法在滿足RFID防碰撞算法的基礎上,盡量解決上述防碰撞算法中的問題。
2.1 算法的基本思想
    讀寫器在發出Request命令后，讀寫器可讀取范圍內的所有標簽都要做出應答，如果讀寫器譯碼后得到n個位發生碰撞，即只有標簽這n個比特是讀寫器無法識別的。讀寫器根據這n個碰撞位所在的位置,分成三種情況進行處理：(1)若碰撞位連續兩位,則采用動態四叉樹分裂查詢； (2)若碰撞位非連續,則采用動態二叉樹分裂查詢；(3)若碰撞位只有一位,則采用二叉樹查詢。
    在發送查詢指令時，不需發送碰撞標簽完整的ID號，只要用二進制代碼表示碰撞位即可，這樣可以在很大程度上減少發送的數據量，繼而降低功耗、提高識別效率。
2.2 算法的工作流程
    算法的步驟如下：
　 (1) 算法先發送一個Request(11111111)命令，所有電子標簽對此做出應答，然后將自己的ID碼發送出去。
　 (2) 讀寫器檢測接收到的信號，若未能檢測到信號，則說明在讀寫器可讀取的范圍內沒有電子標簽，返回步驟(1)；若檢測到信號，則轉到步驟(3)。
　 (3) 判斷是否有碰撞發生，若無則對標簽進行讀寫操作；若有,則轉到步驟(4)。
　 (4) 將查詢碼壓入堆棧,并發送棧頂的查詢碼,滿足該查詢碼的標簽應答。判斷碰撞情況：若沒有標簽應答,則讀寫器本次識別過程結束，并檢堆棧是否為空；若只有一個標簽應答，讀寫器發出RW-DATA指令,對該標簽進行讀寫操作之后，讀寫器發出Sleep指令,標簽進入休眠狀態，不參與后續的識別過程;若有多個標簽做出應答，即發生碰撞，則轉到步驟(5)。
　 (5) 根據碰撞位的不同情況,選擇不同的搜索方法，重復步驟(4),直到堆棧為空。
　 (6) 堆棧為空說明所有標簽都被成功識別，整個標簽識別過程結束。
2.3 算法舉例
    假如電子標簽的ID碼均是8位,在讀寫器可讀取范圍內有4個處于準備狀態的電子標簽A、B、C、D,它們的ID號為：TagA：10000110、TagB：11010010、TagC:01000010、TagD:01001010。本例的搜索過程中堆棧變化情況如圖2所示，算法實現步驟如下：

    (1) 當讀寫器發出Request(11111111)指令后，得到譯碼后的碰撞位為：XX0XXX10。
    (2) 讀寫器將連續碰撞位XX用四叉樹進行查詢,發生碰撞的最高位為第7位，用二進制表示為111。將Request(00,111)、Request(01,111)、 Request(10,111)、Request(11,111)依次入棧，然后發送棧頂指令Request(00，111)，沒有符合查詢碼的標簽響應,該分支的識別過程結束；發送指令Request(01,111)，有標簽C、D響應，即發生了碰撞，將C、D重新譯碼后得到新的譯碼數據為0100X010，此時讀寫器檢測到只有一個碰撞位。參考文獻[6]中設定只有一個碰撞位時,讀寫器能直接識別出兩個標簽，但是由于標簽本身無法識別，所以只有一個碰撞位時，讀寫器也還是要經過一次比較，才能識別出兩個標簽最高碰撞位為第3位,將Request(0,11)、Request(1,11)壓入堆棧。
    (3) 讀寫器發送Request(0，11)命令，只有標簽D應答，經讀寫器讀寫操作后進入休眠態。
　 (4) 讀寫器發送Request(1,11)命令，只有標簽C應答，執行讀寫操作后轉入休眠態。
　 (5) 讀寫器發送Request(10,111)命令，只有標簽A應答，執行讀寫操作后轉入休眠態。
　 (6) 讀寫器發送Request(11,111)命令，只有標簽B應答，執行讀寫操作后轉入休眠態。
　 (7) 堆棧內的命令全部讀取并發送，堆棧為空，說明待識別的標簽全部識別完，標簽識別過程結束。
3 新算法的性能分析
3.1發送數據量分析
　當標簽的ID較長時,讀寫器每次發送的查詢指令的位數就會很多，這樣會嚴重影響傳輸速率和系統識別效率[6]。如果直接用二進制表示碰撞位的信息，則可以大大減少發送的數據量。假設標簽的ID號有N位，則只要n位序列就能表示出所有的碰撞位，其中：

    假設在整個識別過程中查詢M次只有1個碰撞位，則整個識別過程中有M個葉子節點，那么動態二叉樹查詢次數為：
　    

4 實驗仿真與分析
    利用軟件Matlab對上述算法的傳輸數據量、查詢次數和吞吐率進行試驗仿真，結果如圖3所示。

    由圖3(a)可以看出,隨著標簽ID的增長，新算法的傳輸數據量增加很少，與未經過改進的算法的指令長度相比，新算法能很大程度地減少傳輸指令長度，從而能減少系統的能耗，增加系統的識別效率。
    由圖3(b)可以看出，在同樣數目的待識別標簽的情況下，動態二叉樹和動態四叉樹所需的查詢總數，與本文的算法所需查詢總數的比較中，本文新算法所需的總查詢數較少，即識別時間較短。
    由圖3(c)可得新算法的吞吐率高于動態二叉樹和動態四叉樹搜索算法的吞吐率，即新算法的識別率更高。
    本文在研究大量防碰撞算法的基礎上經過比較分析，提出了一種新的基于樹搜索的防碰撞算法，該算法根據碰撞位的情況，動態地選擇合適的搜索樹算法，而且本文還引用了堆棧來存儲查詢命令，這樣可以避免重復、多余的搜索，減少了搜索樹的分支數。由數學分析和算法的仿真結果可得，該算法查詢時間短、系統效率高、性能優良，特別是在待識別標簽數量龐大時，該算法表現出更加明顯的優勢。
參考文獻
[1] Jia Xiaolin,Feng Quanyuan,Fan Taihua, et al. Analysis of  anti-collision protocols for RFID tag identification[C].IEEE  2012 2nd International Conference on Digital Object Identifier, 2012.
[2] 胡兆吉.基于嵌入式的射頻識別系統[D].西安：西安電子科技大學，2011.
[3] 丁治國.RFID關鍵技術研究與實現[D].合肥：中國科學技術大學,2009.
[4] 李興鶴，胡詠梅，王華蓮，等.基于動態二進制的二叉樹搜索結構RFID反碰撞算法[J].山東科學，2006,19(2)：51-55.
[5] 江岸，伍繼雄，黃生葉，等.改進的RFID二進制搜索防碰撞算法[J].計算機工程與應用，2009,45(5)：229-235.
[6] 江城，黃立波.基于二進制搜索的RFID標簽防碰撞算法研究[J].計算機與數字工程，2011(4):29-33.
[7] 孫文勝，胡玲敏.基于后退式搜索的自適應多叉樹防碰撞算法[J].計算機應用, 2011,31(08)：2052-2055.
[8] 丁俊.射頻識別RFID標簽防碰撞算法[D].合肥：中國科技大學2010.