基于碰撞预检测的分组动态帧时隙ALOHA防碰撞算法

改进的基于动态帧时隙ALOHA防碰撞算法陈荣征【期刊名称】《齐齐哈尔大学学报（自然科学版）》【年(卷),期】2016(000)001【摘要】在 RFID 系统中，存在阅读器现多个标签同时通信的碰撞问题，标签防碰撞技术是解决标签防碰撞问题和提高标签识别率的关键。

在分析动态帧时隙ALOHA 算法的基础之是，提出了一种改进的基于随机数重新分组的动态帧时隙ALOHA 算法。

该算法证明了当引入一个随机数的时候，系统的吞吐率是最大的，并且同时利用标签唯一的ID号中的第一位的取值来同，进行重新分组，从而减少了标签碰撞的次数。

仿真实验结果表明，所提出的改进算法执行效率更高，碰撞次数更少，识别成功所需的时隙数更少，有效地提高了标签的识别速度。

%In the RFID system , the presence of multiple tags simultaneously reader collision problem of communication , tag anti-collision technology is the key to solve the problem and improve tag anti-collision tag identification rate . In the analysis of dynamic frame slotted ALOHA algorithm basis , proposed an improved dynamic frame slotted ALOHA algorithm based on random numbers regrouped . The algorithm proved that when introducing a random number when the throughput of the system is the largest , and the same time using different labels unique ID number of the first values , re-grouping ,thus reducing the number of tag collision . Simulation results show that the higher the efficiency of the improved algorithm proposed , fewer collisions , effectively improve the recognition speed label.【总页数】6页(P21-25,35)【作者】陈荣征【作者单位】广东职业技术学院信息工程系，广东佛山 528041【正文语种】中文【中图分类】TP301.6【相关文献】1.动态帧时隙Aloha算法防信息碰撞研究 [J], 曹高峰;卢建军;王晓路2.基于动态帧时隙Aloha的防碰撞算法研究 [J], 陈昊;高勤;安锡文3.基于碰撞预检测的分组动态帧时隙ALOHA防碰撞算法 [J], 陈卓4.改进的动态帧时隙ALOHA防碰撞算法 [J], 史长琼;肖瑞强;吴丹5.基于动态帧时隙ALOHA的危险品运输RFID防碰撞算法 [J], 魏福禄;刘攀;李志斌;孙锋;郭永青;曹宁博因版权原因，仅展示原文概要，查看原文内容请购买。

基于动态帧时隙Aloha的防碰撞算法研究作者：陈昊高勤安锡文来源：《无线互联科技》2017年第17期摘要：在RFID系统中，多标签同时存在会引发标签碰撞问题，文章首先分析已识别标签的情况，对剩余标签的个数进行了估计，并依此动态匹配最佳帧长。

为了进一步提高系统的识别效率，构造了合适的哈希函数，将标签集合均匀地映射到帧时隙集合，降低了标签的冲突率。

仿真表明，该算法提高了系统的吞吐率和稳定性，对Aloha算法的后续研究工作以及工程实践应用具有一定的参考价值。

关键字：动态帧时隙；Aloha算法；防碰撞；哈希函数；标签估计1 RFID概述无线射频识别（Radio Frequency Identification，RFID）作为新型无线非接触式自动识别技术[1]，具有存储容量大、识别速度快和安全系数高等优点，被作为感知层的关键技术广泛应用于物流、销售和定位等领域，并作为物联网领域的核心技术之一，得到极大关注[2]。

RFID系统一般由读写器、电子标签以及应用软件系统组成。

系统在工作的时候，读写器与标签之间利用电磁信号进行数据交换。

当多个标签共用相同的信道时，信号在空中媒介发生干扰，就会引发碰撞，导致标签识别和数据传送失败。

为了减小和消除这种碰撞问题，保证数据在传输过程中的完整性，许多科研工作者对RFID中的防碰撞机制进行了大量深入的研究。

目前，应用较广泛的防碰撞算法大多基于时分多址接入（Time Division Multiple Access，TDMA），主要有如下两类：基于二叉树的确定性算法和基于Aloha的概率性算法[3-5]。

前者优点是能识别出所有标签，没有遗漏现象，但是对读写器硬件要求较高且算法的空间和时间复杂度较高。

后者是Aloha及其改进算法，标签随机选择时隙与读写器通信，复杂度小且容易实现，但存在一定概率的某一标签长时间内所选择的时隙均发生碰撞，在有效时间内无法被读写器识别，存在标签“饥饿”问题。

