一种新的时隙ALOHA算法

赵晓霞, 昂志敏, 郭 治

(合肥工业大学计算机与信息学院,安徽合肥 230009)

无线射频技术(radio frequency identification,简称RFID)因具有识别距离远、穿透力强、多物体识别及抗污染等优点,近年来得到不断的发展和进步,现已广泛应用于工业自动化、商业自动化、交通运输控制管理、门禁保安及防盗等众多领域,成为当前IT行业研究的热点技术之一。

射频识别系统一般由阅读器(Reader)、标签(Tag)和后端数字处理系统构成。因为所有的标签工作在同一个频率,当有多个标签同时回复阅读器时就会发生数据碰撞,造成数据传输错误,因此需要制定相应的防碰撞算法来解决冲突问题。目前用于解决冲突问题算法的多址技术都是基于时分多址(TDMA)的,其中包括二进制树算法和ALOHA算法,以及对这2种算法的改进算法,但还是不能很好地解决大量标签存在时产生的冲突问题。

基于以上原因,本文提出了一种基于码分多址技术(CDMA)的二维时隙 ALO(C-S-ALOHA)[1]的防碰撞算法,并采用m序列作为扩频码。作为一种二维算法,它有效地改善了多标签的冲突问题,提高了吞吐量。文中还给出了数学分析和仿真结果。

1 C-S-ALOHA算法描述

1.1 CDMA技术

CDMA技术是通过不同的扩频序列码来识别不同的用户,即各用户可以在同一工作频段选用不同扩频码来发送信息而互不干扰。具有抗干扰性好、带宽动态分配、保密性和可扩展性好等优点。其中,扩频序列码是CDMA技术的关键,常用的扩频码有m序列、gold序列和walsh码等,其中m序列是扩频系统中应用最广的扩频码,具有编码简单、易于产生的优点。

文献[2,3]选用的walsh码作为RFID系统中的扩频码,但当扩频码长较大时,若选用walsh序列,会有较长的连0连1,这对系统的位同步是不利的。正交扩频系统若采用特性优良的m序列做扩频码,不但编码简单,而且可以增加系统抗突发错误的能力,日益受到业界的推崇,因此本文选用了m序列。

m序列(又称最大长度线性移位寄存器序列)具有良好的伪随机特性,常用作扩频通信系统的扩频码字,由于生成多项式相同的不同m序列是彼此正交的,具有处处约为0的互相关特性和尖锐的自相关特性,故亦可构成正交码扩频系统中的正交码集。

m序列的产生方法：n级线性移位寄存器,经过适当的抽头反馈和模2加法器,能产生序列的最大可能周期是p=2n-1的序列[4]。

1.2 S-ALOHA技术

时隙ALOHA算法[5]是在ALOHA算法的基础上把时间分成多个离散时隙,每个时隙长度T等于标签的数据帧长度,标签只能在每个时隙的分界处才能发送数据。每个时隙存在以下3种情况：

多机器人协同系统在汽车焊接生产线中的应 用 …………………………………………… 钟 平，李华雄（31）

(1)无响应时隙：在此时隙内没有标签发送。

(2)识别时隙：在此时隙内只有1个标签发送,标签被正确识别。

(3)冲突时隙：在此时隙内多个标签发送,产生冲突。这样标签或成功发送或完全冲突,避免了原ALOHA算法中的部分冲突,使冲突期减少1/2,提高了信道的利用率。但是这种方法需要一个同步时钟以使读写器阅读区域内的所有标签的时隙同步。

设T为单个标签完成发送自身ID号的时间,负载G为T时间内某个阅读器认识范围内标签平均到达数量,吞吐量S为T时间内某读写器成功完成通信的标签数量。则时隙ALOHA算法的吞吐量计算公式为：

当G=1时,吞吐量达到最大值,max(S)=e-1=0.368;当G ＞1时,系统处于不稳定状态,当大量标签存在时则不满足需要。

1.3 码分时隙ALOHA算法(C-S-ALOHA)

基于CDMA时隙ALOHA算法是在CDMA信道上使用时隙ALOHA技术,而传送的信息可以在时域和码域上进行二维检测,如图1所示。

图1 二维数据传输模型

在C-S-ALOHA算法中,若每个发送用户有唯一的扩频码字,不同的发送方使用不同的扩频码字以时隙ALOHA方式发送信息,则称为基于发送方的扩频传输协议(T-SSA),它的特点是没有码字选择的冲突;若系统中的码字总数受限于接收方的解调器,各个发送方需竞争码字传送信息,则称为基于接收方的扩频传输协议(R-SSA),它的特点是可以节省码字数,减少码字的同步时间,但有可能出现码字竞争冲突[6]。在RFID系统中基于对硬件电路复杂度的考虑,选取基于接收方的扩频传输协议。即在读写器中存储有限数量的正交码组,在每个标签中存储2组数据：自身的ID号和随机写入的一组正交码。

由于扩频码的数量有限,必然会有不同的标签选用相同正交码,在所有标签取得同步的基础上,标签同时发送 ID号时必然会发生碰撞(见图1)。

图1中,在第3个时隙,有3个标签同时选用了码字4,则发生碰撞,这时仍然采用S-ALOHA算法中的随机退避机制达到识别目的,但只要选用不同的码字就可以在1个时隙传输2个以上标签,图1在时隙1和时隙5读写器接收到这些重叠的信号也能完整地分离出各个标签的ID号,有效地改善了系统的吞吐量。系统的实现也较简单,仅需要在标签中增加1组正交码和相应的扩频电路,在读写器中存储有限数量的正交码组。在基于S-ALOHA算法的电路上变动不大,具有实际意义。

2 C-S-CDMA算法的数学分析

