改进的基于ALOHA的RFID防碰撞算法

王勇，李婷

（南京邮电大学，江苏 南京 210023）

改进的基于ALOHA的RFID防碰撞算法

王勇，李婷

（南京邮电大学，江苏 南京 210023）

为了解决RFID系统中电子标签识别效率不高的问题，对基于ALOHA的随机性防碰撞算法进行了详细分析，提出了一种新的ALOHA防碰撞算法。在该算法中，针对标签估计，采用动态调整的方式自动改变标签估计式中的系数，使得标签估计个数随着已识别的标签数动态变化，从而估计下一帧待识别标签数；而对于帧长调整，根据估计的标签数，通过帧长与标签数分组的关系确定。通过MATLAB进行仿真，结果表明，该算法能明显提高系统的吞吐率和稳定性。

RFID；ALOHA算法；吞吐率；分组；标签估计

1 引言

无线射频识别（radio frequency identification，RFID）是一种利用射频信号和空间耦合的传输特性进行双向通信，实现对物体非接触式自动识别的技术[1]。随着科学技术的发展，RFID技术现已广泛应用于仓库管理[2]、室内定位[3]、图书馆管理[4]等诸多领域。然而当有2个或2个以上的标签在相同信道同时与阅读器进行通信时，由于不同的信号会产生混叠和干扰，使读写器不能对任意一个标签进行识别，从而产生碰撞，导致标签识别和数据传送失败[5,6]。因此为了实现电子标签的有效、可靠识别，如何解决防碰撞问题成为RFID技术研究的关键点之一。

目前，解决碰撞问题的算法主要有基于ALOHA的随机性防碰撞算法[7,8]和基于二进制树的确定性防碰撞算法[9-11]，并在此基础上对两种算法进行改进。其中，随机性防碰撞算法改进的关键点在于帧长的调整，使其动态地与待读标签数相吻合，尤其适用于标签密集、数量较多的情况，确定性防碰撞算法的改进在于减少信息冗余和寻求合理的寻址策略。随机性防碰撞算法简单、成本低，但系统吞吐率易受标签数、帧长等的影响；确定性防碰撞算法虽然能保证每个标签能及时被识别，但具有整个识别周期过长、系统设计较为复杂、标签成本较高等缺点[12,13]。

同时近几年来，针对ALOHA防碰撞算法效率不高的特点，虽然人们提出了各种针对标签估计和帧长调整的动态帧时隙ALOHA算法来改进算法效率，但是由于大多都是通过采用上一帧的识别情况来估计标签数和使帧长等于标签数来改进算法，所以系统的识别效率一般不超过36.8%。

针对这一特点，本文主要研究针对物流货物管理、健康管理、畜牧业流通等RFID主要应用领域的防碰撞算法，并在分析了各类ALOHA防碰撞算法后，提出了一种新的ALOHA防碰撞算法。在算法中，采用动态自适应调整方式，根据每次估计的标签数，动态调整估计因子，使下一次待识别的标签数与实际标签数更接近。同时，为了使系统效率高于理论上当帧长与待识别标签数相等时的效率，本文帧长由帧长与标签数的分组关系确定。仿真表明，改进的算法能使系统的效率有所改善。

2 ALOHA类算法

ALOHA算法是一种最基本、最简单的标签防碰撞算法，它是基于TDMA的一种防碰撞算法，是基于概率的算法。该算法是指阅读器在不同的时间分别与处于阅读器读取范围内的标签通信，从而减少冲突发生的概率，主要包括改进型的 ALOHA[14]和时隙 ALOHA（slotted-ALOHA）算法[15,16]。

2.1 纯ALOHA算法

纯ALOHA（P-ALOHA）算法是一种标签先发言的算法，标签进入阅读器作用范围获得能量，将自己的编码信息发给阅读器，在此过程中，如果有其他标签同时发送信息，就发生信号重叠，导致信息完全碰撞或部分碰撞，系统最大吞吐率约为18.4%。

2.2 时隙ALOHA算法

