王玉青，李開宇，孫純鵬

(南京航空航天大學(xué)自動(dòng)化學(xué)院，江蘇南京 210016)

RFID技術(shù)是近年來應(yīng)用發(fā)展迅速的一種利用射頻通訊方式，實(shí)現(xiàn)的無線非接觸式身份識別的技術(shù)［1］。RFID技術(shù)應(yīng)用系統(tǒng)主要由RFID電子標(biāo)簽、讀寫器、計(jì)算機(jī)通信網(wǎng)絡(luò)3部分組成，當(dāng)系統(tǒng)要閱讀現(xiàn)場貼有RFID標(biāo)簽的對象時(shí)，系統(tǒng)由標(biāo)簽讀寫器向RFID標(biāo)簽發(fā)送特定頻率的電磁波，RFID標(biāo)簽經(jīng)電磁波的觸發(fā)，將內(nèi)部存儲(chǔ)的身份識別碼信息送出，系統(tǒng)通過標(biāo)簽讀寫器識別貨物并進(jìn)行相應(yīng)的信息處理。但是，如果有多個(gè)RFID標(biāo)簽接收到電磁波并同時(shí)發(fā)送信息，則標(biāo)簽讀寫器接收到的信號會(huì)互相干擾，不可避免地出現(xiàn)標(biāo)簽碰撞［2］問題。

目前解決RFID標(biāo)簽碰撞問題主要是基于兩種防碰撞算法［3］:基于ALOHA的隨機(jī)性算法和基于二進(jìn)制樹的確定性算法。其中，前者是采用隨機(jī)選擇發(fā)送時(shí)間的方式，復(fù)雜度及對標(biāo)簽的要求較低［4］，系統(tǒng)識別的可靠性較差，但易于設(shè)計(jì)實(shí)現(xiàn);后者則采用二叉樹的搜索算法，系統(tǒng)識別的可靠性較高，但系統(tǒng)實(shí)現(xiàn)時(shí)需要與RFID標(biāo)簽的識別碼信息相聯(lián)系，硬件設(shè)計(jì)較復(fù)雜，且識別時(shí)間相較長。因此，低成本的RFID標(biāo)簽一般是采用基于ALOHA的防碰撞算法設(shè)計(jì)，如何提高該算法系統(tǒng)識別的可靠性，是目前低成本RFID標(biāo)簽應(yīng)用系統(tǒng)的研究重點(diǎn)。

在研究了經(jīng)典ALOHA型算法的基礎(chǔ)上，提出了一種改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA算法，仿真結(jié)果表明，所提出的算法在系統(tǒng)效率和系統(tǒng)時(shí)延方面較傳統(tǒng)的算法都有明顯改善。

1 系統(tǒng)描述

假設(shè)在DFSA算法［5］的防碰撞系統(tǒng)中，幀長為N，待識別標(biāo)簽數(shù)為n，那么一幀中某個(gè)時(shí)隙為空閑時(shí)隙、可讀時(shí)隙和碰撞時(shí)隙的概率［5－7］分別為

因此，一幀中平均的空閑時(shí)隙、可讀時(shí)隙和碰撞時(shí)隙［8－9］數(shù)目分別為

定義系統(tǒng)時(shí)延 T［10］

定義系統(tǒng)效率

2 標(biāo)簽估計(jì)

在RFID系統(tǒng)中，標(biāo)簽到達(dá)讀寫器的信息并不是大量連續(xù)不斷的，因此很難抽象為某種隨機(jī)過程，但標(biāo)簽會(huì)根據(jù)接收到的讀寫器指令中的幀長度信息，在該幀長范圍內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)，該隨機(jī)數(shù)在幀長范圍內(nèi)平均分布。根據(jù)這一點(diǎn)，對發(fā)生碰撞的時(shí)隙中可能存在的標(biāo)簽數(shù)目做如下估計(jì):

若n個(gè)標(biāo)簽處于讀寫器有效區(qū)域內(nèi)，則選擇一幀中k個(gè)標(biāo)簽選擇時(shí)隙i的概率為

若時(shí)隙i中發(fā)生碰撞，可知選擇時(shí)隙i的標(biāo)簽數(shù)目不少于2，從而可推知分布函數(shù)為

則時(shí)隙i中的標(biāo)簽數(shù)目平均為

再由式(10)得

若要獲得最大系統(tǒng)效率S，要使

