在 RFID 系統中，當多個標籤（Tags）同時響應閱讀器（Reader）時，訊號會發生碰撞導致讀取失敗。Hush 和 Wood 提出的 Tree-Based Algorithm（樹狀識別演算法） 是一種經典的確定性防碰撞機制。
其核心思想是將標籤的 ID 視為一棵二元樹的葉子節點，透過不斷分裂查詢前綴（Prefix），直到縮小範圍到只有一個標籤響應為止。
RFID Tree 演算法運作邏輯
查詢 (Query)： 閱讀器發送一個特定的前綴（例如
01）。響應 (Response)： 所有 ID 以
01開頭的標籤都會回傳它們的下一個位元。衝突檢測 (Collision Detection)：
如果只有
0或只有1響應：代表目前路徑正確，繼續往下探索。如果
0和1同時響應：發生碰撞，閱讀器會選擇一條路徑（例如先走0），並將另一條路徑存入堆疊（Stack）稍後再試。
識別 (Identification)： 當路徑完整匹配某個標籤的 ID 長度且無衝突時，該標籤被成功識別。
此演算法的優缺點
| 優點 | 缺點 |
| 確定性：保證在有限時間內識別所有標籤。 | 傳輸延遲：如果標籤 ID 很長，樹的深度會增加識別時間。 |
| 無須同步：標籤不需要精確的時鐘同步。 | 隱私問題：由於前綴是公開廣播的，部分 ID 資訊可能外洩。 |
| 通訊量穩定：適合標籤數量密集的環境。 | 重複查詢：前綴重複發送會消耗額外電力。 |
import tkinter as tk
from tkinter import messagebox
import random
class RFIDTreeSim:
def __init__(self, root):
self.root = root
self.root.title("RFID Tree-Based 防碰撞模擬 (3-bit)")
self.root.geometry("500x600")
self.tags = []
self.stack = []
self.identified_tags = []
self.current_prefix = None
self.setup_ui()
self.reset_simulation()
def setup_ui(self):
# 標題與標籤資訊
self.info_frame = tk.Frame(self.root)
self.info_frame.pack(pady=10)
self.tag_label = tk.Label(self.info_frame, text="", font=("Courier", 12, "bold"), fg="darkgreen")
self.tag_label.pack()
# 狀態顯示
self.status_var = tk.StringVar(value="請點擊 [下一步] 開始")
self.status_label = tk.Label(self.root, textvariable=self.status_var, font=("Arial", 11, "italic"), fg="blue")
self.status_label.pack(pady=5)
# 歷史日誌
self.listbox = tk.Listbox(self.root, width=50, height=15, font=("Consolas", 10))
self.listbox.pack(pady=10, padx=20)
# 控制按鈕
self.btn_frame = tk.Frame(self.root)
self.btn_frame.pack(pady=10)
self.btn_next = tk.Button(self.btn_frame, text="下一步 (Next Step)", width=15, command=self.process_next_step)
self.btn_next.pack(side=tk.LEFT, padx=5)
self.btn_reset = tk.Button(self.btn_frame, text="重新開始 (Reset)", width=15, command=self.reset_simulation)
self.btn_reset.pack(side=tk.LEFT, padx=5)
def reset_simulation(self):
# 隨機產生 3 到 5 個隨機 3-bit ID (000~111)
available_ids = [format(i, '03b') for i in range(8)]
self.tags = sorted(random.sample(available_ids, random.randint(3, 5)))
self.stack = [""] # 初始前綴
self.identified_tags = []
self.current_prefix = None
# 重置 UI
self.tag_label.config(text=f"待識別標籤: {', '.join(self.tags)}")
self.listbox.delete(0, tk.END)
self.status_var.set("系統重置成功，請按下一步")
self.btn_next.config(state=tk.NORMAL)
self.log("--- 模擬重置：等待查詢 ---")
def log(self, message):
self.listbox.insert(tk.END, message)
self.listbox.see(tk.END)
def process_next_step(self):
if not self.stack:
self.status_var.set("所有標籤已完成識別！")
self.btn_next.config(state=tk.DISABLED)
messagebox.showinfo("完成", f"識別結果: {sorted(self.identified_tags)}")
return
# 彈出當前要檢查的前綴
prefix = self.stack.pop()
self.status_var.set(f"目前查詢前綴: '{prefix}'")
# 找出符合前綴的標籤
matches = [t for t in self.tags if t.startswith(prefix)]
self.log(f"> Query: [{prefix if prefix != '' else 'Empty'}]")
if len(matches) > 1:
# 發生碰撞，將 1 和 0 分別放入堆疊 (先放 1 再放 0，這樣會先處理 0)
self.log(f" [碰撞] 多個標籤符合: {matches}")
self.log(f" -> 分裂路徑為 {prefix}0 與 {prefix}1")
self.stack.append(prefix + "1")
self.stack.append(prefix + "0")
elif len(matches) == 1:
# 只有一個標籤，如果是完整長度或唯一路徑則識別成功
target = matches[0]
self.log(f" [成功] 識別標籤: {target}")
if target not in self.identified_tags:
self.identified_tags.append(target)
else:
self.log(" [安靜] 沒有標籤符合此範圍")
if __name__ == "__main__":
root = tk.Tk()
app = RFIDTreeSim(root)
root.mainloop()
沒有留言:
張貼留言