基于能量和距离分簇的主动式RFID防碰撞算法

刘雄飞，周小军，肖振国

（中南大学 物理与电子学院，湖南 长沙410083）

0 引 言

射频识别技术 （radio frequency identification，RFID），通过射频信号自动识别目标对象，可快速地进行物品追踪和数据交换［1］，根据电子标签数据调制方式可分为主动式和被动式。目前，对主动式RFID 防碰撞算法的研究相对比较缺乏［2－4］，为消除或减少系统中的碰撞问题，设计出一种防碰撞能力强，识别速度快的主动式标签防碰撞算法是很有必要的。

目前，主动式RFID 应用系统的防碰撞机制大多基于ALOHA 类防碰撞算法［5，6］，其中 包 括 改 进 型 的ALOHA［7］和时隙ALOHA 算法［8，9］。但是这些协议都较为简单，数据重传会经常发生，导致系统的吞吐量低，识别时间较长。文献 ［10］提出了一种主动式RFID 动态退避算法，并对CSMA／CA 的退避时间进行了研究，该算法降低了主动式标签功耗和读取时延，但要求系统对数据碰撞自动检测。文献 ［11］在标签密集环境下提出一种被动式标签的PDC（power－based distance clustering）防碰撞机制，其机制只能运用在被动式标签的防碰撞算法中，并不能用来解决主动式标签的碰撞问题。

本文主要研究主动式RFID 防碰撞算法，针对上述问题，提出一种基于能量和距离分簇的主动式RFID 防碰撞机制，把这个机制称之为EDC （energy and distance clustering）。本文首先对该机制进行理论分析和流程设计；然后利用提出的EDC 机制融合现有的纯ALOHA、时隙ALOHA 和非坚持CSMA 防碰撞算法进行实验仿真；最后对有无融合EDC 机制的防碰撞算法的吞吐量和平均传输时延进行分析与比较。

1 EDC机制理论模型

基于能量和距离分簇 （EDC）机制是一个适用于主动式RFID 系统的防碰撞机制。该机制基本原理是利用阅读器接收到的主动式标签的传输功率大小，对距离阅读器周围的主动式标签做簇群分类，每个簇群内远近的标签是通过调整阅读器的接收来自于标签所发出的能量信号强弱进行辨识，而标签发射功率的强度大小取决于标签与阅读器之间的距离。

1.1 能量传输分析

主动式RFID 系统在自由空间传输模型中，距离主动式标签发射天线R 处的功率密度为

在阅读器与主动式标签最佳对准和正确极化时，阅读器可接收的最大功率与功率密度S 成正比，则阅读器的接收功率Pr为

式中：Ae——阅读器接收天线的有效面积，最佳接收状态下

因而有

式中：Pt——标签的发射功率；Gt、Gr——标签和阅读器的天线增益；λ——所传输信号的波长 （取决于频率）。

在自由空间传输中，电磁波随着传输的距离增大，能量在自然扩散中引起传输损耗，则距离R 的自由空间传输损耗Lf为

由式 （5）可知，经过自由空间传输损耗后，距离主动式标签R 处的阅读器接收功率Pr为

则此时的主动式标签发射功率为

1.2 EDC模型分析

主动式标签和阅读器的读取之间的距离是变化的，因为标签在不同位置的天线功率是不同的，由式 （6）可知阅读器接收标签功率Pr与R 的二次方成反比，距离越远，阅读器接收到的信号越弱。因此可根据式 （7）对阅读器接收的可设定范围内的标签发射功率Pt大小进行分簇。通过利用接收功率的变化来进行标签的距离群簇，极大的减少每次做防碰撞算法的标签数目，以期达到更有效率的防碰撞。在EDC机制中，当进行防碰撞算法之前，会首先对所有的主动式标签进行区域分类，然后再逐个簇群的进行防碰撞处理，所以，EDC机制能够有效减少主动式RFID 系统的整体工作量，并能够有效的缩短识别时间。

