【正文】 (2)本文提出了自己的改進型二進制樹算法，該算法是在前述二進制樹基本思路的基礎(chǔ)上，綜合各類算法的改進思路，從理論與實例上對改進算法予以了表述，定義了數(shù)據(jù)格式，命令參數(shù)，執(zhí)行過程，完整的闡述了該算法。(11)讀寫器發(fā)送Select(00100000+1l1 01l 01)命令，應(yīng)答器T4響應(yīng)該命令，將自身序列號與該SNVB(1l1 01101)比較，等于該值，則T4執(zhí)行該命令，被選中進行數(shù)據(jù)操作，然后去選中，即除非重新上電，否則不再對AC命令做出響應(yīng)。 (9)讀寫器發(fā)送Select(00100000+l0l01101)命令，應(yīng)答器T2，T4響應(yīng)該命令，將自身序列號與該SNVB(10l01101)比較，其中T2(10101101)的序列號等于該值，則T2執(zhí)行該命令，被選中進行數(shù)據(jù)操作，然后去選擇，即除非重新上電，否則不再對AC命令做出響應(yīng)。0l，則NVB+SNvB共計15位，對8取整得l，取余得7，即NVB=‘17’，得下一次AC命令攜帶的參數(shù)值，即AC(00010ll l+0101101)。(6)讀寫器發(fā)送Select(00100000+110l0l01)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該SNVB(1l0l0l01)比較，其中T3(110l0l01)的序列號等于該值，則T3執(zhí)行該命令，被選中進行數(shù)據(jù)操作，然后去選中，即除非重新上電，否則不再對AC命令做出響應(yīng)。(4)讀寫器發(fā)送Select(00l00000+l0100101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該SNVB(10100l01)比較，其中T1(10100l01)的序列號等于該值，則Tl執(zhí)行該命令，被選中進行數(shù)據(jù)操作，然后去選中，即除非重新上電，否則不再對AC命令做出響應(yīng)。(2)讀寫器發(fā)送AC(00010100+0101)命令，有效狀態(tài)下的所有應(yīng)答器響應(yīng)該命令，將自身序列號與該SNVB(0101)逐位比較，其中T1(10l00l01)，T3(1l0l0l01)的序列號低四位等于該值，則T1，T3返回剩余位給讀寫器，在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為1XXX，第一個碰撞位為5，coll=5，讀寫器做如下處理：將第一個碰撞位置0，保留碰撞前相同位0l01，得到00l01，則NVB+SNVB共計13位，對8取整得l，取余得5，即NVB=‘15’，得下一次AC命令攜帶的參數(shù)值，即AC(000l0l0l+00l01)。注：識別出一個應(yīng)答器時，對應(yīng)著一個當前的coll值，返回上一個coll值，該值對應(yīng)生成一個Anti．collision命令，重新發(fā)出的就是該Anti．collision命令。20)．接收DeSelectResp指令，確認應(yīng)答器已經(jīng)去選擇，至此，完成對一個應(yīng)答器的完整通信過程。18)．進行數(shù)據(jù)通信，具體操作要根據(jù)實際情況而定，操作完畢，進入下一步。16)．檢查SAK，SAK中攜帶了應(yīng)答器對Select命令中SN是否完整的判斷，若不完整，則返回步驟4)。14)．發(fā)送Select命令，命令參數(shù)為NVB+SN，Select命令與Anticollision是相似的，因為此時無碰撞發(fā)生，SNRe即為完整的SN。12)．再次判斷是否發(fā)生碰撞，若繼續(xù)發(fā)生碰撞，則循環(huán)8)～11)，直到碰撞不再發(fā)生。10)．發(fā)送Anticollision命令，攜帶參數(shù)為NVB+SNVB，SNVB指SN中的有效位，根據(jù)碰撞位得來。8)．逐位比較，識別出碰撞位，置coll為第一個碰撞位的位數(shù)。6)．接收應(yīng)答器返回的SNRe，此時為多個應(yīng)答器的完整SN的混疊數(shù)據(jù)。該數(shù)值定義SNVB為空。則啟動位幀防碰撞循環(huán)，否則，啟用其它專用的防碰撞算法。2)．接收應(yīng)答器返回的Atq。長幀用在讀寫器命令中的Select命令的數(shù)據(jù)傳送?？勺儙迷谧x寫器命令中的Anticollision命令的數(shù)據(jù)傳送。短幀用在讀寫器命令中的Req，Deselect命令，以及應(yīng)答器指令中的Atq，SNRe，SAK，DeSelectResp等指令的數(shù)據(jù)傳送。DeSelectResp指令為1個字節(jié)，總長8位，最低位為有效信息位，如果相符，則該位置l，否則為0，命令格式如圖3．11所示。命令格式如圖3．9所示：圖3．9防碰撞命令應(yīng)答SNRe數(shù)據(jù)格式3．選擇命令應(yīng)答SAK該指令(SelectAcknowledge)是對選擇命令Select做出的響應(yīng)，應(yīng)答器接收到Select命令后，將參數(shù)與自身序列號比較，比較結(jié)果通過SAK指令發(fā)送給讀寫器。命令格式如圖3．8所示：圖3．8請求命令應(yīng)答Atq數(shù)據(jù)格式2．防碰撞命令應(yīng)答SNRe該指令是對防碰撞命令A(yù)nti．collision做出的響應(yīng)，根據(jù)接收到的Anticollision中的SNVB，將自身的SN與其從低位開始比較，除去相同部分后的剩余位作為指令參數(shù)，返回給讀寫器，即為SNRetum。請求命令應(yīng)答AtqAtq即answerto request，應(yīng)答器接收到來自讀寫器的請求命令Re時，發(fā)送該指令作為響應(yīng)。其命令參數(shù)為1個字節(jié)8位，事實上該參數(shù)就是上一命令Select選中的應(yīng)答器的序列號SN。3．選擇命令Select當防碰撞循環(huán)結(jié)束，讀寫器選中一個應(yīng)答器與之通信時，發(fā)送該命令，要求符合命令參數(shù)的應(yīng)答器做出響應(yīng)，其命令參數(shù)為2個字節(jié)，總計16位，事實上，該命令可以作為AC命令的一個特例來理解，即SNVB的位長固定為8位，從而得出NVB的數(shù)值也固定20(00l00000)。圖3．4請求命令Req數(shù)據(jù)格式2．防碰撞命令A(yù)nti。3．2．2基本概念為了描述算法，從讀寫器的角度，定義四個命令如下所示：1．請求命令Req讀寫器處于空閑狀態(tài)時，發(fā)送該命令，要求工作范圍內(nèi)所有的應(yīng)答器做出響應(yīng)。根據(jù)第二章的分析，可以對其進行改進，下面將詳述這個改進過程，為了描述與實現(xiàn)的便利，在改進算法的同時，也將對其做一定的簡化，簡化原則如下：(1)從應(yīng)用的普遍性和全文的統(tǒng)一性考慮，將ISo／IECl4443標準中的PCD，PICC重命名為讀寫器，應(yīng)答器，UID重命名為序列號SN。(2)防碰撞循環(huán)過程中，每次傳送的防碰撞命令A(yù)ntic01lision攜帶的命令參數(shù)的長度是變化的，即采用的是動長傳輸?shù)乃悸?。步驟15：PCD應(yīng)檢驗SAK的串聯(lián)比特是否被設(shè)置，以決定帶有遞增串聯(lián)級別的進一步防沖突環(huán)是否應(yīng)繼續(xù)進行。步驟13：它的UIDCLn與40個比特匹配，則該PlCC以其SAK表示響應(yīng)。注：該值定義了PCD將發(fā)送完整的UIDCLn。最大的重復(fù)數(shù)目是32。步驟9：只有PICC的UIDCLn中的一部分等于PCD所發(fā)送的有效位時，PICC才應(yīng)發(fā)送其UIDCLn的其余部分。這些有效位應(yīng)是PCD所決定的沖突發(fā)生之前被接收到的UIDCLn的一部分再加上(O)b或(1)b。步驟6：PCD識別出第一個沖突的位置。步驟5：假設(shè)場內(nèi)的PICC擁有唯一序列號，那么，如果一個以上的PICC響應(yīng)，則沖突發(fā)生。步驟3：PCD發(fā)送SEL和NvB。步驟2：PCD分配了帶有值為‘20’的NVB。(5) 停止狀態(tài)(Halt)：處于激活狀態(tài)的PICC完成數(shù)據(jù)操作后，接收到來自PCD的停止命令Halt，從而進入停止狀態(tài)。(3) 準備狀態(tài)(Ready)：空閑狀態(tài)的PICC接收到請求命令Req，或停止狀態(tài)的PICC接收到喚醒命令Halt，進入準備狀態(tài)，在該狀態(tài)中，完成防碰撞循環(huán)，從多張卡中選擇出一張PICC。圖3．2Isol4443標準TYPE A類型PIcc狀態(tài)轉(zhuǎn)移圖圖中各個狀態(tài)及其轉(zhuǎn)移關(guān)系說明如下：(1) 掉電狀態(tài)(PowerOff)：PICC未進入PCD工作范圍，沒獲得能量。(8)PCD接收去選擇應(yīng)答命令DeselectResp。(6)PCD發(fā)送去選擇請求命令DeselectReq，表示不再選擇該PICC。若Ats攜帶信息顯示：PICC不支持協(xié)議和參數(shù)選擇PPS，則直接進行數(shù)據(jù)交換，即步驟5)。(2)PICC接收該命令，修改相關(guān)參數(shù)。如果不需要進行參數(shù)修改，則執(zhí)行步驟5)，如果需要進行參數(shù)修改，則執(zhí)行下列操作。(4)PCD對該Ats進行檢測，決定下一步動作。(2)PICC接收到請求選擇應(yīng)答RAts，返回一個選擇應(yīng)答Ats。3．PCD與PICC進行符合ISO／IECl4443．4的數(shù)據(jù)操作。若SAK攜帶信息顯示：PICC返回的UID完整，且清除級聯(lián)層數(shù)，但是不符合IS014443—4，則PCD發(fā)送停止命令Halt，令PICC進入停止狀態(tài)Halt。(8)PCD對該SAK進行檢測，決定下一步動作。(6)PCD根據(jù)PICC的響應(yīng)，若檢測不到碰撞，則發(fā)送Select選擇命令。(4)PICC響應(yīng)防碰撞命令A(yù)nti．collision，返回其UID的部分或者全部。(2)PICC響應(yīng)防碰撞命令A(yù)nti．collision，返回其UID的部分或者全部。2．PCD與PICC進行符合ISO／IECl4443—3的位幀防碰撞循環(huán)。(4)PCD對該Atq進行檢測，決定下一步動作。(2)PICC接收到請求命令Req，返回一個請求命令應(yīng)答Atq。3 改進型二進制樹防碰撞算法3．1．1算法思路PCD的初始化，防碰撞，以及數(shù)據(jù)交換的流程如圖3．1所示：圖3．1ISOl4443標準TYPE A類型PCD通信全過程如圖所示，分為這么幾個部分：1．PCD與PICC進行符合lSO／IECl4443．2的初始化通信。2．4．3性能評價與基本二進制樹比較可知，退避式算法每次傳送的數(shù)據(jù)信息量與基本算法是一樣的，區(qū)別在于，退避式算法的傳送次數(shù)，也即是所遍歷的節(jié)點數(shù)目比之基本算法大大減少，假設(shè)讀寫器工作范圍內(nèi)有n個應(yīng)答器，則所需節(jié)點數(shù)目為而，則可用式子2．19來表示：數(shù)學歸納法證明如下：當讀寫器工作范圍內(nèi)只有一個應(yīng)答器時，顯然有：假設(shè)n個應(yīng)答器時，有：則當系統(tǒng)中有n+1個應(yīng)答器時，由于新增加的這個應(yīng)答器與原來n個應(yīng)答器的序列號均不相同，為了將其與某個匹配度最高的應(yīng)答器區(qū)分開來，需要在原來二進制樹中增加一個節(jié)點，由于節(jié)點之間僅存在父子關(guān)系，且僅通過兩條邊相連，所以有：得證。(4)讀寫器發(fā)送Sleep(10l00l01)命令，所有應(yīng)答器響應(yīng)，將自身序列號與該SN(10100ll1)比較，其中T1(10100l01)的序列號等于該值，則Tl執(zhí)行該命令，進入休眠狀態(tài)，即除非重新上電，否則不再對Request命令做出響應(yīng)。(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ā)送給應(yīng)答器，應(yīng)答器序列號與該值比較，小于或等于該值者，將自身序列號發(fā)回．(4)循環(huán)這個過程，選出一個最小序列號的應(yīng)答器，與之正常通信后，命令該應(yīng)答器進入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng)讀寫器請求命令。此時將最大序列號中對應(yīng)碰撞起始位置為O。退避式二進制樹算法的步驟如下：(1) 應(yīng)答器進入讀寫器工作范圍，讀寫器發(fā)出一個最大序列號，所有應(yīng)答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號發(fā)回給讀寫器。事實上，退避式算法的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法之所以稱為二進制樹，是因為每次碰撞后，均以碰撞起始位為界，將應(yīng)答器分為兩個部分，形象的看，如同一棵樹在進行從根部到主干到樹枝的一個不斷的分叉過程，所以，分叉也即是分組的理念是二進制樹算法的本質(zhì)所在，根據(jù)這一點，算法每次分叉到達末端之后，不再返回根部重新開始分叉，而是返回上一次分叉的節(jié)點即可重新開始新的樹干，該節(jié)點也即是上一次發(fā)生碰撞的節(jié)點。(2)休眠命令Sleep(SN)：該命令攜帶一個參數(shù)SN，應(yīng)答器接收到該命令，將自身的SN與接收到的SN比較，若等于，則該應(yīng)答器被選中，進入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng)Request命令。定義兩個具有普遍意義的命令來描述算法：(1)請求命令Request(SN)：該命令攜帶一個參數(shù)SN，應(yīng)答器接收到該命令，將自身的SN與接收到的SN比較，若小于或者等于，則該應(yīng)答器回送其SN給讀寫器。根據(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ù)，所以這個