無線射頻辨識網路(Radio Frequency Identification Networks, RFID Networks)是利用讀取器(Reader)發送無線電波訊號，而標籤(Tag)接收到無線電波訊號後則將標籤內的資訊回傳給讀取器。相較於傳統的二維條碼(Barcode)擁有快速辨識的特點，也因此被大量應用於大型商場、物流業等等之中，在未來也被認為是實現物聯網(Internet of Things, IoTs)的核心技術之一。
在大多數的物聯網應用中，都需要使用大量的讀取器，但由於讀取器過於密集造成讀取碰撞與讀取率過低的問題產生，這種現象稱為讀取器干擾問題。因此如何避免讀取器干擾發生是相當重要的議題。為了解決讀取器干擾的問題需要從兩個層面著手，首先必須要對讀取器網路佈署，佈署後得以減緩讀取器干擾，但若僅依靠讀取器佈署來避免干擾發生，這會使得硬體的建置成本大幅提升，因此還需從軟體方面著手，也就是讀取器網路防碰撞演算法，唯有從軟體與硬體這兩層面著手，才能夠使讀取器干擾盡可能降到最低。
讀取器佈署問題下，現有的方式皆是採取最佳化演算法(如GA)求解，其中的目標函數為評估拓樸的核心，目前大多數的成本目標都會造成拓樸偏頗，因此我們提出另一種成本評估方式，並改良出新的最佳化演算法(IGAA)，使得讀取器網路佈署可以較符合需求，最後也提出一種階段性的最佳化演算法。
讀取器防碰撞問題下，現有的TDMA方法有DCS、ColorWave、ColorTable等等，這些方法中由於動態調整時槽數造成傳輸成功率不穩定，並且讀取器網路在越複雜環境下，會因為改選方式的關係造成kick連鎖效應，因此我們提出交換改選方式來取代現有的改選方式並引入四色理論來解決這些問題，最後為了找出最好的效能，我們將所提的演算法與現有的演算法做混合。
最後實驗結果證實，在讀取器佈署問題下，我們所提新成本目標與IGAA能得到更好的拓樸，而所提階段性的最佳化演算法能夠以少量時間且使各目標發展更明確。另一方面證實，在讀取器防碰撞問題下，我們所提出的交換改選方式能夠減少kick連鎖效應、應用四色理論後能夠解決動態調整時槽數的問題，且混合式演算法確實能夠得到較高的成功率與吞吐量。

The radio Frequency Identification (RFID) Networks send radio signals to tags via readers. After tags receive radio signals, they will respond their information to readers. Compared with the two-dimensional barcode, the RFID has high efficiency. Thus, the RFID has been considered as one of the principal building blocks for realizing the Internet of Things (IoTs) concept.
In IoTs, most RFID applications (for instance, a supermarket or logistics management) use multiple readers to read the IDs of multiple tags and form the RFID network. Unguarded reader deployment (for instance, readers are largely or randomly deployed) may generate over-crowded readers in the RFID network and therefore brings up interferences. How to avoid interferences between any two readers that is an important topic. The RFID network has to deploy topology which is called the reader deployment in order to solve interferences. Interferences can be reduced after the reader deployment, but it makes high cost of hardware. The RFID network thus has to consider software solution which is called the reader anti-collision. They can minimize interferences when the reader deployment and the reader anti-collision were solved.
In the reader deployment, solutions use optimization algorithms (for instance, the GA) in existing literatures. Optimization algorithms use objective fitness function to evaluate topology, but the cost objective function may lead to biased reader deployment in existing literatures. We thus propose a new cost objective function and improved optimization algorithm (IGAA), which can create a suitable RFID network topology. Finally, we propose a non- optimization algorithm.
In the reader anti-collision, TDMA solutions have DCS, ColorWave, ColorTable and so on. They are the kick effect problem and the dynamic MaxColor problem in complex RFID networks. We thus propose a switch mechanism and the four-color theorem to solve these problems. Finally, we propose a new hybrid algorithm which combines existing algorithms with ours in order to find the best performance.
Simulation results show the cost objective function and IGAA have better performance in the reader deployment. The non-optimization algorithm can reduce processing time and obtain competitive performance. On the other hand, the switch mechanism and the four-color theorem can solve the kick effect problem and the dynamic MaxColor problem in the reader anti-collision. Our hybrid algorithm can obtain favorable performance and achieve high throughput.

