基于CSMA/CD改进的混合RFID防碰撞算法

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

(西藏大学，西藏 拉萨 850012)

0 引 言

计算机通信除了传送数据外，它还进行数据交换、实时监测和数据处理等。但主要是以数据传输为基础，并与计算机相关技术紧密联系。而“射频识别技术”(radio frequency identification,RFID)是一种依赖于计算机技术的非接触式自动识别以及读取相关数据的技术，主要通过无线电信号识别特定目标并读写相关数据。它具有耐高温、使用寿命久、读写性能优越、存储数据容量大和存储信息易更改等优点。RFID系统主要由三部分组成：电子标签、读写器和系统高层。其中读写器不仅要对电子标签做出应答响应，还要实时处理数据信息。数据处理主要由系统高层解决，也就是计算机网络系统。读写器通过标准接口与计算机网络连接，再由计算机网络完成数据处理、传输和通信的功能。

RFID系统广泛应用在众多领域，如家禽养殖业、加工零售业和交通运输业等[1]。但在实际应用中，当多个电子标签同时响应读写器的应答命令时，它们之间建立的共享信道可能会发生冲突即标签碰撞，形成无效传输。若碰撞次数过多，会大大降低信道的利用率，而且影响RFID系统整体的工作效率。目前解决标签碰撞的算法有二进制确定性算法、ALOHA概率性算法和它们的混合改进算法[2-5]。文献[4]中列举了基本的防碰撞协议，而文中基于数据链路层中的TBEB和CSMA/CD[6]协议提出了一种改进算法，提高了首次未识别标签被成功识别的概率。

1 CSMA/CD和截断二进制指数退避算法

“载波侦听多路访问/冲突检测(carrier sense multiple access/collision detection，CSMA/CD)”协议[7-9]是一种分布式介质访问控制协议。CSMA/CD应用在OS17层里的数据链路层，基本工作原理：在发送数据包之前监听共享信道是否处于空闲状态，只有介质处于空闲状态时，才可以被允许发送数据帧。此时，如果有两个或两个以上的站同时监听到介质处于空闲状态且发送帧时，则会产生数据冲突现象，那么发送的数据帧就变为一个无效帧，发送失败。如果检测到站发生冲突，应该立即停止发送，避免造成因传送无效帧而使得介质带宽浪费的现象。随后延时一段时间，再重新争用介质，重新发送数据帧。这样就会有效提高数据传输效率，从而大大减小失传率。

算法流程如下：

(1)待传送帧排队等待；

(2)进行信道监听。如处于空闲状态，立即发送数据并返回(1)；

(3)若信道处于“忙”，继续监听信道，直到信道处于空闲状态时再次传送数据。

把上述协议应用在RFID标签通信中时，需增加发射干扰信号的硬件装置，也就是产生脉冲信号等。以便在监听阶段，同时监听到多个标签时，可以发射干扰信号，强化标签碰撞，有效缩短标签排队等待被识别的时间。完成上述识别过程后，仍会有部分标签无法成功识别，这时不再发送数据包，而是将标签随机退避一个时间段来降低二次重传时发生冲突的概率，即“截断二进制指数退避算法(truncated binary exponential backoff，TBEB)”[10-13]。二次重传时间由TBEB算法来确定，算法流程如下：

(1)碰撞发生后，退避时间规定为2σ。

(2)从整数集[0,1,…,(2k-1)]中随机选取一个整数作为退避时间，记为r，后续重传时间是r的倍数。其中k=min[b,10]，b为重传次数，重传次数不超过10。例如，第二次重传时，k=2,随机数r从整数[0,1,2]中选择一个，其重传时间为从0,2σ,4σ和6σ中随机选择一个。

(3)当重传次数达到16次时，发送仍无法成功识别，则放弃。

上述协议在有线以太网中应用广泛，具有较强的稳定性和可靠性。可以把上述协议的思想借鉴于射频识别技术，只是需要在硬件电路中增加额外的硬件装置来产生电子标签碰撞的干扰信号，这样就可以有效缩短标签排队等待所消耗的时间。

2 ALOHA算法

ALOHA是在“时分多址(time division multiple access,TDMA)”的基础上衍生出来的，用于解决标签识别中多标签碰撞问题的算法。改进算法包括纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法和动态帧时隙ALOHA算法等[14-15]，它们在识别时间和识别效率上都有提升。

2.1 纯ALOHA算法

纯ALOHA算法是最基本的防碰撞算法，当多个标签进入读写器感应范围内且在不同的时间内发送数据包时，会发生如图1所示的部分碰撞和完全碰撞。

图1 纯ALOHA算法碰撞示意图

由于识别过程中，单位时间内标签应答数服从泊松分布，故在时间t内随机发送数据帧时，有n个标签应答的概率为：

