射频识别技术（RFID）防碰撞问题的研究
|
摘要
射频识别技术(Radio Frequency Identification, RFID)作为一种非接触式的自动识别技术,它通过射频信号自动识别目标对象并获取相关数据。RFID具有条形码无可比拟的优点:无需接触,直接读取信息;可在恶劣环境下工作;穿透能力强;可同时处理多个目标等。但作为一种新兴的应用技术,RFID技术尚不成熟,还存在一些不足,如识别准确率不高;标准化进程缓慢等等。其中,由于复杂环境下标签碰撞和读写器碰撞带来的系统工作效率低下问题成了RFID技术应用推广的瓶颈。因此,研究快速、准确、可靠的防碰撞问题解决方案,对于RFID技术的发展有着至关重要的意义。
本文核心内容是关于RFID系统防碰撞算法的研究,包括标签的算法和读写器的算法。针对单读写器作用范围内,多标签通讯的防碰撞问题,文中结合RFID标准(主要是UHF频段的EPC Gen2和ISO18000-6标准),详细研究了已有的ALOHA算法和二进制树搜索算法及其改进算法,深入分析每种算法的性能、优缺点及适用场合。在此基础上,本文提出了一种基于动态帧时隙的改进算法,当标签数量很多时,通过分组限制响应标签个数可达到较高的识别效率。仿真结果表明,当标签数达到1000时,本文提出的算法相对于传统的时隙算法可以使时隙利用率提高80%以上。
另外,对于多读写器环境下的防碰撞问题,尽管它类似于移动通讯中蜂窝网的频率分配问题,但RFID系统也有它自身的特性,如低效的标签引发的标签干扰和读写器在实际工作中的限制等等。本文参考相关国内外文献,定义和分析几种读写器碰撞类型,并利用图论中的着色理论建立读写器碰撞模型。接着研究分析了Color-wave和HiQ这两种解决读写器碰撞问题的算法,为今后研究多读写器与多标签通讯以及移动读写器的通讯过程这些复杂问题打下了基础。
Radio Frequency Identification (RFID) is a kind of non-touching automatic identifying technology. It can automatically identify the target and get information through radio-frequency signal. RFID has unexampled advantages compared to barcode, such as reading information directly without touching; working under bad environment; the better penetrability and identifying more objects simultaneously. As one applied technology, it’s immature yet, and still has some shortcomings, like the poor accuracy rate of identifying, the slow progress of RFID standardization, etc. Among those elements, in the dense environment due to tag-collision and reader-collision problem, the lower efficiency of system will become bottleneck to the RFID technology’s application and promotion. Therefore finding a fast, accurate and reliable solution to solve the anti-collision problem is of very important significance in developing the RFID technology.
The main contents of this thesis are about the research on anti-collision algorithm of RFID systems, including tag’s and reader’s. According to the anti-collision problem of multi-tags communication Within the reading range of a single reader, the paper combine with RFID standard (mainly UHF frequencies as EPC Gen2 and ISO18000-6), and detailedly discuss ALOHA algorithm and Binary tree search algorithm along with algorithms which improved from them. Besides the performance of advantages and disadvantages and their application situation are also analyzed. Based on those work, an improved Dynamic Frame Slotted ALOHA algorithm is put forward. The proposed algorithm compared to conventional ones, when there are a large number of tags in the field, can achieve high system efficiency by grouping to restrict the number of unread tags. Simulation results show that the proposed algorithm improves the slot efficiency above 80% at least compared to the conventional algorithms when the number of tags reach 1000.
Otherwise, the anti-collision problem with respect to the environment of multi-readers, although it’s similar to the Frequency Assignment Problem experienced in cellular telephone networks, but RFID system has its own unique features, like tag interference due to the lower functionality of tag and the practical system operating constraints. Making reference to domestic and foreign literature, several types of readers collision are defined and analyzed, moreover utilizing graph coloring theory to establish collision model of readers. Subsequently, both Colorwave and HiQ algorithm which used to solve the problem of reader-collision are discussed in detail, and it will pave the way for future research on those more complicated problems, like the communication between multi-tags and multi-readers, and the communication process of mobile reader device etc.
本文核心内容是关于RFID系统防碰撞算法的研究,包括标签的算法和读写器的算法。针对单读写器作用范围内,多标签通讯的防碰撞问题,文中结合RFID标准(主要是UHF频段的EPC Gen2和ISO18000-6标准),详细研究了已有的ALOHA算法和二进制树搜索算法及其改进算法,深入分析每种算法的性能、优缺点及适用场合。在此基础上,本文提出了一种基于动态帧时隙的改进算法,当标签数量很多时,通过分组限制响应标签个数可达到较高的识别效率。仿真结果表明,当标签数达到1000时,本文提出的算法相对于传统的时隙算法可以使时隙利用率提高80%以上。
另外,对于多读写器环境下的防碰撞问题,尽管它类似于移动通讯中蜂窝网的频率分配问题,但RFID系统也有它自身的特性,如低效的标签引发的标签干扰和读写器在实际工作中的限制等等。本文参考相关国内外文献,定义和分析几种读写器碰撞类型,并利用图论中的着色理论建立读写器碰撞模型。接着研究分析了Color-wave和HiQ这两种解决读写器碰撞问题的算法,为今后研究多读写器与多标签通讯以及移动读写器的通讯过程这些复杂问题打下了基础。
Radio Frequency Identification (RFID) is a kind of non-touching automatic identifying technology. It can automatically identify the target and get information through radio-frequency signal. RFID has unexampled advantages compared to barcode, such as reading information directly without touching; working under bad environment; the better penetrability and identifying more objects simultaneously. As one applied technology, it’s immature yet, and still has some shortcomings, like the poor accuracy rate of identifying, the slow progress of RFID standardization, etc. Among those elements, in the dense environment due to tag-collision and reader-collision problem, the lower efficiency of system will become bottleneck to the RFID technology’s application and promotion. Therefore finding a fast, accurate and reliable solution to solve the anti-collision problem is of very important significance in developing the RFID technology.
The main contents of this thesis are about the research on anti-collision algorithm of RFID systems, including tag’s and reader’s. According to the anti-collision problem of multi-tags communication Within the reading range of a single reader, the paper combine with RFID standard (mainly UHF frequencies as EPC Gen2 and ISO18000-6), and detailedly discuss ALOHA algorithm and Binary tree search algorithm along with algorithms which improved from them. Besides the performance of advantages and disadvantages and their application situation are also analyzed. Based on those work, an improved Dynamic Frame Slotted ALOHA algorithm is put forward. The proposed algorithm compared to conventional ones, when there are a large number of tags in the field, can achieve high system efficiency by grouping to restrict the number of unread tags. Simulation results show that the proposed algorithm improves the slot efficiency above 80% at least compared to the conventional algorithms when the number of tags reach 1000.
Otherwise, the anti-collision problem with respect to the environment of multi-readers, although it’s similar to the Frequency Assignment Problem experienced in cellular telephone networks, but RFID system has its own unique features, like tag interference due to the lower functionality of tag and the practical system operating constraints. Making reference to domestic and foreign literature, several types of readers collision are defined and analyzed, moreover utilizing graph coloring theory to establish collision model of readers. Subsequently, both Colorwave and HiQ algorithm which used to solve the problem of reader-collision are discussed in detail, and it will pave the way for future research on those more complicated problems, like the communication between multi-tags and multi-readers, and the communication process of mobile reader device etc.
引文
[1] Finkenzeller K著,陈大才译.射频识别技术.北京:清华大学出版社,2000,113-119
[2]张斌,姚大红.RFID技术在实时物流中的应用.价值工程,2004,23(4):117-119
[3]陈志雄.RFID发展的前景与应用分析.金卡工程,2004,8(12):49-52
[4]蒋皓石,张成,林嘉宇.无线射频识别技术及其应用和发展趋势.电子技术应用,2005,31(5):1-4
[5]游战清,李苏剑等编著.无线射频识别技术(RFID)理论与应用.北京:电子工业出版社,2004,100-123
[6]余松森,詹宜巨.基于修剪枝的二进制树形搜索反碰撞算法与实现.计算机工程,2005,31(6):217-218,300
[7]鞠伟成,俞承芳.一种基于动态二进制的RFID抗冲突算法.复旦学报,2005,44(1):46-50
[8] G Khandelwal. Efficient design of dense and time constrained rfid systems:[thesis]. Penn State:Penn State University, 2005,56-57
[9] Dimitri Bertsekas, Robert Gallager著,卢刚,王康译.Data Networks.第二版.北京:人民邮电出版社,2004,176-185
[10] J E Wieselthier,A Ephremides,L A Michels. An Exact Analysis and Performance Evaluation of Framed ALOHA with Capture. IEEE Transaction on communication. 1989,37(2):125-137.
[11]谢希人编著.计算机网络.第4版.北京:电子工业出版社,2003,35-56
[12]康东,石喜勤,李勇鹏等编著.射频识别(RFID)核心技术与典型应用开发案例.第一版.人民邮电出版社,2008,39-56
[13] International Organization for Standardization.ISO/IEC18000-6.Information Technology AIDC Techniques-RFID for Item Management . 2003-03
[14] ISO/IEC JTC 1/SC 31/WG 4N0722,ISO-18000,2003-11-26.Information technology automatic identification and data capture techniques—Radio frequency identification for item management air interface—Part6:Parameters for air interface communications at 860~960MHz
[15]姚建永,郎为民,王建秋等.EPC global组织的RFID标准.物流技术,2006(7):27-32
[16] EPC Global.EPCTM Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz~960MHz Version 1.0.9. 2005-01-31
[17]郎为民,王金泉.RFID标准化组织介绍.数字通信世界,2008(8): 70-73
[18] Robert J W.Graph Colouring and Frequency Assignment:[dissertation]. Nottingham:University of Nottingham,2005,25-29
[19]吴春华,陈军.动态ALOHA法在解决RFID反碰撞问题中的应用.电子器件,2003,26(2):173-176
[20] J R Cha, J H Kim. Dynamic framed slotted aloha algorithms using fast tag estimation method for RFID systems.IEEE Communications Society, 2006,(2):768–772
[21]孙诗东,聂景楠.扩频ALOHA多址系统吞吐量和时延性能分析.电子与信息学报,2006,28(7):1251-1254
[22] S Jain,S R Das. Collision avoidance in a dense RFID network. In:Proceedings of the 1st international Workshop on Wireless Network Testbeds, Experimental Evaluation&Amp. Los Angeles, 2006,49-56
[23] CHA J R,KIM J H.Novel anti-collision algorithms for fast object identification in RFID System.In:The 11th International Conference on Parallel and Distributed Systems. Fukuoka,2005,63-67
[24] Kin Seong Leong,Mun Leng Ng,Cole P H.The reader collision problem in RFID systems.Microwave,Antenna, Progagation and EMC Technologies for Wireless Communications,2005,1(1):658-661
[25] W K hale.Frequency assignment:Theory and applications.Proceedings of the IEEE, 1980,68(12):1497-1514
[26] Katzela I,Naghshineh M.Channel assignment schemes for cellular mobile telecommunication systems:a comprehensive survey. IEEE Personal Communica- tions,1996,3(3):10-31
[27] Ewa Malesinska.Graph-Theoretical Models for Frequency Assignment Problem: [thesis].Technischen University Berlin,1997,32-36
[28]杜清.图的边着色与频率分配.南京工程学院学报,2006,2(2):28-30
[29] J A Zoellner.Frequency assignment games and strategies.IEEE transactions on Electromagnetic Compatibility, 1973,EMC-15(4):191-196
[30] James Waldrop, Daniel W Engels,Sanjay E Sarma.Colorwave:A MAC for RFID Reader Netwoks. IEEE Wireless Communications and Networking, 2003,3(3): 1701-1704
[31] Junius Ho, Daniel W Engels, Sanjay E Sarma. HIQ:A Hierarchical Q-learning Algorithm to Solve the Reader Collision Problem. IEEE, Application and the internet Workshops,2006,4:2-8
[32] A G Barto, S J Bradtke, S P Singh. Learning to act using real-time dynamic programming. Artificial Intelligence , 1995,72:81-138
[33] Maozu Guo,Yang Liu,Malec J.A new Q-learning algorithm based on the metropolis criterion.Systems, Man, and Cybernetics, Part B, IEEE Transactions on,2004,34(4):2140-2143
[34]刘铮.非接触式IC卡中的射频识别技术.信息技术2002,4:23-25
[35]周晓光,王晓华,王伟编著.射频识别(RFID)系统设计、仿真与应用第一版.北京:人民邮电出版社,2008,23-24
[36]周祥.RFID技术在物联网中应用的关键技术探讨:[江苏大学硕士学位论文].镇江:江苏大学,2005,60-65
[37]王伟.射频识别(RFID)技术及其应用的研究.安徽师范大学学报,2008,31(2):139-141,149
[38] G Marrocco,A Fonte,F Bardati.Evolutionary design of miniaturized meander-line antennas for RFID applications.Antennas and Propagation Society International Symposium,2002,(2):362-365
[39] L Ukkonern, L Sydanheirno, M Kivikosk. A novel tag design using inverted-F antenna for radio frequency identification of metallic objects. In:Advances in Wired and Wireless Communication. Sarnoff Symposium, 2004,91-94
[40]谭民,刘禹,曾隽芳等编著.RFID技术系统工程及应用指南.北京:机械工业出版社,2007,36-58
[41]郟雁领.产品电子码(EPC)及其对图书馆的影响.农业图书情报学刊,2005,17(8):153-155
[42]姜丽芬,卢桂章,辛运帏.射频识别系统中的防碰撞算法研究.计算机工程与应用,2007,43(15):29-32
[43]刘佳,张有光.基于时隙的RFID防碰撞算法分析.电子技术应用,2007,33(5):94-96,100
[44] Vogt H. Mutiple Object Identification with Passive RFID Tags Systems.In:Man and Cybernetics,2002 IEEE International Conference.Switzerland,2002,542-648
[45]权冀川,周满珍. ALOHA系统信息到达流的概率分析.解放军理工大学学报, 2001,2(3):67-70
[46] M B Cozzens,F S Roberts.T-coloring of graphs and the channel assignment problem.Congressus Numerantium, 1996,161(3):197-205
[47]王玉宝,史亮,徐宝文.基于Q学习的复杂程序动态依赖性分析.计算机与数字工程,2005,33(2):9-11
[48] Joshi G P,Abdulla Mamun K M,Sung Won Kim.A Reader Anti-collision MACProtocol for Dense Reader RFID System.In:Communications and Mobile Computing, 2009. CMC '09. WRI International Conference on.Yunnan,2009, 313-316
[49] M R Garey,D S Johnson. Computer and Intractability: A Guide to the Theory of NP-Completeness. San Francisco:W.H. Freeman,1979,35-46
[50] C J C H Watkins.Learning from Delayed Rewards:[thesis].London:College University of Cambridge,1989,89-99
[2]张斌,姚大红.RFID技术在实时物流中的应用.价值工程,2004,23(4):117-119
[3]陈志雄.RFID发展的前景与应用分析.金卡工程,2004,8(12):49-52
[4]蒋皓石,张成,林嘉宇.无线射频识别技术及其应用和发展趋势.电子技术应用,2005,31(5):1-4
[5]游战清,李苏剑等编著.无线射频识别技术(RFID)理论与应用.北京:电子工业出版社,2004,100-123
[6]余松森,詹宜巨.基于修剪枝的二进制树形搜索反碰撞算法与实现.计算机工程,2005,31(6):217-218,300
[7]鞠伟成,俞承芳.一种基于动态二进制的RFID抗冲突算法.复旦学报,2005,44(1):46-50
[8] G Khandelwal. Efficient design of dense and time constrained rfid systems:[thesis]. Penn State:Penn State University, 2005,56-57
[9] Dimitri Bertsekas, Robert Gallager著,卢刚,王康译.Data Networks.第二版.北京:人民邮电出版社,2004,176-185
[10] J E Wieselthier,A Ephremides,L A Michels. An Exact Analysis and Performance Evaluation of Framed ALOHA with Capture. IEEE Transaction on communication. 1989,37(2):125-137.
[11]谢希人编著.计算机网络.第4版.北京:电子工业出版社,2003,35-56
[12]康东,石喜勤,李勇鹏等编著.射频识别(RFID)核心技术与典型应用开发案例.第一版.人民邮电出版社,2008,39-56
[13] International Organization for Standardization.ISO/IEC18000-6.Information Technology AIDC Techniques-RFID for Item Management . 2003-03
[14] ISO/IEC JTC 1/SC 31/WG 4N0722,ISO-18000,2003-11-26.Information technology automatic identification and data capture techniques—Radio frequency identification for item management air interface—Part6:Parameters for air interface communications at 860~960MHz
[15]姚建永,郎为民,王建秋等.EPC global组织的RFID标准.物流技术,2006(7):27-32
[16] EPC Global.EPCTM Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz~960MHz Version 1.0.9. 2005-01-31
[17]郎为民,王金泉.RFID标准化组织介绍.数字通信世界,2008(8): 70-73
[18] Robert J W.Graph Colouring and Frequency Assignment:[dissertation]. Nottingham:University of Nottingham,2005,25-29
[19]吴春华,陈军.动态ALOHA法在解决RFID反碰撞问题中的应用.电子器件,2003,26(2):173-176
[20] J R Cha, J H Kim. Dynamic framed slotted aloha algorithms using fast tag estimation method for RFID systems.IEEE Communications Society, 2006,(2):768–772
[21]孙诗东,聂景楠.扩频ALOHA多址系统吞吐量和时延性能分析.电子与信息学报,2006,28(7):1251-1254
[22] S Jain,S R Das. Collision avoidance in a dense RFID network. In:Proceedings of the 1st international Workshop on Wireless Network Testbeds, Experimental Evaluation&Amp. Los Angeles, 2006,49-56
[23] CHA J R,KIM J H.Novel anti-collision algorithms for fast object identification in RFID System.In:The 11th International Conference on Parallel and Distributed Systems. Fukuoka,2005,63-67
[24] Kin Seong Leong,Mun Leng Ng,Cole P H.The reader collision problem in RFID systems.Microwave,Antenna, Progagation and EMC Technologies for Wireless Communications,2005,1(1):658-661
[25] W K hale.Frequency assignment:Theory and applications.Proceedings of the IEEE, 1980,68(12):1497-1514
[26] Katzela I,Naghshineh M.Channel assignment schemes for cellular mobile telecommunication systems:a comprehensive survey. IEEE Personal Communica- tions,1996,3(3):10-31
[27] Ewa Malesinska.Graph-Theoretical Models for Frequency Assignment Problem: [thesis].Technischen University Berlin,1997,32-36
[28]杜清.图的边着色与频率分配.南京工程学院学报,2006,2(2):28-30
[29] J A Zoellner.Frequency assignment games and strategies.IEEE transactions on Electromagnetic Compatibility, 1973,EMC-15(4):191-196
[30] James Waldrop, Daniel W Engels,Sanjay E Sarma.Colorwave:A MAC for RFID Reader Netwoks. IEEE Wireless Communications and Networking, 2003,3(3): 1701-1704
[31] Junius Ho, Daniel W Engels, Sanjay E Sarma. HIQ:A Hierarchical Q-learning Algorithm to Solve the Reader Collision Problem. IEEE, Application and the internet Workshops,2006,4:2-8
[32] A G Barto, S J Bradtke, S P Singh. Learning to act using real-time dynamic programming. Artificial Intelligence , 1995,72:81-138
[33] Maozu Guo,Yang Liu,Malec J.A new Q-learning algorithm based on the metropolis criterion.Systems, Man, and Cybernetics, Part B, IEEE Transactions on,2004,34(4):2140-2143
[34]刘铮.非接触式IC卡中的射频识别技术.信息技术2002,4:23-25
[35]周晓光,王晓华,王伟编著.射频识别(RFID)系统设计、仿真与应用第一版.北京:人民邮电出版社,2008,23-24
[36]周祥.RFID技术在物联网中应用的关键技术探讨:[江苏大学硕士学位论文].镇江:江苏大学,2005,60-65
[37]王伟.射频识别(RFID)技术及其应用的研究.安徽师范大学学报,2008,31(2):139-141,149
[38] G Marrocco,A Fonte,F Bardati.Evolutionary design of miniaturized meander-line antennas for RFID applications.Antennas and Propagation Society International Symposium,2002,(2):362-365
[39] L Ukkonern, L Sydanheirno, M Kivikosk. A novel tag design using inverted-F antenna for radio frequency identification of metallic objects. In:Advances in Wired and Wireless Communication. Sarnoff Symposium, 2004,91-94
[40]谭民,刘禹,曾隽芳等编著.RFID技术系统工程及应用指南.北京:机械工业出版社,2007,36-58
[41]郟雁领.产品电子码(EPC)及其对图书馆的影响.农业图书情报学刊,2005,17(8):153-155
[42]姜丽芬,卢桂章,辛运帏.射频识别系统中的防碰撞算法研究.计算机工程与应用,2007,43(15):29-32
[43]刘佳,张有光.基于时隙的RFID防碰撞算法分析.电子技术应用,2007,33(5):94-96,100
[44] Vogt H. Mutiple Object Identification with Passive RFID Tags Systems.In:Man and Cybernetics,2002 IEEE International Conference.Switzerland,2002,542-648
[45]权冀川,周满珍. ALOHA系统信息到达流的概率分析.解放军理工大学学报, 2001,2(3):67-70
[46] M B Cozzens,F S Roberts.T-coloring of graphs and the channel assignment problem.Congressus Numerantium, 1996,161(3):197-205
[47]王玉宝,史亮,徐宝文.基于Q学习的复杂程序动态依赖性分析.计算机与数字工程,2005,33(2):9-11
[48] Joshi G P,Abdulla Mamun K M,Sung Won Kim.A Reader Anti-collision MACProtocol for Dense Reader RFID System.In:Communications and Mobile Computing, 2009. CMC '09. WRI International Conference on.Yunnan,2009, 313-316
[49] M R Garey,D S Johnson. Computer and Intractability: A Guide to the Theory of NP-Completeness. San Francisco:W.H. Freeman,1979,35-46
[50] C J C H Watkins.Learning from Delayed Rewards:[thesis].London:College University of Cambridge,1989,89-99