RFID系統(tǒng)防碰撞算法研究

陳紅琳

(安徽財(cái)經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 蚌埠 233030)

RFID系統(tǒng)防碰撞算法研究

陳紅琳

(安徽財(cái)經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 蚌埠 233030)

在射頻識(shí)別中，多標(biāo)簽識(shí)別是一個(gè)常見問題，因此多標(biāo)簽防碰撞算法是RFID系統(tǒng)研究的重要內(nèi)容。當(dāng)系統(tǒng)中包含的標(biāo)簽數(shù)較多時(shí)，發(fā)生碰撞的概率將大大增加。為了提高標(biāo)簽識(shí)別的效率，提高射頻識(shí)別系統(tǒng)的性能，對(duì)現(xiàn)有的RFID系統(tǒng)防碰撞算法進(jìn)行了比較分析。從多種防碰撞方法的特性、基于CDMA的防碰撞方法、基于TDMA的算法幾個(gè)方面的研究現(xiàn)狀作了詳盡分析，對(duì)概率性防碰撞算法和確定性防碰撞算法中的最新研究成果進(jìn)行比較，指出各個(gè)算法的優(yōu)缺點(diǎn)，并提出了未來(lái)的研究趨勢(shì)。

無(wú)線射頻識(shí)別；防碰撞；概率性算法；確定性算法

0 引 言

無(wú)線射頻識(shí)別(Radio Frequency IDentification,RFID)也稱為射頻識(shí)別，是一種新興的自動(dòng)識(shí)別技術(shù)。RFID系統(tǒng)已廣泛應(yīng)用于工業(yè)自動(dòng)化、智能交通運(yùn)輸管理、產(chǎn)品防偽、物流、產(chǎn)品追溯等領(lǐng)域，并取得了很好的成效。

美國(guó)的大型零售商沃爾瑪在供應(yīng)鏈管理中采用RFID技術(shù)，減少了現(xiàn)貨倉(cāng)儲(chǔ)30%，從而增加純收入達(dá)153.5億美元。美國(guó)服裝公司將RFID標(biāo)簽貼到商品上，從而使得銷售率增加了14.3%。另外，美國(guó)國(guó)防部將RFID用于軍事，如無(wú)線運(yùn)輸監(jiān)測(cè)系統(tǒng)，用來(lái)識(shí)別跟蹤貨物運(yùn)輸[1]?？梢?，RFID系統(tǒng)有著潛在的效益與廣闊的應(yīng)用前景。

1 RFID防碰撞協(xié)議

RFID系統(tǒng)由標(biāo)簽和閱讀器組成，兩者利用電磁波的反射能量進(jìn)行通信，通過(guò)閱讀器和安裝于載體上的RFID標(biāo)簽，能夠?qū)崿F(xiàn)堆載體的非接觸識(shí)別和數(shù)據(jù)信息交換。當(dāng)在閱讀器的作用范圍內(nèi)存在多個(gè)電子標(biāo)簽時(shí)，電子標(biāo)簽向閱讀器發(fā)送的信號(hào)就會(huì)出現(xiàn)碰撞，此時(shí)閱讀器不能準(zhǔn)確識(shí)別標(biāo)簽。RFID防碰撞的研究主要是解決如何快速準(zhǔn)確地從眾多標(biāo)簽中識(shí)別出一個(gè)標(biāo)簽的問題。目前，國(guó)內(nèi)外很多學(xué)者對(duì)RFID防碰撞問題展開了深入研究，也取得了顯著的成果。

結(jié)合無(wú)線傳輸?shù)奶匦?，多?biāo)簽防碰撞可以通過(guò)以下四種方式解決[2]：空分多址(SDMA)、時(shí)分多址(TDMA)、頻分多址(FDMA)、碼分多址(CDMA)。圖1展示了防碰撞協(xié)議的分類。

圖1 RFID防碰撞協(xié)議

SDMA主要在空間上劃分為多個(gè)集群，使得每個(gè)集群的標(biāo)簽數(shù)量減少，從而減少?zèng)_突發(fā)生的概率，在每個(gè)域內(nèi)可以采用其他防碰撞方法來(lái)解決沖突問題。當(dāng)在閱讀器的作用范圍內(nèi)劃分太多集群，可能會(huì)導(dǎo)致空集群的出現(xiàn)，這是系統(tǒng)額外的開銷，同時(shí)也可能出現(xiàn)擁擠集群，這兩種情況都會(huì)影響系統(tǒng)性能。文獻(xiàn)[1]中提出一種基于舉例的聚類方法(Power-based Distance Clustering，PDC)，解決了在理想狀態(tài)下最優(yōu)集群數(shù)目的計(jì)算方法問題。

FDMA通過(guò)將可用信道劃分成不同頻率的子通道，標(biāo)簽與閱讀器之間的通信可以選擇不同的子通道，以避免發(fā)生沖突。這種方式要求閱讀器和標(biāo)簽?zāi)軌蛞砸欢ǖ臋C(jī)制更換載波頻率，大大增加了實(shí)現(xiàn)的復(fù)雜度，同時(shí)也要求整個(gè)系統(tǒng)能覆蓋更大的帶寬。這要求標(biāo)簽?zāi)軌蚍蛛x不同的信道，由于被動(dòng)式標(biāo)簽不具備這個(gè)功能，而額外的電路必然會(huì)增加標(biāo)簽的復(fù)雜性和成本。目前關(guān)于FDMA的RFID防碰撞算法的研究較少，文獻(xiàn)[3]提出了一種基于混沌序列的擴(kuò)頻ALOHA算法，采用了混沌序列—Chebyshev對(duì)標(biāo)簽的ID序列進(jìn)行擴(kuò)頻，吞吐量較高。

