快速自適應(yīng)多叉樹(shù)防碰撞算法的研究

侯加兵，呂家云，霍文強(qiáng)

（巢湖學(xué)院，安徽 合肥 238000）

1 概述

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，無(wú)線射頻技術(shù)（Radio Frequency Identification，RFID）[1]因具有非接觸性、快速方便、可靠性等特點(diǎn)，被公認(rèn)為物聯(lián)網(wǎng)識(shí)別的關(guān)鍵技術(shù)，已廣泛應(yīng)用于各個(gè)領(lǐng)域.中心機(jī)房作為信息基礎(chǔ)設(shè)施的核心區(qū)域，為信息化的安全、可靠、穩(wěn)定的運(yùn)行保駕護(hù)航，因此，針對(duì)中心機(jī)房關(guān)鍵設(shè)備的全方位實(shí)時(shí)監(jiān)測(cè)顯得尤為重要，RFID技術(shù)因其自身的特點(diǎn)可滿足需求.RFID通常有閱讀器和標(biāo)簽組成，在機(jī)房環(huán)境下，因需對(duì)多個(gè)設(shè)備進(jìn)行監(jiān)測(cè)，就出現(xiàn)RFID閱讀器同時(shí)讀取多個(gè)標(biāo)簽，這樣會(huì)出現(xiàn)信號(hào)碰撞現(xiàn)象，如何實(shí)現(xiàn)RFID對(duì)機(jī)房關(guān)鍵設(shè)備實(shí)時(shí)監(jiān)測(cè)，既要閱讀器同時(shí)讀取多個(gè)標(biāo)簽又要保證數(shù)據(jù)實(shí)時(shí)傳輸，對(duì)RFID的防碰撞算法提出更高的要求.

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

為滿足機(jī)房實(shí)時(shí)監(jiān)測(cè)的要求，重點(diǎn)對(duì)標(biāo)簽防碰撞算法進(jìn)行研究，本文在自適應(yīng)多叉樹(shù)算法基礎(chǔ)上，提出一種快速自適應(yīng)多叉樹(shù)（Fast Adaptive Multi-Tree Search，F(xiàn)AMS）防碰撞算法.該算法在防碰撞之前先對(duì)標(biāo)簽數(shù)進(jìn)行估計(jì)，根據(jù)實(shí)際環(huán)境進(jìn)行多叉樹(shù)快速處理.

2 快速自適應(yīng)多叉樹(shù)防碰撞算法原理

有源標(biāo)簽顯著地提高了RFID系統(tǒng)通信距離，在一定范圍內(nèi)閱讀器與多個(gè)待識(shí)別標(biāo)簽同時(shí)通信時(shí)，很有可能就會(huì)產(chǎn)生標(biāo)簽碰撞.在中心機(jī)房環(huán)境的實(shí)際應(yīng)用中，需要RFID系統(tǒng)對(duì)中心機(jī)房的關(guān)鍵設(shè)備進(jìn)行全天候監(jiān)控和管理，這就對(duì)RFID提出了更高的響應(yīng)需求[8].

根據(jù)標(biāo)簽特征，標(biāo)簽的長(zhǎng)度一般是固定的，每個(gè)位（BIT）出現(xiàn)概率基本相同，標(biāo)簽越多出現(xiàn)的碰撞的概率越大，以快速先驗(yàn)作為標(biāo)簽估計(jì)的條件，可以快速避免標(biāo)簽碰撞，提高RFID安全性能.具體算法描述如下：

定義1標(biāo)簽參數(shù)為Sum（t），若將一天分成若干個(gè)t時(shí)段，該時(shí)間段的標(biāo)簽數(shù)量為Sum（t），并對(duì)該標(biāo)簽數(shù)據(jù)保存作為初始搜索依據(jù)，在完成所有標(biāo)簽識(shí)別之后，將根據(jù)識(shí)別的標(biāo)簽數(shù)I（t）進(jìn)行更新，即：

其中，Sum’（t）為更新后的標(biāo)簽數(shù)量；β∈[0，1]為更新率，其值的大小根據(jù)RFID系統(tǒng)標(biāo)簽訪問(wèn)的規(guī)律性來(lái)確定.一般標(biāo)簽數(shù)量變化不大時(shí)，β就越小，相反，則越大.

定義2碰撞因子U=NC/N，U∈[0，1]，Nc表示碰撞比特?cái)?shù)，N表示比特?cái)?shù).其值越大，說(shuō)明碰撞標(biāo)簽越多，反之，則碰撞標(biāo)簽越少.根據(jù)碰撞因子，可以估計(jì)在時(shí)隙X中，發(fā)生碰撞的標(biāo)簽數(shù)C（x）滿足：

