基于四叉樹的改進型RFID防碰撞算法

0引言

RFID（RadioFrequencyIdentification）即射頻識別技術的英文縮寫，它利用射頻信號通過空間耦合（交變磁場或電磁場）在閱讀器和電子標簽之間實現(xiàn)無接觸的信息傳遞，并通過所傳遞的信息達到自動識別的目的。作為物聯(lián)網感知層中的一種主要技術，RFID目前已經在物流、倉儲、交通等諸多領域廣泛使用。但是，在一個閱讀器的識別范圍內如果有多個標簽存在，當這些標簽同時向閱讀器傳遞信息時，閱讀器就會檢測到沖突，這稱之為“碰撞”，從而造成標簽識別失敗。為了解決這個問題，各種防碰撞算法被提了出來。

目前的RFID防碰撞算法主要分為兩大類:基于ALOHA的算法和基于樹的算法?；贏LOHA的算法運用了時分多址的思想，標簽隨機選擇一個時隙發(fā)送信息，若發(fā)生碰撞則隨機延遲一段時間再重發(fā)。這種算法由于對標簽讀取時間的不確定性，容易出現(xiàn)標簽長時間不被閱讀器讀取的“餓死”現(xiàn)象?；跇涞乃惴ú捎幂喸兊乃枷?，按照二進制組合規(guī)律,運用樹的遍歷算法對所有可能性進行捜索，直到識別出正確的數(shù)據。這種算法的標簽讀取時間是確定的，可以有效解決電子標簽的“餓死”現(xiàn)象。但由于它對每種可能性都進行遍歷,會導致讀取標簽的時延較長，標簽數(shù)量較多時，算法的效率會明顯降低。

在基于樹的防碰撞算法的基礎上，本文提出了一種基于四叉樹的改進型RFID防碰撞算法，通過改進四叉樹的結構，降低標簽識別時間，提高了識別效率。

1基于樹的防碰撞算法

樹是一種重要的非線性數(shù)據結構，它主要由結點和分枝組成。結點即樹中的每一個數(shù)據元素，除根結點和葉子結點外每個結點都有父結點和子結點；分枝即指向其子結點的分支。基于樹的防碰撞算法需要對標簽的ID按照一定的長度進行分組，當分組長度為1時，即為二叉樹算法；當分組長度為2時,即為四叉樹算法;當分組長度為3時，即為八叉樹算法……依此類推。在RFID系統(tǒng)中應用最廣泛的是二叉樹算法，它的基本原理是：閱讀器給標簽發(fā)送一個比特的查詢碼Q（0或1，相當于形成兩個子樹，先查詢0子樹，再查詢1子樹），在閱讀器響應范圍內的每一個標簽判斷自己的ID是否以Q開頭,若是則將自己的ID傳送給閱讀器。這時，有可能會出現(xiàn)三種情況：識別（僅有一個標簽以Q開頭）、碰撞（有兩個或兩個以上標簽以Q開頭）、空閑（無標簽以Q開頭）。若發(fā)生碰撞，則在前一個查詢碼后分別加上0和1,形成兩個新查詢碼（相當于分裂成左右兩個子樹）。先發(fā)送末尾加上0的新查詢碼給標簽，查詢左子樹;再發(fā)送末尾加上1的新查詢碼給標簽,查詢右子樹。在查詢過程中如果再次發(fā)生了碰撞，則重復上述操作，直到成功識別出全部標簽為止。假設有三個標簽,其ID分別為：0101、0110、1010,若采用二叉樹防碰撞算法,其識別過程如圖1所示。

由以上識別過程可以看出，在基于樹的防碰撞算法中,整個樹的結點可分為四種：初始結點、識別結點、碰撞結點和空閑結點。初始結點有且僅有一個，識別結點的數(shù)量與標簽數(shù)量相等，這兩種結點的數(shù)量是確定的。因此，要提高識別效率,關鍵是想辦法減少碰撞結點和空閑結點的數(shù)量。

在基于樹的RFID防碰撞算法中除了應用二叉樹外，多叉樹在很多場合也有實際應用，如四叉樹。四叉樹中標簽分組長度為2,結點編碼共有四種組合：00、01、10、11。同樣是如前所述的三個標簽：0101、0110、1010,采用四叉樹算法的識別過程如圖2所示。

將四叉樹和二叉樹識別過程作對比可以發(fā)現(xiàn)，四叉樹的碰撞結點較少，空閑結點較多。若能通過對四叉樹的結構進行改進，減少甚至去除空閑結點，將大大提高識別效率。

2基于四叉樹的改進型防碰撞算法

基于四叉樹的改進型防碰撞算法主要通過引入分組重編碼的機制，改進生成樹的結構，去除空閑時隙，縮短識別時間,從而提高識別效率。整個算法主要由兩部分組成：分組重編碼和標簽識別。

2.1分組重編碼

該算法首先要對標簽的原始ID碼進行分組，將原始ID碼從最高位到最低位每兩位分成一組，最后一組不足兩位則補0。這樣，每一組的兩位ID就有四種組合：00、01、10、11，對應于四叉樹的四個分支。

下來再對這四種組合的兩位分組ID碼重新進行編碼，用新的編碼來替換兩位分組ID碼，重編碼的規(guī)則如表1所列。

從表1可以看出，用來替換兩位分組ID碼的新編碼最大長度4位，最小長度1位，平均長度2.5位，比原分組ID碼的2位略有增加。新編碼有一個顯著的特點：最高位為1,低位全部為0。之所以采用這種編碼規(guī)則，目的是使閱讀器在識別過程中有更好的區(qū)分度，利用碰撞發(fā)生的位置就可以直接判斷出參與碰撞的標簽的替換編碼。

以上的分組重編碼操作均由標簽完成，因此要求標簽要具有存儲和生成替換編碼的能力。

