基于标签分组的动态帧时隙ALOHA算法

雷隆毓，蒋荣斌，陈子妍，罗雪梅+

(1.贵州大学 电气工程学院，贵州 贵阳 550025；2.六盘水市第二人民医院，贵州 六盘水 553400)

0 引 言

无线射频识别技术RFID(radio frequency identification)是一种可广泛应用在信息化领域的自动识别技术[1]。在无线射频识别系统中，在读写器可识别的范围内出现多个标签发生信息碰撞。因此如何有效、合理解决上述信息碰撞问题成为多标签防碰撞中最需要进行研究的问题。无线射频识别系统通常使用TDMA(时分多址)方式进行数据通信。

现使用时分多址访问接入方式的多标签防碰撞算法分为两种，一种是相对随机性的ALOHA算法，一种是非概率型的二进制树算法[2]。ALOHA算法常常用于实际中处理多标签防碰撞算法，是由于具有随机性的ALOHA算法对标签的要求相对较低，但同时恰恰因为不确定的随机性，ALOHA算法会出现部分标签遗漏识别的问题，即一个标签一直不被抽取识别，导致系统难以及时的识别。ALOHA算法因为具有随机性，因此系统识别效率相对比较低，且最大的系统识别效率为36.8%，然而该情况仅出现于待识别标签数目和阅读器给定的时隙数目相同时。该结论可在参考文献中参见。由于存在该情况，如此便对标签估计算法的精准度有了一定的要求。而标签识别过程发生碰撞的主要原因在于标签分配时隙具有随机性，无法控制标签可以均匀分配在帧时隙中，于是本文针对以上两个原因提出了一种分组算法，减少了对标签估计算法[3]的精准度并尽量使得标签可以均匀分配在每个时隙中，降低了时隙内标签的碰撞几率，提高了系统识别效率。

1 动态帧时隙ALOHA算法分析

由上文可知，仅当时隙数和标签数相等时，可得到系统的最大吞吐量。而在理想实验测试中，因为硬件问题，当帧时隙取值为256时系统已经达最大吞吐率。脱离理想状态后，在实际操作的过程中，在各种因素影响下，例如空气介质、空间条件等等，标签的吞吐量常常无法达到最大值。因此在FSA算法(帧时隙ALOHA算法)的基础上提出了动态帧时隙ALOHA(DFSA)算法[4,12]。常见的动态帧时隙ALOHA算法中往往包含了标签估计算法，因为需要对标签总数做一个估算，此后再通过标签安排时隙发送信息从而进行识别，此间对发生了碰撞的标签做某种的方法进行重新识别，关于DFSA算法的具体实现步骤可以在相关的参考文献中参见，因此此处便不多做概述。

在总结了近年来在DFSA算法基础上为提高系统识别率改进的多种算法，我们可知若想要提高系统的吞吐率和系统识别效率，可大致分为3个方法：

(1)使得帧长与待识别标签数一致。如同上文提及的吞吐率最大值的要求，即：使得帧长与待识别的标签数保持一致。由于标签数量不能直接提供给阅读器，因此大家对DFSA算法研究的一个方向在于如何精确估计待识别的标签数，即标签估计算法。标签估计算法通常是依据实验后几次碰撞情况估计标签总数，或者估算下一帧的帧长，依此提高系统的识别效率。而该方法也只能保证系统的吞吐率比较接近于最大吞吐率0.368[5]。比较常用的标签估计算法有：Schoute标签估计法、切比雪夫不等式标签估计法、贝叶斯标签估计法等。但是改进的标签估计算法各自有各自的缺点，精确性高但是计算要求高，复杂度高，或者实用性不强；

(2)对碰撞时隙和空闲时隙的重新安排和利用。在识别的过程中，最重要的是成功时隙，而空闲时隙和碰撞时隙都属于浪费的时隙，对浪费的时隙重新安排或者减少浪费时隙的产生会使得一个帧长中成功识别的标签数增加，而这是提高吞吐率和系统识别效率的另一个研究方向。在此方向的例子有：增加随机数，增加第二次标签分配的机会，保证碰撞时隙时依然还有标签可以识别，减少碰撞时隙的浪费，从而提高了系统识别效率和系统吞吐率；使用码分多址方法处理碰撞时隙中的标签，同样是减少碰撞时隙的浪费，碰撞标签后阅读器验证标签扩展码，识别相应的标签[6]；使用自适应预约时隙的方法增加时隙利用率，直接阅读成功时隙，对空闲时隙和碰撞时隙进行忽略不识别等方法[7]。该类方法具有可行性，系统识别效率低原因在于产生了过多空闲时隙和碰撞时隙，因此对空闲时隙和碰撞时隙进行控制可以有效避免时隙的浪费；

