增強型混合樹RFID防碰撞算法研究

周偉輝

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

關鍵詞 RFID；二叉樹；四叉樹；混合樹；防碰撞算法

中圖分類號 TP3 文獻標識碼 A 文章編號 1674-6708（2018）216-0148-02

1 EHT算法分析與實現步驟

1.1 EHT算法設計思想

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

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

1.2 EHT算法流程

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

EHT算法流程如下：

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

2）閱讀檢測碰撞位，并將碰撞位信息存入堆棧中，即執行POP（q）命令，并發送該命令，相應的標簽會響應。

3）閱讀器根據響應的標簽數判斷子樹的時隙狀態，會發生以下3種情況之一：

（1）如果子樹上有且僅有一個標簽響應，則該子樹的時隙為成功時隙，即該標簽識別成功，將其轉換為休眠狀態，跳轉至（5）。

（2）如果無標簽響應在該子樹的時隙上，說明該子樹的時隙為空閑時隙，跳轉至（5）。

（3）若有兩個及兩個以上的標簽響應，則該子樹的時隙為碰撞時隙，跳轉至（4）。

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

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

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

5）判斷堆棧是否為空，如果不為空，則跳轉至（2）；如果為空，則算法結束。

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

2 實驗仿真與分析

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

仿真實驗一：總時隙數對比

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

仿真實驗二：碰撞時隙數對比

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

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

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

3 結論

本文針對基于樹的算法識別時間長，識別過程中會產生大量空閑時隙而降低識別效率的不足，提出了一種增強型混合樹防碰撞（EHT）算法。在識別過程中根據響應的標簽數動態選擇二叉樹、三叉樹和四叉樹，完全可以避免空閑時隙的產生。仿真結果表明，EHT算法可以減少在識別過程所耗總時隙數和碰撞時隙數，并且在提高算法識別效率的同時將其穩定地維持在0.65左右，因此EHT算法適合在需要快速讀取大量標簽的場合，能夠實現快速準確的識別所有標簽。