基于新颖跳跃式动态搜索的RFID防碰撞算法:跳跃机器人的碰撞

　　文章编号:1001-9081(2012)01-0288-04 doi:10.3724/SP.J.1087.2012.00288 　　� 　　 　　�摘 要: 扼要分析目前针对标签防碰撞问题采用的防碰撞算法优缺点的基础上，基于跳跃式动态搜索(JDS)算法的思想，提出了一种新颖的JDS标签防碰撞算法。算法将栈思想引入到新的跳跃式策略前后搜索中，避免出现空闲时隙。在读写器问询时，利用标签反馈信息记忆部分已知信息，采用不定长动态传输方式及调整策略识别标签的未知数据位，减少了读写器搜索次数及系统传输量。算法仿真结果表明，系统传输量大大减少，吞吐量有明显提高。
　　
　　�关键词: 无线射频识别；防碰撞算法；调整策略；跳跃式搜索；动态传输
　　�中图分类号: TP391.45; TN92 文献标志码:A
　　 �
　　Abstract: The paper briefly introduced the merits and shortcomings of the existing anti-collision algorithms. Based on the idea of Jumping and Dynamic Searching (JDS) algorithm, a Novel JDS (NJDS) algorithm for tags� anti-collision was proposed. The algorithm brought stack into the new jumping before and after searching strategy to reduce the number of collision slots and avoid idle slots. When requested by readers, it adopted dynamic transmission and variable length adjustment strategy, and used the known information remembered by the feedback tags� information to identify the unknown data bits of tags, which reduced the number of search of readers and the transmission of system. The analysis on simulation results indicates that the proposed algorithm performs significantly better than the existing anti-collision algorithms. The transmission is greatly reduced, and throughput of the system has increased significantly.
　　 Key words: Radio Frequency Identification (RFID); anti-collision algorithm; adjustment strategy; jumping search; dynamic transmission
　　
　　0 引言�
　　
　　无线射频识别(Radio Frequency Identification, RFID)系统中标签防碰撞问题一直是学者讨论的热点，目前，标签防碰撞算法主要有两大类［1］：一类是基于ALOHA协议的随机算法；另一类是基于二进制树的确定算法。基于ALOHA算法的复杂度及对标签硬件的要求较低，但存在不稳定的现象，可能导致“标签饥饿问题”；二进制树算法的识别率可达100%，不存在“标签饥饿问题”，但当标签数量增多时，需浪费大量时隙识别完所有标签［2］。基于ALOHA协议的防碰撞算法一般包括时隙ALOHA算法、帧时隙ALOHA(Frame-Slotted ALOHA, FSA)算法、动态帧时隙ALOHA(Dynamic Frame-Slotted ALOHA, DFSA)算法、增强型动态帧时隙ALOHA（Enhanced Dynamic Frame-Slotted ALOHA, EDFSA）算法和碰撞分组算法（Collision Group Algorithm, CGA）等；基于二进制树的主要算法有二进制搜索(Binary Search, BS)、动态二进制搜索(Dynamic Binary Search, DBS)算法、跳跃式动态二进制搜索(Jumping and Dynamic Searching, JDS)算法等。FSA算法采用帧时隙策略，避免了标签发生部分碰撞现象，降低了标签碰撞概率，但随着未识别标签数的减少其查询帧长固定，致使两者差距变大，使得FSA算法的吞吐量较低［3］；DFSA通过利用碰撞概率估计未识别标签数动态调整帧长，避免时隙的浪费，系统性能有所提高，但当标签数较大时，由于帧长的有限性，碰撞概率急剧增大，致使系统吞吐量下降［4］。针对DFSA算法的不足，EDFSA算法利用分组思想避免大量标签同时响应读写器的查询，系统吞吐性能大大提高［5］。文�献［6］在EDFSA算法基础上进一步提出CGA算法，利用划分和攻克方法来提高识别效率，系统吞吐性能较EDFSA提高，但相对二进制搜索算法其系统吞吐量仍较低。二进制搜索算法根据碰撞信号的译码结果发送寻呼，每识别一个标签，重新返回初始查询命令，解决了发生碰撞时标签识别问题，但读写器与标签都以完整的ID序列号传输数据，增大了系统传输时延［7］。DBS算法采用不定长传输方式缓解了BS算法的平均识别一个标签传输量大问题，但搜索总时隙数并未减少［8］；修剪枝二进制树形反碰撞算法采用碰撞探测法避免了空闲时隙的出现，部分解决了总时隙数过高问题，但仍采用完整的ID传输［9］。改进的返回式二进制搜索算法在返回式搜索算法的基础上沿用了修剪枝二进制树形算法思想避免了空闲时隙出现，并采用了动态二进制搜索算法的不定长传输方式，降低了系统时延及减少了标签传输量，但并未进一步利用已识别标签ID数据位信息，致使反复识别过程仍存在信道浪费现象［10-11］。针对以上算法的不足，文献［12］采用JDS算法，充分利用了返回式搜索和动态二进制搜索的优点，采用向前向后搜索，提高了系统性能，但是标签平均响应次数、传输比特和碰撞时隙数方面仍需要进一步改进。本文提出了一种新颖JDS算法(Novel Jumping and Dynamic Searching, NJDS)，该算法采用新的搜索策略，同时引入栈的思想和新的调整策略，解决了JDS算法的不足，提升了系统的整体性能。�
　　
　　1 NJDS算法描述�
　　算法采用Manchester编码［13］，读写器中增加栈和字符串存储器，标签中添加位计数器和位比较器，约定读写器作用范围内标签能在同一时刻开始传送其ID序列号。算法引入4种命令。�
　　1)REQUEST(UID,�P��1,�P��0)。读写器发送一个UID参数给识别区域内标签，�区域内标签�ID�值的第s~x位与之相符的标签应答(即ID��s~x�表示读写器在第一次寻呼之后，根据译码结果得到的下一次查询前缀)，回传P�1~P�0位信息。其中，�UID�为标签�ID�最高位s至最高碰撞位x的数据位，P�1为次高碰撞位位数，P�0为最低碰撞位位数。��
　　2)SELECT(UID)。将事先确定的UID作为参数发送给标签，作为执行其他命令(如读出或写入数据)的切入开关。�
　　3)READ(UID)。将选中标签自身存储的ID数据发送给读写器。�
　　4)UNSELECT(UID)。取消选中的标签命令，将选中的标签屏蔽使处于非激活状态，对收到的REQUEST命令不作应答。若重新激活，标签必须暂时离开读写器的作用范围施行复位。�
　　
　　1.1 NJDS算法原理�
　　JDS算法的搜索过程是当标签反馈信息为碰撞时隙，读写器采取向前搜索策略，直至遇到可读时隙（即识别一个标签）为止，采取后退方式，返回上一碰撞节点，继续搜索直至识别完读写器工作区域的所有标签。NJDS同样采用了前进和后退搜索方式，它的搜索过程是当标签反馈信息为碰撞时隙，若碰撞时隙只有一个碰撞位，则直接识别两个标签，利用后退搜索方式，返回到上一个碰撞节点另一分支继续搜索；若不止一个碰撞位，读写器继续向前搜索，直至识别一个标签，利用后退方式，返回到上一个碰撞节点的另一分支搜索，直至识别完工作区域的所有标签。搜索直观图比较如图1所示。算法的详细识别过程如表1。其中，SN（Search Number）代表搜索次数，SM（Search Method）表示搜索方式，RQ（REQUEST）为请求命令，RC（Received Code）指接收的ID片段。首先读写器发送Request（NULL,7,0）命令，读写器工作区域内所有标签响应，经Manchester编码译码后的反馈信息，可精确地确定最高、次高、最低碰撞位，分别压入stack1、stack2及stack3；并利用反馈回的已知信息，得到最高碰撞位与次高碰撞位之间的数据string1和最低碰撞位与最低位之间的数据string2。若此次查询未识别出标签，采取向前搜索（Forward Search, FS），根据3个栈及两个字符串，获取下一次查询的3个参数UID、�P��1及�P��0，重复执行上述过程，直至识别出一个标签。识别出标签后，采取后退策略（Backward Rebound, BR），先判断UID的最低位是否为0，若为0，则将0改为1，作为下一次查询Request命令的UID，根据stack2、stack3的栈顶元素得到其余两个参数�P��1、�P��0；若不为0，继续后退搜索，将3个栈的栈顶元素推出，利用stack1的栈顶元素及string1，获得新的UID，重复执行上述过程，跳跃式地将整个工作区域内的标签识别完。从表1、2的算法搜索过程进行比较，NJDS算法的搜索次数及标签平均传输量明显比JDS算法少，而且搜索方式更有规律。�
　　
　　1.2 算法改进�
　　1)减少传输冗余数据。�
　　读写器从寻呼过程接收标签应答的序列号，经Manchester译码结果知，最高碰撞位之前及碰撞最低位之后的位数据，对于读写器是已知的，故不需在发送查询命令时重复传输，以及将最高碰撞位之后的已知位数据保留，则在查询过程可以进一步减少数据传输比特量，从而降低传输时延和能量损耗。该算法利用此特点较JDS动态传输方式减少一半的冗余信息，进一步减少了数据传输比特位。例如读写器译码结果�0×11×0×1�，则读写器保留最高碰撞位之前数据位0及最低碰撞位之后位1，以及最高碰撞位之后的两位11，故在查询过程中，只需反馈第3位至第1位的数据信息，不需传输其他冗余比特位信息，在JDS算法以动态传输方式减少一半的冗余信息的基础上进一步减少数据传输冗余位。�
　　2)减少读写器寻呼次数。�
　　NJDS算法中，引入调整策略，即在读写器中添加一个碰撞比特计数器。如果读写器在查询过程中，反馈回的信息只有一个碰撞位，则读写器直接识别这两个标签，即将碰撞置0和1分别识别，可以减少读写器的寻呼次数，避免读写器与标签之间不必要的功率消耗。例如：若反馈回的ID序列号为�1×01�，则读写器可直接识别出此信息为1001和1101。�
　　3)减少标签总的传输比特。�
　　NJDS算法较JDS优越之处还在于，读写器可根据栈存储的信息，准确地获取下一次查询命令的参数，不需频繁返回到根节点查询，而是根据深度优先策略，依次跳跃式搜索未识别的分支。这使得读写器在搜索的过程中，很大程度上可减少标签的响应个数以及标签传输比特量，降低读写器与标签之间的功率损耗。�
　　
　　1.3 算法流程�
　　算法整体流程如图2所示。�
　　
　　详细步骤如下。�
　　步骤1 读写器初始置3个栈stack1、stack2、stack3及2个字符串string1、string2为NULL，发送初始查询Request(NULL，�L�-1，0)命令(�L�为标签ID的长度)，要求工作区域内的所有标签响应。�
　　步骤2 读写器检测有无标签响应，若无响应，转至步骤8;若有响应，将反馈回的信息经过Manchester编码译码后，检测有无标签碰撞发生。�
　　步骤3 若发生碰撞，检测是否只有一个碰撞位，若是，分别置碰撞位为0和1，识别出两个标签，分别进行其他操作(读出或写入)及UNSELECT操作，将这2个标签屏蔽。采取后退搜索，判断栈是否为空，若为空，转至步骤8;若不空，转至步骤6。�
　　步骤4 若有多个碰撞位，读写器记录最高、次高、最低碰撞位，将其压入栈stack1、stack2、stack3，并得到新的string1和string2，利用这些信息获取下一次查询命令的3个参数，发送Request(UID,�P��1,�P��0)，转至步骤2依次执行。�
　　步骤5 若无碰撞发生，直接识别该标签，执行其他操作(读出或写入)，利用UNSELECT操作将此标签屏蔽。采取后退策略，判断栈是否为空，若为空，转至步骤8;�
　　步骤6 若栈不空，检测UID最低位是否为0，若为0，将UID最低位0改为1，得到新的UID参数，根据stack2、stack3的栈顶元素得到其余两个参数�P��1,�P��0，发送Request(UID,�P��1,�P��0)，转至步骤2依次执行。�
　　步骤7 若不为0，将三个栈的栈顶元素推出，根据stack1、stack3的栈顶元素响应的调整string1、string2，循环执行直至获取的UID最低位为0，转至步骤6。�
　　步骤8 若栈stack1为空，则结束整个识别过程。�
　　
　　2 算法性能分析�
　　
　　2.1 读写器的寻呼次数�
　　
　　�定理1 若有n个电子标签在读写器的工作区域内，设识别n个标签读写器需发送寻呼次数为Q(n)，碰撞次数为C(n)，引入调整策略，设只有一个比特位发生碰撞的节点个数为k，则可得：�
　　Q(n)=C(n)+n－2k(1)�
　　Q(n)=2n－1－2k(2)�
　　证明 �NJDS�算法所形成的二叉树中所有节点代表的是寻呼的总数Q(n)，非叶子节点的总数代表碰撞的次数C(n)，叶子节点的数量即为标签的个数n，由于只有一个比特位发生碰撞的节点个数为k，故根据调整策略有Q(n)=C(n)+�n－�2k，即式(1)成立。�
　　采用数学归纳法来证明。�
　　1)当n=1时，表示读写器工作区域内只有一个标签，则不会发生碰撞，k=0，故Q(1)=1成立。�
　　2)当n=2时，读写器工作区域内有2个标签，此时标签至少有1个比特位发生碰撞。当只有一个比特位发生碰撞，则读写器将该碰撞比特位分别置“0”和“1”，直接识别出这两个标签，读写器识别这两个标签，只需发送一次寻呼命令。�Q(2)=�2×2－2×1－1=1�
　　3)假设有n个标签时，结论也成立，即Q(n)=2n－2k－1，那么当读写器工作区域内有n+1个时，二叉树增加一个节点，碰撞节点也增加一个，即Q(n)=2n－1－2k，若当识别过程中出现k对只有一个比特位发生碰撞的情况，则当识别过程中，此处语句不通顺，是否少了一句，请作相应调整。，故Q(n+1)=C(n+1)+n+1－2k=2(n+1)－�2k－�1。�
　　由此知对于n+1个标签的情况结论也成立，即式(2)成立。�
　　
　　
　　2.2 吞吐量�
　　
　　吞吐量定义为单位时间内成功识别的标签量。
　　�NJDS�算法的吞吐量S可表达成：�
　　S=n/Q(n)�
　　即S=n2n－2k－1。��
　　
　　3 算法仿真结果分析�
　　在理想信道条件下，不计控制、前后缀和校验冗余等开销，参考ISO18000-6标准，进行仿真。标签数量在0~1�000动态变化，比特率为100�Kbps，通过30次仿真取均值，对读写器识别所有标签所用总时隙数、标签不同ID位传输量、系统平均传输比特量以及吞吐量等性能指标进行分析，与DBS算法和JDS算法进行比较。�
　　图3为读写器在识别不同标签数的情况下，NJDS算法与DBS算法和JDS算法所需总时隙数比较，很显然NJDS算法比DBS算法和JDS算法的寻呼次数少。图4为NJDS算法与DBS算法和JDS算法的吞吐量比较，NJDS算法的吞吐率超过了�0.5，�随着标签数的增大，其吞吐率显示出明显的稳定增大趋势。图5~6反应标签传输比特情况以及针对不同标签ID长度进行仿真，相对于DBS、JDS算法，NJDS传输比特数明显减少。�
　　
　　4 结语�
　　基于栈先进后出的思想将碰撞节点的信息存储在栈中，通过对栈中信息的探测，获取下一次查询命令的参数，跳跃式地前后搜索，避免了空闲时隙的出现，缩短了系统的识别延时。NJDS采用了新的动态传输的方式，进一步保留了已知信息，减少了读写器与标签之间的通信量，提高了标签的识别速度，同时高效地节省了信道。另外，通过在算法中引用调整策略，减少了读写器的寻呼次数，降低了系统的功率损耗。算法对标签的硬件要求低，具有较好的实用价值。�
　　�参考文献:�
　　[1]
　　SCHOUTE F S. Dynamic frame length ALOHA ［J］. IEEE Transactions on Communications Letters, 1983, 31(4): 565-568.
　　�[2]
　　王亚奇,蒋国平.基于分组机制的跳跃式动态二进制防碰撞算法［J］.自动化学报，2010,36(10):1390-1400.
　　�[3]
　　王中祥,王俊宇,刘丹,等.BIS:一种降低空时隙开销的RFID防碰撞算法［J］.通信学报,2009,30(9):1-7.
　　�[4]
　　程文青,赵梦欣,徐晶,等.改进的RFID动态帧时隙ALOHA算法［J］.华中科技大学学报:自然科学版,2007,35(6):14-16.
　　�[5]
　　LEE S-R, JOO S-D, LEE C-W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification ［C］// Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services. Washington, DC: IEEE Computer Society, 2005: 166-172.
　　�[6]
　　LIN C-F, LIN F Y-S. Efficient estimation and collision-group-based anticollision algorithms for dynamic frame-slotted ALOHA in RFID networks ［J］. IEEE Transactions on Automation Science and Engineering, 2010, 7(4): 840-848.
　　�[7]
　　CAPETANAKIS J I. Tree algorithms for packet broadcast channels ［J］. IEEE Transactions on Information Theory, 1979, 25(5): 505-515.
　　�[8]
　　鞠伟成,俞承芳.一种基于动态二进制的RFID抗冲突算法［J］.复旦学报:自然科学版,2005,44(1):46-50.
　　�[9]
　　WANG T-P. Enhanced binary search with cut-through operation for anti-collision in RFID systems ［J］. IEEE Communications Letters, 2006, 10(4): 236-238.
　　�[10]
　　SHI X-L, SHI X-W, HUANG Q-L, et al. An enhanced binary anti-collision algorithm of backtracking in RFID system ［J］. Progress in Electromagnetics Research B, 2008, 4: 263-271.
　　�[11]
　　SHI X-L, WEI F, HUANG Q-L, et al. Novel binary search algorithm of backtracking for RFID tag anti-collsion ［J］. Progress in Electromagnetics Research B, 2008, 9: 97-104.
　　�[12]
　　余松森,詹宜巨,王志平,等.跳跃式动态树形反碰撞算法及其分析［J］.计算机工程,2005,31(9):19-21.
　　�[13]
　　王雪,钱志鸿,胡正超,等.基于二叉树的RFID防碰撞算法的研究［J］.通信学报,2010,31(6):49-57.
　　
　　 收稿日期:2011-06-23;修回日期:2011-09-04。�
　　
　　基金项目:
　　教育部新世纪优秀人才支持计划项目(NCET09-0094)；国家863计划项目(2009AA043200)。�
　　
　　 作者简介:
　　冯娜（1984-），女，内蒙古巴彦淖尔人，硕士研究生，主要研究方向：物联网； 潘伟杰（1983-），男，河南漯河人，博士研究生，主要研究方向：物联网、多目标优化； 李少波（1973-），男，湖南岳阳人，教授，博士生导师，教育部新世纪优秀人才计划入选者，主要研究方向：物联网、计算设计、制造业信息化；�杨观赐（1983-），�男，湖南嘉禾人，博士研究生，主要研究方向：计算智能。

推荐访问:算法 碰撞 新颖 基于新颖跳跃式动态搜索的RFID防碰撞算法 rfid防碰撞算法的研究 rfid防碰撞算法有哪些