优先出版 计 算 机 应 用 研 究 第32卷--------------------------------基金项目：国家自然科学基金资助项目(61371113)，交通运输部科技项目(2012-319-813-270，2013-319-825-110)作者简介：杜宗印(1988-)，男，山东嘉祥人，硕士研究生，主要研究方向为射频识别技术、安全认证协议；章国安(1965-)，男，博士，教授，博导，主要研究方向为无线通信网络、车联网、认知无线电等(gzhang@)；袁红林(1971-)男，博士，副教授，主要研究方向为无线信号识别技术；杨振(1987-)，男，硕士研究生，主要研究方向为物联网，智能算法．基于汉明重分组的动态帧时隙ALOHA 防碰撞算法 *杜宗印，章国安，袁红林，杨 振(南通大学 电子信息学院，江苏 南通 226019)摘 要：针对射频识别（RFID ）系统中标签较多时动态帧时隙ALOHA 算法识别效率快速下降的问题，在动态帧时隙ALOHA 算法的基础上，利用标签ID 前M 位的汉明重量对阅读器范围内标签进行分组，提出了一种基于汉明重分组的动态帧时隙ALOHA 算法（LGDFSA ），并利用Matlab 对它进行了仿真模拟。

仿真结果表明，LGDFSA 算法与动态帧时隙ALOHA 算法相比，当标签数较多时系统吞吐量提高，并趋于稳定，总操作数有所减少，系统总体效率提高。

关键词：射频识别；ALOHA 算法；汉明重分组；吞吐量；总操作数 中图分类号：TP301.6 文献标志码：ADynamic framed slotted ALOHA algorithm based on Hamming weight groupingDU Zong-yin, ZHANG Guo-an, YUAN Hong-lin, YANG Zhen(School of Electronics & Information, Nantong University, Nantong 226019, China)Abstract: On count of the rapid decline of efficiency when more tags are in radio frequency identification system, we use the hamming weight of tags ID top M bits to group the tags which are in the scope of the reader, and come up with dynamic framed slotted ALOHA algorithm based on hamming weight grouping (LGDFSA). And this proposed algorithm is simulated by Matlab. Compared with dynamic framed slotted ALOHA algorithm, the results show the system throughput is improved and tends to be stable, the total number of operating in the system is cut down, the overall efficiency of RFID system has been advanced. Key Words: Radio Frequency Identification; ALOHA algorithm; throughput; total number of operating0 0 引言射频识别（Radio Frequency Identification, RFID ）系统是一种非接触式的自动识别技术[1]，它由标签、阅读器和带有后端数据库的服务器三部分组成。

