臺灣大學: 資訊管理學研究所林永松林俊甫Lin, Chun-FuChun-FuLin2013-03-222018-06-292013-03-222018-06-292012http://ntur.lib.ntu.edu.tw//handle/246246/251083在採用分時多工存取（Time-Division Multiple- Access, TDMA）協定的無線射頻辨識網路（Radio Frequency Identification Networks, RFID Networks）中，存在著三類型的研究議題：第一類型，是研究如何有效處理RFID reader collision問題，這問題已被證實是一個NP-hard的問題。第二類型，是如何有效地估計位於RFID reader有效詢答區域（interrogation zone）內可能存在的RFID tag數量。第三類型，是設計一個有效的辨識演算法（Tag arbitration algorithm），使得reader可以用最少的時間，完全辨識位於其有效詢答區域內RFID tag。 在本論文中，我們分別探討上述三類型研究問題，針對第一類問題，我們提出一個廣義的數學模型，並使用Lagrangean Relaxation方法與Simulated Annealing方法來設計快速與有效的演算法來解決屬於NP hard的整數規劃問題。於第二類問題，我們提出一個全新的數學模型，來有效的估計未知的tag數量，實驗數據顯示我們的方法所產生的估計誤差值最小，在研究過程中，我們也提出完全碰撞現象（Full Collision Phenomenon），及其對大多估計演算法所產生的影響。關於第三類問題，我們提出Collision Group Algorithm（CGA），可以有效使RFID reader對其有效詢答區域內RFID tag，進行完全辨識，與其他演算法相比，我們的演算法所需時間較短，也能有效率的處理突然暴增的tag數量對系統所產生的不確定性。Recently there are three research issues giving rise to interest in Radio Frequency Identification (RFID), which adopt Time-Division Multiple-Access (TDMA) protocols: reader collision problem (RCP), estimate problem (EP) and tag arbitration problem (TAP). RCP is known to be a NP-hard problem whose best known algorithm is non-polynomial. EP is also a difficult problem because estimate has to be made based on little information derived from single reading outcome. TAP has lots of research works and some of them are even adopted by international organizations for standards. However, the design of arbitration algorithms to improve the efficiency and stability of current solutions still leaves open to be challenged. In this dissertation, we have studied RCP, EP, and TAP and proposed solutions for them. For RCP, we proposed a general mathematic framework that can describe time slot overlapping and the reader collision problem at the same time. Lagrangean Relaxation (LR) and Simulated Annealing (SA) methods were used to solve RCP. We have also proposed two heuristic algorithms that can have good solution quality of answer but take less time. For EP, we have proposed a distinct estimate model. The experimental results showed our method has the lower estimate error. The full collision phenomenon and its impact on major estimate algorithms were addressed and studied. We also proposed two sliding window methods to enhance estimate accuracy of proposed algorithm. In regard to TAP, we propose a new algorithm based on divide-and-conquer principle with alternation of two distinct reading cycles for tag arbitration on MAC layer. The proposed algorithms are useful for engineers to implement the RFID systems by setting proper frame length to enhance the current RFID standards such as ISO 18000-6 or EPC class 1 generation 2.140 bytestext/htmlen-US碰撞問題辨識問題估計問題RFID網路Reader Collision ProblemsTag Identification ProblemsEstimate ProblemRFID Reader Networksthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/251083/1/index.html