周艷聰，何敏，顧軍華，董永峰

1.河北工業(yè)大學(xué)電氣工程學(xué)院，天津 300130

2.河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401

3.天津商業(yè)大學(xué)信息工程學(xué)院，天津 300134

引入信息預(yù)處理的多狀態(tài)二進(jìn)制改進(jìn)算法

周艷聰1，3，何敏2，顧軍華2，董永峰2

1.河北工業(yè)大學(xué)電氣工程學(xué)院，天津 300130

2.河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401

3.天津商業(yè)大學(xué)信息工程學(xué)院，天津 300134

1 引言

RFID（Radio Frequency Identification，無線射頻識別技術(shù)）是一種非接觸數(shù)據(jù)自動(dòng)采集技術(shù)，它以空間電磁波為傳輸媒介進(jìn)行雙向通信和自動(dòng)識別，已成為目前發(fā)展最為迅速、潛力最大的新興技術(shù)之一。RFID系統(tǒng)主要由閱讀器和標(biāo)簽兩部分組成。當(dāng)標(biāo)簽進(jìn)入閱讀器天線電磁場后，閱讀器通過無線方式實(shí)現(xiàn)對標(biāo)簽的數(shù)據(jù)采集。當(dāng)多個(gè)標(biāo)簽進(jìn)入閱讀器的識讀范圍時(shí)，閱讀器不能同時(shí)響應(yīng)多個(gè)標(biāo)簽的通訊請求，這時(shí)也就產(chǎn)生了標(biāo)簽碰撞問題，從而導(dǎo)致無法進(jìn)行有效、快速的識別。因此，標(biāo)簽防碰撞算法研究成為RFID的重要研究領(lǐng)域。

目前的RFID防碰撞算法主要分為概率性算法和確定性算法兩大類。概率性算法操作簡單，便于實(shí)際應(yīng)用，但其隨機(jī)性大，特性隨著標(biāo)簽數(shù)量的擴(kuò)大會(huì)急劇惡化。確定性算法電路實(shí)現(xiàn)比較復(fù)雜，算法識別率較高，識別速度快，識別準(zhǔn)確率高[1]，因此很多學(xué)者對確定性算法進(jìn)行了研究。典型的有基本二進(jìn)制算法、BBT（Bit-by-Bit Tree）算法[2]、Q-Tree算法[3]、ABS（Adaptive Binary Splitting）算法[4]等；文獻(xiàn)[5]提出一種EAA算法；文獻(xiàn)[6]介紹的基本二進(jìn)制算法實(shí)現(xiàn)簡單，但是閱讀器與標(biāo)簽間的數(shù)據(jù)傳輸量大，交互次數(shù)多，效率低；文獻(xiàn)[7]提出了一種返回式二進(jìn)制搜索算法，這種算法利用棧的思想減少了交互次數(shù)，在一定程度上降低了通訊量，但仍存在較大數(shù)據(jù)冗余；針對基本二進(jìn)制算法中每次都會(huì)發(fā)送大量冗余信息的情況，文獻(xiàn)[8]提出了一種根據(jù)部分已知ID動(dòng)態(tài)查詢ID的動(dòng)態(tài)二進(jìn)制算法，閱讀器每次只發(fā)送從最高位到碰撞位的信息作為搜索前綴，即部分標(biāo)簽的相同前綴，標(biāo)簽發(fā)送碰撞位后的信息，從而減少通訊量。文獻(xiàn)[9-14]等專門對二進(jìn)制算法進(jìn)行了研究和改進(jìn)。文獻(xiàn)[9]提出了一種改進(jìn)的二進(jìn)制算法，采用動(dòng)態(tài)方式傳輸數(shù)據(jù)，簡化了閱讀器發(fā)送的指令和沖突檢測過程；文獻(xiàn)[10]對多狀態(tài)二進(jìn)制算法進(jìn)行了改進(jìn)，通過減少發(fā)令次數(shù)，進(jìn)一步減少了交互次數(shù)和通訊量；文獻(xiàn)[11]針對二進(jìn)制搜索樹所需搜索時(shí)隙多，識別效率低的缺點(diǎn)，對發(fā)生碰撞的比特位進(jìn)行深度分解，并調(diào)整搜索狀態(tài)，從而減少了搜索時(shí)隙數(shù)；文獻(xiàn)[12]改進(jìn)了基于退避思想的動(dòng)態(tài)二進(jìn)制搜索算法，采用FPGA進(jìn)行算法實(shí)現(xiàn)，用硬件方式進(jìn)一步提高算法效率；文獻(xiàn)[13]提出了一種對碰撞位連續(xù)的標(biāo)簽進(jìn)行識別的新算法，其僅對碰撞位連續(xù)情況作了探討。以上研究均對二進(jìn)制防碰撞算法進(jìn)行了某方面的改進(jìn)，但它們大多都同時(shí)傳輸了碰撞位和非碰撞位數(shù)據(jù)，雖然文獻(xiàn)[10]也采用了預(yù)處理的方式，但閱讀器與標(biāo)簽之間的通信量仍存在冗余。本文將對多狀態(tài)二進(jìn)制防碰撞算法進(jìn)行進(jìn)一步改進(jìn)，通過對非碰撞位和無效數(shù)據(jù)的屏蔽來減少閱讀器的接收數(shù)據(jù)，通過狀態(tài)標(biāo)志變化減少交互次數(shù)，從而大大降低整體通訊量，提高了標(biāo)簽識別效率。

