高效的功率可控防碰撞算法

李建雄，邢炳雷，闫必行，刘鹏雪，贾红玉（天津工业大学电子与信息工程学院，天津　300387）



高效的功率可控防碰撞算法

李建雄，邢炳雷，闫必行，刘鹏雪，贾红玉
（天津工业大学电子与信息工程学院，天津300387）

摘要：多标签防碰撞技术是射频识别系统中的关键技术，针对现有的ALOHA防碰撞算法消耗大量的时隙和能量，提出了一种高效的功率可控防碰撞算法.首先，本算法通过对标签UUID进行哈希编码将标签映射到相应的帧时隙，提高了时隙利用率.然后，利用碰撞检测机制，每次只允许无碰撞的标签与阅读器进行通信，从而大大减少了无效通信的过程.最后，采用功率控制机制将标签按区域进行识别，明显地减少了标签碰撞并且节约了通信耗能.通过仿真结果分析可以看出：该算法的性能比已有的防碰撞算法有明显提高，基本满足了RFID系统对标签防防碰撞算法的要求，提高了系统的稳定性.

关键词：射频识别；防碰撞算法；ALOHA；哈希编码；碰撞检测；功率可控

射频识别（radio frequency identification，RFID），是一种近年来逐渐成熟的利用无线传输的识别技术，其通过无线电波自动识别标签数据.与传统识别技术相比，无需直接接触即可完成通信过程，具有识别距离远、操作简单等优点[1].射频识别系统表现出良好的发展趋势，并在医疗、自动化、交通运输管理、定位、产品证件防伪、门禁等众多领域得到了广泛的应用.

阅读器通过天线发送电磁波，电子标签接收到足够的能量后将被激活，将自身信息返回各阅读器，再转达服务器进行处理.当识别区域内的多个标签在同一时刻和阅读器通信时，阅读器将不能正确识别标签，从而降低了通信成功率，因此合理的标签防碰撞算法是RFID研究的重要内容.性能优越的防碰撞算法可以提高射频识别系统的稳定性，更利于其推广.

目前，在国内外RFID系统中使用的防碰撞算法以时分多址最为常见.基于时分多址的标签防碰撞算法主要有两种：一种是随机防碰撞算法[2]，如ALOHA系列算法，其要求标签在通信时随机选择发送时隙；另一种是确定防碰撞算法[3]，如二叉树系列防碰撞算法，其策略为按照树形结构逐步查找所需要的标签.采用标签防碰撞算法可以避免多标签同时和阅读器进行通信，从而保证了整个系统的成功率. ALOHA算法在选择时隙时的随机性，可能会导致个别标签始终无法被成功识别，被称为标签“饿死”现象，而基于二叉树的确定性防碰撞算法虽然可以保证识别成功率，但也存在着算法复杂、识别周期长等问题.

本文根据已存在的ALOHA防碰撞算法[4-8]，提出一种高效的功率可控防碰撞算法.该算法通过对标签UUID进行哈希编码[9]将标签映射到相应的帧时隙，然后利用碰撞检测机制，每次只允许无碰撞的标签与阅读器进行通信，从而大大避免了阅读器与标签间的无效通信过程，提高了时隙利用率，同时采用功率可控机制将标签按识别区域进行识别，明显地减少了标签碰撞并且减少了通信耗能.

1　新型防碰撞算法

本算法是在分组动态帧时隙防碰撞算法[5，7]的基础上提出的，针对多标签识别时产生的大量碰撞的一种改进算法.该算法很好地提升了时隙利用率，减少了阅读器多次查询造成的时隙浪费，不但减少了识别总时间，而且使阅读器在节能方面表现出良好的性能.

1.1算法原理

假设标签均匀分布在识别区域内，本文算法首先需要阅读器对标签进行统计，通过控制阅读器发射功率实现对识别区域的划分，从而实现了将标签按距阅读器的距离分组.功率可控算法的原理如图1所示.

图1　功率可控原理示意图Fig.1 Schematic of power-control