CDMA是讓標(biāo)簽使用不同的調(diào)制碼對(duì)所發(fā)數(shù)據(jù)進(jìn)行調(diào)制，各個(gè)標(biāo)簽按照一定的條件隨機(jī)地產(chǎn)生各自的調(diào)制碼，當(dāng)標(biāo)簽與閱讀器進(jìn)行數(shù)據(jù)通訊時(shí)，標(biāo)簽必須用調(diào)制碼將待發(fā)送序列調(diào)制后發(fā)送，閱讀器接收到信號(hào)后要進(jìn)行解調(diào)。該方法對(duì)提高數(shù)據(jù)傳輸?shù)陌踩杂幸欢ǖ膬?yōu)勢(shì)。

TDMA是把可用信道按時(shí)間分配給不同標(biāo)簽使用，以此解決碰撞問題。這種方式結(jié)構(gòu)簡(jiǎn)單，實(shí)現(xiàn)容易，應(yīng)用廣泛。基于TDMA的算法可以通過(guò)對(duì)標(biāo)簽和閱讀器分別進(jìn)行控制來(lái)實(shí)現(xiàn)，由于標(biāo)簽控制實(shí)現(xiàn)成本較高，因而目前主要的研究重點(diǎn)在于對(duì)閱讀器的控制。

2 基于CDMA的RFID防碰撞算法

CDMA技術(shù)應(yīng)用在RFID技術(shù)需要在標(biāo)簽內(nèi)增加擴(kuò)頻碼序列生成器，由于隨機(jī)產(chǎn)生的序列可能無(wú)法滿足擴(kuò)頻碼的特性，會(huì)導(dǎo)致閱讀器識(shí)別標(biāo)簽失敗，這是CDMA技術(shù)防碰撞算法要解決的首要問題。文獻(xiàn)[4]利用碼分多址技術(shù)，在標(biāo)簽內(nèi)預(yù)存儲(chǔ)所需要的擴(kuò)頻碼，結(jié)合認(rèn)證密鑰和哈希函數(shù)，提出了一種適用于RFID系統(tǒng)的具有防碰撞功能的安全認(rèn)證協(xié)議。該協(xié)議能有效解決碰撞問題，同時(shí)可抵抗多種干擾，具有一定的安全性。文獻(xiàn)[5]提出了一種基于Independent Component Analysis (ICA)的算法，在最大信噪比的條件下，采用CDMA機(jī)制傳輸信號(hào)。該系統(tǒng)能正確分離不同信號(hào)，性能較好；但是該算法由于其收斂速度慢，若學(xué)習(xí)序列選擇不當(dāng)，會(huì)導(dǎo)致閱讀器讀寫標(biāo)簽失敗。文獻(xiàn)[6]改進(jìn)了ICA算法，提出一種新型的FastICA-Based on Negative Entropy (FastICABNE)算法，吞吐率最高可達(dá)69%，性能有極大改善。當(dāng)標(biāo)簽數(shù)目大，而調(diào)制碼序列過(guò)短時(shí)，將導(dǎo)致大量標(biāo)簽選擇相同的調(diào)制碼序列從而發(fā)生碰撞；而當(dāng)標(biāo)簽數(shù)目小，而調(diào)制碼序列過(guò)長(zhǎng)時(shí)，又導(dǎo)致整個(gè)識(shí)別時(shí)間的增加。針對(duì)這個(gè)問題，文獻(xiàn)[7]提出了一種解決方案：閱讀器根據(jù)已經(jīng)識(shí)別的標(biāo)簽數(shù)目，推斷當(dāng)前未識(shí)別的標(biāo)簽數(shù)目，并動(dòng)態(tài)地修改標(biāo)簽產(chǎn)生的調(diào)制碼序列長(zhǎng)度，對(duì)整個(gè)射頻識(shí)別的耗時(shí)過(guò)程進(jìn)行優(yōu)化。由于CDMA存在多址干擾的問題，很多研究者將基于時(shí)隙的防碰撞算法與CDMA有效結(jié)合，充分發(fā)揮兩者的優(yōu)勢(shì)，揚(yáng)長(zhǎng)避短[8-10]。

3 基于TDMA的RFID防碰撞算法

基于TDMA的防碰撞算法有很多，可以歸為兩大類：一類是基于時(shí)隙的概率性算法—ALOHA，另一類是基于二進(jìn)制搜索樹的確定性算法。ALOHA算法標(biāo)簽設(shè)計(jì)簡(jiǎn)單，成本和功耗較低，但是存在錯(cuò)判和誤判的問題。二進(jìn)制算法識(shí)別率較高，錯(cuò)判、誤判率低，但是延遲較大。

3.1 概率性防碰撞算法