专 业 推 荐↓精 品 文 档帧时隙ALOHA反碰撞算法仿真及数据分析邓晓，何怡刚，陈洪云，谢涛（湖南大学电气与信息工程学院，湖南长沙410082）摘要：用MATLAB模拟实际的无源标签反碰撞过程.设计了帧时隙ALOHA算法仿真及数据分析程序，对碰撞过程中的相关数据进行了统计分析，获得碰撞时隙中平均标签数目与碰撞时隙比例的关系，为动态调整帧长度，提高识别效率提供依据.关键词：射频识别；反碰撞；帧时隙ALOHA算法中图分类号：TN911文献标识码：A0引言标签反碰撞算法对于射频识别（RFID）系统的识别能力至关重要，同时还关系到阅读器的实现难度与标签成本，是RFID系统的关键技术之一.标签冲突问题和计算机网络冲突问题类似，但是由于RFID系统本身的一些限制，应用于传统网络中的很多反碰撞技术无法或很难在RFID系统中直接应用.目前，RFID系统的标签反碰撞算法以时分复用（TDMA）为主，主要可以分为基于ALOHA的算法和基于树的算法.基于树的反碰撞算法又可以分为二进制树算法和查询树算法两种类型[1-2].基于ALOHA 的算法是随机性算法，标签利用随机时间响应阅读器的命令.在基本ALOHA算法基础上，产生了时隙ALOHA、帧时隙ALOHA和动态帧时隙ALOHA算法等改进算法[3-5].帧时隙ALOHA算法对系统要求较简单，识别速度较快，在很多国际和国内RFID标准中被采用[6-7]，本文也基于该算法对标签反碰撞过程进行仿真和分析.1算法原理在基本ALOHA算法中，标签进入阅读器读写范围，随机等待一定时间后，向阅读器发送自身ID.在标签的发送过程中，如果其他标签也在发送数据，那么就会发生信号重叠，从而导致完全冲突或部分冲突，如图1所示.发生冲突后，阅读器无法接受正确的信号，标签没有被正确识别，标签随机等待一定的时间后重新发送信号.基本ALOHA算法的一个最大缺点就是发生冲突的概率很大.如果标签传送整个收稿日期：2008-06-30作者简介：邓晓（1975－），男，湖南浏阳人，博士研究生.E－mail：dengxiao＿***********基金项目：国家自然科学基金资助项目（50677014）；国家863计划资助项目（2006AA04A104）；高校博士点基金资ID 的时间为T ，那么其他标签在整个数据发送期T 以及之前的时间T 内发送数据，都会导致冲突的发生.时隙ALOHA （Slotted ALOHA ）算法对此进行了改进，它在基本ALOHA 算法的基础上把时间分成多个离散的时隙，标签只能在每个时隙开始的时候发送数据，这样标签要么就被识别，要么就发生完全冲突，避免了部分冲突，将冲突期减少了一半，提高了信道利用率.这种方法需要一个同步时钟使所有的标签同步，这个同步时钟可以由阅读器发出.帧时隙ALOHA （Frame Slotted ALOHA ）算法在此基础上将多个时隙组成一帧，在一帧中只允许标签发送一次数据，进一步减少了冲突.在一帧中，如果某个时隙没有标签应答，则这个时隙称为空时隙；如果只有一个标签应答，则标签将被识别，称为识别时隙；如果有两个或两个以上的标签应答，则发生标签碰撞，标签无法被识别，称为碰撞时隙.未识别的标签在下一帧时隙中继续参与反碰撞循环，直到所有标签被识别.一帧时隙中，识别时隙与帧长度之比定义为传输通路的（平均）吞吐率S ，吞吐率越高，RFID 系统的识别速度越快.在帧时隙ALOHA 算法中，设空时隙、识别时隙和碰撞时隙的数目分别为F 0、F 1和F C ，这些时隙与帧长度F 之比分别用P 0、P 1和P C 表示.P 0、P 1和P C 与读写范围内的标签数量n 及帧长度F 的概率关系可以表示为:P 0＝（F －1）n F n ，P 1＝C n 1（F －1）n －1Fn ，P C ＝1－P 0－P 1.图2表示三种时隙所占的比例与标签数量、帧长度之间的关系，图中G 为平均数据包交换量，代表标签总数n 与帧长度F 之比.由图可知，当标签数目等于帧长度，即G =1时，吞吐率S 最大，最大值为36.8%[7].因此，如果能根据标签数目动态地调整帧长度，可以使帧时隙ALOHA 算法获得最大的吞吐率.动态帧时隙ALOHA 算法允许根据需要，动态地调整帧长度.由于读写范围内的标签数量是未知的，而且在识别过程中未被识别的标签数目是改变的，因此，怎样估算标签数量，合理地调整帧长度成为动态帧时隙ALOHA 算法的关键.2算法仿真及数据分析本文用MATLAB 设计了一个帧时隙ALOHA 算法仿真和数据分析程序，模拟帧时隙ALOHA 算法的反碰撞过程，算法流程如图3所示. 部分冲突完全冲突共享介质标签3标签2标签1图1基本ALOHA 算法第3期邓晓等：帧时隙ALOHA 反碰撞算法仿真及数据分析592012-05-19########################2012-05-19########################2012-05-192012-05-19########################2012-05-19########################2012-05-19程序对不同帧长度的多个样本进行了模拟，同时，对不同情况下每个碰撞时隙中的平均标签数e 进行了统计.统计表明，不同帧长度碰撞时隙中的平均标签数e 与碰撞时隙所占比例P c 的关系基本相同，关系曲线如图4所示.可以利用如图4所示的曲线估算出未识别的标签数目，然后动态地调整帧长度，步骤如下：1）以帧长度F 进行一轮识别后，统计出碰撞时隙个数F C ；2）计算P C ＝F C /F ；3）根据如图4所示的曲线获得相应的e 值；4）估算未识别标签数目n u ＝e ·F C ；5）调整帧长度为n u 进行下一轮识别.图3程序流程图图4e 与P c 关系曲线汕头大学学报（自然科学版）第23卷602012-05-19########################2012-05-19########################2012-05-192012-05-19########################2012-05-19########################2012-05-19为了测试这种标签数目估算方法的效果，以帧长度等于64为例，对本文所提的估算方法和已有的两种估算方法进行仿真比较[8-9]，结果如图5所示，图中误差E error指估算数目与未识别标签实际数目的差，是对100000个样本进行估算的均方差，“free slots ”曲线和“collision slots ”曲线分别代表原有的利用空时隙和碰撞时隙与总标签数目的关系进行估算的结果，“e -P ccurve ”曲线代表利用本文提出的方法估算的结果.图5表明，本文提出的方法不仅简单快速，准确度也比原有方法有较大提高.当平均数据交换量G 小于1.5时，估算误差减少30%以上，当G 小于1时，误差减少50%以上.这一点非常重要，因为经过一两次帧长度调整后，数据包交换量G 通常会接近1.3结语本文用MATLAB 设计了一个模拟帧时隙ALOHA 算法的仿真和数据分析程序.通过模拟帧时隙ALOHA 算法并对相关数据进行统计和分析，获得了不同帧长度时每个碰撞时隙中平均数目与碰撞时隙比例之间的关系曲线，提出了利用该曲线进行未识别标签估算并动态调整帧长度的方法.与原有标签估算方法相比，用本文方法估算未识别标签的准确度有较大提高.参考文献:[1]Wang Tsanpin.Enhanced binary search with cut -through operation for anti -collision in RFID systems[J].IEEE Communications Letters ，2006，10（4）：236-238.[2]Gyorfi L ，Gyori S.Analysis of tree algorithm for collision resolution[C]//2005International Conference on Analysis of Algorithms ，DMTCS proc ，2005：357-364.[3]Schoute F C.Dynamic frame length ALOHA[J].IEEE Transactions on Communications ，1983，（31）：565-568.[4]Vogt H.Multiple object identification with passive RFID tags systems[C].IEEE International Confer -ence on Systems ，Man and Cybernetics ，2002（3）：651-656.[5]吴春华，陈军.动态ALOHA 法在解决RFID 反碰撞问题中的应用[J].电子器件，2003，26（2）：173-176.[6]Auto -ID Center.Operational specification for a class -1UHF radio -frequency identification （RFID ）tag ，class 1generation 2RFID tag specification ，revision number 0.27.6[S].October ，2003.[7]Finkenzeller K.RFID handbook fundamentals and applications in contactless smart cards and identi -fication[M].2nd ed.West Sussex ：John Wiley &Sons Ltd ，2003．[8]程文青，赵梦欣.改进的RFID 动态帧时隙ALOHA 算法[J].华中科技大学学报，2007，35（6）：14-16.[9]高乐，吴援明.一种用于R F I D 系统中的帧长度调整方法[J].微计算机信息，2007，23（2）：213-215.第3期邓晓等：帧时隙ALOHA反碰撞算法仿真及数据分析612012-05-19########################2012-05-19########################2012-05-192012-05-19########################2012-05-19########################2012-05-19（上接第57页）[14]马建华.水杨酸甲酯清除羟基自由基活性的研究[J].化学通报，2006，3（3）：228-230.[15]Hiroshi Kitagaki M T.1，1-Diphenyl -2-Picrylhydrazyl radical （DPPH ）scavenging ability of sake dur -ing storage[J].Journal of Bioscience And Bioengineering ，1999，87（3）：328-332.[16]Lizette G.Contribution to characterization of oxidative stress in HIV/AIDS patients[J].Pharmacolog -ical research ，2003（47）：217-224.Research on κ-Carrageenan Modified by Salicylic AcidGUO Xi -kun ，SUN Wen -bing ，LIN Shu -dong（Department of Chemistry ，College of Science ，Shantou University ，Shantou 515063，Guangdong ，China ）Abstract ：Low molecular weight （LMW ）κ-carrageenan with the number -average molecular weight of 10000was achieved by depolymerizing natural κ-carrageenan in mild hydrochloric acid condition ，and then was turned into tetrabutylammonium salt.O -salicyloyl LMW κ-carrageenan was obtained by the salt modified with salicylic acid.The fine structure of O -salicyloyl LMW κ-carrageenan was characterized by 1H NMR ，13C NMR ，IR and UV.The results indicated that salicylic acid was reacted with the Hydroxyl groups on G4S 6of κ-carrageenan and formed the O -salicyloyl LMW κ-carrageenan.The degree of acylation was worked out to be 0.69.Meanwhile ，modifying κ-carrageenan with salicylic acid could improve its antioxidative activity in vitro.Key words ：salicylic acid ；κ-carrageenan ；degree of acylation ；antioxidative activity in vitroSimulation and Data Analysis of Frame Slotted ALOHAAlgorithm for Anti -collision in RFID SystemsDENG Xiao ，HE Yi -gang ，CHEN Hong -yun ，XIE Tao（College of Electrical and Information Engineering ，Hunan University ，Changsha 410082，Hunan ，China)Abstract ：Tag Collision arbitration for passive RFID tags is significant for fast identification.A simulation and data analysis program imitating frame slotted ALOHA Algorithm is presented.The relationship between the average tags quantity in collision slots and the collision slots proportion in a frame is analyzed.A novel frame -size adjusting method was proposed based on the relationship for dynamic frame slotted ALOHA Algorithm.Key words ：RFID ；anti -collision ；dynamic frame slotted ALOHA汕头大学学报（自然科学版）第23卷622012-05-19########################2012-05-19########################2012-05-192012-05-19########################2012-05-19########################2012-05-19。

