俘获效应主导态下的RFID标签防碰撞算法基础分析

俘获效应主导态下的 RFID 标签防碰撞算法基础分析

孟凯1，丁伟超 2

1. 武警工程大学装备管理与保障学院，陕西 西安 710086

2.石河子大学政法学院，新疆 石河子 832003

摘要：置于分别或交叉建立在ALOHA之随机性算法及树型态之确定性算法背景上的RFID防碰撞算法确存位于原有基础上的独立或综合性优化，并有效映射在数次查询减少、查询探深浅化、通信当量降低等确定算法之需求场上以及时隙留白减少、时隙撞车减少等随机算法需求场上而未失其优化之用。然无论系单角度抑或双角度结合再优化，纵使将算法放于理想态中，时隙识别率仍在相对范围内约持37%-61%的较低水平。读写器实施识别时会显明专一性的确认强信号信息递送标签而将弱信号标签行使的信息递送视为杂外干扰信号继而剔除之，即因信号所具功率差异而产生的强弱覆盖，使读写器实施工作时仅能做出强信号标签递送识别之捕获，对弱信号进行了放弃。如此，两种算法皆未考量实存的该种俘获效应（Erfassungseffekt）作用，故在此针对俘获效应加入后基于动态背景下动态帧时隙分组检校算法于效用上生发的查询时隙、查识率及通信复杂度方面的作用进行概要的确认分析。

关键词：RFID；防碰撞算法；CGCT算法；DFSA-CCG算法；俘获效应

1. 引言

RFID系统，即射频识别系统，是以电磁波为传输介质来实现数据双向通信的无接触式自动识别技术^[1]，由电子标签/标签（Tag）、读写器/解读器（Reader）和后台系统（Background）三大结构构建。其主要运行框架系基于以电磁波为传导介质所发生的无线射频信号对系统组成中电子标签结构进行呼叫，进而使另一结构读写器响应，实现电子标签和读写器间信息数据互换交流，读写器采集信源后呼叫系统第三组成结构即系统主机端，该端立即回应，续同呼应端进行信息数据再交换，得完成终端和需求对象间的身份识别认证。实际应用场景中，识别标签需求通常具有规模性。多数量待识别标签会周边环绕个体的读写器，自读写器产生查询命令并向周界发送时，于功率支持的识别范围内存在的周边标签均会同时或错时以身份文件（ID）信息发送之方式发生响应，以使读写器需求得到满足。由于双方系以一对多逻辑发生链接，此时若有数标签同时给予回应，则必然出现信息通道冲突，即多个标签碰撞撞车情况。故何以优化过程识别算法，最大化避免标签同占信道而造成标签撞车现象出现几率RFID高查识率的硬性门槛。

当前传统算法已经由不同方向改良，但仍在改进方向上具有一定局限性。在非理想的射频识别实用环境中，待识标签不均匀的散布于可查询范围内，造成读写器同单个标签的射频距离不等，且待识标签亦或有批次原因导致的新旧不一问题，如此远距离或旧化标签信息发出功率大幅减退，相反标签识别请求之功率少有衰退。故解读时，读写器基于信源功率差异导致的不同信号强度而有选择回应，解读结果即为弱信号标签识别请求失败，对范围中更强信号标签查识成功。大比例的防碰撞算法皆缺少该过程中有关俘获效应的考量。

2. 俘获效应主导态下的RFID标签二性质防碰撞算法

1. 算法路径

1. 算法思路

俘获效应型态主要有二：一是基于距离比值；二是基于SNR（讯噪比）。第一型态系基于一定距离比值，俘获效应即发生在若该距离之比值超过某下限临界值时；第二型态系基于S/N,俘获效应发生在讯噪比超过某门限值（设该值为z₀）时。鉴于第一俘获型态下的个体待识标签和阅读器的间距在群体标签无显然差异，且有读写器解读距离之局限，故排除其于RFID系统算法中的使用而选取第二俘获型态。对构建的俘获效应模型进行分析：

设 俘获因子, 标签数量。

有以下：

在强度各异的标签信号在可查识区域内同期回应读写器解读指令时，高强度标签释放的信号掩盖并噪声化低强度标签释放的弱信号，故弱信号的数量决定噪声干扰的度量和强信号受解读的概率，即弱信号数量同噪声干扰度成正比关系，同强信号受解读概率成反比关系。

2. 算法程式