时隙ALOHA算法是对纯ALOHA 算法一种最简单的改进算法，能够节约时间。它是在纯ALOHA算法的基础上，把阅读器发送信号的时间划分成多个连续的离散时隙（slot），而由系统时钟对时隙长度进行控制。与基本ALOHA算法相比，时隙ALOHA算法中任何一个时隙内只存在一个标签成功识别或无标签响应或多个标签完全碰撞，没有基本ALOHA算法中的部分碰撞，所以返回数据发送碰撞的时间减少了一半，这样提高了信道利用率，系统吞吐率提高1倍，系统最大吞吐率约为36.8%，如图1所示。

图1 不同输入负载的系统吞吐率

2.3 帧时隙ALOHA算法

帧时隙ALOHA算法是在时隙ALOHA算法基础上的改进，阅读器将一帧分成N个时隙，每个时隙的长度大于标签的响应时间。标签接到阅读器的请求信号后，在N个时隙中随机选择一个时隙通信。如果一个时隙只被唯一的标签选中，则此时隙中标签传输的信息被阅读器成功接收，标签被正确识别。如果有两个或两个以上的标签选择了同一时隙发送，则会产生冲突，这些同时发送信息的标签就不能被读写器成功识别。整个算法的识别过程都会如此循环，一直到所有标签都被识别完成。

假设帧长为N，阅读器可识别范围内标签数为n，并假定所有标签均匀分布在各个时隙，即标签选择每个时隙的概率都是1/N，那么在一个时隙内具有r个标签的概率将服从二项分布。

具有r个标签的时隙期望值为：

该时隙为空时隙、成功时隙、碰撞时隙的概率分别为：

该时隙为空时隙、成功时隙、碰撞时隙的期望值分别为：

系统吞吐率为：

对式（9）求导，即可得出最佳帧长为：

当n足够大时，由泰勒展开式，可得：

所以，当阅读器帧长N和未识别标签数量n相等时，标签成功传输概率最大，系统工作在最佳状态，同时系统效率在标签数量趋于无穷大时约为36.8%。

图2为帧时隙ALOHA算法在不同帧长条件下，标签数量和系统吞吐率的关系曲线。可以看出，当标签数远小于阅读器的帧时隙数时，会造成时隙的浪费，当标签数和阅读器的帧时隙数相等时，系统的吞吐率最大。

图2 不同帧长的系统吞吐率曲线

2.4 动态帧时隙ALOHA算法

动态帧时隙ALOHA （dynamic framed slotted ALOHA,DFSA）算法针对帧时隙ALOHA算法的标签数目与帧长度相差越多，系统性能越差的这个缺点，提出了一种弥补和改善的方法[17]。具体的做法就是使用动态的帧时隙数，使得每帧内的时隙数接近系统中标签的数目，是一种改进的FSA算法，在该算法中，阅读器能动态调整下一次阅读循环中每帧的时隙数目。

3 改进帧时隙ALOHA算法

通过对上面ALOHA算法的分析可知，影响系统吞吐率的因素主要有标签个数的估计和帧长的调整。其中，在当前研究中较多使用的标签估计算法有最小二乘算法、Schoute算法以及Vogt算法。在这些算法中，每识别完一帧时隙后，虽然能根据上一帧的识别情况估算出下一帧待识别的标签数，并使帧长等于标签数，从而计算出系统的吞吐率，但是它们仅仅使用了本次查询的碰撞标签来进行估计，且系数几乎都是常数，并没有进行验证。同时，使帧长等于标签估计数，虽然能使系统吞吐率达到最大值，但是碰撞率也随之变大，并不能使系统工作在稳定吞吐率下，因此提出了一种新的防碰撞算法。

3.1 标签估计

本标签估计算法是对参考文献[18]中算法的改进，核心是根据本次查询的标签数情况，估计出下一帧的标签数，然后根据已有的标签估计算法，至下一次查询时，估计出该次查询的标签数，然后对其进行比较，得出预测因子，从而使系统能根据两次连续的读取状态自动调整，而当前一帧的碰撞时隙数为零，未识别标签又不为零时，不停止查询，而是继续以初始设置帧长，对系统进行查询，从而形成一个周期，直到所有的标签被识别完。

设第i次查询后，空闲时隙数、成功时隙数、碰撞时隙数分别为 C0(i)、C1(i)、Ck(i)，待识别的下一帧时隙数与碰撞时隙数呈线性关系，即：

那么就可以根据第次查询的碰撞时隙数预测下一帧的标签数，这里k不是固定不变的，而是根据实际情况进行调整。

