本文是一篇计算机论文，针对半有源RFID的防碰撞问题，本文提出了基于已知标签的最大上限时的动态帧调整算法，该算法的主要目标是降低系统中标签设备的功耗，通过对比实验结果可以得出，和现有的防碰撞算法相比，标签设备以小于5%平均读取损失率，降低了标签设备20%左右的平均功耗。
第一章 绪论
1.1 研究背景及意义
随着物联网的发展，RFID设备被广泛应用，例如供应链的货物追踪、图书馆的书本管理等。RFID设备的种类大致可以分为三类：有源RFID、无源RFID和半有源RFID[1]。有源RFID的标签设备中有固定的电源，使其具有远距离通信的特点。无源RFID的标签设备中不含有固定电源，需要通过接收阅读器信号以产生短暂的感应电流用以完成标签和阅读器之间的信息交互，因此无源RFID的通信距离很短，一般不超过8米，在很多的场景下使用受限。半有源RFID采用一种低频唤醒高频通信的工作机制[2]，标签只有在工作状态时才能与阅读器进行信息交互，大部分时间标签设备都处于功耗极低的休眠状态。
2011 年，德国政府在《德国 2020 高技术战略》报告中提出了工业 4.0 的概念，其旨在通过信息通讯技术和信息物理系统相结合的方式，来实现制造业的智能化转型，从而提供更加优质化的服务。2015 年，政府对接工业 4.0 提出了《中国制造 2025》报告，其中也提出了要大力发展智能制造工程，实现制造业重点领域全部智能化[3]。在智能制造的过程中通过传感网和无处不在的 RFID标签实现人与物、物与物间的互联是其必不可少的一环，这些都不可避免的要使用到 RFID技术。因此 RFID技术的相关应用研究对于帮助传统制造业企业的升级具有一定的意义。
半有源RFID通常是电池驱动的支持双频或双频以上通信的电子标签。其中，高频通信模块的能量消耗占据了标签大部分的能量消耗。为了节省标签的能耗，延长标签的使用时间，标签在不工作时，通常关闭高频通信模块，只保留功耗极低的低频通信模块进入信号监听模式，进入所谓的“休眠”状态。当低频通信模块收到激活信号时，标签唤醒高频通信模块，用高频通信完成与阅读器之间的数据交换，然后再次进入休眠状态。针对半有源RFID标签的以上特点，在应用半有源RFID标签的一些典型应用中，如资产盘点应用场景和浙江天目山自然保护区数据采集应用场景，我们通常需要满足或者优化以下两个目标：1）如何让阅读器更快更好的完成标签数据的采集工作；2）如何尽量延长电池供电标签的使用寿命，以便与阅读器完成数据交换。
1.2 国内外研究现状
本节首先介绍移动阅读器数据收集的研究现状，主要包括聚合数据收集和非聚合数据收集，以及移动阅读器的路径规划问题，然后介绍RFID防碰撞算法的研究现状，主要包括概率性的防碰撞的算法和确定性的防碰撞算法以及它们各自存在的问题和优势。
1.2.1 移动阅读器（基站）数据收集的研究现状
最近有大量文献研究如何使用移动阅读器在无线传感器网络（Wireless Sensor Networks, WSN）中收集数据包。根据每个数据包在网络中的传输方式的不同，数据收集问题可以进一步分为两类：有数据聚合方式和无数据聚合方式[4]。数据聚合是指在网络中聚合各个节点的数据来减少网络传输的比特量，从而提高能源效率。在文献[5]中的作者提出了TAG（Tiny Aggregation, TAG）算法，它使用一种类似 SQL语句的声明性语言来表达 WSN中的聚合查询。在文献[6]中，作者研究了构建数据收集树以最大化网络寿命的问题，这已经被证明是 NP完全问题。
在非聚合数据收集方面也有不少相关的研究。在文献[7]中作者将所有的传感器节点都抽象为具有固定位置的静态节点，然后使用具有公平速率控制的树结构来进行数据收集，通过这种方式可以在无线传感器网络中支持大量数据的访问。在文献[8]中的研究表明，如果在具有移动用户的网络中，使用现有静态设置的数据收集方案，性能将会变的很差。
针对无线传感器网络中使用移动阅读器进行数据收集的问题，现在人们做的大部分工作都在研究如何规划一个合理收集路径，以达到数据的高效采集的目的。J. Lee等人在文献[9]中提出了通过数据流量来预测移动阅读器的下一个移动位置，从而提高算法的执行效率。Xing等人在文献[10]中提出了两种依赖于网络路由树的移动阅读器的路径规划策略。
第二章 相关技术与算法介绍
2.1 有源、无源、半有源RFID系统组成和工作原理
RFID 系统核心组成件有阅读器、电子标签、数据处理中心和中间件组成[30]，这也是RFID系统最基本的组成部分。
2.1.1 RFID系统组成
RFID技术从诞生到现在已经八十多年的发展历史了，RFID技术是由二十世纪四十年代的雷达技术衍生而来，RFID系统的大致组成部分为标签和阅读器，标签设备一般用来存储特定信息用于身份认证或者帮助其他传感器设备进行数据传输 。阅读器是功能较强的射频电路，用于对标签数据进行收集，阅读器对标签信息进行采集之后，需要通过其他的电路或者是通信方式将数据信息发送到后台系统。随着RFID技术的发展，针对不同的应用场景，RFID技术在不同的方面进行了取舍，现在市场上的RFID的产品大致可以分为三类：第一类是有源RFID，第二类是无源RFID，第三类是半有源RFID[31]。
（1）有源RFID
有源RFID，也称为主动式的RFID设备，在标签和阅读器之间进行信息交互时，是由标签主动发起交互请求，有源RFID的标签设备中内含电源，因此有源RFID的优势之一就是支持标签与阅读器之间可进行中远距离通信（与无源RFID的通信距离相比）。但是对于标签设备而言，标签设备的能源消耗比较大，可能需要经常更换标签设备中的电源。有源RFID按照工作频段进行划分，大致有三个工作频率，分别为433MHZ、2.4G和5.8G。对于射频信号的传输来说，频率越高，相应的波长就会越短，信号直射能力就会越强，绕射能力就会越差，也就是平常说的“穿透能力”越弱，因此RFID在不同的应用场景会选择不同的一个工作频段。有源RFID有两种工作机制，分别是单工和半双工，有源RFID的通信距离可以达到百米以上，通常被应用于资产的盘点等场景。
2.1.2 RFID的标准体系
RFID 标准体系为了推动RFID 产业规范化而推出的一系列协议标准。RFID 标准体系主要包括 RFID 应用标准、RFID 技术标准、RFID数据标准、RFID性能标准四个方面，这些 RFID标准体系中，比较成熟的主要是 EPC global制定的 RFID标准化体系， ISO （国际标准化组织）制定的 RFID标准化体系以及日本 UID中心制定的标准化体系[32]，下面将分别对这三种体系进行简要的介绍。
2.2 RFID的防碰撞技术
RFID是一种通过射频技术来实现终端之间进行信息交互的一种通信方式，由于在多数情况下阅读器在进行高并发读取时，不同标签的数据包会发生激烈的碰撞，导致信息交互的失败。为了解决此类问题，提高信息交互的效率，RFID的防碰撞技术是采用了时分复用和空分复用的方式、以及预处理等方式来降低撞包的概率。RFID系统中，当阅读器对其能够识别区域内的标签进行信息读取时，产生的碰撞主要分为阅读器碰撞和标签碰撞[37-38]。
2.2.1 RFID碰撞类型
（1）标签-标签碰撞（Tags Collision）。阅读器信息区内有许多标签等待着阅读器的Query指令，标签接到指令后又同时对指令进行应答，由于信号区之间的相互影响，导致阅读器不能认识到某个有用的标签。
（2）标签-阅读器碰撞（Tag-Reader Collision）。在多台RFID阅读器一起运行的操作系统中，位于不同功能区域内的标签同时收到多台阅读器指令时，标签之间不能抉择，导致信息读取失败。
（3）阅读器-阅读器碰撞（Reader-Reader Collision）。多个阅读器同时存在一个静态系统中，由于任何一个阅读器在识别流程中产生的射频标识信息影响了其他阅读器的正常工作流程，从而导致该阅读器无法顺利完成标签识别任务。
在现实的RFID标签识别系统中，发现最大的技术问题就在于标签和标签的碰撞。所以，本章重点对标签的碰撞现象进行了研究，如图2.2所示为最典型的标签碰撞现象，阅读器的信号区内有多个标签同时响应阅读器的数据收集指令。
第三章 基于半有源RFID的移动阅读器最短路径算法研究 ................ 22
3.1 问题的描述 ............................. 22
3.1.1 模型的构建 ............................... 22
3.1.2 Group Steiner Tree问题 ............... 25
第四章 基于半有源RFID的低功耗防冲突算法研究 ................................... 41
4.1 问题的描述 ........................................ 41
4.2 半有源RFID防碰撞算法的设计与分析 ................................ 41
第五章 结论及展望 .................................. 55
第四章 基于半有源RFID的低功耗防冲突算法研究
4.1 问题的描述
半有源RFID采用的低频唤醒高频通信的工作机制，标签在收到阅读器的激活信号之后，所有标签将会被唤醒和阅读器进行数据交互，因此将会产生大量数据包碰撞问题。
对于现有的基于ALOHA的防碰撞算法避免标签碰撞问题的主要思想有两种：一：让标签随机选择一个固定时间长度的时间槽给阅读器发送数据信息；二：通过不同的标签预测方法对未读取的标签数量进行预测，根据预测结果调整合适的帧长供标签随机选择帧中的一个时间槽和阅读器进行数据交互。
上述提到了SA算法和FSA算法就是基于第一种思想进行算法设计的，通过固定的时间槽的长度和在每一帧中标签只选择一个时间槽和阅读器进行数据交互，从而避免了部分碰撞的问题。DFSA算法则是基于第二种思想设计的，DFSA算法通过一系列的预测算法来预测区域内未被读取的标签个数，调整广播的数据帧长度，从而减少碰撞的概率，降低系统的功耗。
本章节从而实际应用的工程角度出发，在实际应用当中，区域内的标签数量的最大上限值通常是一个固定值，区域内的标签个数n在不段的发生变化，为了降低系统的功耗且提高系统的识别率，算法的初始帧长和帧长的调整策略至关重要。
第五章 结论及展望
RFID技术在日常生活中的应用随处可见，但是随着物联网的高速发展，为了降低工程的成本，有源RFID的高功耗已经不能够满足日常应用的需求，而具有低功耗特性半有源RFID技术的应用场景变的更加的广泛。半有源RFID采用低频唤醒高频通信的工作机制，可以极大的降低系统的功耗，节约项目的成本。但是半有源RFID在工程部署的路径规划问题和半有源RFID的防碰撞问题一直都没有一个很好的解决方案来做技术支持，为了解决这两个问题，在本文第三、四章分别对这两个问题进行了详细研究，并提出了自己的可行性方案。
针对于静态标签节点的数据收集问题，本文基于Group Steiner Tree理论提出了基于单个移动阅读器的最短有效路径收集算法。首先基于静态节点之间的可访问性进行分组，然后根据分组结果基于Group Steiner Tree理论构建出一棵Steiner Tree，接下来通过深度优先搜索算法遍历该树生成一个哈密顿环，最后得出移动阅读器的最短有效收集路径。我们从一般情况下和特殊情况下对求出的最短收集路径和理论最短收集路径的结果进行了对比，通过理论证明ABRS算法求出的最短有效收集路径结果和理论最短收集路径的结果的近似比为O（ log2nlogtloglogn），n代表区域内的静态节点数，t(t≤n)为最大网络基础。
针对半有源RFID的防碰撞问题，本文提出了基于已知标签的最大上限时的动态帧调整算法，该算法的主要目标是降低系统中标签设备的功耗，通过对比实验结果可以得出，和现有的防碰撞算法相比，标签设备以小于5%平均读取损失率，降低了标签设备20%左右的平均功耗。此外，我们还自主研发了可实用的半有源RFID的标签设备和阅读器设备。
参考文献（略）