【正文】 即除非重新上電，否則不再響應(yīng) Request 命令。 (3)讀寫(xiě)器發(fā)送 Request(00l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該SN(00101)比較，其中 Tl(10100101)的序列號(hào)對(duì)應(yīng)位等于該值，則 Tl 返回剩余序列號(hào)給讀寫(xiě)器，在讀寫(xiě)器接收端不發(fā)生碰撞，讀寫(xiě)器檢測(cè)到返回?cái)?shù)據(jù)為 l0l，讀寫(xiě)器做如下處理：將上一次 Request(00l01)命令參數(shù) 00101 與返回?cái)?shù)據(jù) 101組合起來(lái)，作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(10100101)。 注：如果上一次發(fā)出的 Request 為全 l，則表明讀寫(xiě)器工作范圍內(nèi)只有一個(gè)應(yīng)答器，此時(shí)應(yīng)答器返回?cái)?shù)據(jù)為完整序列號(hào)，以該序列號(hào)作為 Sleep 命令參數(shù)。 本文中，定義根據(jù)第一個(gè)思路得來(lái)的算法為動(dòng)態(tài)二進(jìn)制樹(shù)，它的一個(gè)典型應(yīng)用為 ISOl4443 TYPEA 二進(jìn)制樹(shù)搜索算法。也即是二進(jìn)制樹(shù)的節(jié)點(diǎn)數(shù)目。 (8)啟動(dòng)第三輪循環(huán)，讀寫(xiě)器發(fā)送 Request(11111111)命令，除 T1， T3 外所有應(yīng)答器響應(yīng)該命令，將自身序列號(hào)與該 SN(1111ll11)比較，均小于該值，于是所有應(yīng)答器均返回自身序列號(hào)給讀寫(xiě)器，因?yàn)樾蛄刑?hào)的唯一性，應(yīng)答器返回的序列號(hào)在讀寫(xiě)器接收端發(fā)生碰撞，讀寫(xiě)器檢測(cè)到返回?cái)?shù)據(jù)為 1X101101，其中 x表示該位發(fā)生了碰撞，讀寫(xiě)器做如下處理：將碰撞起始位 D7 位置 0，低于該位者不變，高于該位者置 1，得到 10101101，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(10101101)。 假設(shè) RFID系統(tǒng)中有一個(gè)讀寫(xiě)器 R，四個(gè)應(yīng)答器 Tl(10100101)， T2 16 (10l01101)， T3(11010101)， T4(11101101)，在某一時(shí)刻，四個(gè)應(yīng)答器 同時(shí)進(jìn)入讀寫(xiě)器的工作范圍之內(nèi)，讀寫(xiě)器發(fā)出命令，四個(gè)應(yīng)答器同時(shí)響應(yīng)，由于 其序列號(hào) SN的唯一性，將發(fā)生應(yīng)答器碰撞，從而啟動(dòng)防碰撞循環(huán)，分析如下： 圖 基本二進(jìn)制樹(shù)算法實(shí)例 注：圖中共有四輪循環(huán)，依次識(shí)別出四個(gè)應(yīng)答器，分別以不同格式的線條表 示，并加有循環(huán)輪次的數(shù)字標(biāo)識(shí)。 基本二進(jìn)制樹(shù)算法的流程圖如圖 2． 3所示： 15 圖 2． 3基本二進(jìn)制樹(shù)算法流程 基本二進(jìn)制樹(shù)算法的步驟如下： (1) 應(yīng)答器進(jìn)入讀寫(xiě)器工作范圍，讀寫(xiě)器發(fā)出一個(gè)最大序列號(hào)，所有應(yīng)答器的序列號(hào)均小于該最大序列號(hào)，所以在同一時(shí)刻將自身序列號(hào)返回給讀寫(xiě)器。 (2)命令參數(shù)長(zhǎng)度是固定的，還是變化的。 由上式可知， 是逐漸遞歸的，通過(guò)遞歸可得： 根據(jù)式 ()，上式可化為： 由此可見(jiàn)， 是關(guān)于 p 的函數(shù)，則 =n/ 也是關(guān)于 p的函數(shù)，一般情況下，可以參考二項(xiàng)分布，將 p取為 1／ 2。 12 為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統(tǒng)當(dāng)中，每個(gè)應(yīng)答器都是獨(dú)一無(wú)二的，它們的獨(dú)立性通過(guò)唯一的自身序列號(hào)來(lái)體現(xiàn)，該序列號(hào)在不同的標(biāo)準(zhǔn)中有不同的名稱，如 EPC 標(biāo)準(zhǔn)中稱其為電子產(chǎn)品代碼 EPC，即英文ElectronicProduct Code 的縮寫(xiě)， IS014443 標(biāo)準(zhǔn)中稱其為唯一標(biāo)識(shí)碼 UID，即英文 Unique Identmer 的縮寫(xiě)【 15】 。 第 4 章： FPGA 實(shí)現(xiàn)改進(jìn)型二進(jìn)制樹(shù)防碰撞算法。 在上述前提下，基于應(yīng)答器的確定型二進(jìn)制樹(shù)防碰撞算法是目前最好的一種選擇，對(duì)其進(jìn)行研究，是最有實(shí)際應(yīng)用價(jià)值的，所以，本文將對(duì)其進(jìn)行理論分析與具體實(shí)現(xiàn)，在研究過(guò)程中，注重與新一代智能 RFID 系統(tǒng)的結(jié)合，應(yīng)用擁有強(qiáng)大功能的 FPGA(FieldProgrammable GateArray)做 為算法運(yùn)行的微處理器，這種思路將是未來(lái) RFID 技術(shù)發(fā)展的重要方向， RFID 技術(shù)中的關(guān)鍵算法與先進(jìn)的電子技術(shù) FPGA 的結(jié)合，將為 RFID 技術(shù)的應(yīng)用拓開(kāi)廣闊的前景。在 RFID 系統(tǒng)中，當(dāng)工作范圍內(nèi)同時(shí)出現(xiàn)了多個(gè)讀寫(xiě)器和多個(gè)應(yīng)答器時(shí)，讀寫(xiě)器與讀寫(xiě)器之間，應(yīng)答器與應(yīng)答器之間的相互干擾，稱 RFID 系統(tǒng)發(fā)生了碰撞【 7】 ，從而導(dǎo)致數(shù)據(jù)不能正確的傳輸，信息無(wú)法得到正確的讀取，一方面影響了產(chǎn)品的識(shí)別，另一方面還可 能導(dǎo)致信息的泄露。 (4)交通管理 交通管理是 RFID 最先應(yīng)用的領(lǐng)域，目前已經(jīng)擁有了成熟的技術(shù)，它利用了應(yīng)答器便捷快速識(shí)別，可靠性高，安全性強(qiáng)的特點(diǎn)，目前主要應(yīng)用范圍是電子車票，高速公路收費(fèi)等方面，在我國(guó)深圳，基于 RFID 技術(shù)的高速公路收費(fèi)系統(tǒng)已經(jīng)得到了成功的應(yīng)用。同時(shí)，根據(jù) RFID 系統(tǒng)的不同，在供電方式上有無(wú)源或者有源，調(diào)制方式上有幅度調(diào)制或者相位調(diào)制，數(shù)據(jù)讀取上有電感耦合或者反向散射等區(qū)別【 5】 。 根據(jù)工作頻率的大小， RFID 系統(tǒng)可以分為如下四個(gè)方面： (1)低頻： 30～ 300KHz，典型應(yīng)用為 134KHz。數(shù)據(jù)交換環(huán)節(jié)即 RFID 系統(tǒng)中的讀出寫(xiě)入設(shè)備，它是系統(tǒng)的核心部件，是后端應(yīng)用環(huán)境和前端信息載體的數(shù)據(jù)通道，在實(shí)際應(yīng)用中，往往被稱為查 詢器，掃描器，閱讀器，編程器等，本文建議采用讀寫(xiě)器 (Read／ Write Device)這種更具普遍意義的說(shuō)法，這樣既包括了從應(yīng)答器中讀出信息，同時(shí)也包括了向應(yīng)答器中寫(xiě)入信息。 1． 2 RFID 系統(tǒng) 1． 2． 1 RFID 系統(tǒng)組成 根據(jù)實(shí)際應(yīng)用環(huán)境， RFID 系統(tǒng)結(jié)構(gòu)有多種不同分法，一般來(lái)說(shuō)，一個(gè)典型RFID 系統(tǒng)包括三個(gè)部分：前端信息載體，數(shù)據(jù)交換環(huán)節(jié)，后端應(yīng)用環(huán)境【 3】。 1 南 陽(yáng) 理 工 學(xué) 院 本科生 畢業(yè)設(shè)計(jì) （ 論文 ） 學(xué)院（系）： 計(jì)算機(jī)與信息工程學(xué)院 專 業(yè)： 通信工程 學(xué) 生： 指導(dǎo)教師： 完成日期 2021 年 4 月 2 南 陽(yáng) 理 工 學(xué) 院 本 科 畢 業(yè) 設(shè) 計(jì)（論文） RFID 二進(jìn)制樹(shù)防碰撞算法設(shè)計(jì) 學(xué) 院（系）： 計(jì)算機(jī)與信息工程學(xué)院 專 業(yè)： 通信工程 學(xué) 生 姓 名： 學(xué) 號(hào)： 指 導(dǎo) 教 師（職稱）： 評(píng) 閱 教 師： 完 成 日 期： 2021 年 4 月 南陽(yáng)理工學(xué)院 Nanyang Institute of Technology 3 RFID 二進(jìn)制樹(shù)防碰撞算法設(shè)計(jì) 【 摘要 】 射頻識(shí)別技術(shù) RFID 是目前正快速發(fā)展的一項(xiàng)新技術(shù)，它通過(guò)射頻信號(hào)進(jìn)行非接觸式的雙向數(shù)據(jù)通信，從而達(dá)到自動(dòng)識(shí)別的目的。 RFID 被譽(yù)為二十一世紀(jì)的十大戰(zhàn)略性產(chǎn)業(yè)之一，可以預(yù)想，未來(lái) RFID 技術(shù)的發(fā)展空間是無(wú)限廣闊的。 CODE 等。 (3)遠(yuǎn)距離系統(tǒng)：典型的作用范圍為 l～ 10m。在數(shù)據(jù)的雙向傳輸過(guò)程中，是通過(guò)電磁場(chǎng)的相互感應(yīng)來(lái)實(shí)現(xiàn)的，該過(guò)程也可以用變壓器的模型來(lái)予以參考。目前在日本和歐洲已經(jīng)有了類似的應(yīng)用。因此，如何保證迅速快捷，又安全可靠的同時(shí)識(shí)別多個(gè)目標(biāo)，就成為了 RFID 技術(shù)發(fā)展的關(guān)鍵性技術(shù)。解決碰撞的過(guò)程相應(yīng)的被稱為防碰撞，如前所述，該防碰撞過(guò)程主要從軟件的角度來(lái)予以解決，稱為防碰撞算法 【 8】 。二進(jìn)制樹(shù)防碰撞算法在多個(gè)國(guó)際標(biāo)準(zhǔn)中均有規(guī)定，基于 IS014443 標(biāo) 準(zhǔn)的 TYPEA 是其中的一個(gè)典型例子，本章首先介紹了涉及到二進(jìn)制樹(shù)防碰撞算法的幾個(gè)標(biāo)準(zhǔn)，其次詳細(xì)研究了 ISOl4443 標(biāo)準(zhǔn)對(duì)二進(jìn)制樹(shù)防碰撞算法的規(guī)定，最后提出了在此基礎(chǔ)上的改進(jìn)算法，這也是本章的重點(diǎn)。 2． 2 RFID 二進(jìn)制樹(shù)防碰撞算法概述 2． 2． 1 基本概念 在 RFID 防碰撞算法中，二進(jìn)制樹(shù)算法是目前應(yīng)用最廣泛的一種 ，之所以稱為“二進(jìn)制樹(shù)”，是因?yàn)樵谒惴▓?zhí)行過(guò)程中，讀寫(xiě)器要多次發(fā)送命令給應(yīng)答器，每次命令都把應(yīng)答器分成兩組，多次分組后最終得到唯一的一個(gè)應(yīng)答器，在這個(gè)分組過(guò)程中，將 對(duì)應(yīng)的命令參數(shù)以節(jié)點(diǎn)的形式存儲(chǔ)起來(lái)，就可以得到一個(gè)數(shù)據(jù)的分叉樹(shù)，而所有的這些數(shù)據(jù)節(jié)點(diǎn)又是以二進(jìn)制的形式出現(xiàn)的，所以稱為“二進(jìn)制樹(shù)”。 n≥ 2，由于應(yīng)答器序列號(hào)的唯一性，將有碰撞發(fā)生，在一個(gè)時(shí)隙內(nèi)發(fā)生碰撞的概率 p 是一個(gè)隨機(jī)事件，在 n 個(gè)應(yīng)答器信息包中 i個(gè)發(fā)生碰撞的概率為： 給出 i個(gè)碰撞，則 CRI的長(zhǎng)度為： 其中 1是 n個(gè)信息包最初的一個(gè)時(shí)隙， 是 i個(gè)碰撞的順利傳輸?shù)臅r(shí)隙， 13 是 ni個(gè)無(wú)碰撞傳輸?shù)臅r(shí)隙。 (1)命令參數(shù)是 1bit 數(shù)據(jù)，還是多 bit 數(shù)據(jù)。 (2)休眠命令 Sleep(SN)：該命令攜帶一個(gè)參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應(yīng)答器被選中，進(jìn)入休眠狀態(tài)，也即是不再響應(yīng) Request 命令，除非該應(yīng)答器通過(guò)先離開(kāi)讀寫(xiě)器工作范圍再進(jìn)入的方式重新上電，才可以再次響應(yīng) Request 命令 。 2． 3． 2 實(shí)例演示 根據(jù)上述分析，下面給出一個(gè)基本二進(jìn)制樹(shù)搜索算法的實(shí)例演示，如圖 2． 4 所示。 (7)讀寫(xiě)器發(fā)送 Sleep(1l010101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號(hào)與該 SN(110l 0101)比較，其中 T3(11010101)的序列 號(hào)等于該值，則 T3 執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。根據(jù)前面的分析可知，做為一種確定性的算法，基本二進(jìn)制樹(shù)一輪循環(huán)總能識(shí)別出一個(gè)應(yīng)答器，所以在 n個(gè)應(yīng)答器的前提下，經(jīng)過(guò) n次循環(huán)可以識(shí)別出 N 個(gè)應(yīng)答器，所以整個(gè)過(guò)程中的循環(huán)次數(shù)為 n． 搜索次數(shù) 定義為算法執(zhí)行命令的次數(shù)。 (2)減少應(yīng)答器分組的詢問(wèn)次數(shù)。這兩種選擇方式并沒(méi)有本質(zhì)區(qū)別，在本文中，采取其中的一種，即：讀寫(xiě)器檢測(cè)到碰撞后，將碰撞起始位置 0，低位不變，從而將碰撞起始位 (置為 O)加低位作為新 Request 命令參數(shù)，應(yīng)答器響應(yīng)，從低位開(kāi)始比較，若對(duì)應(yīng)位等于該參數(shù)，則返回剩余位給讀寫(xiě)器，如果只有 _個(gè)應(yīng)答器響應(yīng)，讀寫(xiě)器檢 測(cè)到無(wú)碰撞發(fā)生，則將上一次發(fā)出的Request 命令參數(shù)與應(yīng)答器返回的剩余位組合起來(lái)，作為新的 Sleep 命令參，該參數(shù)也即是剛剛做出響應(yīng)的這個(gè)應(yīng)答器的序列號(hào)。 (2)讀寫(xiě)器發(fā)送 Request(0l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該SN(0101)比較，其中 Tl(10l00101)， T3(110l0l01)的序列號(hào)低四位等于該值，則 T1， T3 返回剩余位給讀寫(xiě)器，在讀寫(xiě)器接收端發(fā)生碰撞，讀寫(xiě)器檢測(cè)到返回?cái)?shù)據(jù)為 lXXX，讀寫(xiě)器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，得到 0010l，作為下一次 Request 命令參數(shù)值，即 Request(00l01)。注： Request(SN)初始值設(shè)為 Request(11ll1111)。低于該位者不變，高于該位者置 1。 2． 6 本章小結(jié) 本章歸納了現(xiàn)有的二進(jìn)制樹(shù)防碰撞算法，將其分為三個(gè)基本類別，分別講述了其實(shí)現(xiàn)思路，進(jìn)行了實(shí)例演示，并且對(duì)其做了性能分析，結(jié)果表明，動(dòng)態(tài)算法和退避式算法是對(duì)基本算法的兩個(gè)改進(jìn)思路，具有各自的優(yōu)勢(shì)。 表 3． 1IS015693 數(shù)率 3． 1． 2 IS014443 ISO 是英文 InternationalOrganizationForStandardization 的簡(jiǎn)寫(xiě)，即國(guó)際標(biāo)準(zhǔn)化組織， IEC 是 InternationalElectromechanical Commission 的簡(jiǎn)寫(xiě)，即國(guó)際電子科技化委員會(huì)， JTC(JointTechCommittee)是 ISO 和 IEC 組成的一個(gè)聯(lián)合技術(shù)委員會(huì)，負(fù)責(zé) ISO／ IEC 國(guó)際標(biāo)準(zhǔn)的起草、討論、修正、制定、表決和公布等具體事宜， JTC分為各個(gè)子委員會(huì) SC(Submittee)，子委員會(huì)又分為各個(gè)工作組 WG(WorkGroup)，其中子委員會(huì) SCl7 下的 WG8 負(fù)責(zé) ISOl444 ISOl5693以及 ISOl5693 非接觸式智能卡標(biāo)準(zhǔn)具體起草、討論修正、制定、表決和最終 ISO國(guó)際標(biāo)準(zhǔn)的公布【 24】 。有兩個(gè)主要特點(diǎn)，一是獨(dú)特的天線結(jié)構(gòu)和技術(shù)，使其讀寫(xiě)距離可以穩(wěn)定地達(dá)到 10cm 以上，同時(shí)其天線結(jié)構(gòu)中鑲嵌的特殊材料 (鐵氧體等材料 )使其天線電磁場(chǎng)的讀寫(xiě)距離非常均勻，沒(méi)有“死區(qū)”現(xiàn)象出現(xiàn)，二是 SONY 非接觸智能卡數(shù)據(jù)寫(xiě)操作失敗時(shí)的數(shù)據(jù)恢復(fù)功能。 TypeA 由 Philips 半導(dǎo)體公司首次開(kāi)發(fā)和使用，在亞洲等地區(qū)， TypeA 技術(shù)和產(chǎn)品占據(jù)了很大的市場(chǎng)份額。讀寫(xiě)器應(yīng)能確定用哪種方式。 (3)讀寫(xiě)器 發(fā)送