整合基因演算法與二進制粒子群演算法於無線射頻辨識網絡排程問題之研究

Integration of Genetic Algorithms and Binary Particle Swarm Optimization for RFID Networks Scheduling Problems

柯政昕(Cheng-Hsin Ke)

指導教授 ： 邱垂昱

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2009年)

https://doi.org/10.6841/NTUT.2009.00503

摘要

許多的無線射頻辨識(RFID)讀取器已被導入在許多產業的生產線上，而這些RFID讀取器又有許多不同的種類。而在無線射頻辨識網絡裡，RFID讀取器之間會存在訊號碰撞(collision)的問題，這將會導致錯誤的讀取或是讀取不到RFID標籤。本篇研究提出了一個整合基因演算法(Genetic Algorithms)與二進制粒子群演算法(Binary Particle Swarm Optimization)的啟發式演算法(GA-BPSO)對此問題進行求解並得到最佳化排程的結果。而GA-BPSO這個方法結合了基因演算法(Genetic Algorithms)與二進制粒子群演算法(Binary Particle Swarm Optimization)各自的優點。我們使用GA-BPSO來對3個無線射頻辨識網絡問題進行求解，目標是希望得到最小的總處理時間。藉由求解的結果，我們可以認定GA-BPSO是一個有效的演算法，它可以在此問題中找到最佳解。

關鍵字

無線射頻辨識網絡 ； 訊號碰撞 ； 排程

並列摘要

Multi RFID readers are implemented to the product line in many industries and they consist of varied reader resources. There are collisions occurring between readers, and that cause the faulty or missing reads in the network of RFID readers. This research attempts to use integration of genetic algorithms and binary particle swarm optimization (GA-BPSO) to solve the problem and get the optimal scheduling result in the problem. GA-BPSO is combined with advantages of PSO and GA. We use GA-BPSO to solve three problems of the RFID reader network and we attempt to minimize the total transaction time. By the results of the three problems, we can conclude that GA-BPSO is an effective algorithm which can find optimal solutions in the problem of the RFID reader network.

並列關鍵字

the network of RFID readers ； collisions ； scheduling

參考文獻

[14] G. L. Miller, S.-H. Teng, W. Thurston and S. A. Vavasis, “Automatic mesh partitioning in sparse matrix computations: Graph theory issues and algorithms,” an IMA workshop volume, 1993.

[1] A. George and J. W.-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Englewood Cliffs: Prentice-Hall, 1981.

[2] A. Kretsovalis and R. S. H. Mah, “Effect of redundancy on estimation accuracy in process data reconciliation,” Chemical Engineering Science, vol. 42, no. 9, 1987, pp. 2115-2121.

[3] A. Pothen, H. D. Simon and K.-P. Liou, “Partitioning sparse matrices with eigenvectors of graphs,” SIAM Journal of Matrix Analysis and Applications, vol. 11, no. 3, 1990, pp. 430–452.

[4] A. L. Buczak, H. Darabi and M.A. Jafari, “Research on genetic algorithm convergence for sensor network optimization problem,” Information Sciences, vol. 5, no. 1, 2000, pp. 1035-1039.