基于RFID防碰撞算法綜述

劉曉崗　宋高俊

摘要：無線射頻識別（Radio Frequency Identification，RFID）技術(shù)作為當(dāng)下最重要的科技之一，以其廣泛的應(yīng)用性將有越來越大的發(fā)展前景，RFID技術(shù)也由于其非接觸的特性，遇到了多目標(biāo)識別過程中的信息碰撞問題。現(xiàn)對Aloha類防碰撞算法、二進(jìn)制樹防碰撞算法以及改進(jìn)算法進(jìn)行分析。

關(guān)鍵詞：RFID；防碰撞算法；Aloha；二進(jìn)制樹

RFID系統(tǒng)在識別過程中會有一個普遍的問題，那就是對象沖突，當(dāng)在同一時間內(nèi)有若干個電子標(biāo)簽同時請求識別是，閱讀器不能正確區(qū)別出來，這樣當(dāng)多個電子標(biāo)簽同時發(fā)送數(shù)據(jù)的時候，就會出現(xiàn)數(shù)據(jù)的干擾導(dǎo)致數(shù)據(jù)傳輸失敗，這就是文章要研究的防碰撞問題。為了解決這一問題，提高系統(tǒng)的性能，需要制定有效的防碰撞算法，所以防碰撞算法是RFID系統(tǒng)的研究核心。

現(xiàn)有的防碰撞算法包括：Aloha類防碰撞算法，又稱為隨機性算法；二進(jìn)制樹防碰撞算法，又稱為確定性算法；改進(jìn)算法，在原有的基礎(chǔ)上設(shè)計出性能更優(yōu)的算法。

1基于Aloha類防碰撞算法

ALOHA（Additive Link On line Hawaii）算法算是出現(xiàn)比較早的防碰撞算法，它是采取隨機多址方式。作為無線通信協(xié)議，ALOHA算法研究取得成功后被廣泛利用。在理想狀態(tài)下，利用ALOHA類防碰撞算法，系統(tǒng)最高吞吐率是36.8%。但是在實際應(yīng)用中，由于各種因素的干擾，系統(tǒng)的識別效率很難達(dá)到理想的狀態(tài)。

1.1純Aloha算法

純ALOHA算法也叫基本ALOHA算法，是一種比較容易的時分多址算法。當(dāng)標(biāo)簽進(jìn)入閱讀器的工作范圍內(nèi)，標(biāo)簽獲取能量被激活，向閱讀器發(fā)送儲存在標(biāo)簽內(nèi)部的數(shù)據(jù)信息。在這個過程中，假如有兩個標(biāo)簽一同向閱讀器發(fā)送信息，就會產(chǎn)生信息沖突，造成完全碰撞；而當(dāng)一個標(biāo)簽正在向閱讀器發(fā)送過程中，另一個標(biāo)簽開始信息傳送，這種情況下就會出現(xiàn)標(biāo)簽部分碰撞。只有標(biāo)簽單獨在一個時間內(nèi)進(jìn)行信息傳輸時才能讓閱讀器正常識別，不會出現(xiàn)碰撞情況。使用純ALOHA算法，系統(tǒng)最大吞吐率只有18.4%，標(biāo)簽發(fā)生碰撞概率比能夠正確識別概率要大得多。

1.2時隙Aloha算法與幀時隙Aloha算法

由于ALOHA算法中，標(biāo)簽發(fā)送數(shù)據(jù)時間是隨機性的，導(dǎo)致完全碰撞或者部分碰撞。于是將純ALOHA算法進(jìn)行優(yōu)化，得到了時隙ALOHA算法。這種算法是把時間劃分成若干等長時隙（每個時隙長度滿足一個標(biāo)簽成功發(fā)送完數(shù)據(jù)），標(biāo)簽通過不同時隙向閱讀器發(fā)送數(shù)據(jù)，如此一來，就能避免部分碰撞的產(chǎn)生，從而總體上縮減了產(chǎn)生碰撞的次數(shù)。時隙Aloha算法采用分割時隙思想，避免了標(biāo)簽的部分碰撞，只有成功識別和完全碰撞情況，成倍地提高了信道利用率。但要劃分時隙就要解決一個同步問題，在系統(tǒng)中要有同步時鐘，使閱讀器作用范圍內(nèi)的所有標(biāo)簽達(dá)到時隙同步。該算法的系統(tǒng)吞吐率可達(dá)到36.8%，比純Aloha算法效果提高了一倍。

盡管時隙ALOHA算法在信道利用率上比純ALOHA算法得到一定改進(jìn)，可是標(biāo)簽發(fā)生碰撞的概率依然很大，發(fā)生碰撞后的標(biāo)簽會隨機接著發(fā)送數(shù)據(jù)，進(jìn)而影響其他標(biāo)簽的讀取，為了避免這種情況，于是研究出了幀時隙ALOHA算法。這種方法是把多個時隙組成一個幀，在每一個幀內(nèi)，標(biāo)簽任意選擇其中一個時隙發(fā)送數(shù)據(jù)，但只可以發(fā)送一次。在某一個時隙內(nèi)，當(dāng)標(biāo)簽發(fā)生了完全碰撞，將會處于休眠狀態(tài)，等到下一幀進(jìn)行讀取，這樣不會影響本幀內(nèi)其他標(biāo)簽的正常讀取。算法中每一幀的時隙數(shù)都是固定的，并且時隙長會大于一個標(biāo)簽成功發(fā)送完信息的時間。這樣，閱讀器發(fā)送讀取指令后，假如一個時隙內(nèi)僅有一個標(biāo)簽響應(yīng)，則成功讀取標(biāo)簽數(shù)據(jù)；如果時隙內(nèi)沒有一個標(biāo)簽，就會掠過此時隙；如果存在許多標(biāo)簽的話，產(chǎn)生了碰撞后自動等到下一幀的到來，再選擇其他時隙。

