基于黄金分割的动态帧时隙ALOHA防碰撞算法

董永峰，周艳聪，张晶，张素琪

（1.河北工业大学计算机科学与软件学院，天津 300401；2.天津商业大学信息工程学院，天津 300134）

基于黄金分割的动态帧时隙ALOHA防碰撞算法

董永峰1，周艳聪2，张晶1，张素琪2

（1.河北工业大学计算机科学与软件学院，天津 300401；2.天津商业大学信息工程学院，天津 300134）

为了提高射频识别（RFID）系统中标签的识别效率，本文对基于ALOHA的概率性防碰撞算法进行了详细的分析，提出了一种基于黄金分割的动态帧时隙ALOHA防碰撞算法．标签估计中，选取动态调整机制来自动调整标签估计式中的系数，使得标签估计个数随着标签数动态变化；下一查询周期帧时隙长度调整中，根据标签到达的概率分布特点并结合黄金分割法思想，通过设置阈值条件来动态优化帧长度．MATLAB仿真结果表明，该算法能够减少空时隙的数量，有效的提高了系统的识别效率和时隙利用率．

射频识别；防碰撞算法；动态帧时隙；黄金分割法

0 引言

随着科学技术的不断提高，物联网技术得到了全面快速的发展与应用，射频识别（radio frequency identification，RFID）技术作为其关键技术之一，已广泛应用于交通、运输、工业、服务业等各种信息化系统．目前影响RFID识别技术的关键因素是标签的碰撞、冲突问题，这在很大程度上降低了系统对标签成功识别的效率，也成为众多科研人员致力研究的问题．

所谓标签碰撞问题，即在阅读器识别范围内，当有两个或多个标签同时响应阅读器并发送数据时，在通信信道内产生的数据信息间的冲突[1]．目前解决RFID中标签防碰撞问题主要是基于ALOHA的防碰撞算法和基于二进制树的防碰撞算法．基于二进制树的搜索确定性算法是以标签的ID号为基础来防止碰撞发生的[2]，根据标签的ID号划分成0组和1组，以此逐步缩小每组内标签的个数直到最终完成对所有标签的识别．此类算法可以识别完全部标签而不会产生漏读现象，系统的效率可以达到最大值0.43，但相对复杂度较高，识别时间较长，应用较少．基于ALOHA的随机性防碰撞算法基本思想是当阅读器检测到有碰撞时，令标签随机的延迟一段时间再响应阅读器，其中动态帧时隙ALOHA算法是最常见的算法．它将时间划分成多个帧，每帧内又分成多个时隙，帧长度可以根据标签数量动态变化，大大提高了标签识别效率，减少了时隙内标签的碰撞，缩短了识别时间．为了提高识别效率，文献[3]采用构造哈希函数的方法对标签进行时隙分配，使其在时隙内分布最优；文献[4]采用二分查找的方法，根据时隙内标签识别情况来动态的增加或减少时隙数，以减少时隙的浪费和碰撞时隙数的增加．文献[5]中采用FibonacciNumber数列实现帧长度的动态调整，实现了标签的高效识别．

本文在研究了动态帧时隙ALOHA算法帧长调整不灵活的缺点后，提出了一种新的帧长度调整方法．算法中，采用动态调整机制，根据每次估计的标签数,动态调整标签估计式中的系数，使其与实际标签数更接近；当有碰撞发生时，根据阈值条件和当前碰撞情况，采用黄金分割法动态调整下一帧需要的帧长度．仿真结果表明，所提出的算法在系统识别效率和时隙利用率方面都有明显的改善．

1 Aloha类算法简介

Aloha算法是一种基于时分机制（TDMA）的概率性防碰撞算法，最初用来解决通信系统中数据信息的堵塞问题，现已广泛应用于解决RFID系统中标签碰撞问题，主要包括以下几种：纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法等[6-10]．

1.1 纯ALOHA算法（PA）

PA算法是最基本的ALOHA算法，当阅读器检测到有信息冲突时会令标签延迟一段时间再次发送，由于延迟的时间是随机的，所以信息传输过程中可能会出现部分冲突的情况，并且系统效率最大只能达到18.4%．

