一种标签防冲突算法设计

周 晓，曹美玲，李 杰，边裕挺

（1.浙江工业大学 信息工程学院，浙江 杭州 310032；2.浙江工业大学 计算机科学与技术学院，浙江 杭州 310032）

一种标签防冲突算法设计

周 晓1，曹美玲2，李 杰1，边裕挺1

（1.浙江工业大学 信息工程学院，浙江 杭州 310032；2.浙江工业大学 计算机科学与技术学院，浙江 杭州 310032）

针对RFID系统中，多个标签使用共享信道与读写器通信引起的标签信号冲突问题，提出了具有捎带检测技术的标签防冲突算法SRPD-ABS，能够实现多标签信号的读取，完成多目标识别.SRPD-ABS算法基于ABS算法思想，采用捎带检测技术，不但能够避免滞留标签之间的冲突，还能避免新到标签和滞留标签的冲突，减少空闲时隙的产生，从而缩短识别延迟.通过仿真，和ABS算法对比发现，SRPD-ABS算法具有更好的识别性能.

防冲突算法；RFID；智能交通；离开率；到达率

射频识别（Radio frequency identification，RFID）技术是一种自动识别技术，广泛应用在智能交通、物流、零售及医疗等领域，是物联网发展的重要技术之一.典型的RFID系统，通常包括一个读写器和若干个有唯一ID的标签.读写器和标签采用无线射频的方式通信，通过读取标签ID，获得标签数据信息［1］.通信时，在上行链路，多个标签共享同一条通信信道，可能会造成信道访问冲突，因此在通信过程中，需要有高效的防冲突算法，减少冲突，降低误读率和漏读率，提高系统的性能.

现有的标签防冲突算法采用时分多址（Time division multiple access，TDMA）思想，分为两大类，分别是基于Aloha的防冲突算法和基于二进制树的防冲突算法.基于Aloha的防冲突算法有纯Aloha［2］、时 隙 Aloha（Slotted aloha，SA）［2－3］、帧 时 隙Aloha（Frame slotted aloha，FSA）［3］和动态帧时隙Aloha（Dynamic framed slotted aloha，DFSA）［3］.基于 Aloha算法能够避免部分冲突，提高读写器的工作效率，但是随着标签数量的增加，该算法存在不稳定性，容易引起标签饥饿等问题，因此以二进制树为基础的算法获取了更好的应用.典型基于二进制树的算法有基本二进制树算法（Binary tree，BT）［4］、查询二进制树算法（Query tree，QT）［5］、动态二进制树分裂算法（Adaptive binary splitting，ABS）［6－7］.

在RFID技术的应用中，通常读写器需要重复识别标签，并且读写器可读范围内标签的数量是变化的.在读写过程中，有些标签存在于当前读写周期，但不存在于下个读写周期，被称为离开标签；有些标签既存在于当前读写周期又存在于下个读写周期，叫做滞留标签；只存在于下个读写周期的标签被称为新到标签.Jihoon Myung和 Wonjun Lee提出的ABS算法能够完全避免滞留标签之间的冲突，但是不能避免滞留标签和新到标签的冲突，当离开标签较多时，会造成很多空闲时隙.因此笔者基于ABS算法思想，提出了具有捎带检测功能的标签防冲突算法（Self regulation piggyback detect ABS，SRPD-ABS），不但能够避免滞留标签的冲突，而且能够避免滞留标签和新到标签的冲突，还能够利用捎带检测技术，提前对下个时隙进行调整，在不增加冲突时隙的同时，能够更多的减少空闲时隙，缩短识别延迟，提高识别效率.

1 SRPD-ABS算法设计

ABS算法在基于二进制树的算法中，有较好的防冲突性能，但是该算法只能避免滞留标签之间的冲突，不能避免滞留标签和新到标签的冲突，并且离开标签过多时，会造成更多空闲时隙.笔者提出的SRPD-ABS算法不但能够避免滞留标签和新到标签的冲突，而且能够利用捎带检测技术，检测下个时隙是不是有标签响应.所谓捎带检测指在当前时隙，读写器除读取本时隙要读取的标签的ID外，还能根据是否收到下个时隙要发送ID的标签的“存在”信号，向标签发送一个指令，标签看到指令，如果下个时隙没有标签发送ID，新到达的标签自动进行调整，满足条件的标签发送ID，这样能够避免部分空闲时隙，提高信道的利用率.算法具体思想如下：第一个周期，SRPD-ABS和ABS执行过程相同.在Ci（i＝2，…，n）周期，每个标签有三个变量 PSC，ASC和TSCi－1，PSC表示在当前周期已经识别的标签的个数；ASC指示标签在哪个时隙发送自己的ID，TSCi－1标识上个周期识别结束时的TSC值.读写器有三个变量PSC，TSC和TSCi－1.读写器的PSC和TSCi－1变量定义同标签，并且有相同的值，TSC用来标识最大的ASC值.按照文献［8］的标签估计策略，估计新到标签的个数，新到标签的个数用New-count表示，新到标签的ASC为1～New-count中一个随机数加TSC值.滞留标签保留上个周期的ASC值.

