董輝 盛魁 馬健 姚宏亮

摘 要：為解決射頻識別系統(tǒng)中多標簽碰撞問題及提高系統(tǒng)性能，在綜合分析基于時隙Aloha協(xié)議多種防碰撞算法的基礎上，提出一種基于標簽分組先來先服務的自適應幀時隙Aloha防碰撞算法（TG-FCFS ADFSA）.該算法通過對標簽分組和先來先服務及幀時隙預約策略，自適應分配成功時隙來快速識別標簽，極大地提高了RFID系統(tǒng)性能.MATLAB仿真結果證明：TG-FCFS ADFSA算法在標簽數(shù)量越多識別優(yōu)勢越明顯，特別是標簽數(shù)量超過1 000時，該算法比DSFA，GDFSA算法標簽吞吐率提高1倍以上，時隙開銷降低50%以上，系統(tǒng)識別效率和穩(wěn)定性明顯提高.

關鍵詞：射頻識別；防碰撞；幀時隙；分組序化

中圖分類號：TN911. 23 DOI：10.16375/j.cnki.cn45-1395/t.2018.01.011

0 引言

射頻識別（Radio Frequency Identification，RFID）技術是利用無線射頻方式進行非接觸雙向通信，以實現(xiàn)自動識別和遠程實時監(jiān)控及管理[1]，被廣泛應用于交通、物流、制造及公共安全及信息服務等領域[2].在RFID系統(tǒng)中，閱讀器以廣播方式發(fā)布的命令可被信號區(qū)內所有標簽監(jiān)聽到，這種方式造成多個標簽可同響應閱讀器命令，產(chǎn)生彼此干擾，極易發(fā)生標簽碰撞[3].囿于技術實現(xiàn)、制造成本及功耗等諸多因素，當前RFID系統(tǒng)防碰撞算法主要采用時分多路訪問控制技術[4].防碰撞算法主要有3種：①基于搜索樹的防碰撞算法[5]；②基于Aloha協(xié)議的防碰撞算法[6]；③搜索樹和Aloha協(xié)議的混合算法[7].其中②類算法由于標簽內部電路設計、實現(xiàn)過程簡單而被廣泛應用，但會因標簽數(shù)的增多，出現(xiàn)標簽丟失和隨機后識別等不良現(xiàn)象[8]，標簽碰撞的概率增加，導致RFID系統(tǒng)的識別率迅速下降.

通過對多種防碰撞算法的研究，提出了基于標簽分組先來先服務的自適應分配幀時隙Aloha（Tag-Group First Come First Service Adaptive Allocating Dynamic-Frame-Slotted Aloha，TG-FCFS ADFSA）算法，該算法在RFID系統(tǒng)識別標簽時首先采用Vogt算法估算標簽數(shù)，在一次識別任務中，當待識別標簽數(shù)目在355以內時，采用動態(tài)幀時隙（DFSA）算法識別標簽，當待識別的標簽數(shù)達到356以上時，在對標簽分組并序化，并采用先來先服務方式，結合動態(tài)幀長調整及幀時隙自適應分配等策略對標簽進行識別.

1 基于Aloha協(xié)議的算法

純Aloha協(xié)議算法由于信息發(fā)送的隨機性，導致極易發(fā)生信息碰撞，識別率和吞吐率都較低，吞吐率最高約為18.4%[9]；時隙Aloha（SA）算法碰撞概率為純Aloha協(xié)議算法的一半，標簽吞吐率約為36.8%[10]；幀時隙Aloha（FSA）防碰撞算法是把若干時隙組成幀，一個時隙唯一被一個標簽選中，則標簽被識別，否則即碰撞[11].FSA算法因識別速度快被廣泛采用，但缺點是若待識別標簽數(shù)遠小于或大于幀長，系統(tǒng)吞吐率則又會變得很低.動態(tài)幀時隙Aloha （DFSA ）防碰撞算法是根據(jù)待識別標簽數(shù)量，動態(tài)調整幀時隙數(shù)與標簽數(shù)盡可能的接近，使算法的識別效率接近或達到最佳值，但如何估算出標簽數(shù)量又成為該算法的難點，為此，一些學者設計了相關估值方法，如有Vogt算法、Cratio算法、Schoute 算法和 Low Bound 算法等.

