摘 要：RFID（RadioFrequencyIdentification）被稱為無線射頻識(shí)別通信技術(shù)，在發(fā)展的過程中其碰撞問題得到越來越多的人關(guān)注。主要問題出在閱讀器與標(biāo)簽之間的，它包括兩個(gè)方面：閱讀器與標(biāo)簽的通信問題和標(biāo)簽在運(yùn)行當(dāng)中的讀取問題。這兩個(gè)方面影響著技術(shù)的發(fā)展，也相當(dāng)存在著一定的難度。這篇論文根據(jù)了TDMA的確定性的算法和基于ALOHA的概率性算法的綜合，提出了一種融合這兩種算法的優(yōu)缺點(diǎn)的一種新的混合的算法查詢樹的反轉(zhuǎn)動(dòng)態(tài)幀的時(shí)隙算法。

關(guān)鍵詞：QTR-DFSA；標(biāo)簽估算方法；切比雪夫不等式

中圖分類號(hào)：TP391.44

RFID無線射頻識(shí)別通信技術(shù)的標(biāo)簽防碰撞算法分為CDMA（code-divisionmultipleaccess碼分多址、FDMA（frequencydivisionmultipleaccess）頻分多址、TDMA（TimeDivisionMultipleAccess）時(shí)分多址、SDMA（SpaceDivisionMultipleAccess）空分復(fù)用接入。TDMA又可以分為基于樹確定性算法和基于ALOHA概率性算法。

這篇論文根據(jù)了TDMA的確定性的算法和基于ALOHA的概率性算法的綜合，提出了一種融合這兩種算法的優(yōu)缺點(diǎn)的一種新的混合的算法。對(duì)于動(dòng)態(tài)幀時(shí)隙ALOHA算法中它可以動(dòng)態(tài)的調(diào)整幀長以適應(yīng)標(biāo)簽，它的缺點(diǎn)就是調(diào)節(jié)的范圍如果超出了幀長度的調(diào)節(jié)范圍就會(huì)出現(xiàn)多次碰撞。而在查詢樹的算法中只要能夠有足夠長的時(shí)間去識(shí)別，就能夠完全識(shí)別出所有的標(biāo)簽，它也有缺點(diǎn)就是在它的標(biāo)簽數(shù)目過大的時(shí)候，識(shí)別的效率會(huì)大幅度的降低。如果把上面的兩種算法進(jìn)行綜合運(yùn)用，克服各個(gè)算法中的自身缺點(diǎn)就可以得到很好的發(fā)揮?；谶@個(gè)方面就提出了查詢樹的反轉(zhuǎn)動(dòng)態(tài)幀的時(shí)隙算法。在反轉(zhuǎn)查詢樹算法中不單單只是克服了查詢樹的算法的匹配效率低的問題，進(jìn)而也能夠?qū)⒋罅康臉?biāo)簽分類從而能夠適應(yīng)動(dòng)態(tài)幀的時(shí)隙幀長的范圍。最后再接著通過動(dòng)態(tài)幀的時(shí)隙調(diào)整最優(yōu)幀長，能夠正確識(shí)別每一個(gè)標(biāo)簽避免發(fā)生碰撞。

根據(jù)樹的確定性算法和基于ALOHA概率性算法提出改進(jìn)的標(biāo)簽防碰撞算法。算法首先運(yùn)用查詢樹算法把標(biāo)簽分類，對(duì)分類的標(biāo)簽，進(jìn)行了動(dòng)態(tài)的幀時(shí)隙算法的改進(jìn)和讀取。在理想狀態(tài)下，當(dāng)動(dòng)態(tài)幀時(shí)隙算法在運(yùn)行當(dāng)中它的幀長和標(biāo)簽數(shù)目相等的時(shí)候，就可以保證系統(tǒng)得到最大的效率。在現(xiàn)實(shí)生活中的時(shí)候RFID系統(tǒng)的標(biāo)簽數(shù)目要遠(yuǎn)遠(yuǎn)大于幀長的數(shù)目，這就導(dǎo)致了系統(tǒng)的效率降低，甚至出現(xiàn)壞死現(xiàn)象。在這樣的情況下，可以先利用查詢樹算法先將算法標(biāo)簽進(jìn)行分組歸類。查詢樹算法能夠?qū)?biāo)簽分類，而且還減少了標(biāo)簽分組的序列長度，進(jìn)一步的簡化了幀時(shí)隙算法的工作，這樣的一種融合就解決了算法的匹配效率低的問題。這種改進(jìn)的方法被稱為基于查詢樹的反轉(zhuǎn)動(dòng)態(tài)幀的時(shí)隙算法（QTR-DFSA，DynamicFrameSlotALOHAbasedonQueryTreewithReversedIDs）。

