物联网RFID多标签识别防碰撞算法研究与实现

王超梁 赵成 周鹏

摘 要：物联网RFID多标签识别防碰撞算法对系统的识别效率和稳定性至关重要。为了解决多标签识别的碰撞问题，对 ALOHA及其改进算法进行了仿真分析，给出了不同时隙长度时标签数目与系统吞吐量的关系，提出了一种自适应动态调整帧长的防碰撞算法。仿真结果表明，随着标签数量的增加，自适应动态调整时隙长度的防碰撞算法吞吐率明显优于固定时隙算法和传统动态时隙算法。

关键词：物联网；RFID；ALOHA；多标签识别；防碰撞

中图分类号：TP391 文献标识码：A 文章编号：2095-1302（2018）01-00-02

0 引 言

射频识别（Radio Frequency Identification，RFID）依靠非接触式空间电磁感应实现电子标签和读写器之间的信息交互，完成标签信息的传递，被广泛应用于智慧物流、智能交通等领域。 RFID多目标识别系统中的碰撞问题分为读写器碰撞和标签碰撞两种，多标签识别防碰撞算法的研究，解决了多个标签同时与一个读写器进行通信的碰撞问题。在高频电子标签识别领域，标签的防碰撞一般采用基于TDMA的ALOHA算法及其改进算法，ALOHA算法性能会随着标签数量的增加急剧恶化，导致信道利用率偏低；而基于确定性的二进制树搜索算法要遍历所有标签识别的可能性，故搜索效率较低。本文在分析ALOHA及其改进算法的基础上提出了自适应动态时隙的改进算法。

1 基于ALOHA算法的标签防碰撞算法

1.1 ALOHA算法

ALOHA算法是一种非常简单的TDMA算法，最早用于解决网络通信中数据包的拥堵问题，通常用于简单的RFID系统中。采用标签先发言的方式，自动向读写器发送自身的ID信息，完成身份认证后，只要有符合条件的数据包需要传输，读写器和标签就开始通信，直至完成数据包交互。因此，这种处理机制本身与应答器控制、随机的TDMA算法有关，两个标签可以在不同的时间发送请求，从而避免数据发生碰撞，如图1所示。但该算法在数据帧发送的过程中发生碰撞的概率很大，而且标签没有载波监听纠错能力。ALOHA算法平均交换的数据包量在G=0.4时达到最大，仿真结果如图2所示。

平均交换的数据包含量G可以表示为：

如果RFID系统吞吐率用平均吞吐率S表示，其值等于1时表示无数据包发生碰撞，其值等于0时表示没有数据包传输成功，平均吞吐率S为：

可以得到，纯ALOHA算法的最佳信道利用率为18.4%，提高信道利用率和数据吞吐量可采用，标签只在规定的同步时隙内才传输数据包。

1.2 时隙ALOHA算法

时隙ALOHA算法在ALOHA算法的基础上进行了改进，把标签信息传输的时间划分为若干个离散的时隙，数据包只能在时隙的起始端传输，以有效地将单纯ALOHA算法的碰撞周期缩减为原来的一半，同时将信道利用率也提高一倍。当标签进入读写器的识别范围并开始通信时，标签只在规定的时间间隙内发送数据；当读写器不工作或者标签的时隙结束时，标签发送请求命令无效，读写器响应标签请求。相比ALOHA算法，时隙ALOHA算法在很大程度上避开了请求高峰期，碰撞概率为ALOHA算法的一半。由式（3）、（4）可得当G=1时，吞吐率Q的最大值可以达到36.8%，相比ALOHA算法提高了一倍。

1.3 帧时隙ALOHA算法

帧时隙ALOHA算法是指在规定的时隙内，标签可以选择该时隙内的任一数据信道发送数据，如果选择的信道只有一个标签或占用信道的时间小于时隙长度，读写器可成功接收数据。反之，读写器接收数据失败，而未完成数据传输的标签将进入下一循环重新选择时隙（通道）。这种算法的优点是响应速度快，容易实施，但效率不高，而且也解决不了响应通道未开启的问题。由于该算法存在读写器无响应阶段的可能，会造成标签在一定时间段内无法识别，所以基于时隙随机分配的ALOHA算法只适用于低成本的RFID系统。本文对比了帧时隙L分别取16、32、64、128、256时的标签数目与吞吐率的关系，固定帧时隙算法标签数目与吞吐率的关系如图3所示。由此可见，当标签数目和时隙数相等时，系统效率最高。

