摘要：通過對RFID中的碰撞問題和防碰撞算法進行分析，結(jié)合動態(tài)幀時隙ALOHA算法和動態(tài)二進制搜索算法的優(yōu)點，提出一種基于標(biāo)簽估計和標(biāo)簽識別的混合算法。

關(guān)鍵詞：無線射頻輻射；防碰撞算法；ALOHA算法；二進制搜索

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）15-3514-02

在RFID系統(tǒng)中，常用的標(biāo)簽防碰撞算法有基于時分多路法（TDMA）的ALOHA系列的算法和二進制防碰撞系列算法，而兩種算法需根據(jù)標(biāo)簽的數(shù)量才能發(fā)揮其優(yōu)點。但當(dāng)標(biāo)簽數(shù)量無法估計的情況，單純運用一種算法效率會較低。如能同時運用該兩種算法，結(jié)合動態(tài)幀時隙ALOHA算法和動態(tài)二進制搜索算法的優(yōu)點，能根據(jù)非固定標(biāo)簽數(shù)量，較快速解決碰撞問題。

1 RFID防碰撞算法概述

無線射頻輻射技術(shù)（Radio Frequency Identification，RFID），是20世紀(jì)90年代興起的一項非接觸式的自動識別技術(shù)。它是通過射頻方式進行非接觸式雙向通信，以達(dá)到對目標(biāo)對象自動識別的目的。目前已廣泛應(yīng)用于身份識別、工廠制造、物流管理等領(lǐng)域，也是正在發(fā)展的物聯(lián)網(wǎng)的核心技術(shù)。

在RFID系統(tǒng)中，防碰撞技術(shù)是信號識別的關(guān)鍵技術(shù)之一。當(dāng)只有一個標(biāo)簽位于一個閱讀器的可讀范圍內(nèi)，則可直接進行閱讀。但實際情況，通常會有多個標(biāo)簽同時位于一個閱讀器的可讀范圍。在信道共用、頻率相同的情況下，多個標(biāo)簽同時將信號送入一個閱讀器的讀通道會產(chǎn)生信道爭用，各信號之間互相干擾，產(chǎn)生數(shù)據(jù)碰撞，從而造成閱讀器和標(biāo)簽之間的通信失敗。

在解決碰撞問題中已研究出許多解決方法，目前防碰撞技術(shù)的解決方法為通信技術(shù)常用的多路存取法，基本上有四種。空分多路法（SDMA）、頻分多路法（FDMA）、碼分多路法（CDMA）和時分多路法（TDMA）。前三者基于硬件的技術(shù)，通過改善硬件的條件來解決碰撞問題，但因利用率低、實現(xiàn)成本比較高，所以較少實用。一般采用的是易于更新的軟件方法，即基于時分多路法（TDMA）的ALOHA系列算法和二進制防碰撞系列算法。

2 ALOHA系列算法

2.1 ALOHA算法

ALOHA算法的是一種為交互計算機傳輸設(shè)計的時分多路法的多路存取方法，是一種隨機接入方式。基本原理是：當(dāng)用戶要發(fā)送數(shù)據(jù)幀時，就可以在任何時候發(fā)送，當(dāng)發(fā)生沖突時，沖突的幀被破壞，發(fā)送方就得不到響應(yīng)。當(dāng)標(biāo)簽被識別或不被識別時，都會隨機退避一段時間。退避時間是標(biāo)簽在某個時間內(nèi)隨機產(chǎn)生的隨機數(shù)，因為隨機數(shù)不同，便達(dá)到了避開碰撞的目的。

假設(shè)S為吞吐率，T0為傳輸?shù)囊粋€數(shù)據(jù)包所用的時間，G為交換的數(shù)據(jù)量，Pe為成功完成的概率，x為每秒發(fā)送的幀數(shù)，

則t秒發(fā)送n個數(shù)據(jù)幀的概率為： P（n）=（xt）ne-xt/n！

則在T0內(nèi)發(fā)送信息的概率是： Pe=e-G

所以在2T0沒發(fā)送的概率是： Pe=e-2G

可算得吞吐量為： S=Ge-2G

當(dāng)G=0.5時，吞吐率達(dá)到最大值18.4%。

ALOHA算法最大的優(yōu)點是：算法原理簡單，實現(xiàn)成本較低，當(dāng)標(biāo)簽不多時效率高。 缺點是：1）適應(yīng)于實時性不高的場合，只能用于只讀標(biāo)簽。2）當(dāng)標(biāo)簽數(shù)量越大碰撞的概率越大。