2 幾種典型二進(jìn)制算法

在二進(jìn)制算法研究中，比較典型的算法有基本二進(jìn)制算法、返回式二進(jìn)制算法、動(dòng)態(tài)二進(jìn)制算法、多狀態(tài)二進(jìn)制算法，以及基于這些基本典型算法的改進(jìn)算法。其基本思想是將碰撞標(biāo)簽分成0和1兩個(gè)子集，先查詢子集0，無碰撞，則正確識別；若仍有碰撞，則把0子集繼續(xù)分裂成00和01兩個(gè)子集；依次類推，直到識別出子集0中全部標(biāo)簽，再按同樣方法查詢子集1。

2.1 基本二進(jìn)制算法

基本二進(jìn)制以標(biāo)簽序列號為識別基礎(chǔ).當(dāng)檢測到?jīng)_突時(shí)，通過將最高沖突位置0，完成標(biāo)簽組的劃分。標(biāo)簽只對大于等于自身序列號的閱讀器指令回應(yīng)，閱讀器根據(jù)得到的回傳信息修改下一條指令，直到所有標(biāo)簽被正確識別。

具體實(shí)現(xiàn)步驟如下：

（1）閱讀器發(fā)送全“1”指令，令所有標(biāo)簽回傳數(shù)據(jù)。

（2）閱讀器接收標(biāo)簽回傳的信息，檢測沖突位。

（3）有沖突時(shí)，把指令對應(yīng)最高沖突位置0，以此為新的查詢指令，依次排除序列號大于新指令的標(biāo)簽。

（4）無沖突時(shí)直接識別。識別后，對其進(jìn)行去活操作，使其進(jìn)入“無聲”狀態(tài)，對閱讀器發(fā)送的查詢命令不再進(jìn)行響應(yīng)。

（5）重復(fù)步驟（1），繼續(xù)識別標(biāo)簽。

（6）多次檢測后完成所有標(biāo)簽的識別。

2.2 返回式二進(jìn)制算法

返回式二進(jìn)制算法在整個(gè)的搜索流程上和基本二進(jìn)制算法類似，只是加入了棧的思想，使識別完一個(gè)標(biāo)簽后無需返回根節(jié)點(diǎn)從頭開始新標(biāo)簽的識別，而是從離已識別標(biāo)簽最近的識別命令開始，繼續(xù)新標(biāo)簽識別，這樣使交互次數(shù)大大減少。

2.3 動(dòng)態(tài)二進(jìn)制算法

動(dòng)態(tài)二進(jìn)制算法的基本思想：設(shè)標(biāo)簽有L位，在第X位發(fā)生碰撞（從左至右排列），閱讀器發(fā)送參數(shù)（標(biāo)簽的前X位）給區(qū)域內(nèi)標(biāo)簽，與標(biāo)簽前0～X-1位相符的標(biāo)簽發(fā)送剩余的X+1～L-1位信息。但是第一次問詢時(shí)，讀寫器發(fā)送全1指令，處于讀寫器作用域的所有標(biāo)簽都應(yīng)答，其余命令與基本二進(jìn)制搜索算法相同。將動(dòng)態(tài)二進(jìn)制算法和返回式二進(jìn)制算法結(jié)合，形成的動(dòng)態(tài)返回式二進(jìn)制算法，其在減少通訊量和交互次數(shù)上都有很好的改進(jìn)。

