二，改進(jìn)的二進(jìn)制搜索算法
2.1算法約定
鑒于BS算法的缺點(diǎn)，本文提出了一種改進(jìn)的二進(jìn)制搜索算法，算法約定如下：
(1)采用曼徹斯特編碼的電子標(biāo)簽序列號(hào)每個(gè)比特位上的取值不是“0”就是“1”。因此，如果當(dāng)讀寫器探測(cè)到僅有一位碰撞位時(shí)，讀寫器不需要發(fā)送請(qǐng)求命令，可以直接識(shí)別出2個(gè)標(biāo)簽。
(2)讀寫器如果檢測(cè)到有N個(gè)碰撞位，則說明這N個(gè)碰撞位的比特位對(duì)讀寫器來說是未知的，而其他的比特位對(duì)讀寫器來說是已知的。因此讀寫器只需要對(duì)未知的碰撞位處理，而不需要傳輸那些已知的比特位，從而減少傳輸時(shí)延。
為了便于描述以及實(shí)現(xiàn)該算法，給出如下防碰撞命令：
①查詢命令request(DX，MX;DX1，MX1)。參數(shù)DX、DX1分別為檢測(cè)到碰撞位的最高位和次高位，參數(shù)MX、MX1為0、1的二維排列組合，例如檢測(cè)到1?1?00?1，那么讀寫器發(fā)送request(D6，0;D4，0)符合條件的標(biāo)簽響應(yīng)并返回沖突位及相關(guān)信息。
?、谕顺鲞x擇命令unselect.取消事先選中的電子標(biāo)簽，使標(biāo)簽進(jìn)入“無聲”狀態(tài)。在這種狀態(tài)下標(biāo)簽完全是非激活的，對(duì)收到的request命令不做應(yīng)答。為了重新激活標(biāo)簽，必須暫時(shí)離開讀寫器的作用范圍，然后再次進(jìn)入該讀寫器范圍。
2.2算法原理
下面以讀寫器作用范圍內(nèi)的8個(gè)編碼為8bit的標(biāo)簽為例說明該算法，8個(gè)標(biāo)簽的編碼如下：tag1：01001000，tag2：01010100，tag3：01011010，tag4：01000000，tag5：01000010，
tag6：01010000，tag7：01001010，tag8：01011000.
(1)request≤11111111命令，讀寫器作用范圍內(nèi)的所有標(biāo)簽應(yīng)答，讀寫器譯碼的結(jié)果為010????0碰撞位為D4，D3，D2，D1，最高碰撞位為D4，次高碰撞位為D3，因此下次查詢命令為request(D4，0;D3，0)。
(2)讀寫器發(fā)送查詢命令request(D4，0;D3，0)，標(biāo)簽通過比較各自的D4、D3位，與之相同的標(biāo)簽則發(fā)送自己的相關(guān)信息給讀寫器。通過比較后標(biāo)簽4和標(biāo)簽5響應(yīng)，編碼后得到010000?0，讀寫器檢測(cè)到僅只有一位碰撞，可以直接識(shí)別出標(biāo)簽4和標(biāo)簽5.讀寫器正確識(shí)別它們之后，執(zhí)行unselect命令，使標(biāo)簽4和標(biāo)簽5處于“無聲”狀態(tài)。
(3)讀寫器發(fā)送查詢命令request(D4，0;D3，1)，標(biāo)簽1和標(biāo)簽7響應(yīng)，編碼后得到010010?0，讀寫器檢測(cè)到僅只有一位碰撞，可以直接識(shí)別出標(biāo)簽1和標(biāo)簽7.讀寫器正確識(shí)別它們之后，執(zhí)行unselect命令，使標(biāo)簽1和標(biāo)簽7處于“無聲”狀態(tài)。
(4)讀寫器發(fā)送查詢命令request(D4，1;D3，0)，標(biāo)簽2和標(biāo)簽6響應(yīng)，編碼后得到01010?00，讀寫器檢測(cè)到僅只有一位碰撞，可以直接識(shí)別出標(biāo)簽2和標(biāo)簽6.讀寫器正確識(shí)別它們之后，執(zhí)行unselect命令，使標(biāo)簽1和標(biāo)簽7處于“無聲”狀態(tài)。
(5)讀寫器發(fā)送查詢命令request(D4，1;D3，1)，標(biāo)簽3和標(biāo)簽8響應(yīng)，編碼后得到010110?0，讀寫器檢測(cè)到僅只有一位碰撞，可以直接識(shí)別出標(biāo)簽3和標(biāo)簽8.讀寫器正確識(shí)別它們之后，執(zhí)行unselect命令，使標(biāo)簽1和標(biāo)簽7處于“無聲”狀態(tài)。至此，讀寫器作用范圍內(nèi)的所有標(biāo)簽都別正確識(shí)別完畢。算法流程如圖1所示。
四，算法性能比較
假設(shè)讀寫器作用范圍內(nèi)有N個(gè)電子標(biāo)簽，則BS算法完成所有標(biāo)簽識(shí)別的搜索命令次數(shù)S(N)為：
通過理論和仿真比較，采用改進(jìn)后的二進(jìn)制搜索算法較其他兩個(gè)算法有三個(gè)方面的優(yōu)勢(shì)：其一減少了查詢標(biāo)簽次數(shù)，使計(jì)算時(shí)間減小;其二減少了系統(tǒng)數(shù)據(jù)傳輸量，提高了標(biāo)簽的識(shí)別速率;其三較大地提高了系統(tǒng)的吞吐率。
本文對(duì)BS算法及DBS算法過程進(jìn)行了分析，找出了其中的不足之處，在此基礎(chǔ)上提出了一種改進(jìn)的二進(jìn)制搜索算法，并通過Matlab仿真得到該算法的查詢次數(shù)和吞吐率方面的數(shù)據(jù)。通過實(shí)驗(yàn)數(shù)據(jù)表明，該改進(jìn)算法可以減少系統(tǒng)的查詢次數(shù)，提高系統(tǒng)的吞吐率。從而驗(yàn)證了該改進(jìn)算法的優(yōu)越性