概率性防碰撞算法主要分為三種：純ALOHA(PA)、時(shí)隙ALOHA(SA)、幀時(shí)隙(FSA)。在PA算法中，標(biāo)簽隨機(jī)響應(yīng)閱讀器的發(fā)送請(qǐng)求，若單個(gè)標(biāo)簽響應(yīng)，此時(shí)沒有沖突發(fā)生，閱讀器發(fā)送確認(rèn)ACK，若多個(gè)標(biāo)簽響應(yīng)則發(fā)生沖突，此時(shí)閱讀器發(fā)送否定確認(rèn)NACK，沖突的標(biāo)簽隨機(jī)等待一段時(shí)間重新發(fā)送，當(dāng)標(biāo)簽數(shù)量較多時(shí)，碰撞概率急劇增大，識(shí)別全部標(biāo)簽的時(shí)間復(fù)雜度也急劇增加，會(huì)出現(xiàn)標(biāo)簽“餓死”現(xiàn)象。為了減少碰撞并提高標(biāo)簽的識(shí)別率，提出了兩種PA算法的改進(jìn)方案：一種是對(duì)已經(jīng)識(shí)別的標(biāo)簽去活，使之處于休眠態(tài)；另一種是對(duì)已經(jīng)識(shí)別的標(biāo)簽增加它們的回退時(shí)間[2]。這兩種方法在一定程度上可以減少碰撞的發(fā)生，但是都不能很好地解決算法的低效缺陷。

在PA算法的基礎(chǔ)上對(duì)其作了一定的改進(jìn)，提出了時(shí)隙SA算法，即采用時(shí)分多路復(fù)用機(jī)制，將一個(gè)時(shí)間段劃分成多個(gè)時(shí)間片，把可用信道按時(shí)間來(lái)劃分，標(biāo)簽采用爭(zhēng)用的機(jī)制去占用時(shí)隙，標(biāo)簽只能在時(shí)隙之間的分界處發(fā)送自身的信息，這樣避免了信號(hào)部分沖突的概率，但不能避免信號(hào)完全沖突的情況，因此沖突率相比于PA降低了一半，同時(shí)該算法有較好的吞吐率，最大可達(dá)36%。但是當(dāng)標(biāo)簽數(shù)較多時(shí)，碰撞概率較大，對(duì)于沖突的解決也沒有一個(gè)很好的機(jī)制。另外，如果幀長(zhǎng)和標(biāo)簽數(shù)之間的差值較大，那么標(biāo)簽的識(shí)別時(shí)間因?yàn)闆_突現(xiàn)象而極大增加，因此SA算法的系統(tǒng)效率較低[11]。

在此基礎(chǔ)上，研究人員對(duì)SA算法作了改進(jìn)，將傳輸時(shí)間劃分成若干時(shí)隙，若干時(shí)隙發(fā)送一幀，在每一幀里每個(gè)標(biāo)簽被允許發(fā)送一次，標(biāo)簽隨機(jī)選擇一個(gè)時(shí)隙發(fā)送其ID序列，若發(fā)生碰撞，標(biāo)簽會(huì)在下一幀里重發(fā)沖突序列。FSA算法可分為基于時(shí)隙的ALOHA(BFSA)和動(dòng)態(tài)幀時(shí)隙ALOHA(DFSA)[2]。BFSA算法的閱讀器的每一幀時(shí)隙數(shù)是固定不變的，標(biāo)簽只有在規(guī)定的時(shí)隙內(nèi)才能正確傳輸，算法吞吐率最大可達(dá)36.7%[2,12]。在BFSA算法中，當(dāng)閱讀器周圍的標(biāo)簽數(shù)遠(yuǎn)少于時(shí)隙數(shù)時(shí)，必然會(huì)存在大量的空閑時(shí)隙，使得系統(tǒng)的效率低下；而當(dāng)標(biāo)簽數(shù)遠(yuǎn)大于時(shí)隙數(shù)時(shí)，碰撞概率大大提高。DFSA算法可以在閱讀器發(fā)送時(shí)隙受限時(shí)提高系統(tǒng)閱讀效率，使時(shí)隙數(shù)隨標(biāo)簽數(shù)的變化而自動(dòng)調(diào)整。當(dāng)標(biāo)簽數(shù)量較少時(shí)，時(shí)隙數(shù)被初始化為一個(gè)較小的值(如2、4等)，并不斷增加，直到第一個(gè)標(biāo)簽被識(shí)別為止[2]。當(dāng)標(biāo)簽數(shù)很多時(shí)，時(shí)隙的調(diào)整就必須采用一種更為高效的方式。研究表明，當(dāng)閱讀器的時(shí)隙數(shù)和周圍標(biāo)簽數(shù)量相等時(shí)，標(biāo)簽成功傳輸?shù)母怕首畲骩13]。文獻(xiàn)[12]指出，當(dāng)系統(tǒng)最大發(fā)送時(shí)隙數(shù)等于響應(yīng)標(biāo)簽數(shù)量時(shí)，系統(tǒng)傳輸?shù)男蕿?6.4%。DFSA算法實(shí)現(xiàn)的關(guān)鍵在于標(biāo)簽數(shù)的估計(jì)，研究者提出了增強(qiáng)的DFSA算法(EDFSA)，關(guān)于這方面的研究也有很多相關(guān)的成果。由于閱讀器發(fā)送的時(shí)隙不可能隨著周圍標(biāo)簽數(shù)的增加而無(wú)限制增加，因此要給時(shí)隙數(shù)設(shè)置一個(gè)門限值，文獻(xiàn)[14]中建議門限值為256，此時(shí)響應(yīng)的標(biāo)簽數(shù)應(yīng)等于最大時(shí)隙數(shù)。若標(biāo)簽數(shù)遠(yuǎn)大于時(shí)隙數(shù)，此時(shí)可將標(biāo)簽分成若干組，文獻(xiàn)[12]指出，當(dāng)標(biāo)簽數(shù)大于270時(shí)，閱讀器選擇256個(gè)標(biāo)簽進(jìn)行處理，若標(biāo)簽數(shù)小于270，則按照DFSA算法進(jìn)行處理。通過(guò)實(shí)驗(yàn)比較，該算法的效率高于DFSA。此外，文獻(xiàn)[15-16]也對(duì)DFSA算法做了改進(jìn)與優(yōu)化。

