基于优先级分组的防碰撞算法

摘 要：针对在标签数量较多、运动较快的场合，常存在识别效率低且标签漏读率高的问题，提出一种先分组再处理的防碰撞算法——PAJS。该算法按照到达顺序对标签进行分组，以减小漏读率；根据标签识别过程中时隙状况自适应调整帧长度，提高算法的搜索效率；采用跳跃式动态搜索算法处理冲突时隙，从而减少搜索次数和系统传输量。Matlab仿真结果表明，该算法通信复杂度明显小于其他常用算法，吞吐率可达0.59～0.6。在待识别标签较多的场合，该算法优越性更加明显。

关键词：射频识别；标签碰撞；优先级分组；自适应动态帧调整；跳跃式动态搜索

中图分类号： TP391.9

文献标志码：A

Anti-collision algorithm based on priority grouping

ZHANG Cong-li，PENG Xuan*，YANG Lei

School of Automation， Chongqing University， Chongqing 400044， China

Abstract：

Concerning the problems of low recognition efficiency and high misreading rate on the occasions of many tags which move fast， an anti-collision algorithm based on packet-first then handling-second was proposed. The algorithm reduced the misreading rate by to grouping the tags according to the order of arriving， it could adaptively adjust frame length based on slot situation to improve the search efficiency， and use jumping dynamic searching algorithm to deal with conflict slots， which could reduce the number of search for readers and the transmission of system. Matlab simulation results show that the algorithm’s communication complexity is lower than other commonly used algorithms， and throughput can achieve 0.59～0.6. The larger the number of tags is the more obvious superiority of the algorithm is.

英文关键词　Key words：

Radio Frequency IDentification （RFID）； tag collision； priority grouping； adaptive dynamic frame adjustment； jumping dynamic searching

0 引言

无线射频识别（Radio Frequency IDentification， RFID）技术中标签通信冲突本质上是多址接入问题，目前常用的两种基于时分多址（Time Division Multiple Access， TDMA）的反碰撞算法有基于ALOHA协议的随机算法和基于二进制树的确定算法。

ALOHA算法[1-4]主要有时隙ALOHA（Slotted ALOHA， SA）算法、帧时隙ALOHA（Frame-Slotted ALOHA， FSA）算法、动态帧时隙ALOHA（Dynamic Frame-Slotted ALOHA， DFSA）算法、自适应动态帧时隙ALOHA（Adaptive Dynamic Frame ALOHA， ADFA）算法等，其中，DFSA算法由于操作简单和性能良好而成为目前最常用的算法之一。树类算法[5-8]大致分为查询树（Query Tree， QT）算法、二进制树搜索（Binary Tree Searching， BTS）算法、动态二进制树搜索（Dynamic Binary Tree Searching， DBTS）算法、回退式索引二进制树搜索（Regressive Index Binary Tree Searching， RIBS）算法等。文献[9]提出的跳跃式动态搜索（Jumping Dynamic Searching， JDS）算法结合了DBTS和RIBS的优点，在减少搜索次数的同时避免了标签ID中多余部分的传输，缩短了数据传输时间。

ALOHA类算法的复杂度和对标签的要求较低，实现简单，但性能不稳定，识别效率不高，可能导致标签饥饿问题。树类算法的识别效率可达100%，但算法相对复杂，需要的存储空间大，识别时间较长，同时，过多的数据交换会导致算法的安全性较差。另一方面，不论是ALOHA类算法还是树类算法，都只有在读写器处理完当前所有被激活标签后，才处理新到达标签，很可能出现后到反而先处理的现象，在标签运动较快的场合，容易造成较高的漏读率。

针对上述问题，本文结合DFSA算法和JDS算法的优点，提出一种基于优先级分组的自适应动态帧时隙跳跃树防碰撞（下文简称PAJS）算法。该算法由两个阶段组成：基于优先级的分组阶段和标签识别阶段。首先，阅读器定时发送分组命令，根据标签的到达顺序对标签进行分组，先到达的标签先处理。然后，阅读器选择一组标签处理，并根据帧时隙算法的思想顺序识别：若当前是空闲时隙，则继续识别下一时隙；若是成功时隙，识别标签；若为碰撞时隙，则利用跳跃式动态树算法识别。在识别过程中，根据空闲时隙、成功时隙、碰撞时隙数的关系和估计的标签数量动态调整帧长度直到整组标签全部处理，继续下一组标签的识别。