2.4 多狀態(tài)二進(jìn)制算法

算法的主要思想是引入休眠計(jì)數(shù)的方法，閱讀器只發(fā)送最高沖突位的位置信息。標(biāo)簽中設(shè)狀態(tài)標(biāo)志，值為0時(shí)該標(biāo)簽為未屏蔽狀態(tài)，值大于0為屏蔽態(tài)，值為-1的去活態(tài)標(biāo)簽表示已被識別，不再響應(yīng)閱讀器發(fā)送的命令。閱讀器檢測到最高沖突位（假設(shè)為第X位）后，將發(fā)送命令Request（B，X），B是0或者1，處于未被屏蔽狀態(tài)且第X位為0的標(biāo)簽將自身ID號的后X+1～L-1位回傳給閱讀器，其他標(biāo)簽屏蔽值增加1（不論原來是未屏蔽狀態(tài)還是屏蔽狀態(tài)）。閱讀器從接收的數(shù)據(jù)中檢測到新的最高沖突位，重復(fù)上述過程進(jìn)行搜索，直到檢測到無沖突標(biāo)簽，接著發(fā)送一次激活命令，激活屏蔽值為1的標(biāo)簽，將其轉(zhuǎn)為未屏蔽態(tài)，并按返回式二進(jìn)制樹形搜索的方法修改B值返回搜索；重復(fù)，直到所有標(biāo)簽均被識別。

以4個(gè)8位二進(jìn)制標(biāo)簽（10110010，10100011，10110011，11100011）為例，表1、表2、表3和表4分別展示了基本二進(jìn)制、返回式二進(jìn)制、返回式動(dòng)態(tài)二進(jìn)制和多狀態(tài)二進(jìn)制的標(biāo)簽識別過程。

表1 基本二進(jìn)制識別過程

表2 返回式二進(jìn)制識別過程

表3 返回式動(dòng)態(tài)二進(jìn)制識別過程

本文將主要對多狀態(tài)二進(jìn)制防碰撞算法進(jìn)行研究，并針對普通多狀態(tài)二進(jìn)制算法通訊數(shù)據(jù)存在冗余的情況，提出了一種基于信息預(yù)處理的多狀態(tài)二進(jìn)制改進(jìn)算法。該算法將引入信息預(yù)處理與閱讀器部分接收機(jī)制，在識別過程只處理沖突位，并融合動(dòng)態(tài)二進(jìn)制的優(yōu)點(diǎn)，使閱讀器只接收并記錄標(biāo)簽部分?jǐn)?shù)據(jù)，狀態(tài)標(biāo)志根據(jù)不同指令變化，減少交互次數(shù)，從而降低通訊數(shù)據(jù)量。

3 加入信息預(yù)處理的多狀態(tài)二進(jìn)制改進(jìn)算法

3.1 算法基本思想

本文算法的主要思想是在多狀態(tài)二進(jìn)制算法中引入信息預(yù)處理機(jī)制，同時(shí)對閱讀器接收標(biāo)簽數(shù)據(jù)的過程進(jìn)行改進(jìn)，只接收相鄰兩個(gè)沖突位之間的有效信息并記錄，盡量避免數(shù)據(jù)重復(fù)發(fā)送和接收；同時(shí)，通過對狀態(tài)標(biāo)志的有效控制減少命令個(gè)數(shù)，從而減少交互次數(shù)。由于實(shí)際應(yīng)用中標(biāo)簽編碼存在一定的規(guī)律，當(dāng)大量標(biāo)簽并存時(shí)，往往部分位是一致的，即不存在沖突，而防碰撞算法只需要識別沖突位信息，故在標(biāo)簽識別前進(jìn)行一次預(yù)處理，一次性檢驗(yàn)出所有沖突位，然后只對沖突位信息進(jìn)行后繼的處理，這樣勢必大大減少通訊量。經(jīng)過預(yù)處理后的標(biāo)簽根據(jù)狀態(tài)標(biāo)志對閱讀器做不同應(yīng)答。未屏蔽狀態(tài)標(biāo)簽回傳數(shù)據(jù)，只傳遞沖突位信息。閱讀器接收時(shí)只要檢測到有兩位及其以上沖突位，則只接收命令中指定位到當(dāng)前最高沖突位之間的數(shù)據(jù)，其余數(shù)據(jù)不接收。檢測到有一位沖突時(shí)識別兩個(gè)標(biāo)簽，無沖突時(shí)直接識別。有標(biāo)簽被識別后，各標(biāo)簽對應(yīng)狀態(tài)標(biāo)志均作相應(yīng)變化。