最常用的防碰撞算法有：
1. 时隙ALOHA算法：通过将时间划分为多段等长的时隙，规定RFID 电子标签只能在每个时隙的开始时向RFID读写器发送数据帧，这样可以提高RFID系统的吞吐率。

2. 二分查找算法：当标签数量确定时，使用二分查找算法能够快速定位到某一特定标签，避免碰撞。

3. 动态帧时隙ALOHA算法：在固定帧时隙ALOHA算法的基础上，根据标签的实际情况动态调整时隙长度，以满足不同场景下的防碰撞需求。

4. 碰撞位检测算法：通过碰撞位检测技术，能够快速检测到发生碰撞的位，然后采取相应的策略进行碰撞避免或碰撞解决。

5. 树形搜索算法：通过逐层向下搜索的方式，在每一层进行标签的识别，避免在同一层发生碰撞，提高识别的成功率。

6. 虚拟环形防碰撞算法：通过建立虚拟环形空间，将所有标签按照一定的规则排列，然后在环形空间内进行顺序识别，避免了碰撞的发生。

7. 时隙二进制搜索算法：在搜索过程中，通过不断调整时隙长度和二进制的位数，逐渐逼近目标标签，最终实现碰撞避免和标签识别。

8. 动态帧时隙二进制搜索算法：结合了动态帧时隙ALOHA算法和时隙二进制搜索算法的特点，根据实际情况动态调整时隙长度和二进制位数，提高识别效率和准确性。

