登录
注册
标签防冲撞ALOHA算法研究
作者：中南民族大学计算机科学学院 喻成 魏亮 李磊
来源：RFID世界网
日期：2007-12-03 10:34:00
摘要：RFID系统中，多标签引起的冲突是影响系统效率的难题。Aloha算法是运用比较普遍的一种防冲突算法，对目前常用的Aloha算法及其衍生算发进行研究，提出优化的标签防冲突算法。
1 引言
射频识别技术(Radio Frequency Identification，RFID)是自动识别技术的一种，近几年发展非常迅速。射频识别技术的工作方式是利用射频方式进行非接触双向通信，以达到识别目标对象并交换数据。同其它自动识别技术相比，射频识别技术有许多特点，如：无需光学可视、非接触、数据存储容量大、并能同时识别大量数据等，因此它可广泛应用到门禁控制、物流跟踪、仓储管理等领域。
2 RFID系统的数据碰撞问题
RFID系统一般由电子标签、读写器以及天线组成。射频识别系统交换的数据存储在电子标签中。电子标签工作的能量供应及与读写器之间的数据交换，都是通过电磁波的无线传输实现的。
RFID系统的基本工作流程是：读写器通过发射天线发送一定频率的射频信号，当电子标签进入发射天线工作区域时产生感应电流，标签获得能量被激活；标签将自身携带的数据编码等信息通过标签内置天线发送出去；读写器接收天线接收到从标签发送来的载波信号，读写器对接收到的信号进行解调和解码，然后送到后台主系统进行相关处理。
RFID系统工作时，经常有一个以上电子标签同时处于阅读器的作用范围内。当这些电子标签同时将自身携带数据传送给读写器时，读写器读取数据就会出现冲突即数据碰撞，这将导致读写器的接收器不能读出数据，降低RFID系统工作效率。在RFID无源标签系统中，目前广泛使用的防冲突算法大都是TDMA(Time Division Multiple Ac—cess)，主要分为2大类：基于Aloha的算法和基于树的算法，本文在分析目前基于Aloha的各种算法特点和Aloha算法所采用的数学模型的基础上，提出自己的改进算法。
3 AL0HA算法
Aloha算法最初用来解决网络通信中数据包拥塞问题。Aloha算法是一种非常简单的TDMA算法，该算法被广泛应用在RFID系统中。这种算法多采取“标签先发言”的方式，即标签一进入读写器的阅读区域就自动向读写器发送其自身的ID，随即标签和读写器间开始通信。
3．1 时隙ALOHA算法
在Aloha算法中，标签通过循环序列传输数据。标签数据的传输时间仅仅为循环时间的一个小片段。在第一次传输数据完成后，标签将等待一个相对较长的时间后再次传输数据。每个标签的等待时间很小。
鉴于以上缺点，研究人员提出时隙Aloha算法¨ 。在该算法中，标签仅能在时隙的开始传输数据。用于传输数据的时隙数由读写器控制，只有当读写器分配所有的时隙后，标签才能利用这些时隙传输数据。因此与纯Aloha算法不同，时隙Aloha算法是随机的询问驱动的TDMA防冲撞算法。
因为标签仅仅在确定的时隙中传输数据，所以该算法的冲撞发生的频率仅仅是纯Aloha算法的一半而且系统的数据吞吐性能却增加一倍。
虽然时隙Aloha算法提高系统的吞吐量，但是当大量标签进入系统时，该算法的效率并不高，因此帧时隙算法被提出。帧时隙算法是将多个时隙打包成为一帧，标签必须选择一帧中的某个时隙向读写器传输数据。这也是帧时隙Aloha算法与纯的时隙Aloha算法的不同点[2]。
在帧时隙Aloha算法中，所有的帧具有相同的长度，即每一帧中的时隙数是相同的且是固定的。由于读写器并不知道标签数量，当标签数量远大于帧时隙数时，一帧中的所有时隙都会发生碰撞，读写器不能读取标签信息；当标签数远小于一帧中时隙数时，识别过程中将有许多时隙被浪费掉。动态帧时隙算法通过根据识别标签的数量来改变帧长度来客服动态帧时隙的不足。
4 改进的动态帧时隙ALONA算法的实现
4．1 算法分析
通常，在帧时隙Aloha防冲撞算法中，当系统标签数量变得很大时，系统效率就开始降低。当读写器设置帧的长度(包含的时隙数)为N，响应的标签数为n，则r个标签在一个时隙中发生碰撞的二项分布的概率是：
4．2 帧长度的改变方法
根据以上的分析，动态帧时隙算法通过动态的调整帧的长度，使帧的长度和未识别的标签的数量接近，使系统的标签识别率达到最大。因此正确的获取当前未识别标签的数据是该算法成功的关键。
目前流行的帧长度调整方法有两种：一种方法是根据前一帧通信获取到的空的时隙数、发生碰撞的时隙数和只有一个标签传输数据的时隙数来估计标签的数量，由估计的标签的数量来调整下一帧的长度；另一种方法是系统每次启动读循环时设定的初始帧长为{2、4、8、16、32、64、128、256}。
为估计RFID标签数量，在第一种方法中引人多址接人通信系统中著名的三重反馈模型。s表示只有一个标签传输其携带数据的时隙数，即数据传输成功的时隙数。E表示没有标签传输数据的空的时隙数。c表示同时有多个标签在传输数据的时隙数，即发生数据包碰撞的时隙数。以上所有的情况都不考虑数据捕获的效率和噪声的影响。
在实际的RFID系统中，被正确识别的标签将不再响应读写器发送的数据传输请求。同样，再下面的算法中，成功传输数据的标签也不在响应读写器的请求。
文献4中，Schout提出了再一帧中选择时隙i传输数据的标签数满足柏松分布_4]，因此一帧中不能被识别的标签数为：I1 =2．93C。此处的c表示发生碰撞的时隙数。
根据4．1节的推导，通过一次读写器的帧周期，容易得到当前帧中s、E、c没有被读取的标签数I1 =I1一S
4．3 改进的动态帧识别流程
根据以上分析，在估计标签数量的过程中根据情况使用上述两种方案综合。
(1)根据具体的应用模式设定初始化的帧大小F，初始化读写器的时隙数slotCount=F；
(2)读写器发送以F为参数的清点指令，等待标签回复，根据收到的回复统计c、E和S；在任何情况下，读写器的时隙数减一：slotCount一一；
(3)判断slotCount是否为零：slotCount为零，进一步判断c是否为零，c为零，结束清点，c不为零，调用帧长度调整子程序重新设定F，返回步骤(1)；slotCount不为零，发送指令，进入下一时隙，返回步骤(3)。
帧长度子程序：
如果是第一次调整帧长度，令F=I1一S；否则比较上次的系统与前次的系统效率，如果上次的系统效率比前次的大，调整帧长度令F=I1一S，反之，调整帧长度F=2．93C。
5 结束语
标签冲突是影响RFID应用系统效率的关键问题之一，动态ALOHA是根据冲突问题本身的数学特性采取的一种RFID的反冲突方法，通过动态的调整帧的大小实现系统读取效率的改善是有效的解决该问题的方法之一。本文综合几种标签估计方法，改进多标签识别流程图，在标签数目较多的时候效率将大幅提高。
参考文献
[1]L．G．Robeas．Extensions of Packet Communication Tech—nology to a Hand Held Personal Terminal，AFIPS Conf．Proc．，Spring Joint Computer Conf．，1 972，vo1．40，295— 298
[2]J．E．Wieselthier，A．Ephremides，and L．A．Michaels．An Exact Analysis and Perform ance Evaluation of Framed ALOHA with Capture[J]．IEEE Transactions on Communi—,cations，1989，vo1．37，125—137·
[3]R．Rom and M．Sidi．Multiple Access Proto —cols／Perform ance and Analysis．Springer—Verlag，47—77，1990．
[4]F．C．Schoute．Dynam ic Frame Length ALOHA[J]．IEEE Transactions on Communications，Apr．，1983，vo1． 31，565—568
[5]R．Du，H．Okada，H．Nakanishi，H．Sanada，and Y．Tezuka． “Perform ance Evaluation and Optimization of ALOHA Scheme with Capture Effect”．Conf．Rec．GLO—BECOM ’87，Nov．，1987，555—56o
[6]陈香，薛小平，张恩东．标签防冲突算法的研究[J]．通信与信息技术，2006(5)：13—15
原文PDF下载
射频识别技术(Radio Frequency Identification，RFID)是自动识别技术的一种，近几年发展非常迅速。射频识别技术的工作方式是利用射频方式进行非接触双向通信，以达到识别目标对象并交换数据。同其它自动识别技术相比，射频识别技术有许多特点，如：无需光学可视、非接触、数据存储容量大、并能同时识别大量数据等，因此它可广泛应用到门禁控制、物流跟踪、仓储管理等领域。
2 RFID系统的数据碰撞问题
RFID系统一般由电子标签、读写器以及天线组成。射频识别系统交换的数据存储在电子标签中。电子标签工作的能量供应及与读写器之间的数据交换，都是通过电磁波的无线传输实现的。
RFID系统的基本工作流程是：读写器通过发射天线发送一定频率的射频信号，当电子标签进入发射天线工作区域时产生感应电流，标签获得能量被激活；标签将自身携带的数据编码等信息通过标签内置天线发送出去；读写器接收天线接收到从标签发送来的载波信号，读写器对接收到的信号进行解调和解码，然后送到后台主系统进行相关处理。
RFID系统工作时，经常有一个以上电子标签同时处于阅读器的作用范围内。当这些电子标签同时将自身携带数据传送给读写器时，读写器读取数据就会出现冲突即数据碰撞，这将导致读写器的接收器不能读出数据，降低RFID系统工作效率。在RFID无源标签系统中，目前广泛使用的防冲突算法大都是TDMA(Time Division Multiple Ac—cess)，主要分为2大类：基于Aloha的算法和基于树的算法，本文在分析目前基于Aloha的各种算法特点和Aloha算法所采用的数学模型的基础上，提出自己的改进算法。
3 AL0HA算法
Aloha算法最初用来解决网络通信中数据包拥塞问题。Aloha算法是一种非常简单的TDMA算法，该算法被广泛应用在RFID系统中。这种算法多采取“标签先发言”的方式，即标签一进入读写器的阅读区域就自动向读写器发送其自身的ID，随即标签和读写器间开始通信。
3．1 时隙ALOHA算法
在Aloha算法中，标签通过循环序列传输数据。标签数据的传输时间仅仅为循环时间的一个小片段。在第一次传输数据完成后，标签将等待一个相对较长的时间后再次传输数据。每个标签的等待时间很小。
鉴于以上缺点，研究人员提出时隙Aloha算法¨ 。在该算法中，标签仅能在时隙的开始传输数据。用于传输数据的时隙数由读写器控制，只有当读写器分配所有的时隙后，标签才能利用这些时隙传输数据。因此与纯Aloha算法不同，时隙Aloha算法是随机的询问驱动的TDMA防冲撞算法。
因为标签仅仅在确定的时隙中传输数据，所以该算法的冲撞发生的频率仅仅是纯Aloha算法的一半而且系统的数据吞吐性能却增加一倍。
虽然时隙Aloha算法提高系统的吞吐量，但是当大量标签进入系统时，该算法的效率并不高，因此帧时隙算法被提出。帧时隙算法是将多个时隙打包成为一帧，标签必须选择一帧中的某个时隙向读写器传输数据。这也是帧时隙Aloha算法与纯的时隙Aloha算法的不同点[2]。
在帧时隙Aloha算法中，所有的帧具有相同的长度，即每一帧中的时隙数是相同的且是固定的。由于读写器并不知道标签数量，当标签数量远大于帧时隙数时，一帧中的所有时隙都会发生碰撞，读写器不能读取标签信息；当标签数远小于一帧中时隙数时，识别过程中将有许多时隙被浪费掉。动态帧时隙算法通过根据识别标签的数量来改变帧长度来客服动态帧时隙的不足。
4 改进的动态帧时隙ALONA算法的实现
4．1 算法分析
通常，在帧时隙Aloha防冲撞算法中，当系统标签数量变得很大时，系统效率就开始降低。当读写器设置帧的长度(包含的时隙数)为N，响应的标签数为n，则r个标签在一个时隙中发生碰撞的二项分布的概率是：
4．2 帧长度的改变方法
根据以上的分析，动态帧时隙算法通过动态的调整帧的长度，使帧的长度和未识别的标签的数量接近，使系统的标签识别率达到最大。因此正确的获取当前未识别标签的数据是该算法成功的关键。
目前流行的帧长度调整方法有两种：一种方法是根据前一帧通信获取到的空的时隙数、发生碰撞的时隙数和只有一个标签传输数据的时隙数来估计标签的数量，由估计的标签的数量来调整下一帧的长度；另一种方法是系统每次启动读循环时设定的初始帧长为{2、4、8、16、32、64、128、256}。
为估计RFID标签数量，在第一种方法中引人多址接人通信系统中著名的三重反馈模型。s表示只有一个标签传输其携带数据的时隙数，即数据传输成功的时隙数。E表示没有标签传输数据的空的时隙数。c表示同时有多个标签在传输数据的时隙数，即发生数据包碰撞的时隙数。以上所有的情况都不考虑数据捕获的效率和噪声的影响。
在实际的RFID系统中，被正确识别的标签将不再响应读写器发送的数据传输请求。同样，再下面的算法中，成功传输数据的标签也不在响应读写器的请求。
文献4中，Schout提出了再一帧中选择时隙i传输数据的标签数满足柏松分布_4]，因此一帧中不能被识别的标签数为：I1 =2．93C。此处的c表示发生碰撞的时隙数。
根据4．1节的推导，通过一次读写器的帧周期，容易得到当前帧中s、E、c没有被读取的标签数I1 =I1一S
4．3 改进的动态帧识别流程
根据以上分析，在估计标签数量的过程中根据情况使用上述两种方案综合。
(1)根据具体的应用模式设定初始化的帧大小F，初始化读写器的时隙数slotCount=F；
(2)读写器发送以F为参数的清点指令，等待标签回复，根据收到的回复统计c、E和S；在任何情况下，读写器的时隙数减一：slotCount一一；
(3)判断slotCount是否为零：slotCount为零，进一步判断c是否为零，c为零，结束清点，c不为零，调用帧长度调整子程序重新设定F，返回步骤(1)；slotCount不为零，发送指令，进入下一时隙，返回步骤(3)。
帧长度子程序：
如果是第一次调整帧长度，令F=I1一S；否则比较上次的系统与前次的系统效率，如果上次的系统效率比前次的大，调整帧长度令F=I1一S，反之，调整帧长度F=2．93C。
5 结束语
标签冲突是影响RFID应用系统效率的关键问题之一，动态ALOHA是根据冲突问题本身的数学特性采取的一种RFID的反冲突方法，通过动态的调整帧的大小实现系统读取效率的改善是有效的解决该问题的方法之一。本文综合几种标签估计方法，改进多标签识别流程图，在标签数目较多的时候效率将大幅提高。
参考文献
[1]L．G．Robeas．Extensions of Packet Communication Tech—nology to a Hand Held Personal Terminal，AFIPS Conf．Proc．，Spring Joint Computer Conf．，1 972，vo1．40，295— 298
[2]J．E．Wieselthier，A．Ephremides，and L．A．Michaels．An Exact Analysis and Perform ance Evaluation of Framed ALOHA with Capture[J]．IEEE Transactions on Communi—,cations，1989，vo1．37，125—137·
[3]R．Rom and M．Sidi．Multiple Access Proto —cols／Perform ance and Analysis．Springer—Verlag，47—77，1990．
[4]F．C．Schoute．Dynam ic Frame Length ALOHA[J]．IEEE Transactions on Communications，Apr．，1983，vo1． 31，565—568
[5]R．Du，H．Okada，H．Nakanishi，H．Sanada，and Y．Tezuka． “Perform ance Evaluation and Optimization of ALOHA Scheme with Capture Effect”．Conf．Rec．GLO—BECOM ’87，Nov．，1987，555—56o
[6]陈香，薛小平，张恩东．标签防冲突算法的研究[J]．通信与信息技术，2006(5)：13—15
原文PDF下载