假设将整个识别区域划分为4个子区域，T0代表在有效识别范围d0内的标签群，T1代表在识别范围d1但不包括d0内T0的标签群，T2、T3代表同样意义的标签群.当在识别范围内有大量标签存在时，减少发射功率，也就减少了参与识别的标签，从而也就减少了标签的通信碰撞概率.以图1所示为例，阅读器先发射较小的功率，使有效识别区域为d0，仅与d0区域的标签群T0进行通信；在与T0标签群通信结束后，再增加发射功率至有效识别区域为d1（包含d0），屏蔽掉T0标签群而只与T1标签群通信；在与T1标签群通信结束后，再增加发射功率至有效识别区域为d2（包括d1），屏蔽掉T0和T1标签群而只与T2标签通信；最后，增加发射功率到最大，也就是最大有效识别区域d3，屏蔽掉T0、T1和T2标签群而只与剩下的标签群进行通信.

在每组标签的识别过程中，阅读器首先对标签发送一个带有初始帧长L的查询命令，激活范围内的标签收到来自阅读器的查询命令后进行简单的求余运算，用自身的UUID号对帧长L求余，并存储在标签的时隙标志位中.然后标签将时隙标志位信息返回给阅读器，阅读器统计每个时隙中标签的个数.阅读器生成一个L位的碰撞检测序列，当时隙i为单标签占用时，碰撞检测序列的第i位设置为1，空闲或多标签占用时设置为0，阅读器将此碰撞检测序列发送给激活的标签.标签接收到来自阅读器的碰撞检测序列后，通过查询只允许碰撞检测序列对应位值为1的标签响应阅读器的查询.然后阅读器采用变帧长ALOHA算法进行标签识别直到本组标签全部通信完成，被识别的标签将被设置为静默态不再参与后续的识别过程.

1.2算法模型与实现流程

假设n为识别区域内未识别的标签数目，L表示时隙帧长，且每个帧时隙被标签选中的概率是相等的.根据概率论原理[4，10-11]，标签选择任意时隙的概率为1/L，则有r个标签选择同一时隙的概率为：

式中：Pidle表示一个时隙没被标签占用的概率；Psucc表示一个时隙只有一个标签的概率；Pcoll表示一个时隙被多个标签同时占用而产生标签碰撞的概率.

对上式（1）求导可得最高的系统效率[5，10]，此时

由公式（4）可以得出，当标签数与帧长几乎相等的时候系统识别率最高，因此尽量将帧长设置为与未识别标签数相等，但是帧长不能随着标签数的增长一直变大.当标签数很大时，将标签分成m组和m+1组（m≥1），这时分组的临界标签个数为[5，12]

然后得到识别范围内未识别的标签数与分组数之间的关系[5，12]

例如当m = 1时，得到不分组和分成2组的标签临界值为n = 354；通过式（1）—式（8），得到表1的分组规则.

表1　未识别标签数与帧长大小和分组数的关系Tab.1 Relationship between unrecognized tags，framelength and groups

根据Friis[1，13]公式，能得到阅读器发射功率与识别距离的关系

式中：d为识别半径；λ为电磁波波长；Preader为阅读器发射功率；Greader= 8 dBi和Gtag= 1.2 dB分别为阅读器天线增益和标签天线增益；Preader和Greader均为等效全向辐射功率（EIRP），其在北美地区限制在4 W内；p为阅读器天线和标签天线的极化匹配因子（极化完全匹配时，p = 1），ptr= -15 dBm表示无源标签的最小工作门限；τ为标签天线和标签芯片的功率传输因子（共轭阻抗匹配时，τ= 1）.

假设阅读器的最大识别半径为dmax= 10 m，并且标签均匀分布在识别区域内，即标签密度为ρ= n/πd2max，通过结合表1中的数据能够到图1中具体的di值

式中：m表示分组的临界值，根据公式（11），能得到di值对应的阅读器的发射功率Pi值

