, 王祖良 2 , 李鑫 3 1. 清华大学 软件学院, 北京 100081;
2. 西京学院 信息工程学院, 西安 710123;
3. 装甲兵工程学院, 北京 100072
收稿日期：2016-10-13
基金项目：国家自然科学基金重大项目（61190110）
作者简介：田川(1976年-), 男, 博士研究生
通信作者：叶晓俊, 教授。E-mail:yexj@tsinghua.edu.cn
摘要：EPCglobal_Class1 Gen2协议标准中的动态帧时隙ALOHA标签防碰撞Q算法没有完全消除空时隙，浪费了时序资源，在血液管理这种实时性要求高、标签数量大的情况下是不能接受的。该文提出一种多标签识别碰撞避免方法，将标签识别过程分为两次时隙预分配和标签识别2个阶段，消除了Class1 Gen2协议的空时隙以提高时间利用率。对血液管理应用场景进行了数值仿真分析，结果表明该方法能够显著提高标签识别效率。
关键词：射频识别碰撞避免动态帧时隙ALOHA
Multi-tag identification and collision avoidance with RFIDs in blood management
TIAN Chuan1, YE Xiaojun1
, WANG Zuliang2, LI Xin31.College of Software, Tsinghua University, Beijing 100081, China;
2.Department of Electronic and Information Engineering, Xijing University, Xi'an 710123, China;
3.Academy of Armored Forces Engineering, Beijing 100072, China
Abstract: The dynamic frame slotted ALOHA tag anti-collision Q algorithm in the EPCglobal_Class1 Gen2 protocol fails to remove empty slots, which leads to a waste of the slots. This is unacceptable in blood management which requires real-time handling and a large number of tags. A multi-tag identification and collision avoidance method was developed that divides the tag identification into two slot pre-assignments and tag identification. This helps eliminate empty slots in the Class1 Gen2 protocol which improves availability. Simulations of a blood management system indicate that this method significantly improves tag identification efficiency.
Key words: radio frequency identification (RFID)collisions avoidancedynamic frame slotted ALOHA
在血液管理过程中涉及到大量的数据信息(如献血者的资料、血液类型、采血时间、地点、采血者等)，传统的血液管理系统主要采用条形码标准技术，其标签信息存储量小，而且是只读信息，要完成对血液使用流程的管理和跟踪，可能要使用多个条码。同时，条形码在潮湿环境或受磨损的情况下，其可读性会大大降低，甚至会产生误读的情况。随着对血液管理要求的不断提高，传统的条码技术日益显出其局限性，因此人们开始采用物联网领域广泛应用的射频识别(RFID)技术，以解决血液管理中的质量跟踪和追溯管理，提高血液采供效率。
RFID作为一种新的自动识别技术具有强大的技术优势，如存储容量大、使用时间更长、读写速度更快、数据可动态更新、非接触式读取、穿透性强、可运动读写、适用复杂环境等。因此，将RFID技术应用于血液管理具有广阔的应用前景，目前RFID技术已在包括移动采血、质检、运输、血液批量入出库、紧急入出库、医院用血、自动盘点库存等环节的血液全程追溯开展了试点应用。系统运营过程中发现，多个环节均要求阅读器能够在极短时间内对移动血袋(其上附着电子标签)进行可靠的批量识别，这就要求RFID系统具备快速的通信和处理速度。
目前常用的RFID频率大致分为高频、超高频和微波3个频段。相比之下，超高频段比较适合这一领域的应用。目前EPCglobal的Class1 Gen2(简称EPC_C1 G2)协议标准在这一领域得到了业界的认可和广泛应用，该协议工作在860~960 MHz[1]。从实际工程发现，阻碍RFID技术在血液管理中应用的最大障碍是在快速移动环境下标签漏读率仍然过高，达不到实用化的要求。究其原因，除了血液本身的液体属性、血液中的金属离子等特性对无线电波传播产生影响导致物理层通信失败以外，EPC_C1 G2协议过程中的标签碰撞是导致标签漏读的重要原因。
在EPC_C1 G2协议标准中，标签防碰撞是采用动态帧时隙ALOHA算法(DFSA)实现的[1]。DFSA算法近年来得到了广泛关注。文[2]提出了帧长随待识别标签数变化的DFSA协议。文[3]按照标签数量动态调整帧长以获得高的识别效率。文[4]提出利用中断机制实现的动态帧时序ALOHA协议，在标签数量范围很大时具有明显的优越性。文[5]针对EPC_C1 G2标准所采用的DFSA算法，提出一种基于碰撞标签数和空闲时序估计的改进型DFSA算法，阅读器根据估计值调整帧长，比传统DFSA算法能明显缩短估计时间。文[6]从理论上证明了当帧长等于待识别节点数时，识别效率达到最优。针对EPC_C1 G2协议标准，文[7]提出了终止剩余低效时隙等方法与技术，进一步提高了动态帧时隙DFSA算法的识别效率。以上文献提出的DFSA算法时间分配均采用随机分配方法，随机分配会出现标签多次无法被识别的“饿死”现象，在移动的多标签批量识别环境中极易引起标签漏读，无法满足血液管理这种大数量标签高识别率要求的应用环境。因此，文[8]采用预约时隙的方法以显著提高标签识别效率。
本文在分析研究了用于血液管理的EPC_C1 G2动态帧时隙防碰撞算法需求后，在文[8]的基础上提出将标签识别过程分为两次时隙预分配和标签识别2个阶段的碰撞避免方法，进一步提高标签的识别效率。同时利用数值仿真，对该方法在潜在应用中的参数值设置进行优化分析。
1 EPC_C1 G2防碰撞方法在血液管理等大规模标签批量识别应用环境下，被动式电子标签由于成本低、无需提供电源等优点而得到广泛应用。然而，被动式电子标签计算能力有限，它们无法感应信道、觉察碰撞或与其他标签进行通信，一旦接收到阅读器指令便立即发送响应，所以碰撞不可避免会发生。当2个或2个以上标签同时响应阅读器时，这些信号会相互干扰，从而使阅读器无法读取任何一个标签的信息，影响了标签识别的效率。因此，需要通过一定的方法来减少标签碰撞，提高识别速度和效率。
RFID防碰撞算法有ALOHA算法、基于二进制树的算法和混合算法等3种。在RFID的大多数应用领域尤其是血液管理这样的大规模标签应用领域，采用ALOHA算法较为适合。该算法由标签驱动，每个标签随机地选择一个时间点进行传输。这种算法实现简单，成本低。ALOHA算法分为纯ALOHA(pure ALOHA，PA)、时序ALOHA(slot ALOHA, SA)、帧时序ALOHA(frame slot ALOHA, FSA)等，FSA又分为基本帧时序ALOHA(basic frame slot ALOHA，BFSA)和动态帧时序ALOHA(dynamic frame slot ALOHA，DFSA)。
EPC_C1 G2标准的标签防碰撞算法引起研究者的极大关注[7-12]，该标准采用DFSA算法，实例如图 1所示，包括4个标签(Tag1~4)，帧长度为4个时隙(Slot1~4)。
 |