在改進(jìn)算法中，采用曼徹斯特編碼方式，用上升沿表示邏輯0，下降沿表示邏輯1，并且約定每個(gè)標(biāo)簽只能擁有唯一的編碼，不得重復(fù)；所有標(biāo)簽在同一時(shí)刻傳送數(shù)據(jù)，即做到標(biāo)簽同步。

3.2 算法流程

具體操作中，每個(gè)標(biāo)簽配備兩個(gè)重要參數(shù)：狀態(tài)標(biāo)志stateflag和傳送位標(biāo)志startflag。stateflag表示標(biāo)簽被屏蔽情況，0為未屏蔽，大于0為被屏蔽，-1為去活態(tài)即標(biāo)簽被識別。startflag表示標(biāo)簽傳送數(shù)據(jù)起始位，即標(biāo)簽從startflag位開始傳送。當(dāng)檢測到兩位碰撞位時(shí)，閱讀器將不再對后面數(shù)據(jù)進(jìn)行檢測，標(biāo)簽傳送從startflag開始的數(shù)據(jù)；標(biāo)簽只有一位碰撞時(shí)，兩個(gè)碰撞的標(biāo)簽可以同時(shí)被識別[9]。

標(biāo)簽數(shù)據(jù)按從高到低，即從左至右的順序進(jìn)行傳送，最低位即最右位記為0。

預(yù)處理過程：

（1）閱讀器發(fā)送全“1”指令，令所有標(biāo)簽回傳數(shù)據(jù)。

（2）閱讀器接收數(shù)據(jù)，檢測碰撞位。

（3）將碰撞位組織成新的標(biāo)簽，記新標(biāo)簽長度為M。

閱讀器處理流程：

（1）用0初始化指令參數(shù)棧（指令request（0）將令所有標(biāo)簽回傳所有數(shù)據(jù)）。令當(dāng)前最高沖突位為M-1；閱讀器發(fā)送Request(M-1)，等待標(biāo)簽回應(yīng)。

（2）接收標(biāo)簽數(shù)據(jù)。

（3）若無沖突，識別標(biāo)簽；指令棧非空時(shí)指令參數(shù)出棧，得到上一個(gè)最高沖突位；轉(zhuǎn)（6）。指令棧空則停止。

（4）如果只有一位沖突，同時(shí)識別兩個(gè)標(biāo)簽；指令棧非空時(shí)指令參數(shù)出棧，得到上一個(gè)最高沖突位；轉(zhuǎn)（6）。指令?？談t停止。

（5）如果多于一位沖突，最高沖突位入指令參數(shù)棧；記錄當(dāng)前新的最高沖突位及其以前的數(shù)據(jù)；轉(zhuǎn)（6）。

（6）若仍有未被識別標(biāo)簽，則發(fā)送Request（二進(jìn)制表示的最高沖突位）。

（7）接收當(dāng)前最高沖突位以后的標(biāo)簽數(shù)據(jù)，轉(zhuǎn)（3）。

標(biāo)簽：

（1）如果閱讀器指令為Request（0），所有標(biāo)簽回傳所有數(shù)據(jù)。

（2）如果閱讀器指令為Request（二進(jìn)制表示的最高沖突位）；處于未被屏蔽狀態(tài)且對應(yīng)沖突位為0的標(biāo)簽回傳沖突位以后的數(shù)據(jù)，即從startflag開始傳送數(shù)據(jù)；對應(yīng)沖突位為1的標(biāo)簽做屏蔽設(shè)定，即屏蔽標(biāo)志加1。

（3）若有標(biāo)簽被識別，被識別標(biāo)簽設(shè)為去活狀態(tài)，不再參與響應(yīng)，其他標(biāo)簽屏蔽標(biāo)志減1。

整體算法流程圖，如圖1所示。

3.3 算法示例

