快速自適應多叉樹防碰撞算法的研究

侯加兵，呂家云，霍文強

（巢湖學院，安徽 合肥 238000）

1 概述

隨著物聯網技術的快速發展，無線射頻技術（Radio Frequency Identification，RFID）[1]因具有非接觸性、快速方便、可靠性等特點，被公認為物聯網識別的關鍵技術，已廣泛應用于各個領域.中心機房作為信息基礎設施的核心區域，為信息化的安全、可靠、穩定的運行保駕護航，因此，針對中心機房關鍵設備的全方位實時監測顯得尤為重要，RFID技術因其自身的特點可滿足需求.RFID通常有閱讀器和標簽組成，在機房環境下，因需對多個設備進行監測，就出現RFID閱讀器同時讀取多個標簽，這樣會出現信號碰撞現象，如何實現RFID對機房關鍵設備實時監測，既要閱讀器同時讀取多個標簽又要保證數據實時傳輸，對RFID的防碰撞算法提出更高的要求.

傳統的防碰撞算法主要分為兩類，一類是基于ALOHA的不確定算法，主要代表算法有時隙ALOHA、動態時隙ALOHA和幀時隙ALOHA算法等[2]；另一類是基于樹的確定算法，主要代表算法有二叉樹、動態叉樹、混合查詢樹等[3].ALOHA算法在多標簽的情況下，易出現“標簽饑餓”現象，而樹的算法則會產生很長的識別時延，研究人員通過研究分別提出了自適應多叉樹算法[4][5]、無空閑時隙的動態多叉樹查詢樹RFID防碰撞算法[6]和后位退鎖式RFID自適應多叉樹防碰撞算法[7]，這些算法快速識別標簽，減少標簽方面得到很大的改進，但還不能滿足機房關鍵設備實時監測數據的高速、安全、穩定性能要求.

為滿足機房實時監測的要求，重點對標簽防碰撞算法進行研究，本文在自適應多叉樹算法基礎上，提出一種快速自適應多叉樹（Fast Adaptive Multi-Tree Search，FAMS）防碰撞算法.該算法在防碰撞之前先對標簽數進行估計，根據實際環境進行多叉樹快速處理.

2 快速自適應多叉樹防碰撞算法原理

有源標簽顯著地提高了RFID系統通信距離，在一定范圍內閱讀器與多個待識別標簽同時通信時，很有可能就會產生標簽碰撞.在中心機房環境的實際應用中，需要RFID系統對中心機房的關鍵設備進行全天候監控和管理，這就對RFID提出了更高的響應需求[8].

根據標簽特征，標簽的長度一般是固定的，每個位（BIT）出現概率基本相同，標簽越多出現的碰撞的概率越大，以快速先驗作為標簽估計的條件，可以快速避免標簽碰撞，提高RFID安全性能.具體算法描述如下：

定義1標簽參數為Sum（t），若將一天分成若干個t時段，該時間段的標簽數量為Sum（t），并對該標簽數據保存作為初始搜索依據，在完成所有標簽識別之后，將根據識別的標簽數I（t）進行更新，即：

其中，Sum’（t）為更新后的標簽數量；β∈[0，1]為更新率，其值的大小根據RFID系統標簽訪問的規律性來確定.一般標簽數量變化不大時，β就越小，相反，則越大.

定義2碰撞因子U=NC/N，U∈[0，1]，Nc表示碰撞比特數，N表示比特數.其值越大，說明碰撞標簽越多，反之，則碰撞標簽越少.根據碰撞因子，可以估計在時隙X中，發生碰撞的標簽數C（x）滿足：

由于標簽長度在一定的范圍內，若碰撞標簽數量較多時，U=1，C(x)無解，則無法進行標簽估計，可采用標簽隨機分布特性進行標簽估計.

定義3根據多叉樹搜索公式得到[9][10]，若時隙為x，搜索深度為H（x），那么時隙節點數則為2H(X)，第m時隙內的標簽數為：

依據該算法，在初始狀態下，無法估計標簽數量時，可通過Sum(t)進行標簽估計并確定多叉樹的叉數.在執行搜索算法時，若是碰撞時隙，利用碰撞因子U進行標簽估計，若標簽因子過大（U=1），則通過標簽的隨機分布特性進行標簽估計，完成對標簽的搜索和識別.

3 算法性能分析

在機房環境通過RFID技術對關鍵設備的監控和管理，對于RFID技術本身來說主要是要可靠地保證監測數據穩定性傳輸[11]，本文主要通過計算總時隙數和吞吐率，對FAMS算法進行分析.

假設系統內有Nc個待識別的標簽，此時時段參考標簽數為Sum(t)，標簽估計準確率為

為使RFID系統具有最大的吞吐率，搜索叉數L應與標簽數Nc一致.

4 仿真實驗與分析

下面通過Matlab驗證本算法的模擬效果，標簽數量隨機產生，長度為128bit，仿真結果取相同條件下100次實驗的平均值，見圖1、圖2.

圖1 時隙數

圖2 吞吐率

通過仿真數據顯示，標簽總數在100以內時，時隙數較小，吞吐率較大，標簽總數超過100以后，則時隙數快速增大，吞吐率也出現明顯下降，實驗結論得出在標簽總數100以內，本算法性能較好.中心機房的關鍵設備一般指核心交換機、路由設備、UPS、精密空調、重要服務器和存儲設備，數量基本上不超過30臺，本算法很好地滿足機房環境監測需求.

5 結束語

本文利用機房標簽讀寫頻率和標簽數量相對固定的環境下，采用標簽快速搜索技術，結合標簽分布的先驗知識和碰撞規律，提出一種基于快速自適應的多叉樹防碰撞算法.該算法通過快速生成樹算法準確地估計標簽數量，能夠快速、方便、準確地防標簽碰撞，使得RFID閱讀器能夠穩定、高效地搜索和識別標簽，能夠滿足RFID技術對機房關鍵設備全生期周期的需要[12].文中通過理論分析、仿真驗證，證明采用FASM算法的RFID適應于智能機房場景的需要.