Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
อัลกอริทึมการแก้ปัญหาการชนแบบต้นไม้สำหรับอาร์เอฟไอดีโดยใช้การประมาณจำนวนแทกแบบเบยส์
Year (A.D.)
2017
Document Type
Thesis
First Advisor
Lunchakorn Wuttisittikulkij
Second Advisor
Warakorn Srichavengsup
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Electrical Engineering (ภาควิชาวิศวกรรมไฟฟ้า)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Electrical Engineering
DOI
10.58837/CHULA.THE.2017.195
Abstract
Radio Frequency IDentification (RFID) is a promising wireless object identifying technology which uses radio frequency waves to transmit data between an RFID reader and tags. The RFID systems have been effectively applied in different areas, like manufacturing, healthcare, supply chain, transportation and agriculture. Despite the vast deployment of the RFID technology in practice, the inherent RFID tag collision problem still persists as a serious concern and remains a challenge. The tag collision problem happens when some tags in reader's vicinity try to transmit data to a reader simultaneously without priori coordination. The existing RFID Electronic Product Code (EPC) Class 1 Generation 2 (Gen 2) industrial standard family uses the Q algorithm as its anti-collision protocol to resolve the tag collision problem. As the Q algorithm relies on the concept of ALOHA protocols, the achievable maximum system efficiency is only around 34%. In this thesis, we propose two novel anti-collision protocols, namely Bayesian Estimation based Modified Dynamic Tree (BE-MDT) and Binary Splitting Modified Dynamic Tree (BS-MDT), which outperform all existing anti-collision protocols. Both protocols use two phases of operations, i.e., estimate the amount of tags in the system and identify all of them. In the first phase of BE-MDT, we propose a slotted ALOHA based Bayesian tags estimation method which can accumulate the prior knowledge in each slot to estimate the amount of tags in the system and decide the initial frame size to use in the second phase. In the second phase of BE-MDT, we introduce Modified Dynamic Tree (MDT) algorithm which takes the estimated frame size in the first phase as the initial frame and follow by a definite collision skip binary tree algorithm to identify the tags. In our second algorithm, which is BS-MDT, we follow a binary splitting-based tag estimation method in the first phase and use the MDT algorithm in the second phase with a technique to estimate the initial frame size to maximize the system efficiency for any range of tags. We also present the mathematical models for each algorithm to determine the system efficiency and time system efficiency. The mathematical models are validated through computer simulations. Numerical results confirm that the BE-MDT achieve the system efficiency of 45% and the time system efficiency is 78%, whereas the BS-MDT achieves the system efficiency of 46% and the time system efficiency of 80%.
Other Abstract (Other language abstract of ETD)
การระบุด้วยความถี่วิทยุ (อาร์เอฟไอดี) คือ เทคโนโลยีติดตาม/ระบุวัตถุอัตโนมัติแบบไร้สาย โดยใช้คลื่นความถี่วิทยุในการส่งผ่านข้อมูลระหว่างตัวอ่านอาร์เอฟไอดีและแท็ก ระบบอาร์เอฟไอดีมีการประยุกต์ใช้งานอย่างแพร่หลาย อาทิ อุตสาหกรรมการผลิต, ระบบดูแลสุขภาพ, การขนส่งสินค้า และการเกษตร แม้ว่าจะมีการใช้งานเทคโนโลยีอาร์เอฟไอดีอย่างแพร่หลาย แต่ปัญหาการชนกันของแท็กก็ยังคงมีปรากฏอยู่ในระบบอาร์เอฟไอดี ซึ่งเป็นเรื่องน่ากังวลใจและจัดว่าเป็นปัญหาที่มีความท้าทาย ปัญหาการชนกันของแท็กเกิดขึ้นในกรณีที่แท็กหลายตัวพยายามส่งข้อมูลไปยังตัวอ่านเดียวกันในเวลาใกล้เคียงกันโดยไม่ได้มีการประสานกันล่วงหน้า มาตรฐานอุตสาหกรรมของเลขรหัสสินค้าอิเล็กทรอนิกส์ในปัจจุบันเลือกใช้อัลกอริทึมคิวในการแก้ปัญหาการชนกันของแท็ก เนื่องจากอัลกอริทึมคิวทำงานโดยใช้หลักการของโพรโทคอลอโลฮา ประสิทธิภาพสูงสุดของระบบที่ทำได้มีค่าเพียงประมาณ 34% ในงานวิจัยนี้ เรานำเสนอวิธีป้องกันการชนแบบใหม่ 2 วิธี คือ ต้นไม้พลวัตดัดแปลงด้วยการประมาณแบบเบส์ (บีอี-เอ็มดีที) และต้นไม้พลวัตดัดแปลงด้วยการตัดแบ่งแบบไบนารี (บีเอส-เอ็มดีที) ซึ่งมีสามารถทำงานได้ดีกว่าโพรโทคอลป้องกันการชนที่มีอยู่เดิมทั้งหมด โพรโทคอลป้องกันการชนทั้งสองวิธีแบ่งการทำงานออกเป็น 2 ช่วง คือ ช่วงการประมาณจำนวนแท็ก และช่วงการระบุแท็ก โดยในช่วงแรกของบีอี-เอ็มดีที เราเสนอวิธีการประมาณจำนวนแท็กอิงสล็อตอโลฮาแบบเบส์ ซึ่งสามารถสะสมและรวบรวมข้อมูลที่ได้ในแต่ละสล็อตสำหรับใช้ประมาณจำนวนของแท็ก และใช้ในการกำหนดขนาดของเฟรมเริ่มต้นที่ต้องใช้ในช่วงที่สอง ในช่วงที่ 2 ของบีเอส-เอ็มดีที เรานำเสนออัลกอริทึมต้นไม้พลวัตดัดแปลง (เอ็มดีที) ซึ่งใช้ค่าประมาณขนาดของเฟรมจากช่วงแรกเป็นค่าเริ่มต้นของช่วงที่สอง และตามด้วยการใช้อัลกอริทึมต้นไม้ไบนารีแบบข้ามสล็อตที่มีการชน สำหรับอัลกอริทึมบีเอส-เอ็มดีที การทำงานช่วงแรกใช้วิธีการประมาณจำนวนแท็กด้วยการตัดแบ่งแบบไบนารี และใช้อัลกอริทึมต้นไม้พลวัตดัดแปลงเอ็มดีที ในช่วงที่ 2 พร้อมกับเทคนิคในการประมาณขนาดของเฟรมเริ่มต้นเพื่อทำให้ประสิทธิภาพของระบบมีค่าสูงสุดสำหรับทุกค่าของจำนวนแท็ก เรายังได้นำเสนอแบบจำลองการคำนวณทางคณิตศาสตร์สำหรับแต่ละอัลกอริธึมสำหรับคำนวณค่าประสิทธิภาพของระบบและประสิทธิภาพของระบบในเชิงเวลา แบบจำลองการคำนวณทางคณิตศาสตร์นี้ได้รับการตรวจสอบความถูกต้องโดยใช้เทียบผลกับการจำลองด้วยคอมพิวเตอร์ ผลลัพธ์เชิงตัวเลขยืนยันว่าบีอี-เอ็มดีที มีประสิทธิภาพการของระบบ 45% และประสิทธิภาพของระบบในเชิงเวลา 78% ในขณะที่บีเอส-เอ็มดีที มีประสิทธิภาพของระบบ 46% และประสิทธิภาพของระบบในเชิงเวลา 80%
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Wijayasekara, Sanika Krishnamali, "A Tree-Based Collision Resolution Algorithm for RFID using Bayesian Tag Estimation" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 685.
https://digital.car.chula.ac.th/chulaetd/685