目錄
第一章、緒論 1
1.1、研究動機 1
1.2、問題描述與解決方案 2
1.3、論文架構 6
第二章、相關研究背景 7
2.1、讀取器網路佈署 7
2.1.1、目標函數 7
2.1.2、最佳化演算法 12
2.2、讀取器網路防碰撞 20
2.2.1、DCS 21
2.2.2、ColorWave 24
2.2.3、ColorTable 29
2.2.4、評估比較 38
第三章、提出之新方法 40
3.1、讀取器網路佈署方式 40
3.1.1、改良目標函數 40
3.1.2、改良式基因退火演算法 42
3.1.3、階段性最佳化演算法 47
3.2、讀取器網路防碰撞演算法 63
3.2.1、SwitchTable的新概念 63
3.2.2、基於SwitchTable的新方法 65
3.2.3、與現有方法之混合 71
第四章、模擬評估 76
4.1、讀取器網路佈署之評估 76
4.1.1、改良目標函數 77
4.1.2、改良式基因退火演算法 77
4.1.3、階段性最佳化演算法 83
4.2、讀取器網路防碰撞之評估 92
4.2.1、基於SwitchTable的新方法 93
4.2.2、混合式演算法 96
第五章、結論 99
參考文獻 102

圖目錄
圖1.1、Reader-to-Tag干擾 3
圖1.2、Reader-to-Reader干擾 3
圖2.1、y=1/x函數關係 8
圖2.2、重疊面積限制 9
圖2.3、無用讀取器 10
圖2.4、冗餘讀取器 10
圖2.5、重疊面積內的標籤數限制 11
圖2.6、總覆蓋標籤數 11
圖2.7、基因演算法流程圖 14
圖2.8、基因退火演算法流程圖 17
圖2.9、200次迭代下GA與GAA的適應值比較 19
圖2.10、DCS虛擬碼 22
圖2.11、DCS傳送端流程圖 23
圖2.12、DCS接收端流程圖 24
圖2.13、ColorWave虛擬碼 26
圖2.14、ColorWave傳送端流程圖 28
圖2.15、ColorWave接收端流程圖 29
圖2.16、ColorRule虛擬碼 30
圖2.17、ColorTable虛擬碼 32
圖2.18、讀取器網路拓樸 33
圖2.19、讀取器網路中碰撞前ColorTable 33
圖2.20、讀取器網路中碰撞後ColorTable 35
圖2.21、ColorTable傳送端流程圖 36
圖2.22、ColorTable接收端流程圖 38
圖3.1、改良目標函數之情況一 41
圖3.2、改良目標函數之情況二 42
圖3.3、改良目標函數之情況三 42
圖3.4、GAA虛擬碼 43
圖3.5、IGAA虛擬碼 44
圖3.6、Transform虛擬碼 45
圖3.7、改良式基因退火演算法流程圖 46
圖3.8、階段性的最佳化演算法流程圖 49
圖3.9、初始化佈署 51
圖3.10、第一個讀取器佈署Ci值計算 52
圖3.11、第一個讀取器佈署成功 53
圖3.12、第二個讀取器佈署Ci值計算 53
圖3.13、第二個讀取器佈署成功 54
圖3.14、第三個讀取器佈署Ci值計算 54
圖3.15、重新第三個讀取器佈署Ci值計算 55
圖3.16、第三個讀取器佈署成功 55
圖3.17、第四個讀取器佈署Ci值計算 56
圖3.18、重新第四個讀取器佈署Ci值計算 56
圖3.19、佈署讀取器流程圖 57
圖3.20、第四個讀取器佈署成功 58
圖3.21、讀取器R3嘗試功率放大 59
圖3.22、讀取器R3功率放大成功 60
圖3.23、放大讀取器功率流程圖 61
圖3.24、降低讀取器功率 61
圖3.25、降低讀取器功率流程圖 62
圖3.26、SwitchRule虛擬碼 65
圖3.27、SwitchTable虛擬碼 67
圖3.28、讀取器網路中碰撞前SwitchTable 68
圖3.29、讀取器網路中碰撞後SwitchTable 69
圖3.30、SwitchTable傳送端流程圖 70
圖3.31、SwitchTable接收端流程圖 71
圖3.32、DCS於不同讀取器網路情況 73
圖3.33、混合式演算法流程圖 75
圖4.1、加入成本函數後的差異 77
圖4.2、200次迭代下IGAA的適應值比較 78
圖4.3、收斂時的適應值 79
圖4.4、收斂時的複雜度 79
圖4.5、收斂時的迭代次數 80
圖4.6、收斂時的超出重疊面積限制的區塊數量 80
圖4.7、收斂時的無用讀取器數量 81
圖4.8、收斂時的冗餘讀取器數量 81
圖4.9、收斂時的超出重疊面積內標籤限制的區塊數量 82
圖4.10、收斂時的未覆蓋的標籤數量 82
圖4.11、收斂時的成本 83
圖4.12、適應值 84
圖4.13、處理時間 85
圖4.14、超出重疊面積限制的區塊數量 85
圖4.15、無用讀取器數量 86
圖4.16、冗餘讀取器數量 87
圖4.17、超出重疊面積內標籤限制的區塊數量 87
圖4.18、未覆蓋的標籤數量 88
圖4.19、成本 88
圖4.20、各佈署依據的適應值 90
圖4.21、各佈署依據的實際計算量 91
圖4.22、各佈署依據的未覆蓋標籤數量 91
圖4.23、各佈署依據的成本 92
圖4.24、簡單讀取器網路的傳輸成功率 93
圖4.25、簡單讀取器網路的吞吐量 94
圖4.26、一般讀取器網路的傳輸成功率 95
圖4.27、一般讀取器網路的吞吐量 95
圖4.28、複雜讀取器網路的傳輸成功率 96
圖4.29、複雜讀取器網路的吞吐量 96
圖4.30、隨機讀取器網路的傳輸成功率 97
圖4.31、隨機讀取器網路的吞吐量 97
圖4.32、時變讀取器網路的傳輸成功率 98