第i+1次查询后，可以采用JaeRyongCha提出的第一种标签估计算法进行标签估计，为：

则可以求出预测标签与验证标签的相对误差为：

为了使相对误差的平方最小，使ε2对k求导，可得：

值得注意的是，第i+1的标签估计仍需第i+1的标签估计完成后才能得到，这是不现实的，因此调整为：

从而得到下一帧待识别的标签数为：

其中，Ck(0)等于初始设置的帧长；当Ck(i)为零而系统标签未识别完时，系统继续以初始设置帧长识别标签，直到所有标签被识别完。

3.2 帧长调整

由式（4）、式（5）可知，虽然当标签数与帧长相等时，系统能达到最大的吞吐率，但是系统的碰撞率也随即增大，且如果标签数量和系统能达到的帧长最大值相差很多，碰撞问题将难以解决。本算法是根据分组的思想来提高系统的吞吐率。算法首先确定出以2的次幂连续为帧长时，如4、8、16、32，系统吞吐率曲线交点处的标签数，那么该标签数即可作为调整帧长和标签分组数的临界点。一旦标签数达到该临界点，就可以调整相应帧长的大小。而通过计算，可得两相邻曲线的标签交点数为：

然后再根据系统最大效率与标签数进行分组，将各种标签数量下的帧长调整情况补充完整，见表1。

表1 标签数分组与帧长选择

3.3 算法流程

改进算法实现流程如图3所示。首先系统进行初始化，设置初始帧长、初始标签数。然后阅读器发送查询命令，读取标签，记录标签响应情况：若空闲，则空闲时隙加1；若识别，则成功时隙加1；若碰撞，则碰撞时隙加1。记录完后，根据碰撞情况，采用标签估计算法，估计出下一帧待识别的标签数，并根据帧长与标签数分组关系确定下一帧的帧长：若未识别标签数不为零且上一帧碰撞标签数不为零，则进入下一帧识别；若未识别标签数不为零且上一帧碰撞标签数为零，则进入下一周期，重新开始识别。

图3 改进算法实现流程

4 算法仿真与分析

图4 改进算法与固定帧算法的系统吞吐率对比

本文采用MATLAB软件对改进算法进行仿真，并与固定帧时隙ALOHA算法进行系统吞吐率对比，改进算法中标签数目设置为100，初始帧长设置为16，固定帧时隙ALOHA算法固定帧长设置为32，标签数为100。仿真结果如图4所示。从图4中可以看出，本改进算法的系统吞吐率明显优于固定帧时隙ALOHA算法，最大系统吞吐率可以达到42.19%，且随着标签数的增多，系统的吞吐率能以一定的稳定状态维持在35%左右，高于固定帧时隙ALOHA算法。

5 结束语

针对帧时隙ALOHA算法系统吞吐率在标签数达到一定程度后急剧下降的情况，本文对帧时隙ALOHA算法进行了改进，首先通过验证机制对标签进行了估计，然后由标签数与帧长分组关系调整了帧长。改进后，由仿真结果可以看出，系统具有相对稳定的吞吐率且以一定的周期循环，同时系统吞吐率明显高于帧时隙ALOHA算法，并且算法简单，成本低。

[1]LU Y,WU Z,GAO Z M.Advanced technologies,embedded and multimedia for human-centric computing[M].Netherlands:Springer,2014:655-661.

[2]王亚青,凌翔,白小波.基于RFID的仓库管理系统研究[J].物流工程与管理,2015,37(3):37,92-93.WANG Y Q,LING X,BAI X B.Warehouse management system based on RFID [J].Logistics Engineering and Management,2015,37(3):37,92-93.

[3]吴文炤,王潇,赵鲲鹏,等.基于RFID技术的智慧园区室内定位算法[J].电信科学，2016,32(3):187-191.WU W Z,WANG X,ZHAO K P,et al.Indoor localization algorithm based on RFID technology forsmartpark[J].Telecommunications Science,2016,32(3):187-191.

[4]胡英俊.基于RFID技术的图书馆管理系统研究[J].信息技术,2013(9):176-178.HU Y J.Research on library management system based on RFID technology[J].Information Technology,2013(9):176-178.

