时隙ALOHA反碰撞算法在图书馆管理中的应用研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇时隙ALOHA反碰撞算法在图书馆管理中的应用研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：针对图书馆需处理的图书量大，一般的反碰撞算法无法满足图书馆管理的实际需要，故对当前不同的反碰撞算法进行了分析和比较，提出了相对反碰撞效率比较高，并且在ISO/IEC 15693协议中相对容易实现的递减式动态时隙aloha反碰撞算法，以及来解决多标签碰撞问题。仿真结果表明，该算法在同时识别128张标签时依然高效，能够很好地满足图书馆管理的要求。

关键词：射频识别技术； 反碰撞算法； 时隙ALOHA； 效率

中图分类号：TN91134； G250.7 文献标识码：A 文章编号：1004373X(2012)10010304

随着知识经济时代信息量的迅猛增长和对人才需求的不断提高，图书馆已成为继续教育和终身教育的重要基地，也带来了图书馆藏书数量的不断增多，图书馆的功能也已经由传统的“文献中心模式”转变为以读者为中心的“读者中心模式”。当前，在我国的图书馆管理工作中，主要运用条码信息录入与磁条报警系统相结合的管理方式，它具有成本低、操作简单的特点，但也存在局限性，如必须人工借助读写设备进行数据的采集，常因条码、阅读器质量发生误读和拒读等问题影响了借阅效率和服务质量。因此如何有效管理大量的图书，以便更好地为读者服务成为图书馆管理的首要议题。基于射频识别（Radio Frequency Identification，RFID）技术的图书馆管理系统正是在这种背景下提出的。射频识别系统主要包括射频标签(TAG)、阅读器 (READER)和管理系统(PC机)三部分\[1\]。其中射频标签与阅读器之间通过射频天线来实现射频信号的空间耦合。在耦合通道内，根据时序关系，实现能量的传递和数据的交换。但在射频识别系统工作时，可能会有多个的射频标签同时处在阅读器的作用范围内，如果有两个或两个以上的标签同时发送数据，就会导致通信上的冲突。为了防止这些冲突的产生，因此射频识别系统中需要有相应的防碰撞设计。

1 射频识别技术中常用的反碰撞机制

该系统在反碰撞的设计上采用时分多址(TDMA)法\[2\]。即通过使每个标签在单独的某个时隙内占用信道与阅读器进行通信来防止冲突产生，使数据能够准确地在阅读器和标签之间进行传输。具体来说就是每个标签都有一个惟一的UID(64位)号，阅读器通过成功接收每一个UID号来完成对每张标签的识别，如何在最短的时间内将所有的UID号识别出来就是反碰撞算法。常用的标签反碰撞算法主要有ALOHA法、\[3\]时隙ALOHA法。

1.1 ALOHA法

所有多路存取方法中最简单的方法是ALOHA法。这种算法是采取“标签先发言”的方式，即标签一进入阅读器的作用区域就自动向阅读器发送其自身的信息，并在一个周期性的循环中将这些数据不断地发送给阅读器直到数据被阅读器接收。数据传输时间只是重复时间很小的一部分，并且在传输之间产生相当长的间歇，所以存在着一定的概率使得两个标签可以在不同的时间段内传递数据，此时数据包不互相冲突。但各个标签随机地在某个时间点上发送信息，标签在发送完信息后等待随机长时间再重新发送信息。假设一帧信息发送的时长为T0，起始时间为t0，当另一帧的起始时间t1满足t0－T0≤t1≤t0+T0时碰撞将会发生，其碰撞周期为2T0。ALOHA反碰撞算法建立在标签随机发送UID的基础上，所以产生碰撞的机率较大，处理碰撞的效率相对来说比较低。下面对ALOHA反碰撞算法的性能进行分析\[4\]：设吞吐率为S代表有效传输的实际总数据率；输入负载为G表示发送的总数据率。则吞吐率S可以表示为输入负载G与传送成功率P的乘积，其中P是到达的标签能成功完成通信的概率。由概率论知识可知，每秒钟发送的信息帧的数目服从泊松分布，因此t秒钟发送n个数据帧的概率为:P(n)=(λt)ne-λtn！

(1)式中λ为每秒钟平均发送的总的信息帧数，此时输入负载为:G=λt

(2) 因此在碰撞周期2T0内没有发送信息的概率和吞吐率可表示为:P(n=0)t=2T0=e-2λT0=e-2G

(3)

S=2Ge-2G

(4) 吞吐率S与输入负载之间的关系如图1所示。当输入负载G=0.5的时候吞吐率S达到最高为0.183。即此时的信道利用率达到最高的18.3%，然而当负载G逐渐增大的时候(即标签数增多)识别过程中发生碰撞的概率就会随之大大增加，导致反碰撞性能急剧下降，因此只适用于标签数量不多的场合。

图1 ALOHA法吞吐率S与输入负载G关系图1.2 时隙ALOHA法

时隙ALOHA法\[5\]是在ALOHA法基础上改进而来的，是基于阅读器先发言的驱动方式。相比ALOHA法，时隙ALOHA法要求射频标签有一个随机数生成器，可以生成一个随机数用来选择发送的时隙数，只有在选定的同步时隙频标签才会传输数据包。在这种情况下，射频标签仅仅在自身随机的时隙段中传递数据包，因此碰撞率降低，反碰撞的效率得到提高。

时隙ALOHA反碰撞算法通过阅读器使标签的应答同步，避免了ALOHA法的部分碰撞，使碰撞周期从2T0减半为T0，因此在反碰撞效率上明显高于ALOHA反碰撞算法。根据式(1)~(4)可以得到:S=Ge-G

(5) 求导可知当G=1时，吞吐率S达到其最大值0.368，即信道利用率达到36.8%。相比ALOHA算法，在标签识别速度方面提高了近一倍，因此在运用中相当广泛。目前在实际运用中这种算法有很多种优化，通过根据标签数不同而改变时隙数目来使识别效率保持高效的动态时隙ALOHA法就是其中一种。

动态时隙ALOHA法和时隙ALOHA法基本相同，只是在时隙数的选取中视具体情况而定。事实上时隙数的选取对反碰撞算法在效率上有很大影响，在时隙数少的情况下，射频标签选择同一个时隙发送数据的概率增大，因此容易产生碰撞。为了避免大量碰撞发生，需要准备足够大量的时隙。然而这样反而降低了反碰撞算法的性能。因为所有时隙段的持续时间与可能存在的标签数有关，对于只有一个标签存在的特殊情况，过多的时隙数难免造成浪费。弥补的方法是创建动态的时隙，即当识别范围内的标签数相对较多时，提供相对多的时隙数，当识别范围内的标签数相对较少时提供相对少的时隙数，从而达到优化算法的目的。这就是动态时隙ALOHA法，理论上具有比时隙ALOHA法更高的反碰撞效率。