1.2 时隙ALOHA算法（SA）

SA算法是将PA算法的时间分成多个时间段（时隙），标签选择某一时隙的起始处发送信息．由于减少了部分冲突的情况，冲突周期由原来的2T减少为T，即系统吞吐率由S=G*e-2G变成S=G*e-G，所以信道的吞吐率提高了一倍，最大约达到36.8%，如图1所示，但在标签量比较大时，系统的信道利用率仍不是很理想，而且系统中还需要有同步时钟来确保所有标签达到时隙同步．

1.3 帧时隙ALOHA算法（FSA）

FSA算法是将SA算法中的时隙组成帧，标签在某帧内选择时隙发送信息，当时隙内有碰撞时标签会等待该帧识别结束后再在下一帧响应阅读器．对于FSA算法来说，每帧中包含的时隙数是固定不变的，它不随阅读器范围内标签数量的变化而变化．但当标签数变化时，不同的帧长度取得的系统效率是不同的，如图2所示．当标签数目远小于帧时隙数时，需要的时隙数比较少而空闲的时隙会比较多，造成时隙严重浪费，系统的效率也较低；当标签数目远大于帧时隙数时，当前的帧长度不满足当前标签数目的需要，造成时隙内标签碰撞的几率增大．

1.4 动态帧时隙ALOHA算法（DFSA）

图1 PA和SA吞吐率对比关系图Fig.1The throughput comparison of PA and SA

图2 FSA算法不同帧长对应的系统吞吐率Fig.2The system throughput of FSA algorithm corresponding to different frame length

DFSA算法改进了FSA算法中帧时隙数固定不变的缺点，当一帧识别结束后，阅读器根据上一帧时隙中的碰撞情况来估计下一帧中未识别的标签数量，然后调整合理的帧长度作为一下帧的开始，从而解决了时隙浪费的问题，大大提高了信道的吞吐率．

假设阅读器定义的帧长度为L，识别范围内的标签数目为N，n个标签选择某一时隙i的概率服从二项分布，即

某时隙内含有n个标签的期望值为

那么，一帧内成功识别的时隙数S1、空闲时隙数S0、碰撞时隙数Sc的期望值分别为：

系统吞吐率定义为：一次查询周期内，成功识别的时隙数占总时隙数的比值，由式(3)可得系统吞吐率为

由此可以看出，想要提高DFSA算法的识别效率，如何估算初始标签数量以及合理的调整最适帧长度成为动态帧时隙ALOHA算法的关键．

2 基于黄金分割的DFSA防碰撞算法

目前对动态帧时隙ALOHA算法的研究主要在标签数目估计和帧时隙数的调整方面，常用的标签估计算法主要有Schoute，Vogt，e-pc，Lower Bound，C-ratio，伪贝叶斯估计[11-12]等．在这些算法中，每帧识别完成后都会统计时隙内标签的碰撞情况，如成功识别时隙数S1、碰撞时隙数Sc和空闲时隙数S0，下一帧根据上一帧的统计情况估计此时剩余的未被识别的标签数量，然后确定一个适当的帧长度来识别这些标签，以此类推，直到所有标签都被识别完．但他们都忽略了一个问题是，以上算法只是单纯的根据此帧的碰撞情况估计下一帧未识别标签数，而没有对这个估计结果进行验证．此外，在实际应用当中，当帧长度等于标签数目时并没有像期望的那样得到最大的吞吐率，此时时隙内标签的冲突比较频繁[13]．因此，应对DFSA算法进行更深入的研究分析，优化帧长度以达到更好的效果．

2.1 标签数目的估计方法

本文提出的估计方法中，通过当前帧的碰撞情况估计下一帧待识别的标签数，下一帧识别结束后，根据已有的估计方法，对此帧内的所有标签数进行估计，然后与上一帧估计出的结果进行比较，最后根据比较的误差调整上一帧估计式中的系数，从而使2次估计值相接近，估计更准确．

第i次查询结束后，阅读器统计成功识别时隙数S1(i)、碰撞时隙数Sc(i)和空时隙数S0(i),假设下一次查询阅读器应读取的标签数与碰撞时隙数存在某一线性关系，如式(7)所示．