3.2 確定性防碰撞算法

確定性算法的原理是由閱讀器首先發(fā)送一個(gè)匹配前綴，每個(gè)標(biāo)簽都有自己的前綴匹配電路，標(biāo)簽ID號(hào)的相應(yīng)長(zhǎng)度的前綴與閱讀器的匹配前綴進(jìn)行比較，若相同則應(yīng)答。確定性算法主要分為四類：查詢樹搜索算法(Query Tree，QT)、二進(jìn)制樹搜索(Binary Tree，BT)、樹分裂(Tree Splitting，TS)、按位仲裁(Bitwise Arbitration，BTA)。

在QT算法中，閱讀器發(fā)送長(zhǎng)度為n的匹配前綴prefix，標(biāo)簽ID的前n位若與prefix匹配，則發(fā)送其后的ID號(hào)，如果發(fā)生碰撞，此時(shí)閱讀器將prefix后增加一個(gè)0或1構(gòu)成新的prefix，再重新進(jìn)行查詢，直到只有一個(gè)標(biāo)簽響應(yīng)為止[13]。QT算法的查詢過(guò)程符合二叉樹的特性，詢問樹的內(nèi)部節(jié)點(diǎn)為碰撞周期，葉子節(jié)點(diǎn)為成功周期。由于不能得知ID的分布，所以擴(kuò)展查詢前綴的時(shí)候會(huì)產(chǎn)生大量無(wú)用的前綴，使得該算法效率低下。文獻(xiàn)[17]提出了混合詢問樹算法(HybridQueryTree，HQT)，用四叉詢問樹代替二叉詢問樹，采用時(shí)隙補(bǔ)償機(jī)制來(lái)減少空閑周期。若響應(yīng)標(biāo)簽發(fā)生碰撞，閱讀器將prefix后增加兩位二進(jìn)制數(shù)(00、01、10、11)再進(jìn)行詢問。改進(jìn)算法減少了碰撞周期(該算法引進(jìn)了時(shí)隙補(bǔ)償機(jī)制，當(dāng)標(biāo)簽與prefix匹配時(shí)，標(biāo)簽延時(shí)0到3個(gè)時(shí)隙再響應(yīng))，但如果某一時(shí)隙沒有標(biāo)簽響應(yīng)，則產(chǎn)生了空閑時(shí)隙，因此HQT算法不能達(dá)到減少空閑周期到最佳狀態(tài)的目的?；诖耍环N高效的HQT(EfficientHybridQueryTree，EHQT)算法被提出[18]。當(dāng)響應(yīng)標(biāo)簽發(fā)生碰撞，閱讀器將prefix后增加三位二進(jìn)制數(shù)再進(jìn)行詢問，也即采用八叉詢問樹來(lái)進(jìn)一步減少碰撞周期。該算法采用的時(shí)隙補(bǔ)償機(jī)制同樣也是延時(shí)0～3個(gè)時(shí)隙來(lái)發(fā)送，延時(shí)的時(shí)隙數(shù)由prefix的后三位中1的個(gè)數(shù)決定，采用這種方法可以避免空閑時(shí)隙。通過(guò)比較，EHQT算法的詢問次數(shù)比HQT算法大大減少。文獻(xiàn)[19-21]中也有關(guān)于該算法的相關(guān)研究。

