臺灣博碩士論文加值系統

RFID (Radio Frequency Identification) 之技術的迅速推廣與發展近年來快速促進 RFID 系統大規模的發展和研究，特別在關於 RFID 防止碰撞和多餘的 RFID 讀取器在未知的範圍內如何有效的移除，此類問題不斷被廣泛研究及探討。不同的演算法被許多研究人員所提出，以彼此的經驗和法則找出最有效的方案解決這兩個領域的問題。在這篇文章裡，我們提出利用讀取器與讀取器間的距離為參數來優化利用分層移除讀取器之方法的最佳化技術 Distance Based Optimization for Eliminating Redundant Readers (DBO) ，此方法完全適用在移除多餘的 RFID 讀取器，其目的便是為了要識別出 RFID 讀取器浪費之最高數量，並利用最有效且最快速之方法移除最多之多餘的 RFID 讀取器，而 RFID 網路所涵蓋的範圍也會在這方法下保有最佳範圍。我們所提出的 DBO 是一種最佳化的獨立演算法和技術，DBO 程序可大幅降低對標籤的記憶體寫入次數。而且 RFID 讀取器之間不需要互相通訊與交換資料，更不需要花費時間在同步上，也不需收集區域資訊再透過主從式架構集中控制。以上所提都是 DBO 程序的優點，且在演算法的效能評估我們製作了周全的實驗並與其他類別的演算法以多重交叉比較的方式來實現 DBO 技術評估。特別於我們的實驗成果上，在多餘的 RFID 讀取器的識別及降低演算法多餘之花費上都明顯的顯示 DBO 程序演算法是最有效的方法。

The RFID (Radio Frequency Identification) have been developed and promoted rapidly for the past few years. The researches and discussions mainly focus on preventing collisions of RFID and removing redundant RFID readers. Different methods have been proposed by researchers in order to solve the two issues effectively. In this thesis, the Distance Based Optimization for Eliminating Redundant Readers (DBO) method that we proposed, the distance between RFID readers is used as parameter for removing redundant RFID readers. The maximum waste RFID readers can be identified and maximum redundant RFID readers can be removed by using the DBO method. The optimized coverage range of RFID is retained also. The DBO method is based on Layered Optimization Approach for Redundant Reader Elimination in Wireless RFID Networks (LEO) [8]; however, the LEO method is improved and optimized by the DBO method. The I/O of RFID tags is reduced vastly. Neither the communication nor the synchronization between RFID readers is needed. The local information and client-server architecture are not needed anymore. In order to evaluate the result of our method, we established an experiment to compare with other methods. The experiment result shows that our method is very effective on identifying and removing the redundant RFID readers.

摘 要 …………………………………………………………………………i
ABSTRACT …………………………………………………………………………ii
致 謝 ………………………………………………………………………iii
目 錄 ………………………………………………………………………iv
圖 目 錄 …………………………………………………………………………v
表 目 錄 …...……………………………………………………………………vii
Chapter 1 緒論 …………………………………………………………………………1
1.1 研究動機 …………………………………………………………………………1
1.2 研究目的 ………………………………………………………………………………1
1.3 論文架構 ………………………………………………………………………………2
Chapter 2 相關研究 …………………………………………………………………………3
2.1 背景介紹 ………………………………………………………………………………3
2.2 RRE演算法 …………………………………………………………………………6
2.3 LEO演算法 …………………………………………………………………………8
Chapter 3 分層式消除法LEO的缺點探討 ……………………………………………14
Chapter 4以距離為基礎之RFID網路佈署最佳化 ………………………………………17
Chapter 5 效能評估 ………………………………………………………………………25
5.1 實驗模擬 ……………………………………………………………………………25
5.2 實驗結果 ……………………………………………………………………………32
Chapter 6 結論與未來研究方向 ……………………………………………………………34
Chapter 7 參考文件 ……………………………………………………………………………………36

