【導(dǎo)讀】號進行非接觸式的雙向數(shù)據(jù)通信，從而達到自動識別的目的。理的算法來有效的解決該問題，稱為RFID系統(tǒng)的防碰撞算法。在傳統(tǒng)思路中，一般是通過單片機來進行算法處理，隨著RFID技。程的專用集成電路，F(xiàn)PGA擁有高速度，可編程等多個適應(yīng)于算法處理的優(yōu)點，系統(tǒng)二進制樹防碰撞算法，進行了理論與實踐方面的探討，主要分為三個方面，樹算法，該算法識別速度快，執(zhí)行效率高，極大的改進了識別效果。KeyWords：RFID；Anticollision；Read／WriteDeVices；Transponders；FPGA

　　

【正文】 于該位者不變。 (3) 讀寫器將處理后的碰撞起始位與低位發(fā)送給應(yīng)答器，應(yīng)答器序列號與該值比較，等于該值者，將自身序列號中剩余位發(fā)回． (4) 循環(huán)這個過程，就可以選出一個最小序列號的應(yīng)答器，與該應(yīng)答器進行正常通信后，發(fā)出命令使該應(yīng)答器進入休眠狀態(tài)，即除非重新上電，否則不對讀寫器請求命令起響應(yīng)。 (5) 重復(fù)上述過程，即可按序列號從小到大依次識別出各個應(yīng)答器． 2． 4． 2 實例演示 動態(tài)二進制樹算法的實例演示如圖 2． 6 所示 ，基本設(shè)置同基本二進制樹算法： 圖 2． 6動態(tài)二進制樹算法實例 (1)啟動第一輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，所有應(yīng)答器響應(yīng)該命令，按照約定，命令參數(shù)為全 1時，所有應(yīng)答器均返回自身序列號給讀寫器，因為序列號的唯一性，應(yīng)答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 1XXXXl01，其中 X 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，得到 0101，則下一次 Request命令攜帶的參數(shù)值，即 Request(0101)。 (2)讀寫器發(fā)送 Request(0l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該SN(0101)比較，其中 Tl(10l00101)， T3(110l0l01)的序列號低四位等于該值，則 T1， T3 返回剩余位給讀寫器，在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 lXXX，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，得到 0010l，作為下一次 Request 命令參數(shù)值，即 Request(00l01)。 (3)讀寫器發(fā)送 Request(00l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該SN(00101)比較，其中 Tl(10100101)的序列號對應(yīng)位等于該值，則 Tl 返回剩余序列號給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 l0l，讀寫器做如下處理：將上一次 Request(00l01)命令參數(shù) 00101 與返回數(shù)據(jù) 101組合起來，作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(10100101)。 (4)讀寫器發(fā)送 Sleep(10100101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列 22 號與該 SN(10100101)比較，其中 T1(10100101)的序列號等于該值，則 Tl執(zhí)行該命令，進入休眠狀態(tài)，即除非重新上電 ，否則不再響應(yīng) Request 命令。 (5)啟動新一輪循環(huán)，重復(fù)上述步驟，總計 12步后，依次識別出 T1， T3， T2，T4，參數(shù)變化過程見圖 2． 6中標(biāo)示，具體內(nèi)容不再詳述。 2． 4． 3 性能評價 與 3． 3． 2基本二進制樹實例圖比較可知，動態(tài)二進制樹算法的識別過程中，節(jié)點數(shù)目，循環(huán)輪次都是一樣的，但是每次循環(huán)過程中，讀寫器命令與應(yīng)答器指令所攜帶的參數(shù)都是在動態(tài)改變長度的，所以動態(tài)算法的優(yōu)勢主要體現(xiàn)在兩個方面，一是算法執(zhí)行過程中數(shù)據(jù)傳輸時間；二是算法執(zhí)行過程中數(shù)據(jù)信息量。根據(jù)分析，算法執(zhí)行過程中，讀寫器與應(yīng)答器傳送的 數(shù)據(jù)主體是應(yīng)答器的序列號，為了便于分析，假定數(shù)據(jù)交換過程中，雙方只傳送序列號 SN，則在基本算法中，讀寫器與應(yīng)答器均傳送了序列號全部長度，而在動態(tài)算法中，讀寫器傳送序列號的部分位，應(yīng)答器再傳送剩余位，兩者組合起來才得到全部的序列號，顯然，雖然每次傳送時動態(tài)算法的數(shù)據(jù)長度不同，但是在整個算法執(zhí)行過程中，基本算法傳送了兩倍序列號，動態(tài)算法則只傳送了一倍數(shù)據(jù)量，從而可知，動態(tài)算法傳送的信息量是基本算法的 50％，從而數(shù)據(jù)傳輸時間也是原基本算法的 50在本例中，由于假定了應(yīng)答器的序列號為 8 位長度二進制數(shù)，所以這個動態(tài)變化 的優(yōu)勢并不明顯，然而，事實上在實際應(yīng)用中，應(yīng)答器序列號長度往往是極大的，比如說常見的是 96 位，在這樣的情況下，動態(tài)算法的優(yōu)勢就體現(xiàn)出來了。 2． 5 退避式二進制樹防碰撞算法 2． 5． 1 算法思路 退避式二進制樹搜索算法是對基本二進制樹搜索算法的一種改進，根據(jù) 2． 3基本二進制樹算法的分析可知，每識別一個應(yīng)答器后，讀寫器恢復(fù) Request 命令參數(shù)的初始值，重新從二進制樹的根部開始執(zhí)行，對此可以采取退避的思想，即每次識別出一個應(yīng)答器后，算法返回其上一個父節(jié)點，而不返回整棵樹的根節(jié)點。 定義兩個具有普遍意義的命令來描述 算法： (1)請求命令 Request(SN)：該命令攜帶一個參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN與接收到的 SN 比較，若小于或者等于，則該應(yīng)答器回送其 SN 給讀寫器。注： Request(SN)初始值設(shè)為 Request(11ll1111)。 (2)休眠命令 Sleep(SN)：該命令攜帶一個參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應(yīng)答器被選中，進入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。退避式二進制樹算法的流程見圖2． 7，基本設(shè)置可參考基本二進制樹算法： 23 圖 2． 7退避式二進制樹算法流程 如圖所示，退避式二進制樹算法的流程與基本算法的區(qū)別在于：基本算法中，一個應(yīng)答器被識別后，重新啟動新循環(huán)時，讀寫器返回整棵樹的根節(jié)點，獲取原始 Request 命令參數(shù)，而退避式算法中，讀寫器返回上一次發(fā)生碰撞節(jié)點，獲取Request 命令參數(shù)。事實上，退避式算法的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法之所以稱為二進制樹，是因為每次碰撞后，均以碰撞起始位為界，將應(yīng)答器分為兩個部分，形象的看，如同一棵樹在進行從根部到主干到樹枝的一個不斷的分叉過程，所以，分叉也即是 分組的理念是二進制樹算法的本質(zhì)所在，根據(jù)這一點，算法每次分叉到達末端之后，不再返回根部重新開 始分叉，而是返回上一次分叉的節(jié)點即可重新開始新的樹干，該節(jié)點也即是上一次發(fā)生碰撞的節(jié)點。采用該返回思路的二進制樹算法，稱為退避式二進制樹算法。 退避式二進制樹算法的步驟如下： (1) 應(yīng)答器進入讀寫器工作范圍，讀寫器發(fā)出一個最大序列號，所有應(yīng)答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號發(fā)回給讀寫器。 (2)由于應(yīng)答器序列號的唯一性，若應(yīng)答器數(shù)目不小于兩個，必發(fā)生碰撞。此時將最大序列號中對應(yīng)碰撞起始位置 為 O。低于該位者不變，高于該位者置 1。 (3)讀寫器將處理后的最大序列號發(fā)送給應(yīng)答器，應(yīng)答器序列號與該值比較，小于或等于該值者，將自身序列號發(fā)回． (4)循環(huán)這個過程，選出一個最小序列號的應(yīng)答器，與之正常通信后，命令該應(yīng)答器進入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng)讀寫器請求命令。 (5)返回上一個發(fā)生碰撞的節(jié)點，獲取該節(jié)點對應(yīng)的最大序列號，重復(fù)上述過程，即可按序列號從小到大依次識別出各個應(yīng)答器． 24 2． 5． 2 實例演示 退避式二進制樹算法實例演示如圖 2． 8 所示，其設(shè)置參考基本二進制樹算法： 圖 2． 8退避式 二進制樹算法實例 (1)啟動第一輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該 SN(11111111)比較，均小于該值，則所有應(yīng)答器均返回自身序列號給讀寫器，因為序列號的唯一性，應(yīng)答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 lXXXXl0l，其中 X表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 1，得到 1l110l01，作為下一次 Request 命令參數(shù)，即 Request(1l1 l 0l01)。 (2)讀 寫器發(fā)送 Request(1l110101)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該 SN(111l0l01)比較，其中 T1(10100101)， T3(110l0101)的序列號小于該值，則 Tl， T3 返回自身序列號給讀寫器，在讀寫器接收端發(fā)生碰撞，讀 RFID 二進制樹防碰掩算法的研究與實現(xiàn)寫器檢測到返回數(shù)據(jù)為 1XXX0101，讀寫器做如下處理：將碰撞起始位 D5位置 0，低于該位者不變，高于該位者置 1，得到 11l 00101，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(1l100101)。 (3)讀寫器 發(fā)送 Request(11100101)命令，所有應(yīng)答器響應(yīng)，將自身序列號與 SN(1ll 00101)比較，其中 T1(10100101)序列號小于該值，則 Tl返回序列號，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 10100l01，做如下處理：將該值作為下一次 Sleep 命令參數(shù)值，即 Sleep(10100101)。 (4)讀寫器發(fā)送 Sleep(10l00l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該SN(10100ll1)比較，其中 T1(10100l01)的序列號等于該值，則 Tl 執(zhí)行該命令，進入休眠狀態(tài)， 即除非重新上電，否則不再對 Request 命令做出響應(yīng)。 (5)啟動新一輪循環(huán)，重復(fù)上述步驟，總計 12步后，依次識別出 T1， T3， T2，T4，參數(shù)變化過程見圖 2． 8中標(biāo)示，具體內(nèi)容不再詳述。 25 2． 5． 3 性能評價 與基本二進制樹比較可知，退避式算法每次傳送的數(shù)據(jù)信息量與基本算法是一樣的，區(qū)別在于，退避式算法的傳送次數(shù)，也即是所遍歷的節(jié)點數(shù)目比之基本算法大大減少，假設(shè)讀寫器工作范圍內(nèi)有 n個應(yīng)答器，則所需節(jié)點數(shù)目為而，則可用式子 2． 19來表示： 數(shù)學(xué)歸納法證明如下： 當(dāng)讀寫器工作范圍內(nèi)只有一個應(yīng)答器時，顯然有： 假設(shè) n個應(yīng)答器時，有： 則當(dāng)系統(tǒng)中有 n+1 個應(yīng)答器時，由于新增加的這個應(yīng)答器與原來 n個應(yīng)答 器的序列號均不相同，為了將其與某個匹配度最高的應(yīng)答器區(qū)分開來，需要在原 來二進制樹中增加一個節(jié)點，由于節(jié)點之間僅存在父子關(guān)系，且僅通過兩條邊相 連，所以有： 得證。 2． 6 本章小結(jié) 本章歸納了現(xiàn)有的二進制樹防碰撞算法，將其分為三個基本類別，分別講述了其實現(xiàn)思路，進行了實例演示，并且對其做了性能分析，結(jié)果表明，動態(tài)算法和退避式算法是對基本算法的兩個改進思路，具有各自的優(yōu)勢。 3 改進型二進制樹防碰撞算法 3． 1 涉及二進制樹算法的國際標(biāo)準(zhǔn) 3． 1． 1 IS0 15693 ISO l5693【 23】，短距離智能卡 (Vicinity coupling smart cards)標(biāo)準(zhǔn)，讀取距離可高達一分米，使用的頻率為 l3． 56MHz，它設(shè)計簡單，生產(chǎn)成本比IS014443 低，大都用來做出入控制、出勤考核等，現(xiàn)在很多企業(yè)使用的門禁卡大都使用這一類的標(biāo)準(zhǔn)。符合 IS015693 標(biāo)準(zhǔn)的信號接口部分的性能如下： 工作場強：工作場的最小值為 O． 15A／ m，最大場為 5A／ m。 工作頻率：工作頻率為 13． 56MKz 士 7KHz 26 調(diào)制 ：用 2種幅值調(diào)制方式，即 l0％和 l00％調(diào)制方式。讀寫器應(yīng)能確定用哪種方式。 100％幅值調(diào)制 10％的幅值調(diào)制 數(shù)據(jù)編碼 數(shù)據(jù)編碼采用脈沖位置調(diào)制。兩種數(shù)據(jù)編碼模式： 256選 1模式和 4選 1模式。 數(shù)率：有高和低兩種數(shù)率。 表 3． 1IS015693 數(shù)率 3． 1． 2 IS014443 ISO 是英文 InternationalOrganizationForStandardization 的簡寫，即國際標(biāo)準(zhǔn)化組織， IEC 是 InternationalElectromechanical Commission 的簡寫，即國際電子科技化委員會， JTC(JointTechCommittee)是 ISO 和 IEC 組成的一個聯(lián)合技術(shù)委員會，負責(zé) ISO／ IEC 國際標(biāo)準(zhǔn)的起草、討論、修正、制定、表決和公布等具體事宜， JTC分為各個子委員會 SC(Submittee)，子委員會又分為各個工作組 WG(WorkGroup)，其中子委員會 SCl7 下的 WG8 負責(zé) ISOl444 ISOl5693以及 ISOl5693 非接觸式智能卡標(biāo)準(zhǔn)具體起草、討論修正、制定、表決和最終 ISO國際標(biāo)準(zhǔn)的公布【 24】 。 ISO／ IECl4443 標(biāo)準(zhǔn)開始于 1995 年， 單個系統(tǒng)于 1999年進入市場，而其完成在 2021 年以后，迄今為止， ISO／ IECl4443 標(biāo)準(zhǔn)中的非接觸式智能卡的類型可以分為 TypeA 和 TypeB。 TypeC— G 目前已經(jīng)暫時被列入IS014443 標(biāo)準(zhǔn)，等待復(fù)議。 下面簡要介紹一下 ISO／ IECl 4443標(biāo)準(zhǔn)中各個不同類型的非接觸式智能卡。 TypeA 由 Philips 半導(dǎo)體公司首次開發(fā)和使用，在亞洲等地區(qū)， TypeA 技術(shù)和產(chǎn)品占據(jù)了很大的市場份額。 TypeA 技術(shù)設(shè)計簡單扼要，應(yīng)用項目的開發(fā)周期可以很短，同時又能起到足夠的保密作用，可以適用于非常多的應(yīng)用場 合。 TypeB 是一個開放式的非接觸式智能卡標(biāo)準(zhǔn)，所有的讀寫操作可以由應(yīng)用系統(tǒng)開發(fā)者定義，因此被世界上眾多的智能卡廠家所廣泛接受。 TypeC 由日本索尼公司研制。有兩個主要特點，一是獨特的天線結(jié)構(gòu)和技術(shù)，使其讀寫距離可以穩(wěn)定地達到 10cm 以上，同時其天線結(jié)構(gòu)中鑲嵌的特殊材料 (鐵氧體等材料 )使其天線電磁場的讀寫距離非常均勻，沒有“死區(qū)”現(xiàn)象出現(xiàn)，二是 SONY 非接觸智能卡數(shù)據(jù)寫操作失敗時的數(shù)據(jù)恢復(fù)功能。 TypeD 由 C