DFSA-CCG算法基本同于DFSA-CG算法程序：首先，读写器在信道中分定初始时隙，在可查识区域内通过DFSA对待识标签展开算法识别，完成该帧流程后成功时隙、撞车时隙、闲置时隙出现。再加入出现的俘获效应，不考量该效应的成功时隙量相对少于加入后得到的成功时隙，撞车时隙量相对多于加入后发生的撞车时隙。其次，两个以上标签同选唯一时隙发生碰撞时，读写器根据上帧给予的情况反馈而后通过CGCT监测标签发生碰撞数，进而固定未受成功查识的标签，得以确定其滞留的碰撞信息。

3. 算法示例

通过举例以阐明DFSA-CCG算法传达的查识过程。图2为示例标签（Example Tags,ET）：

图1 ET及编码

设读写器查识区域内标签为图2所列ET，标签编码末位成校检位，则DFSA-CCG算法有如下查识程式：

1. 初始化操作读写器，假定反应时隙序号为查识区域内标签编码前三位，并让始发状态 ，时隙计数位 ，成功时隙计数器 ，撞车时隙计数器 ，闲置时隙计数器 ，再设 为帧长， 为新标签抵达率， 为CGCT算法的标签查识计数器；

2. 读写器展开识别请求，确认0号时隙系闲置时隙：

接续执行下一步；

3. 读写器再展开识别请求，确认1号时隙系成功时隙：

接续执行下一步；

4. 读写器再展开识别请求，确认2号时隙系闲置时隙：

接续执行下一步；

5. 读写器再展开识别请求，对3号时隙进行确认，TagD和TagG本应于此时隙同期递送回应信息并冲突撞车，但俘获效应将TagD捕捉，TagG丢失，于是TagD选择完成时隙且受查询成功：

接续执行下一步；

6. 读写器再展开识别请求，确认4号时隙系成功时隙：

接续执行下一步；

7. 读写器再展开识别请求，确认5号时隙系撞车时隙，给予信息反馈为1010????。栈中压入读写器新生成的查识前缀：10100和10101。基于此，读写器始对10100展开查询，结果为TagB成功回应：

读写器对10101展开查询，TagF和TagH本应于此时隙同期递送回应信息并冲突撞车，但俘获效应将TagF捕捉，TagH丢失，于是TagF选择完成时隙且受查询成功：

这时，前缀栈轮空：

接续执行下一步；

8. 读写器再展开识别请求，确认6号时隙系闲置时隙：

接续执行下一步；

9. 读写器再展开识别请求，确认7号时隙系成功时隙：

10. 基于 和 ，而帧长度的最优解是标签值，读写器同时展开捕获失败标签数量和下帧新标签抵达量的计算和估计，恰当设定下帧帧长度。

4. 标签估计

已知标签量和时隙量相近时，系统查识率最高，即帧长度的最优解是标签值。在一阶段流程中，关键问题是基于时隙录取数评估撞车标签数及新标签抵达量以恰当划分下帧帧长。对此问题有多种标签计量算法，以本文筛选一种较为有益算法，即WTC估算法介绍。

首先设每帧内： 为未受查识标签量， 为成功时隙量， 为撞车时隙量， 为闲置时隙量：

该算法由Went-Tzu Chen提出，其通过Max概率决策法以估算个帧内待识别标签量 ：

其中：

该算法估量误差维持在4%以下，同已筛选算法比较能产生最小误差，计算力强，适用于规模性多标签需求场景。

2. 算法分析

1. 分析DFSA-CCG具备的查识效率

另设查识区域内总标签量为 ， 为读写器设定的帧长度（在硬件局限下， 是 ）。待识标签回应查询命令而选择某时隙之概率有：

有数量r的标签同期选择唯一时隙之概率为：

故，撞车时隙出现之概率 ：

得：

而对于 ，则有：

设俘获效应未加入时的个体撞车时隙中平均标签数系 ，则：

有数量r的标签同期选择唯一时隙使得读写器查识之概率为：

于前述2.1.1节中已确定： ，故读写器未查识之概率有：

设俘获效应加入后读写器查识成功的时隙概率是 ，基于上述部分式确定得：

故，成功时隙量在俘获效应加入后应有的算法期待为：

设俘获效应加入后读写器查识成功的时隙概率是 ：

设俘获效应加入后读写器查识成功的时隙概率是 ：

故，撞车时隙量在俘获效应加入后应有的算法期待为：

再设 为用CGCT算法解决俘获效应未加入时个体撞车时隙所需查识数次，即撞车查识数次：

撞车查识数次 ：

