彭　赟

(常州信息職業(yè)技術(shù)學(xué)院電子與電氣工程學(xué)院　江蘇常州　213164)

?

一種改進的動態(tài)幀時隙ALOHA算法

彭赟

(常州信息職業(yè)技術(shù)學(xué)院電子與電氣工程學(xué)院江蘇常州213164)

摘要：隨著射頻識別(RFID)的廣泛應(yīng)用，防碰撞算法性能的優(yōu)劣成為制約其進一步發(fā)展的關(guān)鍵因素。以原始動態(tài)幀時隙ALOHA算法為基礎(chǔ)，結(jié)合一種更加精確的標(biāo)簽數(shù)目估算法，從而動態(tài)地設(shè)置下一幀的時隙數(shù)，以改善防碰撞性能，MATLAB仿真結(jié)果表明該算法能夠顯著提高標(biāo)簽識別效率。

關(guān)鍵詞：射頻識別； 防碰撞； ALOHA

0引言

RFID[1](Radio Frequency Identification)是一種利用無線射頻信號獲得特定對象數(shù)據(jù)的自動識別技術(shù)，由于其具有識別速度快、無需人工干預(yù)等優(yōu)點，因而在庫存管理、考勤、身份識別等領(lǐng)域得到廣泛的應(yīng)用，被業(yè)界公認(rèn)為物聯(lián)網(wǎng)的四大核心技術(shù)之一。

當(dāng)讀卡器識別范圍內(nèi)存在大量待識別電子標(biāo)簽時，不可避免地發(fā)生信息碰撞，該問題嚴(yán)重制約著RFID更為廣泛的發(fā)展與應(yīng)用。因此，需要一種可靠的算法用于解決多標(biāo)簽識別碰撞問題。目前，主要存在二進制搜索法及ALOHA兩類算法[2]。由于ALOHA算法具有簡單、便于實現(xiàn)等優(yōu)點，因而得到了廣泛的應(yīng)用。ALOHA算法的發(fā)展分為四個階段：純ALOHA、時隙ALOHA、幀時隙ALOHA及動態(tài)幀時隙ALOHA。待識別標(biāo)簽數(shù)估計的精確度是動態(tài)幀時隙ALOHA算法的關(guān)鍵，當(dāng)前存在一些較可靠的標(biāo)簽數(shù)目估算法，例如Schoute[3]標(biāo)簽估算法及Vogt[4]等提出的一些算法。然而，Schoute標(biāo)簽估算法為：未識別的標(biāo)簽數(shù)=碰撞時隙數(shù)*每個碰撞時隙中碰撞標(biāo)簽個數(shù)的數(shù)學(xué)期望值，該數(shù)學(xué)期望一般固定為2.39，該算法具有實現(xiàn)簡單、計算量較小、系統(tǒng)識別效率得到提高等優(yōu)點，然而，當(dāng)待識別標(biāo)簽達到一定數(shù)量時，估算值與實際值誤差較大。此外，Vogt等人提出的標(biāo)簽數(shù)目估算法，具有計算量大且對概率特別敏感等缺點。本文以動態(tài)幀時隙ALOHA算法為基礎(chǔ)，結(jié)合一種簡單且準(zhǔn)確的標(biāo)簽估計算法，從而大幅度提高識別系統(tǒng)效率。

1RFID防碰撞分析

從本質(zhì)上來說射頻識別中電子標(biāo)簽信息碰撞問題是多址接入問題，當(dāng)讀卡器識別范圍內(nèi)存在大量待識別標(biāo)簽時，碰撞問題將更加嚴(yán)重，為了有效地解決該問題，一系列防碰撞算法應(yīng)運而生。其中，使用較為廣泛的為ALOHA類算法，其發(fā)展歷程共經(jīng)歷了四個階段：純ALOHA、時隙ALOHA、幀時隙ALOHA及動態(tài)幀時隙ALOHA。

1.1純ALOHA算法

純ALOHA算法[5]的思想是只要電子標(biāo)簽有數(shù)據(jù)要發(fā)送，就盡管讓其發(fā)送。這個過程雖會出現(xiàn)信息沖突，但由于廣播信道具有反饋性，當(dāng)發(fā)送方(電子標(biāo)簽)知道數(shù)據(jù)幀遭到破壞，那么在隨機長的一段時間后將再次發(fā)送數(shù)據(jù)，如果發(fā)送過程中未發(fā)生沖突則表明數(shù)據(jù)傳輸成功，電子標(biāo)簽將進入休眠狀態(tài)，重復(fù)上述步驟直到讀卡器將所有電子標(biāo)簽都成功識別。ALOHA算法思想簡單實用，其最大吞吐率可達18.4%，如圖1中虛線段所表示。

圖1　ALOHA和時隙ALOHA算法比較圖

1.2時隙ALOHA算法

