一种改进的动态帧时隙ALOHA算法

彭　赟

(常州信息职业技术学院电子与电气工程学院　江苏常州　213164)



一种改进的动态帧时隙ALOHA算法

彭赟

(常州信息职业技术学院电子与电气工程学院江苏常州213164)

摘要：随着射频识别(RFID)的广泛应用，防碰撞算法性能的优劣成为制约其进一步发展的关键因素。以原始动态帧时隙ALOHA算法为基础，结合一种更加精确的标签数目估算法，从而动态地设置下一帧的时隙数，以改善防碰撞性能，MATLAB仿真结果表明该算法能够显著提高标签识别效率。

关键词：射频识别； 防碰撞； ALOHA

0引言

RFID[1](Radio Frequency Identification)是一种利用无线射频信号获得特定对象数据的自动识别技术，由于其具有识别速度快、无需人工干预等优点，因而在库存管理、考勤、身份识别等领域得到广泛的应用，被业界公认为物联网的四大核心技术之一。

当读卡器识别范围内存在大量待识别电子标签时，不可避免地发生信息碰撞，该问题严重制约着RFID更为广泛的发展与应用。因此，需要一种可靠的算法用于解决多标签识别碰撞问题。目前，主要存在二进制搜索法及ALOHA两类算法[2]。由于ALOHA算法具有简单、便于实现等优点，因而得到了广泛的应用。ALOHA算法的发展分为四个阶段：纯ALOHA、时隙ALOHA、帧时隙ALOHA及动态帧时隙ALOHA。待识别标签数估计的精确度是动态帧时隙ALOHA算法的关键，当前存在一些较可靠的标签数目估算法，例如Schoute[3]标签估算法及Vogt[4]等提出的一些算法。然而，Schoute标签估算法为：未识别的标签数=碰撞时隙数*每个碰撞时隙中碰撞标签个数的数学期望值，该数学期望一般固定为2.39，该算法具有实现简单、计算量较小、系统识别效率得到提高等优点，然而，当待识别标签达到一定数量时，估算值与实际值误差较大。此外，Vogt等人提出的标签数目估算法，具有计算量大且对概率特别敏感等缺点。本文以动态帧时隙ALOHA算法为基础，结合一种简单且准确的标签估计算法，从而大幅度提高识别系统效率。

1RFID防碰撞分析

从本质上来说射频识别中电子标签信息碰撞问题是多址接入问题，当读卡器识别范围内存在大量待识别标签时，碰撞问题将更加严重，为了有效地解决该问题，一系列防碰撞算法应运而生。其中，使用较为广泛的为ALOHA类算法，其发展历程共经历了四个阶段：纯ALOHA、时隙ALOHA、帧时隙ALOHA及动态帧时隙ALOHA。

1.1纯ALOHA算法

纯ALOHA算法[5]的思想是只要电子标签有数据要发送，就尽管让其发送。这个过程虽会出现信息冲突，但由于广播信道具有反馈性，当发送方(电子标签)知道数据帧遭到破坏，那么在随机长的一段时间后将再次发送数据，如果发送过程中未发生冲突则表明数据传输成功，电子标签将进入休眠状态，重复上述步骤直到读卡器将所有电子标签都成功识别。ALOHA算法思想简单实用，其最大吞吐率可达18.4%，如图1中虚线段所表示。

图1　ALOHA和时隙ALOHA算法比较图

1.2时隙ALOHA算法

纯ALOHA算法中，假设电子标签传递一次数据所消耗的时间为T，电子标签发送数据时刻为0，则在(-T,+T)区间内不能有其他标签发送数据，否则都会引起数据冲突。因此，纯ALOHA算法的碰撞区间长为2T，若将时间划分为若干个时隙，所有电子标签只能在时隙的开始时刻发送数据而非任意时刻，从而可以将碰撞区间长度减小为T，系统的吞吐率将提高一倍最高可达36.8%，这便是时隙ALOHA算法[5]如图1实线所示。

