基于物联网的RFID自适应多叉树防碰撞算法研究

张 琴(福州职业技术学院计算机系，福建福州 350108)

基于物联网的RFID自适应多叉树防碰撞算法研究

张 琴
(福州职业技术学院计算机系，福建福州 350108)

如何设计高效实用的防碰撞算法是RFID系统实现中亟待解决的关键技术问题。本文对常见的多标签防碰撞算法的优缺点进行分析，针对常见的二叉树防碰撞算法存在的通信量大、搜索次数过多等问题，提出一种自适应分裂树的防碰撞算法。仿真结果表明，相对于基本二进制树防碰撞算法，本文算法的系统吞吐率可以保持在50%以上，搜索次数和数据通信量也大大降低，非常适用于大量标签识别的物联网。

物联网；RFID；Manchester编码；防碰撞算法

物联网(Internert of Things)是利用射频识别、传感器等技术，按约定的协议将所有物品与互联网连接起来，实现智能化识别和管理的下一代信息网络，广泛应用于工商业、物流等领域[1]。RFID(Radio Frequency Identification)是一种非接触的无线自动识别和获取信息的技术，它与ZigBee技术、LTE技术和云计算并称为物联网四大关键性应用技术[2]。一般来说RFID系统由阅读器和标签两部分组成，系统运行时，有多个标签处于阅读器的作用范围内，在同一时刻这些标签向阅读器回复信息时，将导致所传输信息相互干扰，这种干扰称为“碰撞”，标签碰撞会对阅读器识别标签和对标签进行读写操作产生不利影响。信息碰撞问题是影响RFID读取效率的重要原因之一。因此设计高效的防碰撞算法是众多学者研究的热点问题。

针对标签识别过程中的碰撞问题，比较常用的解决技术有空分多址(SDMA)、时分多址(TDMA)、频分多址(CDMA)和码分多址(CDMA)等，其中时分多址是最常用的技术[3]。基于TDMA技术的防碰撞算法主要有两类：一是ALOHA类算法，二是基于二进制树机制的防碰撞算法。ALOHA算法检测碰撞的过程完全依赖于阅读器发送的命令，操作简单、成本低，缺点是ALOHA算法发生碰撞的概率很高，尤其是当标签数目较多的时候，该算法性能急剧下降。针对纯ALOHA算法的种种局限性，一些改进的算法，如时隙ALOHA算法、帧时隙ALOHA算法、分组时隙ALOHA算法和动态帧时隙ALOHA算法陆续出现[4]。但是，基于ALOHA机制的防碰撞算法的时隙具有随机性，是不确定的算法，都可能出现一些标签很长一段时间都不能被识别的情况，即“标签饿死”。

基于二进制树机制的算法则是确定型的，是一种阅读器控制算法。这类算法通过将大量待识别标签划分到不同子集，直到某一个子集中出现可识别的标签，重复此类操作，逐步完成全部标签的识别[5]。基于二进制树的搜索算法每一次仅产生两个分裂子集，分裂速度慢，搜索次数多，如果标签数量过大，会存在大量碰撞时隙导致系统效率低。而基于查询树的算法由于需要进行标签匹配相关的操作而需要花费较大通信和处理成本。

针对上述一系列算法存在的缺陷，本文提出了一种改进的自适应分裂树防碰撞算法，根据碰撞位数，自适应选择分裂树，提高搜索效率，减少标签与阅读器之间的通信量。同时，定义状态计数器并且运用矩阵思想对碰撞位进行处理，减少空闲时隙。最后通过MATLAB仿真对算法性能进行比较和分析。

1 算法约定

1.1 算法通信方式

为了准确地确定碰撞位，本文中标签与阅读器之间的数据通信采用曼彻斯特编码。该编码是采用电平的改变来表示数值，其中上升沿编码为逻辑0，下降沿编码为逻辑1。每一位的中间有一跳变，若无状态跳变，则视为非法数据[6]。当多个同时返回的标签编码数位有不同之值时，碰撞位上的上升沿和下降沿就会相互抵消，以至无状态跳变，阅读器就能够很准确地检测出碰撞位。假设有2个RFID标签，其EPC编码(假定为8位)分别为tag1∶10111001和tag2∶10100001，当2个标签同时向阅读器发送自己的EPC编码信息时，利用Manchester编码检测碰撞位置的示意图如图1所示。

图1 Manchester编码碰撞位识别原理示意图

1.2 算法命令

1.2.1 查询命令

CALL(NULL)：首次查询时阅读器要求其作用范围的所有标签进行应答，将自身的EPC值发送给阅读器。

CALL(HP，HPValue，LP，LPvalue)：参数HP、LP分别表示检测到碰撞的最高位和最低位，当阅读器检测到碰撞位数大于2时发出此命令，要求标签返回其第HP-1至LP-1之间的数据。

CALL(HP，HPValue)：参数HP为检测到碰撞的最高位，HPValue取值为0或1，是最高碰撞位的取值。

1.2.2 标签休眠

SLEEP(epc，m)：如果标签的epc码与SLEEP命令中的epc码前m位相等，那么这些标签进入睡眠状态，不再响应阅读器的CALL命令。如果需要重新激活标签，则必须使该标签离开阅读器作用范围后重新进入。

1.2.3 选择命令

SELECT：将标签的epc编码作为参数，表示某一标签被选中，并作为执行读出或写入等其它命令的开关。

1.2.4 读写数据命令

ReadData：应答了SELECT命令的标签将其存储的数据发送给阅读器。

2 算法原理及流程

