分段式位隙分組幀時隙Aloha算法

邢志鵬，楊恒新,張 昀

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

分段式位隙分組幀時隙Aloha算法

邢志鵬，楊恒新,張 昀

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

自從射頻識別(RFID)技術(shù)越來越頻繁地應(yīng)用于各種場合，提高RFID標(biāo)簽的識別效率就成為了一個重要任務(wù)。文中在FSA的基礎(chǔ)上，結(jié)合位隙分組分析，提出分段式位隙分組幀時隙Aloha算法。該算法將位隙分為兩段，在標(biāo)簽發(fā)生碰撞時，由該時隙內(nèi)發(fā)生碰撞的標(biāo)簽先后發(fā)送前后兩段位隙標(biāo)志位進(jìn)行再識別：若在前段位隙中成功識別該時隙內(nèi)所有碰撞的標(biāo)簽，則進(jìn)入下一個時隙的標(biāo)簽識別；若經(jīng)過前段位隙再識別后仍存在碰撞標(biāo)簽，則繼續(xù)發(fā)送后段位隙進(jìn)行識別。理論分析表明，當(dāng)位隙分為等長兩部分時，系統(tǒng)吞吐率曲線在一定標(biāo)簽數(shù)量(文中取10 000)范圍內(nèi)可以保持平坦，在吞吐率達(dá)到65%以上的同時，系統(tǒng)通信量達(dá)到最低。

射頻識別；防碰撞算法；Aloha；位隙分組

0 引 言

作為物聯(lián)網(wǎng)的關(guān)鍵技術(shù)之一，RFID是一種利用空間耦合或電磁感應(yīng)傳遞射頻信號進(jìn)行無接觸的自動識別技術(shù)[1-4]。早在20世紀(jì)70年代，大量的研究人員就開始投身于RFID技術(shù)的研究。進(jìn)入21世紀(jì)后，隨著物聯(lián)網(wǎng)概念的提出，RFID得到了更多的關(guān)注并廣泛應(yīng)用于服務(wù)業(yè)、制造業(yè)等行業(yè)。

由于RFID標(biāo)簽可以無需視距地從遠(yuǎn)距離(比如2～3 m)被高速閱讀(比如每秒100標(biāo)簽)，因此RFID技術(shù)在眾多應(yīng)用中變得越來越普遍。在大多數(shù)情況下，一個RFID系統(tǒng)由一系列閱讀器和電子標(biāo)簽組成。閱讀器通常是一個具有足夠內(nèi)存和讀寫區(qū)域的有源設(shè)備。標(biāo)簽用于標(biāo)識物件，可分為有源標(biāo)簽、半有源標(biāo)簽和無源標(biāo)簽。其中，無源標(biāo)簽具有工藝簡單、價格低廉、使用壽命長等諸多優(yōu)點，實際應(yīng)用規(guī)模較大。無源標(biāo)簽從閱讀器的電磁場中獲取數(shù)據(jù)傳輸所需要的能量[5]。RFID系統(tǒng)正常運行時，閱讀器查詢它閱讀區(qū)域內(nèi)的電子標(biāo)簽，同時激活電子標(biāo)簽內(nèi)部的射頻兼容電路來產(chǎn)生足夠的能量進(jìn)行必要的操作和數(shù)據(jù)傳輸。電子標(biāo)簽使用這些能量可以生成回送給閱讀器的應(yīng)答。一旦閱讀器獲取到電子標(biāo)簽回送過來的應(yīng)答，就立即從后端服務(wù)器(或者數(shù)據(jù)庫)中檢索對應(yīng)標(biāo)簽的信息[6]。

在標(biāo)簽應(yīng)答收集階段，閱讀器通過共享的無線通信信道識別每一個電子標(biāo)簽。當(dāng)閱讀器查詢區(qū)域內(nèi)的多個電子標(biāo)簽同時向閱讀器應(yīng)答時，信號會互相碰撞[7]，閱讀器將無法識別合法標(biāo)簽。這種現(xiàn)象干擾了閱讀器對標(biāo)簽的識別過程，浪費了更多的帶寬，花費了更高的通信開銷，而且提高了標(biāo)簽識別過程中的傳輸時延。因此，一個有效的標(biāo)簽信號碰撞仲裁機制是快速識別RFID系統(tǒng)中不可或缺的[8]。