1.3帧时隙ALOHA算法

观察图1可以发现随着读卡器识别范围内待识别电子标签数量的增加，纯ALOHA算法与时隙ALOHA算法性能急剧下降。于是有研究人员提出帧时隙ALOHA算法[6]，其思想是：将若干时隙打包成一个帧，待识别电子标签随机选择帧时隙中一个特定的时隙号，并在该时隙内与读卡器进行通信，电子标签同样只能在时隙的开始时刻发送数据，图2为分别取帧长64、128及256时，识别0～500个标签所需消耗的总时隙数的仿真图。

图2　不同长度帧时隙ALOHA算法

1.4动态帧时隙ALOHA算法

观察图2发现，当待识别标签数较少时，帧时隙数为64的算法相对于帧长为128及256的算法效率略高，然而随着待识别电子标签数的大幅增加，帧时隙数为64的算法性能急剧下降，而帧时隙数为256则优势显著。针对该问题，有学者提出了动态帧时隙ALOHA算法[7]，根据当前识别过程中的碰撞时隙比例与空时隙比例的取值大小，动态地调整下一帧时隙长度。其工作流程如下所示：

①根据实际应用状况设定帧的初始帧时隙长度为F。

②读卡器发送一帧时隙数为F的清点指令，等待标签应答，读写器根据标签的回应状况，分别统计出空时隙数、碰撞时隙数及成功识别标签时隙数。

③如果碰撞时隙数为0，则结束识别过程，否则计算空时隙、碰撞时隙及成功识别时隙各自占总时隙数的百分比，如果碰撞时隙数占总时隙数的比例大于70%，则将下一轮读卡器发送的帧时隙数加倍；如果空时隙数占总时隙数的比例大于30%，则将下一轮读卡器发送帧时隙数减半；否则下一轮读卡器发送的时隙数不变。

④调整帧的长度，转入步骤②进入新一轮的读卡周期直至完成所有电子标签的识别。

2改进的动态帧时隙ALOHA算法

研究表明当帧长与待识别电子标签数相同时，系统的吞吐率可保持为最大值36.8%。而原始动态帧时隙ALOHA算法，仅根据上轮识别后的统计数据，将下一帧时隙数做乘2、除2或不变等三种操作，无法达到理想的识别效率。如下为本文所示一种精确的标签估计法，通过该估算法能够较为精确地估出待识别标签数，从而将下一帧时隙数设为算法估算的输出值，能够大幅度提高系统的效率。

假设帧的时隙数L等于标签数n与一个合适因子β的乘积，可以得到表达式(1)

(1)

发生碰撞后，假设产生碰撞后未识别的标签数为γ*sc。那么backlog(下一帧时隙数)通过公式(2)获得

(2)

式(2)中ss和sc分别表示成功识别的时隙数和发生碰撞的时隙数。n个标签中有γ个标签占据同一个时隙的概率接近于二项式分布，如表达式(3)所示：

(3)

若帧的大小L足够大，则式(3)接近于泊松分布，当γ=0，则在一个时隙中无标签占有的概率为表达式(4)

(4)

在式(3)中，当γ=1时，只有一个标签占据一个时隙时得到如下表达式：

(5)

因此表达式(2)左半部分接近于

(6)

其中β=L/n为式(1)中的β，式(2)中的右边为：

(7)

联立式(2)，(6)，(7)可以得到：

(8)

ss和sc能够在帧长为L的帧中测得。β能够

通过式(1)，(2)和(8)获得。

(9)

那么backlog估算为：

(10)

然而通过式(8)很难找到求解β和γ的解法。因此，提出一种用于求解β和γ的迭代算法。使βk和γk分别为β和γ的第k次迭代值。首先令x=1/(β1)，并且假设β→∞(x→0)，那么γ1可通过式(8)利用罗必塔法则求得：

(11)