在每组标签的识别过程中，阅读器采用哈希映射碰撞检测机制，标签收到查询命令后将自身唯一识别码（UUID）对帧长L求余并存储在时隙标志位中，即此标签在帧时隙中对应的时隙号

式中：NUM为时隙标志位值，将NUM返回给阅读器.阅读器接收并统计来自标签发来的NUM值，以11个标签（标签UUID为1～1 000内的值），帧长L以8为例，如表2所示.表2中Y表示此时隙有标签占用，N表示此时隙没有标签占用.

表2　帧时隙响应情况Tab.2 Response of time slots

阅读器统计接收到NUM值，得到数据如表3所示.

表3　帧时隙的占用情况Tab.3 Use of time slots

阅读器端建立了一个碰撞检测序列[14]，将只有单标签占用的时隙设置为1，无标签或者多标签占用的时隙设置为0，则有表4所示碰撞检测序列.

表4　生成的碰撞检测序列Tab.4 Generated collision detection sequence

阅读器将生成的碰撞检测序列发送给标签，标签通过查询自己的时隙标志位值对应的碰撞检测序列值是否为1，如果标签的NUM值为1，则阅读器将对该标签进行无碰撞识别，否则，不对该标签进行识别.

具体识别过程为：

（1）阅读器发射全功率对标签进行扫描，利用切比雪夫不等式[15]统计出识别范围内的待识别标签数，依据表1的规则确定阅读器的功率级Pi（置初始值i = 0）.

（2）阅读器使用功率级Pi激活di内的Ti标签群，并发送初始帧长L.

（3）Ti标签群将自身UUID与接收到的帧长L进行哈希处理得到自身的时隙标志位NUM值，并返回NUM值给阅读器.

（4）阅读器接收标签的NUM值信息，统计整个帧长的时隙占用情况，然后将生成碰撞检测序列返回给标签.

（5）标签接收到碰撞检测序列后与自身时隙标志位进行对比，如果时隙标志位对应的碰撞检测序列中的位值为1，则参与此次无碰撞识别过程；若为0，则不参与此次识别过程.

（6）每轮识别过程结束，识别完成的标签被设为静默态，阅读器利用切比雪夫不等式估计未识别标签数.若未识别标签数不为0，调整帧长L重复步骤（3）—步骤（6）；若未识别标签数为0，进入（7）.

（7）调整阅读器发射功率级Pi进行下一组标签的识别，重复步骤（2）—步骤（6），直到整个识别区域的标签数全部被识别.

2　仿真结果

本节将本文提出的算法与BFSA、DFSA、EDFSA进行详细的比较.通过对比不同标签个数时阅读器成功识别所有标签所需的总时隙数，消耗时间和消耗的能量来比较算法的性能.为了保证仿真的效果，假设为理想实验环境：在半径为10 m的圆形内均匀地分布着1 000个标签，并且每个标签都能被正确读取.为了保证实验精度，取100次仿真结果的平均值.

比较BFSA、DFSA、EDFSA和本文提出的算法所需的时隙数如图2所示.从图2可以看出，BFSA算法所需的时隙数成指数增长.当标签数为450以内时，DFSA和EDFSA需要的时隙数差不多，但随着标签的增加，EDFSA的优势越来越明显.从仿真结果可以看出，本文提出的算法与已有的几种ALOHA算法相比具有明显的优势.当标签数为1 000时，本文提出的算法比BFSA、DFSA和EDFSA所用的时隙数分别减少了76.79%、75.93%和55.17%.由于本文提出的算法采用了功率可控机制，减少了同时参与通信的标签；同时哈希编码和碰撞检测机制，有效地减少了无效时隙的参与，仿真结果与理论预期相符.

图2　所需时隙数的比较Fig.2 Comparison of required number of time slots