傳統(tǒng)的基于Aloha的概率型算法存在的缺陷：由于閱讀器發(fā)出的幀長有限，而多標(biāo)簽響應(yīng)具有很大的隨機性，因此，可能導(dǎo)致某一標(biāo)簽在相當(dāng)長的一段時間內(nèi)無法被識別。而且，當(dāng)查詢范圍內(nèi)標(biāo)簽數(shù)量繼續(xù)增大時，系統(tǒng)性能會急劇下降、能耗大、出現(xiàn)“標(biāo)簽饑餓”現(xiàn)象。改進(jìn)型Aloha算法大多將查詢范圍內(nèi)的標(biāo)簽分組，從而解決一幀中標(biāo)簽數(shù)量大的問題。而標(biāo)簽分組本身就存在隨機性，且反復(fù)地對標(biāo)簽進(jìn)行分組增加了指令開銷，附加了額外的通信量[9]。

在研究經(jīng)典Aloha以及相關(guān)改進(jìn)算法的基礎(chǔ)上，文中提出一種分段式位隙分組幀時隙Aloha算法。該算法通過分段的位隙標(biāo)志位對一個碰撞時隙內(nèi)的標(biāo)簽進(jìn)行再識別，從而有效避免了多余時隙的傳送，在保持高吞吐率的同時減少了系統(tǒng)的通信總量。

1 經(jīng)典標(biāo)簽防碰撞算法及其改進(jìn)算法

現(xiàn)存RFID系統(tǒng)的防碰撞算法主要分為兩類：標(biāo)簽防碰撞算法和閱讀器防碰撞算法。標(biāo)簽防碰撞算法又可分成兩類：確定型算法和概率型算法。

確定型算法又稱為樹型算法，主要是基于標(biāo)簽ID的搜索協(xié)議：閱讀器通過改變查詢命令，使標(biāo)簽基于ID號逐級分組，直到有唯一的標(biāo)簽被閱讀器識別為止?；跇涞姆琅鲎菜惴ㄖ饕═S(Tree Splitting)、BT(Binary Tree)、BS(Binary Search)、QT(Query Tree)、CT(Collision Tree),以及在CT上改進(jìn)的ICT(Improved Collision Tree)。

傳統(tǒng)的概率型RFID防碰撞算法包括PA(Pure Aloha)、SA(Slotted Aloha)、FSA(Frame Slotted Aloha)。其中FSA又衍生出BFSA(Basic Frame Slotted Aloha)、DFSA(Dynamic Frame Slotted Aloha)以及EDFSA(Enhanced Dynamic Frame Slotted Aloha)[10]。

FSA算法把若干個時隙分為一幀，在一輪查詢中，標(biāo)簽隨機選擇幀內(nèi)時隙對閱讀器做出響應(yīng)。當(dāng)兩個以上的標(biāo)簽選擇了同一時隙時，就會發(fā)生碰撞。發(fā)生碰撞的標(biāo)簽只得等到下一幀進(jìn)行識別。

文獻(xiàn)[11]中提出了一種位隙分組幀時隙算法(BGFSA)。該算法把一定長度的位隙標(biāo)志位(設(shè)為2L位)置于標(biāo)簽ID的后面，標(biāo)簽響應(yīng)閱讀器時隨機選取位隙標(biāo)志位中一位為1，其余全為0，在發(fā)生碰撞時，閱讀器解析出置1位隙標(biāo)志位的位置，然后從高到低依次把位置信息回傳給標(biāo)簽，沖突時隙內(nèi)的標(biāo)簽對該位置信息進(jìn)行匹配，匹配成功的標(biāo)簽再向閱讀器應(yīng)答。理論上，在一個沖突時隙內(nèi)，最多可識別出2L個沖突的標(biāo)簽。

2 位隙分段

假若把位隙分段，則在一個沖突時隙內(nèi)能夠識別的標(biāo)簽個數(shù)就會大于2L。在最優(yōu)情況下，把2L位位隙標(biāo)志位分為等長的兩段，則一個沖突時隙內(nèi)最多能夠識別L2個標(biāo)簽。假如2L=8，則分段后，最多能夠識別出16個標(biāo)簽。

先考慮固定幀長的情況。設(shè)幀長為N，查詢范圍內(nèi)標(biāo)簽數(shù)為n，位隙標(biāo)志位長度為2L，即每段長度均為L。

那么，單標(biāo)簽時隙的概率為：

(1)

空閑時隙的概率為：

(2)

沖突時隙的概率為：

(3)

一個查詢周期內(nèi)的沖突時隙數(shù)為：

Ncoll=N*Pcoll

(4)

