基于Alonha的RFID防碰撞算法仿真与实现毕业论文.doc

北京科技大学本科生毕业设计（论文）基于Alonha的RFID防碰撞算法仿真与实现毕业论文目录摘要1Abstract2目录1插图清单1附表清单3引言41.绪论51.1RFID技术的广泛普及51.2 开展研究的意义62. RFID系统组成及主要工作原理82.1 RFID系统组成82.2 RFID系统工作原理102.3 RFID系统的特点和应用112.4 RFID系统现存问题和发展前景133. Aloha访问控制协议与RFID防碰撞算法设计153.1 基本多址接入方法153.2 基本Aloha算法及其在RFID系统中的应用173.2.1纯Aloha算法173.2.2时隙Aloha算法203.2.3帧时隙Aloha算法233.2.4改进的动态帧时隙Aloha算法及帧长选择244. 基于固定帧时隙Aloha的RFID防碰撞算法实现与性能仿真274.1 固定帧时隙Aloha算法流程274.2 基于OPNET的RFID模型搭建294.2.1 网络模型搭建294.2.2节点模型搭建314.2.3 进程模型搭建374.3. 仿真结果展示395.改进的动态帧时隙Aloha算法及其性能仿真495.1动态帧时隙Aloha算法流程495.3动态帧时隙Aloha建模与仿真506. 结论54参考文献55附录A 英文资料原文58附录B 中文资料译文68在 学 取 得 成 果77致谢78- 1 -北京科技大学本科生毕业设计（论文）插图清单图1.1 RFID 系统标签碰撞图2图2.1 RFID系统构成8图2.2 电子标签内部结构图9图2.3 无源标签耦合示意图10图3.1 频分多址15图3.2 空分多址16图3.3 纯Aloha算法示意图18图3.4 纯Aloha冲突区示意图18图3.5 Aloha算法输入负载与吞吐量比较19图3.6 RFID系统pure Aloha算法示意图20图3.7 时隙Aloha 算法示意图21图3.8 时隙Aloha与纯Aloha性能比较22图3.9 RFID系统时隙Aloha算法示意图22图3.10 RFID系统帧时隙Aloha算法示意图23图4.1 基于FSA的RFID系统工作流程图29图4.2 OPNET工程主界面30图4.3 RFID系统网络层拓扑结构图31图4.4 标签节点模型32图4.5 自定义封包格式32图4.6 电子标签收发信机属性设置34图4.7 阅读器收发信机属性设置35图4.8 阅读器进程模型37图4.9 标签进程模型38图4.10 进程模型内部结构38图4.11 仿真属性设置39图4.12 仿真结果数据包的产生、复制、销毁统计40图4.13 系统识别率与帧长关系图41图4.14 快速配置窗口41图4.15 系统识别率与帧长关系图42图4.16 FSA识别率与帧长关系曲线43图4.17 碰撞时隙比率与帧长关系图45图4.18 空闲时隙比率与帧长关系图46图4.19 FSA中碰撞时隙比率随帧长变化曲线图48图4.20 FSA中空闲时隙比率随帧长变化曲线图48图5.1 DFSA 系统识别率与负载关系曲线51图5.2 DFSA系统碰撞概率与负载关系曲线51图5.3 DFSA系统空闲率与负载关系曲线52图5.4 基于Aloha的RFID系统性能比较53附表清单表格 1 RFID系统与其他识别系统比较9表格 2 RFID系统分类10表格 3 帧长和标签数改变对应系统识别率统计表39表格 4 帧长和标签数改变对应碰撞时隙比率统计表43表格 5 帧长和标签数改变对应空闲时隙比率统计表43引言RFID射频识别技术可以通过射频信号自动识别目标对象获取相关数据，在对象识别、资产管理、库存控制等领域应用广泛，是现代工业进步的象征。它不需要视距传输、易于重复编程、能快速读取和存储数据，已被广泛应用于工业自动化、物流管理、交通运输等社会生活的各个领域。 尽管RFID技术具有良好的应用前景，其发展也受到了一些因素的制约。其中最关键的就是信息传输过程中的多标签碰撞问题。射频识别系统工作过程中，由于阅读器和标签共享无线信道，所以会出现干扰，这种干扰称为碰撞。碰撞分为阅读器碰撞和标签碰撞两种：阅读器碰撞是指两个临近的阅读器同时对一个标签进行识别，造成标签不能对任意一个阅读器进行回复，这种碰撞可以依靠阅读器之间的通信来解决；标签碰撞是指阅读器作用范围内的两个或多个标签同时向阅读器传输信息造成的干扰。由于标签自身功能少、没有能源、只能通过阅读器的电磁场获得能量，更不能检测碰撞，因此多标签碰撞对RFID系统的性能影响更大。目前防止多标签碰撞的算法主要是Aloha算法和二进制搜索算法。其中二进制搜索算法识别率高，但是标签数量大时识别速度慢。Aloha算法识别速度快，识别算法简单，正是我们要研究的算法。本文将首先研究RFID系统的组成和工作原理。接着根据RFID系统的工作原理和实际应用中的特点，对RFID系统现有的防碰撞算法如Aloha, 时隙Aloha，帧时隙Aloha进行整理和比较，通过时序图和公式推导，找出各算法的优缺点。运用OPNET 网络仿真软件，搭建RFID系统模型，并嵌入帧时隙Aloha，运行仿真，统计系统正确接收时隙概率作为系统识别率，比较在不同的帧长条件下系统识别率的变化情况；比较系统的碰撞时隙比率和空闲时隙比率变化情况。 接着介绍一种改进的防碰撞算法：动态帧时隙Aloha算法。对两种不同的基于Aloha的访问控制协议进行比较，利用仿真模型，统计系统识别率，展现动态帧时隙Aloha在标签数量较多的RFID系统中的性能优势。 1. 绪论1.1 RFID技术的广泛普及 无线射频识别即RFID(radio frequency identification)技术也被称为电子标签技术，是20世纪90年代开始兴起的一种自动识别技术。它通过无线射频信号实现非接触方式下的双向通信，完成对目标对象的自动识别和数据的读写操作。RFID技术具有无接触、精度高、抗干扰、速度快以及适应环境能力强等显著优点，正逐步被广泛应用于工业自动化，商品管理，交通运输控制管理等众多领域，各国政府，IT厂商，零售业巨头1，都给予高度关注。被公认为二十一世纪十大重要技术之一2。这些全面推动了RFID产业的迅猛发展。随着全球产品电子代码中心推出第二代超高频（UHF）RFID电子标签标准（EPCG2）,各大供应商的EPCG2芯片也纷纷亮相。许多高科技公司，比如Intel, Microsoft, Oracle, SUN 等，正在开发支持RFID射频识别电子标签的软硬件平台。国际邮联也正积极推进高效低成本的RFID技术解决方案在国际邮政中的使用。射频识别技术在国外发展得很快。 由于发达国家 RFID 电子标签工作开展得较早，所以在技术、标准、产业链及应用方面都已经比较完备，特别是在核心技术尤其是在芯片技术上，目前已经提供了相对完备的产品线，并且由于技术进步和RFID电子标签工艺的提升以及成本的降低，应用推广进入了良性循环。像TI、Motoro1a、Microchip 、Philips等世界著名厂家都生产RFID 产品3。射频识别技术在国内也广泛推广，目前已应用于中铁车号自动识别系统，高速公路自动收费系统，各种金融商务卡等领域。2006年，我国发布了中国RFID技术政策白皮书：其标准体系包括接口规范、读写协议、编码体系、应用规程、测试规程和数据安全等众多方面。中国设立了 7个RFID标准组：分别是总体组、频率与通信组、标签和阅读器组、信息安全组、数据格式组、应用组和知识产权组。中国RFID标准体系框架的研究工作也已基本完成。目前，中国的 RFID产业链基本建立起来，主要集中在北京、上海、深圳等地。 1.2 开展研究的意义尽管RFID技术在很多领域都具有良好的应用前景，并且已经逐渐在一些领域广泛应用，但其发展也受到了一些因素的制约。其中最关键的就是信息传输过程中的干扰问题。RFID中的碰撞问题主要分为两类：一类即阅读器碰撞问题，它产生于同一个物理区域内存在多个不同的阅读器，它们以同一频率同时与区域内的标签通信而引起的冲突4。另一类是标签碰撞问题，如果标签同时处于阅读器的有效工作区内时，可能会发生多个标签同时发送信号的情况，这时要求阅读器能在很短的时间内识别多个标签，由于阅读器和标签通信共享无线信道，阅读器或标签的信号可能发生信道争用，信号互相干扰等问题，使阅读器不能正确识别标签（如图1.1）。在实际使用中，多标签碰撞是造成干扰的主要原因。 图1.1 RFID 系统标签碰撞图RFID电子标签常依附于廉价商品之上，标签通常采用无源形式以降低成本，需要其防碰撞算法对标签功能不能有过高要求；同时RFID系统以身份识别为主要功能，所以需要在最短的时间内识别出最多的标签 。因此RFID系统必须采用特定的策略或算法来避免冲突现象的发生。将射频区域内多个标签分别识别出来的过程称为防碰撞，防碰撞问题主要就是解决如何快速和准确地从多个标签中选出一个与阅读器进行数据交流，而其他的标签同样可以从接下来的循环中被选出与阅读器通信。防碰撞技术是信号处理与识别的关键技术，其防碰撞协议的优劣，在很大程度上决定了 RFID系统性能及其应用领域。本课题主要针对基于Aloha的防碰撞算法进行研究，对基于Aloha算法的改进算法进行仿真，在帧时隙Aloha算法的基础上获得更快速高效的防碰撞算法，并对各种防碰撞算法进行分析和比较。2. RFID系统组成及主要工作原理2.1 RFID系统组成RFID系统通常由控制系统、阅读器和电子标签构成5（如图2.1）。l 电子标签(tag)是射频识别系统中存储可识别数据的电子装置。l 阅读器(reader)是将标签中的信息读出，或将标签所需要存储的信息写入标签的装置。Error! No bookmark name given.Error! No bookmark name given.Error! No bookmark name given.Error! No bookmark name given.图2.1 RFID系统构成 阅读器包含： 射频单元、电源模块、存储器、 数据协议栈处理器等，是RFID系统的信息控制和处理中心，负责控制与标签间的双向通信并执行来自主机系统的指令。阅读器的频率决定了RFID系统的工作频段，阅读器的功率决定了RFID系统的有效识别距离。射频单元（包括天线）负责发射和接收射频载波信号。射频载波信号由射频振荡器产生并由射频处理器放大，经过天线发射给周围的标签;另一方面，射频模块通过天线接收从标签发射或反射回来的射频载波信号，解调后送数据协议处理器处理。数据协议处理器是阅读器的控制中心，可以解码识读射频模块发来的信号，必要时送后台网络系统进行处理，或执行后台应用软件发来的命令，将要写入标签的信息编码后送射频模块，完成对标签的控制操作。对一些特殊系统还提供防碰撞、加解密以及身份验证等附加功能。常用的接口电路有RS232、RS485、USB等，负责与上位机、后台网络或其它系统进行通信，实现标签信息与后台数据库的实时交互6。电子标签包含：天线，射频接口和芯片（如图2.2）。其中射频接口主要是调制解调器和电压调节器，芯片部分主要封装有逻辑控制单元、EEPROM和存储器单元等。图2.2 电子标签内部结构图RFID标签种类繁多：l 按供电方式分：可分为有源(Active)标签和无源(Passive)标签。l 按工作频率分：可分为低频（LF）标签、高频（HF）标签、超高频（UHF）标签以及微波（uW）标签。l 按通信方式分：可分为主动式标签（TTF）和被动式标签（RTF）。l 按标签芯片分：只读（R/O）标签、读写（R/W）标签和CPU标签。大多数RFID系统属于阅读器主动询问类型即（Reader Talk First-RTF）；也有少量标签主动询问式RFID系统（Tag Talk First-TTF），这类系统主要用在高速移动和特殊环境下。因此这里我们只讨论阅读器主动询问型的RFID系统7。有源式标签又称主动式标签，由电池供电，利用自身射频能量主动向阅读器发送数据，读写距离远。无源式标签又被称为被动式标签，它依靠外界电磁感应供电，读写距离较近，但是成本低。当然，还有半主动式标签，通过反向散射调制方式传送数据。目前市场上使用最多的，是无源标签。这里我们讨论的也将是无源标签。 图2.3 无源标签耦合示意图无源标签的工作模式有两种，一种是近距离电感耦合，一种是远距离电磁耦合8 (如图2.3)。电磁耦合与电感耦合的差别在于：电磁耦合方式中，阅读器将射频能量以电磁波的形式发送出去；在电感耦合方式中，阅读器将射频能量束缚在阅读器电感线圈的周围，通过交变闭合的线圈磁场，沟通阅读器线圈与射频标签线圈之间的射频通道，没有向空间辐射电磁能量。2.2 RFID系统工作原理在正式研究RFID系统的防碰撞算法之前，我们先了解一下RFID系统的工作原理9。RFID系统工作原理如下: 首先，阅读器(reader)通过发射天线发送一定频率的射频信号。当电子标签（tag）进入发射天线工作区域时产生感应电流，射频卡获得能量被启动。经过判断，射频卡将自身编码等信息透过卡内天线发送出去。接着，阅读器接收天线接收到从标签发送来的载波信号，经天线传送到阅读器，阅读器对接收信号进行解调和译码然后送到后台软件系统处理。最后，后台软件系统根据逻辑运算判断该卡的合法性，针对不同的设定做出相应的处理和控制，发出指令信号、控制执行相应的动作。 对于基于不同防碰撞算法的RFID系统，其工作流程有很大差异，具体内容将在之后的三章详细介绍。2.3 RFID系统的特点和应用RFID 标签具有体积小、容量大、寿命长、可重复使用等特点，可支持快速读写、非可视识别、移动识别、多目标识别、定位及长期跟踪管理1011。表格 1 RFID系统与其他识别系统比较 表格1是RFID系统与其他系统在成本，智能化，读写性等各方面的比较情况。由此表，我们发现RFID系统不仅仅是改进的条形码，它可承载信息量大，可细分单品，可大批量快速重复读写，保密性强，抗干扰能力较普通条形码，磁卡好，可与其他各种传感器共同使用，寿命最长，成本也较低，是未来最有市场的一种识别类产品12。表格 2 RFID系统分类RFID 系统工作在4个不同的频段上，分别是低频、高频、超高频和微波 。表格2展示了不同工作频率的RFID系统的技术特点和主要应用。对于无源有源两种系统，它们最大的区别在能量的供应方面。对于低频和高频系统，他们的频段在125kHz-13.56MHz，其工作能量通过电感耦合方式从读卡器耦合线圈的辐射近场中获得，属于无源系统。对于这类的标签，它工艺简单、成本低、无频率约束、有很强的穿透性。它的缺点是：识别距离近，一般在1cm左右；通信速率低，数据传输能力差;能存储的信息有限；阅读器、天线成本高，造价难以大幅下降。 超高频860MHz-960MHz系统的耦合方式采用的是电磁反向散射耦合。它的有效距离为0-10m，天线结构简单、容易实现、价格便宜。由于阅读距离的增加，应用中有可能在阅读区域中同时出现多个射频标签的情况，从而出现了多标签同时读取的情况，因此它的识读率无法达到100%，而且工作模式简单，没有加密功能，无安全性保证。 微波有2.45G和5.8G两个频段，他们都是采用的电磁反向散射耦合的方式进行信息和能量的传输。对于2.45G的系统，它的优势为：标签采用的是电池供电；工作有效范围可达100m以上，它的通信速率高，可以达到1Mbps；电磁波的波长较短，大概为12cm左右，天线可微型化，做到2cm，可以根据实际需要做成各种异形卡。 对于5.8G的系统，它是ETC使用的频段，它的优点为：传输特性接近于光传播，波束集中，方向性好；通信速率为 1Mbps，传输性能好；电磁波波长较短为5cm左右，天线可微型化；可与高速移动的物体上的DSRC设备进行通讯，可识别速度为200KM/H，这点能保证在ETC上应用的可靠性。 2.4 RFID系统现存问题和发展前景虽然 RFID 技术目前已经得到了广泛的应用，但是仍面临一些挑战1314。1）成本美国一个电子标签最低的价格是 5 美分左右，这样的价格是无法应用于某些价值较低的单件商品的，只有电子标签的单价下降到 5 美分以下，才可能大规模应用于整箱整包的商品15。2）标准各个国家和地区出于自身安全和利益的考虑，都在积极地制定自己的标准16：ISO/IEC 18000，EPC Global，日本的 Ubiquitous ID 都在分别制定和推动自己的标准。各个标准体系不但编码体系不尽相同，频率的使用也不同，即使同一频段，在空中接口、实现方法上也有差异，再加上各国无线电管理差异，预留的 RFID 使用频段根本不可能一致。以上各种不统一的标准体系给 RFID 全球化应用带来了重重困难17。3）安全当前广泛使用的无源 RFID 系统还没有非常可靠的安全机制，无法对数据进行很好的保密，数据还容易受到攻击。主要是因为 RFID 芯片本身以及芯片在读或者写数据的过程中都很容易被黑客所利用。对于可读可写标签，还存在电子标签上的信息被恶意更改的隐患。如果电子标签中的信息被窃取甚至恶意更改，将可能给物流保障带来无法估量的损失18。4）识别距离 事实上，RFID 标签的识别距离尚不能满足零售商品的管理需要。目前低频段 RFID 标签的识别距离相当有限，高频段的 RFID 标签有效距离仅为1米左右，超高频 860930MHz 的有效距离为 36 米。 5）多标签碰撞问题RFID系统常应用于物流跟踪和产品识别的领域，这要求RFID阅读器能够在最短的时间内识别出尽量多的产品，而制约RFID阅读器识别效率的最关键的问题就是识别过程中的多标签碰撞问题。其本质就是数据链路层的多址接入和防碰撞算法的选择问题。如何找到一种适用于RFID系统的、高效节能的防碰撞算法，正是本文所要研究的重点。针对上述这些问题，各国专家作了深入的研究，并提出了一系列的方法，如对于安全性问题，文献1920提出了多种签名保密机制，文献21提出了利用水印的技术，其他的还有如使用基于硬件的方法和提出新的认证协议 。为了提高产品的可靠性，很多人提出了相应的改善措施，如文献22提出了利用后端数据库比较应答器的重量的方法来提高识别率，文献23提出了利用 RFID系统所构成的网络来提高系统的可靠性的方法。 RFID 技术应用于物流管理、工业制造、公共信息服务等行业，可大幅提高管理与运作效率，降低成本。随着相关技术的不断完善和成熟，RFID 产业将成为一个新兴的高技术产业群，成为国民经济新的增长点24。因此，研究RFID技术、发展RFID 产业，对提升社会信息化水平、促进经济可持续发展、提高人民生活质量、增强公共安全与国防安全等方面有着深远影响，具有重大意义。3. Aloha访问控制协议与RFID防碰撞算法设计RFID系统防碰撞问题可以归结到通信领域的多址接入技术来解决。硬件方法主要有TDMA、FDMA、CDMA等，其优点为延时小，但会增加系统的复杂度和成本，不适合需要低成本、量产的RFID 系统。软件方法相对成本低廉，更多为我们所接受。其中主要有纯 Aloha、时隙Aloha 、帧时隙 Aloha等，这些方法对系统设计要求较低，易于修改，但时延较长。3.1 基本多址接入方法多址接入基本有四种方法：频分多址，空分多址，码分多址和时分多址。1. 频分多址 FDMA（ Frequency Division Multiple Access） 是通过使用不同的频段，实现信号的同时传输。对于RFID系统来说，可以使用频率可调的电子标签（如图3.1）：阅读器下行链路采用最佳频率fx ,而各个标签采用若干可选应答频率F1-F6。 这样完全可以防止碰撞，但是这需要阅读器为每个接收通路配备单独的接收通道，对阅读器的性能要求过高，成本过高，只适合在特殊场合使用25。图3.1 频分多址2. 空分多址SDMA（Space Division Multiple Access） 是利用空间范围的分割实现通信的同时进行。这是一种很古老的多址方法。要达到SDMA的效果，要求单个阅读器作用范围很小，为此，可以把大量阅读器和天线覆盖面积并排安置在一个阵列中，使得单个阅读器的通信容量在相邻的区域内可重复使用（如图3.2）。当电子标签经过这个阵列时，与之最近的阅读器便可与之通信，由于每个阅读器的影响范围很小，使得相邻阅读器工作范围内的其他电子标签可以正常工作不受影响。空分多址SDMA技术，由于需要安装有自适应定向天线的读写器 ，其复杂度很高，成本也过高，而且识别速度较慢，故此技术仅被应用于某些特殊的领域。 图3.2 空分多址3. 码分多址CDMA （Code Division Multiple Access） 是最新发展起来的一种多址方式，它的应用范围很广，但是却不适合RFID系统。CDMA技术基于扩频通信，即需要把要传送的信号先扩频，再编码调制，发送的是宽带信号。接收端需要将宽带信号解扩，才能实现通信。因此，CDMA抗干扰性好，安全性高，信道利用率高，适合对频谱利用率要求低的领域。然而，它技术过于复杂，信道容量小，频带利用率低，不适合在需要低成本运作的RFID系统上广泛运用。4. 时分多址 TDMA（Time Division Multiple Access） 是把整个通信容量按时间分配给多用户的技术。它的简单和高效十分适合RFID防碰撞系统。TDMA运用于RFID中，有两种工作方式，一种的基于标签控制的，非同步方式。这种方式对数据传输没有控制，因此很慢而且不灵活，很少被采用。另一种是基于阅读器控制的，同步的控制方法：依据一种事先约定的算法，阅读器在其工作范围内，激活所有的电子标签，并根据此算法，选择某个标签与之通信，包括读取写入数据，身份鉴别等。 通信结束后，结束原有通信关联，与另一个标签建立通信。目前，解决RFID 碰撞问题主要基于两种防碰撞算法：Aloha算法和二进制搜索算法。其中，Aloha算法是TDMA的一种，已被广泛运用于生产生活中。3.2 基本Aloha算法及其在RFID系统中的应用 Aloha网络或Aloha协议是世界上最早的无线电计算机通信网，也是最早最基本的无线数据通信协议。它是1968年美国夏威夷大学的一项研究计划的名字，是夏威夷人表示致意的问候语。这项研究计划的目的是要解决夏威夷群岛之间的通信问题。使用无线广播技术的分组交换计算机网络 Aloha 可以使分散在各岛的多个用户通过无线电信道来使用中心计算机，从而实现一点到多点的数据通信。Aloha协议处于OSI模型中的数据链路层,它属于随机存取协议（Random Access Protocol）中的一种。Aloha算法是一种不确定性算法，其延迟时间和检测时间是随机分布的，可分为纯Aloha、时隙Aloha以及帧时隙Aloha算法等。3.2.1纯Aloha算法纯Aloha算法是一种最简单最基本的防碰撞算法。Aloha协议的思想很简单，只要用户有数据要发送，就尽管让他们发送26。当然，这样会产生冲突从而造成帧的破坏。但是，由于广播信道具有反馈性，因此发送方可以在发送数据的过程中进行冲突检测，将接收到的数据与缓冲区的数据进行比较，就可以知道数据帧是否遭到破坏。同样的道理，其他用户也是按照此过程工作。如果发送方知道数据帧遭到破坏（即检测到冲突），那么它可以等待一段随机长的时间后重发该帧。图3.3 纯Aloha算法示意图如图3.3所示，一开始只有发送端1 发送了一个数据帧，那么发送端1将被正确识别。随后发送端2产生数据，并立刻发送，由于信道空闲，故也发送成功。一段时间后，发送端1又产生了数据，并按照Aloha的发送协议立即发送数据，接着发送端3也开始发送数据。这样 1和3就产生了部分碰撞；如果两个发送端恰好在同一时间发送数据，那么信息将被完全碰撞。 该算法的优点是，各个发送端发送数据的时间是完全随机的，不需要同步，比较容易实现，特别是当发送量较少时能够很好的进行工作。但是缺点也很多，比如发送数据后如果产生冲突，则需要延时退避一段时间再发。退避时间选择很困难，如果设置过大，则系统的识别时间就会变长；如果设置过小，系统发生重复碰撞的几率就会大增，需要退避的次数也会过多。纯Aloha 性能分析27：设帧为定长， 站点独占信道时成功发送一帧所用的时间为t, 吞吐率（吞吐量）S 定义为t 内成功发送的平均帧数， 网络负载G定义为t内N个站点总共发送的平均帧数，P定义为成功发送一帧的概率， 则 S= G*P。其中，一帧成功发送的条件是该帧与其前后2帧的到达间隔均大于t。图3.4 纯Aloha冲突区示意图任一帧内有k 个用户到达的概率服从泊松分布。故帧空闲的概率为 e-G。假设帧长为t,在t0到t0+1时间内，其他用户发送帧的尾部与阴影帧的头部冲突；在t0+t到t0+2t，其他用户发送帧的头部与阴影帧的尾部冲突。即危险冲突区为2个帧时。于是传输成功的吞吐率是：S = p0 p1= e-G Ge-G = Ge-2G式中S在G=0.5时，取得最大值，Smax = 1/(2e) 0.18图3.5 Aloha算法输入负载与吞吐量比较纯Aloha所采用的多址方式实际上是一种无规则的时分多址。在泊松分布条件下，每个帧时间尝试发送次数G=0.5时，信道吞吐量S=0.184 。也就是说，纯Aloha最多只能用原信道吞吐量的18.4%。业务繁忙时，发生碰撞概率增多，性能也将急剧下降（如图3.5）。因此纯Aloha只适用于通信量较小的通信系统中。我们可以将基本的pure Aloha 的思想运用到RFID系统中。纯Aloha一般运用于只读RFID系统中，主要采用标签先发言的方式，即电子标签一旦进入阅读器的射频工作范围获得能量后，便向阅读器主动发送自身的序列号。用户有信息即可发送，采用冲突监听与随机重发机制。这样的系统是竞争系统，在通常情况下，某个标签向阅读器发送数据的周期循环过程中，如果有其他电子标签也同时向该阅读器发送数据，此时阅读器接收到的信号就会重叠，导致阅读器无法正确识别和读取数据。由于广播信道具有反馈性，因此阅读器可以在发送数据的过程中进行冲突检测，将接收到的数据与缓冲区的数据进行比较，就可以知道数据帧是否遭到破坏。如果阅读器知道数据帧遭到破坏（即检测出冲突发生），阅读器则向标签发送指令使标签停止发送数据，电子标签接到阅读器指令后，随机延迟一段时间再重新发送数据。 图3.6 RFID系统pure Aloha算法示意图如图3.6中，阅读器向标签广播一个request 命令，3个标签分别响应阅读器。其中标签1和标签2 发生不完全碰撞，标签3被成功识别。第二次标签1和标签2分别响应阅读器，由于恰好选择了同一个时间发送信息，所以两个标签发生了完全碰撞。由于前两轮识别都没能成功识别出标签1和3，所以还需要第三轮识别。3.2.2时隙Aloha算法1972年，Roberts发明了一种能把信道利用率提高一倍的信道分配策略，即时隙Aloha协议28。其原理是用时钟来统一用户的数据发送。它将时间分为离散的时间片，用户每次必须等到下一个时间片才能开始发送数据，从而避免了用户发送数据的随意性，减少了数据产生冲突的可能性，提高了信道的利用率。当有线电视电缆被用来访问Internet的技术被发明时，被弃用多年的时隙Aloha才重新受到重视29。图3.7 时隙Aloha 算法示意图如图3.7所示，时隙Aloha 和纯 Aloha 的区别在于，时间被分割成等长的时间段，时隙Aloha规定发送端必须在一个时隙的开始发送数据，这样，一旦发生冲突，就是完全碰撞，不会产生部分碰撞的情况。使用时隙Aloha的方法，数据包的传送总是在同步的时隙内才开始，该算法使得标签成功发送或者完全冲突， 冲突危险周期被减小一半。由于冲突的危险区平均减少为纯Aloha的一半，因此时隙Aloha的信道利用率为：S = p1 = Ge-G式中S在G=1时，取得最大值，Smax = 1/e 0.36 ，是纯Aloha协议的两倍。图3.8 时隙Aloha与纯Aloha性能比较时隙Aloha的优点是可以将冲突减少一半，但是，它需要全网同步，需要设置一个特殊站点，由该站点发送时钟信号。而且当信道负载微小的增加时，冲突会呈现指数增加，降低信道性能。将时隙Aloha理论运用到RFID系统中，我们可以发现。在时隙Aloha算法中，每个时隙存在无标签响应、唯一标签响应、和多标签响应三种情况。当电子标签的数据帧在某个时隙发生了碰撞，该标签就会随机等待一段固定的时隙长度后，再向阅读器发起通信。如下图所示：图3.9 RFID系统时隙Aloha算法示意图图3.9中阅读器向标签发送request 命令，该指令使阅读器范围内的所有标签同步，标签收到request 指令后，等下一个时隙到来就向阅读器发送数据帧及ID信息（在这里假设一个时隙内，标签可以将所有信息传送完）。例如，图中标签1选择了在时隙2和5中发送信息，标签2和3同时选择了时隙1发送数据，因此发生了完全冲突。时隙2中只有标签1发送的信息，所以被正确接收。标签4和标签5分别选择了时隙3、5和6发送信息，故而分别和标签3、标签2发生了冲突。标签发送数据冲突后，等待一段随机的时间重发，直到发送成功为止。这种算法的优点是避免了部分冲突，使系统的吞吐量提高了一倍。然而碰撞了的电子标签仍然需要随机延时重发。假设阅读器射频工作范围内存在N个标签，理论上阅读器需要至少N个时隙才能成功识别完，如果在识别的过程中，又有别的标签到达，那么系统吞吐率会直线下降。最坏的情况下，系统经过多次搜索，也未能识别出某个标签，导致“饿死现象”。3.2.3帧时隙Aloha算法这是在时隙Aloha算法的基础上，在时间域上进一步离散的结果。帧时隙Aloha将N个时隙组合成一帧，其中时隙长度固定，一帧中所包含的时隙数也固定。在整个识别过程中不改变帧的大小，每一帧的最大时隙数N 默认。帧中每个时隙都足够一个发送端向接收端发送完自身的ID信息。发送端随机选择N个时隙中的一个与接收端通信，一旦发生碰撞则等到下一帧的时候再随机选择时隙重发。而不是随机延迟若干时隙后重发。这样每个发送端在每一个帧中只占用一个时隙进行通信，在同一帧中，同一个发送端不会重复发送数据。这样不仅避免了不完全碰撞造成的冲突，而且简化了随机退避时间的选择机制。 该算法又被称为固定帧时隙Aloha算法（FSA）。 图3.10 RFID系统帧时隙Aloha算法示意图这是基本的帧时隙Aloha的思想。将之运用到RFID系统中，则如图3.10所示，图中每一帧的长度设置为6个时隙，阅读器工作范围内标签数为5个。下行链路中，阅读器向无线信道中广播一个request 命令，同时广播此帧的帧长N。标签接收到此命令信息后，在1-N之间选择一个随机数，作为自己本轮通信所使用的时隙。其中，标签2选择了时隙1，故在此帧的第一个时隙开始时，标签2向阅读器发送身份信息010。由于时隙1只被标签2占用，故标签2被阅读器成功识别。阅读器成功收到标签信息后，向全网广播一个接收信息包 next-slot 表示此包被成功识别。标签2收到此成功识别信息后，进入静默状态，不再与阅读器通信。标签1和4同时选择了时隙3进行通信。当时隙2结束后，时隙3开始，标签1和4共同占用信道 ，发生多标签冲突，此时阅读器无法正确识别标签发过来的信息，故向全网广播一个close-slot 包，此时隙被判断为完全碰撞时隙，标签1和4接收到此close-slot 包后，各自N-coll 加1，并等待下一帧时重发。由于没有任何一个标签选择在第4时隙发送数据包，阅读器检测到第4时隙未接收到包，故判断第4 时隙为空时隙，N-idle加1. 标签5选择第5个时隙并成功完成身份识别和数据交换，时隙6为空时隙，尽管时隙6为空，标签1和4仍然不能利用时隙6发送数据，因为帧时隙Aloha规定，每一个帧中，发送端只能选择一个时隙发送数据。所以，当第一帧结束后，标签1和4仍然未被识别。阅读器再次发送request 命令，开始第二帧的检测，在第二帧中，标签1和4分别选择了时隙3和2，很快也被成功识别了。3.2.4改进的动态帧时隙Aloha算法及帧长选择固定帧时隙Aloha简化了访问控制协议的随机退避机制，但是在使用过程中，也产生很多问题。特别是，当固定帧长N与系统待识别标签数相差较大时，系统性能大幅下降。当标签数远大于帧长N时，可能出现N个时隙均发生多标签碰撞的问题，这样，一帧中系统未能识别任何一个标签，系统进入一个死循环，我们称之为固定帧时隙Aloha的“饿死现象”。当标签数量远小于帧长N时，必然会出现大量的时隙空闲，这样，算法的时隙利用率就大大降低，产生“时隙浪费”。固定帧时隙Aloha算法帧长不随标签数变化，系统无法获得稳定地吞吐率。为了使RFID系统能够更广泛的运用于负载波动较大的场合，需要找到一种对标签数动态变化不敏感的防碰撞算法，就是改进的动态帧时隙Aloha算法。当系统待识别标签数较多时，动态增加帧长，降低时隙碰撞率，提高系统性能；当系统待识别标签数较少时或者随着识别过程的进行，系统待识别标签数逐渐减少时，动态的缩短帧长，降低空闲时隙数比率，可以减少浪费，提高时隙利用率，提高系统性能。DFSA与FSA最大的区别是帧长随标签数目的改变而动态的改变30。 当帧长和标签数量差别较大时，系统的识别效率很低，甚至出现完全无法识别的状况。为了改变这样的状况，我们需要动态的调整帧长以适应标签数量的不断变化。为此我们需要有一个判断待识别标签数量的方法。文献31详细分析了标签估计和帧长选择算法。其中，根据文献32假设碰撞时隙数为C，则未识别标签数N=2.39*C。 帧长选择算法中，假设一帧中的时隙数为N，并且标签数为n，在同一个时隙中出现的标签数为t 的概率服从二项分布：所以被t个标签占用的时隙数m 服从故，可得成功识别标签数S系统识别率T：对上式微分，可得N=n。这就说明当一帧中的时隙数目等于阅读器待识别标签数目时，系统的识别率最高，系统的标签识别速率最快。但是实际应用中，DFSA的帧长只能从多个数值中进行选择，不能任意取值。因为RFID系统传输的数据包一般为ID信息，ID数据包一般为96位的EPC编码，基于时隙的Aloha算法约定阅读器和标签之间的一次通信可以在一个时隙内完成。时隙长度的选择与整个系统的识别时间长短成线性关系。为了尽可能的缩短系统识别时间，提高系统识别速度，就需要尽量缩短每个时隙的长度。在数据传输速率相同的情况下， 要缩短时隙长度，又要保证阅读器和标签之间的身份识别在一个时隙内完成，就必须减少每一时隙内的数据传输量 。由于帧长信息需要及时更新，如果帧长可以任意选择，如257，则需花费9位来传输帧长信息，无疑是一种浪费。为此，本设计人为规定，帧长的取值在4,8,16,32,64,128,256之间选择，并利用3个bit位来表示这八种帧长选择形式（具体选择方法在4.2.2中有详细叙述）。图3. 11 RFID系统动态帧时隙Aloha示意图动态帧时隙Aloha算法基于固定帧时隙Aloha算法，将其运用于RFID系统中，则如图3.11 所示。图中，该系统包含一个阅读器和13个电子标签。每轮通信开始时，阅读器向工作范围内的所有电子标签广播一个带有帧长信息的数据包request，图中帧长为8，标签收到包后，读取帧长8，从1-8中随机选择一个时隙与阅读器通信。图中，tag8选择了第1个时隙，由于只有tag8选择了第1个时隙，tag8在第一轮通信中即被成功识别，不再参与以后的3轮识别。Tag2、tag5、tag13同时选择了时隙2，故时隙2产生多标签碰撞，tag2、tag5、tag13需要在Frame2中重新选择时隙进行第二次识别。Frame1结束后，统计该帧中碰撞时隙数为4，碰撞标签数为9，根据最优帧长选择理论N=n时，系统识别率最高，故下一轮帧长仍然选择为8。第二轮识别（Frame2）结束后，统计该帧中碰撞时隙数为2，碰撞标签数为4，空闲时隙数为1，根据最优帧长选择理论，下一帧的帧长设定为4。故Frame3帧长为4，在Frame3中，空闲时隙为1，碰撞时隙为1，碰撞标签数为2，故Frame 4 的最优帧长选择仍然是4。经过4帧27个时隙，13个标签被完全识别，识别率达48%以上。4. 基于固定帧时隙Aloha的RFID防碰撞算法实现与性能仿真 本文的第二章介绍了RFID系统的基本结构和工作原理，第三章介绍了基本Aloha访问控制协议的工作原理，并对其在RFID领域的运用做了简单的比较，这一章将具体的说明基于固定帧时隙Aloha的RFID系统的通信流程，以及如何利用OPNET网络仿真软件搭建基于帧时隙Aloha的RFID系统并对其系统性能进行分析。4.1 固定帧时隙Aloha算法流程 Aloha协议是通信领域最简单的协议之一，然而它的简单变形帧时隙Aloha算法的实现并没有那么简单。本算法基于RTS型RFID系统，并假设标签ID信息可以在一帧内传完。图4.1简单的描述了整个算法的核心思想，下文简略描述帧时隙Aloha算法实现的过程。（具体程序见附录） 1.时隙0(即第三章中3.2.3提到的request阶段)，仿真开始，触发仿真开始中断begsim-intrpt。识别过程开始, 阅读器广播一个 pk_new_round 命令，该命令中包含帧长N。第一个命令发送后，时隙计数器slot_count自增。同时判断slot-count 是否为0，当slot-count 不为0时，设置一个超时自中断，并将其句柄赋给evh。 此超时自中断如果不及时取消，将在下一个时隙开始之前被触发。当一轮识别结束后，slot-count 重新设置为0。2.阅读器工作范围内的标签收到阅读器的指令，识别出帧长N，然后利用floor(op_dist_uniform(N)+1）函数随机产生一个1，N之间的随机整数，并以该数值所代表的时隙，作为自己与阅读器通信所使用的时隙self_slot。与此同时，记录当前时间所在时隙current-slot。作为整个系统时间同步的起点和标准。所有标签的传输，均从之后的N个时隙中选择进行。 3.slot-count 用于记录当前时间在一帧中所在的时隙。它的取值范围为1-N，随着每轮阅读器的读取情况而自增。第一次循环的第一个时隙时，令slot_count=1 。current_slot为标签同步标识。 表示此帧正式开始工作的时间所在的时隙。next-slot 表示下一个时隙的真实时隙数，令 next-slot=slot_count+current_slot .调用if_slot_shot()函数判断，当slot_count恰好等于标签自己随机产生的时隙数self_slot 时，调用OPNET提供的自中断函数，op_intrpt_schedule_self（transmit_time, code），在时间transmit_time= next_slotslot_length处触发自中断， 与此同时标签向阅读器发送应答信息。该应答信息主要是标签ID。4.阅读器广播完Init_round 命令后，回到初始状态并等待标签回应。当收到信道中来自标签的包后，首先取消先前设置的超时自中断。判断包是否正确接收。如果信道中只有一个标签的应答信息，则判断包成功接收。读取该包中的ID信息，存放在Tag-Id中。并且向外广播一个next-slot 包，该包中携带Tag-Id 信息。阅读器回到初始状态，slot-count 加1，超时中断开启，设置时间为下一时隙的尾部，即slot_count+current_count+1。如果信道中有多个标签的应答信息，则记录发生碰撞的标签数coll_count，并加到total_coll 变量中。同时取消该包的接收，并发送一个close-slot 包。如果当仿真进行到slot_count+current_count+1时，仍然没有数据包被接收，则判定该时隙为空，空闲时隙数N-idle加1，并发送一个close_slot包。5.阅读器工作范围内的所有标签再次收到阅读器发来的包。当收到的包是一个next_slot包时，标签获取其中的ID，并将包摧毁。如果获取的ID值，与自身self_id 相同，则标签进入静默状态。短时间内不再响应阅读器发送的数据包。当获取的ID与自身id 不同时，标签判断下一跳时隙数与随机选择时隙数是否相同，如果相同，则在下一时隙开始后，发送封包。如果不是，则回到wait 状态，继续等待阅读器指令。 直到下一跳时隙数与自身 选择时隙数相同时，即发包。6. 一帧完成后,如果total-coll 为0，即此帧中没有发生标签碰撞的情况。则说明阅读器已经识别出了工作范围内的所有标签。阅读器停止工作，仿真结束。7.一帧结束后，如果total-coll 不为0，则说明该帧过程中，存在多个标签选择同一时隙发送信息的情况，即发生了多标签冲突。将total-coll加到N-coll中，total_coll 置0，开始新一轮的识别。由于是固定帧时隙Aloha，故每次新一轮识别时，帧长固定。阅读器发送时隙数同样为N的新帧， 在新一轮识别中，未被识别的标签重复第一轮识别中的方式。随机选择1-N中间的一个时隙，发送数据。标签发送信息的起始点不能任意，只能在一个时隙的起始处，标签传送的信息要么不碰撞，要么完全碰撞。8.这样，一帧一帧的识别，直到total-coll 为0时，整个识别过程结束。阅读器统计空闲时隙数N-idle，碰撞时隙总数N-coll，以及识别完成所用的总时隙数total-slot。并计算出时隙利用率=成功识别时隙总数/ total-slot，