BT搜索算法的核心是通過(guò)多次比較，不斷篩選出不同的序列號(hào)。標(biāo)簽收到閱讀器發(fā)來(lái)的序列號(hào)，若自己的序列號(hào)小于它，則做出響應(yīng)；如果發(fā)生碰撞，閱讀器會(huì)對(duì)發(fā)生碰撞的最高位置0，其后各位全部置1，然后把該序列作為下一輪請(qǐng)求的序列，重復(fù)這個(gè)過(guò)程，直到只有一個(gè)標(biāo)簽響應(yīng)為止。最后閱讀器使用命令使讀出的標(biāo)簽進(jìn)入“無(wú)聲”狀態(tài)，即在后面的識(shí)別過(guò)程中不再響應(yīng)閱讀器的詢問。重復(fù)執(zhí)行以上過(guò)程，識(shí)別出所有標(biāo)簽[21]。在二進(jìn)制樹搜索算法中，閱讀器每一次詢問都要發(fā)送完整序列，標(biāo)簽也要響應(yīng)完整的標(biāo)簽序列，閱讀器與標(biāo)簽每次發(fā)送的指令位數(shù)較多。動(dòng)態(tài)二進(jìn)制搜索算法在此基礎(chǔ)上做了改進(jìn)[22]，使得閱讀器每次只需發(fā)送到最高碰撞位為止的前半段序列，標(biāo)簽只需要發(fā)送最高碰撞位以后的后半段序列，極大地減少了交互的指令位數(shù)。在二進(jìn)制搜索算法中，每一次識(shí)別出一個(gè)標(biāo)簽后都要從頭開始識(shí)別下一個(gè)標(biāo)簽，因而效率低下。后退式二進(jìn)制搜索算法對(duì)此作了進(jìn)一步的改進(jìn)，文獻(xiàn)[23]使用棧保留了之前的傳輸指令，當(dāng)識(shí)別出一個(gè)標(biāo)簽后，只需從棧中取出指令來(lái)識(shí)別下一個(gè)標(biāo)簽，該算法大大減少了讀寫次數(shù)，提高了搜索效率。目前，在此基礎(chǔ)上，研究人員又對(duì)該算法進(jìn)行優(yōu)化，相繼提出了一系列的優(yōu)化算法。文獻(xiàn)[24]中提出的算法首先要求所有標(biāo)簽向閱讀器發(fā)送完整的序列，然后由閱讀器獲取其中的所有碰撞比特，并記錄碰撞的位數(shù)。在隨后的識(shí)別過(guò)程中，閱讀器和標(biāo)簽只需要對(duì)碰撞位的數(shù)值進(jìn)行識(shí)別，而忽略其他比特位。該算法極大降低了閱讀器與標(biāo)簽之間傳輸數(shù)據(jù)量以及閱讀器發(fā)送請(qǐng)求的次數(shù)，傳輸效率較好。文獻(xiàn)[25]提出一種基于搜索矩陣的自適應(yīng)防碰撞算法(ASM)，該算法根據(jù)標(biāo)簽碰撞位置，獲得一個(gè)固定的2*k階前綴搜索矩陣(k為碰撞次數(shù))，通過(guò)棧來(lái)存儲(chǔ)碰撞時(shí)的搜索深度，當(dāng)閱讀器返回上層未完成全分支搜索節(jié)點(diǎn)處時(shí)，根據(jù)棧中提供的搜索深度及不同時(shí)隙的狀態(tài)，自適應(yīng)地調(diào)整搜索路徑。當(dāng)碰撞位不連續(xù)時(shí)，該算法識(shí)別效率較高，但當(dāng)碰撞位連續(xù)時(shí)，隨著搜索深度的增加，識(shí)別性能降低。文獻(xiàn)[26]在此基礎(chǔ)上作了改進(jìn)，將前綴搜索矩陣改為8*k階，對(duì)碰撞位進(jìn)行分段構(gòu)造初始前綴搜索矩陣，每段最多為3位。在識(shí)別過(guò)程中，如果發(fā)生碰撞，閱讀器則采用一種新的查詢機(jī)制獲得準(zhǔn)確的查詢前綴，動(dòng)態(tài)調(diào)整搜索矩陣。該算法能大大減少碰撞時(shí)隙數(shù)，避免空閑時(shí)隙的產(chǎn)生。

TS算法通過(guò)一個(gè)隨機(jī)數(shù)生成器將響應(yīng)標(biāo)簽劃分成不同的分裂子集，子集大小不斷減小，直到子集里只包含一個(gè)標(biāo)簽為止。每個(gè)標(biāo)簽中有一個(gè)隨機(jī)二進(jìn)制生成器和一個(gè)計(jì)數(shù)器，當(dāng)計(jì)數(shù)器為0時(shí)，標(biāo)簽處于準(zhǔn)備態(tài)，否則處于休眠態(tài)或等待態(tài)。每個(gè)時(shí)隙閱讀器都要告知本時(shí)隙是碰撞、成功還是空閑，處于不同狀態(tài)的標(biāo)簽會(huì)做出相應(yīng)的反應(yīng)。文獻(xiàn)[21]提出通過(guò)在閱讀器設(shè)置棧及標(biāo)簽中設(shè)置內(nèi)部休眠計(jì)數(shù)器，使閱讀器和標(biāo)簽具有記憶功能，因而該算法縮小了符合條件的標(biāo)簽范圍，減少了標(biāo)簽碰撞的概率，同時(shí)由于采用棧存儲(chǔ)命令，減少了發(fā)送指令的位數(shù)，故該算法降低了識(shí)別時(shí)間。當(dāng)標(biāo)簽數(shù)較多時(shí)，分裂樹分裂速度較慢，而若標(biāo)簽數(shù)較少時(shí)，會(huì)存在較多的空閑時(shí)隙。文獻(xiàn)[27]提出了一種自適應(yīng)分裂樹(AdaptiveSplittingTree,AST)算法，在碰撞時(shí)隙內(nèi)，結(jié)合碰撞集規(guī)模確定規(guī)模集參數(shù)，使得碰撞標(biāo)簽均勻分布到各子集中。當(dāng)標(biāo)簽較多時(shí)，該算法可加速分裂，標(biāo)簽較少時(shí)，可以減少空閑時(shí)隙，因而該算法識(shí)別效率較高。