识别标签所消耗的时间[2，6]是衡量防碰撞算法性能的另一个重要指标. EDFSA算法因为采用了分组机制，当标签数大于500时，在节省时间上会表现出明显的优势.纵观整个识别过程，本文提出的算法虽然在碰撞检测阶段增加了一次访问标签的时间，但其极大地减少了标签通信失败和无效时隙参与造成的时间损耗，消耗时间情况如图3所示.由图3可以看出，当标签数为1 000时，本文提出的算法比BFSA、DFSA 和EDFSA所消耗的时间分别减少了78.57%、76.92% 和62.5%，证实本文提出的算法在识别效率上表现出良好的性能.

图3　消耗时间的比较Fig.3 Comparison of time consumption

基于本文提出的功率可控机制，识别标签消耗的能量也成为考察算法性能的重要指标.已存在的防碰撞算法均采用最大功率完成识别过程，当大部分标签距离阅读器较近时会造成能量的浪费.功率可控机制使阅读器每次都用尽可能小的功率来识别标签，而不是一直使用最大功率完成识别过程，消耗能量情况如图4所示.从图4中明显看出，本文提出的算法可以节约大量的能量，当标签数为1 000时，本文提出算法所需的耗能仅为BFSA、DFSA和EDFSA算法的13.33%、15.38%和22.2%，非常符合国家提出的节能减排规划.

图4　消耗能量的比较Fig.4 Comparison of energy consumption

3　结论

（1）利用哈希映射时隙机制替代了原来的标签随机选择时隙方法，降低了标签碰撞的概率.

（2）引入碰撞检测机制，这样不但避免碰撞的标签参与识别过程，而且避免了空闲时隙和碰撞时隙造成的额外开销.

（3）采用功率可控机制，一方面将同时参与识别的标签数减少了，另一方面减少了识别所消耗的能量.

（4）将本文提出的算法与BFSA、DFSA和EDFSA进行详细比较，结果表明：本文提出的防碰撞算法在识别过程中消耗的总时隙数、消耗的时间和耗能方面均有良好的表现，提高了RFID系统的稳定性.

参考文献：

[1]周晓光，王晓华.射频识别（RFID）技术原理与应用实例[M].北京：人民邮电出版社，2006. ZHOU X G，WANG X H. The Principle and Application of Radio Frequency Identification（RFID）Technology[M].Beijing：The People′s Posts and Telecommunications Press，2006（in Chinese）.

[2] VOGT H. Multiple object identification with passive RFID tags [C]//2002 IEEE International Conference on Systems. [s.l.]：Man & Cybernetics，2002：98-113.

[3]余松森，詹宜巨，彭卫东.基于后退式索引的二进制树形搜索反碰撞算法及其实现[J].计算机工程与应用，2004，40 （16）：26-28. YU S S，ZHAN Y J，PENG W D. An anti-collision algorithm based on binary -tree searching of regressive index and its practice [J]. Computer Engineering and Applications，2004，40 （16）：26-28（in Chinese）.

[4]程文青，赵梦欣，徐晶.改进的RFID动态帧时隙ALOHA算法[J].华中科技大学学报：自然科学版，2006，35（6）：14-16. CHENG W Q，ZHAO M X，XU J. Enhanced dynamic frame slotted ALOHA algorithm for anti-collision in RFID systems [J]. Journal of Huazhong University of Science and Technology：Nature Science Edition，2006，35（6）：14-16（in Chinese）.

[5] WANG H，XIAO S L，LIN F Y. Group improved enhanced dynamic frame slotted ALOHA anti-collision algorithm [J]. The Journal of Supercomputing，2014，69（3）：1235-1253.

[6] DENG D J，TSAO H W. Optimal dynamic framed slotted ALOHA based anti-collision algorithm for RFID systems [J]. Wireless Personal Communications，2011，59（1）：109-122.

[7] LEE S R，LEE C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C]//Emerging Directions in Embedded and Ubiquitous Computing Lecture Notes in Computer Science. [s.l.]：[s.n.]，2006：403-412.

[8]吴春华，陈军.动态ALOHA法在解决RFID反碰撞问题中的应用[J].电子器件，2003，26（2）：173-176. WU C H，CHEN J. Application of dynamic ALOHA in RFID′s collision [J]. Journal of Electron Devices. 2003，26（2）：173-176（in Chinese）.