(3)由于读写器硬件的原因，ALOHA算法的最大帧长时隙数为256个。随着标签数量的增加，帧长度不能增加，导致标签之间的碰撞越来越严重，碰撞时隙的数量越来越多，空闲时隙和成功时隙的数量越来越少，导致在识别整个标签组时，总时隙的数量大大增加，这导致系统吞吐量下降，识别效率低[8]。于是面对大量的标签数据，可将大量标签进行分组，保证分组后组内标签数量较少，使发生碰撞的几率不会因为标签数量的增加而增加。因此分组方法也成为了另一个研究主流方向，最经典的分组方法为分组动态帧时隙算法(GDFSA)。此后也有许多的分组方法，比如Q算法及MQ算法[9]、基于哈希函数分组算法[10]、复杂度较高的PIGDFSA算法[11]等。分组算法适用于标签数量较大的场景下。

2 改进的DFSA算法

2.1 标签分组的提出

标签发生碰撞是因为DFSA算法中多个标签产生的随机数一致，而当标签数量较大，进行时隙分配时越发容易出现多个标签选择了同个时隙。

为确定系统识别效率降低趋势，在使得帧长与标签一致的情况下，进行DFSA仿真实验[10]。标签总数取值为1到256，实验结果为系统识别效率随着标签总数的增加最后趋近于0.368，图1为局部放大图，更加直观地观察到系统识别效率随着标签总数增加的降低速率。

图1 DFSA算法随标签增多的系统识别效率变化

由图1可知，系统识别效率随着标签数量的增多而逐渐降低，在10个标签以内时，标签的降低速率达到最快，此后系统识别效率的降低速率趋于缓慢，最后保持在0.368左右。若将每组标签数量控制在较少数额时，系统的识别效率较高，控制在系统识别效率最高处，即标签数量为1到2个，那么组别会变多，并不实际，然而控制每组标签数量大于10则系统效率较低，控制每组标签数量的意义不大，因而取8，可被256整除，同时当每组标签为8个以内时，可以更好提高系统识别效率。

使得分组后每组标签数量较少的思想确定了，那么如何让每组中的这些标签均匀分布在各个时隙中，于是考虑到标签的ID信息。因标签中存储数据的寄存器占8位，标签ID号可通过取模运算分到1到256之间(十进制)，因此可以将标签以ID信息进行分组，可分为256个组。

256组中每个组相互之间是可以区别开的。因此考虑是否可以构造出单组内标签数为8且标签为连续ID或者有一定大小顺序。那么需要在由标签ID分组的256组内连续选择8组，并在每组内抽取一个标签构成新的组。而抽取的过程使用的方法和DFSA算法相似，通过使用随机数的方法。然而通过随机数，具有一定随机性，因此不一定能够保证每个组里能够抽取一个标签，因此新的一组内的标签ID不一定连续，但是却一定是保持着从小到大的顺序，而其中含有空闲时隙在内。

大致算法路线为：阅读器挑选长度为8的连续组号，发出查询组号和一个随机数命令(阅读器的随机数不是随机产生，而是从1开始，一直到标签产生随机数的最大值)，当标签组号与阅读器提供的组号一致时，标签才能进行响应阅读器，否则处于睡眠状态。每组标签在存储组号的同时存储一个随机数，当组号一致时，识别随机数，当标签的随机数与阅读器提供的随机数一致时，才能响应阅读器，并向阅读器发送识别请求。此时标签需要有能够产生随机数的能力，同时需要具有一个寄存器、存储组号和一个随机数。

但是该算法容易出现两个问题：一个问题是因为本算法和DFSA算法都使用了随机数，因此也会出现标签产生的随机数相同情况，即当阅读器和标签比对随机数的时候，可能会出现多个标签随机数相同的情况，会发生多个相同ID号(这里指的是电子标签根据ID信息分的组号，为了方便我们直接说ID号)的标签发送识别请求。该情况发生后，无法保证该帧里的标签个数较少，会影响系统识别效率,使得本文分组方法毫无意义。而产生该情况很大的一方面是由于随机数的范围较小，标签能够产生随机数比较单一。另一个问题是因为随机数的范围无法确定，或者范围过大，因此标签产生的随机数与阅读器产生的随机数总是不一致，如此需要阅读器反复产生随机数并发送，如此会产生大量的空闲时隙，增加了算法的复杂度，降低了系统识别效率。因此随机数的取值范围不应该太大或者太小。因此可以考虑每组的标签平均数，如此便需要估计标签总数，以确定随机数的确定范围，即总数N除256。但此处的估算的标签总数对准确性并没有严格要求，只需要大致的估算范围即可。

因为标签ID号逐渐增加，标签使用哈希函数设定发送信息的时隙，H=id%L，其中L=8，标签根据自身的ID号，通过哈希函数计算，确定了一帧长内发送信息的时隙，并将信息设置为时隙时间发送。这里若使用DFSA算法，使标签产生随机时隙，相对随机化，那么将标签事前由ID信息分组为256组便无意义，因为无法保证新组内标签为连续ID，因此使用哈希函数分配时隙，减少了碰撞可能性。