9. 随机退避策略算法：当发生碰撞时，标签会随机选择一个退避时间进行等待，然后重新发起识别请求。

通过不断随机退避和重试，最终实现标签的识别。

10. 优先级调度算法：根据标签的优先级进行识别，优先级高的标签可以优先获取资源进行识别，避免了碰撞的发生。

这些算法各有特点，适用于不同的应用场景。

在实际应用中，需要根据具体情况选择合适的防碰撞算法来提高RFID系统的性能和可靠性。

—267—基于分组动态帧时隙的RFID 防碰撞算法尹 君，何怡刚，李 兵，邓 晓，谭阳红，肖迎群(湖南大学电气与信息工程学院，长沙 410082)摘 要：为了解决射频识别(RFID)系统中的多标签防碰撞问题，在分析帧时隙ALOHA 算法的基础上，提出一种基于分组动态帧时隙的RFID 防碰撞算法。

当标签数量庞大时，该算法可以通过分组限制响应标签数量达到较高的识别效率。

仿真结果表明，当标签数为1 000时，与传统算法相比，该算法能使时隙利用率提高80%以上。

关键词：帧时隙；防碰撞；分组RFID Anti-collision Algorithm Based on Grouping Dynamic Frame SlottedYIN Jun, HE Yi-gang, LI Bing, DENG Xiao, TAN Yang-hong, XIAO Ying-qun(College of Electrical and Information Engineering, Hunan University, Changsha 410082)【Abstract 】In order to solve the problem of collision between multi-tag in radio frequency identification(RFID) system. This paper proposes RFID anti-collision algorithm based on grouping dynamic frame slotted by analyzing frame slotted ALOHA algorithm. When there are a large number of tags in the field, it can achieve high discernment efficiency by grouping to restrict the number of response tags. Simulation results show that the algorithm improves the slot utilization rate above 80% comparing with the conventional algorithms, when the number of tag is 1 000. 【Key words 】frame slotted; anti-collision; grouping计 算 机 工 程Computer Engineering 第35卷 第20期Vol.35 No.20 2009年10月October 2009·开发研究与设计技术·文章编号：1000—3428(2009)20—0267—03文献标识码：A中图分类号：TP301.61 概述射频识别(Radio Frequency IDentification, RFID)是于20世纪90年代提出的一种利用无线信道实现双向通信的识别技术。

