动态帧时隙算法的研究与改进

2011-10-17张玉茹陈德龙李彬彬

哈尔滨商业大学学报（自然科学版） 2011年6期

关键词：发送数据读卡器读写器

张玉茹，陈德龙，李彬彬

(哈尔滨商业大学计算机与信息工程学院，哈尔滨150028)

防碰撞算法是解决标签碰撞问题(在读写器的作用范围之内有多个标签同时向读写器发送数据，信号之间产生干扰，导致读写器无法正确的识别出标签)的核心方法[1-2].

随机标签防碰撞算法具有识别标签速度快，受系统中标签数目影响小等优点[3-5].本文通过对随机标签防碰撞算法的研究与分析，对动态帧时隙算法进行了分集改进，提高了算法的性能.

1 随机标签防碰撞算法的分析

1)ALOHA算法

在ALOHA算法中，标签周期性的发送数据给读卡器，直到所有标签都完成发送数据给读卡器后，整个重复周期才停止.缺点是数据发送过程中碰撞发生的概率很大.

2)时隙ALOHA算法

时隙ALOHA是在ALOHA算法的基础上进行改进的，该算法的吞吐量是ALOHA的2倍.在该算法中，标签只能在每个时隙的开始发送数据给读卡器，时隙的多少和起始时间由读卡器所控制.因此，碰撞发生的时间间隔只有ALOHA的1/2.缺点是需同步时钟，标签可计算时隙.

3)帧时隙ALOHA算法(FSA)

帧时隙ALOHA算法是在时隙ALOHA算法的基础上改进的，该算法将通信信道被分为若干个帧，每帧又分割为若干时隙.标签在一个数据帧之内只能选择一个时隙进行数据的传输，可以获得较理想的标签平均读写时间.缺点是帧长度固定，实际应用中难以取得较理想的吞吐率.

4)动态帧时隙ALOHA算法(DFSA)

该算法与FSA算法相似，惟一不同之处在于:该算法中，帧长度并不固定，而是会随标签个数动态改变.FSA与DFSA的仿真图如图1、2所示.

由图1、2可知，识别相同数量的标签，DFSA所需要的时隙数远远小于FSA算法所需要的时隙数.

通过对ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法以及DFSA算法相比较，可以看出算法的性能正在逐步提高.为了进一步提高算法性能，对动态帧时隙法进行了改进，提出了一种分集改进方法.

2 算法的改进

分集改进方法中每个标签都增加一个计数器flag，flag值为0或1，表示分集编号.当阅读器发送识别命令时，发送包含参数F、Flag两个参数(F为帧长，Flag为选择分集编号).当标签获得到的Flag值与标签本身计数器Flag值相等时，进入识别状态，而不相等的标签则等待下次的查询.具体算法流程如下.

1)初始化参数:

2)阅读器发送读取命令:标签收到阅读器识别命令后，符合条件flag=Flag的标签进入识别状态，进入识别状态的标签随机选择一个时隙进行发送.

3)阅读器接到的回复可能被判断为以下3种情形.

①识别:识别计数加1，nr++;

②碰撞:碰撞计数加1，nc++;

③无信号:空计数加1，nk++;

任意情况下，阅读器时隙计数减1，即Slot--.

4)判断Slot的值是否为零:

①是:继续判断nc是否为零

a是:结束本次识别周期.

b否:调用帧长调整子程序，估计未识别标签数目，重新设定帧长.

②否:继续下一时隙的检测与识别.

分别动态帧时隙法和改进后的动态帧时隙法进行Matlab仿真，并对数据进行分析，如表1、2、3所示，其中D代表这动态帧时隙算法，G代表改进后的算法.

表1 帧长为4时改进算法与FSA对比

表2 帧长为8时改进算法与DFSA对比

表3 帧长为8时改进算法与DFSA对比

表1、2分别显示了在标签从1增加到50时，得到所需要的时隙数目的平均值(共采集7次)，且初始化帧长分别为4和8.表3是标签数从1增加到100时所得到时隙的平均值，帧长为16.从表中数据可得到，n代表标签数量.当帧长为4，11＜n＜18时;当帧长为8，18＜n＜34时;当帧长为16，40＜n＜70时，改进的算法比动态帧时隙算法所用的时隙数要少，而在范围外，则比动态帧时隙算法所用的时隙数要多.

根据以上数据分析可知，标签的数量范围在3f0～4f0之间时(即标签估算数量，3f0＜Fw＜4f0)，则采用分集改进方法，算法流程如图3所示.