由式(5)，式(8)，式(13)得

從而有

根據(jù)麥克勞林展開式有

令 x=1/n，則有

再由式(15)，式(17)有

由上面的推導(dǎo)可知，若某時(shí)隙為空，則選擇該時(shí)隙的標(biāo)簽數(shù)為零;若信息正確接收，則該時(shí)隙中標(biāo)簽數(shù)目為1;若有碰撞發(fā)生，則可估算該時(shí)隙中的標(biāo)簽數(shù)目為b個(gè)。當(dāng)幀時(shí)隙數(shù)和標(biāo)簽數(shù)越相近時(shí)，系統(tǒng)效率越高。

由此可估算未識別的標(biāo)簽數(shù)目為其中，C2為發(fā)生碰撞的時(shí)隙數(shù)，從而就能根據(jù)估算的標(biāo)簽數(shù)目，確定下一幀的長度。

3 幀長確定

通過上面分析可知，為獲得最大的系統(tǒng)性能，只需在每個(gè)識別周期內(nèi)取和標(biāo)簽數(shù)最接近的幀長大小即可。因此提出了一種具體的幀長調(diào)整方案:

根據(jù)估算出的標(biāo)簽數(shù)目，然后設(shè)定相應(yīng)的幀長，令S(N，n)=S(2N，n)，可得到兩相鄰幀性能曲線，如圖1所示，交點(diǎn)處的標(biāo)簽數(shù)為

從而當(dāng)未識別標(biāo)簽數(shù)＞nN，2N時(shí)將幀長增加一倍，＜ n0.5N，N時(shí)幀長減半。

當(dāng)標(biāo)簽數(shù)＞354時(shí)，將標(biāo)簽進(jìn)行分組，則m組和2 m組系統(tǒng)性能曲線，如圖2所示，交點(diǎn)處的值nm可由式(21)得出

從而有

標(biāo)簽數(shù)nN，2N、nm分別為調(diào)整幀長和分組數(shù)的臨界點(diǎn)，一旦待識別標(biāo)簽數(shù)達(dá)到該臨界點(diǎn)時(shí)，就調(diào)整相應(yīng)幀長或分組數(shù)大小。實(shí)驗(yàn)證明本方案可使系統(tǒng)達(dá)到最佳效率。當(dāng)標(biāo)簽數(shù)為n時(shí)，重新調(diào)整幀長和分組數(shù)，如表1所示，其中表中臨界點(diǎn)附近的標(biāo)簽數(shù)目是令系統(tǒng)效率范圍為34.6%～36.8% 時(shí)確定的。

表1 不同標(biāo)簽數(shù)的最佳幀長和分組數(shù)

4 改進(jìn)算法實(shí)現(xiàn)

傳統(tǒng)ALOHA型算法在標(biāo)簽數(shù)目較少時(shí)，可以獲得較理想的系統(tǒng)效率，但當(dāng)標(biāo)簽數(shù)目逐漸增大的時(shí)候，通常需要指數(shù)倍增長的時(shí)隙數(shù)才能識別出這些標(biāo)簽。因此，提出了IDFSA算法，具體改進(jìn)算法實(shí)現(xiàn)如圖3算法流程圖所描述。

圖3 改進(jìn)算法流程圖

5 仿真結(jié)果

從圖4和圖5中可以看出，當(dāng)標(biāo)簽數(shù)約為250時(shí)，F(xiàn)SA算法中系統(tǒng)效率達(dá)到最大，之后，系統(tǒng)效率會(huì)逐漸降低;DFSA算法在標(biāo)簽數(shù)約＜350時(shí)，系統(tǒng)效率保持在0.34以上，當(dāng)標(biāo)簽數(shù)＞350時(shí)，系統(tǒng)效率顯著降低;而IDFSA算法在所設(shè)定的標(biāo)簽數(shù)范圍500內(nèi)，系統(tǒng)效率約穩(wěn)定在0.35。

為更進(jìn)一步比較IDFSA算法與DFSA算法，將標(biāo)簽數(shù)增加到1 600。如圖6所示，IDFSA算法在標(biāo)簽數(shù)量＞500時(shí)，仍能以約0.35的系統(tǒng)效率工作，而DFSA算法的性能則急劇惡化。

圖7 標(biāo)簽數(shù)最大為500時(shí)各算法的系統(tǒng)時(shí)延比較