由于標(biāo)簽長(zhǎng)度在一定的范圍內(nèi)，若碰撞標(biāo)簽數(shù)量較多時(shí)，U=1，C(x)無(wú)解，則無(wú)法進(jìn)行標(biāo)簽估計(jì)，可采用標(biāo)簽隨機(jī)分布特性進(jìn)行標(biāo)簽估計(jì).

定義3根據(jù)多叉樹(shù)搜索公式得到[9][10]，若時(shí)隙為x，搜索深度為H（x），那么時(shí)隙節(jié)點(diǎn)數(shù)則為2H(X)，第m時(shí)隙內(nèi)的標(biāo)簽數(shù)為：

依據(jù)該算法，在初始狀態(tài)下，無(wú)法估計(jì)標(biāo)簽數(shù)量時(shí)，可通過(guò)Sum(t)進(jìn)行標(biāo)簽估計(jì)并確定多叉樹(shù)的叉數(shù).在執(zhí)行搜索算法時(shí)，若是碰撞時(shí)隙，利用碰撞因子U進(jìn)行標(biāo)簽估計(jì)，若標(biāo)簽因子過(guò)大（U=1），則通過(guò)標(biāo)簽的隨機(jī)分布特性進(jìn)行標(biāo)簽估計(jì)，完成對(duì)標(biāo)簽的搜索和識(shí)別.

3 算法性能分析

在機(jī)房環(huán)境通過(guò)RFID技術(shù)對(duì)關(guān)鍵設(shè)備的監(jiān)控和管理，對(duì)于RFID技術(shù)本身來(lái)說(shuō)主要是要可靠地保證監(jiān)測(cè)數(shù)據(jù)穩(wěn)定性傳輸[11]，本文主要通過(guò)計(jì)算總時(shí)隙數(shù)和吞吐率，對(duì)FAMS算法進(jìn)行分析.

假設(shè)系統(tǒng)內(nèi)有Nc個(gè)待識(shí)別的標(biāo)簽，此時(shí)時(shí)段參考標(biāo)簽數(shù)為Sum(t)，標(biāo)簽估計(jì)準(zhǔn)確率為

為使RFID系統(tǒng)具有最大的吞吐率，搜索叉數(shù)L應(yīng)與標(biāo)簽數(shù)Nc一致.

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

下面通過(guò)Matlab驗(yàn)證本算法的模擬效果，標(biāo)簽數(shù)量隨機(jī)產(chǎn)生，長(zhǎng)度為128bit，仿真結(jié)果取相同條件下100次實(shí)驗(yàn)的平均值，見(jiàn)圖1、圖2.

圖1 時(shí)隙數(shù)

圖2 吞吐率

通過(guò)仿真數(shù)據(jù)顯示，標(biāo)簽總數(shù)在100以內(nèi)時(shí)，時(shí)隙數(shù)較小，吞吐率較大，標(biāo)簽總數(shù)超過(guò)100以后，則時(shí)隙數(shù)快速增大，吞吐率也出現(xiàn)明顯下降，實(shí)驗(yàn)結(jié)論得出在標(biāo)簽總數(shù)100以內(nèi)，本算法性能較好.中心機(jī)房的關(guān)鍵設(shè)備一般指核心交換機(jī)、路由設(shè)備、UPS、精密空調(diào)、重要服務(wù)器和存儲(chǔ)設(shè)備，數(shù)量基本上不超過(guò)30臺(tái)，本算法很好地滿足機(jī)房環(huán)境監(jiān)測(cè)需求.

5 結(jié)束語(yǔ)

本文利用機(jī)房標(biāo)簽讀寫(xiě)頻率和標(biāo)簽數(shù)量相對(duì)固定的環(huán)境下，采用標(biāo)簽快速搜索技術(shù)，結(jié)合標(biāo)簽分布的先驗(yàn)知識(shí)和碰撞規(guī)律，提出一種基于快速自適應(yīng)的多叉樹(shù)防碰撞算法.該算法通過(guò)快速生成樹(shù)算法準(zhǔn)確地估計(jì)標(biāo)簽數(shù)量，能夠快速、方便、準(zhǔn)確地防標(biāo)簽碰撞，使得RFID閱讀器能夠穩(wěn)定、高效地搜索和識(shí)別標(biāo)簽，能夠滿足RFID技術(shù)對(duì)機(jī)房關(guān)鍵設(shè)備全生期周期的需要[12].文中通過(guò)理論分析、仿真驗(yàn)證，證明采用FASM算法的RFID適應(yīng)于智能機(jī)房場(chǎng)景的需要.