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

1、    一種改進(jìn)的防碰撞算法的設(shè)計(jì)與實(shí)現(xiàn)    高玉珍孟祥敏摘要：通過(guò)對(duì)rfid系統(tǒng)的防碰撞問(wèn)題的分析，設(shè)計(jì)了一種改進(jìn)的防碰撞算法改進(jìn)型查詢樹(shù)算法。此算法充分運(yùn)用閱讀器接收到的信息中第一位碰撞位信息，閱讀器根據(jù)收到的碰撞位信息的不同去分解相應(yīng)的標(biāo)簽組。此算法在通信負(fù)載和識(shí)別速度等方面相對(duì)于查詢樹(shù)算法和碰撞樹(shù)算法均有明顯的提高。關(guān)鍵詞. rfid 防碰撞算法 改進(jìn) 查詢樹(shù)1算法描述改進(jìn)型查詢樹(shù)算法，它應(yīng)用在電子標(biāo)簽編碼連續(xù)的場(chǎng)合中有較好的識(shí)別效率。此算法是在查詢樹(shù)算法和碰撞樹(shù)算法的基礎(chǔ)上實(shí)現(xiàn)的改進(jìn)算法，它汲取了碰撞樹(shù)算法中用第一個(gè)碰撞位分解標(biāo)簽組的思想，使

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

3、讀器發(fā)送查詢“指示”階段、標(biāo)簽“回答”階段、閱讀器發(fā)送“應(yīng)答”信息階段。對(duì)應(yīng)到改進(jìn)型查詢樹(shù)算法中，在rfid系統(tǒng)中識(shí)別一組標(biāo)簽的過(guò)程，共可能存在“成功辨認(rèn)”時(shí)間、“擁擠碰撞”時(shí)間和“不認(rèn)識(shí)空閑”時(shí)間三種類型的查詢時(shí)間。2改進(jìn)型查詢樹(shù)算法工作流程通過(guò)上述的理論分析，下面將對(duì)改進(jìn)型查詢樹(shù)算法的工作流程進(jìn)行描述。（1）閱讀器操作：初始階段：系統(tǒng)開(kāi)始工作后，閱讀器發(fā)送一個(gè)初始命令，此命令是對(duì)閱讀器和其工作識(shí)別范圍內(nèi)的待識(shí)別標(biāo)簽進(jìn)行相關(guān)的初始工作。閱讀器的堆棧數(shù)據(jù)信息被初始置為“o”和“l(fā)”，同時(shí)將標(biāo)簽內(nèi)的狀態(tài)計(jì)算器sc和指針計(jì)算器pc的值均置為o，狀態(tài)計(jì)算器的值sc為o表明所有的標(biāo)簽都處于“激活”狀態(tài)

4、，都有可能響應(yīng)閱讀器的查詢操作;指針計(jì)算器的值pc為0表示在初始階段指針計(jì)算器指向標(biāo)簽序列號(hào)的最高位，隨著信息識(shí)別的推進(jìn)，pc的值將逐步向后推進(jìn)，其值也越來(lái)越大。實(shí)現(xiàn)過(guò)程分別有以下三種情況?！俺晒Ρ嬲J(rèn)”：在工作范圍內(nèi)只有一個(gè)標(biāo)簽“回答”此次查詢指示。“擁擠碰撞”：在這種狀態(tài)下，出現(xiàn)了兩個(gè)或兩個(gè)以上的標(biāo)簽“回答”了該查詢，標(biāo)簽出現(xiàn)了碰撞情況。“不認(rèn)識(shí)空閑”：在這個(gè)階段內(nèi)沒(méi)有標(biāo)簽“回答”該閱讀器的查詢。在此情況下，閱讀器直接發(fā)送應(yīng)答信息給工作范圍內(nèi)的標(biāo)簽，同時(shí)再次用當(dāng)前的查詢位進(jìn)行查詢，這樣直接進(jìn)入下一個(gè)碰撞過(guò)程。（2）標(biāo)簽操作：工作在閱讀器范圍內(nèi)的標(biāo)簽在接收到閱讀器的查詢指示后，標(biāo)簽將根據(jù)兩個(gè)計(jì)

5、算器的值來(lái)判斷是否要“回答”閱讀器的此次查詢，這兩個(gè)計(jì)算器分別是狀態(tài)計(jì)算器sc的值和指針計(jì)算器pc。當(dāng)狀態(tài)計(jì)算器sc的值等于o時(shí)存在以下兩類情況：第一種是指針計(jì)算器所指的標(biāo)簽信息位與閱讀器發(fā)送的指令數(shù)據(jù)位相同，則標(biāo)簽就被成功識(shí)別;第二種情況是pc所指的數(shù)據(jù)位與閱讀器的指令數(shù)據(jù)位不相同，此時(shí)標(biāo)簽不響應(yīng)閱讀器的訪問(wèn)，接著所有標(biāo)簽等待閱讀器的“應(yīng)答”信息。閱讀器發(fā)出的“應(yīng)答”信息是用來(lái)告知所有電子標(biāo)簽本次查詢結(jié)果的，同樣也是存在著三個(gè)階段。3算法實(shí)例通過(guò)一個(gè)例子說(shuō)明改進(jìn)型查詢樹(shù)算法的應(yīng)用過(guò)程。首先，設(shè)無(wú)線射頻rfid系統(tǒng)閱讀器的工作范圍內(nèi)有4個(gè)標(biāo)簽，它們的數(shù)據(jù)信息是：1100、1110、0010和0