| 图 1 EPC_C1 G2标签防碰撞算法实例 |
| 图选项 |
EPC_C1 G2标签防碰撞算法基本流程如下：
1) 首先阅读器通过广播命令选择标签。阅读器覆盖范围内的所有标签一旦感知到阅读器即进入准备状态，等待阅读器命令。阅读器经过一定时间延迟后发送包含帧长Qfp参数的Query命令，标签通过随机数产生器产生一个在范围0~2Qfp内的随机数，并将此随机数存入时隙计数器SC中。如果该随机数为0，则立即发送RN16随机数，如果只有一个标签在该时隙发送RN16，例如图 1中Slot1时隙中只有Tag2标签发送数据，则阅读器能够正确接收RN16。正确接收RN16的前提下阅读器向标签发送带有该RN16的ACK确认信息，标签收到此信息即建立了一对一通信链路，可以进行标签数据的读取操作，例如图 1中Tag2标签向阅读器发送电子产品编码(EPC)。
2) 完成一个完整的标签识别后，阅读器向该电子标签发送灭活指令，此后该标签进入静默状态不再参与后续标签识别过程。随机数大于0的标签进入ARBITRATE状态等待后续Rep命令或者Adjust命令。
3) 完成一个时隙处理后，阅读器发送Rep命令，开启一个新的时隙。所有存活标签收到Rep命令后将计数器减1，如果标签随机数为0，立即发送RN16，否则进入ARBITRATE状态。如果在一个时隙内有多于一个标签发送RN16，则产生碰撞，例如图 1中Slot2时隙有标签Tag1和Tag3同时向阅读器发送RN16。阅读器利用曼彻斯特编码能检测到标签碰撞的原理感知到碰撞发生，便向在该时隙中发送RN16的2个标签(Tag1和Tag3)发送NAK信息，指出该时隙发生碰撞，并向所有存活标签发送Rep命令开启一个新的Slot。发生碰撞的标签收到NAK信息后，将时隙计数器设置为7FFF，并进入ARBITRATE状态等待Adjust命令参与新一帧的识别。如果阅读器在一个时隙中未收到任何标签的回应，则该时隙为空时隙。完成本帧所有时隙，或者阅读器根据空时隙、碰撞时隙数量确定调整Q参数后，开启一个新帧继续对未识别的标签进行识别，直到完成全部标签识别，结束标签识别处理。Adjust命令的调整算法采用图 2的Q算法[11]。标签收到Query命令后按要求产生一个随机数，并存入SC中，每收到一个Rep命令则SC减1，直到结果为0才响应阅读器。
 |
