請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65517
標題: | 應用於無線射頻辨識網路之分時多工擷取演算法 Time-Division Multiple-Access Algorithms for Radio Frequency Identification Networks |
作者: | Chun-Fu Lin 林俊甫 |
指導教授: | 林永松(Frank Yeong-Sung Lin) |
關鍵字: | 碰撞問題,辨識問題,估計問題,RFID網路, Reader Collision Problems,Tag Identification Problems,Estimate Problem,RFID Reader Networks, |
出版年 : | 2012 |
學位: | 博士 |
摘要: | 在採用分時多工存取(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65517 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 7.21 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。