6、001。在表11中列舉了改進(jìn)型查詢樹(shù)算法識(shí)別4個(gè)標(biāo)簽的流程，其中，在表格中盡量簡(jiǎn)化操作，省略了閱讀器的初始化操作，同時(shí)查詢位指的是前綴序列中的末位，同時(shí)對(duì)標(biāo)簽收到閱讀器的“應(yīng)答”信息之后的操作也進(jìn)行了簡(jiǎn)化，讓第一輪操作的結(jié)果直接反應(yīng)在下一次的標(biāo)簽狀態(tài)中。第一輪查詢過(guò)程，所有電子標(biāo)簽都處于激活狀態(tài)，因此其狀態(tài)計(jì)算器sc的值均為0。在這種狀態(tài)下，與閱讀器前綴序列查詢位相同的標(biāo)簽響應(yīng)，也就是前兩個(gè)標(biāo)簽回答閱讀器指令;后面兩個(gè)標(biāo)簽1100和1110與閱讀器的前綴序列查詢位不相同，因此這兩個(gè)標(biāo)簽不“回答”，同時(shí)將其狀態(tài)計(jì)算器sc值增l，此時(shí)這兩個(gè)標(biāo)簽等待。閱讀器的此時(shí)收到的信息出現(xiàn)了碰撞，為oox，可以

7、判斷標(biāo)簽發(fā)生了“擁擠碰撞”，此時(shí)閱讀器產(chǎn)生兩個(gè)新的前綴序列000和001并同時(shí)將這兩個(gè)前綴序列壓人堆棧中，然后閱讀器向工作在其范圍的標(biāo)簽發(fā)送擁擠“應(yīng)答”信號(hào)碰撞信息。此時(shí)，工作在其范圍內(nèi)的標(biāo)簽在接收到此信息后，接著執(zhí)行響應(yīng)的狀態(tài)調(diào)整，將其指針計(jì)算器pointer值變?yōu)?，等待閱讀器下一輪的查詢過(guò)程。第二輪查詢過(guò)程，用閱讀器一位數(shù)據(jù)信息進(jìn)行查詢，這一位信息來(lái)自于堆棧，并且這個(gè)堆棧是在上一輪查詢過(guò)程中形成的新堆棧。后面兩個(gè)標(biāo)簽不做出任何反應(yīng)，還是處于等待狀態(tài)，處于等待狀態(tài)的標(biāo)簽直接將sc值增加1，也就是在上一輪的基礎(chǔ)上現(xiàn)在的數(shù)據(jù)變成了2，;前面兩個(gè)標(biāo)簽處于活動(dòng)狀態(tài)，此時(shí)又出現(xiàn)了“碰撞”，只有一個(gè)標(biāo)

8、簽0001“回答”，閱讀器能夠正確辨認(rèn)一個(gè)標(biāo)簽，其標(biāo)簽序列號(hào)為000+1，也就是0001。閱讀器正確辨認(rèn)標(biāo)簽0001后，隨即發(fā)送“應(yīng)答”信息給其他標(biāo)簽，其他標(biāo)簽接收到此信息后，將其自身的狀態(tài)計(jì)算器sc的值減l，隨機(jī)將標(biāo)簽0001置為“沉默”狀態(tài)，標(biāo)簽0010的狀態(tài)計(jì)算器sc=0，又一次回到激活狀態(tài)，其余兩個(gè)標(biāo)簽還是處于等待狀態(tài)。第三輪查詢，這一輪查詢過(guò)程，標(biāo)簽0010被激活并并且與閱讀器查詢位的最后一位相同，因此此時(shí)標(biāo)簽0010被識(shí)別;標(biāo)簽1100和標(biāo)簽1110處于原來(lái)的等待狀態(tài)沒(méi)有改變。以后的查詢過(guò)程與前幾次類似，可以從表i-i看出，用改進(jìn)型查詢樹(shù)算法成功識(shí)別4個(gè)標(biāo)簽所需要的時(shí)間階段。在現(xiàn)實(shí)應(yīng)用場(chǎng)景中，對(duì)于出現(xiàn)大多前綴序列相同的情況的識(shí)別效果相對(duì)會(huì)好得多。此算法在通信負(fù)載和識(shí)別速度等方面相對(duì)于查詢樹(shù)算法和碰撞樹(shù)算法均有明顯的提高，對(duì)無(wú)線射頻信號(hào)的識(shí)別有較大的實(shí)踐意義。參考文獻(xiàn)1郭雨齊，錢(qián)志鴻，白曦源，劉淼，一種rfid閱讀器的列表式讀取方式研究j. 哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2012，44（