純ALOHA算法中，假設(shè)電子標(biāo)簽傳遞一次數(shù)據(jù)所消耗的時間為T，電子標(biāo)簽發(fā)送數(shù)據(jù)時刻為0，則在(-T,+T)區(qū)間內(nèi)不能有其他標(biāo)簽發(fā)送數(shù)據(jù)，否則都會引起數(shù)據(jù)沖突。因此，純ALOHA算法的碰撞區(qū)間長為2T，若將時間劃分為若干個時隙，所有電子標(biāo)簽只能在時隙的開始時刻發(fā)送數(shù)據(jù)而非任意時刻，從而可以將碰撞區(qū)間長度減小為T，系統(tǒng)的吞吐率將提高一倍最高可達36.8%，這便是時隙ALOHA算法[5]如圖1實線所示。

1.3幀時隙ALOHA算法

觀察圖1可以發(fā)現(xiàn)隨著讀卡器識別范圍內(nèi)待識別電子標(biāo)簽數(shù)量的增加，純ALOHA算法與時隙ALOHA算法性能急劇下降。于是有研究人員提出幀時隙ALOHA算法[6]，其思想是：將若干時隙打包成一個幀，待識別電子標(biāo)簽隨機選擇幀時隙中一個特定的時隙號，并在該時隙內(nèi)與讀卡器進行通信，電子標(biāo)簽同樣只能在時隙的開始時刻發(fā)送數(shù)據(jù)，圖2為分別取幀長64、128及256時，識別0～500個標(biāo)簽所需消耗的總時隙數(shù)的仿真圖。

圖2　不同長度幀時隙ALOHA算法

1.4動態(tài)幀時隙ALOHA算法

觀察圖2發(fā)現(xiàn)，當(dāng)待識別標(biāo)簽數(shù)較少時，幀時隙數(shù)為64的算法相對于幀長為128及256的算法效率略高，然而隨著待識別電子標(biāo)簽數(shù)的大幅增加，幀時隙數(shù)為64的算法性能急劇下降，而幀時隙數(shù)為256則優(yōu)勢顯著。針對該問題，有學(xué)者提出了動態(tài)幀時隙ALOHA算法[7]，根據(jù)當(dāng)前識別過程中的碰撞時隙比例與空時隙比例的取值大小，動態(tài)地調(diào)整下一幀時隙長度。其工作流程如下所示：

①根據(jù)實際應(yīng)用狀況設(shè)定幀的初始幀時隙長度為F。

②讀卡器發(fā)送一幀時隙數(shù)為F的清點指令，等待標(biāo)簽應(yīng)答，讀寫器根據(jù)標(biāo)簽的回應(yīng)狀況，分別統(tǒng)計出空時隙數(shù)、碰撞時隙數(shù)及成功識別標(biāo)簽時隙數(shù)。

③如果碰撞時隙數(shù)為0，則結(jié)束識別過程，否則計算空時隙、碰撞時隙及成功識別時隙各自占總時隙數(shù)的百分比，如果碰撞時隙數(shù)占總時隙數(shù)的比例大于70%，則將下一輪讀卡器發(fā)送的幀時隙數(shù)加倍；如果空時隙數(shù)占總時隙數(shù)的比例大于30%，則將下一輪讀卡器發(fā)送幀時隙數(shù)減半；否則下一輪讀卡器發(fā)送的時隙數(shù)不變。

④調(diào)整幀的長度，轉(zhuǎn)入步驟②進入新一輪的讀卡周期直至完成所有電子標(biāo)簽的識別。

2改進的動態(tài)幀時隙ALOHA算法

研究表明當(dāng)幀長與待識別電子標(biāo)簽數(shù)相同時，系統(tǒng)的吞吐率可保持為最大值36.8%。而原始動態(tài)幀時隙ALOHA算法，僅根據(jù)上輪識別后的統(tǒng)計數(shù)據(jù)，將下一幀時隙數(shù)做乘2、除2或不變等三種操作，無法達到理想的識別效率。如下為本文所示一種精確的標(biāo)簽估計法，通過該估算法能夠較為精確地估出待識別標(biāo)簽數(shù)，從而將下一幀時隙數(shù)設(shè)為算法估算的輸出值，能夠大幅度提高系統(tǒng)的效率。

假設(shè)幀的時隙數(shù)L等于標(biāo)簽數(shù)n與一個合適因子β的乘積，可以得到表達式(1)

(1)

發(fā)生碰撞后，假設(shè)產(chǎn)生碰撞后未識別的標(biāo)簽數(shù)為γ*sc。那么backlog(下一幀時隙數(shù))通過公式(2)獲得

(2)

式(2)中ss和sc分別表示成功識別的時隙數(shù)和發(fā)生碰撞的時隙數(shù)。n個標(biāo)簽中有γ個標(biāo)簽占據(jù)同一個時隙的概率接近于二項式分布，如表達式(3)所示：

(3)

若幀的大小L足夠大，則式(3)接近于泊松分布，當(dāng)γ=0，則在一個時隙中無標(biāo)簽占有的概率為表達式(4)

(4)

在式(3)中，當(dāng)γ=1時，只有一個標(biāo)簽占據(jù)一個時隙時得到如下表達式：

(5)

因此表達式(2)左半部分接近于

(6)

其中β=L/n為式(1)中的β，式(2)中的右邊為：

(7)

聯(lián)立式(2)，(6)，(7)可以得到：