2基于二進(jìn)制樹防碰撞算法

二進(jìn)制樹防碰撞算法通過電子標(biāo)簽具有唯一的二進(jìn)制編碼來查詢區(qū)別。此算法工作原理是將產(chǎn)生了碰撞的電子標(biāo)簽分為0、1兩個子集，首先從子集0開始搜尋，要是沒有碰撞產(chǎn)生，說明成功識別。如果產(chǎn)生了碰撞，就將碰撞的標(biāo)簽再分成00與01兩個子集，再從00子集開始搜尋，重復(fù)執(zhí)行操作。0子集的標(biāo)簽完全成功識別后，轉(zhuǎn)向1子集搜尋，直至把全部標(biāo)簽都識別完，任務(wù)結(jié)束。

2.1二進(jìn)制搜索算法與動態(tài)二進(jìn)制搜索算法

與ALOHA類算法不同的是，使用二進(jìn)制搜索算法需要用到標(biāo)簽自身的序列號和閱讀器的查詢指令號。當(dāng)標(biāo)簽序列號與閱讀器查詢指令相同時，標(biāo)簽產(chǎn)生響應(yīng)。要是僅有一個標(biāo)簽做出響應(yīng)，那么成功識別。如果存在若干個標(biāo)簽一同做出響應(yīng)，閱讀器會根據(jù)碰撞位情況修正查詢指令，經(jīng)過不斷修正查詢命令來識別出所有標(biāo)簽。

動態(tài)二進(jìn)制搜索（DBS，Dynamic Binary Search）算法是對二進(jìn)制搜索算法進(jìn)行優(yōu)化的。使用二進(jìn)制搜索算法，整個標(biāo)簽序列號需要多次被傳輸，并且閱讀器發(fā)送的REQUEST指令數(shù)據(jù)位也多，從而會造成查詢時間增加，出錯頻率也跟著提高。動態(tài)二進(jìn)制搜索算法能很好減少數(shù)據(jù)位冗余，但是它的運行流程與二進(jìn)制搜索算法基本相同，只是修改了REQUEST指令。

2.2鎖位后退二進(jìn)制搜索算法與跳躍式動態(tài)二進(jìn)制搜算算法

鎖位后退二進(jìn)制搜索算法也是在二進(jìn)制搜索算法基礎(chǔ)上得到優(yōu)化的，雖然動態(tài)二進(jìn)制搜索算法能減少數(shù)據(jù)傳輸量，但是并不能減少搜索次數(shù)。鎖位后退二進(jìn)制搜索算法的工作原理是當(dāng)閱讀器成功識別出一個標(biāo)簽后，閱讀器不需要重新發(fā)送REQUEST指令，而是直接根據(jù)上一層的鎖位分組退回到上一層，也就是返回根節(jié)點，這樣顯然會減少搜索次數(shù)。

跳躍式動態(tài)二進(jìn)制搜索算法在動態(tài)二進(jìn)制搜索算法和鎖位后退算法的基礎(chǔ)上結(jié)合而成的，涵蓋了兩種算法的優(yōu)點，既減少了數(shù)據(jù)冗余位的發(fā)送，也減少了搜索次數(shù)，同時縮短了查詢時間，也提高了標(biāo)簽識別效率。

跳躍式搜索算法比二進(jìn)制搜索以及鎖位后退搜索需要的查詢次數(shù)少，比動態(tài)搜索算法數(shù)據(jù)傳輸量又少，整體性能相對來說是最好。

3改進(jìn)算法

為了使識別效率更好，不少學(xué)者在原有的基礎(chǔ)上，提出了新的改進(jìn)算法，有學(xué)者提出了優(yōu)化幀內(nèi)時隙長度的策略，并通過馬爾科夫建模實現(xiàn)對標(biāo)簽的讀取周期數(shù)達(dá)到減少的目的。同時，基于二進(jìn)制樹的防碰撞算法也有很多學(xué)者在研究，并且在其基礎(chǔ)上提出了不少改進(jìn)算法，如改進(jìn)的返回式動態(tài)二進(jìn)制算法、NTA算法、EMBT算法和二叉樹搜算算法等，相比之前的動態(tài)二進(jìn)制搜算算法，在平均比特數(shù)上，實現(xiàn)了大大的減少，提高了識別效率。最近，有學(xué)者提出GDRA（geometric distribution reader anticollision）拓?fù)浞桨?，利用篩選幾何概率分布函數(shù)來實現(xiàn)閱讀器碰撞問題最小化，它能提供更高的吞吐量，符合EPC國際標(biāo)準(zhǔn)，在不需要額外的硬件條件就可在真實的RFID系統(tǒng)中實現(xiàn)功能。

4結(jié)語

相比之下，Aloha類算法操作簡單，識別時間短，但穩(wěn)定性不足，系統(tǒng)利用率最高也只能達(dá)到36.8%，并且當(dāng)標(biāo)簽數(shù)量增加時，系統(tǒng)的識別效率將下降的很快。二進(jìn)制算法雖然識別效率高，穩(wěn)定性也較好，但是操作復(fù)雜，識別時間較長。改進(jìn)算法在原有的基礎(chǔ)上，實現(xiàn)新的突破，在準(zhǔn)確度、信道利用率、穩(wěn)定性等方面尋求改善，是未來的研究方向之一。