隨機(jī)選取4個(gè)8位標(biāo)簽：10110010，10100011，10110011，11100011。通過預(yù)處理，檢測出碰撞位為0、4、6三位，將這三位組成一個(gè)新的標(biāo)簽進(jìn)行后續(xù)的識別，這時(shí)標(biāo)簽新編號為010、001、011、101。將這四個(gè)3 bit的標(biāo)簽按照3.2節(jié)所述過程進(jìn)行識別，此時(shí)，標(biāo)簽長度M為3，用0初始化指令參數(shù)棧，并初始化最高沖突位為2。所有標(biāo)簽的開始傳送標(biāo)志startflag（初始為2）減去1，表示下一次標(biāo)簽將從第1位開始傳輸數(shù)據(jù)。由于第2位肯定沖突，所以第一次閱讀器發(fā)送指令Request（二進(jìn)制表示的最高沖突位），為Request（2），這時(shí)第2位是0的標(biāo)簽響應(yīng)，傳送第1位及其之后的數(shù)據(jù)；經(jīng)檢測，發(fā)現(xiàn)仍存在多于1位的沖突，最高沖突位“2”入棧，當(dāng)前最高沖突位更新為“1”，記錄第1位以前的數(shù)據(jù)。已識別字串記錄第2位的‘0’，并入棧；待識別字串記錄第2位的‘1’，在閱讀器下一次從此位開始搜索時(shí)，這一位的數(shù)據(jù)將不用再次發(fā)送，而是直接取出，減少了標(biāo)簽和閱讀器之間的交互。第二次，閱讀器發(fā)送指令Request（1），這時(shí)，第1位為0的只有001這個(gè)標(biāo)簽，因此這個(gè)標(biāo)簽被識別，對標(biāo)簽做去活處理，即將stateflag位置-1，其余標(biāo)簽的stateflag減1。第三次，閱讀器將最高碰撞位（2）出棧，stateflag為0且第2位為0的標(biāo)簽響應(yīng)并傳遞數(shù)據(jù)，閱讀器檢測到兩個(gè)標(biāo)簽傳遞數(shù)據(jù)且只有一個(gè)碰撞位，由于這兩個(gè)標(biāo)簽上一輪傳遞的數(shù)據(jù)已被保存在棧里，將數(shù)據(jù)出棧，和碰撞位做拼接（一個(gè)置0，一個(gè)置1），再加上標(biāo)簽本次檢測傳遞過來的數(shù)據(jù)，這樣可以同時(shí)識別兩個(gè)標(biāo)簽。第四次，由于棧非空，指令參數(shù)棧出棧，為（0），閱讀器發(fā)送Request（0），stateflag為0的所有標(biāo)簽傳遞數(shù)據(jù)，和待識別字串記錄的首位“1”拼接，組成完整的標(biāo)簽被識別。詳細(xì)識別過程見表5。

表4 多狀態(tài)二進(jìn)制識別過程

圖1 改進(jìn)二進(jìn)制防碰撞算法流程圖

表5 標(biāo)簽識別過程（預(yù)處理后）

同時(shí)，分別采用基本二進(jìn)制、動(dòng)態(tài)二進(jìn)制、返回式二進(jìn)制、文獻(xiàn)[9]算法和文獻(xiàn)[10]算法對這四個(gè)標(biāo)簽進(jìn)行識別，其通訊量和交互次數(shù)與新算法的對比如表6所示。

表6 算例交互次數(shù)和通訊數(shù)據(jù)量對比表

新算法引入預(yù)處理機(jī)制后，識別四個(gè)標(biāo)簽的交互次數(shù)為5，和改進(jìn)前相比沒有提高。有效通訊量為52 bit，較文獻(xiàn)[9]算法的83 bit有較大程度下降，較文獻(xiàn)[10]算法的64 bit也有一定程度下降。文獻(xiàn)[10]雖然都引入了預(yù)處理機(jī)制，但本文進(jìn)一步降低了交互次數(shù)，因此整體有效通訊量進(jìn)一步降低了。本案例標(biāo)簽長度較短，僅為8位，閱讀器接收有效數(shù)據(jù)量沒有明顯優(yōu)勢，隨著標(biāo)簽長度的增長，效果將更加顯著（詳細(xì)對比參見圖2）。

4 算法仿真與分析

文獻(xiàn)[10]算法簡化了閱讀器的指令，使其只發(fā)送碰撞位信息，這樣可以減少閱讀器發(fā)送的數(shù)據(jù)量。采用免激活指令，減少了交互次數(shù)。文獻(xiàn)[9]算法雖然閱讀器接收的數(shù)據(jù)量減少了，但是閱讀器本身接收的數(shù)據(jù)包含著非碰撞位信息，仍存在一定的冗余。本文算法，在此基礎(chǔ)上加入了預(yù)處理機(jī)制，即在進(jìn)行常規(guī)識別前，所有標(biāo)簽先發(fā)送數(shù)據(jù)給閱讀器，閱讀器識別所有標(biāo)簽碰撞位并將這些碰撞位組織成新的標(biāo)簽數(shù)據(jù)。而且在識別過程中能有效記錄接收到的既定信息，盡量避免數(shù)據(jù)的重復(fù)發(fā)送和接收，并通過狀態(tài)標(biāo)志對不同指令的變化進(jìn)一步減少交互次數(shù)，從而進(jìn)一步減少了通訊量。