阅读器发送CALL(NULL)命令，其作用范围内的所有电子标签向阅读器传回其自身的EPC编码信息，阅读器接收到反馈信息时，检测回传标签信息的碰撞情况，如果检测到碰撞发生，标签将根据碰撞位连续的情况自适应选择二叉树或四叉树分组。如果检测到自最高碰撞位起连续2位及以上的EPC编码碰撞，则由状态计数器statue的值(1，2，3，4)确定HP、LP的值(00，01，10，11)，阅读器发送命令CALL(HP，HPValue，LP，LPvalue)；标签在回传信息时，由于标签编码的HP之前和LP之后的信息是已知的，所以标签只要回传最高碰撞位HP与最低碰撞位LP之间的数据，从而降低了电子标签和阅读器之间的通信量。算法的流程图如图2所示。

图2 自适应多叉树防碰撞算法流程图

具体的程序实现如下：

矩阵sHr，sLr，str为空，标志状态位statue=1;

//初始化操作。sHr(存储最高碰撞位)，sLr(存储最低碰撞位)，str(存储当前状态计数器statue的值)

CALL(NULL);

If(碰撞位数==0) 识别标签并进行操作，算法结束;

If(碰撞位数==1) 碰撞位赋值0、1，识别标签并进行操作，算法结束;

If(碰撞位数==2) CALL(HP,HPValue)进行二叉树查询;

Else

While(碰撞位数>2)

{记录HP,LP,;

While(statue<=4)

{CALL(HP,HPValue,LP,LPvalue);

If(碰撞位数==1) 碰撞位赋值0、1，识别标签并进行操作

If(碰撞位数==2) CALL(HP,HPValue)进行二叉树查询;

statue++;

If(sHr为空)算法结束;

else Pop sHr(HP),Pop sLr(LP),Pop str(statue);

If(碰撞位数>2) break;}

Push HP into sHr, Push LP into sLr, Push statue into str;}

3 算法仿真及结果分析

为了验证本文中自适应多叉树防碰撞算法的有效性，下面利用Matlab软件对该算法的查询次数和吞吐量进行仿真实验，比较的算法为基本二进制树防碰撞算法，取标签编码位数为8，仿真30次取平均值。两种算法的搜索次数与标签数目的关系如图3所示，吞吐量随标签数目增多变化情况如图4所示。

由图3可知，EPG编码位数为8的条件下，当标签数目比较少时，两种算法搜索次数差别不太大，随着标签数目的增多，空闲时隙情况逐渐减少，本文中算法的优势越来越明显。基本的二进制树防碰撞算法搜索次数随标签数目增加接近线性增长，而本文中算法当标签数目增加到200之后搜索次数基本上处于稳定状态，原因在于自适应多叉树算法可以降低查询树体复杂度，简化搜索流程，进而使查询次数大大减少。

图3 两种算法搜索次数对比图

图4 两种算法吞吐量对比图

由图4可知，EPG编码位数为8的条件下，随着标签数量的增加，基本的二进制树防碰撞算法吞吐量维持在10%～20%之间，而自适应多叉树算法吞吐量明显高于比较算法，吞吐量基本上都高于50%。究其原因，一方面本文算法能进行自适应搜索，避免搜索树体过大出现过多无效搜索，阅读器每一次的查询命令都有有效应答；另一方面如果连续碰撞位数等于1，算法能一次性识别两个标签。所以本文提出的算法可以达到很高的吞吐量。

4 结语

针对传统的二进制树防碰撞算法存在的通信量大、搜索树体庞大导致存在大量无效搜索等问题，本文提出了一种新颖的自适应分裂树防碰撞算法，该算法在二进制树搜索算法的基础上根据碰撞位数，自适应选择分裂树，提高搜索效率，减少标签与阅读器之间的通信量。同时定义状态计数器并且运用矩阵思想对碰撞位进行处理，减少空闲时隙。最后通过实验证明了本算法相较于常见的二进制树算法在阅读器问询次数、系统搜索次数、阅读器与标签之间的数据通信量等方面具有较大的优越性，较大幅度地提高了RFID系统多标签同时识别的性能。

[1]Finkenzeller.RFID handbook fundamentals and applications in contact-less smart cards and identification[M].John Wiley and Sons Ltd,2003.

[2]宁焕生.RFID重大工程与国家物联网[M].北京:机械工业出版社,2011.

[3]谢振华,赖声礼,陈鹏.RFID技术和防碰撞算法[J].计算机工程与应用,2007(6):223-230.

[4]单剑锋,陈明,谢建兵.基于ALOHA算法的RFID防碰撞技术研究[J].南京邮电大学学报,2013(1):56-61.

[5]丁治国,郭立,朱学永,等.基于二叉树分解的自适应防碰撞算法[J].电子与信息学报,2009(6):1395-1399.

[6]Yinghua Cui,Yuping Zhao.Performance evaluation of a multi-branch tree algorithm in RFID[J].Communications, IEEE Transaction on Journals & Magazines,2010(58):1356-1364.

Research of RFID Adaptive Multi-tree Anti-collision Algorithm Based on the Internet of Things

ZHANG Qin

(Fuzhou Polytechnic, Fuzhou Fujian 350108,China)

How to design efficient and practical anti-collision algorithm is the key technology to be solved of RFID system implementation. In this paper, the advantages and disadvantages of the common multi-tag anti-collision algorithm are analyzed firstly. In view of problems in the binary tree anti-collision algorithm more or less: a large amount of communication, abundant total time slot, this paper proposes a adaptive multi-tree anti-collision algorithm. The simulation results show that the system throughput can be maintained at more than 50%, search number and data traffic are also greatly reduced compared with the basic binary anti collision algorithm. The algorithm is suitable for a large number of label identification of the Internet of things.

Internet of Things; RFID；Manchester encoding; anti-collision algorithm

2017-01-14

张 琴(1986- )，女，讲师，从事计算机软件应用开发、信息处理与数据挖掘研究。

TP301.6

A

2095-7602(2017)06-0023-05