2.2標簽識別

在識別過程中，電子標簽可能處于以下三種狀態(tài):

激活狀態(tài)

當閱讀器對響應范圍內的標簽發(fā)送初始化命令時，所有標簽進入激活狀態(tài)；另外，當標簽的編碼與閱讀器發(fā)送的請求編碼一致時，該標簽也將處于激活狀態(tài)。

安靜狀態(tài)

當標簽的編碼與閱讀器當前發(fā)出的請求編碼不同時，該標簽將暫時退出通信連接，進入到安靜狀態(tài)，等待下一次被激活。

休眠狀態(tài)

當一個標簽已經被識別出來，它將進入到休眠狀態(tài)，之后的通信過程不再進行任何響應，一直到整個識別過程全部結束。

具體識別過程如下：

閱讀器向進入自己響應范圍內的所有標簽發(fā)送初始化命令，并令分組序號”=0。

處于激活狀態(tài)的標簽進行響應。若閱讀器檢測到未發(fā)生碰撞，則成功識別，轉(4)；若發(fā)生碰撞，則標簽令分組序號n=n+1,并發(fā)送其第n組替換編碼。

閱讀器接收到標簽發(fā)來的替換編碼，通過識別替換編碼中碰撞發(fā)生的位置和數(shù)量，判斷出響應范圍內標簽的替換編碼的具體值，并將其和n值一起壓入堆棧s中。

閱讀器判斷堆棧s是否為空，不為空則轉(5),為空則轉(6)。

堆棧s頂部編碼和n值出棧，閱讀器發(fā)送棧頂編碼來請求標簽，轉(2)。

所有標簽識別完畢。

識別過程中指定四種替換編碼的壓棧順序為：1000、100、10、1。

2.3算法舉例

假設在閱讀器響應范圍內有6個待識別的電子標簽，其原始ID分別為:標簽a:01101101、標簽b:11000110、標簽c:10011100、標簽d:11001011、標簽e：01001011、標簽f:10101101,則各標簽的原始ID經過分組重編碼后對應的替換編碼如表2所列。

由上表可知，識別上述6個標簽閱讀器共需進行11次查詢，若直接采用傳統(tǒng)的四叉樹算法則需要進行20次查詢，可見改進型算法對于標簽識別效率的提高非常顯著。

3性能分析與仿真

閱讀器完成響應范圍內所有電子標簽的識別工作所花費的時間一般用時隙數(shù)作為單位，它是衡量防碰撞算法性能的重要標準之一，時隙數(shù)越少的算法性能越優(yōu)越。因此，接下來用數(shù)學分析的方法推導出基于四叉樹的改進型防碰撞算法的總時隙數(shù)值，并與二叉樹、四叉樹算法一起進行比較和仿真。

3.1數(shù)學分析

四叉樹算法的碰撞時隙數(shù)、空閑時隙數(shù)、識別時隙數(shù)和總時隙數(shù)(均為期望值)分別為：

基于四叉樹的改進型算法，由識別過程可知，其碰撞時隙數(shù)與傳統(tǒng)四叉樹算法相同，并且通過對標簽的原始ID編碼分組(兩位一組)后重新編碼，實現(xiàn)了在識別標簽的過程中將空閑時隙數(shù)降為0的目的。其捜索樹的結構優(yōu)化為一種無空閑結點的四叉樹，相比傳統(tǒng)的四叉樹算法，貝崎:

3.2算法仿真

接下來對上述的數(shù)學分析用Matlab進行模擬仿真。

圖3顯示了二叉樹算法、傳統(tǒng)四叉樹算法和改進型四叉樹算法等三種算法的碰撞時隙對比?？梢钥闯?，在同等數(shù)量的標簽情況下，改進型四叉樹算法和傳統(tǒng)四叉樹算法的碰撞時隙數(shù)相等，且它們都比二叉樹算法的碰撞時隙數(shù)少得多。

圖3三種算法的碰撞時隙數(shù)對比仿真圖

圖4所示是三種算法的空間時隙數(shù)對比仿真圖。通過圖4可以看出，傳統(tǒng)四叉樹算法的空閑時隙數(shù)比二叉樹算法的空閑時隙數(shù)要多，但改進型四叉樹算法通過引入分組重編碼機制，改進了四叉樹的結構，從而徹底消除了空閑時隙。

圖5所示是三種算法的總時隙數(shù)仿真對比圖，通過仿真

結果可知，改進型四叉樹算法的總時隙數(shù)比二叉樹和傳統(tǒng)四叉樹算法的總時隙數(shù)要少，約為二叉樹和傳統(tǒng)四叉樹算法的60%左右。并且，標簽數(shù)量越大，這種差距就越明顯。

圖4三種算法的空閑時隙數(shù)對比仿真圖

圖5三種算法的總時隙數(shù)對比仿真圖

通過以上的數(shù)學分析和仿真說明基于四叉樹的改進型RFID防碰撞算法的標簽識別性能要明顯優(yōu)于其它兩種算法,其識別效率更高。

4結語

基于四叉樹的改進型RFID防碰撞算法通過對標簽的原始ID碼采取分組重編碼的手段，優(yōu)化了生成樹的結構，消除了空閑時隙，大大提高了標簽的識別效率。通過數(shù)學分析和算法仿真，進一步證明了在同等數(shù)目的標簽情況下，該算法的識別時間要明顯低于傳統(tǒng)的二叉樹和四叉樹算法，并且隨著標簽數(shù)目的增多，這種優(yōu)勢就更加明顯。因此，該算法對于解決標簽密集環(huán)境下的RFID防碰撞問題具有一定的實際意義。

20211221_61c1aa86f10c2__基于四叉樹的改進型RFID防碰撞算法