一種改進的防碰撞算法的設計與實現

高玉珍　孟祥敏

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

關鍵詞. RFID 防碰撞算法 改進 查詢樹

1算法描述

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

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

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

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

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

（1）閱讀器操作：

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

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

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

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

（2）標簽操作：

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

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

3算法實例

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

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

閱讀器的此時收到的信息出現了碰撞，為OOX，可以判斷標簽發生了“擁擠碰撞”，此時閱讀器產生兩個新的前綴序列000和001并同時將這兩個前綴序列壓人堆棧中，然后閱讀器向工作在其范圍的標簽發送擁擠“應答”信號碰撞信息。此時，工作在其范圍內的標簽在接收到此信息后，接著執行響應的狀態調整，將其指針計算器Pointer值變為2，等待閱讀器下一輪的查詢過程。

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

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

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

參考文獻

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

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

[3]中華人民共和國科學技術部等十五部委.2015年物聯網白皮書：全球物聯網正在進入發展新階段，2015.