2017年7月
第38卷一第7期计算机工程与设计C OM P U T E RE N G I N E E R I N G A N DD E S I G N J u l y 一2017V o l .38一N o .7
??????????????????????????????????????????????????基于时隙冲突预判的R F I D 防碰撞算法
江一岸,罗小平(广东农工商职业技术学院计算机系,广东广州510507)摘一要:射频识别技术的应用场景中,由于存在大量标签同时响应阅读器的情况,导致A L O HA 协议中标签长时间无法被识别,为提高A L O HA 协议的识别效率,提出一种基于时隙冲突预判的防碰撞算法三在时隙开始前判断碰撞探测码是否冲突,以此为依据消除空闲时隙,当发生探测码碰撞时,结合冲突位置和时隙冲突规避机制识别标签,有效降低碰撞时隙的发生概率三仿真结果表明,相比于同样基于时隙A L O HA 的经典Q 值算法二F B B S 和B I S 算法,该算法的最高吞吐率可以提高至86.4%,高于对比算法系统效率,碰撞时隙数平均降低了89%二84%和55.1%,在标签数小于500时通信复杂度平均减少了39.6%二38%和14.2%三
关键词:射频识别;防碰撞;时隙冲突;预判;A L O HA 算法
中图法分类号:T P 301.6一文献标识号:A 一文章编号:1000-7024(2017)07-1859-07
d o i :10.16208/j .i s s n 1000-7024.2017.07.030收稿日期:2016-05-25;修订日期:2016-07-05
基金项目:广东省教育厅2012年度广东省高职院校教育教学改革基金项目(20120101006);广东农工商职业技术学院2014年度科研课题
基金项目(x y z d 1403)作者简介:江岸(1982),男,湖南常德人,硕士,讲师,研究方向为射频识别防冲突算法;罗小平(1968),女,湖北武汉人,硕士,副教授,研究方向为软件工程二数据库技术三E -m a i l :c z m 726@163.c o m R F I Da n t i -c o l l i s i o na l g
o r i t h mb a s e do n s l o t t e d c o n f l i c t p r e d i c t i o n J I A N G A n ,L U O X i a o -p i n g
(D e p a r t m e n t o fC o m p u t e r ,G u a n g d o n g A g r i c u l t u r e I n d u s t r y B u s i n e s sP o l y t e c h n i cC o l l e g e ,G u a n g z h o u510507,C h i n a )A b s t r a c t :I n t h e a p p l i c a t i o n s c e n a r i o s o fR F I Dt e c h n o l o g y ,m a n y t a g s r e s p o n s e t o t h e r e a d e r a t t h e s a m e t i m e ,w h i c h l e a d s t o t h e t a g s i n t h eA L O HAa l g o r i t h mc a n n o t b e i d e n t i f i e d f o r a l o n g t i m e .T o i m p r o v e t h e i d e n t i f y e f f i c i e n c y o fA L O HAa l g
o r i t h m ,a na n t i -c o l l i s i o na l g o r i t h mt h a t b a s e do n s l o t t e d c o n f l i c t p r e d i c t i o nw a s p r o p o s e d .B y a n a l y z i n g w h e t h e r t h e d e t e c t i o n c o d e s c o n -f l i c t e x i s t s ,i d l e s l o t sw e r e e l i m i n a t e db e f o r e t h e s t a r t o f s l o t .W h e nd e t e c t i o nc o d e s c o n f l i c t i n g ,t a g sw e r e i d e n t i f i e da c c o r d i n g
t o t h e l o c a t i o n s o f c o l l i s i o na n d t h em e c h a n i s mo f s l o t c o l l i s i o na v o i d a n c e ,t h e p r o b a b i l i t y o f c o l l i s i o nw a s r e d u c e ds u c c e s s f u l l y
.A c c o r d i n g t o t h es i m u l a t i o nr e s u l t s ,c o m p a r e dt oc l a s s i c a lQa l g o r i t h m ,F B B Sa l g o r i t h ma n dB I Sa l g o r i t h mt h a ta l lb a s e do n s l o t t e dA L O HAa l g o r i t h m ,t h eb e s t t h r o u g h p u t r a t eo f t h i sa l g o r i t h mc a nr e a c h86.4%,t h er e c o g n i t i o ne f f i c i e n c y i sh i g
h e r t h a n t h e c o n t r a s t a l g o r i t h m s ,t h e a v e r a g en u m b e r o f c o l l i s i o n s l o t s i s r e d u c e db y 89%,84%a n d55.1%c o m p a r e d t o t h e c o n -t r a s t a l g o r i t h m s ,a n d t h e c o m m u n i c a t i o n c o m p l e x i t y i s r e d u c e db y 39.6%,38%a n d14.2%o na v e r a g e r e s p e c t i v e l y w h e n t h e n u m b e r o f t a g s i s l e s s t h a n500.K e y w
o r d s :r a d i o f r e q u e n c y i d e n t i f i c a t i o n (R F I D );a n t i -c o l l i s i o n ;s l o t t e d c o n f l i c t ;p r e d i c t i o n ;A L O HAa l g o r i t h m 0一引一言
常见的标签防碰撞算法[1]是基于树的防碰撞算法和基
于A L O HA 的随机性算法[2]三基于树型的算法,例如经典
的查询树(q u e r y t r e e ,Q T )算法[3,4]和二进制搜索树(b i -n a r y s
e a r c h t r e e ,B T )算法[5],这类算法不断的将冲突节点分离,以此缩小搜索范围三针对此类算法的改进较多,如后退式二进制搜索算法[6],以及Y u a n -C h e n g L a i 等提出的O B T T 算法[7]三树型搜索算法能够稳定识别所有标签,但存在着识别延时过长,算法实现复杂度高等问题三基于A L O HA 的防碰撞算法主要可以分为帧时隙A L O HA (F S A )算法[8]和动态帧时隙A L O HA (D F S A )算法[9],由于这类算法采用随机竞争策略,导致识别效率低下,已经有相关的研究提出了一些改进方案三如E P C -C 1G 2(E P C -
g l o b a l C l a s s -1G e n e r a t i o n -2)中的Q 算法[10]通过预约机制提高标签的识别速度;张小红提出的F B B S 算法利用差分
万方数据