[1] Shailesh M. Birari and Sridhar Iyer, “Mitigating The Reader Collision Problem in RFID Networks”, International Conference on Networking (ICON), 2005.
[2] Bogdan C˘arbunar, Murali Krishna Ramanathan, Mehmet Koyut¨urk, Christoph Hoffmann and Ananth Grama, “Redundant Reader Elimination in RFID Systems”, Proceedings of IEEE SECON, pp. 176-184, 2005.
[3] Bogdan C˘arbunar, “Coverage problems in wireless sensor and RFID system,” Technical Report 2005-40 Purdue University 2005.
[4] M. Cardei and J. Wu. “Coverage in Wireless Sensor Networks. Handbook of Sensor Networks,” CRC Press, 2004
[5] J. R. Cha and J. H. Kim, “Novel Anti-collision Algorithms for Fast Object Identification in RFID system,” in Proc. ICPADS2005, Fukuoka, Japan, Jul. 20-22, 2005, pp. 63-67
[6] J. R. Cha and J. H. Kim, “Dynamic Framed Slotted ALOHA Algorithm using Fast Tag Estimation method for RFID System,” in Proc. CCNC2006, Las Vegas, USA, Jan. 8-10, 2006.
[7] D. W. Engels and S. E. Sarma, “The reader collision problem,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 2002.
[8] Ching-Hsien Hsu, Yi-Min Chen and Chao-Tung Yang, “A Layered Optimization Approach for Redundant Reader Elimination in Wireless RFID Networks”, Proceedings of the IEEE APSCC, pp. 138–145, 2007.
[9] Junius Ho, Daniel W. Engels and Sanjay E. Sarma, “HiQ: A Hierarchical Q-Learning Algorithm to Solve the Reader Collision Problem,” Proceedings of the International Symposium on Applications and the Internet Workshops (SAINTW'06), pp. 88-91, 2006.
[10] Nazish Irfan and Mustapha C.E. Yagoub, “Efficient Approach for Redundant Reader Elimination in Large-Scale RFID Networks”, Proceedings of the IEEE ICIIC, pp. 102, 2010.
[11] Ari Juels, Ronald L. Rivest, and Michael Szydlo, “The blocker tag: selective blocking of RFID tags for consumer privacy,” Proceedings of the 10th ACM Conference on Computer and communications security, pp. 103–111, 2003.
[12] Joongheon Kim, Sunhyoung Kim, Dongshin Kim, Wonjun Lee and Eunkyo Kim, “Low-Energy Localized Clustering: An Adaptive Cluster Radius Configuration Scheme for Topology Control in Wireless Sensor Networks,” Proceedings of the IEEE Vehicular Technology Conference (VTC), pp. 2546-2550, 2005.
[13] Sanjay E. Sarma, Stephen A. Weis, and Daniel W. Engels, “RFID systems and security and privacy implications,” Proceedings of the 4th international workshop on Cryptographic Hardware and Embedded Systems, LNCS 2523, pp. 454–469.
[14] Sasa Slijepcevic and Miodrag Potkonjak, “Power efficient organization of wireless sensor networks,” Proceedings of IEEE ICC, pp. 472-476, 2001.
[15] Joao Luıs Sobrinho, Roland de Haan and Jose Manuel Brazio, “Why RTS-CTS is not your ideal wireless LAN multiple access protocol,” Proceedings of the IEEE Wireless Communications and Networking Conference, pp. 81-87, 2005.
[16] Di Tian and Nicolas D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” Proceedings of the 1st ACM WSNA’02, pp. 32–41, 2002.
[17] James Waldrop, Daniel W. Engels and Sanjay E. Sarma, “Colorwave: an anticollision algorithm for the reader collision problem,” Proceedings of the IEEE International Conference on Communications, pp. 1206-1210, 2003.
[18] Xin Wang and Koushik Kar, “Throughput modelling and fairness issues in CSMA/CA based ad-hoc networks,” Proceedings of the 24th Annual Joint Conference on IEEE Computer and Communications Societies (INFOCOM 2005), pp. 23 – 34, 2005.
[19] Stephen Weis, Sanjay E. Sarma, Ronald L. Rivest and Daniel W. Engels, ”Security and privacy aspects of low-cost radio frequency identification systems,” Security in Pervasive Computing, LNCS 2803, pp. 201-212, 2004.
[20] Fun Ye, Shiann-Tsong Sheu, Tobias Chen and Jenhui Chen, “The Impact of RTS Threshold on IEEE 802.11 MAC Protocol,” Tamkang Journal of Science and Engineering, Vol. 6, No. 1, pp. 57-63 2003.
[21] Fan Ye, Gary Zhong, Songwu Lu and Lixia Zhang, “Peas: a robust energy conserving protocol for long-lived sensor networks,” Proceedings of the 23rd IEEE ICDCS, pp.28-37, 2003.
[22] Kun-Ming Yu, Chang Wu Yu and Zheng-Yi Lin, “A Density-Based Algorithm for Redundant Reader Elimination in a RFID Network”, Proceedings of the IEEE FGCN, pp. 89, 2008.
[23] Zhi-Ying Yang and Jun-Liang Chen, “The Simulation and Analysis of Algorithms for Redundant Reader Elimination in RFID System”, Proceedings of the IEEE EMS, pp. 494, 2009.
[24] Honghai Zhang and Jennifer C. Hou, “Maintaining sensing coverage and connectivity in large sensor networks,” Wireless Ad Hoc and Sensor Networks: An International Journal, Vol. 1, No. 1-2, pp. 89-123, January 2005.