用Java進(jìn)行算法的模擬仿真，仿真參數(shù)如表7所示。隨機(jī)產(chǎn)生長度為64 bit的若干標(biāo)簽，分別采用基本二進(jìn)制、動(dòng)態(tài)二進(jìn)制、返回式二進(jìn)制、文獻(xiàn)[9]算法和文獻(xiàn)[10]算法對標(biāo)簽進(jìn)行識別，識別不同數(shù)量的標(biāo)簽時(shí)幾種算法在有效通訊量上的對比，如圖2所示。

表7 仿真參數(shù)列表

圖2 幾種算法識別不同數(shù)量標(biāo)簽的通訊量對比

從圖2對比數(shù)據(jù)可以看出，改進(jìn)算法在有效通訊數(shù)據(jù)量上有較大優(yōu)勢。假設(shè)標(biāo)簽長度為L，待識別標(biāo)簽數(shù)目為N，存在M個(gè)碰撞位，考慮最復(fù)雜情況下，即碰撞標(biāo)簽數(shù)目最大的情況，即N=2M。

在通訊數(shù)據(jù)量方面，基本二進(jìn)制通訊量為：

本文借鑒了文獻(xiàn)[9]中部分思想，因此，先對原算法進(jìn)行討論。通常情況下，文獻(xiàn)[9]算法對于非沖突部分，即L-M位的處理，當(dāng)其全部位于第一個(gè)沖突位前端時(shí)，其重復(fù)發(fā)送次數(shù)最少，每個(gè)標(biāo)簽只發(fā)送一次，共N次。當(dāng)其全部位于最后一個(gè)沖突位后端時(shí)，其重復(fù)發(fā)送次數(shù)最多，發(fā)送次數(shù)為MN次。

當(dāng)其位于沖突位中間時(shí)，其平均發(fā)送次數(shù)為(M+1)N/2，共(L-M)(M+1)N/2位。

改進(jìn)后的二進(jìn)制，對于非沖突部分，即L-M位，其重復(fù)發(fā)送次數(shù)最少，每個(gè)標(biāo)簽只發(fā)送一次，共N次，即(L-M)N位，這也是新算法通訊量減少的主要原因。

改進(jìn)算法的預(yù)處理階段，對于M個(gè)沖突位，K=lbM-1+1，標(biāo)簽發(fā)送數(shù)據(jù)K+LN位。

對于預(yù)處理之后的識別過程：閱讀器N-2次發(fā)送指令，每次指令長度為K，則共發(fā)送K(N-2)=K(2M-2)位。

動(dòng)態(tài)返回二進(jìn)制約為返回二進(jìn)制的1/2，故改進(jìn)二進(jìn)制通訊數(shù)據(jù)量與動(dòng)態(tài)返回二進(jìn)制的通訊量之比約為：

同樣加入預(yù)處理過程，本文與文獻(xiàn)[10]的主要區(qū)別在閱讀器接收的有效數(shù)據(jù)和交互次數(shù)上。除去預(yù)處理過程，同樣考慮最壞情況下，即每位存在沖突且N=2M，文獻(xiàn)[10]閱讀器接收的數(shù)據(jù)量近似為本文算法的2倍；文獻(xiàn)[10]交互次數(shù)為2(2M-1)，每次指令長度為K+1，則共發(fā)送2(2M-1)(K+1)位，較本文算法交互次數(shù)多出1倍。

隨著標(biāo)簽數(shù)量不斷增加，引入預(yù)處理機(jī)制的新算法在通訊量上較其他算法仍有較大程度的提高。

當(dāng)標(biāo)簽碰撞位不連續(xù)時(shí)，新算法性能提升尤其顯著。同樣設(shè)定標(biāo)簽長度為128 bit，當(dāng)碰撞位占標(biāo)簽總長度的25%時(shí)，本文算法與文獻(xiàn)[9]算法、文獻(xiàn)[10]算法的傳送數(shù)據(jù)對比如圖3所示。其中通訊量統(tǒng)計(jì)均為閱讀器發(fā)送指令數(shù)據(jù)+閱讀器接收數(shù)據(jù)，文獻(xiàn)[10]和本文算法則又加入了預(yù)處理過程的通訊量。由此可見本文算法在通訊量上的性能提升，如果忽略預(yù)處理過程，本文算法優(yōu)勢將更加明顯。