图1表示EDC机制距离分簇模型。阅读器对所有标签按照其功率大小进行距离的排序和分类，用T、T′和T″来表示属于不同簇群内的标签，根据阅读器从标签那接收到不同的信号，可以分出不同群簇的标签，而这些群簇也正是代表着距离远近彼此不同的主动式标签。图1所示把每个簇群能量信号 （即主动式标签发射功率）的区间值设为step 值，阅读区域可以分为sd、sd－step 和sd－2＊step 标签群簇区间，因此在任何时候，只有同一个群簇的标签请求发送数据与阅读器通信，优先从能量信号强的簇群开始识别。即当第一群簇sd 的标签经阅读器识别完毕后，并立即进入休眠模式，然后第二群簇sd′的标签才能与阅读器通信，以此类推进行识别。

图1 阅读器与标签之间距离分簇

图2所示，主动式标签信号强度也可在同一簇群内进行层级分类，按照阅读器接收的功率大小把标签距离为d1＞d2＞d3＞d4＞d5，从而阅读器对标签的读取顺序为：T5→T4→T3→T2→T1，如此循环进行逐个读取标签信息，极大的减少标签的碰撞。

2 基于EDC机制的算法流程

EDC机制的运行首先是阅读器读取第一个簇群后，所有属于同一个簇群的主动式标签都会进入休眠模式，阅读器则会开始识别下一个簇群内的标签，这样一轮一轮的读取阅读器所能接收到的最远的那个簇群为止，就结束了整个流程。

图2 同一簇群内标签能量信号强度分类

EDC的流程如图3所示，首先所有的主动式标签先对阅读器发出请求指令，阅读器接收到所有标签发出的指令，其中也包含了信号的强度，然后阅读器按照信号强度找出最大值和最小值，设置sd 为标签信号的最强功率信号，把这个最强功率信号当作一个区间值step；如果还有任何未读取的标签，该标签的信号强度又大于或等于sd 值，则这些标签需要执行主动式防碰撞算法来解决碰撞问题；否则，就将sd 值减少一个区间值step；假如sd 小于最小值时，整个流程就结束。

图3 基于EDC机制的算法流程

在理论上来说，EDC机制与现提出来的主动式算法相兼容，而大多数RFID 系统中，阅读器都提供了功率控制机制，与EDC机制相结合能够增强防碰撞能力。EDC 机制同样也可以解决处在流动密集环境 （如物流仓库或卸货码头）的标签碰撞，由于标签碰撞率较高，识别过程需要较长的时间，则需要通过调整EDC 机制一个重要参数step值。此参数用来确定的标签簇群的范围，在一个簇群范围内，step 值决定簇群内标签的数量。在密集的环境中，需要有多个簇群，则step 值就调低，反之就调高，避免不必要的读取次数，来提高识别效率。但本文暂不讨论流动环境，因此设step 参数为固定值。

由图3可知，整个EDC要运行成功，最重要的就是一开始阅读器必须能够成功的取得所有标签的信号，并能够分辨出最大和最小的信号强度，假如不能够成功计算出标签的最大和最小的信号强度时，就不能够准确的对在场所有标签根据它们与阅读器的距离进行分簇，然而要达到这一目的，其中一个最重要的因素就是EDC 机制必须先要解决信号碰撞问题。由于信号在空气环境下中传送，阅读器在接收信号的时候就很可能发生碰撞问题，如果因为碰撞问题导致EDC 在一开始就无法准确的辨识标签的信息和它的信号强度时，那就整个机制无法顺利执行。