基于分组的动态帧时隙ALOHA防碰撞算法
马耀庭
【期刊名称】《内江师范学院学报》
【年(卷),期】2017(032)008
【摘要】为了解决多标签防碰撞问题,对目前最常用的帧时隙ALOHA防碰撞算法进行详细的分析后,通过比较指出各种防碰撞算法的优缺点.提出了一种通过分组限制响应标签数量并调整帧长的防碰撞改进算法.仿真表明,该算法优于现有的动态帧时隙ALOHA算法,无论标签数目多少,均可获得最佳系统效率.
【总页数】5页(P64-68)
【作者】马耀庭
【作者单位】内江师范学院物理与电子信息工程学院, 四川内江 641199
【正文语种】中文
【中图分类】TN915.04
【相关文献】
1.基于ALOHA的分组动态帧时隙RFID系统防碰撞算法 [J], 李飞高;张贵林
2.基于碰撞预检测的分组动态帧时隙ALOHA防碰撞算法 [J], 陈卓
3.基于哈希分组的动态帧时隙ALOHA防碰撞算法 [J], 周艳聪;董永峰;张晶;顾军华
4.基于汉明重分组的动态帧时隙ALOHA 防碰撞算法 [J], 杜宗印;章国安;袁红林;杨振
5.基于功率分组的动态帧时隙ALOHA防碰撞算法研究 [J], 施建文;贾惠芹;王晟哲;李慧娟
因版权原因，仅展示原文概要，查看原文内容请购买。

