【正文】 刻將自身序列號返回給讀寫器。 (2) 由于應(yīng)答器序列號的唯一性，當(dāng)應(yīng)答器數(shù)目不小于兩個時，必然發(fā)生碰撞．發(fā)生碰撞時，將最大序列號中對應(yīng)的碰撞起始位設(shè)置為 O，低于該位者不變，高于該位者設(shè)置為 l。 (3) 讀寫器將處理后的序列號發(fā)送給應(yīng)答器，應(yīng)答器序列號與該值比較，小于或等于該值者，將自 身序列號返回給讀寫器。 (4) 循環(huán)這個過程，就可以選出一個最小序列號的應(yīng)答器，與該應(yīng)答器進(jìn)行正常通信后，發(fā)出命令使該應(yīng)答器進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng)讀寫器請求命令。也就是說，下一次讀寫器再發(fā)最大序列號時，該應(yīng)答器不再響應(yīng)。 (5)重復(fù)上述過程，即可按序列號從小到大依次識別出各個應(yīng)答器。 注：第五步時，從步驟 1開始重復(fù)，也就是說，讀寫器識別完一個應(yīng)答器后，將重新發(fā)送原始的最大序列號。 2． 3． 2 實例演示 根據(jù)上述分析，下面給出一個基本二進(jìn)制樹搜索算法的實例演示，如圖 2． 4 所示。 假設(shè) RFID系統(tǒng)中有一個讀寫器 R，四個應(yīng)答器 Tl(10100101)， T2 16 (10l01101)， T3(11010101)， T4(11101101)，在某一時刻，四個應(yīng)答器 同時進(jìn)入讀寫器的工作范圍之內(nèi)，讀寫器發(fā)出命令，四個應(yīng)答器同時響應(yīng)，由于 其序列號 SN的唯一性，將發(fā)生應(yīng)答器碰撞，從而啟動防碰撞循環(huán)，分析如下： 圖 基本二進(jìn)制樹算法實例 注：圖中共有四輪循環(huán)，依次識別出四個應(yīng)答器，分別以不同格式的線條表 示，并加有循環(huán)輪次的數(shù)字標(biāo)識。 (1)啟動第一輪循環(huán)，讀寫器發(fā)送 Request(1lll1111)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(1l1l1111)比較，均小于該值，于是所有應(yīng)答器均返回自身序列號給讀寫器，因為序列號的唯一性，應(yīng)答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 lXXXXl0l，其中 X 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 l，得到 11ll0l01，作為下一次 Request 命令攜帶的參數(shù)值，即Request(11110l01)。 (2)讀寫器發(fā)送 Request(11110101)命令，所有應(yīng)答器響應(yīng)該命令，將 自身序列號與該 SN(11110l01)比較，其中 T1(10l00101)， T3(1l010101)的序列號小于該值，則 Tl， T3 返回自身序列號給讀寫器，在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 1XXX0l01，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，高于該位者置 l，得到 11l00l01，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(11100101)。 (3)讀寫器發(fā)送 Request(11100101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(111 00l01)比較，其中 Tl(10100l01)的序列號小于該值，則 Tl返回自身序列號給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 10100101，讀寫器做如下處理：將該數(shù)值作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(10100101)。 (4)讀寫器發(fā)送 Sleep(10100101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(10l00111)比較，其中 T1(10l00101)的序列號等于該值，則 T1 執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。 17 (5)啟動第二 輪循環(huán)，讀寫器發(fā)送 Request(111l1111)命令，除 T1 外所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(11111l11)比較，均小于該值，于是所有應(yīng)答器均返回自身序列號給讀寫器，因為序列號的唯一性，應(yīng)答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 1XXXXl01，其中 X 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 1，得到 11110101，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(11110101)。 (6)讀寫器發(fā)送 Request(11110101)命令，．除 Tl外所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(11l10101)比較，其中 T3(1l010l01)的序列號小于該值，則 T3 返回自身序列號給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 110l0101，讀寫器做如下處理：將該數(shù)值作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(11010101)。 (7)讀寫器發(fā)送 Sleep(1l010101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(110l 0101)比較，其中 T3(11010101)的序列 號等于該值，則 T3 執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。 (8)啟動第三輪循環(huán)，讀寫器發(fā)送 Request(11111111)命令，除 T1， T3 外所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(1111ll11)比較，均小于該值，于是所有應(yīng)答器均返回自身序列號給讀寫器，因為序列號的唯一性，應(yīng)答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 1X101101，其中 x表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D7 位置 0，低于該位者不變，高于該位者置 1，得到 10101101，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(10101101)。 (9)讀寫器發(fā)送 Request(10101101)命令，除 Tl， T3 外所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(10101101)比較，其中 T2(10101101)的序列號等于該值，則 T2 返回自身序列號給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 l0101101，讀寫器做如下處理：將該數(shù)值作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(10101101)。 (10)讀寫器發(fā)送 Sleep(10101101)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該 SN(10101101)比較，其中 T2(10101101)的序列號等于該值，則 T2執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。 (11)啟動第四輪循環(huán)，讀寫器發(fā)送 Request(1l111111)命令，除 Tl， T3， T2外所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(11l1l111)比較，均小于該值，則所有應(yīng)答器均返回自身序列號給讀寫器，因為只有應(yīng)答器 T4 返回數(shù)據(jù)，所以在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 11101101，讀寫器做如下處理：將該數(shù)值作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(1l1 01101)。 (12)讀寫器發(fā)送 Sleep(1ll 01101)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該 SN(11101l01)比較，其中 T4(1l1 01101)的序列號等于該值，則 T4 執(zhí)行該命令，進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng) Request 命令。 2． 3． 3 性能評價 假設(shè)工作范圍內(nèi)有 N個應(yīng)答器存在，通過基本二進(jìn)制樹搜索算法進(jìn)行防碰撞操作，依次識別出所有應(yīng)答器。循環(huán)次數(shù) 定義為在整個防碰撞循環(huán)過程中的循 18 環(huán) 輪次，也即是二進(jìn)制樹的遍歷次數(shù)。根據(jù)前面的分析可知，做為一種確定性的算法，基本二進(jìn)制樹一輪循環(huán)總能識別出一個應(yīng)答器，所以在 n個應(yīng)答器的前提下，經(jīng)過 n次循環(huán)可以識別出 N 個應(yīng)答器，所以整個過程中的循環(huán)次數(shù)為 n． 搜索次數(shù) 定義為算法執(zhí)行命令的次數(shù)。也即是二進(jìn)制樹的節(jié)點數(shù)目。該值可以用式子 來表示【 21】 ，其中 Integ 表示取整。 通信時間 t定義為數(shù)據(jù)交換的時間，也即是命令執(zhí)行的時間。假設(shè)有 n個應(yīng)答器，從讀寫器到應(yīng)答器的傳輸時間為 tl，反之為 t2．總時間為 t，則傳輸?shù)目倳r間 t 可以用式 來表示【 22】： 數(shù) 學(xué)歸納法證明如下： 假設(shè)只有一個應(yīng)答器，則讀寫器發(fā)送命令，應(yīng)答器響應(yīng)，無碰撞，識別出應(yīng)答器。 假設(shè)有兩個應(yīng)答器，則讀寫器發(fā)送命令，兩個應(yīng)答器響應(yīng)，發(fā)生碰撞，為第一次過程，該時間為： 讀寫器修改命令參數(shù)，發(fā)出命令，僅一個應(yīng)答器響應(yīng)，則識別出該應(yīng)答器， 這一次過程時間與前一次一致，讀寫器再發(fā)送命令，最后一個應(yīng)答器響應(yīng)，得到 識別，時間也是一樣的，則總時間為： 當(dāng)有 n個應(yīng)答器時，假設(shè)識別總時間為： 則當(dāng) n+1 個應(yīng)答器時，讀寫器首先發(fā)送命令，應(yīng)答器全體響應(yīng)，發(fā)生碰撞，這個過程時間為： 讀寫器修改 命令參數(shù)，發(fā)出命令， k 個應(yīng)答器響應(yīng)，余下 p 個不響應(yīng)， k+p=n+l，則識別出該 k 個應(yīng)答器需要時間為： 再識別余下 p 個需要時間為： 則這兩者時間之和為： 加上前一次的． t1+t2，總時間為： 19 得證。 因為基本二進(jìn)制樹算法中每次傳輸?shù)男蛄刑?SN 長度相同， ，所以有： 基本二進(jìn)制樹搜索算法是所有二進(jìn)制樹算法的基礎(chǔ)，分析基本二進(jìn)制樹搜索算法的性能可知，對于固定數(shù)目的應(yīng)答器，二進(jìn)制樹算法的性能主要取決于二進(jìn)制樹的節(jié)點數(shù)目和單次傳輸命令參數(shù)的時間，事實上，二進(jìn)制樹的節(jié)點數(shù)目與應(yīng)答器分組的思路是直接相 關(guān)的，而單次傳輸命令參數(shù)的時間則取決于該命令包含的數(shù)據(jù)位數(shù)。所以，要改善二進(jìn)制樹算法的性能，就必須從這兩點著手，現(xiàn)有的二進(jìn)制樹搜索算法有很多種，它們都是在基本二進(jìn)制樹搜索算法的基礎(chǔ)上加以改進(jìn)得來的，根據(jù) 前 述分析，主要的改進(jìn)思路有兩個 ： (1)減少每次通信過程中的數(shù)據(jù)傳輸位數(shù)。 (2)減少應(yīng)答器分組的詢問次數(shù)。 本文中，定義根據(jù)第一個思路得來的算法為動態(tài)二進(jìn)制樹，它的一個典型應(yīng)用為 ISOl4443 TYPEA 二進(jìn)制樹搜索算法。定義根據(jù)第二個思路得來的算法為退避式二進(jìn)制樹，它的一個典型應(yīng)用為 EPC 二進(jìn)制樹搜索 算法。 2． 4 動態(tài)二進(jìn)制樹防碰撞算法 2． 4． 1 算法思路 定義兩個具有普遍意義的命令來描述算法： (1)請求命令 Request( )，該命令攜帶一個參數(shù) SN，長度為，應(yīng)答器接收到該命令，將自身的 SN中的前 1～ x位與接收到的比較，若兩者相等，則該 答器返回其 SN 的剩余位給讀寫器。注：Request( )初始值設(shè)為 Request(1l111111)，約定當(dāng)參數(shù)值為全 1時，應(yīng)答器返回完整序列號。 (2)休眠命令 Sleep(SN)，該命令攜帶一個參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等 于，則該應(yīng)答器被選中，進(jìn)入休眠狀態(tài)，也即是不再響應(yīng) Request 命令，除非該應(yīng)答器通過先離開讀寫器工作范圍再進(jìn)入的方式重新上電，才可以再次響應(yīng) Request 命令。動態(tài)二進(jìn)制樹算法的流程與基本二進(jìn)制樹算法是一致的，它們的區(qū)別在于：基本二進(jìn)制樹算法中，應(yīng)答器返回完整序列號，而動態(tài)二進(jìn)制樹算法中，應(yīng)答器只返回序列號的有效部分；同樣，基本二進(jìn)制樹算法中，讀寫器生成新 Request 命令時，其命令參數(shù)長度是固定為8位的，而動態(tài)二進(jìn)制樹算法中，該命令參數(shù)長度是根據(jù)應(yīng)答器返回的序列號來動態(tài)變化的。 動態(tài) 二進(jìn)制樹算法的流程如 圖 2． 5所示： 20 圖 2． 5動態(tài)二進(jìn)制樹算法流程 事實上，動態(tài)二進(jìn)制樹對基本二進(jìn)制樹的改進(jìn)是基于如下考慮的，在基本二進(jìn)制樹的分析過程中可見，算法的核心部分即新命令參數(shù)的生成，是根據(jù)是否發(fā)生碰撞，以及碰撞位來決定的，特別是新 Request 命令參數(shù)的生成是由碰撞的起始位來確定的，而碰撞的起始位的得到只需要應(yīng)答器序列號中包括碰撞起始位在內(nèi)的部分位即可，把這些位稱為序列號的有效位，同樣，新 Request 命令參數(shù)也為包括碰撞起始位 (設(shè)為 0)在內(nèi)的部分位，綜合如下：若選擇高位加碰撞起始位(設(shè)為 0)，則算法為應(yīng)答器序列號 對應(yīng)位小于這些位的數(shù)值者，返回剩余低位，若選擇碰撞起始位 (設(shè)為 0)加低位，則算法為應(yīng)答器序列號對應(yīng)位等于這些位的數(shù)值者，返回剩余高位，從而讀寫器的新 Request 命令參數(shù)與應(yīng)答器返回的序列號有效部分組合起來，可以得到一個完整的應(yīng)答器序列號。這兩種選擇方式并沒有本質(zhì)區(qū)別，在本文中，采取其中的一種，即：讀寫器檢測到碰撞后，將碰撞起始位置 0，低位不變，從而將碰撞起始位 (置為 O)加低位作為新 Request 命令參數(shù)，應(yīng)答器響應(yīng)，從低位開始比較，若對應(yīng)位等于該參數(shù)，則返回剩余位給讀寫器，如果只有 _個應(yīng)答器響應(yīng)，讀寫器檢 測到無碰撞發(fā)生，則將上一次發(fā)出的Request 命令參數(shù)與應(yīng)答器返回的剩余位組合起來，作為新的 Sleep 命令參，該參數(shù)也即是剛剛做出響應(yīng)的這個應(yīng)答器的序列號。 注：如果上一次發(fā)出的 Request 為全 l，則表明讀寫器工作范圍內(nèi)只有一個應(yīng)答器，此時應(yīng)答器返回數(shù)據(jù)為完整序列號，以該序列號作為 Sleep 命令參數(shù)。 動態(tài)二進(jìn)制樹算法的步驟如下： (1) 應(yīng)答器進(jìn)入讀寫器工作范圍，讀寫器發(fā)出一個最大序列號，約定此時所有應(yīng)答器均返回完整序列號，則同一時刻應(yīng)答器將自身序列號發(fā)回給讀寫器。 (2) 由于應(yīng)答器序列號的唯一性，當(dāng) 應(yīng)答器數(shù)目不小于兩個時，必然發(fā)生碰 21 撞。發(fā)生碰撞時，將最大序列號中對應(yīng)的碰撞起始位置為 0。低