基于碰撞預檢測的分組動態幀時隙ALOHA防碰撞算法

陳 卓（信陽農林學院，河南信陽，464000）

?

基于碰撞預檢測的分組動態幀時隙ALOHA防碰撞算法

陳 卓
（信陽農林學院，河南信陽，464000）

本文在分析傳統 ALOHA 算法的基礎上，提出了一種基于碰撞預檢測的分組動態幀時隙 ALOHA 防碰撞算法。該算法通過分組限制響應的標簽數量，并且在組內預先發送一個短暫的碰撞檢測幀去檢測幀內的情況，達到在閱讀器與標簽之間建立一個完全無碰撞信道的目的。仿真結果表明，當標簽數量較大時，該算法能有效減少總數據傳輸量，提高識別效率。

射頻識別；防碰撞算法；幀時隙；標簽分組

射頻識別技術（Radio Frequency Identification，RFID）是90年代開始興起的一種自動識別技術，它利用無線射頻方式在閱讀器和電子標簽之間進行非接觸的雙向數據通信，以達到信息識別的目的。當 RFID 系統運行時，常有很多處于閱讀器作用范圍之內的標簽在同一時刻向閱讀器傳輸信息，就不可避免地出現相互干擾的現象，稱為碰撞。深入研究防碰撞算法有助于進一步提升 RFID 系統對標簽的識別效率。

1　傳統ALOHA 算法

目前，防碰撞算法一般采用時分多路方式（Time Division Multiple Access，TDMA），主要分為以下兩類：基于二叉樹的確定性算法和基于ALOHA的隨機性算法。本文主要對后者進行分析。

純 ALOHA算法是最簡單最基本的一種防碰撞算法。當標簽進入閱讀器的識別范圍內時主動向閱讀器發送自身信息，閱讀器只有在準確識別出一個標簽后才與該標簽進行通信。對于多個不同的標簽來說，由于發送時間隨機，不同標簽的數據發送時間就可能發生沖突。這種算法容易實現，但最大吞吐率（系統效率）只有18.4%，故實際應用中很少使用。固定幀時隙 ALOHA算法（Basic Framed Slotted ALOHA，BFSA）將信道分成許多離散幀，每一幀由若干個時隙組成，大小固定不變，幀中每個時隙長度要能夠完成一個標簽與閱讀器之間的通信。標簽在每個幀內隨機選擇一個時隙向閱讀器發送應答信息，閱讀器將成功識別的標簽“滅活”，不再響應后續的操作。與純ALOHA算法相比，BFSA使沖突時間減半，將最大吞吐率提高到36.8%。但當標簽數遠大于時隙數時，系統耗時會大幅度增加；而當標簽數遠小于時隙數時，則會造成時隙浪費。動態幀時隙 ALOHA算法（Dynamic Framed Slotted ALOHA，DFSA）根據每幀中的空閑和碰撞情況動態調整幀長度，從而保證時隙數與標簽數量相當，使系統獲得最佳吞吐率。然而在實際應用中，由于硬件限制，幀長度不能無限增加，否則會導致系統耗時呈指數增長，識別效率急劇下降。

2　基于碰撞預檢測的分組動態幀時隙ALOHA 算法

基于碰撞預檢測的分組動態幀時隙ALOHA 算法（Packet Dynamic Frame Slotted ALOHA Based On Pre-detection，PDSA）是在DFSA算法的基礎上提出，引入預檢測和分組的環節，是一種針對大規模標簽快速識別的改進型算法。

2.1算法原理及描述

本算法識別標簽共分為三個階段，分別為：標簽分組、碰撞檢測和信息傳輸。

首先估算待識別的標簽數，與設定的最大幀長度Lmax=256進行對比，當待識別的標簽數遠大于Lmax時，將場內標簽分為待命組和休眠組，規定只允許待命組標簽響應且待命組標簽個數定為 256個，休眠組的標簽暫不響應。當待識別的標簽數低于Lmax時，閱讀器將不再進行分組，而只是按動態幀時隙的方法來識別標簽。當閱讀器限制了部分能響應閱讀器查詢的標簽數量后，在前一幀結束和后一幀開始的中間間隔，閱讀器廣播分組信息及幀長，標簽在接收到該信息后，設置自己的狀態并生成自身的組內識別碼。待識別標簽的數量、幀長度與分組數有如下關系：

表1　標簽數、幀長和分組數之間的關系

在分組結束后，閱讀器就要對組內標簽進行識別，本算法引入了碰撞預檢測思想。閱讀器在識別組內標簽前，預先發送一個信道爭用指令，以激活在其作用范圍內的所有標簽。標簽接收指令后，需先同步時鐘，然后同步進入信道爭用周期。標簽的隨機數產生器產生一個范圍為［1，N］（N為碰撞檢測時隙數）的整數Nr并存儲在標簽寄存器中，作為時隙順序數。進入數據傳輸階段，所有標簽按照各自的發送順序，發送一個短暫檢測幀，用以檢測該時隙內的碰撞情況。在每個時隙中，都會有三種可能情況：碰撞時隙、空閑時隙和可讀時隙。