因此，用CGCT算法解决俘获效应未加入时个体撞车时隙所需查识数次 是：

因单个撞车时隙中的标签平均数量较低，故而通过CGCT算法查识，会发生单个标签受查识后出现单个标签近似丢失之情形。基于此，CGCT算法解决个体撞车时隙所查识标签量约是：

CGCT算法在俘获效应下解决单个撞车时隙的查识平均数次 是：

故，CGCT算法解决全体撞车时隙的总查识数次 是：

综上，DFSA-CCG算法的吞吐率 为：

而随标签量的递增，DFSA-CCG算法的 保持稳定。

图2 DC算法的 和 因子间关系

如图2，固定标签量为500时，DC算法的 和 因子的具体关系。对图5分析可知，随 因子递增， 出现降低趋势，但降低幅度并为很大，故俘获效应对DFSA-CCG算法发生的效应较弱。在此认为 因子的上涨及俘获几率的升高使得 降低，也就有俘获撞车时隙量增加， 时，完整的俘获全体撞车时隙，因此： 。若 ，则证明无俘获效应加入，DFSA-CCG算法的 在数值上等同于算法本身的查识率，即： 。

2. 分析DFSA-CCG算法具有的通信复杂度

Query、QueryRep、ACK三指令是RFID系统展开工作时，第一结构标签和第二结构读写器在数据通道里实施通信的三大指令。

设读写器递送Query指令的长度是22位的

，递送QueryRep指令的长度是4位的 ，递送ACK指令的长度是18位的 。Query负责设定单个帧长和解决撞车时隙所发出的识别前缀，QueryRep负责配发新的时隙指令，ACK负责履行查识成功标签的睡眠工作。假定电子标签的身份文件信息位长是96位，将其设为 。

图3 DC算法平均通信复杂性（ ）和标签量关系

分析图3，已知若 ，整个查识过程无俘获效应加入，平均 和DFSA-CG算法的123位概似相等；若 ，整个查识过程受全体俘获，撞车时隙消失，平均 约为120位。可知，查识中的冲突减少所伴随的是 因子的增大，因而相对性降低了算法 ，应注意之，即便降低亦仍保持在单个标签数据传输平均是在120-123位间进行游动。

3. 结论

本文涉及的DC算法通过对因俘获效应而忽视的标签和新标签抵达量的合理性估算，得以恰当设定续帧长度，实现整体查识率的最佳化。经过以上概要分析，DFSA-CCG算法的吞吐率，即 ，平均通信复杂度，即平均 。当俘获效应主导查识过程时，DC算法受该效应作用较小，显然于此方面优于他类算法，使用在真实动态场景中应较为适宜。

参考文献：

[1] Weinstein, R. RFID: a technical overview and its application to the enterprise[J]. It Professional, 2005, 7(3):27-33.

[2] 胡正超. 基于二进制树的RFID防碰撞算法的研究[D]. 吉林大学, 2009.

[3] Gou H, Jeong H C, Yoo Y. A Bit collision detection based Query Tree protocol for anti-collision in RFID system[C]// IEEE 6th International Conference on Wireless and Mobile Computing, Networking and Communications, WiMob 2010, Niagara Falls, Ontario, Canada, 11-13 October, 2010. IEEE, 2012.

[4] Yang C N, Hu L J, Lai J B . Query Tree Algorithm for RFID Tag with Binary-Coded Decimal EPC[J]. IEEE Communications Letters, 2012, 16(10):1616-1619.

[5] Jia X, Feng Q, Yu L, et al. Stability Analysis of an Efficient Anti-Collision Protocol for RFID Tag Identification[J]. IEEE Transactions on Communications, 2012, 60(8): 2285-2294.

[6] Ryu J, Lee H, Seok Y H, et al. A Hybrid Query Tree Protocol for Tag Collision Arbitration in

RFID systems[C]. International conference on communications, 2007, pp.5981-5986.

[7] Jia X, Feng Q, Ma C. An Efficient Anti-Collision Protocol for RFID Tag Identification [J].

IEEE Communications Letters, 2010, 14(11):1014-1016.

8. Solic P, Radic J, Rozic N. Energy Efficient Tag Estimation Method for ALOHA-Based RFID Systems [J].IEEE Sensors Journal,2014, 14(10):3637-3647.

1作者简介：孟凯（1989—），男，山东肥城人，硕士研究生，研究方向为军事装备。

^{孟凯 （1989.10），男，汉族，山东肥城人，学历:研究生，研究方向:无线射频}