2.2時隙ALOHA算法和動態(tài)時隙ALOHA算法

時隙ALOHA算法采用的是時分隨機多址的方式，在數(shù)據(jù)的傳送總是在同步的時隙內(nèi)才開始，避免了ALOHA算法的部分碰撞，發(fā)生碰撞的時間縮短到T=t。

所以該算法的吞吐量為： S=Ge-G

當(dāng)G=1時，吞吐率達(dá)到最大值36.8%。

但當(dāng)G=1時，標(biāo)簽數(shù)量繼續(xù)增大時，因所有的時隙段的持續(xù)時間與可能存在的標(biāo)簽有關(guān)，且可能只有一個標(biāo)簽處于讀寫器的作用范圍的時候，便出現(xiàn)“死讀”現(xiàn)象，無法讀取。如果標(biāo)簽數(shù)量過小，則會浪費信道。解決方法可采用非固定的時隙。

動態(tài)時隙ALOHA算法原理是通過閱讀器發(fā)送兩個時隙大小不同的時隙，如碰撞標(biāo)簽數(shù)量多，則用下一個請求命令增加時隙數(shù)量，直到發(fā)現(xiàn)一個的標(biāo)簽為止，以此方法找到調(diào)整時隙大小。

2.3幀時隙ALOHA算法、動態(tài)幀時隙ALOHA算法和增強的動態(tài)幀時隙ALOHA算法

幀時隙ALOHA算法把N個時隙作為一個通信單位，幀。標(biāo)簽在每個幀時隙中隨機發(fā)送一次信息，因此傳輸數(shù)量增大，適合傳輸數(shù)量較大的情況。

但由于所有幀具有相同且固定的時隙長度，如時隙ALOHA算法相似的，固定的時間段必直接影響了識別的效率。所以需動態(tài)調(diào)整發(fā)送的時間段。

動態(tài)幀時隙ALOHA算法能根據(jù)每個幀中空閑和碰撞情況動態(tài)的調(diào)整幀長度，在每一個循環(huán)中都利用一個標(biāo)簽估計函數(shù)來修改幀的大小。標(biāo)簽估計函數(shù)是根據(jù)閱讀器反饋的空時隙數(shù)、成功時隙數(shù)和碰撞時隙數(shù)計算下一個識別循環(huán)需要的時隙數(shù)。

增加的動態(tài)幀時隙ALOHA算法是基于對標(biāo)簽數(shù)量的限制或標(biāo)識來改進算法。如分組動態(tài)幀時隙ALOHA算法，通過分組來限制每幀中的響應(yīng)標(biāo)簽數(shù)。后也有提出通過對分組的函數(shù)的改善，提出很多改進的方法。如加入分?jǐn)?shù)參數(shù)和標(biāo)簽分組序號的算法，Gen2協(xié)議的Q值選擇方法。但由于算法復(fù)雜，實現(xiàn)起來困難，所以目前應(yīng)用更多的是動態(tài)幀時隙ALOHA算法。

3 二進制防碰撞系列算法

3.1二進制樹搜索算法

二進制防碰撞算法是由在一個讀寫器和多個標(biāo)簽之間規(guī)定的相互作用（命令和應(yīng)答）規(guī)則構(gòu)成的。

算法實現(xiàn)如下：

1）REQUEST（EPC）：請求序列號。讀寫器發(fā)送一序列號作為參數(shù)給標(biāo)簽，標(biāo)簽把參數(shù)與自己的序列號比較，如果小于或等于，則送回序列號給讀寫器。

2）SELECT（EPC）：選擇標(biāo)簽。讀寫器發(fā)送某個序列號給標(biāo)簽，該序列號的標(biāo)簽將此作為切入開關(guān)。

3）READ-DATA：讀寫數(shù)據(jù)。選中的標(biāo)簽向讀寫器發(fā)送數(shù)據(jù)。

4）UNSELECT：取消選擇。標(biāo)簽進入不作答狀態(tài)。

在參數(shù)與標(biāo)準(zhǔn)序號比較中，運用了二進制樹搜索算法。其思想是通過多次比較，不斷縮小相應(yīng)標(biāo)簽的范圍，直至對唯一標(biāo)簽進行識別，再對以上操作循環(huán)運行，繼續(xù)識別下一個唯一標(biāo)簽，直到全部標(biāo)簽識別完為止。在搜索策略上改善的有自適應(yīng)二叉樹搜索算法、自適應(yīng)查詢數(shù)算法和返回式搜索算法。

3.2動態(tài)二進制樹搜索算法和改進的二進制樹搜索算法

