一种ALOHA算法的帧长度改进方法

陈夫桂 姜志峰 朱利娟 云中华

摘 要： 基于动态帧时隙ALOHA算法，运用拟牛顿法，使用某种近似矩阵代替牛顿法中的Hessian矩阵，解决牛顿法中复杂度计算的问题，由此缩短计算时间并提高计算精度。统计出不同时隙数下可识别的标签数，进而建立专家库，使读写器根据标签数目更准确地设定时隙数，达到全局搜索的目的，进而缩短匹配识别时间。仿真结果表明，运用拟牛顿法明显提高了数据交换量和识别效率。

关键词： ALOHA； 拟牛顿法； 近似矩阵； 专家库； 全局搜索； 识别效率

中图分类号： TN911.1?34； TP301 文献标识码： A 文章编号： 1004?373X（2018）15?0097?04

A frame length improved method based on ALOHA algorithm

CHEN Fugui1， JIANG Zhifeng2， ZHU Lijuan3， YUN Zhonghua2

（1. Office of Academic Affairs， Tibet University， Lhasa 850012， China； 2. School of Engineering， Tibet University， Lhasa 850012， China；

3. Tibetan Information Technology Research Center， Tibet University， Lhasa 850012， China）

Abstract： On the basis of dynamic frame slotted ALOHA algorithm， the Hessian matrix in the Newton method is replaced by a certain approximate matrix in quasi?Newton method to solve the problem of complexity calculation in Newton method， which can shorten the computation time and improve the calculation precision. The number of identifiable tags under different time slots is calculated to establish the expert library， so as to make the reader?writer set the number of time slots more accurately according to the number of tags， achieve the purpose of global search， and shorten the matching and recognition time. The simulation results show that the quasi?Newton method can improve the data exchange capacity and recognition efficiency effectively.

Keywords： ALOHA； quasi?Newton method； approximate matrix； expert library； global search； recognition efficiency

0 引 言

射频识别技术（Radio Frequency Identification，RFID）是一种非接触式自动识别技术，具有安全性、便捷性和高效性等优点，被广泛应用在农业、控制业和交通运输业等各个领域，成为物联网应用的热门技术之一。另外，RFID技术的普遍推广和应用，RFID系统存在的问题也日渐凸显，如多个标签同时占用一个信道或者多个读写器争抢一个标签。其中读写器同时识别多个标签时发生的碰撞尤为严重，即读写器同时接收2个或2个以上标签数据。目前对于解决多标签碰撞问题有三大类算法[1?2]：基于确定性的二进制算法、基于概率性的ALOHA算法和这两者的混合改进算法。

ALOHA算法中标签随机向读写器发送数据，在同一时间内读写器接收到多个标签发送的数据时就会发生数据重叠，发生碰撞的标签等待一段时间再次发送，直到标签完全被读写器成功识别，其他改进方法是把时间长度进行划分调整。此类算法操作性强，但识别效率相对较低。由于每个标签都有一个特定的ID号，二进制算法通过分类的思想，对发生碰撞标签的碰撞位进行划分为“0”和“1”两个子ID，进行标签再识别。这种算法识别效率相对较高，在实际应用中比较普遍。但这两种算法在实际应用中都会受到不同因素的约束，而本文考虑在节约经济成本和提高系统识别效率的前提下对ALOHA算法进行数学改进，通过建立专家库的方法构建不同时隙数所能识别的匹配标签数，有效缩短识别时间并提高了平均数据包交换量。

1 ALOHA算法

ALOHA算法[3?4]包括纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法和动态帧时隙ALOHA算法。纯ALOHA算法在连续的时间内随机选择某个时间点发送数据；时隙ALOHA算法是在纯ALOHA算法的基础上把时间长度划分为离散的时隙间隔，随机选择某个时隙发送数据；帧时隙ALOHA算法是把离散化的某几个时隙组合成一帧，进而改进为本文中动态的改进帧长度算法，即动态帧时隙ALOHA算法。

2 改进方法

2.1 估计标签数

动态幀时隙ALOHA算法是根据标签数目变化动态地改变帧长数目的大小，而本文根据已有动态帧时隙ALOHA算法研究[5?6]成果进行改进。通过仿真分析上一帧读写器的识别情况，动态地调整下一帧所需的时隙数。统计出每一帧所需的最佳时隙数，建立专家库，进行全局搜索匹配，准确地设定时隙数目，缩短识别匹配时间。

假设动态帧时隙ALOHA算法中帧时隙数和标签的数目分别为[s]和[n]，其中一个标签占用某个时隙的概率服从二项分布。在时隙数范围内，标签选择占用某个时隙的概率相等，[m]个标签选择同一个时隙的概率为：