從圖7可以看出，隨著標(biāo)簽數(shù)的增加，系統(tǒng)完全識別所有標(biāo)簽所需系統(tǒng)時(shí)延逐漸增加。但當(dāng)標(biāo)簽數(shù)目＞120時(shí)，IDFSA算法相對于FSA算法、DFSA算法在在識別相同數(shù)目的標(biāo)簽時(shí)所消耗的時(shí)間要少很多;特別地，當(dāng)標(biāo)簽數(shù)為500時(shí)，IDFSA算法比DFSA算法的系統(tǒng)時(shí)延減少約1倍，并且隨著標(biāo)簽數(shù)的增加，這種減少的趨勢將越來越明顯。

6 結(jié)束語

針對目前基于ALOHA防碰撞算法中各種幀長調(diào)整方案的優(yōu)缺點(diǎn)，提出了一種簡單易行的幀長確定方法:當(dāng)未識別標(biāo)簽數(shù)低于閾值354時(shí)，IDFSA算法所需時(shí)隙數(shù)將隨標(biāo)簽數(shù)的增加而線形增長;當(dāng)未識別標(biāo)簽數(shù)大于閾值354時(shí)，通過分組限制每幀中的應(yīng)答標(biāo)簽數(shù)，讀寫器每次詢問只有一組標(biāo)簽響應(yīng)。從而動(dòng)態(tài)地調(diào)整幀長和分組數(shù)，提高了系統(tǒng)效率并減少了計(jì)算和操作的復(fù)雜度。仿真結(jié)果顯示，采用IDFSA算法在標(biāo)簽數(shù)＜16 000時(shí)，均能以約35%的系統(tǒng)效率工作;而DFSA算法在標(biāo)簽數(shù)大于350時(shí)，系統(tǒng)效率顯著降低，性能急劇惡化。在識別相同數(shù)目的標(biāo)簽所消耗系統(tǒng)時(shí)延方面，當(dāng)標(biāo)簽數(shù)約＞120時(shí)，IDFSA算法比DFSA算法、FSA算法減少較多系統(tǒng)時(shí)延，而且隨著標(biāo)簽數(shù)的增加，這種減少的趨勢將更加明顯。因此，在大量標(biāo)簽數(shù)情況下，采用IDFSA算法可使系統(tǒng)效率達(dá)到最佳，系統(tǒng)時(shí)延最少。

［1］WANT R.An introduction to RFID technology［J］.IEEE Pervasive Computing，2006，5(1):25 －33.

［2］VOGT H.Multiple object identification with passive RFID tags［C］.Hammamet，Tunisia:Proceedings of the IEEE International Conference on Systems，Man，And Cybernetics，2002:6－11.

［3］MAURIZIO A B，F(xiàn)RANCESCA L，F(xiàn)RANCESCA M.Instant collision resolution for tag identification in RFID networks［J］.Ad Hoc Networks，Elsevier，2007，5(8):1220 －1230.

［4］KLEINROCK L，LAM SS.Packet switching in a multi－ access broadcast channel:performance evaluation［J］.IEEE Transactions on Communications，1975，23(4):410 －423.

［5］VOGT H.Multiple object identification with passive RFID tags［C］.Hammamet，Tunisia:Proceedings of IEEE International Conference on Systems，Man，and Cybernetics，2002:1－6.

［6］VOGT H.Efficient object identification with passive RFID tags［C］.Zurich，Switzerland:Proceedings of International Conference on Pervasive Computing，2002:98 －113.

［7］CHA JR，KIM J H.Novel anti－ collision algorithms for fast object identification in RFID system［C］.Washington D.C，USA:Proceedings of the 11th International Conference on Parallel and Distributed Systems，2005:63 －67.

［8］LEE SR，JOO SD，LEE C W.An enhanced dynamic framed ALOHA algorithm for RFID tag identification［C］.Washington D.C.，USA:Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems:Networking and Services，2005:166 －174.

［9］BONUCCELLI M A，LONETTI F，MARTELLI F.Tree slotted ALOHA:a new protocol for tag identification in RFID networks［C］.New York，USA:Proceedings of the International Symposium on a World of Wireless，Mobile and Multimedia Networks，2006.603 －608.

［10］CHA J，KIM J.Novel anti－ collision algorithms for fast object identification in RFID system［C］.Ultra USA:IEEE Proc.2005 11th Int'lConf.Parallel and Distributed Systems(ICPADS)，2005(2):63－67.