一种基于图论的RFID防冲突建模与优化方法  

An Approach of RFID Anti-Collision Modeling and Optimizing Based on Graph Theory

作　　者：陈泰伟[1] 项颖[1] 吴黎明[1] 吴学文[1] 

机构地区：[1]广东工业大学信息工程学院,广东广州510006

出　　处：《微电子学与计算机》2012年第1期155-158,163,共5页Microelectronics & Computer

摘　　要：针对RFID系统的超高频段、多读写器的静态拓扑结构,研究了读写器冲突问题,并提出了一种图论的图着色算法与遗传算法相结合的防冲突干扰方法.该静态预定义算法对读写器冲突建立图论模型,将读写器时隙分配问题转化为图论模型的K-顶点着色问题,优化遗传算法并用于求解图的K-顶点着色问题,求得最小时隙数和最优时隙分配方案.最后将算法应用于算例.实验结果表明该方法可行、实用,能够有效地防止读写器冲突干扰.Based on the study of the read collision in the static topology multi-UHF RFID network,a new anti-collision scheme by making use of graph coloring and genetic algorithm is present.After developing a read collision graph model,this preset algorithm convert time assignment into the problem of k-vertex graph coloring,and optimize genetic algorithms to solve the problem of k-vertex graph coloring,at last get the smallest timeslots and acquire the most optimal solution,and finally,the instance is presented.The simulation result shows that the scheme is practical and feasible.It also implies that it is effective for RFID anti-collision.

关 键 词：UHFRFID 读写器冲突 图着色 遗传算法 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]