1 RFID系統(tǒng)的標(biāo)簽估算方法

標(biāo)簽估算方法可以最大限度使用閱讀器和標(biāo)簽，準(zhǔn)確動(dòng)態(tài)調(diào)整幀長來適應(yīng)待識(shí)別標(biāo)簽的數(shù)目，來減少時(shí)隙的浪費(fèi)，提高運(yùn)算效率。在運(yùn)行估算狀態(tài)下，主要是基于閱讀器和標(biāo)簽的通信狀態(tài)，各個(gè)時(shí)隙出現(xiàn)的狀態(tài)通過輪回識(shí)別過程可以分為三種時(shí)隙。

第一種：閑置時(shí)隙，該運(yùn)行過程中標(biāo)簽還沒有收到發(fā)送到的數(shù)據(jù)信號(hào)，所設(shè)置的時(shí)隙總數(shù)為C0。

第二種：可讀時(shí)隙，該時(shí)隙在運(yùn)行識(shí)別過程中只有一個(gè)標(biāo)簽向其發(fā)送數(shù)據(jù)信號(hào)，并能夠可以成功接收識(shí)別，所以設(shè)置所有可讀的時(shí)隙數(shù)位C1。

第三種：碰撞時(shí)隙，在發(fā)生碰撞識(shí)別的過程中不止一個(gè)標(biāo)簽向其發(fā)送數(shù)據(jù)信號(hào)，所以設(shè)置所有發(fā)生碰撞的時(shí)隙總數(shù)為Ck。

2 切比雪夫不等式

這個(gè)標(biāo)簽算法是由H.Vogt提出，被稱作Vogt-Ⅱ標(biāo)簽估算法。設(shè)幀長為N的閱讀器與n個(gè)標(biāo)簽發(fā)生通信，該算法首先設(shè)置了一個(gè)限制的時(shí)隙數(shù)C0，可讀時(shí)隙數(shù)C1，碰撞時(shí)隙數(shù)Ck，組成一個(gè)向量空間（C0，C1，Ck），然后算出空閑時(shí)隙數(shù)的期望值C0N，η，可讀時(shí)隙數(shù)期望值為C1N，n，碰撞時(shí)隙數(shù)期望值為CkN，n，組成向量空間（C0N，η，C1N，n，CkN，n）。然后再計(jì)算向量之間的距離設(shè)為ξ，在設(shè)置兩個(gè)向量之間的最小標(biāo)簽數(shù)位標(biāo)簽的估計(jì)最小標(biāo)簽數(shù)為nn。

根據(jù)上面的算式也可以得出C0N，η和C1N，n，這樣標(biāo)簽數(shù)目的估算值與實(shí)際標(biāo)簽的數(shù)目值是最接近的，進(jìn)行改進(jìn)的算法也主要針對(duì)閱讀器相對(duì)江大的標(biāo)簽數(shù)量。

3 RFID系統(tǒng)最優(yōu)的幀長分析

利用動(dòng)態(tài)幀時(shí)隙ALOHA算法動(dòng)態(tài)調(diào)整幀長，使系統(tǒng)能夠減少對(duì)幀長的浪費(fèi)，也不會(huì)導(dǎo)致碰撞的重復(fù)頻繁發(fā)生，影響系統(tǒng)的運(yùn)行效率。要設(shè)置幀長為N，對(duì)應(yīng)的時(shí)隙也為N，也就有n個(gè)標(biāo)簽在進(jìn)行閱讀，那么k和標(biāo)簽在某個(gè)時(shí)隙的碰撞概率應(yīng)該滿足二項(xiàng)分布k～B（n，1/N），即： ，可以推導(dǎo)出某一個(gè)時(shí)隙內(nèi)只要有一個(gè)標(biāo)簽被成功識(shí)別的出來的概率和數(shù)學(xué)期望是：

有上面的公式就可以得到估算的標(biāo)簽數(shù)目n，在這里就設(shè)置了標(biāo)簽被成功識(shí)別為已知量，閱讀器的幀長為未知量N，并定義系統(tǒng)的效率公式為：

4 反轉(zhuǎn)標(biāo)簽系列號(hào)查詢樹算法

