RFID 樹狀演算法（Tree-search Algorithms）
在 RFID 防碰撞研究中，Capetanakis 的 Splitting Method 是樹狀演算法（Tree-search Algorithms）的鼻祖，通常被稱為 BSTA (Binary Tree Search Algorithm)。
雖然它們都使用「樹」的概念，但在標籤的行為與分裂邏輯上有些微差異。
1. 核心概念對比
Capetanakis Splitting (隨機分裂/計數法)
這是一種動態分裂法。當碰撞發生時，標籤「擲硬幣」決定去向。
邏輯：參與碰撞的標籤隨機產生一個 0 或1。
計數器：選到 0 的標籤立刻發送；選到 1 的標籤將計數器加 1，進入等待狀態。
特點：不需要知道標籤的完整 ID，適合匿名性要求高的環境。
Tree-search Algorithms (前綴搜尋/QT)
這是一種確定性分裂法，通常指 Query Tree (QT)。
邏輯：閱讀器發送一個位元前綴（如
01），標籤根據自己的 ID 匹配。分裂：碰撞後，閱讀器直接分裂前綴（變為
010和011）。特點：標籤硬體極其簡單（無須計數器或隨機發生器）。
重點機制解析
| 特性 | Capetanakis (Splitting) | Tree-Search (QT) |
| 分裂依據 | 標籤內部的隨機亂數 | 標籤內部的固定 ID 位元 |
| 狀態存儲 | 標籤需維護一個 Counter | 標籤完全無狀態 (Memoryless) |
| 反饋要求 | 標籤需聽取閱讀器的 碰撞/成功 指令 | 標籤只聽前綴匹配 |
| 優點 | 不洩漏 ID 隱私，對 ID 分布不敏感 | 標籤硬體成本最低 |
Splitting Method (Capetanakis) 的精髓在於它的「遞迴性」。當碰撞發生，它不是去查 ID，而是讓標籤自己「站隊」。選 0 的先走，選 1 的後走。
import tkinter as tk
from tkinter import messagebox
import random
class CapetanakisSim:
def __init__(self, root):
self.root = root
self.root.title("Capetanakis Splitting vs Tree-search")
self.root.geometry("650x700")
# 模擬參數
self.tags = [] # 標籤列表，每個包含 {id: '010', counter: 0}
self.identified = []
self.step_count = 0
self.collision_stack = [] # 用於追蹤分裂層級
self.setup_ui()
self.reset_sim()
def setup_ui(self):
tk.Label(self.root, text="Capetanakis Splitting Method", font=("Arial", 14, "bold")).pack(pady=10)
self.info_label = tk.Label(self.root, text="", font=("Consolas", 10), fg="blue")
self.info_label.pack()
# 畫布顯示標籤計數器狀態
self.canvas = tk.Canvas(self.root, width=500, height=120, bg="#e8f5e9")
self.canvas.pack(pady=10)
self.log_box = tk.Listbox(self.root, width=80, 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="下一步 (Slot Scan)", width=20, bg="#bbdefb", command=self.next_step)
self.btn_next.pack(side=tk.LEFT, padx=10)
tk.Button(btn_frame, text="重置 (Random Tags)", width=20, command=self.reset_sim).pack(side=tk.LEFT, padx=10)
def reset_sim(self):
# 隨機產生 4 個標籤
ids = [format(i, '03b') for i in range(8)]
self.tags = [{"id": tid, "counter": 0} for tid in random.sample(ids, 4)]
self.identified = []
self.step_count = 0
self.update_ui()
self.log_box.delete(0, tk.END)
self.log_box.insert(tk.END, "--- 系統重置：所有標籤 Counter = 0 ---")
def update_ui(self):
tag_str = ", ".join([f"[{t['id']} C:{t['counter']}]" for t in self.tags])
self.info_label.config(text=f"標籤狀態: {tag_str}\n已識別: {self.identified}")
self.draw_tags()
def draw_tags(self):
self.canvas.delete("all")
for i, t in enumerate(self.tags):
x = 50 + i*100
color = "orange" if t['counter'] == 0 else "gray"
self.canvas.create_oval(x, 20, x+40, 60, fill=color)
self.canvas.create_text(x+20, 80, text=f"ID:{t['id']}")
self.canvas.create_text(x+20, 100, text=f"Cnt:{t['counter']}", font=("Arial", 10, "bold"))
def next_step(self):
if not self.tags:
messagebox.showinfo("完成", "所有標籤已識別！")
return
self.step_count += 1
# 只有 Counter 為 0 的標籤會發送訊號
active_tags = [t for t in self.tags if t['counter'] == 0]
self.log_box.insert(tk.END, f"Step {self.step_count}: 檢查 Counter=0 的標籤...")
if len(active_tags) > 1:
# 發生碰撞
self.log_box.insert(tk.END, f" [!] 碰撞！{len(active_tags)} 個標籤競爭。")
self.log_box.itemconfig(tk.END, fg="red")
# Capetanakis 分裂邏輯：
# 1. 參與碰撞的隨機選 0 或 1
# 2. 沒參與碰撞的 (Counter > 0) 全部 +1 (讓位)
for t in self.tags:
if t['counter'] == 0:
t['counter'] = random.randint(0, 1)
if t['counter'] == 1:
self.log_box.insert(tk.END, f" - 標籤 {t['id']} 隨機選 1, 進入等待")
else:
self.log_box.insert(tk.END, f" - 標籤 {t['id']} 隨機選 0, 準備重試")
else:
t['counter'] += 1 # 原本就在等待的標籤，因為新分裂而推遲
elif len(active_tags) == 1:
# 成功識別
target = active_tags[0]
self.log_box.insert(tk.END, f" [V] 成功！識別標籤 {target['id']}")
self.log_box.itemconfig(tk.END, fg="green")
self.identified.append(target['id'])
self.tags.remove(target)
# 成功後，所有等待中的標籤 Counter -1 (向上移動一層)
for t in self.tags:
t['counter'] -= 1
self.log_box.insert(tk.END, " - 所有等待標籤 Counter 減 1")
else:
# 空閒 (Idle)
self.log_box.insert(tk.END, " [-] 無標籤發送 (Idle)。")
for t in self.tags:
t['counter'] -= 1
self.log_box.insert(tk.END, " - 所有等待標籤 Counter 減 1")
self.update_ui()
self.log_box.see(tk.END)
if __name__ == "__main__":
root = tk.Tk()
app = CapetanakisSim(root)
root.mainloop()
沒有留言:
張貼留言