同樣，成功識別的標(biāo)簽數(shù)為：

Nsucc=N*Psucc

(5)

一個查詢周期內(nèi)平均每個沖突時隙的標(biāo)簽數(shù)為：

(6)

位隙標(biāo)志位分段后，由于前后兩段等長且隨機在自己的段中置1，因此位隙等效長度為L2,則等效時隙長度為：

Neq=N*L2

(7)

等效時隙下單標(biāo)簽時隙的概率為：

(8)

因此一個查詢周期內(nèi)總的成功識別的標(biāo)簽數(shù)為：

(9)

由于在沖突時隙內(nèi)使用位隙進(jìn)行再識別，等效于增加了額外的時隙。前段位隙增加的額外時隙為：

(10)

其中

(11)

通過前段位隙進(jìn)行再識別后，還剩下的標(biāo)簽數(shù)為：

tremain=t-L*PFBS-succ

(12)

其中

(13)

在前段位隙產(chǎn)生的沖突時隙數(shù)為：

(14)

平均每個FBS的沖突時隙內(nèi)標(biāo)簽數(shù)為：

(15)

后段位隙增加的額外時隙數(shù)為：

(16)

其中

(17)

所以，一個沖突時隙內(nèi)增加的額外時隙數(shù)為：

Nextra-cs=NF+NB

(18)

一個查詢周期增加的總的額外時隙數(shù)為：

Nextra=Ncoll*Nextra-cs

(19)

因此，整個系統(tǒng)的吞吐率為：

(20)

其中

t=

(21)

k=

(22)

取N=64、L=8，觀察系統(tǒng)吞吐率曲線，如圖1所示。

圖1 三種算法吞吐率曲線

可見SBGFSA算法在保持了高吞吐率的同時，在標(biāo)簽數(shù)量較多時，吞吐率依然可以保持在50%以上。

令位隙標(biāo)志位長度2L=24，不同幀長下系統(tǒng)的吞吐率曲線如圖2所示。

圖2 SBGFSA在位隙標(biāo)志位長度為24時

一般最大幀長為256[12]，這里把最大幀長就定為256。由圖2可見，當(dāng)幀長為256時，在標(biāo)簽數(shù)量較高的情況下系統(tǒng)吞吐率是最大的，且在一定標(biāo)簽范圍內(nèi)，系統(tǒng)吞吐率近似可以看成一定值，約為70%左右，但在標(biāo)簽數(shù)量較低情況下，系統(tǒng)吞吐率會下降。

為提高標(biāo)簽數(shù)量較低情況下的系統(tǒng)吞吐率，在圖2的基礎(chǔ)上取N=32與N=256兩條曲線，如圖3所示。根據(jù)標(biāo)簽的數(shù)量，動態(tài)改變幀長。以兩條曲線的交點為幀長調(diào)整點，調(diào)整方法見表1。改進(jìn)后的吞吐率曲線為圖3中加粗實線部分。

表1 SBGFSA算法幀長調(diào)整機制

圖3 SBGFSA算法動態(tài)幀長調(diào)整機制

按照如上所述，該算法能以近70%的信道利用率識別一萬以內(nèi)的標(biāo)簽。

3 最優(yōu)位隙長度

為研究吞吐率與位隙長度之間的關(guān)系，固定幀長N=256，改變位隙長度2L。吞吐率曲線如圖4所示。

圖4 SBGFSA算法在幀長為256時

由圖4可見，在L達(dá)到12以后，隨著L的增加，曲線變化越來越小。

位隙標(biāo)志位的引入會提高吞吐率，但同時也增加了閱讀器與標(biāo)簽的通信量，最優(yōu)位隙長度的選取應(yīng)兼顧通信量。

由式(20)可得，平均識別一個標(biāo)簽所需要的時隙數(shù)為：

(23)

識別所有標(biāo)簽需要的總時隙數(shù)為：

(24)

設(shè)標(biāo)簽ID信息長96位，即LTagID=96。則通信量(此處忽略不同算法下閱讀器查詢命令長度差異)為：

(25)

圖5表明，當(dāng)L=12時系統(tǒng)的通信量可達(dá)到最小[13]。

(a)標(biāo)簽數(shù)4 000到5 000段通信量曲線

(b)標(biāo)簽數(shù)6 000到6 500段通信量曲線

4 算法描述

文中提出的SBGFSA算法在保持了高吞吐率的同時，兼顧了通信量。以下為該算法的具體執(zhí)行流程。

