增強(qiáng)型混合樹(shù)RFID防碰撞算法研究

周偉輝

摘 要 為了解決現(xiàn)階段RFID技術(shù)中存在的多標(biāo)簽碰撞問(wèn)題。針對(duì)二叉樹(shù)算法識(shí)別時(shí)間長(zhǎng)，四叉樹(shù)算法產(chǎn)生大量空閑時(shí)隙而降低識(shí)別效率的不足，提出了一種增強(qiáng)型混合樹(shù)防碰撞（EHT）算法。該算法根據(jù)待識(shí)別標(biāo)簽數(shù)目來(lái)動(dòng)態(tài)選擇基于樹(shù)的算法，從而縮短識(shí)別時(shí)間，提高識(shí)別效率和減少所耗總時(shí)隙數(shù)。仿真結(jié)果表明，當(dāng)待識(shí)別標(biāo)簽總數(shù)超過(guò)1 000時(shí)，EHT算法的識(shí)別效率仍能維持在65%以上，所耗總時(shí)隙數(shù)為1 500個(gè)左右。因此EHT算法可以很好地解決多標(biāo)簽碰撞問(wèn)題，并在大規(guī)模標(biāo)簽識(shí)別場(chǎng)合中具有良好的應(yīng)用前景。

關(guān)鍵詞 RFID；二叉樹(shù)；四叉樹(shù)；混合樹(shù)；防碰撞算法

中圖分類(lèi)號(hào) TP3 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1674-6708（2018）216-0148-02

1 EHT算法分析與實(shí)現(xiàn)步驟

1.1 EHT算法設(shè)計(jì)思想

文章針對(duì)基于樹(shù)的算法識(shí)別時(shí)間長(zhǎng)，識(shí)別過(guò)程中會(huì)產(chǎn)生大量空閑時(shí)隙而降低識(shí)別效率的不足，提出了一種增強(qiáng)型混合樹(shù)防碰撞（Enhanced hybrid tree， EHT）算法。在識(shí)別過(guò)程中根據(jù)響應(yīng)的標(biāo)簽數(shù)動(dòng)態(tài)選擇二叉樹(shù)、三叉樹(shù)和四叉樹(shù)，共有7個(gè)待識(shí)別標(biāo)簽數(shù)，第一輪識(shí)別中采用四叉樹(shù)算法識(shí)別一個(gè)標(biāo)簽，產(chǎn)生兩個(gè)碰撞時(shí)隙，第二輪識(shí)別成功識(shí)別三個(gè)標(biāo)簽，第三輪識(shí)別成功識(shí)別一個(gè)標(biāo)簽，產(chǎn)生一個(gè)碰撞標(biāo)簽，最后一輪成功識(shí)別全部標(biāo)簽，總共搜索查詢了4次，只產(chǎn)生一個(gè)空閑時(shí)隙，可以得出混合樹(shù)算法能夠減少搜索查詢次數(shù)從而縮短識(shí)別時(shí)間，同時(shí)能減少空閑時(shí)隙從而太高識(shí)別效率。

EHT算法是基于樹(shù)的算法的改進(jìn)，通過(guò)標(biāo)簽的碰撞位來(lái)進(jìn)行碰撞標(biāo)簽的分組，當(dāng)有且僅有一個(gè)最高碰撞位時(shí)，采用二叉樹(shù)算法，將最高碰撞位為“0”的標(biāo)簽分組到左子樹(shù)，將最高碰撞位為“1”的標(biāo)簽分組到右子樹(shù)；當(dāng)有最高碰撞位和次高碰撞位連續(xù)時(shí)，采用四叉樹(shù)算法，從左到右依次存放的是碰撞位為“00”“01”“10”“11”的標(biāo)簽；若最高碰撞位和次高碰撞位連續(xù)但碰撞位“00”“01”“10”“11”不全部存在時(shí)，動(dòng)態(tài)選擇二叉樹(shù)或三叉樹(shù)進(jìn)行識(shí)別，這樣可以避免空閑時(shí)隙的產(chǎn)生，可以保證無(wú)空閑時(shí)隙。

1.2 EHT算法流程

在EHT算法中，用堆棧來(lái)保存每次碰撞標(biāo)簽的碰撞位信息，并不斷重復(fù)更新碰撞位信息，直到堆棧為空，算法結(jié)束。

EHT算法流程如下：

1）閱讀器發(fā)送Request（？）命令給所有待識(shí)別的標(biāo)簽，？一開(kāi)始為全“1”，這樣可以保證一開(kāi)始所有標(biāo)簽都能響應(yīng)。

2）閱讀檢測(cè)碰撞位，并將碰撞位信息存入堆棧中，即執(zhí)行POP（q）命令，并發(fā)送該命令，相應(yīng)的標(biāo)簽會(huì)響應(yīng)。

3）閱讀器根據(jù)響應(yīng)的標(biāo)簽數(shù)判斷子樹(shù)的時(shí)隙狀態(tài)，會(huì)發(fā)生以下3種情況之一：

（1）如果子樹(shù)上有且僅有一個(gè)標(biāo)簽響應(yīng)，則該子樹(shù)的時(shí)隙為成功時(shí)隙，即該標(biāo)簽識(shí)別成功，將其轉(zhuǎn)換為休眠狀態(tài)，跳轉(zhuǎn)至（5）。

