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

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

针对RFID系统的超高频段、多读写器的静态拓扑结构,研究读写器冲突问题,并提出了一种图论的图着色算法与遗传算法相结合的防冲突干扰方法.该静态预定义算法对读写器冲突建立图论模型,将读写器时隙分配问题公式化为图论模型的K一顶点着色问题,优化遗传算法并用于求解图的K一顶点着色问题,以求得读写器网络所需的最小时隙数和最优的时隙分配方案.最后将该算法应用于实例.实验结果表明该方法具有可行性和实用性,并能够有效地防止读写器冲突干扰.

Based on the study of the UHF RFID reader collision in the multi-reader static topological network, in this paper, a new reader anti-collision approach by making use of graph coloring and genetic algorithm is proposed. By modeling a reader collision graph, this preset algorithm converts time slot assignment into the problem of K-vertex graph coloring, and optimizes genetic algorithms to solve the problem of K-vertex graph coloring, in order to find out the minimum time slot number and its optimal assignment. Finally, this algorithm is applied to an instance. The simulation shows that the reader anti-collision algorithm is effective, practical and feasible for UHF RFID reader to defend collision.