(1)閱讀器估計查詢范圍內(nèi)的標(biāo)簽數(shù)量并發(fā)出一個Query查詢命令。該Query命令包含一個Q值，Q取值依據(jù)為：若標(biāo)簽數(shù)大于490，則取8，否則取5。數(shù)據(jù)幀長為2Q。

(2)標(biāo)簽隨機選擇時隙，將其裝入自己的槽計數(shù)器，同時生成兩個12以內(nèi)的隨機數(shù)S1與S2。

(4)閱讀器檢查標(biāo)簽的返回ID信息與位隙信息。如果本時隙沒有響應(yīng)信號或者有無沖突的標(biāo)簽響應(yīng)信號，則閱讀器做相應(yīng)的處理，然后轉(zhuǎn)(8)。如果標(biāo)簽返回的ID信息有沖突，則轉(zhuǎn)(5)。

(5)閱讀器查看FBS信息里有幾位為1。如果有n位為1，則說明本時隙內(nèi)至少有n個標(biāo)簽產(chǎn)生碰撞。閱讀器按照從高位到低位的順序，分別提取出含有1的位置信息，并將該信息包含到一個新的查詢命令QueryRepFBS中。本時隙內(nèi)的標(biāo)簽在收到該命令后，提取出該位置信息，并與自己的第一段位隙信息進(jìn)行匹配。匹配成功的標(biāo)簽將自己的數(shù)據(jù)包返回給閱讀器。閱讀器檢測返回的ID信息。如果沒有沖突，就利用ACK命令進(jìn)行確認(rèn)；如果有沖突，則轉(zhuǎn)(6)。

(6)閱讀器查看整個位隙信息里有幾位為1，并按照從高位到低位的方式，分別提取出含有1的位置信息，將其包含到另一個新的查詢命令QueryRepSBS中。本時隙內(nèi)的標(biāo)簽在收到該命令后，提取出該位置信息，并與自己的整個位隙位進(jìn)行匹配。匹配成功的再次返回自己的ID信息。閱讀器查看是否有沖突：如果沒有沖突，利用ACK命令確認(rèn)；如果還有沖突，則丟包，進(jìn)行NAK確認(rèn)[14-15]。

(7)閱讀器將FBS中含有1的最高位清零，如果FBS不為0，則進(jìn)入次高位，然后執(zhí)行(5)-(7)，直到FBS為0。

(8)閱讀器發(fā)送QueryRep命令，查詢范圍內(nèi)的標(biāo)簽接到命令后將自己的槽計數(shù)器減1，然后轉(zhuǎn)(3)。如果本時隙是最后一個時隙，結(jié)束本輪查詢并轉(zhuǎn)(1)。

(9)某一輪查詢中，所有時隙都是空時隙，整個查詢過程結(jié)束。

5 結(jié)束語

RFID是物聯(lián)網(wǎng)發(fā)展的核心部分，它的發(fā)展將會給人類的生產(chǎn)、生活帶來翻天覆地的變化。其巨大潛力將隨著物聯(lián)網(wǎng)的發(fā)展得到進(jìn)一步的體現(xiàn)。防碰撞問題是RFID的一個關(guān)鍵問題。這將推動越來越多的研究人員投入到RFID防碰撞算法的研究中去。

文中理論推導(dǎo)得出：通過位隙分段，可以在保持高吞吐率的同時減少系統(tǒng)的總通信量。在此基礎(chǔ)上，提出的分段式位隙分組幀時隙Aloha算法在閱讀器查詢范圍標(biāo)簽數(shù)量較多時，仍然能夠保持穩(wěn)定且高效的信道利用率。

考慮到在確定性防碰撞算法中，可以利用發(fā)生碰撞標(biāo)簽的ID段進(jìn)行再識別或進(jìn)行通信量控制[16]。因此，在后續(xù)工作中，可以從以下兩方面開展進(jìn)一步的研究。

(1)在SBGFSA算法的基礎(chǔ)上，將碰撞時隙中標(biāo)簽的ID段加以利用，進(jìn)一步提高算法性能。

(2)將位隙段分三段以上，研究算法性能。由特殊到一般，探尋是否存在一般規(guī)律。

[1]WangYuhao,LiuYi,LeungH,etal.AsegmentcollisioninversionprotocolforRFIDtagreading[J].IEEECommunicationsLetters,2013,17(10):2008-2011.

[2]LiuXiaohui,QianZhihong,ZhaoYanhang,etal.Anadaptivetaganti-collisionprotocolinRFIDwirelesssystems[J].ChinaCommunications,2014,11(7):117-127.

