RFID系统时隙不完全竞争防碰撞算法

RFID系统时隙不完全竞争防碰撞算法 杨 坤，冷甦鹏 (电子科技大学通信与信息工程学院，成都 611731) 摘 要：基于ISO/IEC 18000-6C超高频射频识别标准，提出一种时隙不完全竞争防碰撞算法。将动态二叉树搜索技术引入竞争性冲突避免机制，并加入对空闲时隙和碰撞时隙的特殊处理策略。通过NS-2平台建立仿真模型，分析对比动态二叉树搜索算法、ISO/IEC 18000-6C标准算法和SPC算法的性能。仿真结果表明，SPC算法识别时间分别比动态二叉树搜索算法和18000-6C标准算法缩短约30%和20%，识别率比18000-6C算法提高约35%。 关键词：时隙Aloha；二叉树搜索；射频识别；不完全竞争 Slot Partial Competitive Anti-collision Algorithm for RFID System YANG Kun, LENG Su-peng (School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China) 【Abstract】Based on the ISO/IEC 18000-6C UHF Radio Frequency Identification(RFID) standard, this paper proposes a Slot-based Partial Competitive(SPC) anti-collision algorithm, which introduces dynamic binary tree search technology into the competitive collision avoidance mechanism for the first time. Moreover, the SPC algorithm applies the specific technologies to idle slots and collision slots. The performances of the dynamic binary tree search, ISO/IEC 18000-6C and the SPC algorithm are compared via NS-2 simulation experiments. Simulation results indicate that the SPC algorithm is able to not only reduce the recognition time by 30% and 20% compared with the binary tree search algorithm and the 18000-6C algorithm, respectively, but also improve the recognition rate by 35% compared with 18000-6C algorithm. 【Key words】slot Aloha; binary tree search; Radio Frequency Identification(RFID); partial competitive DOI: 10.3969/j.issn.1000-3428.2011.01.090 计 算 机 工 程 Computer Engineering 第37卷 第1期 Vol.37 No.1 2011年1月January 2011·开发研究与设计技术· 文章编号：1000—3428(2011)01—0260—03文献标识码：A 中图分类号：TP301.6