基于黄金分割的动态帧时隙ALOHA防碰撞算法董永峰;周艳聪;张晶;张素琪【摘要】为了提高射频识别(RFID)系统中标签的识别效率,本文对基于ALOHA的概率性防碰撞算法进行了详细的分析,提出了一种基于黄金分割的动态帧时隙ALOHA防碰撞算法.标签估计中,选取动态调整机制来自动调整标签估计式中的系数,使得标签估计个数随着标签数动态变化;下一查询周期帧时隙长度调整中,根据标签到达的概率分布特点并结合黄金分割法思想,通过设置阈值条件来动态优化帧长度.MATLAB仿真结果表明,该算法能够减少空时隙的数量,有效的提高了系统的识别效率和时隙利用率.【期刊名称】《河北工业大学学报》【年(卷),期】2015(044)003【总页数】7页(P53-59)【关键词】射频识别;防碰撞算法;动态帧时隙;黄金分割法【作者】董永峰;周艳聪;张晶;张素琪【作者单位】河北工业大学计算机科学与软件学院,天津300401;天津商业大学信息工程学院,天津300134;河北工业大学计算机科学与软件学院,天津300401;天津商业大学信息工程学院,天津300134【正文语种】中文【中图分类】TP391.44随着科学技术的不断提高，物联网技术得到了全面快速的发展与应用，射频识别（radio frequency identification，RFID）技术作为其关键技术之一，已广泛应用于交通、运输、工业、服务业等各种信息化系统．目前影响RFID识别技术的关键因素是标签的碰撞、冲突问题，这在很大程度上降低了系统对标签成功识别的效率，也成为众多科研人员致力研究的问题．所谓标签碰撞问题，即在阅读器识别范围内，当有两个或多个标签同时响应阅读器并发送数据时，在通信信道内产生的数据信息间的冲突[1]．目前解决RFID中标签防碰撞问题主要是基于ALOHA的防碰撞算法和基于二进制树的防碰撞算法．基于二进制树的搜索确定性算法是以标签的ID号为基础来防止碰撞发生的[2]，根据标签的ID号划分成0组和1组，以此逐步缩小每组内标签的个数直到最终完成对所有标签的识别．此类算法可以识别完全部标签而不会产生漏读现象，系统的效率可以达到最大值0.43，但相对复杂度较高，识别时间较长，应用较少．基于ALOHA的随机性防碰撞算法基本思想是当阅读器检测到有碰撞时，令标签随机的延迟一段时间再响应阅读器，其中动态帧时隙ALOHA算法是最常见的算法．它将时间划分成多个帧，每帧内又分成多个时隙，帧长度可以根据标签数量动态变化，大大提高了标签识别效率，减少了时隙内标签的碰撞，缩短了识别时间．为了提高识别效率，文献[3]采用构造哈希函数的方法对标签进行时隙分配，使其在时隙内分布最优；文献[4]采用二分查找的方法，根据时隙内标签识别情况来动态的增加或减少时隙数，以减少时隙的浪费和碰撞时隙数的增加．文献[5]中采用FibonacciNumber数列实现帧长度的动态调整，实现了标签的高效识别．本文在研究了动态帧时隙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）DFSA算法改进了FSA算法中帧时隙数固定不变的缺点，当一帧识别结束后，阅读器根据上一帧时隙中的碰撞情况来估计下一帧中未识别的标签数量，然后调整合理的帧长度作为一下帧的开始，从而解决了时隙浪费的问题，大大提高了信道的吞吐率．假设阅读器定义的帧长度为L，识别范围内的标签数目为N，n个标签选择某一时隙i的概率服从二项分布，即某时隙内含有n个标签的期望值为那么，一帧内成功识别的时隙数S1、空闲时隙数S0、碰撞时隙数Sc的期望值分别为：系统吞吐率定义为：一次查询周期内，成功识别的时隙数占总时隙数的比值，由式(3)可得系统吞吐率为由此可以看出，想要提高DFSA算法的识别效率，如何估算初始标签数量以及合理的调整最适帧长度成为动态帧时隙ALOHA算法的关键．目前对动态帧时隙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所示．根据泊松分布图中上升阶段和下降阶段幅度均为单调的增加或减少的特点，对于标签而言即单位时间内，标签数量增加或减少比较快．所以根据这一特点对其斜率进行模拟，可以更好的预测下一次标签识别需要的时隙数，减少标签传输过程中的碰撞概率．通过对泊松分布特点的分析可知，精确计算泊松分布的斜率是比较复杂的，为了减少标签冲突，提高识别率，我们采用黄金分割法即黄金比值（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所示．为了验证改进算法的性能优势，本实验采用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算法相比，当标签数较多时，本算法体现出了很好的时隙利用率，标签数少时优势减少．随着标签数的增加，3种算法在所需空时隙数方面的比较情况如图8所示．从图中可以看出，本算法所需空时隙数明显少于DFSA算法，与FPDFSA算法相比，在标签数少时没有多大变化，当标签数多时所需的空时隙数量快速减少．随着标签数的增加，3种算法在所需总时隙数方面的比较情况如图9所示．从图中可以看出，本算法所需总的时隙数少于DFSA算法，但与FPDFSA算法相比，虽然在标签数目较多时减少了空时隙的数量，但所需的总时隙数目相差不大，当标签数少时几乎与FPDFSA一样，当标签数多时略低于FPDFSA算法．这主要是因为标签数的增多加大了时隙的碰撞概率，此方面仍需要做进一步的改进．综上所述，本文算法在系统效率和时隙利用率上都有明显的改善，并且算法简单，可操作性强．防碰撞算法是提高RFID系统识别效率的关键．标签估计和帧长度调整方法是动态帧时隙ALOHA算法中改进的主要方面，本文通过对黄金分割法和泊松分布的研究与分析，将其应用到DFSA算法中，采用动态方法估计未识别标签数量，根据设置阈值条件来判断如何进行帧长度的黄金分割调整．通过MATLAB软件的仿真比较，在标签数量较少时，算法的系统效率明显高于常用的动态帧时隙ALOHA算法；同时，该算法在时隙利用率以及减少空时隙数方面都有明显的改善，并且算法简单、可操作性强．【相关文献】[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-basedanti-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．。

可并行识别的分组动态帧时隙ALOHA标签防碰撞算法袁莉芬;杜余庆;何怡刚;吕密;程珍【摘要】In order to solve the problem of low throughput rate and efficiency of the current dynamic frame slot ALOHA collision algorithms, a grouped dynamic frame slotted ALOHA tag anti-collision algorithm based on Parallelizable identification (PIGDFSA) is proposed. Based on the experiments, the method and strategy of increasing the system throughput rate and lowering the tag collision rate are presented by exploring effects of the number of the tags and its groups, the frame length on the system throughout and tag collision rate. Combining the multi-antenna of the RFID system and FastICA technology, the collision slot can be redefined, and the number of the unrecognized tags can be used to set the number of groups and frame length adaptively. The simulation results show that the PIGDFSA algorithm can stabilize the throughput rate more than 92% when the number of tags reaches 2000, and it has higher throughput rate, lesser idle slot and higher algorithm efficiency compared with the FSA-256, GDFSA, and BSDBG algorithm.%该文针对现有动态帧时隙 ALOHA 标签防碰撞算法的系统吞吐率低、算法效率低等问题,提出一种可并行识别的分组动态帧时隙 ALOHA(PIGDFSA)标签防碰撞算法.该文以实验为基础,探索了待识别标签数、标签分组数、帧长对系统吞吐率与标签碰撞率的影响,研究了提升系统吞吐率与降低标签碰撞率的策略与方法.结合射频识别(RFID)的多天线系统,引入FastICA技术,从而实现碰撞时隙重新定义,并以此为基础,利用未识别标签数目自适应确定分组数与帧长.仿真结果表明:PIGDFSA算法在标签数达到2000时,算法吞吐率仍能稳定在92%以上,与FSA-256, GDFSA, BSDBG等算法相比具有更高的算法吞吐率,更少的空隙时隙,更高的算法效率.【期刊名称】《电子与信息学报》【年(卷),期】2018(040)004【总页数】7页(P944-950)【关键词】射频识别;ALOHA算法;FastICA;分组;动态帧时隙【作者】袁莉芬;杜余庆;何怡刚;吕密;程珍【作者单位】合肥工业大学电气与自动化工程学院合肥 230009;合肥工业大学电气与自动化工程学院合肥 230009;合肥工业大学电气与自动化工程学院合肥230009;德州农工大学美国德克萨斯州卡城 TX77843;合肥工业大学电气与自动化工程学院合肥 230009【正文语种】中文【中图分类】TP391.45射频识别(Radio Frequency IDentification, RFID)系统中读写器和标签之间进行通信过程中会产生标签碰撞问题，导致标签的识别准确度、速度和效率等性能变差，标签防碰撞算法成为了当前RFID系统亟待突破的关键技术之一[1,2]。

优化的动态帧时隙ALOHA防碰撞算法郭来功;黄友锐;蔡俊【期刊名称】《计算机应用研究》【年(卷),期】2012(029)011【摘要】对动态帧时隙ALOHA防碰撞算法中的标签个数估计进行改进,采用动态调整机制,使标签个数估计式系数自动调整,解决阅读器下一个查询周期应该使用的帧时隙长度的问题.针对实测中当帧长度与标签个数相等时冲突率较高的问题,将查询命令时间计入总的帧长度中以优化帧长度.仿真结果表明,优化后的DFSA算法延迟时间减少,冲突率降低,系统效率提高,在标签数量较少时效果尤为明显.%To improve the estimation of the number of tags in the dynamic framed slotted ALOHA anti-collision algorithm, this paper used dynamic adjustment mechanism to automatically adjust the formula coefficient of estimation of the number of tags for the problem of the length of the frame slot which the reader should be used in the next polling cycle. For the problem of higher collision rate when the frame length equal to the number of tags, it optimized the frame length by including the query command time in the total frame time. The simulation results show that the optimized DFSA algorithm reduces total delay time and the collision rate, improves system efficiency, especially in the number of tags are less.【总页数】3页(P4141-4143)【作者】郭来功;黄友锐;蔡俊【作者单位】安徽理工大学电气与信息工程学院,安徽淮南232001;安徽理工大学电气与信息工程学院,安徽淮南232001;安徽理工大学电气与信息工程学院,安徽淮南232001【正文语种】中文【中图分类】TN911.23;TP301.6【相关文献】1.动态帧时隙Aloha算法防信息碰撞研究 [J], 曹高峰;卢建军;王晓路2.基于动态帧时隙Aloha的防碰撞算法研究 [J], 陈昊;高勤;安锡文3.基于碰撞预检测的分组动态帧时隙ALOHA防碰撞算法 [J], 陈卓4.可并行识别的分组动态帧时隙ALOHA标签防碰撞算法 [J], 袁莉芬;杜余庆;何怡刚;吕密;程珍5.基于动态帧时隙ALOHA的危险品运输RFID防碰撞算法 [J], 魏福禄;刘攀;李志斌;孙锋;郭永青;曹宁博因版权原因，仅展示原文概要，查看原文内容请购买。