收稿日期：２０１４-１２-２２；修回日期：２０１５-０２-０２ 基金项目：中国博士后科学基金资助项目（２０１２Ｍ５１２０７９）
作者简介：丁治国（１９７７-），男，安徽合肥人，工程师，博士（后），主要研究方向为射频识别技术与计算机网络（ｄｉｎｇｚｇ＠ａｈ．ｅｄｕ．ｃｎ）；雷迎科（１９７５-），男，博士，主要研究方向为机器学习与信号处理．
基于优先级避让的防碰撞算法研究*
丁治国，雷迎科
（解放军电子工程学院信息管理中心，合肥２３００３７）
摘 要：针对非确定性防碰撞算法可能出现的标签饥渴问题，提出了一种基于优先级避让的防碰撞算法。该算法将每一轮的标签识别过程分为标签预约和标签读取两个阶段，并根据标签在读写器作用范围内的驻留时间分配优先级。当预约时隙中出现碰撞时，读写器利用碰撞因子估计标签数量，当判断两个优先级不同的标签同时选择一个时隙时，优先级低的标签将在读取过程中主动避让，从而使对应的读取时隙避免碰撞。理论分析和仿真实验表明，该算法不仅可以有效减少碰撞时隙，提高系统的吞吐率，而且可以较好地解决标签饥渴问题，降低标签的漏检率，特别适用于标签数量大且对漏检率有严格要求的ＲＦＩＤ系统。关键词：射频识别；优先级；避让；标签饥渴；防碰撞算法
中图分类号：ＴＰ３９１．４４ 文献标志码：Ａ 文章编号：１００１-３６９５（２０１６）０３-０８３６-０４ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１-３６９５．２０１６．０３．０４４
Ｒｅｓｅａｒｃｈｏｎａｎｔｉ-ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｐｒｉｏｒｉｔｙａｖｅｒｓｉｏｎ
ＤｉｎｇＺｈｉｇｕｏ，ＬｅｉＹｉｎｇｋｅ
（ＣｅｎｔｅｒｏｆＩｎｆｏｒｍａｔｉｏｎＭａｎａｇｅｍｅｎｔ，ＥｌｅｃｔｒｏｎｉｃＩｎｓｔｉｔｕｔｅｏｆＰＬＡ，Ｈｅｆｅｉ２３００３７，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎｏｒｄｅｒｔｏａｌｌｅｖｉａｔｅｔｈｅｐｒｏｂｌｅｍｏｆｔａｇｓｔａｒｖａｔｉｏｎｉｎｔｈｅａｌｏｈａ-ｂａｓｅｄａｌｇｏｒｉｔｈｍｓ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｎｅｗａｎｔｉ-ｃｏｌ-ｌｉｓｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｐｒｉｏｒｉｔｙａｖｅｒｓｉｏｎ．Ｔｈｅａｌｇｏｒｉｔｈｍｄｉｖｉｄｅｄｅａｃｈｉｄｅｎｔｉｆｉｃａｔｉｏｎｒｏｕｎｄｉｎｔｏｔｗｏｓｔｅｐｓｉｎｃｌｕｄｉｎｇｏｆｒｅｓｅｒｖａ-ｔｉｏｎｓｔａｇｅａｎｄｉｄｅｎｔｉｆｉｃａｔｉｏｎｓｔａｇｅ．Ｉｔａｓｓｉｇｎｅｄｄｉｆｆｅｒｅｎｔｔａｇｓｔｏｄｉｆｆｅｒｅｎｔｐｒｉｏｒｉｔｉｅｓａｃｃｏｒｄｉｎｇｔｏｔｈｅｉｒｈｕｎｇｅｒ．Ｉｎｔｈｅｒｅｓｅｒｖａｔｉｏｎ
ｓｔａｇｅ，
ａｒｅａｄｅｒｅｓｔｉｍａｔｅｄｔｈｅｎｕｍｂｅｒｏｆｔａｇｓｉｎｃｏｌｌｉｓｉｏｎｓｌｏｔｓｂｙｃｏｍｐｕｔｉｎｇｔｈｅｃｏｌｌｉｓｉｏｎｆａｃｔｏｒ．Ｗｈｅｎｔｈｅｒｅａｄｅｒｆｏｕｎｄｔｗｏｄｉｆ-ｆｅｒｅｎｔｐｒｉｏｒｉｔｙｔａｇｓｃｈｏｓｅｔｈｅｓａｍｅｓｌｏｔ，
ｉｔｗｏｕｌｄｉｎｆｏｒｍｔｈｅｌｏｗｐｒｉｏｒｉｔｙｔａｇｔｏｅｖａｄｅｉｎｉｄｅｎｔｉｆｉｃａｔｉｏｎｓｔａｇｅ．Ｔｈｅｏｒｙａｎｄｃｏｍｐｕｔ-ｅｒｓｉｍｕｌａｔｉｏｎｓｓｈｏｗｔｈａｔｔｈｅｎｅｗａｎｔｉ-ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍｃａｎｉｍｐｒｏｖｅｔｈｅｔｈｒｏｕｇｈｐｕｔａｎｄｒｅｄｕｃｅｔｈｅｍｉｓｓｉｎｇｒａｔｅ．Ｉｔｉｓａｐｐｌｉｅｄ
ｔｏＲＦＩＤｓｙｓｔｅｍｗｈｅｒｅｔａｇｓａｒｅｈｉｇｈ-ｓｐｅｅｄａｎｄｔｈｅｎｕｍｂｅｒｏｆｔａｇｓｉｓｌａｒｇｅ．
Ｋｅｙｗｏｒｄｓ：ｒａｄｉｏｆｒｅｑｕｅｎｃｙｉｄｅｎｔｉｆｉｃａｔｉｏｎ（ＲＦＩＤ）；ｐｒｉｏｒｉｔｙ；ａｖｅｒｓｉｏｎ；ｔａｇｓｔａｒｖａｔｉｏｎ；ａｎｔｉ-ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍ
射频识别作为新型无线非接触式自动识别技术已在物流、销售、交通和定位领域得到广泛应用。其中，用以解决读写器作用范围内多标签与读写器通信问题的防碰撞算法已成为该领域广泛研究的热点问题之一。
受标签技术和成本的约束，现有的防碰撞算法主要包括两
类，即基于树型的搜索算法［１～４］
和基于时隙随机选择的ＡＬＯ-ＨＡ算法［５～１５］。前者按照二进制树或多进制树结构，通过不断
修改查询前缀，直至对唯一标签进行识别。由于该类算法可以遍历整个搜索空间，不存在标签漏检，被称为确定性方法。其中，文献［４］通过计算碰撞因子估计碰撞时隙内标签数量，从而自适应调整搜索叉树，可将算法吞吐率提高到６５％左右（传统二进制搜索算法吞吐率为５０％左右）。第二类算法简单，易于实现，但存在一定概率的某一标签长时间内所选择的时隙均发生碰撞，存在漏检风险，即标签饥渴问题，因此被称为可能性方法。在可能性方法的研究中，传统的时隙、帧时隙和动态帧时隙ＡＬＯＨＡ算法等存在性能瓶颈，即便在标签数量估计准确的情况下（文献［７］总结了多种标签估计方法），即分配的时隙数与待识别标签数量相等时，ＲＦＩＤ系统的吞吐率也无法突破４０％。为此部分学者提出了不等长时隙和按需时隙分配的方
法［６，８］，通过标签预约机制减少空闲和碰撞时隙的时长，可较
大幅度地提高算法的识别效率，但该类方法没有考虑标签饥渴问题，仍然存在标签漏检风险。文献［１５］提出的优先级分组算法根据待识别标签在读写器有效区域内的驻留时间分配优先级，相同优先级的标签分为一组，级别高的分组优先识别，但在分组内仍然采用跳跃式动态搜索算法（一种确定性的二进树搜索算法），因此性能一般且实现成本较高。
本文则在标签预约机制的基础上，根据标签的饥渴度分配优先级，当两个不同优先级的标签在预约过程中发生碰撞时，优先级低的标签会在读取过程中主动避让，从而使优先级高的标签成功识别。
1 基于优先级避让的防碰撞算法
1．1 标签预约机制
为了减少标签在随机选择时隙过程中的盲目性，从而减少空闲和碰撞时隙数，文献［６］提出了一种标签预约机制，即将一组标签的循环识别过程分为标签预约和标签读取两个阶段。在时隙预约阶段，读写器作用范围内的所有标签随机选择预约时隙并发送短随机序列（长度远小于标签的序列号）用于检测预约冲突，对于预约过程中出现的空闲和碰撞时隙，读写器在标签读取阶段将不再分配对应的时隙以减少空闲和碰撞的发
第３３卷第３期２０１６年３月 计算机应用研究
ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＶｏｌ．３３Ｎｏ．３
Ｍａｒ．２０１６