1 概述 射频识别(Radio Frequency Identification, RFID)技术是物联网核心技术，利用射频方式进行非接触双向通信，达到识别标签的目的。典型的RFID系统主要包括标签和读写器 2个部分。标签用于区分对象身份，自身携带了ID及其他信息；读写器通过射频信号与标签通信。标签将自身ID号发送给读写器，实现身份和信息识别。然而，当阅读器作用范围内存在多个标签，同一时刻可能有多个标签向阅读器返回信息，在无线信道上产生标签冲突。因此，需要采用防碰撞算法尽量避免冲突发生，最大限度地正确识别更多的标签。 2 RFID防碰撞算法研究现状 RFID系统防碰撞算法通常分为二叉树搜索算法和Aloha法。二叉树搜索算法使用了曼彻斯特编码，在多标签响应时按位识别出碰撞，根据碰撞的位置，按一定法则重新搜索射频标签。传统的二进制算法需要传输的数据量大，传输时间长，影响了RFID系统的效率。文献[1]提出的动态二叉树搜索算法把传输的数据分成2个部分，收发双方各自传送其中一部分数据，可把传输的数据减小到一半，达到缩短传输时间的目的。 Aloha法又分为时隙Aloha、帧时隙Aloha、时隙随机Aloha等。帧时隙Aloha算法在时隙Aloha算法的基础上，把N个时隙组成一帧，标签在每个帧中随机选择一个时隙发送数据[2]以减少标签冲突概率。而时隙随机Aloha可以在一个识别周期内随时更改时隙数，让未识别的标签重新选择时隙，实现自适应调整[3]。 时隙随机Aloha算法被ISO/IEC 18000-6C标准[4]采用，该标准已经成为全球性超高频RFID主流规范之一。Intel公司提供的 R1000超高频读写器芯片使用了该标准。18000-6C协议流程如图1所示。 图1 18000-6C协议流程 读写器发送query命令，命令中含有槽计时器参数Q。标签在0~21Q−个时隙内随机选择一个数作为时槽数，标签的时槽数为0时响应读写器，随机产生16位随机数RN16发送给读写器。读写器收到RN16后，如果发现没有碰撞则发送ACK确认接收正确，标签收到ACK命令后回送自己的EPC数据给读写器。读写器检测EPC数据是否有效，如果无基金项目：国家自然科学基金资助项目(60802024)；国家“863”计划基金资助重点项目(2009AA011801)；国家科技重大专项基金资助项目(2008ZX03006-001)；教育部博士点基金资助项目(200806141014)；通信抗干扰国家级重点实验室基金资助项目(9140C0203010904) 作者简介：杨 坤(1984-)，男，硕士研究生，主研方向：RFID防碰撞算法；冷甦鹏，教授、博士 收稿日期：2010-02-26 E-mail：spleng@uestc.edu.cn 第37卷 第1期 杨 坤，冷甦鹏：RFID系统时隙不完全竞争防碰撞算法 261 效发送NAK，则标签收到NAK后，重新转换为就绪状态参与下一次循环。如果EPC有效，则读写器发送query_rep命令开始下一个时隙的识别。由18000-6C防碰撞算法流程分析可得，当NAK丢失或出现误码的情况下，读写器发送完NAK命令一段时间后会继续发送下一个询问命令，没有正确收到NAK的标签若又收到读写器的下一个询问命令，会误认为自己已经被正确识别。进而转为休眠状态，不再参与下一次循环，这个标签就会被漏读。另外，在18000-6C标准定义的标签读取流程中存在大量空闲时隙和碰撞时隙，这些时隙内不能正确识别标签，浪费了大量读取时间。 3 SPC算法描述 本文基于18000-6C存在的缺陷，设计了一种新型时隙不完全竞争防碰撞(Slot-based Partial Competitive, SPC)算法。其基本思路为：如果出现空闲时隙，SPC算法会发送命令跳过此时隙。如果某个时隙多个标签同时响应读写器发生碰撞，则进一步采用二叉树搜索算法进行识别。该算法吸收了二叉树算法识别率高的特点，标签漏读个数明显低于18000-6C标准算法。 3.1 命令约定 命令约定具体如下： (1)检测命令——detect(Q)。阅读器发送该命令给区域内标签，收到命令后，标签随机产生2Qbit的数据，从0~21Q−中选择其中一个时隙。例如区域内有3个标签，并且Q=7，标签就产生128 bit的数据，用于识别标签选择占用的时隙号。标签选择第k个时隙，就将第k个比特位置1，其余位全部置0。然后，3个标签将产生的128 bit数据同时传送给读写器。读写器收到标签数据后可以获知时隙的占用情况，如下所示： Tag1 0 0 1 0 0 … 0 0 0 Tag2 0 0 0 1 0 … 0 0 0 Tag3 0 0 0 1 0 … 0 0 0 检测结果 0 0 x x 0 … 0 0 0 检测结果为0的时隙没有标签选择，该时隙是空闲时隙；检测结果为乱码(x)表示该时隙至少被一个标签选择。 (2)搜索命令——request(baseuid)。此命令发送一个序列号baseuid给标签。如果标签ID号小于或等于baseuid，将自己的ID号回送给读写器。 3.2 算法描述 SPC算法主要由2个阶段构成。第1阶段采用Aloha机制识别标签，只出现空闲时隙和成功时隙；第2阶段仅发生在标签碰撞时，将执行二叉树搜索算法识别碰撞时隙内的 标签。 (1)发送detect命令 当某个比特位上所有标签的值都为0时，则读写器可以确定该位为0，该时隙为空闲时隙，读写器记录下所有的空闲时隙(S1,S2,…,Sn)。检测结果为乱码的比特位对应的时隙可能被一个标签选择，或者被多个标签选择，2种情况是无法区分的。读写器存储一个计数器count，表示目前所处的时隙数(0≤count<21Q−)，count的初始值为0。 (2)发送query或query_rep命令 首先判断count值是否属于空闲时隙序列(S1,S2,…,Sn)。如果是说明此时隙是空闲时隙。读写器发送query_rep命令；count增加1。否则，说明此时隙至少有一个标签选择。读写器发送query命令，count增加1。如果此时隙只有一个标签选择，则按照时隙随机算法机制识别标签。 (3)碰撞时隙中使用二叉树搜索算法 如果某时隙有多个标签选择，此时会有多个标签向读写器发送RN16随机数。这时读写器通过检测判定产生了标签碰撞，则启动第2阶段的二叉树搜索机制。 图2给出了第2阶段的流程示意图。当某个时隙出现碰撞时，会发送request命令开始二叉树搜索算法识别标签。 发送request命令RN16小于baseuid的标签发送RN16发送select命令是否有碰撞RN16标签发送自己的EPC数据EPCEPC是否有误收到unselect的标签，进入休眠继续发送request命令，识别碰撞时隙的其余标签是否select否检测是否有信号是否该时隙所有标签都被识别，退出循环requestunselect开始下一个时隙的识别…检测到碰撞

…发送select命令是 图2 碰撞时隙内识别标签示意图 例如有3个标签同时选择了该时隙，从检测结果可以看出，第14位、第12位、第10位有碰撞，如下所示： Tag1 1 0 1 0 0 0 … Tag2 1 1 1 1 0 0 … Tag3 1 1 1 0 0 1 … 检测结果 1 x 1 x 0 x … 读写器发送request命令。先将第14位置0，即baseuid= 1011111111111111。该时隙内的标签收到命令后对比自己的RN16，如果小于baseuid则回复自己的RN16给读写器，只有Tag1回应读写器。读写器检测不到碰撞，向此标签发送select命令。Tag1收到命令后，发送自己的数据给读写器。读写器收到标签数据后，向Tag1发送unselect命令，Tag1收到命令后，转为休眠状态。用同样的方式，将第14位、 第12位依次置0可以识别Tag2和Tag3。当该时隙内所有标签识别完时，读写器发送query_rep命令，开始下一个时隙的识别。 由此可见，SPC算法与18000-6C算法最重要的区别在于18000-6C算法在某个时隙内有多个标签发生碰撞时无法处理其中任何一个标签，而SPC算法在该时隙内使用二叉树搜索算法读取标签，直到把该时隙的所有标签一一识别。这样就充分利用了碰撞时隙，节省了识别时间。 4 仿真分析 本文搭建NS-2仿真平台对SPC算法进行性能评估，仿