基于碰撞樹的RFID多標(biāo)簽識別防碰撞算法研究.pdf

1、射頻識別(Radio Frequency Identification，RFID)技術(shù)是一種自動識別方法，它通過射頻電波對存儲在射頻標(biāo)簽芯片中的數(shù)據(jù)進(jìn)行無線讀取。RFID系統(tǒng)通常由閱讀器、標(biāo)簽、應(yīng)用系統(tǒng)構(gòu)成。典型的RFID閱讀器一般具有充足的存儲容量和計算能力。RFID標(biāo)簽卻存在很大的差異，從只能接收并響應(yīng)閱讀器命令的無源被動標(biāo)簽，到具有獨立的片上微控系統(tǒng)、存儲器、電源等的主動標(biāo)簽和智能標(biāo)簽。由于低成本、低能耗，無源被動標(biāo)簽越來越受到人

2、們的青睞，并被廣泛使用。
　　許多RFID應(yīng)用系統(tǒng)需要同時對多個射頻標(biāo)簽進(jìn)行識別和處理。當(dāng)多個標(biāo)簽或閱讀器同時在相同信道進(jìn)行信息傳輸?shù)臅r候，就會發(fā)生碰撞(collision)，增加系統(tǒng)通信開銷，延長數(shù)據(jù)交互時間，甚至導(dǎo)致RFID系統(tǒng)工作失效。因此，高效的防碰撞算法(anti-collision algorithm)，對于RFID多標(biāo)簽識別系統(tǒng)，特別是大規(guī)模RFID應(yīng)用系統(tǒng)，非常重要。RFID系統(tǒng)中碰撞可以分為標(biāo)簽碰撞(tag co

3、llision)和閱讀器碰撞(readercollision)。本論文主要研究和解決標(biāo)簽碰撞和防碰撞問題。
　　當(dāng)多個標(biāo)簽同時響應(yīng)閱讀器的查詢請求，它們發(fā)送的數(shù)據(jù)信號在信道中相互干擾，就會引發(fā)標(biāo)簽碰撞，致使閱讀器無法完成對這些標(biāo)簽的識別和數(shù)據(jù)采集。目前解決標(biāo)簽碰撞的防碰撞算法主要分為:基于ALOHA的時隙類算法，如:時隙ALOHA算法(S-ALOHA)、幀時隙ALOHA算法(FSA);基于樹搜索的樹型算法，如:查詢樹算法(QT)、

4、二進(jìn)制樹算法(BT)。幾乎所有已知防碰撞算法的識別效率都低于50％，這不能滿足實際生產(chǎn)應(yīng)用的需要。因此，提高多標(biāo)簽識別效率，打破多標(biāo)簽識別效率瓶頸，成為防碰撞算法研究的重要內(nèi)容和目標(biāo)。
　　同時，在防碰撞算法研究中，通常假設(shè)標(biāo)簽編號成均勻分布。事實上，均勻分布之外的其它分布模式，如連續(xù)分布、部分連續(xù)分布，在很多應(yīng)用場合使用更加頻繁，例如:集裝箱碼頭、大型貨倉、進(jìn)出口檢測等。因為，這些場合中，許多附著RFID標(biāo)簽的物品屬于同類物品，

5、它們通常來自同一地域的同一生產(chǎn)廠商。根據(jù)標(biāo)簽編號分配和使用原則，它們所使用標(biāo)簽的編號主要是連續(xù)分布。所以，類似這樣的分布模式，在防碰撞算法研究中應(yīng)當(dāng)給予充分的關(guān)注。
　　論文首先針對當(dāng)前防碰撞算法中存在的效率瓶頸問題，提出了一種高效的防碰撞算法，即碰撞樹算法(collision tree protocol，CT)。CT算法成功的打破了先前防碰撞算法的效率瓶頸，首次將多標(biāo)簽識別效率提高到50％以上。碰撞行為和碰撞位的處理是CT算法的

6、關(guān)鍵和核心。CT算法根據(jù)閱讀器檢測到的碰撞位信息，直接生成兩個新的前綴，同時將發(fā)生碰撞的標(biāo)簽組分為兩個組。以此，CT算法完全消除了多標(biāo)簽識別過程中可能存在的空周期(idle cycle)，大幅度提高了RFID多標(biāo)簽識別的性能。
　　論文同時建立了一種新的二叉樹結(jié)構(gòu)，即碰撞樹（collision tree），用于描述CT算法的多標(biāo)簽識別過程，分析CT算法的識別性能。根據(jù)碰撞樹的定義，碰撞樹的所有中間節(jié)點與CT算法的碰撞周期一一對應(yīng)，

