反轉(zhuǎn)查詢樹的動態(tài)幀時隙算法

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

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

中圖分類號：TP391.44

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

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

根據(jù)樹的確定性算法和基于ALOHA概率性算法提出改進(jìn)的標(biāo)簽防碰撞算法。算法首先運(yùn)用查詢樹算法把標(biāo)簽分類，對分類的標(biāo)簽，進(jìn)行了動態(tài)的幀時隙算法的改進(jìn)和讀取。在理想狀態(tài)下，當(dāng)動態(tài)幀時隙算法在運(yùn)行當(dāng)中它的幀長和標(biāo)簽數(shù)目相等的時候，就可以保證系統(tǒng)得到最大的效率。在現(xiàn)實(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)一步的簡化了幀時隙算法的工作，這樣的一種融合就解決了算法的匹配效率低的問題。這種改進(jìn)的方法被稱為基于查詢樹的反轉(zhuǎn)動態(tài)幀的時隙算法（QTR-DFSA，DynamicFrameSlotALOHAbasedonQueryTreewithReversedIDs）。

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

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

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

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

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

2 切比雪夫不等式

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

[5]周曉光，王曉華.射頻識別（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].