表目錄
表2.1、評估最佳化演算法 18
表2.2、評估防碰撞演算法 39
表3.1、階段性的最佳化演算法之階段性檢測項目 48
表3.2、標籤座標 50
表3.3、標籤距離關係 51
表3.4、平均相鄰數於不同網路環境下 74
表3.5、DCS傳輸成功率於不同網路環境下 74
表4.1、最佳化演算法模擬參數 76
表4.2、階段性的最佳化演算法模擬參數 83
表4.3、比較增加讀取器功率與數量 89
表5.1、評估IGAA演算法 99
表5.2、評估SwitchTable演算法 101

[1] L. Sanchez and V. Ramos, “Towards a new paradigm for RFID identification: Should we cluster RFID tags or not?,” in Proc. Wireless and Mobile Computing, Networking and Communications (WiMob), Lyon , Oct. 7-9, 2013, pp. 444-451.
[2] S. Ma, Y. Zhang and D. Wang, “Distributed work flow system for RFID integration and application,” in Proc. Information, Computing and Telecommunication, Beijing, Sept. 20-21 , 2009, pp. 62-65.
[3] L. D. Xu, W. He, and S. Li, “Internet of Things in industries: A survey,” Industrial Informatics, vol. 10, Nov. 2014, pp. 2233-2243.
[4] G. Fortino, A. Guerrieri, W. Russo and C. Savaglio, “Integration of agent-based and Cloud Computing for the smart objects-oriented IoT,”  in Proc.Computer Supported Cooperative Work in Design (CSCWD), Hsinchu, May 21-23, 2014, pp. 493-498.
[5] I. Ganchev, Z. Ji and M. O'Droma, “A generic IoT architecture for smart cities,” in Proc. Irish Signals & Systems Conference 2014 and 2014 China-Ireland International Conference on Information and Communications Technologies (ISSC 2014/CIICT 2014). 25th IET, Limerick, June 26-27, 2013, pp. 196-199.
[6] T. Yashiro, S. Kobayashi, N. Koshizuka and K. Sakamura, “An Internet of Things (IoT) architecture for embedded appliances,” in Proc. Humanitarian Technology Conference (R10-HTC), Aug. 26-29, 2013, pp. 314-319.
[7] F. Hussian, S. Durrani, J. Farooqi, H. Mahmood, G. Junjua, I. Jattala and N. Ikram, “RFID & WSN based integrated maternity ward monitoring system,” in Proc. Multi Topic Conference (INMIC), Lahore , Dec. 19-20, 2013, pp. 43-48.
[8] W. Chun, E. Noel and K.W. Tang, “The tag duplication problem in an integrated WSN for RFID-based item-level inventory monitoring,” in Proc. Networked Sensing Systems, Kanazawa, June 17-19, 2008, pp. 59-62.
[9] L. Wang, L. D. Xu, Z. Bi and Y. Xu, “Data Cleaning for RFID and WSN Integration,” IEEE Transactions on Industrial Informatics, vol. 10, Feb. 2014, pp. 408-418.
[10] Y. Kang, M. Kim and H. Lee, “A hierarchical structure based reader anti-collision protocol for dense RFID reader networks,” in Proc. Advanced Communication Technology (ICACT), Seoul, Feb. 13-16, 2011, pp. 164-167.
[11] C.-Y. Chiu, C.-H Ke and K.Y. Chen, “Optimal RFID networks scheduling using genetic algorithm and swarm intelligence,”  in Proc. Systems, Man and Cybernetics, San Antonio, TX, Oct. 11-14, 2009, pp. 1201-1208.
[12] X.-m. Zhang, Q.-k. Yan and J. Li, “The planning of workshop RFID network based on modified genetic algorithm using metropolis rule,” in Proc. Industrial Engineering and Engineering Management (IE&EM), Changchun, Sept. 3-5, 2011, pp. 778-781.
[13] H.-L. Ding, W. W. Y. Ng, P. P. K. Chan, D. S. Yeung and D.-L. Wu, “RFID reader deployment using RBFNN with L-GEM,” in Proc. Machine Learning and Cybernetics (ICMLC), Qingdao, July 11-14, 2010, pp. 1153-1158.
[14] Y. Gao, X. Hu, L. Peng, H. Liu and F. Li, “A differential evolution algorithm combined with cloud model for RFID reader deployment,” in Proc. Advanced Computational Intelligence (IWACI), Wuhan, Oct. 19-21, 2011, pp. 193-198.
[15] M. Ma, P. Wang and C.-H. Chu, “A novel distributed algorithm for redundant reader elimination in RFID networks,” in Proc. RFID-Technologies and Applications (RFID-TA), Johor Bahru, Sept. 4-5, 2013, pp. 1-6.
[16] O. Botero and H. Chaouchi, “RFID network topology design based on genetic algorithms,” in Proc. RFID-Technologies and Applications (RFID-TA), Sitges, Sept. 15-16, 2011, pp. 300-305.
[17] P.-J. Chuang, C.-H. Wei, and Y.-S. Chiu, “GAA: A new optimization technique for task matching and scheduling in HCSs,” Journal of Information Science and Engineering, vol. 21, Mar. 2005, pp. 287-308.
[18] M. Mitchell, An Introduction to Genetic Algorithms, Cambridge: MIT Press, 1996.
[19] Z. P. Lo and B. Bavarian, “Job scheduling on parallel machines using simulated annealing,” in Proc. 1991 IEEE Int’l Conf. on Systems, Man, and Cybernetics, Charlottesville, VA, Oct. 13-16, 1991, pp. 391-396. 
[20] C. Y. Shen, Y. H. Pao, and P. Yip, “Scheduling multiple job problems with guided evolutionary simulated annealing approach,” in Proc. 1st IEEE Conf. on Evolutionary Computation, Orlando, FL ,Jun. 27-29, 1994, pp. 702-706.
[21] J. Ho, D.W. Engels and S.E. Sarma, “HiQ: a hierarchical Q-learning algorithm to solve the reader collision problem,” in Proc. Applications and the Internet Workshops, 2006. SAINT Workshops 2006. International Symposium on, Jan. 23-27, 2006.
[22] J. Waldrop, D.W. Engels and S.E. Sarma, “Colorwave: a MAC for RFID reader networks,” in Proc. Wireless Communications and Networking, New Orleans, LA, Mar. 20-20, 2003, pp. 1701-1704.
[23] J. Waldrop, D.W. Engels and S.E. Sarma, “Colorwave: an anticollision algorithm for the reader collision problem,” in Proc. Communications, 2003. ICC '03. IEEE International Conference on, May 11-15, 2003, pp. 1206-1210. 
[24] S. Zhou, Z. Luo, E. Wong, “Interconnected RFID reader collision model and its application in reader anti-collision,” in Proc. of 2007 IEEE International Conference On RFID Gaylord Texan Tesort, Grapevine, TX, Mar. 26-28, 2007, pp. 212-219.
[25] “ETSI EN 302 208-1 v1.4.1,” Nov. 2011. [Online]. Available :www.etsi.org.
[26] S. Birari and S. Iyer, “Mitigating the reader collision problem in RFID networks with mobile readers,” in Proc. 13th IEEE International Conference on Networks, Nov. 16-18, 2005, pp. 463-468.
[27] X. Zeng and J. Tian, “Solution to both frequency interference and tag interference of RFID system,” in Proc. Intelligent Control and Information Processing (ICICIP), Dalian, July 15-17, 2012, pp. 555-559.
[28] T. Chen, Y. Yang and B. Yang, “RFID Dense Reader Network Anti-collision PSO Model and Solving,” in Proc. Intelligent Human-Machine Systems and Cybernetics (IHMSC), Zhejiang, Aug. 26-27, 2011, pp. 92-96.
[29] J.-B. Eom, S.-B. Yim and T.-J. Lee, “An Efficient Reader Anticollision Algorithm in Dense RFID Networks With Mobile RFID Readers,” IEEE Transactions on Industrial Electronics, vol. 56, July 2009, pp. 2326-2336.
[30] S.-Y. Lin and L.-W. Wei, “Color table based distributed collision avoidance algorithm for RFID reader network,” in Proc. Computational Problem-Solving (ICCP), Leshan, Oct. 19-21, 2012, pp. 35-39.
[31] K. Appel, W. Haken, The solution of the four-color-map problem. Scientific American, 1977.