(1)

其中，λ表示单位时间内标签出现的次数；G=λt表示识别过程中的数据包交换量。

那么在碰撞周期2T内无其他标签应答响应的概率为：

p(n=0)|t=2T=e-2G

(2)

由式(2)可得纯ALOHA算法的吞吐率为：

S=G·[p(n=0)|t=2T]=G·e-2G

(3)

当G=0.5时，识别效率达到18.4%，如图2所示，识别效率相对较低。

图2 纯ALOHA算法数据交换量和

2.2 时隙ALOHA算法

时隙ALOHA算法在纯ALOHA算法的基础上把时间长度划分为离散的时隙间隔，而碰撞周期缩短为T，这样每个时隙间隔中将会出现碰撞、成功识别和空闲三种情况。由式(2)可得，时隙ALOHA算法的吞吐率为：

S=G·[p(n=0)|t=T]=G·e-G

(4)

其中，当G=1时，识别效率达到36.8%。

图3为两种算法平均数据包交换量与吞吐率的变化曲线，相对于纯ALOHA算法的识别效率(18.4%)有明显提高，但需要时钟同步且对时隙长度的划分更加精细。

图3 两种算法数据交换量与吞吐率的关系曲线

2.3 帧时隙ALOHA算法

在时隙ALOHA算法的基础上，把多个时隙划分组合成一帧，每一帧中随机接受标签发送的数据包即帧时隙ALOHA算法。假设时隙ALOHA算法中帧长数目和标签的数目分别为F和n，由于一个标签占用某个时隙的概率服从二项分布，那么m个标签选择同一个时隙的概率为：

(5)

由式(5)可得，一帧中分布有m个标签的时隙数的期望值为：

(6)

当m=1时，表示时隙中只有一个标签处于应答状态，则成功时隙数的期望值为：

(7)

当m=0时，表示时隙处于空闲状态，则空闲时隙数的期望值为：

(8)

当m>1时发生碰撞，则发生碰撞时隙数的期望值为：

(9)

由式(7)可得成功识别的概率为：

(10)

对上式进行微分计算可得：

(11)

由式(11)可得，当F=n时，即标签数等于帧长数，读写器的吞吐效率达到最优。

(12)

由式(12)可知，帧时隙ALOHA算法的识别效率达到36.8%。

图4为不同帧长下对应的标签数目与吞吐率的关系曲线，五条曲线分别对应的帧长数为256、128、64、32和16，其中曲线的最高点均是在标签数量和帧长数目近似相等的条件下达到的。此时，系统的识别效率达到最佳。

图4 时隙ALOHA标签数目与吞吐率的关系曲线

要使RFID系统的识别效率达到最大，帧长度必须和等待被识别的标签数目近似相等。各种改进算法中对标签数目的估计提出了一些有效的改进措施，文献[16-17]中介绍了一种估计标签数的方法，可以比较准确地估计出标签数目。近似估计标签数目的表达式如下所示：

Ntags=2.39*Ck

(13)

其中，Ntags表示待估计标签的数目；Ck表示在一帧中发生碰撞的总时隙数。

3 改进新型混合算法

改进的混合算法中首先判断标签数目是否大于256，若大于256，则需要对标签数进行分组处理，使得标签数量和帧长数近似相等，达到系统可识别的最大识别度。然后通过时隙ALOHA算法完成首次识别，减少电子标签发生冲突的次数。此时，仍有不确定数量的未成功识别标签。通过载波监听/冲突检测机制，即边发送边监听信道来缩短碰撞时间，使电子标签有充足的退避时间，更合理地执行截断二进制指数退避算法，循环上述过程直到所有标签被识别。

算法主要步骤为：

(1)判断标签数目是否大于256，若大于256，标签进行预处理分组，否则执行步骤(2)；

(2)标签开始向读写器发送消息，进行识别，称之为多路存取，完成首次识别；

(3)经过一轮查询后，将统计成功识别的时隙数目记为ω；

(4)根据ω/F≥ε(0.5<ε<1)进行判断，如果ε介于0.5和1之间，说明成功识别的标签数目较多，此时执行截断二进制指数退避算法进行二次识别，否则执行步骤(5)；

(5)进行信道检测，如果信道处于空闲状态，立即发送标签；

(6)反之加强信道干扰，提前结束碰撞，进入TBEB进行二次识别；

(7)直到剩余标签通过CSMA/CD和TBEB完全识别，结束算法，否则执行步骤(2)。经过时隙ALOHA算法完成首次识别，剩余标签由CSMA/CD和TBEB联合进行二次识别，标签即可在最短的时间内完成识别。

混合算法流程图如图5所示。

4 仿真结果与分析