在交互次數(shù)上，由于采用的搜索策略都是基于返回式二進(jìn)制的棧式操作，改進(jìn)程度不大，故在這方面較文獻(xiàn)[9]性能提升不明顯。圖4進(jìn)一步探討了標(biāo)簽碰撞位沖突率，即碰撞位占總數(shù)據(jù)位數(shù)比例對通訊數(shù)據(jù)量的影響。當(dāng)標(biāo)簽長度為128 bit，數(shù)量為70時(shí)，文獻(xiàn)[9]算法、文獻(xiàn)[10]算法的通訊數(shù)據(jù)量和本文算法對比，碰撞位占20%以下時(shí)，本文算法通訊量減少最為明顯，且隨著碰撞位數(shù)的減少，通訊量隨之快速減少。

圖3 碰撞位沖突率為25%時(shí)各算法通訊量對比

總之，本文算法經(jīng)仿真驗(yàn)證，其在標(biāo)簽數(shù)據(jù)不發(fā)生完全碰撞，且碰撞位不連續(xù)時(shí)，通訊量減少的效果尤其顯著。在文獻(xiàn)[9]算法中，每次都需要對標(biāo)簽未發(fā)送的數(shù)據(jù)進(jìn)行搜索，如果碰撞位不連續(xù)，則會(huì)將非碰撞位信息一并發(fā)送，而加入預(yù)處理操作后，每次只發(fā)送碰撞位信息，減少了非碰撞位傳送的開銷，再加上對交互指令的有效減少，整體通訊量大大降低。由此可見，在標(biāo)簽碰撞位不連續(xù)且碰撞位少于標(biāo)簽總比特位數(shù)一定比例的情況下，本文算法的通訊量有很大程度的減少。

5 結(jié)束語

對幾種基本防碰撞算法的原理進(jìn)行了研究，并進(jìn)行了實(shí)例驗(yàn)證，針對閱讀器和標(biāo)簽之間通訊數(shù)據(jù)量存在冗余的情況進(jìn)行了重點(diǎn)研究。通過加入信息預(yù)處理和閱讀器只接收有效標(biāo)簽數(shù)據(jù)的機(jī)制，對文獻(xiàn)[9-10]多狀態(tài)二進(jìn)制算法進(jìn)行了改進(jìn)。本文算法在標(biāo)簽識別過程中只處理沖突位信息，并對識別過程進(jìn)行了簡化，既減少了交互次數(shù)又減少了閱讀器每次接收標(biāo)簽數(shù)據(jù)的數(shù)量，使過程通訊量大大減少。模擬仿真結(jié)果表明，本文算法在標(biāo)簽各數(shù)據(jù)位不完全碰撞，且碰撞位不連續(xù)的情況，降低通訊量的效果尤其明顯，結(jié)合生產(chǎn)生活實(shí)際，提出的算法具有較大應(yīng)用價(jià)值。

圖4 通訊量和標(biāo)簽碰撞位沖突率的關(guān)系

[1]李世煜，馮全源.分層深度搜索樹型RFID防碰撞算法設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（11）：82-84.

[2]Hush D R，Wood C.Analysis of tree algorithms for RFID arbitration[C]//Proceedings of the IEEE International Symposium on Information Theory，1998：107.

[3]Law C，Lee K，Siu K Y.Efficient memory less protocol for tag identification[C]//Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications，Lyons，2000，4：75-84．

[4]Leong K S，Ng M L，Grasso A R.Synchronization of RFID readers for dense RFID reader environments[C]//Proceedings of the International Symposium on Applications and the Internet Workshops，2006：295-298．

[5]He Mingxing，Hong Shijin，F(xiàn)an Pingzhi，et al.A fast RFID tag identification algorithmbased on counter and stack[J].Expert Systems with Applications，2011，38：6829-6838.

[6]Vogt H.Multiple object identification with passive RFID[C]// Proceedings of the IEEE International Conference on Tags Systems，Man and Cybernetics，2002：6-9.

[7]余松森，詹宜巨，彭衛(wèi)東，等.基于后退式索引的二進(jìn)制樹形搜索反碰撞算法及其實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（16）：26-28.