前述提到的问题将严重影响EDC 的运行，根据ISO／IEC 18000－7主动式标签收集算法［12］，本文结合时隙ALOHA 协议来解决这个问题，首先阅读器对整个所有标签发出请求并提出收集 （collection command）指令来取得所有标签的信号。而对于主动式标签来讲，主动式标签有自己的电源，所有一开始阅读器可以通过唤醒命令 （wake－up）让所有标签从休眠中醒来，再进行查询命令 （query command）获取所有主动式标签信号，通过获取最大值最小值命令 （received max／min）分辨出最大和最小的信号强度，再搭配时隙 （Slot）的选择，来解决EDC 机制下一开始取得标签的信息和信号强度碰撞问题，如图4所示。

图4 解决EDC机制下取得信号强度最大最小值时阅读器和标签之间碰撞

3 仿真与实验结果

通过上述理论分析，EDC 机制并不是一个一般性单独存在的机制，相反的它必须搭配现今已被提出的主动式标签的防碰撞算法来进行的。本文利用EDC 与现有的防碰撞算法相结合，来增强主动式标签的防碰撞能力。以下实验在Matlab仿真平台进行，对EDC机制融合纯ALOHA、时隙ALOHA 和非坚持CSMA 算法3种现有的防碰撞算法进行定量分析。通过文献 ［1］所知衡量防碰撞算法优劣的主要有两个指标：吞吐量和平均传输时延，其中实验中的吞吐量是单位时间内成功传输到接入点的数据包的总和，平均传输时延是数据包从终端产生到成功的传输到接入点的平均时间间隔。

3.1 吞吐量性能分析

以下实验对有无融合EDC 机制的纯ALOHA、时隙ALOHA 和非坚持CSMA 这3种防碰撞算法进行吞吐量性能比较。从图5 可以看出，在无搭载EDC 机制时，纯ALOHA 算法的最大吞吐量为0.184，仿真结果与理论值吻合的很好。而在存在EDC 机制时，最大吞吐量为0.248，较大的提高了算法的吞吐量。

图5 EDC机制在纯ALOHA 算法中的吞吐量

从图6和图7可以看出，有EDC 机制的算法吞吐量提升效果显著：时隙ALOHA 算法最大吞吐量从原算法的0.368提高到0.465；非坚持CSMA 算法的最大吞吐量提高至0.610。而随着业务量的增加，融合EDC 机制的算法吞吐量下降更为缓慢，因此在可以证明有EDC 机制的算法都能得到进一步提升，吞吐量明显优于原算法。

图6 EDC机制在时隙ALOHA 算法中的吞吐量

3.2 平均传输时延分析

主动式RFID 系统在数据传输产生碰撞后，需要对发生碰撞的数据进行重传，因此还需要考虑算法的传输时延特性。下面对纯ALOHA、时隙ALOHA 和非坚持CSMA这3种算法搭载EDC机制进行平均传输时延分析，仿真结果如图8～图10所示。

图7 EDC机制在非坚持CSMA 算法中的吞吐量

图8 EDC机制在纯ALOHA 算法中的平均传输时延

图9 EDC机制在时隙ALOHA算法中的平均传输时延

从图8和图9的平均传输时延曲线可以看出，有EDC机制的延迟随业务量的增加基本呈线性增加，而无EDC 机制的仿真延迟数据包的曲线随业务量的增加呈指数增加，系统时延性能变得越来越差。由此可知基于EDC 机制的两种算法延时都优于原算法。

图10 EDC机制在非坚持CSMA算法中的平均传输时延

从图10看到，EDC 机制在非坚持CSMA 算法中的平均传输时延在业务量较少时，两者性能上都无差别，传输延迟并不显著。而业务量增加到一定值时，无EDC 机制的原算法延迟曲线急剧上升，性能迅速恶化。因此当系统业务量较大时，基于EDC机制的非坚持CSMA 防碰撞算法的平均传输时延远小于原算法。同时与图8和图9比较可知，基于EDC 的非坚持CSMA 算法比有EDC 机制的ALOHA和时隙ALOHA 算法性能更好，提供了相对较低的延迟。

