應用於無線射頻辨識網路之分時多工擷取演算法

在採用分時多工存取（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數量對系統所產生的不確定性。

關鍵字

碰撞問題；辨識問題；估計問題； RFID網路

並列摘要

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.

並列關鍵字

Reader Collision Problems ； Tag Identification Problems ； Estimate Problem ； RFID Reader Networks

參考文獻

[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, “Network flows: theory, algorithms and applications,” Prentice-Hall, 1993.

[3] Auto-ID Center, “Draft protocol specification for a 900 MHz class 0 radio frequency identification tag,” February, 2003.

[4] S.M. Birari and S. Iyer, “Mitigating the reader collision problem in RFID networks with mobile readers,” 13th IEEE International Conference on Networks, (ICON), November, 2005.

[5] M.A. Bonuccelli, F. Lonetti, and F.Martelli, “Instant collision resolution for tag identification in RFID networks,” Elsevier Ad Hoc Networks, November, 2007.

[7] J. I. Capetanakis, “Tree algorithms for packet broadcast channels,“ IEEE Transactions on Information Theory, vol. 25, issue 5, pp. 505-515, September, 1979.

國際替代計量

應用於無線射頻辨識網路之分時多工擷取演算法

全文下載

主題瀏覽