对读写器回馈信号作如下定义［9］：

I，0：空闲时隙，且没有未被识别的新到标签.

I，1：空闲时隙，且有未被识别的新到标签.

C：冲突时隙，有两个或两个以上的标签响应.

R，0：当前时隙可读，下个时隙没有标签响应.

R，1：当前时隙可读，下个时隙有标签响应.

识别过程中ASC＝PSC的标签发送ID，ASC＝PSC＋1的标签发送“存在”信号.读写器检测到标签的信号，根据标签信号发出回馈信号，标签根据回馈信号，调整PSC和ASC的过程如下：

I，0：如果标签的ASC＞PSC，ASC＝ASC－1.

I，1：如果标签的 ASC＝TSCi－1＋1，ASC＝PSC；如果标签的ASC＞TSCi－1＋1，ASC＝ASC－1.

C：标签随机选择0或1，如果标签选择1，当PSC≤TSCi－1时，陷入冲突的标签 ASC＝TSCi－1＋1，没有陷入冲突且ASC＞TSCi－1＋1的标签，ASC＝ASC＋1；当PSC＞TSCi－1时，如果标签 ASC≥PSC，标签 ASC＝ASC＋1.如果标签选择0，ASC不变.

R，0：标签的识别个数计数器PSC＝PSC＋1，当PSC≤TSC时，如果 ASC＝TSCi－1＋1，ASC＝PSC，如果ASC＞TSCi－1＋1，ASC＝ASC－1.

R，1：标签的识别个数计数器PSC＝PSC＋1.

读写器操作部分，当PSC≤TSC时，读写器收到标签的信号，判断当前状态.如果有两个或两个以上标签发送ID，发生冲突，读写器发送回馈信号“C”；如果只有一个标签发送ID，读写器接收标签ID，PSC＝PSC＋1，如果PSC＞TSCi－1＋1，TSC＝TSC＋1，读写器再检测有没有标签发送“存在”信号，如果有，读写器发送回馈“R，1”；否则，发送“R，0”.如果没有标签发送ID，当空闲时，如果有新到没被识别的标签，读写器发送“I，1”，如果新到标签都已识别完，读写器发送“I，0”，并令TSC－1.

2 算法性能分析

为了进一步研究SRPD-ABS算法性能，本节对ABS算法和SRPD-ABS算法识别延迟进行分析［9］.

2.1 ABS算法

假设在C1识别周期，有n个标签，DABS（C1）为C1周期的总的识别延迟，这个周期的识别延迟和BT算法相同，有

式中：DC，DR，DI分别为冲突时隙、可读时隙和空闲时隙数，并且DR＝n，有

标签的识别过程是一个马尔可夫过程［10］，因此在Ci（i＝2，…，n）周期，需要有上个周期的识别结果作为依据.在Ci（i＝2，…，n）周期，所有要识别的标签分为两类，滞留标签和新到标签，这两类标签的个数是影响识别延迟的重要参数，Ci周期的识别延迟不能简单用公式（2）来表示.文献［6－7］中，假设DABS（Ci｜Ci－1）为Ci周期总的识别延迟，离开的标签为β个，新到的标签为α个，则有

2.2 SRPD-ABS算法

在C1周期，SRPD-ABS算法和ABS算法具有相同的识别延迟，下面对Ci（i＝2，…，n）周期进行分析.

在Ci周期，假设DSRPD－ABS（Ci｜Ci－1）为Ci周期总的识别延迟，离开标签为β个，新到标签为α个，有

证明：Ci－1周期识别结束，因为有β离开标签，那么就会有n－β滞留标签，因此首先需要n－β可读时隙.当α＞β时，新到标签中，有β个填补离开标签所致的空闲时隙，剩下的α－β个新到标签的识别延迟等于采用ABS算法的识别延迟.当α＜β时，所有新到标签都在离开标签形成的空闲时隙完成，另外还会有β－α个空闲时隙.两种情况下，标签选择识别时隙均服从二项分布，因此得到公式（4）.

2.3 仿真结果分析

