【正文】 100101)序列號(hào)小于該值，則 Tl 返回序列號(hào)，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測(cè)到返回?cái)?shù)據(jù)為 10100l01，做如下處理：將該值作為下一次 Sleep 命令參數(shù)值，即 Sleep(10100101)。TypeA 由 Philips 半導(dǎo)體公司首次開發(fā)和使用，在亞洲等地區(qū)，TypeA 技術(shù)和產(chǎn)品占據(jù)了很大的市場(chǎng)份額。然而，在應(yīng)用層面上 A 類有著比 B 類更多的廠商支持，是市場(chǎng)上的主流應(yīng)用技術(shù)，其后續(xù)支持較好。(1)PCD 選擇級(jí)聯(lián)層 l，發(fā)送防碰撞命令 Anti．collision。3．2 IS014443 標(biāo)準(zhǔn)二進(jìn)制樹防碰撞算法3．2．1 基本概念I(lǐng)SO／IECl4443 標(biāo)準(zhǔn)主要規(guī)定了 TYEP A 和 TYPEB 兩種類型的非接觸式智能卡，以 13．56MHz 交變信號(hào)為載波頻率，讀寫距離為 0～l0cm，通信速率均為l06kb／s(9．4us perbit)。表 3．1IS015693 數(shù)率3．1．2 IS014443ISO 是英文 InternationalOrganizationForStandardization 的簡(jiǎn)寫，即國(guó)際標(biāo)準(zhǔn)化組織， IEC 是 InternationalElectromechanical Commission 的簡(jiǎn)寫，即國(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é)ISOl444ISOl5693 以及 ISOl5693 非接觸式智能卡標(biāo)準(zhǔn)具體起草、討論修正、制定、表決和最終 ISO 國(guó)際標(biāo)準(zhǔn)的公布【24】 。低于該位者不變，高于該位者置1。(2)讀寫器發(fā)送 Request(0l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該SN(0101)比較，其中 Tl(10l00101)，T3(110l0l01)的序列號(hào)低四位等于該值，則 T1，T3 返回剩余位給讀寫器，在讀寫器接收端發(fā)生碰撞，讀寫器檢測(cè)到返回?cái)?shù)據(jù)為 lXXX，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，得到 0010l，作為下一次 Request 命令參數(shù)值，即 Request(00l01)。(2)減少應(yīng)答器分組的詢問次數(shù)。(7)讀寫器發(fā)送 Sleep(1l010101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號(hào)與該 SN(110l0101)比較，其中 T3(11010101)的序列號(hào)等于該值，則 T3 執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。(2)休眠命令 Sleep(SN)：該命令攜帶一個(gè)參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若等于，則該應(yīng)答器被選中，進(jìn)入休眠狀態(tài)，也即是不再響應(yīng) Request 命令，除非該應(yīng)答器通過先離開讀寫器工作范圍再進(jìn)入的方式重新上電，才可以再次響應(yīng) Request 命令。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í)隙，是 ni 個(gè)無碰撞傳輸?shù)臅r(shí)隙。二進(jìn)制樹防碰撞算法在多個(gè)國(guó)際標(biāo)準(zhǔn)中均有規(guī)定，基于 IS014443 標(biāo)準(zhǔn)的 TYPEA 是其中的一個(gè)典型例子，本章首先介紹了涉及到二進(jìn)制樹防碰撞算法的幾個(gè)標(biāo)準(zhǔn)，其次詳細(xì)研究了 ISOl4443 標(biāo)準(zhǔn)對(duì)二進(jìn)制樹防碰撞算法的規(guī)定，最后提出了在此基礎(chǔ)上的改進(jìn)算法，這也是本章的重點(diǎn)。因此，如何保證迅速快捷，又安全可靠的同時(shí)識(shí)別多個(gè)目標(biāo)，就成為了 RFID 技術(shù)發(fā)展的關(guān)鍵性技術(shù)。在數(shù)據(jù)的雙向傳輸過程中，是通過電磁場(chǎng)的相互感應(yīng)來實(shí)現(xiàn)的，該過程也可以用變壓器的模型來予以參考。CODE 等。RFID 二進(jìn)制樹防碰撞算法設(shè)計(jì)【摘要】射頻識(shí)別技術(shù) RFID 是目前正快速發(fā)展的一項(xiàng)新技術(shù)，它通過射頻信號(hào)進(jìn)行非接觸式的雙向數(shù)據(jù)通信，從而達(dá)到自動(dòng)識(shí)別的目的。數(shù)據(jù)交換環(huán)節(jié)即 RFID 系統(tǒng)中的讀出寫入設(shè)備，它是系統(tǒng)的核心部件，是后端應(yīng)用環(huán)境和前端信息載體的數(shù)據(jù)通道，在實(shí)際應(yīng)用中，往往被稱為查詢器，掃描器，閱讀器，編程器等，本文建議采用讀寫器(Read／Write Device)這種更具普遍意義的說法，這樣既包括了從應(yīng)答器中讀出信息，同時(shí)也包括了向應(yīng)答器中寫入信息。同時(shí)，根據(jù) RFID 系統(tǒng)的不同，在供電方式上有無源或者有源，調(diào)制方式上有幅度調(diào)制或者相位調(diào)制，數(shù)據(jù)讀取上有電感耦合或者反向散射等區(qū)別【5】 。在 RFID 系統(tǒng)中，當(dāng)工作范圍內(nèi)同時(shí)出現(xiàn)了多個(gè)讀寫器和多個(gè)應(yīng)答器時(shí)，讀寫器與讀寫器之間，應(yīng)答器與應(yīng)答器之間的相互干擾，稱 RFID 系統(tǒng)發(fā)生了碰撞【7】 ，從而導(dǎo)致數(shù)據(jù)不能正確的傳輸，信息無法得到正確的讀取，一方面影響了產(chǎn)品的識(shí)別，另一方面還可能導(dǎo)致信息的泄露。第 4 章：FPGA 實(shí)現(xiàn)改進(jìn)型二進(jìn)制樹防碰撞算法。由上式可知， 是逐漸遞歸的，通過遞歸可得：根據(jù)式()，上式可化為：由此可見， 是關(guān)于 p 的函數(shù)，則 =n/ 也是關(guān)于 p 的函數(shù)，一般情況下，可以參考二項(xiàng)分布，將 p 取為 1／2?；径M(jìn)制樹算法的流程圖如圖 2．3 所示：圖 2．3 基本二進(jìn)制樹算法流程基本二進(jìn)制樹算法的步驟如下：(1) 應(yīng)答器進(jìn)入讀寫器工作范圍，讀寫器發(fā)出一個(gè)最大序列號(hào)，所有應(yīng)答器的序列號(hào)均小于該最大序列號(hào)，所以在同一時(shí)刻將自身序列號(hào)返回給讀寫器。(8)啟動(dòng)第三輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，除 T1，T3 外所有應(yīng)答器響應(yīng)該命令，將自身序列號(hào)與該 SN(1111ll11)比較，均小于該值，于是所有應(yīng)答器均返回自身序列號(hào)給讀寫器，因?yàn)樾蛄刑?hào)的唯一性，應(yīng)答器返回的序列號(hào)在讀寫器接收端發(fā)生碰撞，讀寫器檢測(cè)到返回?cái)?shù)據(jù)為 1X101101，其中 x 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D7 位置 0，低于該位者不變，高于該位者置 1，得到 10101101，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(10101101)。本文中，定義根據(jù)第一個(gè)思路得來的算法為動(dòng)態(tài)二進(jìn)制樹，它的一個(gè)典型應(yīng)用為 ISOl4443 TYPEA 二進(jìn)制樹搜索算法。(3)讀寫器發(fā)送 Request(00l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該SN(00101)比較，其中 Tl(10100101)的序列號(hào)對(duì)應(yīng)位等于該值，則 Tl 返回剩余序列號(hào)給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測(cè)到返回?cái)?shù)據(jù)為l0l，讀寫器做如下處理：將上一次 Request(00l01)命令參數(shù) 00101 與返回?cái)?shù)據(jù) 101 組合起來，作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(10100101)。(3)讀寫器將處理后的最大序列號(hào)發(fā)送給應(yīng)答器，應(yīng)答器序列號(hào)與該值比較，小于或等于該值者，將自身序列號(hào)發(fā)回．(4)循環(huán)這個(gè)過程，選出一個(gè)最小序列號(hào)的應(yīng)答器，與之正常通信后，命令該應(yīng)答器進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng)讀寫器請(qǐng)求命令。ISO／IECl4443 標(biāo)準(zhǔn)開始于 1995年，單個(gè)系統(tǒng)于 1999 年進(jìn)入市場(chǎng)，而其完成在 2022 年以后，迄今為止，ISO／IECl4443 標(biāo)準(zhǔn)中的非接觸式智能卡的類型可以分為 TypeA 和TypeB。TYPEA 和 TYPEB 的不同主要在于載波的調(diào)制深度和位編碼方式，TYPEA 采用l00％ASK 調(diào)制、同步時(shí)序以及改進(jìn)的米勒(Miller)編碼方式，使用的是間斷式調(diào)制方式，即當(dāng)表示信息“l(fā)”時(shí)，表示有信號(hào)到卡，當(dāng)表示信息“0“時(shí)，沒有信號(hào)到卡。(2)PIC。由上面的比較可以看出，兩種技術(shù)各有優(yōu)劣，這也是 lSO 組織確定了兩種標(biāo)準(zhǔn)的原因之一。下面簡(jiǎn)要介紹一下 ISO／IECl 4443 標(biāo)準(zhǔn)中各個(gè)不同類型的非接觸式智能卡。(2)讀寫器發(fā)送 Request(1l110101)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該 SN(111l0l01)比較，其中 T1(10100101)，T3(110l0101)的序列號(hào)小于該值，則 Tl，T3 返回自身序列號(hào)給讀寫器，在讀寫器接收端發(fā)生碰撞，讀 RFID 二進(jìn)制樹防碰掩算法的研究與實(shí)現(xiàn)寫器檢測(cè)到返回?cái)?shù)據(jù)為 1XXX0101，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，高于該位者置 1，得到 11l 00101，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(1l100101)。(5)啟動(dòng)新一輪循環(huán)，重復(fù)上述步驟，總計(jì) 12 步后，依次識(shí)別出T1，T3，T2，T4，參數(shù)變化過程見圖 2．6 中標(biāo)示，具體內(nèi)容不再詳述。2．4 動(dòng)態(tài)二進(jìn)制樹防碰撞算法2．4．1 算法思路定義兩個(gè)具有普遍意義的命令來描述算法：(1)請(qǐng)求命令 Request( )，該命令攜帶一個(gè)參數(shù) SN，長(zhǎng)度為，應(yīng)答器接收到該命令，將自身的 SN 中的前 1～x 位與接收到的比較，若兩者相等，則該答器返回其 SN 的剩余位給讀寫器。(10)讀寫器發(fā)送 Sleep(10101101)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該 SN(10101101)比較，其中 T2(10101101)的序列號(hào)等于該值，則 T2 執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。(3) 讀寫器將處理后的序列號(hào)發(fā)送給應(yīng)答器，應(yīng)答器序列號(hào)與該值比較，小于或等于該值者，將自身序列號(hào)返回給讀寫器。馬爾可夫鏈遍歷性分布要滿足下列兩個(gè)條件【18】：這里有：也就是 n 個(gè)信息包從發(fā)生碰撞開始傳輸?shù)?CRI 區(qū)間長(zhǎng)度的數(shù)學(xué)期望，是在一個(gè)時(shí)隙內(nèi)到達(dá)這個(gè)系統(tǒng)信息包的期望值，該過程屬于泊松過程【l9】 。2 現(xiàn)有 RFID 二進(jìn)制樹防碰撞算法2．1 RFID 防碰撞算法概述RFID 系統(tǒng)的數(shù)據(jù)通信雙方是讀寫器和應(yīng)答器，在實(shí)際的 RFID 系統(tǒng)工作時(shí)，可能會(huì)出現(xiàn)同時(shí)多個(gè)讀寫器和多個(gè)應(yīng)答器共存的情況，毫無疑問，此時(shí)系統(tǒng)的數(shù)據(jù)交換就會(huì)出現(xiàn)信道與時(shí)序上的重疊，也就是發(fā)生了碰撞，在多個(gè)讀寫器與多個(gè)應(yīng)答器的射頻識(shí)別系統(tǒng)中，存在著兩種形式的沖突方式，一種是同一應(yīng)答器同時(shí)收到不同讀寫器發(fā)出的命令，另一種是同一個(gè)讀寫器同時(shí)收到多個(gè)不同應(yīng)答器返回的數(shù)據(jù)，前者我們稱為讀寫器碰撞，后者稱為應(yīng)答器碰撞【9】 ，在實(shí)際應(yīng)用當(dāng)中，一般是讀寫器做為主設(shè)備，來識(shí)別多個(gè)應(yīng)答器，所以發(fā)生讀寫器碰撞的應(yīng)用場(chǎng)合是不多的，因此下文將著重研究應(yīng)答器碰撞。目前關(guān)于防碰撞算法的研究還在進(jìn)行當(dāng)中，理論成果已經(jīng)得出了很多，許多國(guó)際標(biāo)準(zhǔn)也對(duì)一些成熟的算法進(jìn)行了規(guī)定，但是無論在理論效率還是實(shí)際應(yīng)用上，都還存在很大的改進(jìn)空間。(1)物流管理 ．物流管理是 RFID 技術(shù)最具應(yīng)用前景的領(lǐng)域，近年來提出了一個(gè)物聯(lián)網(wǎng)的概念，意在將全球所有的物品信息都用唯一的電子代碼來表示，從而將這些物品都聯(lián)系在一起，可以隨時(shí)隨地的識(shí)別，追蹤，管理這些物品，最終在產(chǎn)品，用戶，企業(yè)和政府之間建立但是該應(yīng)用涉及到的方面太廣，技術(shù)難度很大，目前還在研究當(dāng)中。后端應(yīng)用環(huán)境主要完成數(shù)據(jù)信息的存儲(chǔ)及處理，它實(shí)質(zhì)上就是一個(gè)數(shù)據(jù)管理系統(tǒng)，也是一個(gè)全局控制系統(tǒng)，一般由 PC 機(jī)或者工作站組成，同時(shí)也包括了應(yīng)用軟件在內(nèi)，整個(gè)后端應(yīng)用環(huán)境負(fù)責(zé)接收來自讀寫器的數(shù)據(jù)，并進(jìn)行存儲(chǔ)以及相應(yīng)的處理，協(xié)同調(diào)節(jié)多個(gè)讀寫器的工作，該部分在應(yīng)用中常稱為中間件(Savant)，它擴(kuò)展了 RFID 系統(tǒng)的應(yīng)用范圍和應(yīng)用能力，是未來 RFID 系統(tǒng)智能化，大型化發(fā)展的有力技術(shù)支撐，是 RFID 技術(shù)發(fā)展的重要方式。在各種算法當(dāng)中，二進(jìn)制樹算法因?yàn)樗R(shí)別應(yīng)答器的確定性，成為了應(yīng)用最廣泛的一種，多個(gè)國(guó)際標(biāo)準(zhǔn)均對(duì)其進(jìn)行了規(guī)定，這推動(dòng)了防碰撞算法的發(fā)展，但是也帶來了解決思路不統(tǒng)一的矛盾。由于在 RFID 系統(tǒng)中，應(yīng)答器是大規(guī)模生產(chǎn)的。(3)有源系統(tǒng)：應(yīng)答器內(nèi)置電池負(fù)責(zé)供給工作電壓。由此可見，標(biāo)準(zhǔn)統(tǒng)一化問題的重要性與困難性是并存的，這將是一個(gè)任重而道遠(yuǎn)的過程。概要性的描述了 RFID 防碰撞算法，對(duì)其進(jìn)行了分類，重點(diǎn)介紹其中的二進(jìn)制樹防碰撞算法，研究了三種最基本的二進(jìn)制樹算法，對(duì)其進(jìn)行了原理闡述，性能分析，以及實(shí)例演示。2．2．2 性能指標(biāo)定義碰撞解決時(shí)期 CRI，即 Collision Resolution Interval【16】 ，即解決一個(gè)讀寫器工作范圍內(nèi)碰撞所需要的時(shí)隙數(shù)，對(duì)二進(jìn)制樹算法的評(píng)價(jià)，一些常用的性能指標(biāo)如下所示【17】：首先是算法執(zhí)行效率 ，定義如下：在算法執(zhí)行過程，一共 個(gè)時(shí)隙，識(shí)別了 n 個(gè)應(yīng)答器，則 =n/ 表示算法的執(zhí)行效率。圖 2．2 二進(jìn)制樹算法分類2．3 基本二進(jìn)制樹防碰撞算法2．3．1 算法思路定義兩個(gè)具有普遍意義的命令來描述算法：(1)請(qǐng)求命令 Request(SN)：該命令攜帶一個(gè)參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若小于或者等于，則該應(yīng)答器回送其 SN 給讀寫器。(5)啟動(dòng)第二輪循環(huán)，讀寫器發(fā)送 Request(111l1111)命令，除 T1 外所有應(yīng)答器響應(yīng)該命令，將自身序列號(hào)與該 SN(11111l11)比較，均小于該值，于是所有應(yīng)答器均返回自身序列號(hào)給讀寫器，因?yàn)樾蛄刑?hào)的唯一性，應(yīng)答器返回的序列號(hào)在讀寫器接收端發(fā)生碰撞，讀寫器檢測(cè)到返回?cái)?shù)據(jù)為 1XXXXl01，其中 X表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4