2.2 组内识别方法

同上述第一个问题，当标签产生随机数时相同ID号的多个标签产生了相同随机数，同时和阅读器产生的随机数一致时会导致新组一组内出现多个相同的ID标签，这里的哈希函数并没有发挥使得标签可以分散分布的作用，反而使得相同ID号的标签分布在同一个时隙中，因此该类标签在使用哈希函数分配时隙时，必定会发生碰撞，碰撞时隙增加，从而降低了系统识别效率。

系统识别效率是成功时隙除以总时隙，而总时隙包含了成功时隙、空闲时隙和碰撞时隙。若可以减少空闲时隙和碰撞时隙的浪费，便可以减少总时隙的时隙数，从而提高了系统识别效率。因此如何减少空闲时隙和碰撞时隙的浪费，这里考虑了将碰撞时隙进行重新分配，将碰撞的标签在碰撞时隙和空闲时隙中进行重新安排，增加了空闲时隙和碰撞时隙的利用。那么便产生了问题，如何确定空闲时隙和碰撞时隙，这里便考虑了可以在组内使用预分配方法，标签对时隙进行预约并反馈给阅读器，阅读器反馈空闲时隙和碰撞时隙的记录，标签重新确定发送信息的时隙，使得碰撞时隙和空白时隙可以重新利用。同时也可以尽可能减少上述相同ID号的多个标签产生相同随机数时必定进行碰撞的几率。

具体实现方法：在标签识别之前，标签发出预约时隙的申请，阅读器接收申请后，对空白时隙和碰撞时隙进行记录，同时向标签返回空白时隙和碰撞时隙的记录，标签比对阅读器返回的时隙记录，若预约的时隙与阅读器返回的时隙数一致，则重新在该时隙范围内重新选择时隙进行信息发送，若标签预约的时隙与阅读器返回的时隙数不一致，表示标签预约的时隙不属于空闲时隙和碰撞时隙，而属于成功时隙，则该标签依照预约情况在该时隙发送信息。重新分配空闲时隙和碰撞时隙可以减少空白时隙和碰撞时隙的浪费，提高了时隙的利用率。

2.3 算法识别过程

算法识别过程具体步骤描述如下：

(1)标签总数的估计：阅读器第一次发送查询指令和初始帧长度，阅读器初始化计数值w，标签返回自己的数据信息，阅读器记录空闲时隙、成功时隙和碰撞时隙，并使用标签估计算法对标签总数N进行大致估计，计算出随机数的范围[1:N/256]，并返回给标签N值；

(2)标签分组：电子标签确定自身的组别，一共分成256组。同时，每个标签随机产生一个随机数R,范围为[1∶N/256]，存储在标签寄存器中；

(3)阅读器发送组号命令：阅读器生成连续的8个组号Gr(第一次的组号为1到8，此后组号为第一次组号加上计数值w*8，即首次组号为1到8，下一次为9到16，几次类推)和一个随机数V(此后每帧识别结束后V自增，直到V值到达随机数的最大值)，阅读器向标签发出查询组号和随机数V命令；

(4)标签响应判定：当标签组号与查询的组号Gr一致时，标签才能进行响应阅读器，否则处于睡眠状态。当组号一致时，识别随机数，当标签的随机数R与阅读器提供的随机数V一致时，才能响应阅读器，并向阅读器发送识别请求；

(5)标签预约时隙：标签根据L=8使用哈希函数(H=id%L)确定发送信息的时隙，并向阅读器预约；

(6)阅读器记录预约情况并返回：阅读器记录标签预约时隙，返回碰撞时隙Sn、空白时隙S0，标签比对阅读器返回的时隙，若标签预约的时隙不属于阅读器返回的时隙数内时，则标签将信息设置为该时隙进行信息发送。若标签预约的时隙属于阅读器返回的时隙数内时，则标签在空白时隙S0和碰撞时隙Sn中重新选择时隙进行信息发送，并设置该时隙发送信息；

(7)阅读器进行一帧内的标签识别；

(8)判断是否存在待识别标签：阅读器根据标签预约情况及V值大小判断组内是否还有数据，有则进行第(3)步，发送同一个组号Gr，但产生下一个随机数V，重新进行一组的标签分配。若组内无数据且V值已达最大值，则判断计数值w是否为32，若小于32则计数值w自增一次并进行第(3)步，进行新的一组的标签安排；若计数大于32则识别结束。

为了直观地理解本文算法，图2展示了本文算法的流程。

图2 本文算法流程

3 仿真结果与分析