[9]王骁，郭网媚，肖鹤玲，等.基于哈希函数的高效完善安全网络编码算法[J].华中科技大学学报：自然科学版，2013，41（5）：102-104. WANG X，GUO W M，XIAO H L，et al. Efficient perfect secure network coding algorithm using Hash function [J]. Journal of Huazhong University of Science and Technology：Nature Science Edition，2013，41（5）：102-104（in Chinese）.

[10]尹君，何怡刚，李兵.基于分组动态帧时隙的RFID防碰撞算法[J].计算机工程，2009，35（20）：267-269. YIN J，HE Y G，LI B. RFID anti-collision algorithm based on groupingdynamicframeslotted[J].ComputerEngineering，2009，35（20）：267-269（in Chinese）.

[11] YANG Q，LI J C，WANG H Y. A dynamic framed slotted ALOHA anti -collision algorithm based on tag -grouping for RFID systems [C]//2012 IEEE 11th International Conference. Xi′an：[s.n.]，2012：1-3.

[12]徐圆圆，曾隽芳，刘禹.基于ALOHA算法的帧长及分组数改进研究[J].计算机应用，2008，28（3）：588-590. XU Y Y，ZENG J F，LIU Y. Research of optimizing frame size and group division in aloha-based algorithms [J]. Computer Applications，2008，28（3）：588-590（in Chinese）.

[13] KIM I，XU S，RAHMAT-SAMII Y. Generalised correction to the friis formula：Quick determination of the coupling in the Fresnel region [J]. IET Microw，Antennas Propage，2013，13 （7）：1092-1101.

[14]李建成.射频识别系统空中接口通信协议关键技术研究与实现[D].长沙：国防科学技术大学，2011. LI J C. Research and implementation technologies of communication protocol for RFID air interface [D]. Changsha：Graduate School of National University of Defense Technology，2011（in Chinese）.

[15]王萌，陈殿仁. RFID系统多标签识别防碰撞算法[J].太赫兹科学与电子信息学报，2013，11（4）：601-605. WANG M，CHEN D R. Anti-collision multi-tag identification algorithms for RFID systems[J]. Journal of Terahertz Science and Electronic Information Technology，2013，11（4）：601-605 （in Chinese）.

Efficient anti-collision algorithm based on power-control

LI Jian-xiong，XING Bing-lei，YAN Bi-xing，LIU Peng-xue，JIA Hong-yu
（School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China）

Abstract：The technology of multi-tag anti-collision is the key in radio frequency identification（RFID）system，in view of the existing problem that ALOHA anti-collision algorithms consume a lot of time solts and energy，an efficient anti-collision algorithm based on power-control is proposed. First，the UUID of tags will be done hash coding and the tags will be mapped to the corresponding slots in this algorithm to improve the utilization rate of slots. Then，collision detection mechanism allows only non-collision tags to communicate with the reader，thereby greatly reduces the ineffective communication process. Finally，the power-control mechanism to identify the tags by region significantly reduces the tag collision and saves the energy consumption of communication. It is found from the analysis of simulation results that the performance of the algorithm has been improved significantly compared with the existing anti-collision algorithms. It can satisfy the RFID system requirement of anti-collision algorithm，which improves the stability of system.

Key words：radio frequency identification（RFID）；anti-collision；ALOHA；Hash code；collision detection；power-control

通信作者：李建雄（1969—），男，副教授，硕士生导师，主要研究方向为射频识别技术、微波技术与天线、电磁场的数值计算. E-mail：lijianxiong@tjpu.edu.cn

基金项目：国家自然科学基金资助项目（61372011）；天津市应用基础与前沿技术研究计划项目（15JCYBJC16300）

收稿日期：2015-07-17

DOI：10.3969/j.issn.1671-024x.2016.02.014

中图分类号：TP311

文献标志码：A

文章编号：1671－024X（2016）02－0072－05