每一帧识别完成后，冲突时隙内的标签会在下一帧识别时响应，所以剩余的标签数由冲突时隙数决定，这里假定剩余标签数与冲突标签数存在某一线性关系，系数k不是固定不变的，可以根据时隙的碰撞情况做适当的调整．

第i+1次查询结束后，采用Bin ZHEN在文献[14]中提出的标签估计方法（DFSAZ）对本次查询内的总标签数进行估计，如式(8)所示．

要使两次查询结果的误差最小，即n1i+1=n2i+1，将(8)式带入(7)式，求得k的值为

由于第1次查询时需要第2次查询结果出来才能计算出k值，这是不现实的，所以对上式进行改进为

将(10)式带入(7)式得到下一次查询待识别的标签数目的估计值，为

这就是下一次识别的动态标签个数估计方程，其中k为一可变系数，取决于本次的碰撞情况和上次的碰撞的情况，F为开始识别时设置的初始时隙数．

2.2 时隙调整方法

2.2.1 黄金分割法

黄金分割法的数学定义是采用黄金值求解函数最大（小）值的一种数值搜索方法．对于区间[0，1]，将其分成长度分别为r和1 r的两部分（其中r＞1 r），当1/r=r/1 r时，求得位于区间[0,1]的根为5 1/2，其近似值就是黄金比值0.618．如图3所示．

黄金分割是1种数学上的比例关系，在很多科学实验中，选取方案常用1种0.618法，即优选法，它可以使我们合理地安排较少的试验次数找到合适的条件，在建筑、文学、工农业生产和科学实验中有着广泛而重要的应用．

对于泊松分布，其数学定义为：如果稀有事件A在每个单元（设想为n次实验）内平均出现次，那么在一个单元（n次）的试验中，稀有事件A出现次数x的概率分布服从Poisson分布[15]．由此可知，标签随机进入阅读器读写范围内的概率分布符合泊松分布的特点．泊松分布曲线图如图4所示．根据泊松分布图中上升阶段和下降阶段幅度均为单调的增加或减少的特点，对于标签而言即单位时间内，标签数量增加或减少比较快．所以根据这一特点对其斜率进行模拟，可以更好的预测下一次标签识别需要的时隙数，减少标签传输过程中的碰撞概率．

图3 线段上的黄金比值Fig.3The golden ratio on a segment

图4 泊松分布曲线图Fig.4The curve of Poisson distribution

通过对泊松分布特点的分析可知，精确计算泊松分布的斜率是比较复杂的，为了减少标签冲突，提高识别率，我们采用黄金分割法即黄金比值（0.618）来求得斜率的近似值．有的采用了二分查找的方法即两边取中的策略，近似模拟其斜率，也有的通过分析冲突因子和冲突时隙的关系来拟合其曲线来减少冲突．

2.2.2 黄金分割法时隙调整

本文通过黄金分割法动态的调整帧内时隙数以达到最佳，避免因时隙的过多或过少而引起的系统效率的降低．通过对标签到达阅读器的概率分布可得，调整最佳时隙数是本文的核心部分，其中，通过判断每帧标签的冲突情况来动态的调整时隙数．基于二分法的DFSA算法中，时隙长度的调整是在帧内，每识别完一个时隙即根据当前时隙的状态进行相应的增加或减少时隙数，这样可以很好的实现帧长度的调整，但是工作量很大，耗时也较长．本文提出一种简单的帧长度调整方案．

当一帧识别结束后，首先通过此帧的碰撞情况计算下一帧的最大时隙数，根据上述标签估计算法估计出的下一帧待识别的标签数，则下一帧最大帧长即为此时的待识别标签数．

2.2.3 算法流程

算法基本过程如下：

1）初始化预处理，设置初始标签数N，初始时隙数F，同时将帧长计数器SlotCounter初始化为F，清零碰撞计数器Sc、成功识别计数器S1和空时隙计数器S0．阅读器发送查询命令等待标签回复．

2）标签收到阅读器的查询命令后，随机的选取[0-F]中的一个数，并存入时隙计数器内．