7、碰撞樹的所有葉子節(jié)點與CT算法的可讀周期一一對應(yīng)。碰撞樹是一種滿二叉樹（full binary tree），碰撞樹中沒有空節(jié)點(idle node)。根據(jù)碰撞樹的性質(zhì)，可以簡單直接的計算和分析CT算法的識別性能。
　　CT算法的另一個重要優(yōu)勢在于其識別性能的穩(wěn)定性（stability）。穩(wěn)定性是論文提出的用于分析和評價防碰撞算法性能的一項新指標(biāo)。在流水生產(chǎn)、自動控制等許多RFID應(yīng)用系統(tǒng)中，標(biāo)簽識別算法的穩(wěn)定性具有非常重要的意義。

8、因為這些系統(tǒng)對標(biāo)簽的識別時間和系統(tǒng)能耗等具有較為嚴(yán)格或精確的定量控制要求。防碰撞算法的穩(wěn)定性是指算法的識別性能只與識別標(biāo)簽的數(shù)量有關(guān)，而不受其它因素的影響，同時，算法的平均識別性能趨于一個常數(shù)。理論分析和實驗結(jié)果均表明:CT算法是一個穩(wěn)定高效的RFID多標(biāo)簽識別防碰撞算法。由于CT算法簡單易于實現(xiàn)，能以較低的系統(tǒng)消耗，快速有效的完成RFID標(biāo)簽的識別，所以，CT算法能夠適用于各種RFID標(biāo)簽識別系統(tǒng)，解決標(biāo)簽碰撞問題。
　　由于C

9、T算法完全消除了防碰撞算法中可能存在的空周期，將多標(biāo)簽識別效率提高到50％以上，打破了防碰撞算法的效率瓶頸，并且具有嚴(yán)格的碰撞樹結(jié)構(gòu)對其進(jìn)行描述和分析，所以，CT算法開啟了基于碰撞樹的防碰撞算法系列，為后續(xù)防碰撞算法研究奠定了基礎(chǔ)。在CT算法基礎(chǔ)上，論文提出了兩種新的防碰撞算法:二元確定性碰撞樹算法(ICT)和雙響應(yīng)碰撞樹算法(BCT)。兩種算法的提出，進(jìn)一步完善了基于碰撞樹的防碰撞算法系列。
　　在ICT算法中，論文提出了二元確

10、定性原理，并將其用于RFID多標(biāo)簽識別過程，提高算法的識別性能。同時，標(biāo)簽編號連續(xù)分布模式和部分連續(xù)分布模式被納入了防碰撞算法的研究范疇。根據(jù)二元確定性原理，如果在閱讀器收到的標(biāo)簽響應(yīng)中，只有一位數(shù)據(jù)位發(fā)生碰撞時，ICT算法通過指派該碰撞位的值，就能在同一個查詢周期中同時識別到兩個標(biāo)簽，而無需繼續(xù)查詢。理論和實驗結(jié)果表明:當(dāng)標(biāo)簽編號連續(xù)分布時，ICT算法能將多標(biāo)簽識別效率提高到100％以上。因此，ICT算法特別適用于標(biāo)簽編號連續(xù)分布和部

11、分連續(xù)分布的RFID應(yīng)用場合。
　　在BCT算法中，論文提出了雙響應(yīng)機(jī)制，將標(biāo)簽響應(yīng)周期劃分為兩個子周期，使兩組標(biāo)簽?zāi)軌蛟趦蓚€響應(yīng)子周期中分別獨立地響應(yīng)閱讀器的查詢請求。通過這種方式，BCT算法進(jìn)一步提高了RFID系統(tǒng)多標(biāo)簽識別的性能。特別是在減少閱讀器的查詢次數(shù)，降低閱讀器和標(biāo)簽的通信數(shù)據(jù)量，以及降低系統(tǒng)能耗等方面，BCT算法具有明顯的優(yōu)勢。無論標(biāo)簽編號是均勻分布還是連續(xù)分布，BCT算法的識別效率均在100％以上。同CT算法和I