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

邢志鵬，楊恒新,張 昀

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

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

邢志鵬，楊恒新,張 昀

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

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

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

0 引 言

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

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

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

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

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

1 經典標簽防碰撞算法及其改進算法

現存RFID系統的防碰撞算法主要分為兩類：標簽防碰撞算法和閱讀器防碰撞算法。標簽防碰撞算法又可分成兩類：確定型算法和概率型算法。

確定型算法又稱為樹型算法，主要是基于標簽ID的搜索協議：閱讀器通過改變查詢命令，使標簽基于ID號逐級分組，直到有唯一的標簽被閱讀器識別為止。基于樹的防碰撞算法主要包括TS(Tree Splitting)、BT(Binary Tree)、BS(Binary Search)、QT(Query Tree)、CT(Collision Tree),以及在CT上改進的ICT(Improved Collision Tree)。

傳統的概率型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算法把若干個時隙分為一幀，在一輪查詢中，標簽隨機選擇幀內時隙對閱讀器做出響應。當兩個以上的標簽選擇了同一時隙時，就會發生碰撞。發生碰撞的標簽只得等到下一幀進行識別。

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

2 位隙分段

假若把位隙分段，則在一個沖突時隙內能夠識別的標簽個數就會大于2L。在最優情況下，把2L位位隙標志位分為等長的兩段，則一個沖突時隙內最多能夠識別L2個標簽。假如2L=8，則分段后，最多能夠識別出16個標簽。

先考慮固定幀長的情況。設幀長為N，查詢范圍內標簽數為n，位隙標志位長度為2L，即每段長度均為L。

那么，單標簽時隙的概率為：

(1)

空閑時隙的概率為：

(2)

沖突時隙的概率為：

(3)

一個查詢周期內的沖突時隙數為：

Ncoll=N*Pcoll

(4)

同樣，成功識別的標簽數為：

Nsucc=N*Psucc

(5)

一個查詢周期內平均每個沖突時隙的標簽數為：

(6)

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

Neq=N*L2

(7)

等效時隙下單標簽時隙的概率為：

(8)

因此一個查詢周期內總的成功識別的標簽數為：

(9)

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

(10)

其中

(11)

通過前段位隙進行再識別后，還剩下的標簽數為：

tremain=t-L*PFBS-succ

(12)

其中

(13)

在前段位隙產生的沖突時隙數為：

(14)

平均每個FBS的沖突時隙內標簽數為：

(15)

后段位隙增加的額外時隙數為：

(16)

其中

(17)

所以，一個沖突時隙內增加的額外時隙數為：

Nextra-cs=NF+NB

(18)

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

Nextra=Ncoll*Nextra-cs

(19)

因此，整個系統的吞吐率為：

(20)

其中

t=

(21)

k=

(22)

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

圖1 三種算法吞吐率曲線

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

令位隙標志位長度2L=24，不同幀長下系統的吞吐率曲線如圖2所示。

圖2 SBGFSA在位隙標志位長度為24時

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

為提高標簽數量較低情況下的系統吞吐率，在圖2的基礎上取N=32與N=256兩條曲線，如圖3所示。根據標簽的數量，動態改變幀長。以兩條曲線的交點為幀長調整點，調整方法見表1。改進后的吞吐率曲線為圖3中加粗實線部分。

表1 SBGFSA算法幀長調整機制

圖3 SBGFSA算法動態幀長調整機制

按照如上所述，該算法能以近70%的信道利用率識別一萬以內的標簽。

3 最優位隙長度

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

圖4 SBGFSA算法在幀長為256時

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

位隙標志位的引入會提高吞吐率，但同時也增加了閱讀器與標簽的通信量，最優位隙長度的選取應兼顧通信量。

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

(23)

識別所有標簽需要的總時隙數為：

(24)

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

(25)

圖5表明，當L=12時系統的通信量可達到最小[13]。

(a)標簽數4 000到5 000段通信量曲線

(b)標簽數6 000到6 500段通信量曲線

4 算法描述

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

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

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

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

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

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

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

(8)閱讀器發送QueryRep命令，查詢范圍內的標簽接到命令后將自己的槽計數器減1，然后轉(3)。如果本時隙是最后一個時隙，結束本輪查詢并轉(1)。

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

5 結束語

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

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

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

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

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

[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] 黃玉蘭.物聯網射頻識別(RFID)技術與應用[M].北京:人民郵電出版社,2013.

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

[8] 王玉琢.UHFRFID系統防碰撞研究[D].北京:北京郵電大學,2011.

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

[10] 王 宇.基于改進的RFID標簽防碰撞技術的研究[D].長春:吉林大學,2013.

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

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

[13] 張志涌,楊祖櫻.MATLAB教程:R2010a[M].北京:北京航空航天大學出版社,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

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

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

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