论文部分内容阅读
[摘 要] 标签防碰撞是RFID系统中的一个非常重要的研究方向．文章对EPC Gen2标准和ISO 18000-6标准的TypeA中所采用的DFSA算法中的标签数目估计方法进行了对比研究，得出几种方法的评估结果，从而为动态帧长度的调整提供依据．
[关键词] 射频识别 防碰撞 动态帧时隙算法
[Abstract] Tag anti-collision is a very important research in RFID system.Several tag estimation methods are proposed for DFSA algorithm which was used in both EPC Gen2 Standard and ISO 19000-6 TypeA Standard. Comparative study of these methods obtain assessment result,providing a guide for framesize adjusting.
[Keywords] RFID anti-collision DFSA algorithm
1.引言
在沃尔玛等国际企业的带动下，超高频射频识别（RFID）技术的应用进入了高速发展阶段，标签防碰撞问题成为RFID系统中一个非常重要的研究方向。对于RFID标签防碰撞技术，可以从硬件、软件两种途径来实现[1]。硬件实现就是采用多址识别技术如TDMA，FDMA，CDMA等来实现，优点是时延小，但是以增加系统复杂性和提高成本为代价。目前在RFID系统中一般不采用硬件的方法，国际标准中都是采用软件的方法，主要应用的有基于二进制树的确定性算法和基于ALOHA的非确定性算法。基于ALOHA的算法是随机性算法，在它的基础上产生了时隙ALOHA、帧时隙ALOHA和动态帧时隙ALOHA算法（DFSA算法）等改进算法。其中DFSA算法成为一种非常重要的防碰撞算法，两大国际标准EPC Gen2标准和ISO18000-6标准的TypeA中的防碰撞方案都是基于DFSA算法的。该算法相比与前面的几种算法最重要的优势便是对于帧长度的动态调整，提高了时隙利用率。在DFSA算法中最关键的技术之一就是如何估计标签的数目，为帧长度调整提供依据。因此，文章对DFSA算法中的标签估计方法进行分析，得出几种方法的可靠性评估结果。
2.前提条件
理解标签防碰撞的前提条件是：
（1）标签的数目事先是未知的；
（2）标签的ID号不是连续的；
（3）DFSA算法中由于硬件的限制，一帧时隙数往往只能为2的幂；
（4）为保证系统性能，一帧大小一般不超过256；
（5）标签为无源标签，没有载波侦听功能。
3.最佳的帧长度
帧时隙ALOHA算法的基本原理是[2]：将时间分成很多小时间段，即时隙。多个时隙组成一帧，接收到阅读器的查询命令后，读写范围内的标签随机选择其中一个时隙应答。如果某个时隙中没有标签应答，这个时隙称为空时隙；如果有两个或者两个以上的标签应答，则发生标签碰撞，标签无法被识别，称为碰撞时隙。
识别时隙的个数与帧长度的比值称为传输通路的平均吞吐率。吞吐率越高，系统的识别速度越快。为了获得最大的吞吐率，必须使识别时隙所占的比例最大化。设帧长度为F，阅读器读写范围内的标签数目为N，则某一时隙为空时隙的概率P0、识别时隙的概率P1、碰撞时隙的概率Pc分别为：
图3-1 时隙比例与负载G的关系
图3-1为各种时隙比例与负载G的关系。由以上分析可知，当帧长度F与标签数目N相等，即平均数据包交换量为1时，动态帧时隙算法可以获取最高效率。因此，标签估计的重要任务就是通过一种方法估计未识别标签数目，从而能够据此确定下一帧的长度。
4.标签数目估算方法
4.1 根据碰撞率Pc估算标签数目
由于硬件的限制[3]，一帧时隙数N往往只能为2的幂，而且为保证系统性能，一帧大小一般不超过256。DFSA算法需要估计待识别标签的数目，根据时隙碰撞概率公式：
图4-1 不同标签数目下的时隙碰撞概率理论值
图4-1给出了不同标签数目下的时隙碰撞概率理论值。由上图可以看出，在不同的F下，碰撞概率是随着标签数量的增加而单调递增的，即固定的一帧时隙数F下，碰撞概率与标签数目在理论上存在一一对应关系。由于DFSA算法当前的帧长度大小F是已知的（初始F值为16），只要统计一下当前一帧识别之后碰撞的时隙数S，则可以估算当前帧标签碰撞概率为PC=S/F。根据公式（1），利用查找碰撞概率值表的方法或者逼近计算法，可以估计出当前的标签数N，减去当前一帧正确识别的标签数，就得到近似的剩余未识别标签数目，并依据表4-1动态调整下一帧的帧长。
这种方法，当F比较大时，公式（1）的查找或逼近算法会比较耗费资源和时间，不利于简单小系统的应用。
4.2 简单估算法
CHA J R，KIM J H提出了一种简单的标签数目估计算法[4]。文中指出，在DFSA算法下，系统始终在接近于最高吞吐率情况下工作，因此可近似假设F=N，定义一个时隙的碰撞比率：
因此一个碰撞时隙内平均存在的标签数Ctag为：
只要在一轮的标签识别后，统计出碰撞的时隙数S，则可以估算待识别的标签数为S*2.3922。文章中的仿真结果显示，以上两种标签数目估计方法性能差异不大。
4.3 根据识别率P1估算标签数目
根据切比雪夫定理[6]，可知每个读周期读出的标签和标签总数之比依赖概率收敛到P1。即：
（C1/N）=P1=S，则每一个读周期结束时，期望读出的标签个数为：
由此式，在已知时隙数N和识别的标签数C（阅读器能够纪录已识别的标签数）情况下，可用最小均方差：
(4-5)
来估计现场实际的标签数N。因此，若估计出的标签数N小于当前时隙数F，则减少一帧中的时隙数，若N大于当前时隙数F，则增加时隙数N，使得系统能以最大吞吐率工作。
4.4 利用仿真统计获得的e-pc关系曲线估计标签数目
邓晓等人提出利用e-pc关系曲线估计标签数目的方法[5]，文中设计了帧时隙ALOHA算法仿真及数据分析程序，对碰撞过程中的相关数据进行了统计分析，获得碰撞时隙中平均标签数目e与碰撞时隙比例的关系，为动态调整帧长度，提高识别效率提供依据。统计表明，不同帧长度碰撞时隙中的平均标签数e与碰撞时隙所占比例PC的关系基本相同。
可以利用关系曲线估算出未识别的标签数目，然后动态地调整帧长度，步骤如下：
（1）以帧长度F进行一轮识别后，统计出碰撞时隙个数Fc；
（2）计算Pc=Fc/F；
（3）根据关系曲线获得相应的e值；
（4）估算未识别标签数目nu=e*Fc；
（5）调整帧长度为nu进行下一轮识别。
利用统计的方法获得未识别标签数目估计的曲线，方法比较简单，但在实际应用中受硬件条件的制约，需要考虑一帧的时隙数为2的幂次。
4.5 其他方法
Vogt[7]注意到碰撞大多发生在两个标签之间，于是对空白时隙数目和识别时隙数目做简单的线性组合，就得到标签数目估计。但是这是一个有偏估计。Vogt[8]还给出了另一种误差最小估计方法，该方法力图寻找一个最佳符合所有3种时隙数目观测值的估计结果。这是一个遍历搜索最优结果的方法，计算复杂度较高。赵宏博提出一种新的导数可靠度合并估计方法DRCTE[9]，利用空白时隙、识别时隙、碰撞时隙做出3个初步估计，在合并得到最后估计结果。
5.结束语
各种标签估计方法各有其优缺点，基本都是在空白时隙数、识别时隙数、碰撞时隙数理论的基础上进行估计。普遍存在的问题是要么估算准确度不高，要么计算比较复杂。从准确性的角度来看，利用碰撞时隙比例估算标签数目的误差相对较小，应该选择方法1、4或5。从复杂度小的原则考虑应该选择方法2估计标签数目。在实际应用中，应该根据具体的应用场合，条件及限制选择合适的标签数目估算方法。
参考文献：
[1] 沈宇超，沈树群，王海波，徐大雄.射频识别系统中的防碰撞算法设计[J].电子与信息学报，1999-05-020.
[2] 邓晓，何怡刚，向阳，肖迎群，一种新的RFID标签数目估算方法[J].计算机工程与应用，2008-31-041.
[3] 刘佳，张有光，基于时隙的RFID防碰撞算法分析[J].电子技术应用，2007-05-053.
[4] J. Cha and J. Kim, “Novel anti-collision algorithms for fast object identification in RFID system,” in Proc. Parallel and Distributed System 2005, vol. 2, pp. 63-67.
[5] 邓晓，何怡刚，陈洪云，谢涛，帧时隙ALOHA反碰撞算法仿真及数据分析[J].汕头大学学报（自然科学版），2008-03-010.
[6] 程文青，赵梦欣，徐晶，改进的RFID动态帧时隙ALOHA算法[J].华中科技大学学报（自然科学版），2007-06-005.
[7] Vogt H. Multiple object identification with passive RFID tags // IEEE Proceeding Systems , Man and ybernetics.Yasmine Hammamet , Tunisia , 2002 : 629.
[8] Vogt H. Efficient object identification with passive RFID tags // IEEE Proceeding Pervasive Computing. Los Alamitos , California , 2002 : 992113.
[9] 郭宏博，赵玉萍，一种新的导数可靠度的RFID标签数目估计[J].北京大学学报（自然科学版），2008-05-013.
[10] 赵庆.RFID技术应用领域分析及展望[J] .金卡工程，2005,(9)
[11] 李进东,范琴秀.射频识别技术的发展与应用[J].科技信息(学术版) ，2006,(1) .
[12] 胡一凡. RFID射频识别技术综述[J] .计算机时代，2006,(12) .
[13] 陈邦媛.射频通信电路[M] .第二版，北京：科学出版社，2006：
[14] KRAUS J D, MARHERFKA R J著.天线(上册) [M]，第三版. 章文勋,译. 北京:电子工业出版社，2004：191-193 .
基金项目：
广东省重点引导项目（项目编号：No.2005B10101005）
作者简介:
蔡明(1983-),男，广东省广州市人，助理工程师，学士,主要研究领域为电子技术、计算机科学。
[关键词] 射频识别 防碰撞 动态帧时隙算法
[Abstract] Tag anti-collision is a very important research in RFID system.Several tag estimation methods are proposed for DFSA algorithm which was used in both EPC Gen2 Standard and ISO 19000-6 TypeA Standard. Comparative study of these methods obtain assessment result,providing a guide for framesize adjusting.
[Keywords] RFID anti-collision DFSA algorithm
1.引言
在沃尔玛等国际企业的带动下，超高频射频识别（RFID）技术的应用进入了高速发展阶段，标签防碰撞问题成为RFID系统中一个非常重要的研究方向。对于RFID标签防碰撞技术，可以从硬件、软件两种途径来实现[1]。硬件实现就是采用多址识别技术如TDMA，FDMA，CDMA等来实现，优点是时延小，但是以增加系统复杂性和提高成本为代价。目前在RFID系统中一般不采用硬件的方法，国际标准中都是采用软件的方法，主要应用的有基于二进制树的确定性算法和基于ALOHA的非确定性算法。基于ALOHA的算法是随机性算法，在它的基础上产生了时隙ALOHA、帧时隙ALOHA和动态帧时隙ALOHA算法（DFSA算法）等改进算法。其中DFSA算法成为一种非常重要的防碰撞算法，两大国际标准EPC Gen2标准和ISO18000-6标准的TypeA中的防碰撞方案都是基于DFSA算法的。该算法相比与前面的几种算法最重要的优势便是对于帧长度的动态调整，提高了时隙利用率。在DFSA算法中最关键的技术之一就是如何估计标签的数目，为帧长度调整提供依据。因此，文章对DFSA算法中的标签估计方法进行分析，得出几种方法的可靠性评估结果。
2.前提条件
理解标签防碰撞的前提条件是：
（1）标签的数目事先是未知的；
（2）标签的ID号不是连续的；
（3）DFSA算法中由于硬件的限制，一帧时隙数往往只能为2的幂；
（4）为保证系统性能，一帧大小一般不超过256；
（5）标签为无源标签，没有载波侦听功能。
3.最佳的帧长度
帧时隙ALOHA算法的基本原理是[2]：将时间分成很多小时间段，即时隙。多个时隙组成一帧，接收到阅读器的查询命令后，读写范围内的标签随机选择其中一个时隙应答。如果某个时隙中没有标签应答，这个时隙称为空时隙；如果有两个或者两个以上的标签应答，则发生标签碰撞，标签无法被识别，称为碰撞时隙。
识别时隙的个数与帧长度的比值称为传输通路的平均吞吐率。吞吐率越高，系统的识别速度越快。为了获得最大的吞吐率，必须使识别时隙所占的比例最大化。设帧长度为F，阅读器读写范围内的标签数目为N，则某一时隙为空时隙的概率P0、识别时隙的概率P1、碰撞时隙的概率Pc分别为：
图3-1 时隙比例与负载G的关系
图3-1为各种时隙比例与负载G的关系。由以上分析可知，当帧长度F与标签数目N相等，即平均数据包交换量为1时，动态帧时隙算法可以获取最高效率。因此，标签估计的重要任务就是通过一种方法估计未识别标签数目，从而能够据此确定下一帧的长度。
4.标签数目估算方法
4.1 根据碰撞率Pc估算标签数目
由于硬件的限制[3]，一帧时隙数N往往只能为2的幂，而且为保证系统性能，一帧大小一般不超过256。DFSA算法需要估计待识别标签的数目，根据时隙碰撞概率公式：
图4-1 不同标签数目下的时隙碰撞概率理论值
图4-1给出了不同标签数目下的时隙碰撞概率理论值。由上图可以看出，在不同的F下，碰撞概率是随着标签数量的增加而单调递增的，即固定的一帧时隙数F下，碰撞概率与标签数目在理论上存在一一对应关系。由于DFSA算法当前的帧长度大小F是已知的（初始F值为16），只要统计一下当前一帧识别之后碰撞的时隙数S，则可以估算当前帧标签碰撞概率为PC=S/F。根据公式（1），利用查找碰撞概率值表的方法或者逼近计算法，可以估计出当前的标签数N，减去当前一帧正确识别的标签数，就得到近似的剩余未识别标签数目，并依据表4-1动态调整下一帧的帧长。
这种方法，当F比较大时，公式（1）的查找或逼近算法会比较耗费资源和时间，不利于简单小系统的应用。
4.2 简单估算法
CHA J R，KIM J H提出了一种简单的标签数目估计算法[4]。文中指出，在DFSA算法下，系统始终在接近于最高吞吐率情况下工作，因此可近似假设F=N，定义一个时隙的碰撞比率：
因此一个碰撞时隙内平均存在的标签数Ctag为：
只要在一轮的标签识别后，统计出碰撞的时隙数S，则可以估算待识别的标签数为S*2.3922。文章中的仿真结果显示，以上两种标签数目估计方法性能差异不大。
4.3 根据识别率P1估算标签数目
根据切比雪夫定理[6]，可知每个读周期读出的标签和标签总数之比依赖概率收敛到P1。即：
（C1/N）=P1=S，则每一个读周期结束时，期望读出的标签个数为：
由此式，在已知时隙数N和识别的标签数C（阅读器能够纪录已识别的标签数）情况下，可用最小均方差：
(4-5)
来估计现场实际的标签数N。因此，若估计出的标签数N小于当前时隙数F，则减少一帧中的时隙数，若N大于当前时隙数F，则增加时隙数N，使得系统能以最大吞吐率工作。
4.4 利用仿真统计获得的e-pc关系曲线估计标签数目
邓晓等人提出利用e-pc关系曲线估计标签数目的方法[5]，文中设计了帧时隙ALOHA算法仿真及数据分析程序，对碰撞过程中的相关数据进行了统计分析，获得碰撞时隙中平均标签数目e与碰撞时隙比例的关系，为动态调整帧长度，提高识别效率提供依据。统计表明，不同帧长度碰撞时隙中的平均标签数e与碰撞时隙所占比例PC的关系基本相同。
可以利用关系曲线估算出未识别的标签数目，然后动态地调整帧长度，步骤如下：
（1）以帧长度F进行一轮识别后，统计出碰撞时隙个数Fc；
（2）计算Pc=Fc/F；
（3）根据关系曲线获得相应的e值；
（4）估算未识别标签数目nu=e*Fc；
（5）调整帧长度为nu进行下一轮识别。
利用统计的方法获得未识别标签数目估计的曲线，方法比较简单，但在实际应用中受硬件条件的制约，需要考虑一帧的时隙数为2的幂次。
4.5 其他方法
Vogt[7]注意到碰撞大多发生在两个标签之间，于是对空白时隙数目和识别时隙数目做简单的线性组合，就得到标签数目估计。但是这是一个有偏估计。Vogt[8]还给出了另一种误差最小估计方法，该方法力图寻找一个最佳符合所有3种时隙数目观测值的估计结果。这是一个遍历搜索最优结果的方法，计算复杂度较高。赵宏博提出一种新的导数可靠度合并估计方法DRCTE[9]，利用空白时隙、识别时隙、碰撞时隙做出3个初步估计，在合并得到最后估计结果。
5.结束语
各种标签估计方法各有其优缺点，基本都是在空白时隙数、识别时隙数、碰撞时隙数理论的基础上进行估计。普遍存在的问题是要么估算准确度不高，要么计算比较复杂。从准确性的角度来看，利用碰撞时隙比例估算标签数目的误差相对较小，应该选择方法1、4或5。从复杂度小的原则考虑应该选择方法2估计标签数目。在实际应用中，应该根据具体的应用场合，条件及限制选择合适的标签数目估算方法。
参考文献：
[1] 沈宇超，沈树群，王海波，徐大雄.射频识别系统中的防碰撞算法设计[J].电子与信息学报，1999-05-020.
[2] 邓晓，何怡刚，向阳，肖迎群，一种新的RFID标签数目估算方法[J].计算机工程与应用，2008-31-041.
[3] 刘佳，张有光，基于时隙的RFID防碰撞算法分析[J].电子技术应用，2007-05-053.
[4] J. Cha and J. Kim, “Novel anti-collision algorithms for fast object identification in RFID system,” in Proc. Parallel and Distributed System 2005, vol. 2, pp. 63-67.
[5] 邓晓，何怡刚，陈洪云，谢涛，帧时隙ALOHA反碰撞算法仿真及数据分析[J].汕头大学学报（自然科学版），2008-03-010.
[6] 程文青，赵梦欣，徐晶，改进的RFID动态帧时隙ALOHA算法[J].华中科技大学学报（自然科学版），2007-06-005.
[7] Vogt H. Multiple object identification with passive RFID tags // IEEE Proceeding Systems , Man and ybernetics.Yasmine Hammamet , Tunisia , 2002 : 629.
[8] Vogt H. Efficient object identification with passive RFID tags // IEEE Proceeding Pervasive Computing. Los Alamitos , California , 2002 : 992113.
[9] 郭宏博，赵玉萍，一种新的导数可靠度的RFID标签数目估计[J].北京大学学报（自然科学版），2008-05-013.
[10] 赵庆.RFID技术应用领域分析及展望[J] .金卡工程，2005,(9)
[11] 李进东,范琴秀.射频识别技术的发展与应用[J].科技信息(学术版) ，2006,(1) .
[12] 胡一凡. RFID射频识别技术综述[J] .计算机时代，2006,(12) .
[13] 陈邦媛.射频通信电路[M] .第二版，北京：科学出版社，2006：
[14] KRAUS J D, MARHERFKA R J著.天线(上册) [M]，第三版. 章文勋,译. 北京:电子工业出版社，2004：191-193 .
基金项目：
广东省重点引导项目（项目编号：No.2005B10101005）
作者简介:
蔡明(1983-),男，广东省广州市人，助理工程师，学士,主要研究领域为电子技术、计算机科学。