BTA算法要求標(biāo)簽將ID從高位到低位依次發(fā)送，在發(fā)送過(guò)程中要求保持標(biāo)簽的同步性，換句話說(shuō)，就是要求多個(gè)標(biāo)簽發(fā)送相同的位，當(dāng)只有兩個(gè)標(biāo)簽發(fā)送碰撞時(shí)，此時(shí)出現(xiàn)兩個(gè)不同的響應(yīng)位，該位的位置就可以被指定[28]，該算法能識(shí)別出全部標(biāo)簽，但搜索時(shí)間過(guò)長(zhǎng)。文獻(xiàn)[29]提出了基于狀態(tài)仲裁的鎖位防碰撞算法，該算法首先檢測(cè)所有標(biāo)簽的沖突位，進(jìn)行鎖位處理，將沖突位生成新的序列，然后把標(biāo)簽分為去活態(tài)、休眠態(tài)和準(zhǔn)備態(tài)三種狀態(tài)：已經(jīng)識(shí)別的標(biāo)簽標(biāo)記為去活態(tài)；符合詢問條件的為準(zhǔn)備態(tài)；其余的為休眠態(tài)。每識(shí)別出一個(gè)標(biāo)簽后，下一次的搜索就可限制在準(zhǔn)備態(tài)的標(biāo)簽中，當(dāng)準(zhǔn)備態(tài)的標(biāo)簽全部識(shí)別后，處于休眠態(tài)的標(biāo)簽就可轉(zhuǎn)變?yōu)闇?zhǔn)備態(tài)。該算法極大地減少了一次識(shí)別中沖突的標(biāo)簽數(shù)，能快速識(shí)別出各種標(biāo)簽，同時(shí)鎖位處理可以減少通信的數(shù)據(jù)量，特別對(duì)于標(biāo)簽ID連續(xù)的情況，該算法有極大的優(yōu)越性。

通過(guò)對(duì)以上比較典型的確定性防碰撞算法的特性進(jìn)行分析，對(duì)幾種算法在執(zhí)行過(guò)程中標(biāo)簽和閱讀器的傳輸數(shù)據(jù)量、閱讀器識(shí)別次數(shù)、算法實(shí)現(xiàn)的難易程度及算法執(zhí)行效率作了比較，結(jié)果見表1。

表1 幾種改進(jìn)算法性能比較

4 提高防碰撞算法效率的策略

基于對(duì)相關(guān)文獻(xiàn)的閱讀與分析，防碰撞算法的設(shè)計(jì)目標(biāo)是準(zhǔn)確、快速、完整、安全地識(shí)別標(biāo)簽，算法分別從識(shí)別次數(shù)、傳輸數(shù)據(jù)量和減少空閑時(shí)隙入手，來(lái)提高標(biāo)簽讀取效率。

(1)識(shí)別次數(shù)。標(biāo)簽識(shí)別次數(shù)越少，閱讀器識(shí)別所有標(biāo)簽的時(shí)間越短，識(shí)別效率越高。在幀時(shí)隙ALOHA算法和查詢樹算法中，通過(guò)在識(shí)別過(guò)程中劃分時(shí)隙，減少同一時(shí)刻響應(yīng)的標(biāo)簽數(shù)來(lái)減少碰撞的概率，從而達(dá)到減少識(shí)別次數(shù)的目的。另外，在二進(jìn)制搜索樹算法中，利用棧來(lái)存儲(chǔ)已發(fā)送的請(qǐng)求命令參數(shù)，也可以減少發(fā)送請(qǐng)求命令的次數(shù)。最后，在識(shí)別過(guò)程中應(yīng)用碼分多址、頻分多址技術(shù)對(duì)數(shù)據(jù)進(jìn)行編碼，只要編碼的碼元或頻率不同，也可以區(qū)分不同標(biāo)簽，從而減少標(biāo)簽識(shí)別次數(shù)。

(2)傳輸數(shù)據(jù)量。識(shí)別過(guò)程中傳輸?shù)臄?shù)據(jù)量多少必然影響識(shí)別時(shí)間，因此，各種算法在優(yōu)化過(guò)程中也要考慮如何減少傳輸數(shù)據(jù)量的問題，可以從三方面入手：第一，對(duì)所有標(biāo)簽進(jìn)行預(yù)處理，即在標(biāo)簽識(shí)別前，先通過(guò)所有標(biāo)簽的發(fā)送序列判斷碰撞位，忽略相同的比特位，后面的識(shí)別過(guò)程中只用對(duì)碰撞位進(jìn)行處理，這種方法可以極大減少識(shí)別過(guò)程中的傳輸數(shù)據(jù)量；第二，采用棧存儲(chǔ)已發(fā)送的命令參數(shù)，完成一次識(shí)別操作后，不需要重復(fù)發(fā)送請(qǐng)求命令，只需從棧中讀取即可；第三，減少請(qǐng)求和響應(yīng)命令中參數(shù)的比特位數(shù)，忽略已經(jīng)識(shí)別的和相同的比特位，只發(fā)送未識(shí)別的比特位，減少冗余數(shù)據(jù)的傳送。