(8)

ss和sc能夠在幀長為L的幀中測得。β能夠

通過式(1)，(2)和(8)獲得。

(9)

那么backlog估算為：

(10)

然而通過式(8)很難找到求解β和γ的解法。因此，提出一種用于求解β和γ的迭代算法。使βk和γk分別為β和γ的第k次迭代值。首先令x=1/(β1)，并且假設(shè)β→∞(x→0)，那么γ1可通過式(8)利用羅必塔法則求得：

(11)

式(1)和(2)表明，β2能夠通過γ1推斷。

(12)

因為變量L，Sc，Ss都是有限常量。因此可以通過β2得到γ2：

(13)

式(8)表明變量γ和β都呈現(xiàn)反向比例關(guān)系，如圖3所示。并可以因為β2<β1，β3<β2，所以γ3<γ2，從而可以得到迭代算法。

(14)

(15)

那么集合{βk}滿足。

(16)

因為{βk}是有界單調(diào)遞減的序列，有一個極限值。因此，序列{βk}轉(zhuǎn)成有限值可以使用迭代式(14)，(15)及β1=∞，γ1=2開始尋找第k*次迭代式γk*的值。當(dāng)滿足下列條件的閾值∈threshold時：

(17)

那么backlog(下一幀的幀長)可以通過以下式(18)求得：

(18)

式(14)和(15)表明選擇一個合適的閾值∈threshold時可以迅速獲合適的γ，并通過式(18)求得下一輪合適的幀長。

圖3　β和γ的關(guān)系

3仿真結(jié)果分析

圖4為MATLAB對原始動態(tài)幀時隙ALOHA(DFSA)算法與改進算法取100次平均值進行比較得到的結(jié)果，改進算法中閾值∈threshold設(shè)為0.001。兩算法初始時刻幀時隙數(shù)均為64，待識別標(biāo)簽數(shù)在0～1 000之間變化，可以發(fā)現(xiàn)當(dāng)識別區(qū)域內(nèi)只有少量待識別電子標(biāo)簽(0～200)時，兩種算法性能相當(dāng)。隨著識別區(qū)域內(nèi)的電子標(biāo)簽數(shù)的不斷遞增，改進算法效率優(yōu)勢逐漸體現(xiàn)出來，當(dāng)電子標(biāo)簽數(shù)在600左右時，效率提高了近25%；當(dāng)電子標(biāo)簽數(shù)為1 000時，改進算法消耗的時隙數(shù)為原算法的52%，效率提高了近一倍。

圖4　仿真結(jié)果

4結(jié)束語

本文將一種精確的標(biāo)簽估算法與動態(tài)幀時隙ALOHA算法相結(jié)合，以提高RFID系統(tǒng)的識別效率，并從公式推導(dǎo)及MATLAB仿真兩方面，驗證了算法的科學(xué)性及有效性。但需要進一步探索性能優(yōu)良的防碰撞算法，以促進RFID更廣泛地應(yīng)用與發(fā)展，為人們的生活帶來更多的方便。

參考文獻：

[1]王鑫，賈慶軒，高欣.基于位圖構(gòu)建的RFID自適應(yīng)N樹防碰撞算法[J]. 上海交通大學(xué)學(xué)報，2015, 49(2): 150-157.

[2]鄧曉.一種新的RFID標(biāo)簽數(shù)目估計方法[J].計算機工程與應(yīng)用，2012, 48(5): 142-144.

[3]Schoute, F. Dynamic Frame Length ALOHA[J].Communications, IEEE Transactionson, 1983, 31(4): 565-568.

[4]H Vogt.Efficient object identification with passive RFID tags [J].in Proc. International Conference on Pervasive Computing，2012, 28(5): 98-113.

[5]Chen W T, Lin G H. An efficient anti-collision method for tag identification in a RFID system [J]. IEICE Trans Commun，2006, 89(12): 3389-3392.

[6]J R. Cha, J H Kim. Novel anti-collision algorithms for fast object identification in RFID system [J]. in Proc. International Conference on Parallel and Distributed Systems, 2005, 2(5): 63-67.

[7]Vinod Nam, Lixin Gao. Energy-Aware Tag Anti-collision Protocols for RFID System [J]. IEEE Transactions on Mobile Computing, 2012, 9(1): 44-59.

收稿日期：2016-04-20

作者簡介：彭赟(1987-)，男，碩士，主要研究方向：嵌入式開發(fā)、射頻通信

中圖分類號：TP 391.44

文獻標(biāo)志碼：A

文章編號：1672-2434(2016)03-0027-04

An Improved Dynamic Frame Slotted ALOHA Algorithm

PENG Yun

(School of Electronic and Electrical Engineering, Changzhou College of Information Technology, Changzhou 213614, China)

Abstract：With the wide use of RFID, the drawback of anti-collision algorithm is a key factor which has restricted its development. Based on the dynamic frame slot ALOHA algorithm, this paper proposes an accurate tag estimation algorithm. The simulation results show that the improved algorithm can significantly improve the efficiency of system identification.

Key words：RFID; anti-collision; ALOHA