Query Tree Protocol(查詢式樹狀協定) for RFID Tag Anti-Collision
import tkinter as tk
from tkinter import ttk, scrolledtext
from collections import deque
class QTSimulatorApp:
def __init__(self, master):
# --- GUI Setup ---
self.master = master
master.title("RFID 查詢樹 (QT) 協定模擬器")
# 頂部控制面板
self.input_frame = ttk.Frame(master, padding="10")
self.input_frame.pack(fill='x')
ttk.Label(self.input_frame, text="請輸入 6 個 6 位元 Tag ID (000000 到 111111):").grid(row=0, column=0, columnspan=6, pady=5, sticky='w')
self.id_entries = []
# Tag ID 輸入框
for i in range(6):
entry = ttk.Entry(self.input_frame, width=8)
entry.grid(row=1, column=i, padx=5, pady=2)
self.id_entries.append(entry)
# 根據用戶提供的範例圖填充預設值 (Tag A 到 Tag F)
self.id_entries[0].insert(0, "000100") # Tag A
self.id_entries[1].insert(0, "001010") # Tag B
self.id_entries[2].insert(0, "100011") # Tag C
self.id_entries[3].insert(0, "101110") # Tag D
self.id_entries[4].insert(0, "110110") # Tag E
self.id_entries[5].insert(0, "111001") # Tag F
self.simulate_button = ttk.Button(self.input_frame, text="開始 QT 模擬", command=self.run_simulation)
self.simulate_button.grid(row=2, column=0, columnspan=6, pady=10)
# --- 顯示結果區 ---
self.result_frame = ttk.Frame(master, padding="10")
self.result_frame.pack(fill='both', expand=True)
# 樹狀顯示區 (Treeview)
tree_label = ttk.Label(self.result_frame, text="✅ 查詢樹過程 (Treeview)")
tree_label.pack(pady=5)
# 使用一個 Frame 包裹 Treeview 和 Scrollbar
tree_container = ttk.Frame(self.result_frame)
tree_container.pack(side="left", fill="both", expand=True, padx=5)
self.tree = ttk.Treeview(tree_container, columns=("Tags", "結果"), show="tree headings")
self.tree.heading("#0", text="插槽 (Slot) | 查詢字串 (Q)")
self.tree.heading("Tags", text="匹配標籤 ID 集合")
self.tree.heading("結果", text="結果")
self.tree.column("#0", width=180, anchor="w")
self.tree.column("Tags", width=200, anchor="w")
self.tree.column("結果", width=80, anchor="center")
# 加入 Scrollbar
yscrollbar = ttk.Scrollbar(tree_container, orient="vertical", command=self.tree.yview)
self.tree.configure(yscrollcommand=yscrollbar.set)
yscrollbar.pack(side="right", fill="y")
self.tree.pack(side="left", fill="both", expand=True)
# 過程日誌區 (ScrolledText)
log_label = ttk.Label(self.result_frame, text="📜 步驟日誌")
log_label.pack(pady=5)
self.log_text = scrolledtext.ScrolledText(self.result_frame, wrap=tk.WORD, width=50, height=20, state='disabled')
self.log_text.pack(side="right", fill="both", expand=True, padx=5)
# 設定 Treeview 顏色標籤
self.tree.tag_configure('success', background='lightgreen', foreground='darkgreen')
self.tree.tag_configure('collision', background='coral', foreground='black')
self.tree.tag_configure('idle', background='lightgray', foreground='darkgray')
def log(self, message, color=None):
"""將訊息寫入日誌區並控制顏色"""
self.log_text.config(state='normal')
if color:
self.log_text.tag_config(color, foreground=color)
self.log_text.insert(tk.END, message + "\n", color)
else:
self.log_text.insert(tk.END, message + "\n")
self.log_text.see(tk.END)
self.log_text.config(state='disabled')
def run_simulation(self):
"""主模擬函式，執行 QT 協定邏輯"""
self.tree.delete(*self.tree.get_children()) # 清除上次結果
self.log_text.config(state='normal')
self.log_text.delete('1.0', tk.END)
self.log_text.config(state='disabled')
# 1. 驗證並獲取 Tag ID 列表
try:
tag_ids = []
for entry in self.id_entries:
tag_id = entry.get()
if not (len(tag_id) == 6 and all(c in '01' for c in tag_id)):
self.log(f"**輸入錯誤**: 所有 Tag ID 必須是 6 位元的 '0' 或 '1' 組成。", 'red')
return
tag_ids.append(tag_id)
if len(set(tag_ids)) != 6:
self.log(f"**輸入錯誤**: 所有 Tag ID 必須是唯一的。", 'red')
return
self.log(f"--- RFID QT 協定模擬開始 ---", 'blue')
self.log(f"初始標籤集合 (N=6): {tag_ids}")
self.log(f"---")
except Exception as e:
self.log(f"**發生未知錯誤**: {e}", 'red')
return
# 2. 查詢樹 (QT) 協定邏輯
# Stack 儲存待處理的查詢字串 (S)。根據 QT 協定，閱讀器先推入 '1' 和 '0'。
# 由於範例圖是先處理 0 側，所以我們將 '0' 放在前面。
# Stack: 儲存 (查詢字串 S, 父節點 iid)
# 初始時，使用空字串作為根查詢，並將 '0' 和 '1' 作為第一個分裂
query_stack = deque([('0', ''), ('1', '')])
# 記錄 Treeview 節點 ID 以建立階層
tree_parents = {}
# 模擬範例圖中的 Slot 編號
slot_counter = 1
# 根節點 (Slot 1)
root_iid = self.tree.insert("", tk.END, text=f"Slot {slot_counter} | Q: (Null)", values=(", ".join(tag_ids), "碰撞"), tags=('collision',))
tree_parents[''] = root_iid
slot_counter += 1
while query_stack:
query, parent_query = query_stack.popleft() # 彈出下一個查詢字串 Q
# 找到匹配當前查詢字串 Q 的標籤子集 (Tags with prefix Q)
matching_tags = [tag_id for tag_id in tag_ids if tag_id.startswith(query)]
num_matches = len(matching_tags)
# 決定父節點 iid
parent_iid = tree_parents.get(parent_query, root_iid)
# 插入樹狀結構
tag_str = ", ".join(matching_tags)
if num_matches == 1:
# 成功識別 (Identification Success)
identified_tag = matching_tags[0]
result_text = "識別成功"
tag_style = 'success'
self.log(f"Slot {slot_counter}: 廣播 Q='{query}' -> 標籤 {identified_tag} 成功回應。", 'green')
elif num_matches > 1:
# 碰撞 (Collision)
# 閱讀器將 Q0 和 Q1 推入堆疊中，用於下一輪分割
next_queries = [(query + '0', query), (query + '1', query)]
query_stack.extendleft(next_queries) # 確保 '0' 側先處理
result_text = "碰撞"
tag_style = 'collision'
self.log(f"Slot {slot_counter}: 廣播 Q='{query}' -> 發生碰撞 ({num_matches} 個標籤)。將 '{query}0', '{query}1' 推入堆疊。", 'red')
elif num_matches == 0:
# 空閒時隙 (Idle Slot)
result_text = "空閒"
tag_style = 'idle'
self.log(f"Slot {slot_counter}: 廣播 Q='{query}' -> 無標籤回應 (空閒時隙)。", 'gray')
# 插入當前節點
current_iid = self.tree.insert(parent_iid, tk.END, text=f"Slot {slot_counter} | Q: {query}", values=(tag_str, result_text), tags=(tag_style,))
tree_parents[query] = current_iid
self.log(f" -> 待處理堆疊: {[(q, p) for q, p in query_stack]}")
self.log(f"---")
slot_counter += 1
self.log(f"--- 模擬完成！總共使用 {slot_counter-1} 個時隙（Slot） ---", 'blue')
# 執行主程式
if __name__ == "__main__":
root = tk.Tk()
app = QTSimulatorApp(root)
root.mainloop()
import tkinter as tk
from tkinter import ttk, scrolledtext
from collections import deque
class QTSimulatorApp:
def __init__(self, master):
# --- GUI Setup ---
self.master = master
master.title("RFID Query Tree (QT) 協定模擬器")
# 設定 Tag ID 輸入區
self.input_frame = ttk.Frame(master, padding="10")
self.input_frame.pack(fill='x')
ttk.Label(self.input_frame, text="請輸入 6 個 6 位元 Tag ID (e.g., 001010):").grid(row=0, column=0, columnspan=2, pady=5, sticky='w')
self.id_entries = []
for i in range(6):
entry = ttk.Entry(self.input_frame, width=8)
entry.insert(0, f"") # 預設留空
entry.grid(row=1 + i // 3, column=i % 3 + (i // 3) * 2, padx=5, pady=2)
self.id_entries.append(entry)
# 範例 Tag ID (可手動修改)
self.id_entries[0].insert(0, "001010")
self.id_entries[1].insert(0, "001100")
self.id_entries[2].insert(0, "100001")
self.id_entries[3].insert(0, "100110")
self.id_entries[4].insert(0, "000000")
self.id_entries[5].insert(0, "111111")
self.simulate_button = ttk.Button(self.input_frame, text="開始模擬", command=self.run_simulation)
self.simulate_button.grid(row=3, column=0, columnspan=6, pady=10)
# --- 顯示結果區 ---
self.result_frame = ttk.Frame(master, padding="10")
self.result_frame.pack(fill='both', expand=True)
# 樹狀顯示區 (Treeview)
ttk.Label(self.result_frame, text="✅ 查詢樹過程 (ttk.Treeview)").pack(pady=5)
self.tree = ttk.Treeview(self.result_frame, columns=("Tags"), show="tree headings")
self.tree.heading("#0", text="查詢字串 (Query)")
self.tree.heading("Tags", text="匹配標籤 ID")
self.tree.column("#0", width=150, anchor="w")
self.tree.column("Tags", width=250, anchor="w")
self.tree.pack(side="left", fill="both", expand=True, padx=5)
# 過程日誌區 (ScrolledText)
ttk.Label(self.result_frame, text="📜 步驟日誌").pack(pady=5)
self.log_text = scrolledtext.ScrolledText(self.result_frame, wrap=tk.WORD, width=50, height=20)
self.log_text.pack(side="right", fill="both", expand=True, padx=5)
def log(self, message):
"""將訊息寫入日誌區"""
self.log_text.insert(tk.END, message + "\n")
self.log_text.see(tk.END)
def run_simulation(self):
"""主模擬函式"""
self.tree.delete(*self.tree.get_children()) # 清除上次結果
self.log_text.delete('1.0', tk.END)
# 1. 驗證並獲取 Tag ID 列表
try:
tag_ids = []
for entry in self.id_entries:
tag_id = entry.get()
if not (len(tag_id) == 6 and all(c in '01' for c in tag_id)):
raise ValueError("所有 Tag ID 必須是 6 位元的 '0' 或 '1' 組成。")
tag_ids.append(tag_id)
if len(set(tag_ids)) != 6:
raise ValueError("所有 Tag ID 必須是唯一的。")
self.log(f"--- 模擬開始 ---")
self.log(f"初始標籤集合 (N=6): {tag_ids}")
self.log(f"---")
except ValueError as e:
self.log(f"**輸入錯誤**: {e}")
return
# 2. 查詢樹 (QT) 協定邏輯
# Stack 儲存待處理的查詢字串 (S)
# 初始時推入 '0' 和 '1'，代表第一位為 0 或 1 的標籤子集
query_stack = deque(['1', '0']) # 通常是 '0' 先處理，這裡用 stack 配合 deque popleft
# Treeview 的父節點 ID 字典，用於建立階層
tree_parents = {'': self.tree.insert("", tk.END, text="ROOT: 初始集合", values=(", ".join(tag_ids),))}
identified_tags = set()
total_steps = 0
while query_stack:
total_steps += 1
query = query_stack.popleft() # 彈出下一個查詢字串 S
# 找到匹配當前查詢字串 S 的標籤子集 (Tags with prefix S)
matching_tags = [tag_id for tag_id in tag_ids if tag_id.startswith(query)]
num_matches = len(matching_tags)
# 決定父節點
parent_query = query[:-1]
parent_iid = tree_parents.get(parent_query, tree_parents[''])
# 插入樹狀結構
current_iid = self.tree.insert(parent_iid, tk.END, text=f"Query: {query}", values=(", ".join(matching_tags),))
tree_parents[query] = current_iid
self.log(f"步驟 {total_steps}: 閱讀器廣播查詢字串 S = '{query}'")
self.log(f" -> 匹配標籤數: {num_matches}")
if num_matches == 1:
# 成功識別 (Identification Success)
identified_tag = matching_tags[0]
identified_tags.add(identified_tag)
self.tree.item(current_iid, tags=('success',))
self.tree.tag_configure('success', background='lightgreen')
self.log(f" -> **成功識別** Tag ID: {identified_tag}")
elif num_matches > 1:
# 碰撞 (Collision)
# 閱讀器推入 S0 和 S1 到堆疊中，用於下一輪分割
next_queries = [query + '0', query + '1']
query_stack.extend(next_queries)
self.tree.item(current_iid, tags=('collision',))
self.tree.tag_configure('collision', background='coral')
self.log(f" -> **發生碰撞**。將 '{query}0' 和 '{query}1' 推入堆疊。")
elif num_matches == 0:
# 空閒時隙 (Idle Slot)
self.tree.item(current_iid, tags=('idle',))
self.tree.tag_configure('idle', background='lightgray')
self.log(f" -> **無標籤回應** (空閒時隙)。")
self.log(f" -> 當前堆疊 (待處理查詢): {list(query_stack)}")
self.log(f"---")
# 3. 模擬結束
if len(identified_tags) == len(tag_ids):
self.log(f"✅ 模擬完成！所有 {len(tag_ids)} 個標籤皆已成功識別。")
else:
self.log(f"❌ 模擬結束，但有 {len(tag_ids) - len(identified_tags)} 個標籤未被識別。請檢查輸入。")
# 執行主程式
if __name__ == "__main__":
root = tk.Tk()
app = QTSimulatorApp(root)
root.mainloop()
沒有留言:
張貼留言