(3)空閑時(shí)隙。在非確定性算法和確定性算法中都可以對(duì)識(shí)別過(guò)程進(jìn)行時(shí)隙劃分，可大大減少碰撞概率，但不可避免地存在一定的空閑時(shí)隙，延長(zhǎng)了識(shí)別時(shí)間，特別是當(dāng)標(biāo)簽數(shù)量較少時(shí)，空閑時(shí)隙會(huì)較多。在FSA算法中，可以通過(guò)估算標(biāo)簽數(shù)來(lái)動(dòng)態(tài)調(diào)整時(shí)隙數(shù)，時(shí)隙數(shù)越接近標(biāo)簽數(shù)，算法效率越高。QT算法中根據(jù)二進(jìn)制樹的結(jié)構(gòu)來(lái)劃分時(shí)隙，標(biāo)簽數(shù)較少時(shí)，可采用文獻(xiàn)[18]中的八叉樹結(jié)構(gòu)，根據(jù)三位二進(jìn)制位中1的個(gè)數(shù)來(lái)確定時(shí)隙數(shù)。當(dāng)標(biāo)簽數(shù)較多時(shí)，可以在識(shí)別過(guò)程中使碰撞標(biāo)簽均勻分布在不同時(shí)隙來(lái)減少空閑時(shí)隙，或者利用棧中存儲(chǔ)的搜索深度及不同時(shí)隙的狀態(tài)，自動(dòng)調(diào)整搜索路徑，這兩種方法都能在一定程度上減少空閑時(shí)隙。

綜上所述，提高標(biāo)簽識(shí)別效率的角度和方法各不相同，算法難易程度也存在一定的差異。一般來(lái)說(shuō)，算法越簡(jiǎn)單，實(shí)現(xiàn)越容易，但效率越低；相反，算法效率越高，算法越復(fù)雜，越難實(shí)現(xiàn)。同時(shí)，不同算法在標(biāo)簽數(shù)量變化時(shí)識(shí)別效率也會(huì)隨之不同。所以，在具體應(yīng)用中，應(yīng)綜合考慮成本、標(biāo)簽數(shù)、效率、環(huán)境等多種因素來(lái)設(shè)計(jì)合適的算法。

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

基于對(duì)已經(jīng)取得的成果以及對(duì)未來(lái)應(yīng)用中可能出現(xiàn)的問題的分析，目前，仍有以下問題值得進(jìn)一步的研究：

(1)基于空分多址的RFID防碰撞算法研究。未來(lái)RFID系統(tǒng)必應(yīng)用于大規(guī)模、超大規(guī)模的標(biāo)簽數(shù)的環(huán)境，在空間上劃分域，按區(qū)域識(shí)別，能提高系統(tǒng)識(shí)別效率，而目前在這方面的研究較少。

(2)RFID識(shí)別過(guò)程的信息安全、抗干擾問題。由于標(biāo)簽與閱讀器之間采用無(wú)線的方式傳輸信息，這就面臨著很多安全方面的問題，而采用現(xiàn)有的無(wú)線安全策略又必然會(huì)增加標(biāo)簽成本。

因此，好的算法應(yīng)兼顧成本、性能、安全性等各方面的因素。

[1]UllahS,AlsalihW,AlsehaimA,etal.Areviewoftagsanti-collisionandlocalizationprotocolsinRFIDnetworks[J].JMedSyst,2012,36:4037-4050.

[2]KlairDK,ChinKW,RaadR.AsurveyandtutorialofRFIDanti-collisionprotocols[J].IEEECommunicationSurveysandTutorials,2010,12(3):400-421.

[3] 陳旭輝,萬(wàn) 磊,龔仁彬.基于混沌擴(kuò)頻序列的RFID防碰撞算法分析[J].微電子學(xué)與計(jì)算機(jī),2012,29(12):64-67.

[4] 丁治國(guó),朱學(xué)永,雷迎科.基于碼分多址和防碰撞功能的RFID安全認(rèn)證協(xié)議[J].中國(guó)科學(xué)院研究生院學(xué)報(bào),2010,27(3):397-403.

[5]YuanLifen,HeYigang.ApplicationofICA-basedanti-collisionalgorithminRFIDsystem[J].AnalogIntegratedCircuitsandSignalProcessing,2010,63(2):169-175.

[6] 彭永華,何怡剛.一種新型ICA算法在RFID系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程,2012,38(19):25-29.

[7] 王 平,胡愛群,裴文江.一種基于碼分復(fù)用機(jī)制的超高頻RFID防碰撞方法[J].電子與信息學(xué)報(bào),2007,29(11):2637-2640.

[8] 李澤蘭,何怡剛,劉拓晟.基于廣義地址碼的RFID防碰撞算法[J].計(jì)算機(jī)測(cè)量與控制,2010,18(5):1114-1117.

[9] 趙曉霞,昂志敏,郭 治.一種新的時(shí)隙ALOHA算法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2010,33(6):855-858.

