基于RFID的混合型标签防碰撞算法研究
|
摘要
无线射频识别技术(Radio Frequency Identification,简写作RFID)是一种非接触的自动识别技术。RFID技术革新了追踪产业的发展,它的应用十分广阔。目前,这些应用发展迅速并且越发高效、节能,所以,随着日益增多的标签产品出现,标签读取技术前景宽广。然而,实际上标签读取协议仍面临许多问题。一个主要的难题是标签碰撞,当多个标签同时对一个阅读器产生响应时就会碰撞。在这种情况下,RFID阅读器的标签读取能力低下,并且能耗过多。
本文围绕RFID系统标签防碰撞算法展开研究分析。首先分析其研究背景。之后对国内外的研究现状进行分析。再在简单介绍RFID系统结构、工作流程的基础上,重点讨论目前RFID防碰撞算法,对Aloha算法,树型算法及混合型算法进行分析比较。进一步对目前常用的标签防碰撞算法进行仿真分析,在分析已有的防碰撞算法基础上提出一种新算法——基于碰撞反演的混合型算法,并通过MATLAB加以仿真分析及验证。
基于碰撞反演的混合型算法充分利用了Aloha算法和树型算法的优点,即结合了Aloha的时隙机制,又采用了树型的碰撞反演。新算法的特点是结合码表的使用,充分利用碰撞,以对后续的时隙进行合理的规划,从而减少碰撞。针对空闲时隙的处理,本算法采用了“提前结束”的方式,减少了空闲时隙的耗时,加快了标签的接入速度。最后通过仿真实验表明,新算法在标签数较多的情况下的确优于目前主流常用的算法,确实加快了标签接入的速度。
Technology of Radio Frequency Identification (RFID) is non-contact and automatic identification. RFID technologies have innovated the tracking industry, and applications is very broad. Facing more and more tag numbers, the promise of tag reading is brightly, especially these applications are so fast and energy efficient. In fact, tag reading algorithms face many problems. A key one being tag collision, which occurs when multiple tags reply simultaneously to a reader. In this case, an RFID reader experiences low tag reading performance, and wastes valuable energy.
This thesis focus on researching tag's an-collision algorithm of RFID system. Firstly, it introduces researching background. At the second place, analying domestic and international present condition of research. Then based on simply introducing the RFID-system's structure and working process, it mainly discuss RFID an-collision protocols at present. At the same time, making a comparison of aloha algorithm, tree algorithm and hybrid algorithm. Further more, to analysis the common tag an-collision algorithm from simulation. And from this, we present an improved protocol----hybrid algorithm of collision inversion, and through the MATLAB simulation to analysis and test it.
Hybrid algorithm of collision inversion makes full use of the advantages of aloha algorithm and tree algorithm, which combines time mechanism of aloha, and collision inversion of the other. Particularly, because of the code table, it can make full use of the former collision to arrange subsequent slots and reduce collisions. Dealing with the idle slots, this algorithm adapt "early end", which can speed up the tag access, to reduce the time of idle slots. Finally, simulation experiments show that the new one is better than the common algorithms, and is really accelerating the access speed.
本文围绕RFID系统标签防碰撞算法展开研究分析。首先分析其研究背景。之后对国内外的研究现状进行分析。再在简单介绍RFID系统结构、工作流程的基础上,重点讨论目前RFID防碰撞算法,对Aloha算法,树型算法及混合型算法进行分析比较。进一步对目前常用的标签防碰撞算法进行仿真分析,在分析已有的防碰撞算法基础上提出一种新算法——基于碰撞反演的混合型算法,并通过MATLAB加以仿真分析及验证。
基于碰撞反演的混合型算法充分利用了Aloha算法和树型算法的优点,即结合了Aloha的时隙机制,又采用了树型的碰撞反演。新算法的特点是结合码表的使用,充分利用碰撞,以对后续的时隙进行合理的规划,从而减少碰撞。针对空闲时隙的处理,本算法采用了“提前结束”的方式,减少了空闲时隙的耗时,加快了标签的接入速度。最后通过仿真实验表明,新算法在标签数较多的情况下的确优于目前主流常用的算法,确实加快了标签接入的速度。
Technology of Radio Frequency Identification (RFID) is non-contact and automatic identification. RFID technologies have innovated the tracking industry, and applications is very broad. Facing more and more tag numbers, the promise of tag reading is brightly, especially these applications are so fast and energy efficient. In fact, tag reading algorithms face many problems. A key one being tag collision, which occurs when multiple tags reply simultaneously to a reader. In this case, an RFID reader experiences low tag reading performance, and wastes valuable energy.
This thesis focus on researching tag's an-collision algorithm of RFID system. Firstly, it introduces researching background. At the second place, analying domestic and international present condition of research. Then based on simply introducing the RFID-system's structure and working process, it mainly discuss RFID an-collision protocols at present. At the same time, making a comparison of aloha algorithm, tree algorithm and hybrid algorithm. Further more, to analysis the common tag an-collision algorithm from simulation. And from this, we present an improved protocol----hybrid algorithm of collision inversion, and through the MATLAB simulation to analysis and test it.
Hybrid algorithm of collision inversion makes full use of the advantages of aloha algorithm and tree algorithm, which combines time mechanism of aloha, and collision inversion of the other. Particularly, because of the code table, it can make full use of the former collision to arrange subsequent slots and reduce collisions. Dealing with the idle slots, this algorithm adapt "early end", which can speed up the tag access, to reduce the time of idle slots. Finally, simulation experiments show that the new one is better than the common algorithms, and is really accelerating the access speed.
引文
[I]J.-D. Shin, S.-S. Yeo, T.-H. Kim, S. K. Kim. Hybrid Tag Anti-collision Algorithms [S]. RFID Systems. UK:Springer Berlin/Heidelberg,2007.
[2]V. Namboodiri and L. Gao. Energy-aware tag anti-collision protocols for RFID systems [C]. Fifth Annual IEEE International Conferance on Pervasive Computing and Communications (PerCom),(NY,USA),2007,23-46.
[3]李宝山等RFID防碰撞算法计算机仿真模型的研究[J].自动化与仪器仪表,2010年
[4]王璇.HF频段RFID长距离读写器协调工作问题研究[D].华东理工大学,2007年
[5]王刚RFID智能货架与系统的设计研究[D].江苏大学,2011年
[6]赵庆等RFID技术应用领域分析及展望[J].金卡工程,2005年
[7]K. Finkenzeller.John Wiley, Sons Ltd. Fundamentals and Applications in Contactless Smart Cards and Identification [M]. RFID handbook,2003.
[8]S. Lahiri. RFID Sourcebook. USA:IBM Press,2006.
[9]L. A. Burdet. RFID multiple access methods [R]. http://www.vs.inf.ethz.ch/edu/SS2004/DS/ reports/06 rfid-mac re-port.pdf.
[10]冯亮.基于RFID的供应链仓储管理研究及系统设计[D].山东大学,2010年
[11]R. Want. An introduction to RFID technology [J]. IEEE Pervasive Computing, vol.5, no.1, 2006,25-33.
[12]S. Lewis. Think RFID technology[OL]. http://hosteddocs.ittoolbox.com/laran032604.pdf, 2004.
[13]胡欣.积极制定自主知识产权RFID标准重点推介自主创新成果[J].信息技术与标准化,2009年9期
[14]刘姗姗等.基于RFID技术的林木种质资源管理系统初探[J].森林工程,2008年
[15]M. A. Bonuccelli, F. Lonetti, F. Martelli. Tree slotted Aloha:a new protocol for tag identification in RFID networks [C]. International Symposium on World of Wireless, Mobile and Multimedia Networks,(Niagara-Falls, USA),2006,603-608.
[16]J. Ryu, H. Lee, Y. Seok, T. Kwon, Y. Choi. A hybrid query tree protocol for tag collision arbitration in RFID systems [J]. IEEE ICC,(Scotland), Jun 2007,5981-5986.
[17]刘勇等.浅谈物联网的感知层[J].电脑学习,2010年5期
[18]C. Law, K. Lee, K.-Y. Siu. Efficient memoryless protocol for tag identification (extended abstract) [C]. Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (Toronto, CA), Aug 2000,75-84.
[19]刘振文.基于硬件的RFID防碰撞算法研究[D].华南理工大学,2009年
[20]李俊凤.射频识别系统中间件的研究与实现[D].华南理工大学,2008年
[21]袁耀.射频识别系统中圆极化微带天线阵的设计研究[D].南京邮电大学,2009年
[22]E. Microelectronics. Supertag category protocols [DB]. Data sheet, http://www.gaw. ru/doc/EM-Marin/P4022.PDF.
[23]D. K. Klair, K.-W. Chin, R. Raad. An investigation into the energy efficiency of pure and slotted Aloha based RFID anti-collision protocols [C]. IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, (Helsinki,Finland),2007.
[24]马辉.基于RFID门禁系统天线的研究与应用[D].南京邮电大学,2009年
[25]B. Zhen, M. Kobayashi, M. Shimizu. Framed Aloha for multiple RFID objects identification [J]. IEICE-Transactions on Communications, vol.88-B,2005,991-999.
[26]J.-R. Cha, J.-H. Kim. Novel anti-collision algorithms for fast object identification in RFID system [C]. The 11th Intl. Conference on Parallel and Distributed Systems, (Korea),2005, 63-67.
[27]T.-W. Hwang. B.-G. Lee, Y. S. Kim, D. Y. Suh, J. S. Kim. Improved anti-collision scheme for high speed identification in RFID system [C]. Proc. First International Conference on Innovative Computing, Information and Control, (China),2006,449-452.
[28]J. Wang, Y. Zhao, D. Wang. A novel fast anti-collision algorithm for RFID systems [C]. International Conference on in Wireless Communications, Networking and Mobile Computing (WiCom 2007), (Shanghai,China),2007.
[29]闫雪.电信运营商在物联网商业生态系统中的定位[D].北京邮电大学,2010年
[30]沈红伟.UHF无源电子标签芯片及关键集成技术研究[D].中国科学院微电子研究所,2008年
[31]付俊.无线射频识别技术研究[J].山西科技,2009年
[32]S. Yu, Y. Zhan, Z. Wang. Z. Tang. Anti-collision algorithm based on jumping and dynamic searching and its analysis [J]. Computer Engineering, vol.31,2005,19-20.
[33]C. Floerkemeier. Transmission control scheme for fast RFID object identification [C]. The 4th Annual Intl. Conference on Pervasive Computing and Communications Workshops, (Pisa, Italy),2006.
[34]R. Rivest. Network control by bayesian broadcast [J]. IEEE Trans. Inf. Theory, vol. IT-33, May 1987,323-328.
[35]孙光付RFID及其在物流配送中的应用[D].华中科技大学,2005年
[36]刘锡杰.UHF频段RFID读写器的设计[D].大连理工大学,2007年
[37]C. J. Tree algorithms for packet broadcast channels [J]. IEEE Trans. Inf. Theory, vol.25, no. 5,1979.505-515.
[38]D. R. Hush, C. Wood. Analysis of tree algorithms for RFID arbitration [J]. The IEEE Intl. Symposium on Information Theory,(Mexico City, USA),1998,107-107.
[39]J. Myung, W. Lee. Adaptive binary splitting:A RFID tag collision arbitration protocol for tag identification[J]. IEEE BROADNETs,(Boston, MA. USA), Oct.2005,347-355.
[40]J. Myung, W. Lee, J. Srivastava. Adaptive binary splitting for efficient RFID tag anti-collision [J]. IEEE Personal Commun. Mag.,vol.10. no.3.2006.144-146.
[41]J. Myung, W. Lee, T. Shih. An adaptive memoryless protocol for RFID tag collision arbitration[J]. IEEE Trans. Multimedia, vol.8, no.5,2006,1096-1101.
[42]J. Myung, W. Lee. An adaptive memoryless tag anti-collision protocol for RFID networks [C]. The 24th IEEE Annual Conference on Computer Communications (INFOCOM 2005), (Miami, USA), Mar.2005.
[43]集网络应用优势结当今学生风采[J].测控技术,2008年11期
[44]池海祥CDMA2000移动通信系统时钟设计与关键技术的研究[D].北京交通大学,2006
[2]V. Namboodiri and L. Gao. Energy-aware tag anti-collision protocols for RFID systems [C]. Fifth Annual IEEE International Conferance on Pervasive Computing and Communications (PerCom),(NY,USA),2007,23-46.
[3]李宝山等RFID防碰撞算法计算机仿真模型的研究[J].自动化与仪器仪表,2010年
[4]王璇.HF频段RFID长距离读写器协调工作问题研究[D].华东理工大学,2007年
[5]王刚RFID智能货架与系统的设计研究[D].江苏大学,2011年
[6]赵庆等RFID技术应用领域分析及展望[J].金卡工程,2005年
[7]K. Finkenzeller.John Wiley, Sons Ltd. Fundamentals and Applications in Contactless Smart Cards and Identification [M]. RFID handbook,2003.
[8]S. Lahiri. RFID Sourcebook. USA:IBM Press,2006.
[9]L. A. Burdet. RFID multiple access methods [R]. http://www.vs.inf.ethz.ch/edu/SS2004/DS/ reports/06 rfid-mac re-port.pdf.
[10]冯亮.基于RFID的供应链仓储管理研究及系统设计[D].山东大学,2010年
[11]R. Want. An introduction to RFID technology [J]. IEEE Pervasive Computing, vol.5, no.1, 2006,25-33.
[12]S. Lewis. Think RFID technology[OL]. http://hosteddocs.ittoolbox.com/laran032604.pdf, 2004.
[13]胡欣.积极制定自主知识产权RFID标准重点推介自主创新成果[J].信息技术与标准化,2009年9期
[14]刘姗姗等.基于RFID技术的林木种质资源管理系统初探[J].森林工程,2008年
[15]M. A. Bonuccelli, F. Lonetti, F. Martelli. Tree slotted Aloha:a new protocol for tag identification in RFID networks [C]. International Symposium on World of Wireless, Mobile and Multimedia Networks,(Niagara-Falls, USA),2006,603-608.
[16]J. Ryu, H. Lee, Y. Seok, T. Kwon, Y. Choi. A hybrid query tree protocol for tag collision arbitration in RFID systems [J]. IEEE ICC,(Scotland), Jun 2007,5981-5986.
[17]刘勇等.浅谈物联网的感知层[J].电脑学习,2010年5期
[18]C. Law, K. Lee, K.-Y. Siu. Efficient memoryless protocol for tag identification (extended abstract) [C]. Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (Toronto, CA), Aug 2000,75-84.
[19]刘振文.基于硬件的RFID防碰撞算法研究[D].华南理工大学,2009年
[20]李俊凤.射频识别系统中间件的研究与实现[D].华南理工大学,2008年
[21]袁耀.射频识别系统中圆极化微带天线阵的设计研究[D].南京邮电大学,2009年
[22]E. Microelectronics. Supertag category protocols [DB]. Data sheet, http://www.gaw. ru/doc/EM-Marin/P4022.PDF.
[23]D. K. Klair, K.-W. Chin, R. Raad. An investigation into the energy efficiency of pure and slotted Aloha based RFID anti-collision protocols [C]. IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, (Helsinki,Finland),2007.
[24]马辉.基于RFID门禁系统天线的研究与应用[D].南京邮电大学,2009年
[25]B. Zhen, M. Kobayashi, M. Shimizu. Framed Aloha for multiple RFID objects identification [J]. IEICE-Transactions on Communications, vol.88-B,2005,991-999.
[26]J.-R. Cha, J.-H. Kim. Novel anti-collision algorithms for fast object identification in RFID system [C]. The 11th Intl. Conference on Parallel and Distributed Systems, (Korea),2005, 63-67.
[27]T.-W. Hwang. B.-G. Lee, Y. S. Kim, D. Y. Suh, J. S. Kim. Improved anti-collision scheme for high speed identification in RFID system [C]. Proc. First International Conference on Innovative Computing, Information and Control, (China),2006,449-452.
[28]J. Wang, Y. Zhao, D. Wang. A novel fast anti-collision algorithm for RFID systems [C]. International Conference on in Wireless Communications, Networking and Mobile Computing (WiCom 2007), (Shanghai,China),2007.
[29]闫雪.电信运营商在物联网商业生态系统中的定位[D].北京邮电大学,2010年
[30]沈红伟.UHF无源电子标签芯片及关键集成技术研究[D].中国科学院微电子研究所,2008年
[31]付俊.无线射频识别技术研究[J].山西科技,2009年
[32]S. Yu, Y. Zhan, Z. Wang. Z. Tang. Anti-collision algorithm based on jumping and dynamic searching and its analysis [J]. Computer Engineering, vol.31,2005,19-20.
[33]C. Floerkemeier. Transmission control scheme for fast RFID object identification [C]. The 4th Annual Intl. Conference on Pervasive Computing and Communications Workshops, (Pisa, Italy),2006.
[34]R. Rivest. Network control by bayesian broadcast [J]. IEEE Trans. Inf. Theory, vol. IT-33, May 1987,323-328.
[35]孙光付RFID及其在物流配送中的应用[D].华中科技大学,2005年
[36]刘锡杰.UHF频段RFID读写器的设计[D].大连理工大学,2007年
[37]C. J. Tree algorithms for packet broadcast channels [J]. IEEE Trans. Inf. Theory, vol.25, no. 5,1979.505-515.
[38]D. R. Hush, C. Wood. Analysis of tree algorithms for RFID arbitration [J]. The IEEE Intl. Symposium on Information Theory,(Mexico City, USA),1998,107-107.
[39]J. Myung, W. Lee. Adaptive binary splitting:A RFID tag collision arbitration protocol for tag identification[J]. IEEE BROADNETs,(Boston, MA. USA), Oct.2005,347-355.
[40]J. Myung, W. Lee, J. Srivastava. Adaptive binary splitting for efficient RFID tag anti-collision [J]. IEEE Personal Commun. Mag.,vol.10. no.3.2006.144-146.
[41]J. Myung, W. Lee, T. Shih. An adaptive memoryless protocol for RFID tag collision arbitration[J]. IEEE Trans. Multimedia, vol.8, no.5,2006,1096-1101.
[42]J. Myung, W. Lee. An adaptive memoryless tag anti-collision protocol for RFID networks [C]. The 24th IEEE Annual Conference on Computer Communications (INFOCOM 2005), (Miami, USA), Mar.2005.
[43]集网络应用优势结当今学生风采[J].测控技术,2008年11期
[44]池海祥CDMA2000移动通信系统时钟设计与关键技术的研究[D].北京交通大学,2006