依據碰撞檢測階段的檢測結果，閱讀器計算出最小的可讀時隙序號，處在這個時隙內的標簽就在該時隙內與閱讀器進行數據交換，實現標簽信息的無差錯傳輸。標簽成功識別后，閱讀器就對該標簽發出“滅活”指令，使其不再響應后續任何指令。閱讀器向后查詢次小的可讀時隙序號，繼續建立與標簽之間的通信及操作。而那些發生碰撞或者空閑的時隙內，閱讀器不再與標簽通信，直接跳躍式查詢。如此循環，直到閱讀器作用范圍內沒有標簽響應為止。

2.2算法性能分析

設閱讀器周圍有n個待識別標簽，碰撞檢測的時隙數為N，那么下一個時隙中出現m個標簽的概率服從二項分布。

成功識別的概率為m=1時的概率P1，此時在一幀中無沖突時隙的個數Ns為：

由于在數據傳輸階段是完全無碰撞的，所以系統讀取標簽的效率E 為：

式中，Lr為每個成功讀取標簽信息的時隙長度，Lc為每個碰撞檢測階段的時隙長度，將式（2）代入式（3）可得：

3　仿真

利用Matlab環境對BFSA算法、DFSA算法和PDSA算法仿真，記錄三種算法在標簽數從0遞增到1000時，全部標簽識別完成所需要消耗的時隙數和系統效率，并進行比較分析。假設一幀中最大時隙數為256，BFSA算法的固定幀長度為256，DFSA算法的幀長度動態取值為16~256。本文算法初始最小幀長度為16，且取值為20。

圖1　算法所需時隙數比較

圖2　算法系統效率比較

從圖1中可以看出，隨著標簽數的增多，BFSA算法消耗的時隙數幾乎呈指數增長；DFSA算法在標簽數較少的時候呈一種線性關系，但超過500以后，時隙數增長趨勢較快；PDSA算法在標簽數小于256時，和DFSA相當，但隨著標簽數增大幾乎保持一種線性關系，在相同標簽數的情況下，PDSA算法所需的時隙數最少。從圖2中可以看出，系統的識別效率在標簽數大于300

以后呈下降趨勢，BFSA和DFSA算法的識別效率最高能達到約36%，而PDSA算法識別效率大幅度提高，最高能達到約86%。這是因為引入了預檢測和分組的環節對標簽合理分組，使組內標簽數目與幀長度相匹配，且充分利用了前一次檢測時隙的結果，有效避免傳輸過程中的碰撞，從而達到一個較高的識別效率。

4　結束語

本文在分析傳統 ALOHA 算法的基礎上，提出了一種基于碰撞預檢測的分組動態幀時隙 ALOHA 防碰撞算法。該算法通過分組的方式限制響應的標簽數量，并且在組內預先發送一個短暫的碰撞檢測幀去檢測幀內的情況，使閱讀器與標簽之間建立了一個完全無碰撞的信道，有效減少總數據傳輸量，提高識別效率。

［1］ 李青青.RFID防碰撞算法研究［D］.南昌：南昌航空大學，2012：23-40.

［2］ 劉佳，張有光.基于時隙的RFID防碰撞算法分析［J］.電子技術應用，2007，33（5）：94-96.

［3］ 尹君，何怡剛，李兵.基于分組動態幀時隙的RFID防碰撞算法［J］.計算機工程，2009，35（20）：267-269.

［4］ 單劍峰，謝建兵，莊琴清.基于分組的動態幀時隙ALOHA防碰撞算法研究［J］.計算機技術與發展，2011，21（11）：39-45.

［5］ 江雨.物聯網中的RFID標簽防碰撞算法研究［D］.蘭州：西北師范大學，2012：26-32.

Packet Dynamic Frame Slotted ALOHA Anti-collision Algorithm Based On Pre-detection

Chen Zhuo
（XinYang College Of Agriculture And Forestry，XinYang，464000，China）

This paper proposes a packet dynamic frame slotted ALOHA anti-collision algorithm based on Predetection by analyzing traditional ALOHA Algorithms.It can limit the number of response tags through grouping，and send a short collision-detection frame in advance to detect the in-frame situation，in order to create a collision-free channel between readers and tags.Simulation results show that，when the number of tags is large，the algorithm can effectively reduce the total amount of transferred data and inprove the identification efficiency.

RFID；anti-collision algorithm；frame slot；tag packet

陳卓（1989-），男，漢族，河南信陽人，助教，碩士研究生，研究方向為檢測技術與自動化裝置、電子與通信工程、傳感器。