一種改進(jìn)的防碰撞算法的設(shè)計與實(shí)現(xiàn)

高玉珍　孟祥敏

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

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

1算法描述

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

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

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

2改進(jìn)型查詢樹算法工作流程

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

（1）閱讀器操作：

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

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

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

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

（2）標(biāo)簽操作：

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

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

3算法實(shí)例

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

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

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

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

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

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

參考文獻(xiàn)

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

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

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