3）阅读器依次查询每个时隙，根据标签的响应信息记录碰撞情况：如果时隙内有一个标签响应，则S1+ +，如果时隙内没有标签响应则S0++，如果时隙内有多个标签（2）响应，则Sc++．

4）根据碰撞情况，采用标签估计法，估计下一帧剩余标签数，并初始化下一帧最大帧长Fmax．

5）计算Sc/F，若Sc/f＜0.51，令帧长F等于估计的标签数；若Sc/Fslot，表示发生碰撞的情况较多，则进行黄金比例调整下一帧时隙数．

6）判断标签数N是否为0，不为0则转到第2）步继续识别，直到所有标签都被识别完结束．

主要流程图如图5所示．

图5 基于黄金分割的动态帧时隙ALOHA算法流程图Fig.5The flow chart of dynamic framed slotted tag anti-collision algorithm based on golden section

3 算法的仿真及结果分析

为了验证改进算法的性能优势，本实验采用MATLAB软件进行程序编写，在Windows7平台和2G内存环境下运行，标签最大数目设置为100，初始帧长度设为16，在相同条件下运行100次，对仿真实验结果取平均．本实验中，DFSA算法的标签估计采用DFSAZ估计法，FPDFSA算法为文献[13]提出的1种改进的DFSA方法．图6～图9为基于MATLAB软件对本文算法、DFSA算法和FPDFSA算法进行的仿真，分别在系统效率、时隙利用率、总时隙数、空时隙数方面进行比较分析．

首先定义两个性能参数：系统效率和时隙利用率．系统效率是指在一个识别周期内，成功识别的标签数与所需的总的时隙数的比值；时隙利用率是指在一个识别周期内，成功识别的时隙与碰撞时隙的和与总的时隙数的比值，主要反应时隙内空时隙出现的情况．

随着标签数的增加，3种算法在系统效率方面的比较情况如图6所示．从图中可以看出，本算法的系统效率明显优于DFSA算法，最大系统效率可以达到0.4，随着标签数的增加，系统效率维持在0.35左右，高于DFSA算法的0.3左右．与FPDFSA算法相比较，在标签数量较少时本文算法可以取得很好的系统效率，随着标签数增加这种优势逐渐减弱．

随着标签数的增加，3种算法在时隙利用率方面的比较情况如图7所示．从图中可以看出，本算法与DFSA算法相比有较高的时隙利用率，与FPDFSA算法相比，当标签数较多时，本算法体现出了很好的时隙利用率，标签数少时优势减少．

图63 种算法系统效率比较Fig.6The comparison on system efficiency about these three algorithms

图73 种算法时隙利用率比较Fig.7The comparison on the slot utilization about these three algorithms

随着标签数的增加，3种算法在所需空时隙数方面的比较情况如图8所示．从图中可以看出，本算法所需空时隙数明显少于DFSA算法，与FPDFSA算法相比，在标签数少时没有多大变化，当标签数多时所需的空时隙数量快速减少．

随着标签数的增加，3种算法在所需总时隙数方面的比较情况如图9所示．从图中可以看出，本算法所需总的时隙数少于DFSA算法，但与FPDFSA算法相比，虽然在标签数目较多时减少了空时隙的数量，但所需的总时隙数目相差不大，当标签数少时几乎与FPDFSA一样，当标签数多时略低于FPDFSA算法．这主要是因为标签数的增多加大了时隙的碰撞概率，此方面仍需要做进一步的改进．综上所述，本文算法在系统效率和时隙利用率上都有明显的改善，并且算法简单，可操作性强．

4 结论

防碰撞算法是提高RFID系统识别效率的关键．标签估计和帧长度调整方法是动态帧时隙ALOHA算法中改进的主要方面，本文通过对黄金分割法和泊松分布的研究与分析，将其应用到DFSA算法中，采用动态方法估计未识别标签数量，根据设置阈值条件来判断如何进行帧长度的黄金分割调整．通过MATLAB软件的仿真比较，在标签数量较少时，算法的系统效率明显高于常用的动态帧时隙ALOHA算法；同时，该算法在时隙利用率以及减少空时隙数方面都有明显的改善，并且算法简单、可操作性强．

