0引言

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

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

在基于樹(shù)的防碰撞算法的基礎(chǔ)上，本文提出了一種基于四叉樹(shù)的改進(jìn)型RFID防碰撞算法，通過(guò)改進(jìn)四叉樹(shù)的結(jié)構(gòu)，降低標(biāo)簽識(shí)別時(shí)間，提高了識(shí)別效率。

1基于樹(shù)的防碰撞算法

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

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

在基于樹(shù)的RFID防碰撞算法中除了應(yīng)用二叉樹(shù)外，多叉樹(shù)在很多場(chǎng)合也有實(shí)際應(yīng)用，如四叉樹(shù)。四叉樹(shù)中標(biāo)簽分組長(zhǎng)度為2,結(jié)點(diǎn)編碼共有四種組合：00、01、10、11。同樣是如前所述的三個(gè)標(biāo)簽：0101、0110、1010,采用四叉樹(shù)算法的識(shí)別過(guò)程如圖2所示。

將四叉樹(shù)和二叉樹(shù)識(shí)別過(guò)程作對(duì)比可以發(fā)現(xiàn)，四叉樹(shù)的碰撞結(jié)點(diǎn)較少，空閑結(jié)點(diǎn)較多。若能通過(guò)對(duì)四叉樹(shù)的結(jié)構(gòu)進(jìn)行改進(jìn)，減少甚至去除空閑結(jié)點(diǎn)，將大大提高識(shí)別效率。

2基于四叉樹(shù)的改進(jìn)型防碰撞算法

基于四叉樹(shù)的改進(jìn)型防碰撞算法主要通過(guò)引入分組重編碼的機(jī)制，改進(jìn)生成樹(shù)的結(jié)構(gòu)，去除空閑時(shí)隙，縮短識(shí)別時(shí)間,從而提高識(shí)別效率。整個(gè)算法主要由兩部分組成：分組重編碼和標(biāo)簽識(shí)別。

2.1分組重編碼

該算法首先要對(duì)標(biāo)簽的原始ID碼進(jìn)行分組，將原始ID碼從最高位到最低位每?jī)晌环殖梢唤M，最后一組不足兩位則補(bǔ)0。這樣，每一組的兩位ID就有四種組合：00、01、10、11，對(duì)應(yīng)于四叉樹(shù)的四個(gè)分支。

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

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

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

2.2標(biāo)簽識(shí)別

在識(shí)別過(guò)程中，電子標(biāo)簽可能處于以下三種狀態(tài):

激活狀態(tài)

當(dāng)閱讀器對(duì)響應(yīng)范圍內(nèi)的標(biāo)簽發(fā)送初始化命令時(shí)，所有標(biāo)簽進(jìn)入激活狀態(tài)；另外，當(dāng)標(biāo)簽的編碼與閱讀器發(fā)送的請(qǐng)求編碼一致時(shí)，該標(biāo)簽也將處于激活狀態(tài)。

安靜狀態(tài)

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

休眠狀態(tài)

當(dāng)一個(gè)標(biāo)簽已經(jīng)被識(shí)別出來(lái)，它將進(jìn)入到休眠狀態(tài)，之后的通信過(guò)程不再進(jìn)行任何響應(yīng)，一直到整個(gè)識(shí)別過(guò)程全部結(jié)束。

具體識(shí)別過(guò)程如下：

閱讀器向進(jìn)入自己響應(yīng)范圍內(nèi)的所有標(biāo)簽發(fā)送初始化命令，并令分組序號(hào)”=0。

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

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

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

堆棧s頂部編碼和n值出棧，閱讀器發(fā)送棧頂編碼來(lái)請(qǐng)求標(biāo)簽，轉(zhuǎn)(2)。

所有標(biāo)簽識(shí)別完畢。

識(shí)別過(guò)程中指定四種替換編碼的壓棧順序?yàn)椋?000、100、10、1。

2.3算法舉例

假設(shè)在閱讀器響應(yīng)范圍內(nèi)有6個(gè)待識(shí)別的電子標(biāo)簽，其原始ID分別為:標(biāo)簽a:01101101、標(biāo)簽b:11000110、標(biāo)簽c:10011100、標(biāo)簽d:11001011、標(biāo)簽e：01001011、標(biāo)簽f:10101101,則各標(biāo)簽的原始ID經(jīng)過(guò)分組重編碼后對(duì)應(yīng)的替換編碼如表2所列。

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

3性能分析與仿真

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

3.1數(shù)學(xué)分析

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

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

3.2算法仿真

接下來(lái)對(duì)上述的數(shù)學(xué)分析用Matlab進(jìn)行模擬仿真。

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

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

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

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

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

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

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

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

4結(jié)語(yǔ)

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

20211221_61c1aa86f10c2__基于四叉樹(shù)的改進(jìn)型RFID防碰撞算法