[5]周沫.超高频射频识别系统标签检测性能研究 [D].南京:南京邮电大学,2013.ZHOU M.The research of tag identification performance in UHF RFID system[D].Nanjing:Nanjing University of Posts and Telecommunications,2013.

[6]JIA X,FENG Q,FAN T,et al.RFID technology and its applications in internet of things (IOT)[C]//The 2nd International Conference on Consumer Electronics,Communications and Networks,April 21-23,2012,Yichang,China.New Jersey:IEEE Press,2012:1282-1285.

[7]孟淑玲.射频识别系统中防冲突算法的研究[D].天津：天津大学,2008.MENG S L.Research on anti-collision algorithm in RFID system[D].Tianjin:Tianjin University,2008

[8]LEE D,CHOI J,LEE W,et al.A time-optimal anti-collision algorithm for FSA based RFID systems[J].Etri Joural,2011,33(3):458-461.

[9]MYUNG J,LEE W,SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti collision[J].IEEE communications Letters,2006,10(3):144-146.

[10]KIM S H,PARK P G.An efficient tree-based tag anti-collision protocol for RFID systems[J].IEEE Transactions on Letters,2007,11(5):449-451.

[11]LAI Y C,LIN C C.A pair resolution blocking algorithm on adaptive binary splitting for RFID systems [J]. IEEE Communications Letters,2008,12(6):432-234.

[12]尹君,何怡刚,李兵.基于分组动态帧时隙的RFID防碰撞算法[J].计算机工程,2009,35(20):267-269.YIN J,HE Y G,LI B.RFID anti-collision algorithm based on grouping dynamic frame slotted[J].Computer Engineering,2009,35(20):267-269.

[13]胡玲敏.RFID系统的防碰撞算法研究[D].杭州:杭州电子科技大学,2011.HU L M.Research on anti-collision algorithm in RFID system[D].Hangzhou:Hangzhou Dianzi University,2011.

[14]单建锋,陈明,谢建兵.基于ALOHA算法的RFID防碰撞研究[J].南京邮电大学学报(自然科学报),2013,33(1):56-61.SHAN J F,CHEN M,XIE J B.Research on RFID anti-collision technnology based on Aloha algorithm [J].Journal of Nanjing University of Posts and Telecommunications(Natural Science Edition),2013,33(1):56-61.

[15]WANG H,PEI C,SU B.Collision free arbitration protocol for activeRFID systems [J].JournalofCommunicationsand Networks,2012,14(1):34-39.

[16]舒远仲,田蕾,张丽.基于排队理论的时隙ALOHA防碰撞算法[J].计算机工程与设计,2013,34(7):2632-2636.SHU Y Z,TIAN L,ZHANG L.Timeslots ALOHA anti-collision algorithm based on queuing theory[J].Computer Engineering and Design,2013,34(7):2632-2636.

[17]SCHOUTE F C.Dynamic frame length ALOHA [J].IEEE Transactions on Communications,1983,31(4):565-568.

[18]栗华.UHF RFID多标签防碰撞算法的研究与性能分析[D].济南:山东大学,2011.LI H.Research and performance analysis of UHF RFID multi-tag anti-collision algorithms[D].Jinan:Shandong University,2011.

Improved RFID anti-collision algorithm based on ALOHA

WANG Yong,LI Ting
Nanjing University of Posts and Telecommunications,Nanjing 210023,China

In order to solve the problem of low efficiency of electronic tag identification in RFID system,a new ALOHA anti-collision algorithm was presented.In this algorithm,the coefficients of the tag estimation were automatically changed by using the dynamic adjustment method,which made the number of tag estimation could be dynamic changed with the number of identified tags,then the number of tags to be identified was estimated.And for the frame length adjustment,it could be determined by the relationship between the length of the frame and the tag number according to the estimated number of tags.With the tool of MATLAB,the results show that the proposed algorithm can significantly improve the throughput and stability of the system.

RFID,ALOHA algorithm,throughput,grouping,tag estimation

TP391

A

10.11959/j.issn.1000-0801.2016174

2016-03-30；

2016-06-15

王勇（1961-），男，博士，南京邮电大学教授，主要研究方向为虚拟仪器（VXI），测量与控制技术，各类通信网的监测、监控与管理。

李婷（1991-），女，南京邮电大学硕士生，主要研究方向为精密测试技术与智能仪器。