由于所有标签的ID号是互异的,当其选用不同的扩频码发送ID号,或者选用相同的扩频码在不同的时隙发送,才可以成功地被读写器经解扩获得,而不同的标签选用了相同的扩频码且在同一时隙发送仍将会导致标签碰撞[7]。

假设CDMA时隙ALOHA接入系统每次可分配的扩频序列码为N个,以0,1,…,N-1标识这些扩频序列码。假设某时隙内第i个标签使用第Rn个扩频码(Rn是一个随机整数0≤Rn≤N-1)发送自身ID号。而当这一时隙中有其它标签使用同一个扩频码发送ID号时,就会产生冲突,信息就不可能被正确接收。因为标签发送自身ID号所用的扩频码可以看成均匀分布在[0,N-1]之间(即假设一个阅读器范围内的标签是均匀分布的),则一个标签在该时隙中使用某个扩频码发送的概率为：

如果在时隙 T内有K+1个标签发送自身ID号,则另外K个标签与第i个标签没有使用同一个扩频码的概率[8]为：

根据假设条件,一个阅读器区域内标签数目足够多,可以把初始接入信息到达过程看作是Poisson过程,则在一个时隙内有K个标签信息到达的概率为：

在每个时隙的开始处,假设一个阅读器区域内欲发送的接入信息有K+1个,且至少有N个接入信息能被阅读器接收到。对某个标签发送的信息,另外K个标签被看作为干扰。设Pc(K)是在K个干扰下一个标签的信息被成功捕获和恢复的概率,平均信道吞吐量S是每个时隙内成功发送被阅读器成功收到的平均信息数目,它可以表示为：

在CDMA时隙ALOHA系统中,假设不考虑多址干扰和忽略高斯白噪声,则 Pc(K)=P(K),同时在C-S-ALOHA接入系统中,不同的扩频码序列总有一个接收机在前端控制器中,则S(G)又可以表示为：

对(6)式求导数,并令其导数为零。即令∂S/∂G=0,当 G=N,吞吐量取最大 值,即max(S)=N/e=G/e,可见C-S-ALOHA算法的吞吐量是与扩频码阶数成正比的,是S-ALOHA算法的最大吞吐量0.36的 N倍。由于受硬件电路的影响,扩频码阶数是有限的,并不能通过无限增大扩频码阶数来提高系统的吞吐量。

3 计算机仿真结果及分析

为了验证本文提出的算法,在Matlab环境下进行了仿真[9],仿真条件是标签分布服从Poisson分布。分别仿真了 N=1的C-S-ALOHA算法吞吐量,即S-ALOHA算法理论所能达到的最大吞吐量,验证了算法的最大吞吐量约为0.36,如图2所示。

图2 N=1时C-S-A LOHA算法的吞吐量

对不同阶数的扩频码的吞吐量进行对比,如图3所示,实验表明：

(1)当N＜G时,标签的吞吐量S与负载G成正比。

(2)当N=G时,标签的负载G达到极值。

(3)当N＞G时,标签的吞吐量S与负载G成反比,同时也表明阶数越大对于G＞N时所引起的吞吐量的衰减影响越小,此结果与理论分析相符。

S-ALOHA和C-S-ALOHA(N=4)2种算法的吞吐量,如图 4所示。实验结果表明,C-SALOHA算法的吞吐量明显优于S-ALOHA算法。

图3 不同阶扩频码的吞吐量比较

图4 2种算法的比较

4 结束语

本文提出了一种利用m序列作为扩频码的C-S-ALOHA算法,把码分多址技术和时隙ALOHA算法相结合,可以进行时域和码域的二维碰撞检测。理论和实验结果表明：C-S-ALOHA算法的吞吐量明显优于S-ALOHA算法;而且用于传送信息分组的扩频序列码阶数越多,系统的吞吐量越大,当扩频码阶数大于负载时,对于吞吐量衰减影响不大。但由于受硬件电路限制,扩频码阶数不能无限制的增加。与目前流行的S-ALOHA算法相比较,新算法极大地提高了系统的吞吐量,并且采用m序列编译码简单,硬件电路更改不大,具有很好的应用前景。但本文未对时延作出分析,这将是后期研究的方向。

[1]王建伟,赵玉萍,Korhonen T.RFID系统防碰撞协议研究：设计与优化[J].电子与信息学报,2009,31(2)：1-4.

[2]梁 彪,胡爱群,秦中元.一种新的 RFID防碰撞算法设计[J].电子与信息学报,2007,29(9)：2158-2160.

[3]曹小华,陶德馨,李文锋.时隙A LOHA防冲突算法的马尔可夫链模型研究[J].武汉理工大学学报：交通科学与工程版,2007,31(5)：796-799.

[4]邱 庆,张水莲,陈海燕.m序列在双正交码扩频系统中的应用[J].无线电工程,2004,34(8)：58-62.

[5]陈 香,薛小平,张思东.标签防冲突算法的研究[J].现代电子技术通信与信息技术,2006,(5)：13-15.

[6]谢 磊,陈慧芳,仇佩亮.HFC网络CDM A时隙A LOHA接入系统性能分析[J].电路与系统学报,2000,5(3)：6-8.

[7]Liang B,Hu A Q,Qin Z Y.T rends and brief comments on anti-collision techniques in RFID[C]//Proc of the 6th Int Conf on ITS Telecomm,Chengdu,China,2006：241-245.

[8]程 楠,刘志敏,王继新.Ad hoc网络 TDMA分布式动态时隙算法[J].计算机应用研究,2005,(1)：222-225.

[9]刘拓晟,何怡刚,侯再平,等.超高频射频识别的防碰撞算法设计[J].计算机工程,2008,44(36)：87-89.