高玉珍　孟祥敏

摘要：通過對RFID系統(tǒng)的防碰撞問題的分析，設(shè)計了一種改進的防碰撞算法——改進型查詢樹算法。此算法充分運用閱讀器接收到的信息中第一位碰撞位信息，閱讀器根據(jù)收到的碰撞位信息的不同去分解相應(yīng)的標簽組。此算法在通信負載和識別速度等方面相對于查詢樹算法和碰撞樹算法均有明顯的提高。

關(guān)鍵詞. RFID 防碰撞算法 改進 查詢樹

1算法描述

改進型查詢樹算法，它應(yīng)用在電子標簽編碼連續(xù)的場合中有較好的識別效率。此算法是在查詢樹算法和碰撞樹算法的基礎(chǔ)上實現(xiàn)的改進算法，它汲取了碰撞樹算法中用第一個碰撞位分解標簽組的思想，使得實現(xiàn)過程略過了不少步驟，使用效率和性能得到了較高。

改進型查詢樹算法的實現(xiàn)對標簽的制作工藝相對較高，需要在標簽中設(shè)置兩個計算器，兩個計算器分別是狀態(tài)計算器sc和指針計算器PC。其中，狀態(tài)計算器是用來記錄標簽分組信息的，即滿足sc等于0的標簽就可以“回答”閱讀器的查詢，指針計算器用于記錄標簽序列號的位置信息，此位置信息是標簽中與閱讀器發(fā)送的查詢位進行比較的位置信息。在辨認過程中的閱讀器部分，閱讀器中需要有一個保存待發(fā)送查詢序列數(shù)據(jù)信息的容器，并且要求這個容器還必須具有“后進先出”的特點，因此就想到了堆棧，此時在閱讀器端增加一個堆棧。

在改進型查詢樹算法中定義一個查詢過程包含三個階段的時間，分別是閱讀器發(fā)送查詢“指示”階段、標簽“回答”階段、閱讀器發(fā)送“應(yīng)答”信息階段。對應(yīng)到改進型查詢樹算法中，在RFID系統(tǒng)中識別一組標簽的過程，共可能存在“成功辨認”時間、“擁擠碰撞”時間和“不認識空閑”時間三種類型的查詢時間。

2改進型查詢樹算法工作流程

通過上述的理論分析，下面將對改進型查詢樹算法的工作流程進行描述。

（1）閱讀器操作：

初始階段：系統(tǒng)開始工作后，閱讀器發(fā)送一個初始命令，此命令是對閱讀器和其工作識別范圍內(nèi)的待識別標簽進行相關(guān)的初始工作。閱讀器的堆棧數(shù)據(jù)信息被初始置為“O”和“l(fā)”，同時將標簽內(nèi)的狀態(tài)計算器sc和指針計算器PC的值均置為O，狀態(tài)計算器的值sc為O表明所有的標簽都處于“激活”狀態(tài)，都有可能響應(yīng)閱讀器的查詢操作;指針計算器的值PC為0表示在初始階段指針計算器指向標簽序列號的最高位，隨著信息識別的推進，PC的值將逐步向后推進，其值也越來越大。實現(xiàn)過程分別有以下三種情況。

“成功辨認”：在工作范圍內(nèi)只有一個標簽“回答”此次查詢指示。

“擁擠碰撞”：在這種狀態(tài)下，出現(xiàn)了兩個或兩個以上的標簽“回答”了該查詢，標簽出現(xiàn)了碰撞情況。

“不認識空閑”：在這個階段內(nèi)沒有標簽“回答”該閱讀器的查詢。在此情況下，閱讀器直接發(fā)送應(yīng)答信息給工作范圍內(nèi)的標簽，同時再次用當前的查詢位進行查詢，這樣直接進入下一個碰撞過程。

（2）標簽操作：

工作在閱讀器范圍內(nèi)的標簽在接收到閱讀器的查詢指示后，標簽將根據(jù)兩個計算器的值來判斷是否要“回答”閱讀器的此次查詢，這兩個計算器分別是狀態(tài)計算器sC的值和指針計算器PC。當狀態(tài)計算器sc的值等于O時存在以下兩類情況：第一種是指針計算器所指的標簽信息位與閱讀器發(fā)送的指令數(shù)據(jù)位相同，則標簽就被成功識別;第二種情況是PC所指的數(shù)據(jù)位與閱讀器的指令數(shù)據(jù)位不相同，此時標簽不響應(yīng)閱讀器的訪問，接著所有標簽等待閱讀器的“應(yīng)答”信息。

