在 RFID 防碰撞技術中，查詢樹演算法 (Query Tree, QT) 是最經典且被廣泛應用的「記憶體無關型 (Memoryless)」演算法。與前面的 Tree-Based 演算法相比，它的特點是標籤不需要存儲任何中間狀態，只需響應閱讀器的指令。
QT 演算法運作原理解析
無狀態性 (Memoryless)： 在之前的樹狀演算法中，標籤可能需要記住自己在哪一個節點。但在 Query Tree (QT) 中，標籤非常「笨」，它們只負責聽。如果閱讀器喊「開頭是 01 的請回答」，標籤發現自己符合就回傳剩下的位元。這降低了標籤的硬體成本。
查詢效率：
碰撞 (Collision)：當多個標籤響應。閱讀器會將前綴加長（例如從
0變成00和01）再次嘗試。空閒 (Idle)：如果某個前綴下沒有標籤（例如沒有
1開頭的標籤），這一步就是浪費的。成功 (Success)：只有一個標籤回傳，識別完成。
3-bit 的規模： 在 3-bit 的空間中，樹的最大深度為 3。總查詢次數會取決於標籤 ID 的分布情況。如果標籤 ID 非常接近（例如
000和001），則會引發較多次的碰撞。
import tkinter as tk
from tkinter import messagebox
import random
class QTAlgorithmSim:
def __init__(self, root):
self.root = root
self.root.title("RFID Query Tree (QT) 模擬器")
self.root.geometry("600x650")
# 核心數據
self.tags = []
self.queue = [] # QT 使用 Queue (廣度優先) 或 Stack (深度優先)
self.identified = []
self.query_count = 0 # 統計查詢次數
self.setup_ui()
self.reset_sim()
def setup_ui(self):
# 標題
tk.Label(self.root, text="Query Tree (QT) Algorithm", font=("Arial", 16, "bold")).pack(pady=10)
# 標籤資訊區
self.info_frame = tk.Frame(self.root, relief=tk.SUNKEN, bd=1)
self.info_frame.pack(pady=5, padx=20, fill=tk.X)
self.tag_info = tk.Label(self.info_frame, text="", font=("Consolas", 11), fg="green")
self.tag_info.pack(pady=5)
# 統計數據顯示
self.stat_label = tk.Label(self.root, text="查詢次數: 0 | 已識別: 0", font=("Arial", 10))
self.stat_label.pack()
# 日誌顯示
self.log_box = tk.Listbox(self.root, width=70, height=18, font=("Consolas", 10))
self.log_box.pack(pady=10)
# 按鈕區
btn_frame = tk.Frame(self.root)
btn_frame.pack(pady=10)
self.btn_next = tk.Button(btn_frame, text="下一步 (Query)", width=15, bg="#e1f5fe", command=self.step_qt)
self.btn_next.pack(side=tk.LEFT, padx=10)
tk.Button(btn_frame, text="重新開始", width=15, command=self.reset_sim).pack(side=tk.LEFT, padx=10)
def reset_sim(self):
# 隨機產生 3-bit ID
all_possible = [format(i, '03b') for i in range(8)]
self.tags = sorted(random.sample(all_possible, random.randint(3, 4)))
self.queue = [""] # 從空前綴開始
self.identified = []
self.query_count = 0
self.tag_info.config(text=f"目標標籤集: {self.tags}")
self.update_stats()
self.log_box.delete(0, tk.END)
self.log_box.insert(tk.END, "--- 系統已就緒，等待第一次查詢 ---")
self.btn_next.config(state=tk.NORMAL)
def update_stats(self):
self.stat_label.config(text=f"查詢次數: {self.query_count} | 已識別: {len(self.identified)}/{len(self.tags)}")
def step_qt(self):
if not self.queue:
messagebox.showinfo("完成", "所有標籤已識別完成！")
self.btn_next.config(state=tk.DISABLED)
return
# 1. 閱讀器發送查詢前綴 (Query)
prefix = self.queue.pop(0) # 取出最前面的前綴 (廣度優先搜尋)
self.query_count += 1
self.update_stats()
# 2. 標籤檢查是否匹配
matching_tags = [t for t in self.tags if t.startswith(prefix)]
self.log_box.insert(tk.END, f"Round {self.query_count}: 閱讀器廣播前綴 [{prefix if prefix!='' else 'NULL'}]")
# 3. 判斷碰撞、成功或無響應
if len(matching_tags) > 1:
self.log_box.insert(tk.END, f" -> [碰撞] 發現 {len(matching_tags)} 個標籤，分裂前綴...")
self.log_box.itemconfig(tk.END, fg="red")
# 發生碰撞，將新的前綴 0 和 1 加入隊列
self.queue.append(prefix + "0")
self.queue.append(prefix + "1")
elif len(matching_tags) == 1:
tag = matching_tags[0]
# 在 QT 中，如果前綴長度等於標籤長度，或是剛好剩一個響應，即識別成功
self.log_box.insert(tk.END, f" -> [成功] 識別標籤 ID: {tag}")
self.log_box.itemconfig(tk.END, fg="blue")
if tag not in self.identified:
self.identified.append(tag)
else:
self.log_box.insert(tk.END, " -> [空閒] 無任何標籤響應")
self.log_box.itemconfig(tk.END, fg="gray")
self.log_box.see(tk.END)
if __name__ == "__main__":
root = tk.Tk()
app = QTAlgorithmSim(root)
root.mainloop()
沒有留言:
張貼留言