改進動態幀時隙ALOHA算法

王玉青，李開宇，孫純鵬

(南京航空航天大學自動化學院，江蘇南京 210016)

RFID技術是近年來應用發展迅速的一種利用射頻通訊方式，實現的無線非接觸式身份識別的技術［1］。RFID技術應用系統主要由RFID電子標簽、讀寫器、計算機通信網絡3部分組成，當系統要閱讀現場貼有RFID標簽的對象時，系統由標簽讀寫器向RFID標簽發送特定頻率的電磁波，RFID標簽經電磁波的觸發，將內部存儲的身份識別碼信息送出，系統通過標簽讀寫器識別貨物并進行相應的信息處理。但是，如果有多個RFID標簽接收到電磁波并同時發送信息，則標簽讀寫器接收到的信號會互相干擾，不可避免地出現標簽碰撞［2］問題。

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

在研究了經典ALOHA型算法的基礎上，提出了一種改進的動態幀時隙ALOHA算法，仿真結果表明，所提出的算法在系統效率和系統時延方面較傳統的算法都有明顯改善。

1 系統描述

假設在DFSA算法［5］的防碰撞系統中，幀長為N，待識別標簽數為n，那么一幀中某個時隙為空閑時隙、可讀時隙和碰撞時隙的概率［5－7］分別為

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

定義系統時延 T［10］

定義系統效率

2 標簽估計

在RFID系統中，標簽到達讀寫器的信息并不是大量連續不斷的，因此很難抽象為某種隨機過程，但標簽會根據接收到的讀寫器指令中的幀長度信息，在該幀長范圍內產生一個隨機數，該隨機數在幀長范圍內平均分布。根據這一點，對發生碰撞的時隙中可能存在的標簽數目做如下估計:

若n個標簽處于讀寫器有效區域內，則選擇一幀中k個標簽選擇時隙i的概率為

若時隙i中發生碰撞，可知選擇時隙i的標簽數目不少于2，從而可推知分布函數為

則時隙i中的標簽數目平均為

再由式(10)得

若要獲得最大系統效率S，要使

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

從而有

根據麥克勞林展開式有

令 x=1/n，則有

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

由上面的推導可知，若某時隙為空，則選擇該時隙的標簽數為零;若信息正確接收，則該時隙中標簽數目為1;若有碰撞發生，則可估算該時隙中的標簽數目為b個。當幀時隙數和標簽數越相近時，系統效率越高。

由此可估算未識別的標簽數目為其中，C2為發生碰撞的時隙數，從而就能根據估算的標簽數目，確定下一幀的長度。

3 幀長確定

通過上面分析可知，為獲得最大的系統性能，只需在每個識別周期內取和標簽數最接近的幀長大小即可。因此提出了一種具體的幀長調整方案:

根據估算出的標簽數目，然后設定相應的幀長，令S(N，n)=S(2N，n)，可得到兩相鄰幀性能曲線，如圖1所示，交點處的標簽數為

從而當未識別標簽數＞nN，2N時將幀長增加一倍，＜ n0.5N，N時幀長減半。

當標簽數＞354時，將標簽進行分組，則m組和2 m組系統性能曲線，如圖2所示，交點處的值nm可由式(21)得出

從而有

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

表1 不同標簽數的最佳幀長和分組數

4 改進算法實現

傳統ALOHA型算法在標簽數目較少時，可以獲得較理想的系統效率，但當標簽數目逐漸增大的時候，通常需要指數倍增長的時隙數才能識別出這些標簽。因此，提出了IDFSA算法，具體改進算法實現如圖3算法流程圖所描述。

圖3 改進算法流程圖

5 仿真結果

從圖4和圖5中可以看出，當標簽數約為250時，FSA算法中系統效率達到最大，之后，系統效率會逐漸降低;DFSA算法在標簽數約＜350時，系統效率保持在0.34以上，當標簽數＞350時，系統效率顯著降低;而IDFSA算法在所設定的標簽數范圍500內，系統效率約穩定在0.35。

為更進一步比較IDFSA算法與DFSA算法，將標簽數增加到1 600。如圖6所示，IDFSA算法在標簽數量＞500時，仍能以約0.35的系統效率工作，而DFSA算法的性能則急劇惡化。

圖7 標簽數最大為500時各算法的系統時延比較

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

6 結束語

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

［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，FRANCESCA L，FRANCESCA 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.