[8]李興鶴，胡詠梅，王華蓮，等.基于動(dòng)態(tài)二進(jìn)制的二叉樹搜索結(jié)構(gòu)RFID反碰撞算法[J].山東科學(xué)，2006，19（2）：51-55.

[9]江岸，武繼雄，黃生葉，等.改進(jìn)的RFID二進(jìn)制搜索防碰撞算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（5）：229-231.

[10]吳躍前，辜大光，范振粵，等.RFID系統(tǒng)防碰撞算法比較分析及其改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（3）：210-213.

[11]蕭耀友，胡鋼，魏欽偉，等.基于二進(jìn)制樹分解的動(dòng)態(tài)防碰撞算法[J].通信技術(shù)，2011，44（1）：99-101.

[12]向垂益，何怡剛，李兵，等.動(dòng)態(tài)二進(jìn)制樹搜索算法的改進(jìn)[J].計(jì)算機(jī)工程，2010，36（2）：260-262.

[13]陳沖，徐志，何明華.一種新的RFID防碰撞算法的研究[J].福州大學(xué)學(xué)報(bào)，2009，37（3）：367-371.

[14]孫文勝，劉婷.一種改進(jìn)的基于二叉樹搜索的防碰撞算法[J].計(jì)算機(jī)工程，2011，37（10）：257-259.

ZHOU Yancong1，3,HE Min2,GU Junhua2,DONG Yongfeng2

1.School of Electrical Engineering,Hebei University of Technology,Tianjin 300130,China
2.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China
3.School of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China

As there is redundant communication data in multi-state binary algorithm of anti-collision,information preprocessing and partly receive mechanisms are introduced for algorithm improvements.Only the collision information is dealing with in the identification process,and reader only receives part data from tags,avoiding data sent and

repeatedly.Different instructions make state flags self-change,thus the interaction times and the communication data are reduced greatly.Simulation for the algorithm is done in Java.The results show that the new algorithm has obvious advantages in reducing the communication data when the collision bits are not continuous,and collision rate is lower 25%.Excluding the information pretreatment,the new algorithm has more significant advantage at any collision rate.

anti-collision;radio frequency identification;pretreatment mechanism;multi-state binary;dynamic binary

針對多狀態(tài)二進(jìn)制防碰撞算法通訊數(shù)據(jù)存在冗余的情況，引入信息預(yù)處理與閱讀器部分接收機(jī)制。在識別過程只處理沖突位，閱讀器只接收并記錄標(biāo)簽部分?jǐn)?shù)據(jù)，盡量避免數(shù)據(jù)重復(fù)發(fā)送與接收，狀態(tài)標(biāo)志根據(jù)不同指令做變化，減少交互次數(shù)，從而降低通訊數(shù)據(jù)量。采用Java進(jìn)行算法模擬仿真，結(jié)果表明，在碰撞位不連續(xù)，碰撞位沖突率低于25%時(shí)，算法在減少通訊量方面，具有明顯優(yōu)勢。若不計(jì)入預(yù)處理過程，該算法在任何碰撞位沖突率下通訊數(shù)據(jù)量都有較大優(yōu)勢。

防碰撞；射頻識別；預(yù)處理機(jī)制；多狀態(tài)二進(jìn)制；動(dòng)態(tài)二進(jìn)制

A

TP301.6

10.3778/j.issn.1002-8331.1112-0652

ZHOU Yancong,HE Min,GU Junhua,et al.Improvement of multi-state binary anti-collision algorithm introduced information pretreatment.Computer Engineering and Applications,2013,49（19）：204-209.

河北省自然科學(xué)基金應(yīng)用基礎(chǔ)（No.F2010000142）；天津市自然科學(xué)基金（No.12JCZDJC21200）。

周艷聰（1978—），女，博士研究生，講師，研究方向?yàn)閿?shù)據(jù)挖掘，智能信息處理，物流優(yōu)化；何敏（1987—），女，碩士研究生，研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)；顧軍華，男，教授，博士生導(dǎo)師，研究方向?yàn)橹悄苄畔⑻幚砼c軟計(jì)算，圖像處理；董永峰（1977—），男，博士，副教授，研究方向?yàn)閿?shù)據(jù)挖掘。E-mail：zycong78@126.com

2012-01-09

2012-03-31

1002-8331（2013）19-0204-06

CNKI出版日期：2012-05-21http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1137.002.html