閱讀器發(fā)出的“應(yīng)答”信息是用來告知所有電子標簽本次查詢結(jié)果的，同樣也是存在著三個階段。

3算法實例

通過一個例子說明改進型查詢樹算法的應(yīng)用過程。首先，設(shè)無線射頻RFID系統(tǒng)閱讀器的工作范圍內(nèi)有4個標簽，它們的數(shù)據(jù)信息是：1100、1110、0010和0001。在表1—1中列舉了改進型查詢樹算法識別4個標簽的流程，其中，在表格中盡量簡化操作，省略了閱讀器的初始化操作，同時查詢位指的是前綴序列中的末位，同時對標簽收到閱讀器的“應(yīng)答”信息之后的操作也進行了簡化，讓第一輪操作的結(jié)果直接反應(yīng)在下一次的標簽狀態(tài)中。

第一輪查詢過程，所有電子標簽都處于激活狀態(tài)，因此其狀態(tài)計算器SC的值均為0。在這種狀態(tài)下，與閱讀器前綴序列查詢位相同的標簽響應(yīng)，也就是前兩個標簽回答閱讀器指令;后面兩個標簽1100和1110與閱讀器的前綴序列查詢位不相同，因此這兩個標簽不“回答”，同時將其狀態(tài)計算器sc值增l，此時這兩個標簽等待。

閱讀器的此時收到的信息出現(xiàn)了碰撞，為OOX，可以判斷標簽發(fā)生了“擁擠碰撞”，此時閱讀器產(chǎn)生兩個新的前綴序列000和001并同時將這兩個前綴序列壓人堆棧中，然后閱讀器向工作在其范圍的標簽發(fā)送擁擠“應(yīng)答”信號碰撞信息。此時，工作在其范圍內(nèi)的標簽在接收到此信息后，接著執(zhí)行響應(yīng)的狀態(tài)調(diào)整，將其指針計算器Pointer值變?yōu)?，等待閱讀器下一輪的查詢過程。

第二輪查詢過程，用閱讀器一位數(shù)據(jù)信息進行查詢，這一位信息來自于堆棧，并且這個堆棧是在上一輪查詢過程中形成的新堆棧。后面兩個標簽不做出任何反應(yīng)，還是處于等待狀態(tài)，處于等待狀態(tài)的標簽直接將sc值增加1，也就是在上一輪的基礎(chǔ)上現(xiàn)在的數(shù)據(jù)變成了2，;前面兩個標簽處于活動狀態(tài)，此時又出現(xiàn)了“碰撞”，只有一個標簽0001“回答”，閱讀器能夠正確辨認一個標簽，其標簽序列號為000+1，也就是0001。閱讀器正確辨認標簽0001后，隨即發(fā)送“應(yīng)答”信息給其他標簽，其他標簽接收到此信息后，將其自身的狀態(tài)計算器sc的值減l，隨機將標簽0001置為“沉默”狀態(tài)，標簽0010的狀態(tài)計算器sc=0，又一次回到激活狀態(tài)，其余兩個標簽還是處于等待狀態(tài)。

第三輪查詢，這一輪查詢過程，標簽0010被激活并并且與閱讀器查詢位的最后一位相同，因此此時標簽0010被識別;標簽1100和標簽1110處于原來的等待狀態(tài)沒有改變。

以后的查詢過程與前幾次類似，可以從表I-I看出，用改進型查詢樹算法成功識別4個標簽所需要的時間階段。在現(xiàn)實應(yīng)用場景中，對于出現(xiàn)大多前綴序列相同的情況的識別效果相對會好得多。此算法在通信負載和識別速度等方面相對于查詢樹算法和碰撞樹算法均有明顯的提高，對無線射頻信號的識別有較大的實踐意義。

參考文獻

[1]郭雨齊，錢志鴻，白曦源，劉淼，一種RFID閱讀器的列表式讀取方式研究[J]. 哈爾濱工業(yè)大學(xué)學(xué)報，2012，44（11）： 96-100.

[2]李秉璋，景征駿，羅燁，基于后退式二進制的RFID防碰撞搜索算法[J].計算機應(yīng)用與軟件，2009，26（12）：96—98

[3]中華人民共和國科學(xué)技術(shù)部等十五部委.2015年物聯(lián)網(wǎng)白皮書：全球物聯(lián)網(wǎng)正在進入發(fā)展新階段，2015.