[10]ZhangWeijun,ZhangShuping,ZhangDawei.Ananti-collisionalgorithmofRFIDtagsbasedonCDMA[J].AdvancesinIntelligentandSoftComputing,2012,159:119-123.

[11] 姜仲云,錢 晨,袁玉勇,等.一種新型混合幀ALOHA和BS防沖突算法[J].電子科技,2011,24(10):88-92.

[12] 翟 永,徐 進(jìn).一種用于RFID系統(tǒng)的防碰撞算法[J].計(jì)算機(jī)工程,2009,35(9):272-274.

[13]BolicM,RyleDS,StojmenovicI.RFIDsystems:researchtrendsandchallenges[J].Wiley,2010,207:1124-1143.

[14] 郭來(lái)功,黃友銳,蔡 俊.優(yōu)化的動(dòng)態(tài)幀時(shí)隙ALOHA防碰撞算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(11):4141-4143.

[15]LiuShian,PengXiaojuan.ImproveddynamicframeslottedALOHAalgorithmforanti-collisioninRFIDsystems[J].InternetofThings,2012,312:242-247.

[16] 劉齊宏,李天德,周志斌,等.基于射頻識(shí)別系統(tǒng)RFID動(dòng)態(tài)時(shí)隙算法的經(jīng)濟(jì)性研究[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2009,41(6):183-186.

[17]RyuJ，LeeH，SeokY，etal．AhybridquerytreeprotocolfortagcollisionarbitrationinRFIDsystems[C]//ProcofIEEEinternationalconferenceoncommunications.[s.l.]:IEEEPress，2007:5981-5986．

[18] 孫文勝，陳安輝.高效的RFID混合詢問樹防碰撞算法[J].計(jì)算機(jī)應(yīng)用研究,2011,28(10):3717-3719.

[19] 周 清,蔡 明.改進(jìn)的RFID混合查詢樹防碰撞算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(1):209-213.

[20] 南敬昌,單曉艷,高明明.RFID系統(tǒng)中改進(jìn)的混合查詢樹防碰撞算法[J].計(jì)算機(jī)工程,2012,38(23):291-292.

[21] 高金輝,鄭曉彥.RFID系統(tǒng)中二進(jìn)制搜索防碰撞改進(jìn)算法[J].計(jì)算機(jī)測(cè)量與控制,2012,20(10):2754-2756.

[22] Choi J H,Lee D,Youn Y.Scanning-based preprocessing for enhanced tag anti-collision protocols[C]//Proc of international symposium on communications and information technologies．Washington,DC:IEEE Computer Society,2006:1207-1211.

[23] 余松森,詹宜巨,彭衛(wèi)東,等.基于后退式索引的二進(jìn)制樹形搜索反碰撞算法及其實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(16):26-28.

[24] 袁正午,段莉丹.改進(jìn)的基于堆棧存儲(chǔ)的二進(jìn)制搜索算法[J].計(jì)算機(jī)應(yīng)用,2012,32(11):3089-3091.

[25] 丁治國(guó),郭 立,劉 琦.一種基于搜索矩陣的自適應(yīng)防碰撞算法[J].模式識(shí)別與人工智能,2008,21(4):476-481.

[26] 文 超,歐若風(fēng),凌 力.基于自適應(yīng)分裂樹的RFID防碰撞算法[J].計(jì)算機(jī)工程,2011,37(24):287-289.

[27] 徐海峰,姜 暉,劉 振.一種改進(jìn)的RFID自適應(yīng)防碰撞算法[J].計(jì)算機(jī)工程,2012,38(17):290-292.

[28] Bo F,Tao L J,Bo G J,et al.ID-binary tree stack anti-collision algorithm for RFID[C]//Proc of 11th IEEE symposium on computers and communications.Sardinia,Italy:IEEE,2006:207-212.

[29] 張捍東,何明敏.基于狀態(tài)仲裁的鎖位防碰撞算法[J].計(jì)算機(jī)工程,2012,38(15):290-292.

Research on Anti-collision Algorithm of RFID System

CHEN Hong-lin

(School of Management Science and Engineering,Anhui University of Finance and Economics,Bengbu 233030,China)

Multi-tag identification is a common problem in the radio frequency identification,and anti-collision algorithm of multi-tag identification is the key of RFID system research.When the system contains a number of tags,the probability of collision will be greatly increased.In order to improve the efficiency of tag identification and the performance of radio frequency identification,some anti-collision algorithm of RFID system are compared and analyzed.The research situation is analyzed in detail form the characteristics of many anti-collision algorithms and the anti-collision methods based on CDMA and TDMA whose latest results are compared,and the advantage and disadvantage of them are pointed out.Finally,the future research trend is put forward.

radio frequency identification;anti-collision;probabilistic algorithm;deterministic algorithm

2015-08-20

2015-12-17

時(shí)間：2016-09-18

2014安徽省自然科學(xué)基金項(xiàng)目(1408085MF127)；校級(jí)科研項(xiàng)目(ACKY1565)

陳紅琳(1975-)，女，講師，碩士，研究方向?yàn)槲锫?lián)網(wǎng)技術(shù)。

http://www.cnki.net/kcms/detail/61.1450.TP.20160918.1707.014.html

TP301

A

1673-629X(2016)10-0108-05

10.3969/j.issn.1673-629X.2016.10.024