【正文】 quest 命令做出響應。 3 改進型二進制樹防碰撞算法 3． 1 涉及二進制樹算法的國際標準 3． 1． 1 IS0 15693 ISO l5693【 23】，短距離智能卡 (Vicinity coupling smart cards)標準，讀取距離可高達一分米，使用的頻率為 l3． 56MHz，它設計簡單，生產成本比IS014443 低，大都用來做出入控制、出勤考核等，現在很多企業(yè)使用的門禁卡大都使用這一類的標準。 100％幅值調制 10％的幅值調制 數據編碼 數據編碼采用脈沖位置調制。 ISO／ IECl4443 標準開始于 1995 年， 單個系統(tǒng)于 1999年進入市場，而其完成在 2021 年以后，迄今為止， ISO／ IECl4443 標準中的非接觸式智能卡的類型可以分為 TypeA 和 TypeB。 TypeA 技術設計簡單扼要，應用項目的開發(fā)周期可以很短，同時又能起到足夠的保密作用，可以適用于非常多的應用場 合。 TypeD 由 Cub。 TypeC 由日本索尼公司研制。 下面簡要介紹一下 ISO／ IECl 4443標準中各個不同類型的非接觸式智能卡。 數率：有高和低兩種數率。 工作頻率：工作頻率為 13． 56MKz 士 7KHz 26 調制 ：用 2種幅值調制方式，即 l0％和 l00％調制方式。 25 2． 5． 3 性能評價 與基本二進制樹比較可知，退避式算法每次傳送的數據信息量與基本算法是一樣的，區(qū)別在于，退避式算法的傳送次數，也即是所遍歷的節(jié)點數目比之基本算法大大減少，假設讀寫器工作范圍內有 n個應答器，則所需節(jié)點數目為而，則可用式子 2． 19來表示： 數學歸納法證明如下： 當讀寫器工作范圍內只有一個應答器時，顯然有： 假設 n個應答器時，有： 則當系統(tǒng)中有 n+1 個應答器時，由于新增加的這個應答器與原來 n個應答 器的序列號均不相同，為了將其與某個匹配度最高的應答器區(qū)分開來，需要在原 來二進制樹中增加一個節(jié)點，由于節(jié)點之間僅存在父子關系，且僅通過兩條邊相 連，所以有： 得證。 (2)讀 寫器發(fā)送 Request(1l110101)命令，所有應答器響應，將自身序列號與該 SN(111l0l01)比較，其中 T1(10100101)， T3(110l0101)的序列號小于該值，則 Tl， T3 返回自身序列號給讀寫器，在讀寫器接收端發(fā)生碰撞，讀 RFID 二進制樹防碰掩算法的研究與實現寫器檢測到返回數據為 1XXX0101，讀寫器做如下處理：將碰撞起始位 D5位置 0，低于該位者不變，高于該位者置 1，得到 11l 00101，作為下一次 Request 命令攜帶的參數值，即 Request(1l100101)。此時將最大序列號中對應碰撞起始位置 為 O。事實上，退避式算法的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法之所以稱為二進制樹，是因為每次碰撞后，均以碰撞起始位為界，將應答器分為兩個部分，形象的看，如同一棵樹在進行從根部到主干到樹枝的一個不斷的分叉過程，所以，分叉也即是 分組的理念是二進制樹算法的本質所在，根據這一點，算法每次分叉到達末端之后，不再返回根部重新開 始分叉，而是返回上一次分叉的節(jié)點即可重新開始新的樹干，該節(jié)點也即是上一次發(fā)生碰撞的節(jié)點。 定義兩個具有普遍意義的命令來描述 算法： (1)請求命令 Request(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若小于或者等于，則該應答器回送其 SN 給讀寫器。 (5)啟動新一輪循環(huán)，重復上述步驟，總計 12步后，依次識別出 T1， T3， T2，T4，參數變化過程見圖 2． 6中標示，具體內容不再詳述。 (5) 重復上述過程，即可按序列號從小到大依次識別出各個應答器． 2． 4． 2 實例演示 動態(tài)二進制樹算法的實例演示如圖 2． 6 所示 ，基本設置同基本二進制樹算法： 圖 2． 6動態(tài)二進制樹算法實例 (1)啟動第一輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，所有應答器響應該命令，按照約定，命令參數為全 1時，所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數據為 1XXXXl01，其中 X 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，得到 0101，則下一次 Request命令攜帶的參數值，即 Request(0101)。 (2) 由于應答器序列號的唯一性，當 應答器數目不小于兩個時，必然發(fā)生碰 21 撞。 動態(tài) 二進制樹算法的流程如 圖 2． 5所示： 20 圖 2． 5動態(tài)二進制樹算法流程 事實上，動態(tài)二進制樹對基本二進制樹的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法的核心部分即新命令參數的生成，是根據是否發(fā)生碰撞，以及碰撞位來決定的，特別是新 Request 命令參數的生成是由碰撞的起始位來確定的，而碰撞的起始位的得到只需要應答器序列號中包括碰撞起始位在內的部分位即可，把這些位稱為序列號的有效位，同樣，新 Request 命令參數也為包括碰撞起始位 (設為 0)在內的部分位，綜合如下：若選擇高位加碰撞起始位(設為 0)，則算法為應答器序列號 對應位小于這些位的數值者，返回剩余低位，若選擇碰撞起始位 (設為 0)加低位，則算法為應答器序列號對應位等于這些位的數值者，返回剩余高位，從而讀寫器的新 Request 命令參數與應答器返回的序列號有效部分組合起來，可以得到一個完整的應答器序列號。 2． 4 動態(tài)二進制樹防碰撞算法 2． 4． 1 算法思路 定義兩個具有普遍意義的命令來描述算法： (1)請求命令 Request( )，該命令攜帶一個參數 SN，長度為，應答器接收到該命令，將自身的 SN中的前 1～ x位與接收到的比較，若兩者相等，則該 答器返回其 SN 的剩余位給讀寫器。所以，要改善二進制樹算法的性能，就必須從這兩點著手，現有的二進制樹搜索算法有很多種，它們都是在基本二進制樹搜索算法的基礎上加以改進得來的，根據 前 述分析，主要的改進思路有兩個 ： (1)減少每次通信過程中的數據傳輸位數。 通信時間 t定義為數據交換的時間，也即是命令執(zhí)行的時間。循環(huán)次數 定義為在整個防碰撞循環(huán)過程中的循 18 環(huán) 輪次，也即是二進制樹的遍歷次數。 (10)讀寫器發(fā)送 Sleep(10101101)命令，所有應答器響應，將自身序列號與該 SN(10101101)比較，其中 T2(10101101)的序列號等于該值，則 T2執(zhí)行該命令，進入休眠狀態(tài)，即除非重新上電，否則不再響應 Request 命令。 (6)讀寫器發(fā)送 Request(11110101)命令，．除 Tl外所有應答器響應該命令，將自身序列號與該 SN(11l10101)比較，其中 T3(1l010l01)的序列號小于該值，則 T3 返回自身序列號給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數據為 110l0101，讀寫器做如下處理：將該數值作為下一次 Sleep 命令攜帶的參數值，即 Sleep(11010101)。 (2)讀寫器發(fā)送 Request(11110101)命令，所有應答器響應該命令，將 自身序列號與該 SN(11110l01)比較，其中 T1(10l00101)， T3(1l010101)的序列號小于該值，則 Tl， T3 返回自身序列號給讀寫器，在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數據為 1XXX0l01，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，高于該位者置 l，得到 11l00l01，作為下一次 Request 命令攜帶的參數值，即 Request(11100101)。 注：第五步時，從步驟 1開始重復，也就是說，讀寫器識別完一個應答器后，將重新發(fā)送原始的最大序列號。 (3) 讀寫器將處理后的序列號發(fā)送給應答器，應答器序列號與該值比較，小于或等于該值者，將自 身序列號返回給讀寫器。注： Request(SN)初始值設為 Request(11111111)。需要說明的是，這只是一個大略的分類法，主要目的在于說明二進制樹分類的基本原則。 2． 2． 3 算法分類 在基本的二進制樹搜索算法的基礎上，有多種形式的二進制樹搜索算法，它 14 們之間主要的區(qū)別在于命令的數據形式，主要有兩點。 馬爾可夫鏈遍歷性分布要滿足下列兩個條件 【 18】 ： 這里有： 也就是 n個信息包從發(fā)生碰撞開始傳輸的 CRI區(qū)間長度的數學期望， 是 在一個時隙內到達這個系統(tǒng)信息包的期望值，該過程屬于泊松過程【 l9】 。 分析如下： n=l，顯而易見，在第一個時隙內不發(fā)生碰撞，可以成功識別該應答器， =1。如圖 2． 1所示。從應用的角度來說，正確有效的識別是實際所需要的，因此下文將著重于二進制樹防碰撞算法的研究。 11 2 現有 RFID 二進制樹防碰撞算法 2． 1 RFID 防碰撞算法概述 RFID 系統(tǒng)的數據通信雙方是讀寫器和應答器，在實際的 RFID 系統(tǒng)工作時，可能會出現同時多個讀寫器和多個應答器共存的情況，毫無疑問，此時系統(tǒng)的數據交換就會出現信道與時序上的重疊，也就是發(fā)生了碰撞，在多個讀寫器與多個應答器的射頻識別系統(tǒng)中，存在著兩種形式的沖突方式，一種是同一應答器同時收到不同讀寫器發(fā)出的命令，另一種是同一個讀寫器同時收到多個不同應答器返回的數據，前者我們稱為讀寫器碰撞，后者稱為應答器碰撞【 9】，在實際應用當中，一般是讀寫器做為主設備，來識別多個應答器，所以發(fā)生讀寫器碰撞的應用場合是不多的，因此下文將 著重研究應答器碰撞。 第 3 章：改進型二進制樹防碰撞算法?；谏鲜隹紤]，論文將分四章來予以講述，文章結構與內容安排如下： 第 1 章：緒論。在實際的應用當中，應答器由于其低成本的優(yōu)越 ,從而得到大量的生產，而讀寫器往往是固定在系統(tǒng)的某處，來識別多個應答器，所以碰撞的主要情況是應答器碰撞，即一個讀寫器的工作范圍內同時出現了 多個應答器，并且對該讀寫器發(fā)出的命令同時予以響應，從而導致讀寫器無法正確的識別出一個應答器，稱該現象為發(fā)生了應答器碰撞。目前關于防碰撞算法的研究還在進行當中，理論成果已經得出了很多，許多國際標準也對一些成熟的算法進行了規(guī)定，但是無論在理論效率還是實際應用上，都還存在很大的改進空間。 1． 3． 3 RFID 防碰撞算法 隨著 RFID 技術的發(fā)展，多目標識別成為了一個很重要 的應用方向，特別在目標跟蹤，物品識別，訪問控制等操作中，利用 RFID 技術，對附著在不同目標上的應答器快速可靠的進行識別，從而大大提高了定位的精確度，管理的自動化促進了整個產業(yè)鏈的發(fā)展。 1． 3． 2 RFID 標準統(tǒng)一化 RFID 最初是各個廠家在各自的獨立標準下開發(fā)出來的，缺乏統(tǒng)一的規(guī)范，因此制約了該項技術在大規(guī)模系統(tǒng)中的應用，隨著 RFID 技術的發(fā)展，參與到其中的國家，組織，企業(yè)也越來越多，目前形成了國際標準化組織 ISO，泛在 ID中心 UID，全球電子產品代碼管理中心 EPC 三大標準體系，這些標準涉及到 RFID系統(tǒng)的物理結構，通信協(xié)議，防碰撞算法，應用系統(tǒng)接口協(xié)議等等多個方面的內容，它們針對不同的頻率，基于不同的工作原理，甚至在同樣的應用背景下也有著巨大的協(xié)議上的區(qū)別。 (3)防偽應用 應答器在防偽應用中有識別快速，偽造難，成本低等優(yōu)點，再加上安全認證和加密功能，就可以大大提高偽造的難度和成本，同時，在識別的時刻，可以通過讀寫器的快速閱讀功能，在瞬間得出所有物品的信息，并加以記錄 和處理。 (1)物流管理 ． 物流管理是 RFID 技術最具應用前景的領域，近年來提出了一個物聯(lián)網的概念，意在將全球所有的物品信息都用唯一的電子代碼來表示，從而將這些物品都聯(lián)系在一起，可以隨時隨地的識別，追蹤，管理這些物品，最終在產品，用戶，企業(yè)和政府之間建立但是該應用涉及到的方面太廣，技術難度很大，目前還在研究當中。 8 1． 2． 3 RFID 系統(tǒng)工作原理 RFID 是一門多學科綜合技術，涉及到電磁場理論，數字電路，模擬電路，無線電廣播，通信原理等多方面知識 RFlD 系統(tǒng)中，讀寫器將要發(fā)送的信號調制到載波上，經由射頻通道，通過天線發(fā) 送出去，應答器上的電壓根據載波的變化而變化，將該電壓信號進行整流和濾波后，得到解調后的數據，這是下行鏈路的過程，應答器傳輸的數據的變化控制應答器天線上負載電阻的通斷，從而促使讀寫器天線上電壓的變化，從而實現了數據的上行鏈路傳輸。 (4)混頻：多個頻率的混合使用，典型應用為 134KHz+430MHz。 (2)遙耦合：典型的作用范圍為 lcm～ 1m。后端應用環(huán)境主要完成數據信息的存儲及處理， 7 它實質上就是一個數據管理系統(tǒng)，也是一個全局控制系統(tǒng)，一般由 PC 機或者工作站組成，同時也包括了應用軟件在內，整個后端應用 環(huán)境負責接收來自讀寫器的數據，并進行存儲以及相應的處理，協(xié)同調節(jié)多個讀寫器的工作，該部分在應用中常稱為中間件 (Savant)，它擴展了 RFID 系統(tǒng)的應用范圍和應用能力，是未來 RFID 系統(tǒng)智能化，大型化發(fā)展的有力技術支撐，是 RFID 技術發(fā)展的重要方式。 應答器的典型產品有 TI公司的 6000 系列， Phil