【正文】 (2)PIC。2．PCD 與 PICC 進行符合 ISO／IECl4443—3 的位幀防碰撞循環(huán)。(4)PCD 對該 Atq 進行檢測，決定下一步動作。(2)PICC 接收到請求命令 Req，返回一個請求命令應答 Atq。3．2．2 算法思路PCD 的初始化，防碰撞，以及數(shù)據(jù)交換的流程如圖 3．1 所示：圖 3．1ISOl4443 標準 TYPE A 類型 PCD 通信全過程如圖所示，分為這么幾個部分：1．PCD 與 PICC 進行符合 lSO／IECl4443．2 的初始化通信。表 3．2 讀寫器和應答器的中英文名稱及其縮寫注：這里的近距離耦合器(PCD，ProximityCoupling Device)和近耦合卡(PICC，ProximityCard)即前文的讀寫器和應答器，為尊重原 IS014443 標準，這里保留該說法。在價格上由于 A 類的廣泛性和芯片本身的低端設計性，A 類有更大的優(yōu)勢。由上面的比較可以看出，兩種技術各有優(yōu)劣，這也是 lSO 組織確定了兩種標準的原因之一。TYPEA 和 TYPEB 的不同主要在于載波的調(diào)制深度和位編碼方式，TYPEA 采用l00％ASK 調(diào)制、同步時序以及改進的米勒(Miller)編碼方式，使用的是間斷式調(diào)制方式，即當表示信息“l(fā)”時，表示有信號到卡，當表示信息“0“時，沒有信號到卡。TypeG 由中國制定，在應用層面，TypeG 體現(xiàn)出了足夠的技術先進性，但是在非接觸智能卡核心技術的研發(fā)和掌握上、微電子工業(yè)基礎設施和設備上，還有一段漫長的路要走。TypeF 由歐洲 LEGIC 公司研制，其保密系統(tǒng)的產(chǎn)品在歐洲市場占有率達到60％以上。TypeE 由以色列 oTI 公司研制，應用市場主要在歐洲和美國等地。TypeD 由 Cubic 公司研制，該系統(tǒng)的非接觸方式讀卡／認證速度非?？焖?，約為 70ms 左右，并且實現(xiàn)了數(shù)據(jù)加密技術，開創(chuàng)了交通系統(tǒng)中“刷卡”的先例。TypeC 由日本索尼公司研制。TypeA 技術設計簡單扼要，應用項目的開發(fā)周期可以很短，同時又能起到足夠的保密作用，可以適用于非常多的應用場合。下面簡要介紹一下 ISO／IECl 4443 標準中各個不同類型的非接觸式智能卡。ISO／IECl4443 標準開始于 1995年，單個系統(tǒng)于 1999 年進入市場，而其完成在 2022 年以后，迄今為止，ISO／IECl4443 標準中的非接觸式智能卡的類型可以分為 TypeA 和TypeB。數(shù)率：有高和低兩種數(shù)率。100％幅值調(diào)制10％的幅值調(diào)制數(shù)據(jù)編碼數(shù)據(jù)編碼采用脈沖位置調(diào)制。工作頻率：工作頻率為 13．56MKz 士 7KHz調(diào)制：用 2 種幅值調(diào)制方式，即 l0％和 l00％調(diào)制方式。3 改進型二進制樹防碰撞算法3．1 涉及二進制樹算法的國際標準3．1．1 IS0 15693ISO l5693【23】 ，短距離智能卡(Vicinity coupling smart cards)標準，讀取距離可高達一分米，使用的頻率為 l3．56MHz，它設計簡單，生產(chǎn)成本比IS014443 低，大都用來做出入控制、出勤考核等，現(xiàn)在很多企業(yè)使用的門禁卡大都使用這一類的標準。2．5．3 性能評價與基本二進制樹比較可知，退避式算法每次傳送的數(shù)據(jù)信息量與基本算法是一樣的，區(qū)別在于，退避式算法的傳送次數(shù)，也即是所遍歷的節(jié)點數(shù)目比之基本算法大大減少，假設讀寫器工作范圍內(nèi)有 n 個應答器，則所需節(jié)點數(shù)目為而，則可用式子 2．19 來表示：數(shù)學歸納法證明如下：當讀寫器工作范圍內(nèi)只有一個應答器時，顯然有：假設 n 個應答器時，有：則當系統(tǒng)中有 n+1 個應答器時，由于新增加的這個應答器與原來 n 個應答器的序列號均不相同，為了將其與某個匹配度最高的應答器區(qū)分開來，需要在原來二進制樹中增加一個節(jié)點，由于節(jié)點之間僅存在父子關系，且僅通過兩條邊相連，所以有：得證。(4)讀寫器發(fā)送 Sleep(10l00l01)命令，所有應答器響應，將自身序列號與該 SN(10100ll1)比較，其中 T1(10100l01)的序列號等于該值，則 Tl 執(zhí)行該命令，進入休眠狀態(tài)，即除非重新上電，否則不再對 Request 命令做出響應。(2)讀寫器發(fā)送 Request(1l110101)命令，所有應答器響應，將自身序列號與該 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ā)送給應答器，應答器序列號與該值比較，小于或等于該值者，將自身序列號發(fā)回．(4)循環(huán)這個過程，選出一個最小序列號的應答器，與之正常通信后，命令該應答器進入休眠狀態(tài)，即除非重新上電，否則不再響應讀寫器請求命令。此時將最大序列號中對應碰撞起始位置為 O。退避式二進制樹算法的步驟如下：(1) 應答器進入讀寫器工作范圍，讀寫器發(fā)出一個最大序列號，所有應答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號發(fā)回給讀寫器。事實上，退避式算法的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法之所以稱為二進制樹，是因為每次碰撞后，均以碰撞起始位為界，將應答器分為兩個部分，形象的看，如同一棵樹在進行從根部到主干到樹枝的一個不斷的分叉過程，所以，分叉也即是分組的理念是二進制樹算法的本質(zhì)所在，根據(jù)這一點，算法每次分叉到達末端之后，不再返回根部重新開始分叉，而是返回上一次分叉的節(jié)點即可重新開始新的樹干，該節(jié)點也即是上一次發(fā)生碰撞的節(jié)點。(2)休眠命令 Sleep(SN)：該命令攜帶一個參數(shù) SN，應答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態(tài)，即除非重新上電，否則不再響應 Request 命令。定義兩個具有普遍意義的命令來描述算法：(1)請求命令 Request(SN)：該命令攜帶一個參數(shù) SN，應答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若小于或者等于，則該應答器回送其 SN 給讀寫器。根據(jù)分析，算法執(zhí)行過程中，讀寫器與應答器傳送的數(shù)據(jù)主體是應答器的序列號，為了便于分析，假定數(shù)據(jù)交換過程中，雙方只傳送序列號 SN，則在基本算法中，讀寫器與應答器均傳送了序列號全部長度，而在動態(tài)算法中，讀寫器傳送序列號的部分位，應答器再傳送剩余位，兩者組合起來才得到全部的序列號，顯然，雖然每次傳送時動態(tài)算法的數(shù)據(jù)長度不同，但是在整個算法執(zhí)行過程中，基本算法傳送了兩倍序列號，動態(tài)算法則只傳送了一倍數(shù)據(jù)量，從而可知，動態(tài)算法傳送的信息量是基本算法的 50％，從而數(shù)據(jù)傳輸時間也是原基本算法的 50 在本例中，由于假定了應答器的序列號為 8 位長度二進制數(shù)，所以這個動態(tài)變化的優(yōu)勢并不明顯，然而，事實上在實際應用中，應答器序列號長度往往是極大的，比如說常見的是 96 位，在這樣的情況下，動態(tài)算法的優(yōu)勢就體現(xiàn)出來了。(5)啟動新一輪循環(huán)，重復上述步驟，總計 12 步后，依次識別出T1，T3，T2，T4，參數(shù)變化過程見圖 2．6 中標示，具體內(nèi)容不再詳述。(3)讀寫器發(fā)送 Request(00l01)命令，所有應答器響應，將自身序列號與該SN(00101)比較，其中 Tl(10100101)的序列號對應位等于該值，則 Tl 返回剩余序列號給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為l0l，讀寫器做如下處理：將上一次 Request(00l01)命令參數(shù) 00101 與返回數(shù)據(jù) 101 組合起來，作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(10100101)。(5) 重復上述過程，即可按序列號從小到大依次識別出各個應答器．2．4．2 實例演示動態(tài)二進制樹算法的實例演示如圖 2．6 所示，基本設置同基本二進制樹算法：圖 2．6 動態(tài)二進制樹算法實例(1)啟動第一輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，所有應答器響應該命令，按照約定，命令參數(shù)為全 1 時，所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 1XXXXl01，其中 X 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，得到 0101，則下一次Request 命令攜帶的參數(shù)值，即 Request(0101)。低于該位者不變。(2) 由于應答器序列號的唯一性，當應答器數(shù)目不小于兩個時，必然發(fā)生碰撞。注：如果上一次發(fā)出的 Request 為全 l，則表明讀寫器工作范圍內(nèi)只有一個應答器，此時應答器返回數(shù)據(jù)為完整序列號，以該序列號作為 Sleep 命令參數(shù)。動態(tài)二進制樹算法的流程如圖 2．5 所示：圖 2．5 動態(tài)二進制樹算法流程事實上，動態(tài)二進制樹對基本二進制樹的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法的核心部分即新命令參數(shù)的生成，是根據(jù)是否發(fā)生碰撞，以及碰撞位來決定的，特別是新 Request 命令參數(shù)的生成是由碰撞的起始位來確定的，而碰撞的起始位的得到只需要應答器序列號中包括碰撞起始位在內(nèi)的部分位即可，把這些位稱為序列號的有效位，同樣，新 Request命令參數(shù)也為包括碰撞起始位(設為 0)在內(nèi)的部分位，綜合如下：若選擇高位加碰撞起始位(設為 0)，則算法為應答器序列號對應位小于這些位的數(shù)值者，返回剩余低位，若選擇碰撞起始位(設為 0)加低位，則算法為應答器序列號對應位等于這些位的數(shù)值者，返回剩余高位，從而讀寫器的新 Request 命令參數(shù)與應答器返回的序列號有效部分組合起來，可以得到一個完整的應答器序列號。(2)休眠命令 Sleep(SN)，該命令攜帶一個參數(shù) SN，應答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態(tài)，也即是不再響應 Request 命令，除非該應答器通過先離開讀寫器工作范圍再進入的方式重新上電，才可以再次響應 Request 命令。2．4 動態(tài)二進制樹防碰撞算法2．4．1 算法思路定義兩個具有普遍意義的命令來描述算法：(1)請求命令 Request( )，該命令攜帶一個參數(shù) SN，長度為，應答器接收到該命令，將自身的 SN 中的前 1～x 位與接收到的比較，若兩者相等，則該答器返回其 SN 的剩余位給讀寫器。本文中，定義根據(jù)第一個思路得來的算法為動態(tài)二進制樹，它的一個典型應用為 ISOl4443 TYPEA 二進制樹搜索算法。所以，要改善二進制樹算法的性能，就必須從這兩點著手，現(xiàn)有的二進制樹搜索算法有很多種，它們都是在基本二進制樹搜索算法的基礎上加以改進得來的，根據(jù)前述分析，主要的改進思路有兩個：(1)減少每次通信過程中的數(shù)據(jù)傳輸位數(shù)。假設有兩個應答器，則讀寫器發(fā)送命令，兩個應答器響應，發(fā)生碰撞，為第一次過程，該時間為：讀寫器修改命令參數(shù)，發(fā)出命令，僅一個應答器響應，則識別出該應答器，這一次過程時間與前一次一致，讀寫器再發(fā)送命令，最后一個應答器響應，得到識別，時間也是一樣的，則總時間為：當有 n 個應答器時，假設識別總時間為：則當 n+1 個應答器時，讀寫器首先發(fā)送命令，應答器全體響應，發(fā)生碰撞，這個過程時間為：讀寫器修改命令參數(shù)，發(fā)出命令，k 個應答器響應，余下 p 個不響應，k+p=n+l，則識別出該 k 個應答器需要時間為：再識別余下 p 個需要時間為：則這兩者時間之和為：加上前一次的．t1+t2，總時間為：得證。通信時間 t 定義為數(shù)據(jù)交換的時間，也即是命令執(zhí)行的時間。也即是二進制樹的節(jié)點數(shù)目。循環(huán)次數(shù) 定義為在整個防碰撞循環(huán)過程中的循環(huán)輪次，也即是二進制樹的遍歷次數(shù)。(12)讀寫器發(fā)送 Sleep(1ll 01101)命令，所有應答器響應，將自身序列號與該 SN(11101l01)比較，其中 T4(1l1 01101)的序列號等于該值，則 T4 執(zhí)行該命令，進入休眠狀態(tài)，即除非重新上電，否則不再響應 Request 命令。(10)讀寫器發(fā)送 Sleep(10101101)命令，所有應答器響應，將自身序列號與該 SN(10101101)比較，其中 T2(10101101)的序列號等于該值，則 T2 執(zhí)行該命令，進入休眠狀態(tài)，即除非重新上電，否則不再響應 Request 命令。(8)啟動第三輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，除 T1，T3 外所有應答器響應該命令，將自身序列號與該 SN(1111ll11)比較，均小于該值，于是所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 1X101101，其中 x 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D7 位置 0，低于該位者不變，高于該位者置 1，得到 10101101，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(10101101)。(6)讀寫器發(fā)送 Request(11110101)命令， ．除 Tl 外所有應答器響應該命令，將自身序列號與該 SN(11l10101)比較，其中 T3(1l010l01)的序列號小于該值，則 T3 返回自身序列