经过一轮识别后，统计出成功识别的时隙数、碰撞时隙数和空闲时隙数的数目分别为[Ns]，[Nc]和[Nf]。其中发生碰撞的概率为[Nfs]。由式（5）可得：

式中：碰撞时隙数[Nf]和帧时隙数[s]已知，利用数学方法求解出标签数[n]。本文在牛顿法的基础上采用拟牛顿法进行数学改进。由于牛顿法每迭代1次，牛顿法结果的有效数字将会增加1倍，而且每次都要计算迭代函数的Hessian矩阵和它的逆矩阵，当计算维数较大时，复杂度也会增加，而拟牛顿法[7]中使用某种近似矩阵代替Hessian矩阵，可以解决牛顿法中复杂度计算的问题，缩短计算时间并提高计算精度。

基本步骤如下：

1） 取初始值为[n0]，收敛精度[ε>0]；

2） 设[H0=I]，[k=0]，计算出目标函数在[nk]处的梯度[gk=?f（nk）]，若[gk≤ε]，计算终止；否则转步骤3）；

3） 确定搜索方向[pk]，[pk=Hk?gk]；

4） 从[nk]开始，沿[pk]做一维搜索，满足[f（nk+tk?pk）=mint≥0f（nk+tk?pk）]且[nk+1=nk+tk?pk]；

5） 若[f（nk+1）≤ε]，计算终止；否则转步骤6）；

6） 若[k=m]，则令[n0=nm+1]，转步骤2）；否则令[Δnk=][nk+1-nk]，[Δpk=pk+1-pk]，[Δgk=gk+1-gk]，计算出[Hk+1]；

7） 令[k=k+1]，转步骤3）。

上述步骤为拟牛顿迭代算法的基本过程，但在实际应用中，很多标签的寄存器位数小于8位，故对应的帧长数[8]小于256（[L≤28]），同时在整个系统中碰撞时隙数小于帧长数。因此，对进行拟牛顿迭代算法式（7）中的[Nc]和[L]是在一定数目内的，可以通过上述方法求解出对应不同帧时隙数的标签数。拟牛顿法基本流程图如图1所示。

2.2 算法流程改进

标签识别时，每次完全识别都会耗费大量时间，造成整个系统总的识别时间较长。故在上述基础上通过构建专家库的思想，可进行全局匹配，即不同时隙数与对应标签数进行匹配。这样可以大大缩短因匹配不佳或者不符合而耗费时间，提高整个系统的识别时间。改进算法流程如图2所示。

读写器首先发送请求命令，等待标签响应回复，并初始化空闲时隙计数器[Nf]、碰撞时隙计数器[Nc]和成功识别时隙计数器[Ns]为0，以及帧长数[9][L=2Q（Q=1，2，8）]。此时经过一轮识别后，判断时隙可响应状态为空闲、碰撞或成功，对于成功识别或者发生碰撞的时隙计数器加1，同时帧长数减1。数次循环后，判断帧长数是否为零；若帧长数不为零，调整标签应答命令；若为零，此时判断碰撞时隙计数器[Nc]是否为零，若为零，识别结束，否则通过查询专家库调整帧长数，循环上述过程，直至标签完全识别。

上述识别过程中假定标签数小于256，而在实际应用场合中标签数目远大于256。当标签数大于256时，求解出不同时隙数所对应的标签数时计算复杂度会增加，同时，识别大量标签时，整个系统的功率损耗也会增加，识别时间也会变长。此时，就需要对标签数进行分组处理。表1为标签分组处理原则[10]。

3 仿真结果与分析

通过对动态帧时隙ALOHA算法中帧长度进行改进，提出一种操作性强、经济成本低的方法。但在实际应用中首先考虑标签的数目，在最优标签数的情况下建立专家库。然后直接依据专家库设定不同时隙数下可识别的标签数，这样可大大缩短系统识别时间，有效提高系统识别效率。

本文中选取100个标签，分别对固定帧时隙算法和改进算法进行Matlab实验仿真。固定帧时隙算法中帧长数目是固定的，无法改变。由于改进算法能动态的反应时隙数的变化情况，从而动态地设定标签数，使得读写器周围存在的标签可以完全被成功识别。

图3中的两种算法分别是固定帧时隙算法和改进后的动态帧时隙算法。前者的帧长数目是固定的，通过大量的Matlab实验仿真发现，当帧长数为64时系统的识别性能最高。识别100个标签大约需要370个时隙，即平均每3.7个时隙识别一个标签。对于改进算法，识别100个标签大约需要300个时隙，平均每3个时隙成功识别一个标签，相比固定帧时隙算法识别效率有所提高。

