Dynamic Binary Search Tree Algorithm (動態二元搜尋樹演算法)
Dynamic Binary Search Tree Algorithm (動態二元搜尋樹演算法) 是對傳統二元搜尋樹的一種優化。在 RFID 防碰撞中，它通常結合了 「回退機制」 或 「動態調整查詢深度」，以減少無謂的查詢（Idle Slots）。
與固定深度的搜尋不同，動態搜尋會根據碰撞發生的位元位置，直接跳過不必要的節點。
演算法邏輯解析
動態分裂 (Splitting)：
當發生碰撞時，演算法不會停止，而是根據碰撞發生的位元（最高有效位），將目前的標籤群組動態地切割。
與固定搜尋的差異：
在某些動態版本中，如果閱讀器檢測到連續多位元沒有碰撞，它會動態增加查詢位元的長度（跳過中間節點），從而減少通訊來回的次數。
回退 (Backtracking)：
當左子樹（例如以 0 開頭的分支）處理完畢後，演算法會根據堆疊（Stack）自動回退到右子樹（以 1 開頭的分支）。
總結比較
| 演算法 | 防止碰撞原理 | 適用場景 |
| Static Tree | 固定位元逐一查詢 | 標籤數量少且固定 |
| Dynamic Tree | 根據碰撞位置跳躍或調整深度 | 標籤數量變動大、ID 分布不均 |
| CDMA/DSSS | 碼分多址，同時發送 | 高度併發、對即時性要求高 |
| Slotted ALOHA | 隨機時槽，機率碰撞 | 標籤硬體成本極低 |
import tkinter as tk
from tkinter import messagebox
import random
class DynamicBinaryTreeSim:
def __init__(self, root):
self.root = root
self.root.title("Dynamic Binary Search Tree RFID 防碰撞模擬")
self.root.geometry("700x700")
self.tags = []
self.identified = []
self.stack = [] # 存儲查詢前綴
self.query_count = 0
self.setup_ui()
self.reset_sim()
def setup_ui(self):
tk.Label(self.root, text="Dynamic Binary Search Tree Algorithm", font=("Arial", 16, "bold")).pack(pady=10)
# 標籤顯示區
self.tag_info = tk.Label(self.root, text="", font=("Consolas", 12), 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.canvas = tk.Canvas(self.root, width=600, height=250, bg="white", highlightthickness=1)
self.canvas.pack(pady=10)
# 日誌
self.log_box = tk.Listbox(self.root, width=80, height=15, 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="#fff9c4", command=self.process_step)
self.btn_next.pack(side=tk.LEFT, padx=10)
tk.Button(btn_frame, text="重新開始 (Reset)", width=15, command=self.reset_sim).pack(side=tk.LEFT, padx=10)
def reset_sim(self):
# 隨機產生 4 個不重複的 4-bit ID (增加深度感)
all_ids = [format(i, '04b') for i in range(16)]
self.tags = sorted(random.sample(all_ids, 4))
self.stack = [""] # 從根節點開始
self.identified = []
self.query_count = 0
self.update_stats()
self.log_box.delete(0, tk.END)
self.canvas.delete("all")
self.log_box.insert(tk.END, "--- 系統重置：等待掃描 ---")
self.tag_info.config(text=f"目標標籤: {', '.join(self.tags)}")
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 draw_node(self, prefix, x, y, level, is_collision=False):
color = "red" if is_collision else "lightblue"
r = 20
self.canvas.create_oval(x-r, y-r, x+r, y+r, fill=color)
self.canvas.create_text(x, y, text=prefix if prefix != "" else "Root", font=("Arial", 8))
def process_step(self):
if not self.stack:
messagebox.showinfo("完成", f"識別結果: {self.identified}")
self.btn_next.config(state=tk.DISABLED)
return
prefix = self.stack.pop()
self.query_count += 1
self.update_stats()
# 模擬標籤響應
matches = [t for t in self.tags if t.startswith(prefix)]
self.log_box.insert(tk.END, f"Round {self.query_count}: 查詢前綴 [{prefix}]")
# 繪圖座標 (簡單示意)
level = len(prefix)
x = 300 + (len(self.stack) * 30) # 隨意位移避免重疊
y = 40 + (level * 50)
if len(matches) > 1:
# 碰撞：動態分裂
self.log_box.insert(tk.END, f" [!] 碰撞: 符合數 {len(matches)}。分裂為 {prefix}0 與 {prefix}1")
self.log_box.itemconfig(tk.END, fg="red")
self.draw_node(prefix, x, y, level, True)
# 動態樹優化：先放 1 再放 0 (深度優先)
self.stack.append(prefix + "1")
self.stack.append(prefix + "0")
elif len(matches) == 1:
# 成功識別
tag = matches[0]
self.log_box.insert(tk.END, f" [V] 成功: 識別出標籤 {tag}")
self.log_box.itemconfig(tk.END, fg="blue")
self.draw_node(prefix, x, y, level, False)
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 = DynamicBinaryTreeSim(root)
root.mainloop()
沒有留言:
張貼留言