2 自适应动态时隙ALOHA算法

动态时隙ALOHA算法解决了固定时隙算法时隙长度不变引起的标签等待问题，采用动态改变时隙个数的方式来提高系统的吞吐率。在多标签识别的过程中，标签数量的增加需要更多的时隙个数来完成数据传送。随着标签数量的增加，系统的识别效率急剧下降。本文提出了一种自适应动态时隙的防碰撞算法，根据标签的数量自适应调整时隙长度，使得在标签数量较多的情况下仍然可以得到较好的吞吐率。首先，读写器初定一个固定的帧长发送命令，标签根据自身的条件对是否符合要求作出回应；然后，读写器对发送数据的标签进行身份验证分析后，大致估算已识别和未识别的标签数；最后，依据未识别的标签数量，调整相应的帧长和通道数后，开始识别标签。当未识别标签数量太多时，数据通道不够分配，通常使用分组算法将未识别标签分成多个组，然后根据分组情况自适应调整时隙长度来完成各组标签的识别。本文采用改进演化算法进行时隙长度自适应调整，根据识别标签和未识别标签的个数，调整时隙长度，选取系统吞吐率作为优化函数，采用如下公式调整时隙长度：

其中：fmax为多标签识别系统最大吞吐率，favg为平均吞吐率，f '为每次选择的两个标签中具有较大吞吐率的选择方式， f为不同标签的适应度值，pc1为调整时隙长度演化计算的最大交叉概率，pm1为演化计算最大变异概率。

自适应动态时隙ALOHA算法和动态时隙ALOAH算法的性能比较如图4所示。可以看出，当标签数量在0～400之间时，本文改进算法与动态帧时隙算法的吞吐率相当；当标签数量超过400时，改进算法的吞吐率明显优于传统动态时隙算法。

本文改进算法与固定时隙算法的性能比较如图5所示。可以看出，当标签数目在0～200之间时，改进算法的吞吐率优于固定时隙算法；当标签数目在200～300之间时，固定时隙算法的吞吐率优于本文改进算法；当标签数目在300～400之间时，两者的吞吐率相当；当标签数目在400～1 000之间时，本文改进算法的吞吐率优于固定时隙算法。

3 结 語

本文在对ALOHA算法及其改进算法仿真分析的基础上，给出了固定帧时隙算法时隙长度与吞吐量的关系，提出了一种自适应动态调整帧长的防碰撞算法。仿真结果表明，系统吞吐率最优时，所取的时隙数和标签数量基本相等；随着标签数量的增加，自适应动态调整时隙长度的防碰撞算法吞吐率明显优于固定时隙算法和传统动态时隙算法。

参考文献

[1]王鑫.面向RFID系统防碰撞算法及安全机制研究[D].北京：北京邮电大学，2015.

[2]栗红果. RFID中标签防碰撞算法的研究与改进[D].武汉：华中科技大学，2014.

[3]王必胜，张其善.可并行识别的超高频RFID系统防碰撞性能研究[J].通信学报，2009，30（6）：108-113.

[4]朱云龙，陈瀚宁，申海.生物启发计算：个体、群体、群落演化模型与方法[M].北京：清华大学出版社，2013.

[5]施卫东.一种改进的RFID标签防碰撞算法[J].科技通报，2015，31（4）：121-123.

[6]刘道微.基于自适应搜索机制的RFID标签防碰撞算法[J].金卡工程，2016（11）：34-35.

[7]康维新，吴学文.一种改进的RFID标签防碰撞算法[J].哈尔滨商业大学学报（自然科学版）， 2014 （6）：677-681.

[8]王佩玮.无线射频识别标签防碰撞算法比较分析[J].物联网技术， 2017，7（4）：21-24.