将本文算法与DFSA算法、哈希分组算法[10]在MATLAB平台环境下分别进行模拟仿真，并对仿真的结果进行分析。使用的MATLAB软件为R2014b，硬件环境是8核Intel i5处理器，底层操作系统为Windows 10。

此处为了方便对比，这里设置4种算法都已知标签个数，且帧长与待识别的标签数相等，当标签总数大于256，初始查询帧长设定长度为256。仿真的标签总数设置为从50开始，间隔50个，一直到2000个。为保证数据的准确，实验程序运行了100次取平均值。

3.1 系统识别效率对比分析

仿真时系统识别效率计算方法为：成功时隙/(成功时隙+碰撞时隙+空白时隙)，图3为4种算法系统识别效率对比图。

图3 系统识别效率对比

DFSA算法和本文预约时隙算法都需要设定初始帧长为256，因此在标签小于256时，空闲时隙浪费较多，因而系统识别效率较低。而哈希函数算法与本文算法都利用了标签ID进行分组，没有设定初始帧长为256，因而在标签总数小于256时，避免了大量空闲时隙的浪费。因此出现在图3中，当标签数小于256时，4种算法出现了两种方向的情况。

随着标签数量的增加，本文算法系统的识别效率在已知标签总数的情况下，基本稳定在0.6以上，而DFSA算法基本稳定在0.36左右，明显可知本文算法识别效率远远高于DFSA算法。对比本文算法和哈希函数分组算法，在标签小于500之前，哈希函数算法的系统效率大致分布于0.45到0.6之间，而大于500之后，系统识别效率保持在0.4以上。而前500个标签，哈希函数算法的系统效率较高，随着标签增加，系统效率变低的原因是标签增加，在哈希函数分组后，组内的标签数也随之增加，碰撞几率增加，系统识别效率变低。而本算法由标签ID信息不同分组成256个组，再按由小到大依次选取8组作为新的组，保证了新组内的标签数量较少。

而本文算法出现图3中的阶梯式的情况,特别是1到256之间，出现该现象是因为随机数的选择范围，当由标签ID信息分组的组内标签数普遍多于随机数的范围，标签的碰撞几率将增加，因此当标签数为256的倍数时，系统效率相对较高，而当标签数为256的倍数前一个数时，随机数的范围并不适合用于该标签总数，组内标签数大于随机数的最大值，因而容易产生碰撞，导致系统效率处于最低的状态。

3.2 时隙开销对比分析

图4～图6分别是4种算法的空白时隙、碰撞时隙、总时隙的对比图。

图4 空闲时隙对比

图5 碰撞时隙对比

图6 总时隙对比

由图5可以看出本文算法产生的碰撞时隙和空闲时隙相对其它算法较少，而本文出现碰撞的原因主要是随机数的重复，虽然使用了预约时隙的方法，使碰撞时隙重新得到安排，减少了碰撞几率，但是还是会出现碰撞问题。其中本文预约时隙与DFSA算法都有初始帧长256的设定，因此在小于256时如图4出现大量的空闲时隙浪费情况。

通过对比可以看出减少了碰撞的几率和空闲时隙浪费的原因有两种：一个是将标签进行分组，对比本文算法和本文预约时隙时隙算法可看出，当标签基数较大的时候，利用预约时隙的方法能够减少碰撞时隙的产生，但这种减少的程度不够大。而使用分组后，单组标签较少，且按照标签ID号的由小到大的顺序安排时隙，使得碰撞几率降低。因为限制了组内标签的数量，所以随着标签增加，哈希函数分组算法碰撞时隙和空闲时隙增加速度较快，而本文算法两种时隙的增加速度较为缓慢。二是因为使用了预约时隙的方法。这点对比本文预约时隙算法和DFSA算法可以看出，预约时隙算法减少了碰撞时隙和空闲时隙的产生。

通过图6可以看出随着标签数量的增加，虽然4种算法需要的总时隙时间都在增加，但因为本文算法的碰撞时隙和空白时隙的大大减少，本文算法所需要的总时隙的增加速度明显缓慢。

4 结束语

本文算法进行了两次分组，第一次将标签由ID信息分组成256个组，第二次是按顺序在8组内随机抽取每组的标签，形成新的一组，如此限制了识别组内标签数量，保持着较少数量，后由标签ID信息使用哈希函数分配时隙，使得标签可以相对均匀分布于时隙中，减少碰撞几率。而在该组内实行预约时隙算法，尽可能减少标签生成的随机数发生重复所带来的碰撞。从适用性上看，本文算法的分组方法适合于标签数量较大且标签ID不完全一致的场景。本文算法在总时隙数、碰撞时隙数、空闲时隙数上都有明显的较少，在系统识别效率上有着明显的提高，可使得系统识别效率维持在0.6以上。优势相对明显，具有研究意义和应用意义。如何更好确定随机数的取值范围和是否可以不使用预约时隙方法是本文算法尚未解决的问题。