| 图 2 自动调整帧长Q算法 |
| 图选项 |
如果Q的取值相对较大，而标签数量相对较少，则有可能产生更多的空时隙；相反，如果Q的取值相对较小而标签数量较多，则有可能产生更多碰撞。因此，参数Q需要根据实际应用进行精细调整。
2 基于预约机制的防碰撞算法EPC_C1 G2标准按照标签响应情况采用自动Q算法实现帧长度的调整。Q为整数，用来指示标签产生随机数的范围，Qfp为浮点数，是Q的精确值，Q是最接近Qfp的整数。Qfp初始值等于4.0，c为调整步进，c∈[0.1, 0.5]。EPC_C1 G2标准采用非等长帧，相对于固定帧长度的方法，有效提高了识别效率。此外，该算法根据当前帧的识别时隙数、空时隙数和碰撞时隙数决定是否终止当前帧，开启新的帧识别，显著降低了空时隙数和碰撞时隙数，进一步提高识别效率。然而，这种方法并没有完全杜绝空时隙的产生，浪费了宝贵的时序资源。这在血液管理这种实时性要求高，标签数量大的应用情况，尤其不能接受，采用预约时隙的方法可以显著提高标签识别效率[11]。本节在文[11]的基础上提出一种两次预分配的方法，进一步提高识别效率。
2.1 算法处理流程预分配时隙方法将整个识别过程分为2个阶段：预分配时隙和标签识别。在预分配时隙阶段，阅读器安排一定数量的预分配短时隙，并向覆盖范围内的所有标签发送带有Q参数的预分配ReAss命令。标签接收到ReAss命令，利用随机数产生器产生一个介于0~2Q之间的随机数r作为本标签的分配时隙预约号，并存入SC计数器。用同样方法产生一个长度为l的预分配码RCk(k=1, 2, …, n，其中n为阅读器覆盖范围内的标签总数)，并在时隙r内向阅读器回传预分配码RCk。设Si时隙所对应的预分配队列为SMi(0≤i＜2Q)，阅读器按照接收到的预分配码设置预分配队列SMi，第i个时隙如果成功接收到单一标签发送的预分配码RCk，则该时隙为识别时隙，置SMi=1。如果第i个时隙没有标签发送预分配码，则该时隙为空时隙SMi=0，空时隙在标签识别阶段并不分配时隙，从而避免了时隙浪费。否则如果第i个时隙有多个标签同时发送了预分配码，从而产生了预分配码碰撞，则SMi=2，同时，碰撞时隙计数器CoCount进行加1计数。还有一种特殊情况，如果多个标签选择了同一时隙，并且预分配码也相同，由于阅读器和标签之间的通信采用ASK调制方式，此时信号得到加强，阅读器可以正确解调预分配码，导致预分配冲突，这种冲突在预分配阶段无法感知，只有到后续标签识别阶段才会被检测到，所以这种预分配冲突无法避免。当第1次预分配完成以后，为了在预分配时隙阶段尽可能多地分配识别时隙，以保证标签识别阶段尽可能多地正确识别标签，将第1次预分配存在冲突的时隙再进行一次预分配。阅读器利用碰撞计数器作为参数，向碰撞标签发送二次预分配命令ReAss2，碰撞标签接到二次预分配命令后进行与第1次分配类似的操作。阅读器根据收到的二次预分配码更新SM队列。
在标签识别阶段，阅读器根据预分配队列发送识别命令。首先指针复位为i=0，判断指针当前所指队列位置，如果当前队列SMi的值为1则发送带当前时隙号的标签识别命令，标签接收到识别命令将时隙号i与本标签保存的预约号r进行比对，如果相等则响应阅读器，回传本标签ID号，完成识别，并进行灭活处理，在后续识别过程中不再参与识别过程。阅读器处理流程如图 3所示，对应的标签处理流程与之类似。
 |