（2）如果無(wú)標(biāo)簽響應(yīng)在該子樹(shù)的時(shí)隙上，說(shuō)明該子樹(shù)的時(shí)隙為空閑時(shí)隙，跳轉(zhuǎn)至（5）。

（3）若有兩個(gè)及兩個(gè)以上的標(biāo)簽響應(yīng)，則該子樹(shù)的時(shí)隙為碰撞時(shí)隙，跳轉(zhuǎn)至（4）。

4）閱讀器檢測(cè)碰撞標(biāo)簽的碰撞位信息，此時(shí)會(huì)發(fā)生以下兩種情況之一：

（1）若閱讀器檢測(cè)出有且僅有一個(gè)最高碰撞位時(shí)，選擇二叉樹(shù)算法，并將碰撞信息存放在堆棧中，即執(zhí)行PUSH（0q，1q ）命令，跳轉(zhuǎn)至（2）。

（2）若閱讀器檢測(cè)到最高碰撞位和次高碰撞位連續(xù)時(shí)，選擇四叉樹(shù)算法，并將碰撞位存放在堆棧中，即執(zhí)行PUSH（××q）命令，跳轉(zhuǎn)至（2）。

5）判斷堆棧是否為空，如果不為空，則跳轉(zhuǎn)至（2）；如果為空，則算法結(jié)束。

EHT算法流程圖如圖1所示。

2 實(shí)驗(yàn)仿真與分析

在MATLAB平臺(tái)下編程進(jìn)行實(shí)驗(yàn)仿真，本文算法標(biāo)簽數(shù)的最大取值為1000個(gè)，標(biāo)簽編碼長(zhǎng)度為64位，仿真實(shí)驗(yàn)100次取其最后平均值，在理想的實(shí)驗(yàn)環(huán)境下，誤差率小于等于5%。將本文EHT算法與CT算法、AHT算法、ISE-BS算法作比較，分別進(jìn)行了三組仿真實(shí)驗(yàn)對(duì)比：總時(shí)隙數(shù)對(duì)比、碰撞時(shí)隙數(shù)對(duì)比、算法識(shí)別效率對(duì)比，仿真結(jié)果如圖2、3、4所示。

仿真實(shí)驗(yàn)一：總時(shí)隙數(shù)對(duì)比

從圖2可以看出本文EHT算法在識(shí)別標(biāo)簽過(guò)程中所耗總時(shí)隙數(shù)較其他三種算法要少很多，當(dāng)識(shí)別標(biāo)簽數(shù)達(dá)到1000個(gè)左右時(shí)，EHT算法所耗總時(shí)隙數(shù)為1200個(gè)左右，而CT算法超過(guò)了2000個(gè)，這也能說(shuō)明EHT算法的優(yōu)越性。而分析其原因是因?yàn)镋HT算法在識(shí)別標(biāo)簽過(guò)程中不會(huì)產(chǎn)生空閑時(shí)隙，而CT算法和AHT算法會(huì)產(chǎn)生空閑時(shí)隙，這樣就增加了總時(shí)隙數(shù)。

仿真實(shí)驗(yàn)二：碰撞時(shí)隙數(shù)對(duì)比

圖3為各算法的碰撞時(shí)隙數(shù)比較，可以看出EHT算法在碰撞時(shí)隙數(shù)上與ISE-BS算法和AHT算法基本相近，但比CT算法減少了很多，這是因?yàn)镃T算法利用的純二叉樹(shù)算法來(lái)進(jìn)行識(shí)別標(biāo)簽，當(dāng)代識(shí)別標(biāo)簽數(shù)增大是，碰撞產(chǎn)生的概率大大增加，從而產(chǎn)生了大量的碰撞時(shí)隙數(shù)。

仿真實(shí)驗(yàn)三：識(shí)別效率對(duì)比

識(shí)別效率作為衡量算法的好與壞的一個(gè)重要指標(biāo)，識(shí)別效率高的算法更優(yōu)。圖4為各算法識(shí)別效率對(duì)比，可以得到，EHT算法識(shí)別效率是最高的，即使標(biāo)簽數(shù)目達(dá)到1 000時(shí)，仍可以穩(wěn)定的保持在65%左右，從而可以得出本文提出的EHT算法性能比其他三種算法更高，能夠高效解決大量標(biāo)簽碰撞問(wèn)題。

3 結(jié)論

本文針對(duì)基于樹(shù)的算法識(shí)別時(shí)間長(zhǎng)，識(shí)別過(guò)程中會(huì)產(chǎn)生大量空閑時(shí)隙而降低識(shí)別效率的不足，提出了一種增強(qiáng)型混合樹(shù)防碰撞（EHT）算法。在識(shí)別過(guò)程中根據(jù)響應(yīng)的標(biāo)簽數(shù)動(dòng)態(tài)選擇二叉樹(shù)、三叉樹(shù)和四叉樹(shù)，完全可以避免空閑時(shí)隙的產(chǎn)生。仿真結(jié)果表明，EHT算法可以減少在識(shí)別過(guò)程所耗總時(shí)隙數(shù)和碰撞時(shí)隙數(shù)，并且在提高算法識(shí)別效率的同時(shí)將其穩(wěn)定地維持在0.65左右，因此EHT算法適合在需要快速讀取大量標(biāo)簽的場(chǎng)合，能夠?qū)崿F(xiàn)快速準(zhǔn)確的識(shí)別所有標(biāo)簽。