改进的混合RFID防碰撞算法中，首先判断标签的数目，在标签数目小于指定数量时，通过时隙ALOHA算法完成首次识别，否则进行分组处理。之后未识别的标签通过载波监听/冲突检测机制来增强碰撞干扰，缩短碰撞时间。在载波监听/冲突检测和截断二进制指数退避作用下大大缩短了碰撞时间。

图6为改进混合算法和时隙ALOHA算法的标签数和吞吐率的性能比较，在最大分组帧长数256处对应的标签数大约为256，即就是标签数和帧长数相等，重传效率达到39.1%，相比时隙ALOHA算法的吞吐率(36.8%)有所改进。

图5 混合算法流程

图6 两种算法中标签数和吞吐率的关系曲线

时隙ALOHA算法中只是对未识别顽固标签进行重复识别。改进算法的初始阶段,由时隙ALOHA算法完成，在后续识别阶段，改进算法在载波监听/冲突检测和截断二进制指数退避算法的作用下降低了重传次数。同时，当两种算法处于相同的吞吐率情况下，改进算法所需的识别时间明显小于时隙ALOHA算法的识别时间。

5 结束语

在时隙ALOHA算法的思想上，结合载波监听/冲突检测和截断二进制指数退避算法机制，提出了一种基于CSMA/CD的混合RFID防碰撞算法，引入二次重传机制。相比时隙ALOHA算法，标签信息吞吐率较高。后续可以根据标签数目变化动态地改变帧长，进一步缩短截断二进制指数退避时所消耗的时间。

此外，RFID新的防碰撞算法可能将会深入到RFID网络物理层(频率、信号调制和数据加密)和数据链路层的特性。在无线协同网络层可以实现信息编码，由此可以更好地实现分集性能，有效提高信息的传输速率，同时具有较低的硬件损耗。而在数据链路层中可以将数据信息自适应组合，并调节发送速率使得与接收端相匹配，使得防碰撞算法结合计算机协议思想得到更好的改进，充分提高RFID系统的工作效率。

[1] ULLAH S,ALSALIH W,ALSEHAIM A,et al.A review of tags anti-collision and localization protocols in RFID newworks[J].Journal of Medical Systems,2012,36(6):4037-4050.

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

[3] 王 勇,李 婷.改进的基于ALOHA的RFID防碰撞算法[J].电信科学,2016,32(8):77-81.

[4] DEMIRKOL I,ERSOY C,ALAGOZ F.MAC protocols for wireless sensor networks[J].IEEE Communications Magazine,2006,44(4):115-121.

[5] KLAIR D K,CHIN K W,RAAD R.A survey and tutorial of RFID anti-collision protocols[J].IEEE Communication Surveys and Tutorials,2010,12(3):400-421.

[6] GALLAGER R G. A perspective on multiaccess channels[J].IEEE Transactions on Information Theory,1985,31(2):124-142.

[7] 李宝山,乔 聪.基于P-坚持CSMA提高RFID系统吞吐率的改进算法[J].计算机测量与控制,2013,21(12):3322-3324.

[8] 马 纯,尹小燕,房鼎益,等.退避算法多负载状况下的退避窗口最优设定[J].计算机应用研究,2015,32(1):175-178.

[9] CHEN Xiaoming,HONG Geok-Soon.A simuliation study of the predictive p-persistent CSMA protocol[C]//Proceedings of the35th annual simulation symposium.Washington,DC,USA:IEEE Computer Society,2002.

[10] 蒋子峰,陆建德.IEEE802.15.4动态自适应CSMA/CA算法设计与仿真[J].计算机技术与发展,2010,20(9):69-73.

[11] 黄 仁,郜 辉,任军华.非时隙CSMA/CA性能分析与研究[J].计算机工程与应用,2009,45(7):108-110.

[12] 何 伟,南敬昌,潘 峰.改进的动态p-坚持CSMA协议[J].计算机工程,2010,36(21):118-120.

[13] 苏恒阳,谭英丽.改进的RFID动态帧时隙ALOHA算法[J].计算机仿真,2011,28(8):148-152.

[14] 钱东昊,张 琨,张 磊.基于标签识别码分组的防碰撞算法研究[J].计算机应用与软件,2015,32(7):252-254.

[15] 高金辉,郑晓彦.新型的RFID混合防碰撞算法[J].电子技术应用,2011,37(12):130-132.

[16] SCHOUTE F C．Dynamic frame length ALOHA[J]．IEEE Transactions on Communication，1983，31:565-568．

[17] CHA J Y，KIM J Y．Novel anti-collision algorithms for fast object identification in RFID system[C]//Proceedings of the11th international conference on parallel and distributed systems．Washington,DC,USA:IEEE Computer Society,2005:604-609．