一种新型去除空闲和减少碰撞的帧时隙ALOHA防碰撞算法

邓红卫，林紫玉，姚铭，李民

(1.衡阳师范学院 计算机科学与技术学院，湖南 衡阳 421002；2.智能信息处理与应用湖南省重点实验室，湖南 衡阳 421002)

在动态RFID系统中，标签经过长度有限的识别区域，识别时间受限，标签碰撞及丢失问题不可避免。文献[1]提出一种基于比特查询的查询方法，通过用比特串取代标签的ID序列，充分利用碰撞比特信息，提高标签识别效率，但由于标签估计数的不确定性，仍然存在浪费空闲时隙和标签碰撞问题。文献[2]提出去空闲时隙ALOHA算法(CIFSA)，在预约思想的基础上，根据预约序列，标签修改自身预定义时隙，屏蔽该帧中的空闲时隙，只有成功和碰撞两种时隙，缩短每一帧的帧长，提高标签识别效率，但还是没有解决多标签间的碰撞问题，标签识别效率仍然比较低。

针对动态RFID系统中标签防碰撞问题，本文提出一种新型去除空闲和减少碰撞的帧时隙ALOHA防碰撞算法。算法在去空闲时隙算法基础上，通过碰撞调整机制增加成功时隙数。核心思想就是区分碰撞时隙存在的两种情况，将碰撞时隙向前移动、空闲时隙向后移动，并标记第一个多标签选中时隙与第一个空闲时隙，通过碰撞调整机制将碰撞时隙转化为成功时隙，将空闲时隙转化为成功时隙，提高每帧的标签识别效率。

图2 标签移动原理

图3 算法流程

1 算法原理

1.1 去空闲时隙原理

如图1所示，去空闲时隙原理具体步骤：首先标签选择随机自己通信时隙i，阅读器接收到标签预定义时隙后，对每一个比特位进行比较，被一个或多个标签选中的比特位记为X；未被标签选中的比特位记为0，生成预约序列。标签根据阅读器返回的预约序列重新调整自身的通信时隙，若预约位在预约序列中对应的时隙前有m个0，标签向前移动m位，并修改自身的i值，得到去空闲后序列。当标签数≥时隙数时，以256为单位进行分组；否则，按上述方法去空闲时隙。

1.2 碰撞区分原理

改进算法在阅读器端以4比特为一个检测单元进行标签的响应，在当前检测单元出现碰撞时，开启一个多比特时隙，区分开始时，阅读器发送“查询前缀+1”，处于阅读器识别范围内的标签收到查询请求后，利用ID匹配“查询前缀+1”。如果匹配，就响应阅读器请求命令，若显示无碰撞，表明只有一个标签选中该比特位；否则，表明多个标签选中该比特位。一个检测单元区分完毕之后，继续下一个检测单元。

1.3 空闲移动原理

碰撞区分后，将所有空闲比特位向后移动，标记第一个多标签选中的比特位和第一个空闲比特位。多标签选中的比特位随机选取一个标签保留本位，其余标签移动至后方空闲比特位，依次填充空闲比特位，使空闲比特位转化为单个标签选中比特位，空闲比特位标记依次向后移动。

2 算法具体分析

2.1 算法步骤

算法流程如图3所示。具体步骤如下：步骤一：阅读器发出一条Init(L)初始命令。

步骤二：处在识别区的标签在L个时隙中随机选择一个时隙，将其对应预约位置为1，其余置为0，生成一个长度为L的预约序列，发送给阅读器。同时将预约位存储在自身的计数器S_C中。

步骤三：阅读器比较所有响应标签返回的预约序列，生成碰撞信息：如果同一个比特位被N(N≥1)个标签选中，记为X；否则，记为0。

步骤四：阅读器发送Adjust命令，标签根据阅读器返回的碰撞信息，修改预约数：

1)将L个比特以4比特为单位划分检测单元，在当前检测单元出现多标签响应时，阅读器发送“查询前缀+1”，处于阅读器识别范围内的标签收到查询请求时，利用ID匹配“查询前缀+1”。如果匹配，就响应阅读器请求命令，若显示无碰撞，表明只有一个标签选中该比特位；否则，表明多个标签选中该比特位。

2)区分好选中位的标签数后，将所有空闲比特位向后移动，标记第一个多标签选中的比特位为Xcoll，标记第一个空闲比特位为Lidle。多标签选中的比特位随机选择一个标签保留本位，其余标签依次从第一个空闲比特位开始填充，Lidle标记依次向后移动，Xcoll标记也依次向后移动，以此类推。

步骤五：标签根据阅读器命令进行调整，修改计数器S_C中的值，得到新的比特序列。

步骤六：阅读器开始识别，在一帧中与所有标签通信。完成后查看是否有标签碰撞的时隙，若有，返回步骤一，直至所有标签识别；否则，识别结束。

