陳 卓（信陽農(nóng)林學(xué)院，河南信陽，464000）

?

基于碰撞預(yù)檢測的分組動態(tài)幀時隙ALOHA防碰撞算法

陳 卓
（信陽農(nóng)林學(xué)院，河南信陽，464000）

本文在分析傳統(tǒng) ALOHA 算法的基礎(chǔ)上，提出了一種基于碰撞預(yù)檢測的分組動態(tài)幀時隙 ALOHA 防碰撞算法。該算法通過分組限制響應(yīng)的標(biāo)簽數(shù)量，并且在組內(nèi)預(yù)先發(fā)送一個短暫的碰撞檢測幀去檢測幀內(nèi)的情況，達(dá)到在閱讀器與標(biāo)簽之間建立一個完全無碰撞信道的目的。仿真結(jié)果表明，當(dāng)標(biāo)簽數(shù)量較大時，該算法能有效減少總數(shù)據(jù)傳輸量，提高識別效率。

射頻識別；防碰撞算法；幀時隙；標(biāo)簽分組

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

1　傳統(tǒng)ALOHA 算法

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

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

2　基于碰撞預(yù)檢測的分組動態(tài)幀時隙ALOHA 算法

基于碰撞預(yù)檢測的分組動態(tài)幀時隙ALOHA 算法（Packet Dynamic Frame Slotted ALOHA Based On Pre-detection，PDSA）是在DFSA算法的基礎(chǔ)上提出，引入預(yù)檢測和分組的環(huán)節(jié)，是一種針對大規(guī)模標(biāo)簽快速識別的改進(jìn)型算法。

2.1算法原理及描述

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

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

表1　標(biāo)簽數(shù)、幀長和分組數(shù)之間的關(guān)系

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

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

2.2算法性能分析

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

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

由于在數(shù)據(jù)傳輸階段是完全無碰撞的，所以系統(tǒng)讀取標(biāo)簽的效率E 為：

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

3　仿真

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

圖1　算法所需時隙數(shù)比較

圖2　算法系統(tǒng)效率比較

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

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

4　結(jié)束語

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

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

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

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

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

［5］ 江雨.物聯(lián)網(wǎng)中的RFID標(biāo)簽防碰撞算法研究［D］.蘭州：西北師范大學(xué)，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-），男，漢族，河南信陽人，助教，碩士研究生，研究方向為檢測技術(shù)與自動化裝置、電子與通信工程、傳感器。