下面通过算法仿真，对SRPD-ABS算法和ABS算法进行分析比较.RFID标签防碰撞算法通常把碰撞时隙、空闲时隙和可读时隙作为重要的衡量指标.在标签的识别过程中，到达率和离开率是影响识别时隙重要参数.

图1以离开率和到达率作为变量，模拟两个变量对SRPD-ABS算法和ABS算法的识别延迟的影响.图1中曲面2表示SRPD-ABS算法的识别延迟，曲面1表示ABS算法的识别延迟.假设上个周期识别500个标签，由图1可以知，离开率在0.64～1之间时，ABS在部分区域略胜一筹，离开率在0～0.64之间时，SRPDABS远远好于ABS.到达率和识别延迟之间呈线性关系，随着到达率的增加，识别延迟也在增加.

图1 离开率和到达率对识别延迟的影响（n＝500）Fig.1 The effection on identification delay of leaving ratio and arriving ratio（n＝500）

3 结 论

在RFID系统中，由于多个标签同时与读写器通信引起冲突，导致更大的识别延迟，笔者基于ABS算法的基本思想，提出其改进算法SRPD-ABS算法，利用捎带检测技术，根据前一个周期的识别结果，提前一个时隙检测下个时隙标签的响应情况，如果发现空闲，可以提前做出调整，避免更多空闲时隙的产生.根据仿真结果，模拟实际应用环境，SRPDABS算法产生比ABS算法少的冲突时隙和空闲时隙，有效减少识别延迟，提高识别效率.

［1］FINKENZELLER K.射频识别（RFID）技术［M］.陈大才，译.北京：电子工业出版社，2001.

［2］TAO Cheng，LI Jin.Analysis and simulation of RFID anti-collision algorithms［C］／／International Conference on Advanced Communication Technology.New York：IEEE Press，2007：697-701.

［3］SHIH D H，SUN P L，YEN D C.Taxonomy and survey of RFID anti-collision protocols［J］.Computer Communications，2006，29（11）：2150-2166.

［4］CHEN W C，HORNG S J，FAN Ping-zhi.An enhanced anticollision algorithm in RFID based on counter and stack［C］／／Second International Conference on Systems and Networks Communications.New York：IEEE Press，2007：21-24.

［5］WANG T P.Enhanced binary search with cut-through operation for anti-collision in RFID systems［J］.IEEE Communication Letters，2006，10（4）：236-238.

［6］MYUNG J，LEE W J.Adaptive binary splitting for efficient RFID tag anti-collision［J］.IEEE Communication Letters，2006，10（3）：144-146.

［7］LAI Y C，LIN C C.Two blocking algorithms on adaptive binary splitting：single and pair resolutions for RFID tag identi？cation［J］.IEEE／ACM Transactions on Networking，2009，17（3）：962-975.

［8］EOM J，LEE T J.Frame-slotted Aloha with estimation by pilot frame and identification by binary selection for RFID anti-collision［C］／／International Symposium on Communications and Information Technologies.New York：IEEE Press，2007：1027-1031.

［9］CAO Mei-ling，ZHOU Xiao，ZHU Yi-hua.An anti-collision algorithm for RFID tags based on adaptive binary splitting［C］／／International Conference on Computer and Electrical Engineering.New York：IEEE Press，2010：307-311.

［10］VOGT H.Efficient object identification with passive RFID tags［C］／／International Conference on Systems，Man and Cybernetics.New York：IEEE Press，2002：98-113.

A design of tag anti-collision algorithm

ZHOU Xiao1，CAO Mei-ling2，LI Jie1，BIAN Yu-ting1
（1.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310032，China；2.College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310032，China）

To solve the problem of signal collision，which is caused by multiple labels using a shared channel with the tag reader communication signal，in RFID （Radio Frequency Identification）system，a new tag anti-collision algorithm—SRPD-ABS（Self Regulation Piggyback Detect ABS）is proposed.It can read multi-tag signal and identify multi targets from them.SRPD-ABS algorithm is proposed based on ABS （Adaptive Binary Splitting）.The piggyback detect technique is used in it.It can not only avoid conflict between the staying tags，but also avoid collision between the new arriving tags and the staying tags.It can also reduce the idle time slot and shorten the identification delay.Through simulation，SRPD-ABS has a better performance than ABS.

anti-collision algorithm；RFID；intelligent transportation；leaving ratio；arriving ratio

TN911

A

1006-4303（2011）06-0679-04

2010-09-25

浙江省自然科学基金资助项目（Y107618）；浙江省科技厅资助项目（2008C21144）

周 晓（1971—），男，浙江永康人，副教授，博士，研究方向为自组织网络与智能交通，E-mail：zx＠zjut.edu.cn.

（

陈石平）