| 图 3 阅读器处理流程 |
| 图选项 |
2.2 算法性能分析由于整个识别过程分为时隙预分配和标签识别2个阶段，预分配阶段传送的数据长度相比标签识别阶段的要短许多，加之本文分析性能主要是为参数优化提供依据，不进行绝对性能的比较，因此为简单起见不考虑预分配阶段时隙间隙和等待时间。将识别效率定义为平均识别标签数与占用时隙数之比。可分配时隙数为2Q，n个标签中有k个标签选择2Q个时隙中的一个时隙的概率Pk服从二项分布，由二项分布公式得
| ${{p}_{k}}=\left( \begin{matrix} n \\ k \\\end{matrix} \right){{\left( \frac{1}{{{2}^{Q}}} \right)}^{k}}{{\left( 1-\frac{1}{{{2}^{Q}}} \right)}^{n-k}}.$ | (1) |
| ${{\mathit{p}}_{\rm{ck}}}=\left( \begin{matrix} n \\ k \\\end{matrix} \right){{\left( \frac{1}{{{2}^{Q}}} \right)}^{k}}{{\left( 1-\frac{1}{{{2}^{Q}}} \right)}^{n-k}}\left( \begin{matrix} {{2}^{l}} \\ 1 \\\end{matrix} \right){{\left( \frac{1}{{{2}^{l}}} \right)}^{k}}.$ | (2) |
| ${{\mathit{P}}_{\rm{collision}}}=\sum\limits_{k=2}^{n}{\left( \begin{matrix} n \\ k \\\end{matrix} \right){{\left( \frac{1}{{{2}^{Q}}} \right)}^{k}}{{\left( 1-\frac{1}{{{2}^{Q}}} \right)}^{n-k}}\left( \begin{matrix} {{2}^{l}} \\ 1 \\\end{matrix} \right){{\left( \frac{1}{{{2}^{l}}} \right)}^{k}}.}$ | (3) |
| ${{\rm{2}}^{\mathit{Q}}}{{\mathit{P}}_{\rm{collision}}}={{\rm{2}}^{\mathit{Q}}}\sum\limits_{k=2}^{n}{\left( \begin{matrix} n \\ k \\\end{matrix} \right){{\left( \frac{1}{{{2}^{Q}}} \right)}^{k}}{{\left( 1-\frac{1}{{{2}^{Q}}} \right)}^{n-k}}\left( \begin{matrix} {{2}^{l}} \\ 1 \\\end{matrix} \right){{\left( \frac{1}{{{2}^{l}}} \right)}^{k}}.}$ | (4) |
| $\eta =\frac{n{{\left( 1-\frac{1}{{{2}^{Q}}} \right)}^{n-1}}}{\frac{l{{2}^{Q}}}{m}+{{\rm{2}}^{\mathit{Q}}}\sum\limits_{k=2}^{n}{\left( \begin{matrix} n \\ k \\\end{matrix} \right){{\left( \frac{1}{{{2}^{Q}}} \right)}^{k}}{{\left( 1-\frac{1}{{{2}^{q}}} \right)}^{n-k}}\left( \begin{matrix} {{2}^{v}} \\ 1 \\\end{matrix} \right){{\left( \frac{1}{{{2}^{l}}} \right)}^{k}}+n{{\left( 1-\frac{1}{{{2}^{Q}}} \right)}^{n-1}}}}.$ | (5) |
 |
| 图 4 识别效率与预分配码长数值仿真结果 |
| 图选项 |
由图 4可知，识别效率μ随着Q值的增加而提高。当Q=3时，无论l为多少(1~16)，μ均近似为0。这是由于此时可预分配的时隙数仅为8，待识别标签数为100，相差太大，所以识别效率太低，近似为0。另一方面，当Q大于等于8时，再加大Q对识别效率的改善已不显著，Q等于8、9、10三条曲线在l大于4以后几乎重合。这是由于当Q大于或等于8时，可预分配时隙数大于等于256，是待识别标签数的2.5倍以上，由于当帧长等于待识别节点数时，识别效率达到最优[6]，过大的Q反而带来通信资源的过度开销，会导致系统综合性能下降。考查预分配码长度对识别性能的影响，综合所有有效的7条Q值曲线(除Q=3外)，l取值存在最优值，大概在3到4之间，实际工程设计中可取为4。此时，除Q为3和4之外，其余4条曲线识别率均高于80%，最高的3条曲线甚至达到90%。
Q=8；n从10到400变化，步进为10；预l为3、4、5作为控制参数进行仿真试验，结果如图 5所示。
 |