[3]ParkJ,ChungMY,LeeTJ.IdentificationofRFIDtagsinframed-slottedALOHAwithrobustestimationandbinaryselection[J].IEEECommunicationsLetters,2007,11(5):452-454.

[4]HakeemMJ,RaahemifarK,KhanGN.NovelmodulobasedALOHAanti-collisionalgorithmforRFIDsystems[C]//ProcofIEEEinternationalconferenceonRFID.[s.l.]:IEEE,2014:97-102.

[5]ShihDH,SunPoling,YenDC,etal.TaxonomyandsurveyofRFIDanti-collisionprotocols[J].ComputerCommunications,2006,29(11):2150-2166.

[6] 黃玉蘭.物聯(lián)網(wǎng)射頻識別(RFID)技術(shù)與應(yīng)用[M].北京:人民郵電出版社,2013.

[7] 王 鈺.RFID防碰撞算法研究[D].南京:南京郵電大學(xué),2011.

[8] 王玉琢.UHFRFID系統(tǒng)防碰撞研究[D].北京:北京郵電大學(xué),2011.

[9]DengDJ,TsaoHW.OptimaldynamicframedslottedALOHAbasedanti-collisionalgorithmforRFIDsystems[J].WirelessPersonalCommunications,2011,59(1):109-122.

[10] 王 宇.基于改進(jìn)的RFID標(biāo)簽防碰撞技術(shù)的研究[D].長春:吉林大學(xué),2013.

[11] 栗 華.UHFRFID多標(biāo)簽防碰撞算法的研究與性能分析[D].濟南:山東大學(xué),2011.

[12]WangHui,XiaoShengliang,LinFeiyu,etal.GroupimprovedenhanceddynamicframeslottedALOHAanti-collisionalgorithm[J].JournalofSupercomputing,2014,69(3):1235-1253.

[13] 張志涌,楊祖櫻.MATLAB教程:R2010a[M].北京:北京航空航天大學(xué)出版社,2011.

[14]LiXiaowu,FengQuanyuan.AnimproveddynamicframedslottedALOHAusingposterioriprobabilitytagestimationalgorithminthemobileradiofrequencyidentificationsystems[J].JournalofComputationalandTheoreticalNanoscience,2014,11(6):1417-1421.

[15]DhakalS,ShinS.Precise-optimalframelengthbasedcollisionreductionschemesforframeslottedalohaRFIDsystems[J].KSIITransactionsonInternetandInformationSystems,2014,8(1):165-182.

[16]LaiYuancheng,HsiaoLing-Yen,LinBor-Shen.AnRFIDanti-collisionalgorithmwithdynamiccondensationandorderingbinarytree[J].ComputerCommunications,2013,36(17-18):1754-1767.

A Frame Slot Aloha Algorithm of Sectional Bit-slot Group

XING Zhi-peng,YANG Heng-xin，ZHANG Yun

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

Since the radio frequency identification (RFID) technology is more and more frequently used in various occasions,it is an important task to improve the recognition efficiency of RFID tags.Combined with bit-slot grouping,a sectional bit-slot group frame slot Aloha algorithm is proposed in this paper based on the classical FSA.The algorithm divides the bit-slot into two sections,when collision occurs to a particular slot,the collided tags send the forward bit-slot and backward bit-slot to the reader for recognition:if the reader identifies all the collided tags successfully in the forward bit-slot,the reader enters the next slot of tag identification.If the collision still exists after the recognition in the forward bit-slot,the collided tags continue to send backward bit-slot to the reader for recognition.Theoretical analysis shows when a bit-slot is divided into two isometric parts,system throughput curve maintains flat at the range of a certain number of tags (within 10 000).Furthermore,while the throughput is over 65%,the system communication traffic reaches the lowest.

RFID;anti-collision algorithm;Aloha;bit-slot group

2015-07-20

2015-10-22

時間：2016-03-22

國家自然科學(xué)基金青年科學(xué)基金項目(61302155)

邢志鵬(1989-)，男，碩士研究生，研究方向為智能信息處理；楊恒新，副教授，研究方向為無線射頻識別技術(shù)；張 昀，碩士生導(dǎo)師，研究方向為通信信號盲檢測、神經(jīng)網(wǎng)絡(luò)和無線傳感器網(wǎng)絡(luò)等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.088.html

TP301.6

A

1673-629X(2016)04-0031-05

10.3969/j.issn.1673-629X.2016.04.007