1.1 TG-FCFS ADFSA算法基礎

1.1.1 幾個基本概念

1） 標簽丟失率

RFID系統(tǒng)在一次標簽識別過程中，在有限的逗留時間內識別信號區(qū)未被閱讀器識別標簽數(shù)與待識別標簽總數(shù)之比即為標簽丟失率.標簽丟失率與RFID系統(tǒng)的吞吐率、識別效率等密切相關，是衡量RFID系統(tǒng)性能的一個重要指標.

2） 隨機后識別

基于Aloha協(xié)議的防碰撞算法，標簽隨機選擇時隙與閱讀器進行信息交互，可能造成先進入識別區(qū)的標簽被后識別，即隨機后識別現(xiàn)象[8].這種現(xiàn)象是導致標簽丟失的原因之一，但是如果通過增加標簽的逗留時間弱化這一問題又會影響系統(tǒng)的吞吐率，本文通過標簽分組序化操作，來弱化標簽識別的隨機性，降低標簽丟失率提高識別率.

3） 3種時隙及吞吐率

時隙僅被一個標簽選中請求識別即為成功時隙，時隙沒有被任何標簽選中響應即為空閑時隙，若一個時隙被2個以上的標簽選擇則為碰L撞時隙.根據(jù)文獻[12]，一個時隙內標簽響應的概率為：

1.2 TG-FCFS ADFSA算法關鍵步驟

1）估算待識別的標簽總數(shù)

本文根據(jù)對幾種常見估算算法的進行比較分析，發(fā)現(xiàn)Vogt算法估算誤差較小且穩(wěn)定[10]，通過實測的與預期的3種時隙數(shù)的比較分析，估算誤差最小，所以本文采用該算法標簽數(shù)，Vogt公式如下：

其中，Ci，Cs，Cc分別表示一幀的空閑、成功、碰撞時隙數(shù)，對d取最小值n，即是估算的待識別的標簽數(shù).

2）標簽分組序化操作策略

① 標簽分組策略

如果n的值在355以內，使用動態(tài)幀時隙算法直接對標簽識別，無需分組，如表1所示.

在許多應用場景，信號區(qū)待識別標簽數(shù)目較多，因受到標簽存儲、成本等因素局限，幀長最大值通常取Lmax=256，若標簽數(shù)n≥356，則按進入識別區(qū)的時間先后分組，每個分組內標簽數(shù)最大值為355，以最大幀長對每組標簽進行識別，依據(jù)表2對標簽分組.

② 標簽分組序化相關概念

標簽分組序化是指在標簽進入信號區(qū)以后，根據(jù)進入的時間段順序按表2規(guī)則對標簽分組，每組賦予一個序列號（Serial Number，SN），同組內的標簽SN相同，非同組的SN不同，此過程稱之為標簽分組序化.間隔的時間段為分組序化周期（Period of Tag_Serialing， PTS）.

③ 標簽分組的序化策略

為提高RFID系統(tǒng)的吞吐率和識別率，本文算法采用循環(huán)隊列方法對標簽組序化.循環(huán)隊列的數(shù)據(jù)結構是一維數(shù)組空間S，有S[0]至S[15]16個元素，頭尾指針header、rear初值均為0，數(shù)組S的每個元素存儲相應時序標簽組的標簽數(shù).當rear超過數(shù)組元素個數(shù)時，rear置0，重新開始循環(huán)隊列.

當信號區(qū)標簽數(shù)n≥356，以表2的方法對標簽進行分組，令新標簽SN=rear，之后rear=（rear+1）% 16（注：%為取模運算符，下同），經(jīng)過此運算，得到可以反復使用的SN循環(huán)隊列{0，1，2，3，…，14，15}.通常情況下，RFID系統(tǒng)中一次識別任務通常不會多于2 000，把標簽組最多為16是合理的，若分組過多，幀時隙就不能有效利用.

標簽組的序化步驟如下：

Step 1 閱讀器開始工作，每隔一段時間發(fā)送序含參數(shù)head和rear的序化命令SC（Sequencing Command），head=rear=0，表示識別區(qū)內沒有分組被序化.

Step 2 識別區(qū)內標簽對響應SC命令分為2種情形：

A 若標簽的SN≠NULL，則表示該標簽已被序化，不再響應此命令，標簽SN值不變.