| 图 5 识别效率随待识别标签数变化的数值仿真结果 |
| 图选项 |
从图 5看出，当固定Q=8时，μ随着n的增加而增加，对于l=3的曲线，当n大于100时μ开始下降，对于l为4和5的曲线，当n大于200时μ开始下降。
3 结论本文提出的多标签识别碰撞避免方法将标签识别过程分为两次时隙预分配和标签识别2个阶段，消除了EPC_C1 G2标准的空时隙，显著提高了标签识别效率。数值仿真结果表明识别效率随着Q的增加而增加，但当Q大于或等于8时，再增加Q对识别效率的改善已不明显，因此在给定标签数和标签ID长度的前提下存在最佳的Q。同时，在给定这两个值的前提下，预约分配码长度也存在最优值，本文仿真环境下l=4是最佳预分配码长度。
下一步需要对参数进行综合仿真优化，以获得更有价值的研究成果，用以指导实际工程应用中关键参数的设计。
参考文献
| [1] | EPCglobal. EPCTM radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860 MHz-960 MHz version 1.2.0[S]. EPCglobal, 2008. |
| [2] | Schoute F C. Dynamic frame length ALOHA[J]. IEEE Transactions on Communication, 1983, 31(4): 565–568. DOI:10.1109/TCOM.1983.1095854 |
| [3] | Kaewsirisin S, Supanakoon P, Promwong S, et al. Performance study of dynamic framed slotted ALOHA for RFID systems[C]//International Conference on Electrical Eng-ineering/electronics, Computer, Telecom-munications and Information Technology. Krabi, Thailand:IEEE Press, 2008:413-416. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=4600459 |
| [4] | CUI Yiheng, Wang Huiying. A new anti-collision method for RFID systems[C]//Computational Intelligence and Informatics (CINTI). Budapest:IEEE Press, 2011:51-55. http://ieeexplore.ieee.org/document/6108557/ |
| [5] | Kim S C, Kim S K. An Enhanced Anti-collision Algorithm for EPC Gen2 RFID System[C]//5th FTRA International Conference on Multimedia and Ubiquitous Engineering, Crete, Greece:IEEE Press, 2011:293-296. http://dl.acm.org/citation.cfm?id=2060497 |
| [6] | Barletta L, Borgonovo F., Cesana M. A formal proof of the optimal frame setting for dynamic-frame ALOHA with known population size[J]. IEEE Transactions on Information Theory, 2014, 60(11): 7221–7230. DOI:10.1109/TIT.2014.2354642 |
| [7] | Lei Zhu, Tak S, Peter Y. The optimal reading strategy for EPC Gen-2 RFID anti-collision system[J]. IEEE Transactions on communications, 2010, 58(9): 2725–2733. DOI:10.1109/TCOMM.2010.080310.090421 |
| [8] | CHEN Yihong, FENG Quanyuan, MA Zheng, et al. Multiple-bits-slot reservation ALOHA protocol for tag identification[J]. IEEE Transactions on Consumer Electronics, 2013, 59(1): 93–100. DOI:10.1109/TCE.2013.6490246 |
| [9] | Leonardo D, Sánchez M, Víctor M. Adding randomness to the EPC Class1 Gen2 standard for RFID networks[C]//IEEE 23rd International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC). Sydney, Australia:IEEE Press, 2012:609-614. http://ieeexplore.ieee.org/document/6362856/ |
| [10] | Iztok B, Andrej V, Andrej T. Resolving collision in EPCglobal Class-1 Gen-2 system by utilizing the preamble[J]. IEEE Transactions on wireless communications, 2014, 13(10): 5330–5339. DOI:10.1109/TWC.2014.2350975 |
| [11] | Ehsan V, Rabab K, Ian F. Performance analysis of RFID protocols:CDMA versus the standard EPC Gen-2[J]. IEEE Transactions on Automations Science and Engineering, 2014, 11(4): 1250–1261. DOI:10.1109/TASE.2013.2295394 |
| [12] | Hessar F, Roy S. Energy based performance evaluation of passive EPC Gen 2 Class 1 RFID systems[J]. IEEE Transactions on Communications, 2013, 61(4): 1337–1348. DOI:10.1109/TCOMM.2013.13.110603 |