图83 种算法空时隙数比较Fig.8The comparison on empty slot number about these three algorithms

图93 种算法所需总时隙数比较Fig.9The comparison on the required total time slot number about these three algorithms

[1]宁焕生．RFID重大工程与国家物联网[M]．北京：机械工业出版社，2011．

[2]Chennai，Tamil Nadu．Analysis of bit grouping algorithm for collision resolution in passive RFID tags[J]．International Journal of Engineering Science and Technology，2010，2（9）：4192-4240．

[3]郭志涛，程林林，周艳聪，等．动态帧时隙ALOHA算法的改进[J]．计算机应用研究，2012，29（3）：907-909．

[4]郭志涛，李玮玮，等．基于二分查找的动态帧时隙标签防冲突算法[J]．计算机应用研究，2012，29（11）：4287-4289．

[5]周朝阳．射频识别系统冲突防范算法[J]．计算机系统应用，2013，22（10）：132-135．

[6]Eom Jun-Bong，Lee Tae-Jin．Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J]．IEEE Communication Letters，2010，14（1）：60-62．

[7]吴海峰，曾玉．RFID动态帧时隙ALOHA防冲突中的标签估计和帧长确定[J]．自动化学报，2010，36（4）：621-624．

[8]EomJ B，Lee T J，RietmanR，et al．Anefficient framed-slot-tedALOHA algorithm withpilot frame andbinary selection for anti-collisionof RFID tags[J]．IEEE Communication Letters，2008，12（11）：861-863．

[9]Eom J B，Lee T J．Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J]．IEEE Communication Letters，2010，14（1）：60-62．

[10]Okkyeong Bang，Sunghyun Kim，Hyuckjae Lee．Identification of RFID tags in dynamic framed slotted Aloha[C]//Advanced Communication Technology of ICACT 11th International Conference．2009，1：354-357．

[11]孙文胜，金成敏．新型的RFID动态帧时隙ALOHA防碰撞算法[J]．信息与控制，2012，41（2）：233-237．

[12]Lin Chun-Fu，Lin Frank Yeong-Sung．Efficient estimation and collision-group-based anti-collision algorithms for dynamic frame-slotted ALOHA in RFID networks[J]．IEEE Transactions on Automation Science and Engineering，2010，7（4）：840-848．

[13]栗华．UHFRFID多标签防碰撞算法的研究与性能分析[D]．济南：山东大学，2011．

[14]BinZhen，Mamoru KOBAYASHI，Masashi SHIMIZU．Framed Aloha for multiple RFID objects identification[J]．IEICE Transactions on Communications，2005，E88-B：991-999．

[15]杨永发．概率论与数理统计教程[M]．天津：南开大学出版社，2009．

[责任编辑 田丰夏红梅]

Dynamic framed slotted tag anti-collision algorithm based on golden section

DONG Yongfeng1，ZHOU Yancong2，ZHANG Jing1，ZHANG Suqi2

(1.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;2.School of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China)

In order to improve the efficiency of tag identification in RFID（Radio Frequency Identification）system，the probabilistic collision algorithm based on the ALOHA has been analyzed in detail.A dynamic frame slot ALOHA anticollision algorithm based on the golden section was proposed.In tag estimation,the coefficients in tag estimation are adjusted automatically so that the estimated number of tags changes dynamically with the tags number.In next polling cycle,frame slot length is adjusted based on the probability distribution of the tag.And combined with golden section method of thought,the threshold conditions are set to dynamically optimize the frame length.Matlab simulation results show that the algorithm can reduce the number of empty slots and improve the recognition and slot utilization efficiency of system.

radio frequency identification;anti-collision algorithm;dynamic framed;slotted;golden section method

TP391.44

A

1007-2373(2015)03-0053-07

10.14081/j.cnki.hgdxb.2015.03.011

2015-02-17

天津市应用基础与前沿技术研究计划（14JCYBJC15900）；河北省高等学校科学技术研究项目（ZD20131097）

董永峰（1977-），男（汉族），副教授，博士．

数字出版日期：2015-06-17数字出版网址：http://www.cnki.net/kcms/detail/13.1208.T.20150617.1538.004.html