因標(biāo)簽中序列號中還包含了閱讀器發(fā)送來的補充信息，為了避免了序列號中多余部分的傳輸，提高傳輸速度，提出了動態(tài)二進制樹搜索算法，在讀寫器和標(biāo)簽相互作用時，標(biāo)簽序列號去除了補充信息。

對二進制樹搜索算法的改進，有后退式索引算法、有跳躍式樹形算法、二叉樹索索算法、二進制查詢樹算法、二時隙樹RFID標(biāo)簽防碰撞算法、二時隙樹算法等，這些算法都在一定程度上提高了識別的效率。

4 基于ALOHA系列算法和二進制搜索算法的混合算法

在ALOHA系列算法中，由于算法簡單，實現(xiàn)起來成本低，所以較常用，特別是動態(tài)幀時隙ALOHA算法。在標(biāo)簽數(shù)量較多，傳輸數(shù)據(jù)較大時，動態(tài)幀ALOHA算法能發(fā)揮出實時性強的優(yōu)點。但是，ALOHA系列算法對標(biāo)簽的識別是隨機的，所以碰撞機會不確定，當(dāng)發(fā)生碰撞的標(biāo)簽過多，將直接導(dǎo)致算法識別效率下降。

而二進制搜索算法因基于樹的搜索方法，對標(biāo)簽的選擇是可預(yù)測的，所以能在標(biāo)簽數(shù)量比較少的情況下，對標(biāo)簽的識別的能力較強。但由于需要對每個標(biāo)簽進行請求和響應(yīng)互動過程，所以當(dāng)標(biāo)簽數(shù)量過多是，會大大降低算法的識別效率。

所以，如果在實際處理中，當(dāng)標(biāo)簽數(shù)不確定時，可采用動態(tài)幀時隙ALOHA算法和動態(tài)二進制搜索算法結(jié)合的混合算法。把防碰撞問題分為標(biāo)簽估計和標(biāo)簽識別兩個模塊。在標(biāo)簽估計模塊中，因標(biāo)簽數(shù)量可能比較大，所以先采用適合標(biāo)簽數(shù)量較大而比較簡單的動態(tài)幀時隙ALOHA算法對標(biāo)簽數(shù)量進行估計。經(jīng)過估計，進入識別模塊的標(biāo)簽就比較少了，這時再采用動態(tài)幀時隙ALOHA算法對標(biāo)簽初步識別，當(dāng)發(fā)生碰撞的時候，碰撞的標(biāo)簽數(shù)量又當(dāng)前比識別模塊中標(biāo)簽少，再通過二進制搜索算法對標(biāo)簽進行二次識別。繼續(xù)進行下個標(biāo)簽估計、識別，如此循環(huán)，直至所有標(biāo)簽識別完為止。這樣結(jié)合了兩個系列算法對不同標(biāo)簽數(shù)量處理的優(yōu)勢，能大大提高識別效率。

5 結(jié)束語

由以上分析可見，在解決標(biāo)簽碰撞問題中，ALOHA系列算法和二進制搜索算法都各有優(yōu)缺點，在實際處理問題中，可以運用基于ALOHA系列算法和二進制搜索算法的混合算法，發(fā)揮兩者優(yōu)點，較快速解決碰撞問題。

參考文獻(xiàn)：

[1] Kleinberg J，Tardos E.算法設(shè)計[M].張立昂，屈婉玲，譯.北京：清華大學(xué)出版社，2007.

[2] 黃玉蘭.物聯(lián)網(wǎng)：射頻識別（RFID）核心技術(shù)詳解[M].2版.北京：人民郵電出版社，2012.

[3] 董麗華.RFID技術(shù)與應(yīng)用[M].北京：電子工業(yè)出版社，2008.

[4] 王雪.基于二叉樹的RFID防碰撞算法的研究[J].通訊學(xué)報，2010（6）：49-57.

[5] 孫文勝，金陳敏.新型的RFID動態(tài)幀時隙ALOHA防碰撞算[J].信息與控制，2012（4）：233-238.

[6] 王曉東.算法設(shè)計與分析[M].2版.北京：清華大學(xué)出版社，2008.

[7] 丁治國.RFID關(guān)鍵技術(shù)研究與實現(xiàn)[D].合肥：中國科學(xué)技術(shù)大學(xué)，2009.

[9] 程文青，趙夢欣，徐晶.改進的RFID動態(tài)幀時隙A10ho算法[J].華中利技人學(xué)學(xué)報：自然利學(xué)版，2007，35（6）：14，16.