分段式位隙分组帧时隙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