Time-Division Multiple-Access Algorithms for Radio Frequency Identification Networks
Date Issued
2012
Date
2012
Author(s)
Lin, Chun-Fu
Abstract
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.
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.
Subjects
Reader Collision Problems
Tag Identification Problems
Estimate Problem
RFID Reader Networks
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
index.html
Size
23.27 KB
Format
HTML
Checksum
(MD5):95a68a812677bf0072b6e79bfc3ba59c