B 若標簽的SN=NULL，則說明該標簽是新進入識別區(qū)的，令SN=rear后，再rear =（rear+1） % 16，標簽加入最新標簽分組.圖1為標簽組序化操作實現(xiàn)示例.

標簽組序化偽代碼如下：

Reader：

Flag_point： If mod（Identity_Time，PTS）==0 //識別時間每過PTS

{Send SC（header，rear //閱讀器發(fā)送序化命令SC（head，rear）

Tag：If（not Receive SC） // 信號區(qū)內的標簽未收到SC（head，rear）命令

{ if （header == rear） {goto Flag_Point；} }

Else { If （tag' s SN==Null） { Tag' s SN =rear； Send Ack； }

//新進入識別區(qū)的標簽加入最新標簽分組， 標簽發(fā)送Ack確認信號

Else { Tag' s SN is unchanged；}

}

Reader：

If（ Receive Ack ） { rear = （rear +1） % 16；} //經(jīng)過取模運算， rear指針指向新的隊尾

Else { rear is unchanged； }

3） 標簽組先來先服務

在標簽分組序化操作策略中，信號區(qū)內的標簽被分成多組，當閱讀器發(fā)送查詢命令，若標簽組SN與命令參數(shù)相等可響應.標簽組先來先服務就是指擁有最早時間序列號的標簽響應閱讀器的指令.

標簽組先來先服務的步驟：

Step 1 閱讀器發(fā)送帶有參數(shù)header的標簽組識別命令IC（header） （Identify_Command，IC），識別具有最早時序號的標簽.

Step 2 每一幀循環(huán)結束后，IC （header）的執(zhí)行情況如下：

A 若具有最早SN的標簽全被識別，header =（header +1）%16，即header指向下個標簽組；

B 若具有最早SN的標簽未全被識別，header值不變，下個幀循環(huán)繼續(xù)識別該組的標簽.

標簽組先來先服務偽代碼如下：

Reader： Send IC （head）； // 閱讀器發(fā)送擁有最早標簽組序號的識別命令

Tag：Receive IC （head）； //標簽收到識別命令

If （Tag' s SN =head） { Tag response to IC （head）；} //標簽應答閱讀器的識別命令

Else {Tag no response to IC（head）； }

Reader： If（a frame cycle is finished） //一次幀循環(huán)結束

{ if （there is unIdentityIdentitied Tag） //有未識別的出現(xiàn)碰撞

{Reader' s header is unchanged； }

Else { Reader' s header=（header +1）%16； } // head+1取模，指向下一個標簽組

2 TG-FCFS ADFSA算法實現(xiàn)步驟

TG-FCFS ADFSA算法流程如圖2所示，實現(xiàn)過程可分為以下幾個階段：

Step 1 標簽數(shù)量估算和分組序化

①簽數(shù)量估算： 在識別開始階段，用Vogt 算法估算出標簽的數(shù)目n.

②分組序化：

A 當n≤355時，直接調用DFSA算法識別標簽.

B 當n≥356時，閱讀器根據(jù)表2計算標簽分組數(shù)g，同時定義一個初值為0計數(shù)變量i，并發(fā)出時序命令SC（header，rear），對標簽分組序化，每個標簽分組獲得時序編號SN.

Step 2 判定最早時序標簽分組是否存在

閱讀器廣播一個時間組開始命令TC（header），確定最早時序分組是否還在識別區(qū)內.該命令執(zhí)行的結果有2種情況：

①識別區(qū)內不存在標簽組SN與header相等，說明最早時序標簽組已不存在，閱讀器的header =（header+1）%16，即進入下一個時序標簽組識別過程，計數(shù)變量i=i+1.

②若識別信號區(qū)內存在標簽組SN=header，則表示最早時序標簽組仍在信號區(qū)內且組內還有被識別的標簽，此類標簽發(fā)出ACK信號.

Step 3 幀時隙分配

當閱讀器收到標簽的ACK后，立刻發(fā)送幀開始命令FSC（M），標簽收到命令其時隙計數(shù)器隨機生成①個時隙號，每個標簽都發(fā)送自己的時隙號，預約時隙.閱讀器根據(jù)標簽的預約，判斷出成功、空閑或碰撞的時隙，成功時隙標志位Flag =0，否則Flag =-1，根據(jù)時隙預約的情況，閱讀器發(fā)出Update（ ）命令，每個標簽知通過此命令可獲其他標簽預約時隙的情況.

Step 4 標簽識別階段

①閱讀器發(fā)送識別命令IC（header），擁有最早時序號SN =header的標簽才可響應，標簽向發(fā)送自己的ID，閱讀器直接對獲得成功時隙的標簽進行識別，即標簽組先來先服務，同時閱讀器發(fā)送Sleep（ ）指令，被正確識別的標簽變成靜默狀態(tài)，不以節(jié)省時隙開銷.

②閱讀器檢查當前幀是否結束

A 否，進入當前幀下一時隙，繼續(xù)識別最早時序標簽

B 是，檢查最早時序標簽組內是否有未識別的標簽，若有，則header指針不變，跳到Step 3，開始下一幀，再次進行時隙分配，直到將該時序組的標簽被識別完；若無，header= （head+1）%16，標簽組計算變量 i=i+1.

Step 5 判斷i值，若i≤g，則說明存在沒有被識別的標簽分組，下一組變?yōu)樽钤鐣r序組，轉到Step 3，開始新的幀，進入下一組標簽的識別過程；若i>g，則所有標簽分組都被識別完，算法運行結束.

3 算法分析與仿真比較

本文提出的TG-FCFS ADFSA算法，最大為幀長256，標簽僅需8位二進制數(shù)電路，所需存儲空間為8bit，與EPC C1G2協(xié)議[12]需要20位隨機二進制數(shù)產(chǎn)生電路要簡單的多，所以TG-FCFS ADFSA算法得標簽電路更為簡單，減少了標簽制造成本.同時為了驗證TG-FCFS ADFSA算法的有效性，將本文提出的算法與DFSA及其改進GDFSA算法進行比較分析，仿真實驗環(huán)境為Windows7，4G DDR4，i5-7500 CPU，仿真軟件MATLAB 2016b.假設標簽空間分布相對平均，待識別的標簽數(shù)初值為20，結合實際情況，上限不超過1 600，為了更準確的分析與驗證，在同等環(huán)境下仿真結果取100次實驗的均值，對比三者標簽的吞吐率、時隙開銷及識別率情況.

3.1 標簽的吞吐率比較

在MATALAB上對DFSA，GDFSA和TG-FCFS ADFSA 這3種算法進行仿真，得到的吞吐率曲線如圖3.

TG-FCFS ADFSA算法采用了標簽的預估算法Vogt、標簽分組及先來先服務策略、動態(tài)幀調整策略、幀時隙自適應算法等，克服了DFSA算法在標簽數(shù)快速增多吞吐率急速下降的劣勢，同時相比GDFSA算法，TG-FCFS ADFSA算法在吞吐率、穩(wěn)定性方面仍具有很大的優(yōu)勢.在標簽數(shù)不多于355時，算法吞吐率曲線基本相同，當標簽數(shù)n≥356，DFSA算法的吞吐率持續(xù)下降，當標簽數(shù)n =1 600時，吞吐率下降到0.1以下，吞吐率極低；GDFSA算法先對對標簽分組，吞吐率可穩(wěn)定36%左右，但基于標簽分組先來先服務動態(tài)幀時隙自適應算法，吞吐率可達到0.6左右，其性能曲線明顯最優(yōu)，當標簽數(shù)n>1 000以上時，相比DFSA和GDFSA算法，TG-FCFS ADFSA算法效率分別提高約200%和99%，當標簽數(shù)量更多是，算法效率會更高.

3.2 時隙消耗總數(shù)分析

在標簽識別過程中，RFID系統(tǒng)消耗的時隙總消耗數(shù)愈少系統(tǒng)性能愈優(yōu)秀.通過仿真實驗，3種算法所消耗的時隙總數(shù)如圖4所示，可以看出當標簽數(shù)增到1 000以后，DFSA算法指數(shù)增長，GDFSA和TG-FCFS ADFSA算法線性增長，但TG-FCFS ADFSA算法增長最慢，可見TG-FCFS ADFSA算法的優(yōu)勢明顯，TG-FCFS ADFSA算法的效率遠遠高于DFSA 算法和 GDFSA 算法.

3.3 標簽的丟失率與識別率

通過仿真實驗，比較在不同標簽密度情況下，3種算法標簽的丟失率如圖5所示，從中可以看出相同密度的情況下，TG-FCFS ADFSA算法的標簽丟失率顯然比其他2種算法要低許多，相應的，TG-FCFS ADFSA算法標簽的吞吐率和識別率就為最高，可以看出，TG-FCFS ADFSA算法大幅度減少標簽碰撞的概率，該算法比DFSA和GDFSA算法識別率更高，可提高RFID識別系統(tǒng)的性能.

4 結論

本文提出一種基于標簽分組先來先服務的RFID電子標簽防碰撞算法，該算法首先對標簽數(shù)量進行預估，其次當標簽數(shù)大于355時對標簽分組并序化操作，然后采用標簽分組先來先服務及自適應分配幀時隙的策略，對標簽進行快速識別.通過仿真實驗表明隨電子標簽數(shù)量的快速增加，尤其是數(shù)量大于1 000時，系統(tǒng)的時隙開銷與其他算法相比較少，但標簽吞吐率仍保持在較高水平且穩(wěn)定性較好，有效地提高了電子標簽的總的識別效率，而且通過上文的分析可知標簽電路復雜度又低，可降低標簽的生產(chǎn)成本，因此本文算法具有較好的應用前景.

參考文獻

[1]趙嘉，曾文波.一種用于智能交通系統(tǒng)標簽天線的設計與仿真[J].廣西工學院學報，2010 ，21（1）：73-76，89.

[2]何維，張彥會，粟騰超，等.基于GPS/GPRS/RFID物流車載終端的設計[J]. 廣西科技大學學報，2014，25（4）：59-62.

[3]QIAN Z H，WANG X.An Overview of anti-collision protocols for Radio frequency identification devices[J].China Communications，2014，11（11）：44-59.

[4]陳紅琳.RFID 系統(tǒng)防碰撞算法研究[J].計算機技術與發(fā)展，2016，26（10）：108-112.

[5]YANG G H，MA J C，CUI L，et al. Study on the improved recession binary tree algorithm[J]. Advanced Materials Research， 2014. 1006-1007：1076-1079.

[6]WANG Y P， SHENG H， WANG X L，et al. Anti-collision algorithm analysis of a LOHA-based RFID[J]. Applied Mechanics and Materials，2013，273（1）：745-749.

[7]YAN X Q，YIN Z P，XIONG Y L.A hybrid collision resolution protocol for passive RFID Tag Identification[J]. International Journal of Distributed Sensor Networks，2010，5（1）：84-90.

[8]李曉武.移動RFID系統(tǒng)標簽識別技術的研究[D].成都：西南交通大學，2014.

[9]單劍鋒，陳 明，謝建兵.基于ALOHA算法的RFID防碰撞技術研究[J]. 南京郵電大學學報（自然科學版），2013，33（1）：56-61.

[10]陳榮征.改進的基于動態(tài)幀時隙 ALOHA 防碰撞算法[J].齊齊哈爾大學學報（自然科學版），2016，32（1）：21-25，35.

[11]LI X W，WANG Z J，REN X，et al. A improved frame slotted aloha protocol with early end in mobile RFID systems[J].Sensors & Transducers，2013（7）：82-86.

[12]王勇，李婷. 改進的基于 ALOHA 的 RFID 防碰撞算法[J].電信科學，2016，32（8）：77-81.

Abstract：Based on the comprehensive analysis of various tag frame slotted Aloha tag anti-collision algorithms， the TG-FCFS ADFSA anti-collision algorithm is presented to solve the problem of collision between multi-tag and improve the efficiency in RFID system. The algorithm can quickly identify the tags by adaptively allocating the successful slots， which greatly improves the performance of the RFID system through the strategy of the tag groups FCFS （First Come First Service） and the reserved frame slots. Matlab simulation results show the identification advantage of the algorithm is obvious in the case of more tags， especially when the number of tags is over 1000， throughput of the algorithm is over doubled than the DSFA or GDFSA algorithm， but the slot consumption is reduced by more than 50%， the identification efficiency and stability of system are obviously improved.

Key words： RFID （radio frequency identification）； anti-collision； frame slots； serialization of tag group

（學科編輯：張玉鳳）