式(1)和(2)表明，β2能够通过γ1推断。

(12)

因为变量L，Sc，Ss都是有限常量。因此可以通过β2得到γ2：

(13)

式(8)表明变量γ和β都呈现反向比例关系，如图3所示。并可以因为β2<β1，β3<β2，所以γ3<γ2，从而可以得到迭代算法。

(14)

(15)

那么集合{βk}满足。

(16)

因为{βk}是有界单调递减的序列，有一个极限值。因此，序列{βk}转成有限值可以使用迭代式(14)，(15)及β1=∞，γ1=2开始寻找第k*次迭代式γk*的值。当满足下列条件的阈值∈threshold时：

(17)

那么backlog(下一帧的帧长)可以通过以下式(18)求得：

(18)

式(14)和(15)表明选择一个合适的阈值∈threshold时可以迅速获合适的γ，并通过式(18)求得下一轮合适的帧长。

图3　β和γ的关系

3仿真结果分析

图4为MATLAB对原始动态帧时隙ALOHA(DFSA)算法与改进算法取100次平均值进行比较得到的结果，改进算法中阈值∈threshold设为0.001。两算法初始时刻帧时隙数均为64，待识别标签数在0～1 000之间变化，可以发现当识别区域内只有少量待识别电子标签(0～200)时，两种算法性能相当。随着识别区域内的电子标签数的不断递增，改进算法效率优势逐渐体现出来，当电子标签数在600左右时，效率提高了近25%；当电子标签数为1 000时，改进算法消耗的时隙数为原算法的52%，效率提高了近一倍。

图4　仿真结果

4结束语

本文将一种精确的标签估算法与动态帧时隙ALOHA算法相结合，以提高RFID系统的识别效率，并从公式推导及MATLAB仿真两方面，验证了算法的科学性及有效性。但需要进一步探索性能优良的防碰撞算法，以促进RFID更广泛地应用与发展，为人们的生活带来更多的方便。

参考文献：

[1]王鑫，贾庆轩，高欣.基于位图构建的RFID自适应N树防碰撞算法[J]. 上海交通大学学报，2015, 49(2): 150-157.

[2]邓晓.一种新的RFID标签数目估计方法[J].计算机工程与应用，2012, 48(5): 142-144.

[3]Schoute, F. Dynamic Frame Length ALOHA[J].Communications, IEEE Transactionson, 1983, 31(4): 565-568.

[4]H Vogt.Efficient object identification with passive RFID tags [J].in Proc. International Conference on Pervasive Computing，2012, 28(5): 98-113.

[5]Chen W T, Lin G H. An efficient anti-collision method for tag identification in a RFID system [J]. IEICE Trans Commun，2006, 89(12): 3389-3392.

[6]J R. Cha, J H Kim. Novel anti-collision algorithms for fast object identification in RFID system [J]. in Proc. International Conference on Parallel and Distributed Systems, 2005, 2(5): 63-67.

[7]Vinod Nam, Lixin Gao. Energy-Aware Tag Anti-collision Protocols for RFID System [J]. IEEE Transactions on Mobile Computing, 2012, 9(1): 44-59.

收稿日期：2016-04-20

作者简介：彭赟(1987-)，男，硕士，主要研究方向：嵌入式开发、射频通信

中图分类号：TP 391.44

文献标志码：A

文章编号：1672-2434(2016)03-0027-04

An Improved Dynamic Frame Slotted ALOHA Algorithm

PENG Yun

(School of Electronic and Electrical Engineering, Changzhou College of Information Technology, Changzhou 213614, China)

Abstract：With the wide use of RFID, the drawback of anti-collision algorithm is a key factor which has restricted its development. Based on the dynamic frame slot ALOHA algorithm, this paper proposes an accurate tag estimation algorithm. The simulation results show that the improved algorithm can significantly improve the efficiency of system identification.

Key words：RFID; anti-collision; ALOHA