邢志鵬，楊恒新,張 昀

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

分段式位隙分組幀時(shí)隙Aloha算法

邢志鵬，楊恒新,張 昀

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

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

射頻識(shí)別；防碰撞算法；Aloha；位隙分組

0 引 言

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

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

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

在研究經(jīng)典Aloha以及相關(guān)改進(jìn)算法的基礎(chǔ)上，文中提出一種分段式位隙分組幀時(shí)隙Aloha算法。該算法通過分段的位隙標(biāo)志位對(duì)一個(gè)碰撞時(shí)隙內(nèi)的標(biāo)簽進(jìn)行再識(shí)別，從而有效避免了多余時(shí)隙的傳送，在保持高吞吐率的同時(shí)減少了系統(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號(hào)逐級(jí)分組，直到有唯一的標(biāo)簽被閱讀器識(shí)別為止。基于樹的防碰撞算法主要包括TS(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算法把若干個(gè)時(shí)隙分為一幀，在一輪查詢中，標(biāo)簽隨機(jī)選擇幀內(nèi)時(shí)隙對(duì)閱讀器做出響應(yīng)。當(dāng)兩個(gè)以上的標(biāo)簽選擇了同一時(shí)隙時(shí)，就會(huì)發(fā)生碰撞。發(fā)生碰撞的標(biāo)簽只得等到下一幀進(jìn)行識(shí)別。

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

2 位隙分段

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

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

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

(1)

空閑時(shí)隙的概率為：

(2)

沖突時(shí)隙的概率為：

(3)

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

Ncoll=N*Pcoll

(4)

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

Nsucc=N*Psucc

(5)

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

(6)

位隙標(biāo)志位分段后，由于前后兩段等長(zhǎng)且隨機(jī)在自己的段中置1，因此位隙等效長(zhǎng)度為L(zhǎng)2,則等效時(shí)隙長(zhǎng)度為：

Neq=N*L2

(7)

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

(8)

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

(9)

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

(10)

其中

(11)

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

tremain=t-L*PFBS-succ

(12)

其中

(13)

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

(14)

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

(15)

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

(16)

其中

(17)

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

Nextra-cs=NF+NB

(18)

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

Nextra=Ncoll*Nextra-cs

(19)

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

(20)

其中

t=

(21)

k=

(22)

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

圖1 三種算法吞吐率曲線

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

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

圖2 SBGFSA在位隙標(biāo)志位長(zhǎng)度為24時(shí)

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

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

表1 SBGFSA算法幀長(zhǎng)調(diào)整機(jī)制

圖3 SBGFSA算法動(dòng)態(tài)幀長(zhǎng)調(diào)整機(jī)制

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

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

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

圖4 SBGFSA算法在幀長(zhǎng)為256時(shí)

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

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

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

(23)

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

(24)

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

(25)

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

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

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

4 算法描述

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

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

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

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

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

(6)閱讀器查看整個(gè)位隙信息里有幾位為1，并按照從高位到低位的方式，分別提取出含有1的位置信息，將其包含到另一個(gè)新的查詢命令QueryRepSBS中。本時(shí)隙內(nèi)的標(biāo)簽在收到該命令后，提取出該位置信息，并與自己的整個(gè)位隙位進(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)簽接到命令后將自己的槽計(jì)數(shù)器減1，然后轉(zhuǎn)(3)。如果本時(shí)隙是最后一個(gè)時(shí)隙，結(jié)束本輪查詢并轉(zhuǎn)(1)。

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

5 結(jié)束語(yǔ)

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

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

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

(1)在SBGFSA算法的基礎(chǔ)上，將碰撞時(shí)隙中標(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)射頻識(shí)別(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].長(zhǎng)春:吉林大學(xué),2013.

[11] 栗 華.UHFRFID多標(biāo)簽防碰撞算法的研究與性能分析[D].濟(jì)南:山東大學(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

時(shí)間：2016-03-22

國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61302155)

邢志鵬(1989-)，男，碩士研究生，研究方向?yàn)橹悄苄畔⑻幚?；楊恒新，副教授，研究方向?yàn)闊o(wú)線射頻識(shí)別技術(shù)；張 昀，碩士生導(dǎo)師，研究方向?yàn)橥ㄐ判盘?hào)盲檢測(cè)、神經(jīng)網(wǎng)絡(luò)和無(wú)線傳感器網(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