综合以上3种时延对比图可以看出，有EDC 机制的算法延时都比原算法的延时要低，随业务量的增加延时特性更为显著，因此实验也证明了EDC 机制也有效的提高了主动式RFID 系统识别速度。

4 结束语

本文针对主动式RFID 防碰撞算法的吞吐量低、识别速度慢的问题，提出一种基于能量和距离分簇 （EDC）主动式防碰撞机制。实验通过3种基于EDC 机制防碰撞算法进行了分析与比较，可以得出如下结论：

（1）在系统吞吐量上，基于EDC 机制的算法比原算法的吞吐量均得到提高，证明EDC 机制有效的提高RFID 系统的吞吐量性能。

（2）在平均传输时延上，业务量较多时，基于EDC 机制的算法有相对有较低的时延，系统延时性能较好，使得提高了系统的识别速率。

（3）综上，基于EDC 机制的算法增强了主动式RFID系统的防碰撞性能，提高了主动式RFID 在实际项目应用中的实用性。

［1］Karmakar，Nemai Chandra.Handbook of smart antennas for RFID systems［M］.New York：Wiley，2010.

［2］Klair D K，Chin K W，Raad R.A survey and tutorial of RFID anti－collision protocols［J］.Communications Surveys ＆ Tutorials，IEEE，2010，12 （3）：400－421.

［3］LIU Chenchen.Research on three kinds of mechanism of active RFID tag communication protocols［J］.Coal Technology，2012，31 （4）：166－168（in Chinese）.［刘尘尘.有源RFID 标签通信协议三种机制研究［J］.煤炭技术，2012，31 （4）：166－168.］

［4］SUN Qunying.Research on anti－collision algorithms for dense active RFID system and applications［D］.Hangzhou：Zhejiang University，2011 （in Chinese）.［孙群英.密集环境中有源RFID防冲撞算法的研究及应用［D］.杭州：浙江大学，2011.］

［5］Huang Y H，Huang X，Sun Q.The design of the management system for parking lot based on 2.45GHz active RFID ［C］／／International Conference on Computer Science and Service System.IEEE，2011：850－853.

［6］Ullah S，Alsalih W，Alsehaim A，et al.A review of tags anticollision and localization protocols in RFID networks［J］.Journal of Medical Systems，2012，36 （6）：4037－4050.

［7］SHAN Jianfeng，CHEN Ming，XIE Jianbing.Research on RFID tag anti－collision technology base on aloha algorithm ［J］.Journal of Nanjing University of Posts and Telecommunications （Natural Science），2013，33 （1）：56－61 （in Chinese）. ［单剑锋，陈明，谢建兵.基于ALOHA算法的RFID防碰撞技术研究［J］.南京邮电大学学报（自然科学版），2013，33 （1）：56－61.］

［8］Wang H，Pei C，Su B.Collision－free arbitration protocol for active RFID systems［J］.Journal of Communications and Networks，2012，14 （1）：34－39.

［9］SHU Yuanzhong，TIAN Lei，ZHANG Li.Time slots ALOHA anti－collision algorithm based on queuing theory［J］.Computer Engineering and Design，2013，34 （7）：2632－2636 （in Chinese）.［舒远仲，田蕾，张丽.基于排队理论的时隙ALOHA 防碰撞算法［J］.计算机工程与设计，2013，34 （7）：2632－2636.］

［10］Nilsson B，Bengtsson L，Svensson B.An application dependent medium access protocol for active RFID using dynamic tuning of the back－off algorithm ［C］／／IEEE International Conference on RFID.IEEE，2009：72－79.

［11］Ali K，Hassanein H，Tana A E M.RFID anti－collision protocol for dense passive tag environments［C］／／32nd IEEE Conference on Local Computer Networks.IEEE，2007：819－824.

［12］CHUNG S H，Dong－Chul S.Performance improvement of tag collection in active RFID systems based on ISO／IEC 18000－7［J］.IEICE Transactions on Communications，2011，94 （7）：2062－2073.