劉曉崗 宋高俊
摘要:無線射頻識(shí)別(Radio Frequency Identification,RFID)技術(shù)作為當(dāng)下最重要的科技之一,以其廣泛的應(yīng)用性將有越來越大的發(fā)展前景,RFID技術(shù)也由于其非接觸的特性,遇到了多目標(biāo)識(shí)別過程中的信息碰撞問題?,F(xiàn)對(duì)Aloha類防碰撞算法、二進(jìn)制樹防碰撞算法以及改進(jìn)算法進(jìn)行分析。
關(guān)鍵詞:RFID;防碰撞算法;Aloha;二進(jìn)制樹
RFID系統(tǒng)在識(shí)別過程中會(huì)有一個(gè)普遍的問題,那就是對(duì)象沖突,當(dāng)在同一時(shí)間內(nèi)有若干個(gè)電子標(biāo)簽同時(shí)請(qǐng)求識(shí)別是,閱讀器不能正確區(qū)別出來,這樣當(dāng)多個(gè)電子標(biāo)簽同時(shí)發(fā)送數(shù)據(jù)的時(shí)候,就會(huì)出現(xiàn)數(shù)據(jù)的干擾導(dǎo)致數(shù)據(jù)傳輸失敗,這就是文章要研究的防碰撞問題。為了解決這一問題,提高系統(tǒng)的性能,需要制定有效的防碰撞算法,所以防碰撞算法是RFID系統(tǒng)的研究核心。
現(xiàn)有的防碰撞算法包括:Aloha類防碰撞算法,又稱為隨機(jī)性算法;二進(jìn)制樹防碰撞算法,又稱為確定性算法;改進(jìn)算法,在原有的基礎(chǔ)上設(shè)計(jì)出性能更優(yōu)的算法。
1基于Aloha類防碰撞算法
ALOHA(Additive Link On line Hawaii)算法算是出現(xiàn)比較早的防碰撞算法,它是采取隨機(jī)多址方式。作為無線通信協(xié)議,ALOHA算法研究取得成功后被廣泛利用。在理想狀態(tài)下,利用ALOHA類防碰撞算法,系統(tǒng)最高吞吐率是36.8%。但是在實(shí)際應(yīng)用中,由于各種因素的干擾,系統(tǒng)的識(shí)別效率很難達(dá)到理想的狀態(tài)。
1.1純Aloha算法
純ALOHA算法也叫基本ALOHA算法,是一種比較容易的時(shí)分多址算法。當(dāng)標(biāo)簽進(jìn)入閱讀器的工作范圍內(nèi),標(biāo)簽獲取能量被激活,向閱讀器發(fā)送儲(chǔ)存在標(biāo)簽內(nèi)部的數(shù)據(jù)信息。在這個(gè)過程中,假如有兩個(gè)標(biāo)簽一同向閱讀器發(fā)送信息,就會(huì)產(chǎn)生信息沖突,造成完全碰撞;而當(dāng)一個(gè)標(biāo)簽正在向閱讀器發(fā)送過程中,另一個(gè)標(biāo)簽開始信息傳送,這種情況下就會(huì)出現(xiàn)標(biāo)簽部分碰撞。只有標(biāo)簽單獨(dú)在一個(gè)時(shí)間內(nèi)進(jìn)行信息傳輸時(shí)才能讓閱讀器正常識(shí)別,不會(huì)出現(xiàn)碰撞情況。使用純ALOHA算法,系統(tǒng)最大吞吐率只有18.4%,標(biāo)簽發(fā)生碰撞概率比能夠正確識(shí)別概率要大得多。
1.2時(shí)隙Aloha算法與幀時(shí)隙Aloha算法
由于ALOHA算法中,標(biāo)簽發(fā)送數(shù)據(jù)時(shí)間是隨機(jī)性的,導(dǎo)致完全碰撞或者部分碰撞。于是將純ALOHA算法進(jìn)行優(yōu)化,得到了時(shí)隙ALOHA算法。這種算法是把時(shí)間劃分成若干等長時(shí)隙(每個(gè)時(shí)隙長度滿足一個(gè)標(biāo)簽成功發(fā)送完數(shù)據(jù)),標(biāo)簽通過不同時(shí)隙向閱讀器發(fā)送數(shù)據(jù),如此一來,就能避免部分碰撞的產(chǎn)生,從而總體上縮減了產(chǎn)生碰撞的次數(shù)。時(shí)隙Aloha算法采用分割時(shí)隙思想,避免了標(biāo)簽的部分碰撞,只有成功識(shí)別和完全碰撞情況,成倍地提高了信道利用率。但要?jiǎng)澐謺r(shí)隙就要解決一個(gè)同步問題,在系統(tǒng)中要有同步時(shí)鐘,使閱讀器作用范圍內(nèi)的所有標(biāo)簽達(dá)到時(shí)隙同步。該算法的系統(tǒng)吞吐率可達(dá)到36.8%,比純Aloha算法效果提高了一倍。
盡管時(shí)隙ALOHA算法在信道利用率上比純ALOHA算法得到一定改進(jìn),可是標(biāo)簽發(fā)生碰撞的概率依然很大,發(fā)生碰撞后的標(biāo)簽會(huì)隨機(jī)接著發(fā)送數(shù)據(jù),進(jìn)而影響其他標(biāo)簽的讀取,為了避免這種情況,于是研究出了幀時(shí)隙ALOHA算法。這種方法是把多個(gè)時(shí)隙組成一個(gè)幀,在每一個(gè)幀內(nèi),標(biāo)簽任意選擇其中一個(gè)時(shí)隙發(fā)送數(shù)據(jù),但只可以發(fā)送一次。在某一個(gè)時(shí)隙內(nèi),當(dāng)標(biāo)簽發(fā)生了完全碰撞,將會(huì)處于休眠狀態(tài),等到下一幀進(jìn)行讀取,這樣不會(huì)影響本幀內(nèi)其他標(biāo)簽的正常讀取。算法中每一幀的時(shí)隙數(shù)都是固定的,并且時(shí)隙長會(huì)大于一個(gè)標(biāo)簽成功發(fā)送完信息的時(shí)間。這樣,閱讀器發(fā)送讀取指令后,假如一個(gè)時(shí)隙內(nèi)僅有一個(gè)標(biāo)簽響應(yīng),則成功讀取標(biāo)簽數(shù)據(jù);如果時(shí)隙內(nèi)沒有一個(gè)標(biāo)簽,就會(huì)掠過此時(shí)隙;如果存在許多標(biāo)簽的話,產(chǎn)生了碰撞后自動(dòng)等到下一幀的到來,再選擇其他時(shí)隙。
2基于二進(jìn)制樹防碰撞算法
二進(jìn)制樹防碰撞算法通過電子標(biāo)簽具有唯一的二進(jìn)制編碼來查詢區(qū)別。此算法工作原理是將產(chǎn)生了碰撞的電子標(biāo)簽分為0、1兩個(gè)子集,首先從子集0開始搜尋,要是沒有碰撞產(chǎn)生,說明成功識(shí)別。如果產(chǎn)生了碰撞,就將碰撞的標(biāo)簽再分成00與01兩個(gè)子集,再從00子集開始搜尋,重復(fù)執(zhí)行操作。0子集的標(biāo)簽完全成功識(shí)別后,轉(zhuǎn)向1子集搜尋,直至把全部標(biāo)簽都識(shí)別完,任務(wù)結(jié)束。
2.1二進(jìn)制搜索算法與動(dòng)態(tài)二進(jìn)制搜索算法
與ALOHA類算法不同的是,使用二進(jìn)制搜索算法需要用到標(biāo)簽自身的序列號(hào)和閱讀器的查詢指令號(hào)。當(dāng)標(biāo)簽序列號(hào)與閱讀器查詢指令相同時(shí),標(biāo)簽產(chǎn)生響應(yīng)。要是僅有一個(gè)標(biāo)簽做出響應(yīng),那么成功識(shí)別。如果存在若干個(gè)標(biāo)簽一同做出響應(yīng),閱讀器會(huì)根據(jù)碰撞位情況修正查詢指令,經(jīng)過不斷修正查詢命令來識(shí)別出所有標(biāo)簽。
動(dòng)態(tài)二進(jìn)制搜索(DBS,Dynamic Binary Search)算法是對(duì)二進(jìn)制搜索算法進(jìn)行優(yōu)化的。使用二進(jìn)制搜索算法,整個(gè)標(biāo)簽序列號(hào)需要多次被傳輸,并且閱讀器發(fā)送的REQUEST指令數(shù)據(jù)位也多,從而會(huì)造成查詢時(shí)間增加,出錯(cuò)頻率也跟著提高。動(dòng)態(tài)二進(jìn)制搜索算法能很好減少數(shù)據(jù)位冗余,但是它的運(yùn)行流程與二進(jìn)制搜索算法基本相同,只是修改了REQUEST指令。
2.2鎖位后退二進(jìn)制搜索算法與跳躍式動(dòng)態(tài)二進(jìn)制搜算算法
鎖位后退二進(jìn)制搜索算法也是在二進(jìn)制搜索算法基礎(chǔ)上得到優(yōu)化的,雖然動(dòng)態(tài)二進(jìn)制搜索算法能減少數(shù)據(jù)傳輸量,但是并不能減少搜索次數(shù)。鎖位后退二進(jìn)制搜索算法的工作原理是當(dāng)閱讀器成功識(shí)別出一個(gè)標(biāo)簽后,閱讀器不需要重新發(fā)送REQUEST指令,而是直接根據(jù)上一層的鎖位分組退回到上一層,也就是返回根節(jié)點(diǎn),這樣顯然會(huì)減少搜索次數(shù)。
跳躍式動(dòng)態(tài)二進(jìn)制搜索算法在動(dòng)態(tài)二進(jìn)制搜索算法和鎖位后退算法的基礎(chǔ)上結(jié)合而成的,涵蓋了兩種算法的優(yōu)點(diǎn),既減少了數(shù)據(jù)冗余位的發(fā)送,也減少了搜索次數(shù),同時(shí)縮短了查詢時(shí)間,也提高了標(biāo)簽識(shí)別效率。
跳躍式搜索算法比二進(jìn)制搜索以及鎖位后退搜索需要的查詢次數(shù)少,比動(dòng)態(tài)搜索算法數(shù)據(jù)傳輸量又少,整體性能相對(duì)來說是最好。
3改進(jìn)算法
為了使識(shí)別效率更好,不少學(xué)者在原有的基礎(chǔ)上,提出了新的改進(jìn)算法,有學(xué)者提出了優(yōu)化幀內(nèi)時(shí)隙長度的策略,并通過馬爾科夫建模實(shí)現(xiàn)對(duì)標(biāo)簽的讀取周期數(shù)達(dá)到減少的目的。同時(shí),基于二進(jìn)制樹的防碰撞算法也有很多學(xué)者在研究,并且在其基礎(chǔ)上提出了不少改進(jìn)算法,如改進(jìn)的返回式動(dòng)態(tài)二進(jìn)制算法、NTA算法、EMBT算法和二叉樹搜算算法等,相比之前的動(dòng)態(tài)二進(jìn)制搜算算法,在平均比特?cái)?shù)上,實(shí)現(xiàn)了大大的減少,提高了識(shí)別效率。最近,有學(xué)者提出GDRA(geometric distribution reader anticollision)拓?fù)浞桨福煤Y選幾何概率分布函數(shù)來實(shí)現(xiàn)閱讀器碰撞問題最小化,它能提供更高的吞吐量,符合EPC國際標(biāo)準(zhǔn),在不需要額外的硬件條件就可在真實(shí)的RFID系統(tǒng)中實(shí)現(xiàn)功能。
4結(jié)語
相比之下,Aloha類算法操作簡單,識(shí)別時(shí)間短,但穩(wěn)定性不足,系統(tǒng)利用率最高也只能達(dá)到36.8%,并且當(dāng)標(biāo)簽數(shù)量增加時(shí),系統(tǒng)的識(shí)別效率將下降的很快。二進(jìn)制算法雖然識(shí)別效率高,穩(wěn)定性也較好,但是操作復(fù)雜,識(shí)別時(shí)間較長。改進(jìn)算法在原有的基礎(chǔ)上,實(shí)現(xiàn)新的突破,在準(zhǔn)確度、信道利用率、穩(wěn)定性等方面尋求改善,是未來的研究方向之一。