周偉輝

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

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

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

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

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

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

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

1.2 EHT算法流程

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

EHT算法流程如下：

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

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

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

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

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

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

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

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

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

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

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

2 實驗仿真與分析

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

仿真實驗一：總時隙數(shù)對比

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

仿真實驗二：碰撞時隙數(shù)對比

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

仿真實驗三：識別效率對比

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

3 結(jié)論

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