一種改進(jìn)的動態(tài)幀時(shí)隙ALOHA算法

彭　赟

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

?

一種改進(jìn)的動態(tài)幀時(shí)隙ALOHA算法

彭赟

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

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

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

0引言

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

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

1RFID防碰撞分析

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

1.1純ALOHA算法

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

圖1　ALOHA和時(shí)隙ALOHA算法比較圖

1.2時(shí)隙ALOHA算法

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

1.3幀時(shí)隙ALOHA算法

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

圖2　不同長度幀時(shí)隙ALOHA算法

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

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

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

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

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

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

2改進(jìn)的動態(tài)幀時(shí)隙ALOHA算法

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

因此表達(dá)式(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)

因?yàn)樽兞縇，Sc，Ss都是有限常量。因此可以通過β2得到γ2：

(13)

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

(14)

(15)

那么集合{βk}滿足。

(16)

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

(17)

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

(18)

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

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

3仿真結(jié)果分析

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

圖4　仿真結(jié)果

4結(jié)束語

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

參考文獻(xiàn)：

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

[2]鄧曉.一種新的RFID標(biāo)簽數(shù)目估計(jì)方法[J].計(jì)算機(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

文獻(xiàn)標(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