图4为平均数据包交换量与吞吐率的关系。从图中可以看出：当平均数据包交换量小于0.4时，两种算法的吞吐率相近；当大于0.4时，改进算法的吞吐率明显高于固定帧时隙ALOHA算法的吞吐率；而改进算法的平均数据包交换量达到4.5，固定帧时隙ALOHA算法的吞吐率仅持续到3.4左右，相比于固定帧时隙ALOHA算法的平均数据包交换量大约提高了36.3%。另外从图5中可以看出，当标签数在100～300之间时，系统的识别效率在25%～40%之间浮动。所以本文中的改进算法在数据交换量和吞吐效率方面都有所提高。

4 结 论

本文在动态帧时隙ALOHA算法的基础上，利用数学思想提出一种改进帧长度的方法。改进算法的核心在于建立专家库进行全局搜索，动态地依据专家库设定不同时隙数下所对应匹配的标签数，相比固定帧时隙ALOHA算法，提高了系统平均数据交换量并缩短系统识别时间。因此，本文改进的方法有效提高了标签识别效率。

注：本文通讯作者为云中华。

参考文献

[1] 王飞，张武.基于分组的动态时隙ALOHA算法[J].计算机系统应用，2013，22（7）：77?80.

WANG Fei， ZHANG Wu. Algorithm based on packet dynamic time slot ALOHA [J]. Computer systems & applications， 2013， 22（7）： 77?80.

[2] 马翠红，赵跃，杨友良，等.一种改进的RFID防碰撞时隙ALOHA算法[J].河北联合大学学报（自然科学版），2014，36（2）：54?57.

MA Cuihong， ZHAO Yue， YANG Youliang， et al. An improved RFID anti?collision slot ALOHA algorithm [J]. Journal of Hebei United University （natural science）， 2014， 36（2）： 54?57.

[3] 陈坤，苏寒松，孙尚龙.RFID中基于分组动态A?LOHA防碰撞算法的研究[J].电子测量技术，2011，34（11）：55?57.

CHEN Kun， SU Hansong， SUN Shanglong. Research on A?LOHA anti?collision algorithm based on packet dynamic type in RFID [J]. Electronic measurement technology， 2011， 34（11）： 55?57.

[4] 张小红，胡应梦.分组自适应分配时隙的RFID防碰撞算法研究[J].电子学报，2016，44（6）：1328?1335.

ZHANG Xiaohong， HU Yingmeng. Research on RFID anti?collision algorithm for adaptive allocation of time slots [J]. Acta electronica sinica， 2016， 44（6）： 1328?1335.

[5] 陈平华，王康顺，李超，等.基于线性回归的动态帧时隙ALOHA算法[J].计算机仿真，2014，31（7）：259?263.

CHEN Pinghua， WANG Kangshun， LI Chao， et al. Dynamic frame slot ALOHA algorrithm based on linear regression [J]. Computer simulation， 2014， 31（7）： 259?263.

[6] 管小卫，傅伟，蒋道霞.一种改进的分组帧时隙ALOHA算法[J].制造业自动化，2014，36（14）：1?4.

GUAN Xiaowei， FU Wei， JIANG Daoxia. An improved packet frame time slot ALOHA algorithm [J]. Manufacturing automation， 2014， 36（14）： 1?4.

[7] 马琰，蔡丽霞，任晓娜.一种自适应帧长RFID标签防碰撞算法[J].计算机与现代化学，2014（11）：113?116.

MA Yan， CAI Lixia， REN Xiaona. A collision avoidance algorithm for adaptive frame?length RFID tags [J]. Computer and modern chemistry， 2014（11）： 113?116.

[8] 黄仁，张静，程平.一种ALOHA算法的帧长度调整方法[J].计算机工程与应用，2011，47（9）：115?117.

HUANG Ren， ZHANG Jing， CHENG Ping. A frame length adjustment method for ALOHA algorithm [J]. Computer engineering and applications， 2011， 47（9）： 115?117.

[9] 高乐，吴援明，王晓磊.一种用于RFID系统中的帧长度调整方法[J].微计算机信息，2007（5）：213?215.

GAO Le， WU Yuanming， WANG Xiaolei. A frame length adjustment method used in RFID system [J]. Microcomputer information， 2007（5）： 213?215.

[10] 李晶.一种改进的RFID防碰撞时隙ALOHA算法[D].长春：吉林大学，2009.

LI Jing. An improved RFID anti?collision slot ALOHA algorithm [D]. Changchun： Jilin University， 2009.