查詢樹的優(yōu)點(diǎn)是內(nèi)存很小，實(shí)現(xiàn)很簡單，標(biāo)簽跟閱讀器的前綴進(jìn)行比較，就能夠匹配成功，然后發(fā)射前綴后面的序列號(hào)，它的匹配的速度要比二進(jìn)制搜索樹快的多。本算法利用反轉(zhuǎn)查詢樹的動(dòng)態(tài)幀時(shí)隙算法（QTR-DFSA）來進(jìn)行對(duì)標(biāo)簽的動(dòng)態(tài)幀時(shí)隙算法進(jìn)行識(shí)別，運(yùn)用反轉(zhuǎn)標(biāo)簽的序列號(hào)查詢樹算法進(jìn)行標(biāo)簽分類，分為幾組就可以滿足幀長動(dòng)態(tài)調(diào)整范圍，這是這個(gè)算法的核心。利用幀時(shí)隙算法中的系統(tǒng)效率 ，設(shè)它的幀長為2的n次冪，這樣就可以看出，相鄰的幀長的效率交界點(diǎn)為ηn=η2N，設(shè)它的標(biāo)簽數(shù)大于nnode，幀長翻倍，標(biāo)簽數(shù)目要小于nnode時(shí)，幀長就隨之減少一倍。標(biāo)簽數(shù)位 = ，設(shè)置動(dòng)態(tài)幀時(shí)隙的幀長為256，如果標(biāo)簽數(shù)大于256時(shí)，會(huì)發(fā)生碰撞，將改進(jìn)的QTR-DFSA算法特別針對(duì)標(biāo)簽很多的情況。根據(jù)幀長與標(biāo)簽數(shù)的對(duì)應(yīng)關(guān)系，把標(biāo)簽的數(shù)量控制在354之內(nèi)，利用切比雪夫不等式發(fā)生碰撞數(shù)在354之內(nèi)，就可以很容易的通過動(dòng)態(tài)幀時(shí)隙算法來詢問標(biāo)簽。

5 改進(jìn)解析流程圖

（1）最大幀長為256的時(shí)候，閱讀器的標(biāo)簽進(jìn)行正常運(yùn)轉(zhuǎn)；

（2）閱讀器與標(biāo)簽不受外界環(huán)境的相互干擾；

（3）標(biāo)簽彼此之間相互獨(dú)立，不存在發(fā)生碰撞信息；

（4）采用切比雪夫不等式就可以計(jì)算出標(biāo)簽的大概數(shù)目。

6 結(jié)束語

上面主要是對(duì)動(dòng)態(tài)幀時(shí)隙ALOHA算法和查詢樹算法的基礎(chǔ)上做出的相應(yīng)的基本的改進(jìn)技術(shù)，提出了一種基于反轉(zhuǎn)查詢樹的動(dòng)態(tài)幀時(shí)隙ALOUA算法。提出這個(gè)算法的思想是因?yàn)榉崔D(zhuǎn)標(biāo)簽的序列號(hào)的查詢樹算法，他解決了標(biāo)簽發(fā)生碰撞問題，解決了匹配的效率低的問題。通過計(jì)算標(biāo)簽數(shù)目，再通過動(dòng)態(tài)幀時(shí)隙算法進(jìn)行動(dòng)態(tài)調(diào)整它的最佳的幀長，進(jìn)而能夠識(shí)別標(biāo)簽。比單獨(dú)的算法有很大的提升。

參考文獻(xiàn)：

[1]王曉華，周曉光.射頻識(shí)別技術(shù)及其應(yīng)用[J].現(xiàn)代電子技術(shù)，2005：43-44.

[2]NTTCOMWARE株式會(huì)社研究開發(fā)部（著），鄭維強(qiáng)（譯）.RFID的現(xiàn)狀和發(fā)展趨勢[M].北京：人民郵電出版社，2007：P12.

[3]中華人民共和國科學(xué)技術(shù)部.中國射頻識(shí)別RFID技術(shù)政策白皮書[S].2007，9.

[4]譚民，劉禹，曾雋芳.RFID技術(shù)系統(tǒng)工程及應(yīng)用指南[M].北京：機(jī)械工出版社，2007：90-91.

[5]周曉光，王曉華.射頻識(shí)別（RFID）技術(shù)原理與應(yīng)用實(shí)例[M].北京：人民郵電出版社，2006.

[6]VogtH.EfficientobjectidentificationwithpassiveRFIDtags[J].IEEEPervasiveConputing.2002，14（10）：98-113.

[7]BonuccelliMA，LonettiF，MartelliF.InstantcollisionresolutionfortagidentificationinRFIDnetworks[J].AdHocNetworks，2007，5（8）：l220-1232.

[8]J.Myung，W.Lee，T.K.Shih.AnAdaptiveMemorylessProtocolforRFIDTagCollisionArbitration[J].IEEETransactionsonMultimedia，VoL8（5），October2006：1096-1101.

[9]ChoJ.S，ShinJ.D，KimS.K.RFIDtaganti-collisionprotocol：QuerytreewithreversedIDs[C].