基于动态帧时隙Aloha的防碰撞算法研究

    陈昊+高勤+安锡文

    摘 要：在RFID系统中，多标签同时存在会引发标签碰撞问题，文章首先分析已识别标签的情况，对剩余标签的个数进行了估计，并依此动态匹配最佳帧长。为了进一步提高系统的识别效率，构造了合适的哈希函数，将标签集合均匀地映射到帧时隙集合，降低了标签的冲突率。仿真表明，该算法提高了系统的吞吐率和稳定性，对Aloha算法的后续研究工作以及工程实践应用具有一定的参考价值。

    关键字：动态帧时隙；Aloha算法；防碰撞；哈希函数；标签估计

    1 RFID概述

    无线射频识别（Radio Frequency Identification，RFID）作为新型无线非接触式自动识别技术[1]，具有存储容量大、识别速度快和安全系数高等优点，被作为感知层的关键技术广泛应用于物流、销售和定位等领域，并作为物联网领域的核心技术之一，得到极大关注[2]。

    RFID系统一般由读写器、电子标签以及应用软件系统组成。系统在工作的时候，读写器与标签之间利用电磁信号进行数据交换。当多个标签共用相同的信道时，信号在空中媒介发生干扰，就会引发碰撞，导致标签识别和数据传送失败。为了减小和消除这种碰撞问题，保证数据在传输过程中的完整性，许多科研工作者对RFID中的防碰撞机制进行了大量深入的研究。

    目前，应用较广泛的防碰撞算法大多基于时分多址接入（Time Division Multiple Access，TDMA），主要有如下两类：基于二叉树的确定性算法和基于Aloha的概率性算法[3-5]。前者优点是能识别出所有标签，没有遗漏现象，但是对读写器硬件要求较高且算法的空间和时间复杂度较高。后者是Aloha及其改进算法，标签随机选择时隙与读写器通信，复杂度小且容易实现，但存在一定概率的某一标签长时间内所选择的时隙均发生碰撞，在有效时间内无法被读写器识别，存在标签“饥饿”问题。基于Aloha的防碰撞算法主要包括纯Aloha（Pure Aloha，PA）、时隙Aloha（ Slotted Aloha，SA）、帧时隙Aloha（Framed Slotted Aloha，FSA）、动态帧时隙Aloha（Dynamic Frame Slotted Aloha，DFSA）等。其中，DFSA算法可以根据实际的标签数目动态地调整帧长度，其识别速度快，可使信道吞吐率达到最大，所以应用也最为广泛。由于在实际情况下，标签数量通常是未知的，所以如何估计标签数目是决定系统吞吐率的关键。本文在此基础上，首先统计已识别标签的数据情况，通过对剩余标签的数目进行估计，并构造合适的哈希函数对标签进行时隙分配，减少了标签随机选择时隙带来的误差，直到所有的标签被正确识别。

    2 时隙基本定义

    在基于Aloha的算法中，将时间分成很多小时间段，每一段称为时隙，多个时隙组成一帧，每帧包含的时隙个数称为帧长度。对于一个给定的时隙，存在以下3种结果：空闲时隙（Idle Slot，IS），即没有任何标签选择在该时隙进行回复；成功时隙，当前时隙中仅有一个标签参与回复，读写器成功识别该标签；碰撞时隙，存在两个及两个以上标签在该时隙进行回复，

    此时会产生数据碰撞。如图1所示。

    假设读写器范围内有8个标签，帧长为8，即每帧中含有8个时隙，各标签在每帧中随机选取一个时隙发送信息。通过读写器和标签的一系列命令和回应之后，出现如图1所示情况，根据定义，可知时隙1，4，7为成功时隙，时隙2，6为碰撞时隙，时隙3，5，8为空闲时隙，也即标签1，3，7被成功识别；标签2，5发生碰撞，标签4，6，8发生碰撞，并且由此可知，标签识别过程中，空闲时隙和碰撞时隙出现的概率很高。

    3 时隙算法说明

    3.1 标签选择时隙方法

    在RFID系统中，标签数目一般很多，在几十至几千个之间，由于标签选择时隙具有一定的随机性，如果不能合理地安排时隙，那么由于效率低而造成的时间开销损失会非常严重。防碰撞算法的实质是减少时隙的碰撞。通过构造合适的函数，确定标签选择时隙的基准，使得标签能根据一定的算法均匀地分布到各个时隙，降低标签空闲及碰撞情况。

    每个标签都有唯一的识别码（UID），其包含了标签的基本信息，文中采用计算量较小的除留余数法构造的哈希函数[6]，满足了简单均匀的要求，具体计算公式为：

    Hash（ID）=[ID/w] mod p ，H（ID）∈[0，p-1]

    其中，除数p称作模，一般取值为小于帧长L的素数，[ ]为取整符号，即取该数的整数部分，这里的w为读写器发给标签的正整数，其数值是根据碰撞情况变动的。当标签收到读写器发送的帧长时，对相应的标签ID取余，然后该标签在[0，p-1]中根据所得的余数值选择对应的时隙发送数据，即通过Hash运算将标签集合映射到帧时隙对应的集合。比如：标签ID=（10001101）2=141，取 w=1，L=17，经计算得：H（141）=5，即标签选择时隙5发送数据，完成识别。

    但是，我们需要明确，均匀的哈希函数可以减少冲突，但是不能完全避免冲突，比如，在读写器的可读范围内，其中有3个标签ID分别为：ID1=（10001101）2=141，ID2=（11000000）2=192，ID3=（11110011）2=243，经简单计算可得，H（ID1）=H（ID2）=H（ID3）=5，即3个标签都选择了5号时隙发送数据，导致冲突，标签无法被正确识别。经过对上述3个ID相关整数值进行分解可得，ID1=141=8×17+5，ID2=192=11×17+5，ID3=243=14×17+5，通过比较得，3个整数含有不同的w×L值（即w×L=17），故可选择w=17，L=19，经计算得，H（ID1）=8，H（ID2）=11，H（ID3）=14，即标签ID1选择了时隙8发送数据，同理，ID2选择时隙11发送数据，ID3选择时隙14发送数据，标签被分配到了下一帧的不同時隙，大幅度地减少了碰撞情况。Hash函数是通过递归搜索碰撞时隙进而识别碰撞标签的，所以在算法中，必须适当改变参数，改变的原则可设为：下一帧的w值可选为当前帧w与L的乘积，此时Hash运算可以将碰撞降低到最小，使当前帧中碰撞的标签尽可能映射到下一帧的不同时隙。

    3.2 标签估计与帧长调整

    信息是用来消除不确定性的东西，要解决识别过程中的多标签碰撞问题，首先需要对标签数进行预测，了解更多的标签信息。假设一帧内有L个时隙，即帧长为L，共有n个待检测的标签，由于标签选择各个时隙数是等概率的，从数学原理上来讲，时隙Aloha的碰撞是一个多重伯努利试验问题[7]，每个标签以1/L来随机选择一帧中的某个时隙发送数据。假定各个时隙的时间间隔相等，并且不考虑捕获效应[8]（两个或两个以上标签同时产生成功时隙）和环境噪声等其他因素对系统的影响，那么可以得到同一时隙里有r个标签同时发送数据的概率为：

    由上述公式可以得到，空闲时隙P（i）、成功时隙P（s）、碰撞时隙P（c）的概率情况如下：

    P（i）=P（0）；P（s）=P（1） ；P（c）=1-P（0） -P（1） （2）

    由于RFID系统的识别效率为读写器在一个识别帧长的时间内成功传输信息的时隙数目所占的比例，可用P（s）表示。那么，通过P（s）对标签数n求导可得：

    （3）

    令上述结果（3）等于0，再利用泰勒公式进行展开计算，可以得到，当帧长度L与待识别的标签数目n满足L≈n+1时，理论信道的最大吞吐率为36.8%，图2为不同帧长条件下，标签数与系统吞吐率的曲线关系。

    因此尽量设置帧长满足上述关系，但是由于硬件的条件限制及标签的成本问题，帧长不能随着标签数的增大一直变大，为减少标签的碰撞，按照构造的Hash函数进行时隙的分配，提高时隙的利用率。对应的流程如图3所示。

    目前已经提出了多种标签数目估计方法，其中Vogt算法可以做出误差相对较为小且稳定的估计，其主要思想是采用切比雪夫不等式：一个涉及随机变量的随机试验过程其输出很可能在该变量的期望值附近，即使得下式中差值最小的n为标签数目估计值。

    其中，Ci，Cs，Cc分别为实验读取的空闲时隙数，成功时隙数，碰撞时隙数，E（i），E（s），E（c）为空闲时隙的期望值、成功时隙的期望值以及碰撞时隙的期望值。具体计算方式为：

    E（i）=L×P（i）；E（s）=L×P（s） ；E（c）=L×P（c）

    一个读周期结束后，读写器通过Ci，Cs和Cc值所提供的信息，使用切比雪夫估计方法估计系统中存在的标签数量，在此基础上设置下一个读周期的帧长。要找到使ε最小的标签数n，需根据实际情况设定n的范围。经多次实验，设定n在[Cs+2Cc， 2（Cs+2Cc）]范围内变化，计算量也将大大减少。

    4 仿真结果

    通过Matlab仿真，DFSA算法在最佳情况时，识别效率为36.8%。相比DFSA算法，文中改进算法的吞吐率有大幅的提高，最高可达54%左右，并且当标签数目很大时（比如标签数大于1 500个），本文算法仍能将系统识别效率维持在较高水平，达到40%以上，结果如图4所示。

    5 结语

    防碰撞算法是提高RFID系统识别效率的关键，标签估计和帧长度调整方法是动态帧时隙Aloha算法中改进的主要方面。本文通过对二项分布和Hash函数的研究与分析，将两者相结合，克服了标签随机选择时隙的随机性误差，采用精准的标签估算方法，加快了读写器识别标签的速度。仿真表明，算法能够有效减少识别过程所需的总时隙数、空时隙数和碰撞时隙数，从而提高系统的识别效率，具有较大的实际应用价值。

    [参考文献]

    [1]游战清，李苏剑.无线射频技术（RFID）理论与应用[M].北京：电子工业出版社，2004.

    [2]谢磊，殷亚凤，陈曦，等.RFID数据管理：算法、协议与性能评测[J].计算机学报，2013（36）：457-470.

    [3]王雪，钱志鸿，胡正超，等.基于二叉树的RFID防碰撞算法的研究[J].通信学报，2010（31）：49-57.

    [4]徐圆圆，曾隽芳，刘禹.基于ALOHA算法的帧长及分组数改进研究[J].计算机应用，2008（28）：588-590.

    [5]梁彪，郑勇鑫，王玉莹，等.基于模运算标签分类的RFID标签防碰撞识别方法[J].无线互联科技，2014（2）：56-58.

    [6]张虹，韩磊，马海波.Hash-tree反碰撞算法[J].计算机工程，2007（33）：67-69.

    [7]陆端，王刚，闫述.改进ALOHA算法在RFID多目标识别中的应用[J].微計算机信息，2006（22）：231-233.

    [8]陈毅红，冯全源.基于捕获效应的预约时隙分配RFID防碰撞协议研究[J].计算机学报，2015（38）：2375-2389.