2.2 算法分析

假设识别范围类共有N个标签，L为帧时隙的大小，根据二项式分布定理可以推知：

同一帧同一个时隙被M个标签选中的概率：

该时隙为空闲时隙的概率：

该时隙为成功时隙的概率：

该时隙为碰撞时隙的概率：

由以上公式可知它们的期望分别是：

空闲时隙：

成功时隙：

碰撞时隙：

吞吐率S为：

吞吐率LL为：

吞吐率P为：

3 算法仿真

为验证NCIRC_FSA算法的有效性，假设在相同的识别长度范围内，标签均匀分布，待识别标签数量介于100~1 500之间。在Windows10的操作环境下，利用MATLAB 2018b对帧长为256时隙的FSA算法、DFSA算法[3]、GDFSA算法[4]、CIFSA算法[5]以及NCIRC_FSA算法进行仿真，以100次实验的均值作为仿真结果，对以上五种算法的标签吞吐率、时隙开销及标签丢失率情况进行对比分析。

3.1 吞吐率分析

在MTALAB上对FSA、DFSA、GDFSA、CIFSA和NCIRC_FSA这五种算法进行仿真得到吞吐率曲线为图4所示。

图4 吞吐率分析

由图4可见FSA、DFSA、GDFSA三种算法吞吐率曲线峰值基本重合，其峰值吞吐率为0.36，而FSA吞吐率曲线在到达峰值后呈现出急速下降的趋势，当标签数N=1 500时，DFSA算法吞吐率几乎为零。DFSA算法虽然采用了动态帧时隙策略但吞吐率曲线仍避免不了下降的趋势，而GDFSA算法则在此基础上采取标签分组以及先来先服务策略可有效避免这一趋势并使吞吐率稳定在0.36左右；CIFSA算法则在GDFSA算法的基础上采用预约改进思想去除了空闲时隙的影响，使吞吐率稳定在0.75左右；NCIRC_FSA算法采用标签分组、先来先服务策略以及标签移位策略和去空闲策略，去除空闲时隙以及碰撞时隙的影响使标签吞吐率能稳定在1.00左右，避免了FSA算法和DFSA算法在标签数快速增多的情况下吞吐率急速下降的趋势，相比GDFSA算法以及CIFSA算法，NCIRC_FSA算法的吞吐率稳定性更强。

3.2 时隙总数分析

如图5所示，当待识别标签数量由100递增至1 500的过程中，FSA算法和DFAS算法所消耗的时隙总数随待识别标签数量的递增呈指数级增长,而GDFSA算法、CIFSA算法和NCIRC_FSA随待识别标签数量的递增则呈线性增长，其中NCIRC_FSA算法增长速度最慢，优势明显。

图5 时隙总数分析

3.3 丢失率分析

标签识别简化动态RFID模型如图6所示。标签停留时长为T=350(slot)，信号区内标签数目初值为100；通过调整信号区内标签的数目改变标签密度，分析标签密度变化对移动RFID系统性能(TLR)所产生的影响。

图6 简化动态RFID模型

图7 标签丢失率分析

如图7所示：(1)初始时DFSA与GDFSA丢失率曲线重合，并且两种算法丢失率均低于FSA算法，原因是DFSA和GDFSA两种算法采用动态帧时隙策略降低了其标签丢失率；当标签数目N>354时，FSA、DFSA丢失率曲线重合，而GDFSA丢失率低于这两者算法，是因为FSA、DFSA算法均以最大帧进行识别，系统识别效率已经达到最大，而GDFSA采用标签分组及先来先服务思想增大了系统识别率减少标签的丢失。(2)CIFSA算法丢失率小于GDFSA算法，原因是CIFSA在其基础上采用预约思想去除空闲时隙的影响，大大提高系统识别率，减少标签丢失。(3)NCIRC_FSA算法的标签丢失率远远小于FSA、DFSA、GDFSA、CIFSA这四种算法，原因是NCIRC_FSA算法将碰撞时隙和空闲时隙通过预约思想和标签移位思想转换为成功时隙，消除了空闲时隙和碰撞时隙所产生的影响，降低了标签丢失率。

4 结语

本文提出一种新型去除空闲和去除碰撞的帧时隙ALOHA防碰撞算法(NCIRC_FSA)，算法首先预估识别区域内标签数量，当标签数N≤256时采用动态帧时隙策略。否则，采用标签分组及先来先服务策略。然后根据预约思想将时隙重新进行排列，采用标签移位思想将碰撞位标签依次移至空闲时隙。最后去除多余的空闲时隙，实现标签快速识别。通过仿真分析表明随着待识别标签数的增加，与其他算法相比，NCIRC_FSA算法系统的时隙开销最小，吞吐率最高且稳定性最佳，有效地提高了系统的识别效率。