【正文】 5．1 算法思路退避式二進(jìn)制樹搜索算法是對(duì)基本二進(jìn)制樹搜索算法的一種改進(jìn)，根據(jù)2．3 基本二進(jìn)制樹算法的分析可知，每識(shí)別一個(gè)應(yīng)答器后，讀寫器恢復(fù)Request 命令參數(shù)的初始值，重新從二進(jìn)制樹的根部開始執(zhí)行，對(duì)此可以采取退避的思想，即每次識(shí)別出一個(gè)應(yīng)答器后，算法返回其上一個(gè)父節(jié)點(diǎn)，而不返回整棵樹的根節(jié)點(diǎn)。定義兩個(gè)具有普遍意義的命令來(lái)描述算法：(1)請(qǐng)求命令 Request(SN)：該命令攜帶一個(gè)參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若小于或者等于，則該應(yīng)答器回送其 SN 給讀寫器。注：Request(SN)初始值設(shè)為 Request(11ll1111)。(2)休眠命令 Sleep(SN)：該命令攜帶一個(gè)參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若等于，則該應(yīng)答器被選中，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。退避式二進(jìn)制樹算法的流程見(jiàn)圖 2．7，基本設(shè)置可參考基本二進(jìn)制樹算法：圖 2．7 退避式二進(jìn)制樹算法流程如圖所示，退避式二進(jìn)制樹算法的流程與基本算法的區(qū)別在于：基本算法中，一個(gè)應(yīng)答器被識(shí)別后，重新啟動(dòng)新循環(huán)時(shí)，讀寫器返回整棵樹的根節(jié)點(diǎn)，獲取原始 Request 命令參數(shù)，而退避式算法中，讀寫器返回上一次發(fā)生碰撞節(jié)點(diǎn)，獲取 Request 命令參數(shù)。事實(shí)上，退避式算法的改進(jìn)是基于如下考慮的，在基本二進(jìn)制樹的分析過(guò)程中可見(jiàn)，算法之所以稱為二進(jìn)制樹，是因?yàn)槊看闻鲎埠?，均以碰撞起始位為界，將?yīng)答器分為兩個(gè)部分，形象的看，如同一棵樹在進(jìn)行從根部到主干到樹枝的一個(gè)不斷的分叉過(guò)程，所以，分叉也即是分組的理念是二進(jìn)制樹算法的本質(zhì)所在，根據(jù)這一點(diǎn)，算法每次分叉到達(dá)末端之后，不再返回根部重新開始分叉，而是返回上一次分叉的節(jié)點(diǎn)即可重新開始新的樹干，該節(jié)點(diǎn)也即是上一次發(fā)生碰撞的節(jié)點(diǎn)。采用該返回思路的二進(jìn)制樹算法，稱為退避式二進(jìn)制樹算法。退避式二進(jìn)制樹算法的步驟如下：(1) 應(yīng)答器進(jìn)入讀寫器工作范圍，讀寫器發(fā)出一個(gè)最大序列號(hào)，所有應(yīng)答器的序列號(hào)均小于該最大序列號(hào)，所以在同一時(shí)刻將自身序列號(hào)發(fā)回給讀寫器。(2)由于應(yīng)答器序列號(hào)的唯一性，若應(yīng)答器數(shù)目不小于兩個(gè)，必發(fā)生碰撞。此時(shí)將最大序列號(hào)中對(duì)應(yīng)碰撞起始位置為 O。低于該位者不變，高于該位者置1。(3)讀寫器將處理后的最大序列號(hào)發(fā)送給應(yīng)答器，應(yīng)答器序列號(hào)與該值比較，小于或等于該值者，將自身序列號(hào)發(fā)回．(4)循環(huán)這個(gè)過(guò)程，選出一個(gè)最小序列號(hào)的應(yīng)答器，與之正常通信后，命令該應(yīng)答器進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng)讀寫器請(qǐng)求命令。(5)返回上一個(gè)發(fā)生碰撞的節(jié)點(diǎn)，獲取該節(jié)點(diǎn)對(duì)應(yīng)的最大序列號(hào)，重復(fù)上述過(guò)程，即可按序列號(hào)從小到大依次識(shí)別出各個(gè)應(yīng)答器．2．5．2 實(shí)例演示退避式二進(jìn)制樹算法實(shí)例演示如圖 2．8 所示，其設(shè)置參考基本二進(jìn)制樹算法：圖 2．8 退避式二進(jìn)制樹算法實(shí)例(1)啟動(dòng)第一輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該 SN(11111111)比較，均小于該值，則所有應(yīng)答器均返回自身序列號(hào)給讀寫器，因?yàn)樾蛄刑?hào)的唯一性，應(yīng)答器返回的序列號(hào)在讀寫器接收端發(fā)生碰撞，讀寫器檢測(cè)到返回?cái)?shù)據(jù)為 lXXXXl0l，其中 X 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 1，得到 1l110l01，作為下一次 Request 命令參數(shù)，即 Request(1l1l 0l01)。(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)。(3)讀寫器發(fā)送 Request(11100101)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與 SN(1ll 00101)比較，其中 T1(10100101)序列號(hào)小于該值，則 Tl 返回序列號(hào)，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測(cè)到返回?cái)?shù)據(jù)為 10100l01，做如下處理：將該值作為下一次 Sleep 命令參數(shù)值，即 Sleep(10100101)。(4)讀寫器發(fā)送 Sleep(10l00l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號(hào)與該 SN(10100ll1)比較，其中 T1(10100l01)的序列號(hào)等于該值，則 Tl 執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再對(duì) Request 命令做出響應(yīng)。(5)啟動(dòng)新一輪循環(huán)，重復(fù)上述步驟，總計(jì) 12 步后，依次識(shí)別出T1，T3，T2，T4，參數(shù)變化過(guò)程見(jiàn)圖 2．8 中標(biāo)示，具體內(nèi)容不再詳述。2．5．3 性能評(píng)價(jià)與基本二進(jìn)制樹比較可知，退避式算法每次傳送的數(shù)據(jù)信息量與基本算法是一樣的，區(qū)別在于，退避式算法的傳送次數(shù)，也即是所遍歷的節(jié)點(diǎn)數(shù)目比之基本算法大大減少，假設(shè)讀寫器工作范圍內(nèi)有 n 個(gè)應(yīng)答器，則所需節(jié)點(diǎn)數(shù)目為而，則可用式子 2．19 來(lái)表示：數(shù)學(xué)歸納法證明如下：當(dāng)讀寫器工作范圍內(nèi)只有一個(gè)應(yīng)答器時(shí)，顯然有：假設(shè) n 個(gè)應(yīng)答器時(shí)，有：則當(dāng)系統(tǒng)中有 n+1 個(gè)應(yīng)答器時(shí)，由于新增加的這個(gè)應(yīng)答器與原來(lái) n 個(gè)應(yīng)答器的序列號(hào)均不相同，為了將其與某個(gè)匹配度最高的應(yīng)答器區(qū)分開來(lái)，需要在原來(lái)二進(jìn)制樹中增加一個(gè)節(jié)點(diǎn)，由于節(jié)點(diǎn)之間僅存在父子關(guān)系，且僅通過(guò)兩條邊相連，所以有：得證。2．6 本章小結(jié)本章歸納了現(xiàn)有的二進(jìn)制樹防碰撞算法，將其分為三個(gè)基本類別，分別講述了其實(shí)現(xiàn)思路，進(jìn)行了實(shí)例演示，并且對(duì)其做了性能分析，結(jié)果表明，動(dòng)態(tài)算法和退避式算法是對(duì)基本算法的兩個(gè)改進(jìn)思路，具有各自的優(yōu)勢(shì)。3 改進(jìn)型二進(jìn)制樹防碰撞算法3．1 涉及二進(jìn)制樹算法的國(guó)際標(biāo)準(zhǔn)3．1．1 IS0 15693ISO l5693【23】 ，短距離智能卡(Vicinity coupling smart cards)標(biāo)準(zhǔn)，讀取距離可高達(dá)一分米，使用的頻率為 l3．56MHz，它設(shè)計(jì)簡(jiǎn)單，生產(chǎn)成本比IS014443 低，大都用來(lái)做出入控制、出勤考核等，現(xiàn)在很多企業(yè)使用的門禁卡大都使用這一類的標(biāo)準(zhǔn)。符合 IS015693 標(biāo)準(zhǔn)的信號(hào)接口部分的性能如下：工作場(chǎng)強(qiáng)：工作場(chǎng)的最小值為 O．15A／m，最大場(chǎng)為 5A／m。工作頻率：工作頻率為 13．56MKz 士 7KHz調(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 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】 。ISO／IECl4443 標(biāo)準(zhǔn)開始于 1995年，單個(gè)系統(tǒng)于 1999 年進(jìn)入市場(chǎng)，而其完成在 2022 年以后，迄今為止，ISO／IECl4443 標(biāo)準(zhǔn)中的非接觸式智能卡的類型可以分為 TypeA 和TypeB。TypeC—G 目前已經(jīng)暫時(shí)被列入 IS014443 標(biāo)準(zhǔn)，等待復(fù)議。下面簡(jiǎn)要介紹一下 ISO／IECl 4443 標(biāo)準(zhǔn)中各個(gè)不同類型的非接觸式智能卡。TypeA 由 Philips 半導(dǎo)體公司首次開發(fā)和使用，在亞洲等地區(qū)，TypeA 技術(shù)和產(chǎn)品占據(jù)了很大的市場(chǎng)份額。TypeA 技術(shù)設(shè)計(jì)簡(jiǎn)單扼要，應(yīng)用項(xiàng)目的開發(fā)周期可以很短，同時(shí)又能起到足夠的保密作用，可以適用于非常多的應(yīng)用場(chǎng)合。TypeB 是一個(gè)開放式的非接觸式智能卡標(biāo)準(zhǔn)，所有的讀寫操作可以由應(yīng)用系統(tǒng)開發(fā)者定義，因此被世界上眾多的智能卡廠家所廣泛接受。TypeC 由日本索尼公司研制。有兩個(gè)主要特點(diǎn)，一是獨(dú)特的天線結(jié)構(gòu)和技術(shù)，使其讀寫距離可以穩(wěn)定地達(dá)到 10cm 以上，同時(shí)其天線結(jié)構(gòu)中鑲嵌的特殊材料(鐵氧體等材料)使其天線電磁場(chǎng)的讀寫距離非常均勻，沒(méi)有“死區(qū)”現(xiàn)象出現(xiàn)，二是 SONY 非接觸智能卡數(shù)據(jù)寫操作失敗時(shí)的數(shù)據(jù)恢復(fù)功能。TypeD 由 Cubic 公司研制，該系統(tǒng)的非接觸方式讀卡／認(rèn)證速度非常快速，約為 70ms 左右，并且實(shí)現(xiàn)了數(shù)據(jù)加密技術(shù)，開創(chuàng)了交通系統(tǒng)中“刷卡”的先例。并且，Cubic 將一些人體的生物特性，例如指紋、面部圖案識(shí)別等融入于非接觸智能卡技術(shù)中，開創(chuàng)了非接觸智能卡生物識(shí)別的新領(lǐng)域。TypeE 由以色列 oTI 公司研制，應(yīng)用市場(chǎng)主要在歐洲和美國(guó)等地。OTI 獨(dú)創(chuàng)的一些非接觸智能卡技術(shù)，可以使一個(gè)接觸式智能卡提升成為一個(gè)非接觸式智能卡，另外，OTI 研究開發(fā)的單芯片解決方案和雙模塊解決方案支持接觸式和非接觸式(13．56MHz)兩種接口應(yīng)用，并自動(dòng)識(shí)別和轉(zhuǎn)換。TypeF 由歐洲 LEGIC 公司研制，其保密系統(tǒng)的產(chǎn)品在歐洲市場(chǎng)占有率達(dá)到60％以上。LEGIC 保密模塊包括 SM05(S)、SMlOO(S)、SM300／400(S)等。TypeG 由中國(guó)制定，在應(yīng)用層面，TypeG 體現(xiàn)出了足夠的技術(shù)先進(jìn)性，但是在非接觸智能卡核心技術(shù)的研發(fā)和掌握上、微電子工業(yè)基礎(chǔ)設(shè)施和設(shè)備上，還有一段漫長(zhǎng)的路要走。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)。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í)，沒(méi)有信號(hào)到卡。這種方式的優(yōu)點(diǎn)是信息區(qū)別明顯，受到干擾的機(jī)會(huì)少，不容易誤操作，缺點(diǎn)是需要能量持續(xù)到卡； TYPEB 采用采用 10％ASK 調(diào)制、非同步時(shí)序和不歸零(NRz)編碼方式，使用了一種調(diào)幅的調(diào)制方式，信息“l(fā)”和“0”的區(qū)別是在于信號(hào)的強(qiáng)弱，這一點(diǎn)容易受到外界干擾，需要采用冗余校驗(yàn)來(lái)解決。由上面的比較可以看出，兩種技術(shù)各有優(yōu)劣，這也是 lSO 組織確定了兩種標(biāo)準(zhǔn)的原因之一。然而，在應(yīng)用層面上 A 類有著比 B 類更多的廠商支持，是市場(chǎng)上的主流應(yīng)用技術(shù)，其后續(xù)支持較好。在價(jià)格上由于 A 類的廣泛性和芯片本身的低端設(shè)計(jì)性，A 類有更大的優(yōu)勢(shì)。ISO／IECl4443 標(biāo)準(zhǔn)由以下四個(gè)部分組成：Part1：Physical characteristics(物理特性)；Part2：Radiofrequencypowerandsignal interface(頻譜功率和信號(hào)接口)㈣；Part3：Initialization andanti．collision(初始化和防碰撞算法)例；Part4：Transmissionprotocols(傳輸協(xié)議)。表 3．2 讀寫器和應(yīng)答器的中英文名稱及其縮寫注：這里的近距離耦合器(PCD，ProximityCoupling Device)和近耦合卡(PICC，ProximityCard)即前文的讀寫器和應(yīng)答器，為尊重原 IS014443 標(biāo)準(zhǔn)，這里保留該說(shuō)法。表 3．3Type A 的通信信號(hào)接口ISOl4443 標(biāo)準(zhǔn)在第三部分:“初始化和防碰撞算法”中，對(duì)防碰撞算法進(jìn)行了規(guī)定，定義了 PICC 進(jìn)入 PCD 時(shí)的輪詢，通信初始化階段，從多卡中選取其中的一張的方法等。3．2．2 算法思路PCD 的初始化，防碰撞，以及數(shù)據(jù)交換的流程如圖 3．1 所示：圖 3．1ISOl4443 標(biāo)準(zhǔn) TYPE A 類型 PCD 通信全過(guò)程如圖所示，分為這么幾個(gè)部分：1．PCD 與 PICC 進(jìn)行符合 lSO／IECl4443．2 的初始化通信。(1)PCD 不斷發(fā)送請(qǐng)求命令 Req，檢測(cè)工作范圍內(nèi)的 PlCC。(2)PICC 接收到請(qǐng)求命令 Req，返回一個(gè)請(qǐng)求命令應(yīng)答 Atq。(3)PCD 接收到來(lái)自 PICC 的請(qǐng)求命令應(yīng)答 Atq，表明有 PICC 存在。(4)PCD 對(duì)該 Atq 進(jìn)行檢測(cè)，決定下一步動(dòng)作。此時(shí)若 Atq 攜帶信息顯示，PICC 符合 ISOl4443—3，則啟動(dòng)位幀防碰撞循環(huán)，否則啟動(dòng)專用的防碰撞循環(huán)。2．PCD 與 PICC 進(jìn)行符合 ISO／IECl4443—3 的位幀防碰撞循環(huán)。(1)PCD 選擇級(jí)聯(lián)層 l，發(fā)送防碰撞命令 Anti．collision。(2)P