RFID Slotted ALOHA

 在 RFID 防碰撞技術中，Slotted ALOHA 是一種基於「機率」的防碰撞演算法，與之前的「查詢樹 (QT)」這種確定性方法完全不同。

Slotted ALOHA 的核心邏輯：

1. 時間槽 (Slots)：閱讀器將時間劃分為多個等長的「時槽」。

2. 隨機選擇：每個標籤在每一輪開始時，會從 $0$ 到 $L-1$（$L$ 是框長度）之間隨機選一個數字，作為自己發送訊息的時槽。

3. 三種狀態：

   • 空閒 (Idle)：該時槽沒有標籤發送訊號。

   • 成功 (Success)：該時槽只有一個標籤發送訊號，成功讀取。

   • 碰撞 (Collision)：兩個以上標籤在同一時槽發送，訊號互相干擾，讀取失敗。

4. 重試：發生碰撞的標籤會在下一輪重新選擇隨機時槽，直到被識別為止。

Slotted ALOHA 的關鍵觀察：

1. 效率 (Efficiency)：

   • 最佳效率發生在 標籤數量 ≈ 時槽數量 時。

   • 如果時槽太少，會一直發生碰撞（Collision）。

   • 如果時槽太多，會浪費很多時間在空閒時槽（Idle）。

2. 與 Tree Algorithm 的不同：

   • Tree Algorithm: 像是在玩「猜數字」，透過刪去法一步步縮小範圍。

   • Slotted ALOHA: 像是在玩「投籃」，大家同時投，如果一球進框就得分，兩球同時撞在一起就都不算。

3. 動態調整 (Dynamic Framed Slotted ALOHA, DFSA)：

   • 在進階應用中，閱讀器會根據碰撞的頻率來動態調整下一輪的框長（Frame Size）。如果碰撞太多，就把時槽數翻倍；如果空閒太多，就減少時槽。

import tkinter as tk

from tkinter import messagebox

import random

class SlottedAlohaSim:

    def __init__(self, root):

        self.root = root

        self.root.title("RFID Slotted ALOHA 防碰撞模擬")

        self.root.geometry("600x700")

        

        # 參數設定

        self.frame_size = 4  # 設定每輪有 4 個時槽

        self.tags = []       # 待識別標籤

        self.identified = [] # 已識別標籤

        self.round_count = 0 # 輪數統計

        

        self.setup_ui()

        self.reset_sim()

    def setup_ui(self):

        tk.Label(self.root, text="Slotted ALOHA 模擬器", 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.canvas = tk.Canvas(self.root, width=500, height=100, bg="white")

        self.canvas.pack(pady=10)

        # 日誌顯示

        self.log_box = tk.Listbox(self.root, width=70, 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="執行下一輪掃描", width=15, bg="#fff9c4", command=self.run_round)

        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):

        # 隨機產生 4 到 6 個 3-bit 標籤

        all_possible = [format(i, '03b') for i in range(8)]

        self.tags = random.sample(all_possible, random.randint(4, 6))

        

        self.identified = []

        self.round_count = 0

        self.update_display()

        self.log_box.delete(0, tk.END)

        self.log_box.insert(tk.END, "--- 系統重置：等待掃描 ---")

        self.log_box.insert(tk.END, f"設定框長 (Frame Size) = {self.frame_size}")

        self.btn_next.config(state=tk.NORMAL)

    def update_display(self):

        self.tag_info.config(text=f"剩餘待辨識標籤: {self.tags}")

        self.stat_label.config(text=f"目前執行輪數: {self.round_count} | 已識別: {len(self.identified)}")

        self.draw_slots([])

    def draw_slots(self, slot_results):

        self.canvas.delete("all")

        w = 500 / self.frame_size

        for i in range(self.frame_size):

            color = "white"

            text = f"Slot {i}"

            if i < len(slot_results):

                count = len(slot_results[i])

                if count == 0: color = "#eeeeee"; text = "Idle"

                elif count == 1: color = "#c8e6c9"; text = f"Success\n({slot_results[i][0]})"

                else: color = "#ffccbc"; text = f"Collision\n({count} tags)"

            

            self.canvas.create_rectangle(i*w, 0, (i+1)*w, 100, fill=color, outline="black")

            self.canvas.create_text(i*w + w/2, 50, text=text, justify=tk.CENTER)

    def run_round(self):

        if not self.tags:

            messagebox.showinfo("完成", "所有標籤已成功讀取！")

            self.btn_next.config(state=tk.DISABLED)

            return

        self.round_count += 1

        # 每個標籤隨機選擇一個時槽

        slots = [[] for _ in range(self.frame_size)]

        for tag in self.tags:

            chosen_slot = random.randint(0, self.frame_size - 1)

            slots[chosen_slot].append(tag)

        self.log_box.insert(tk.END, f"=== 第 {self.round_count} 輪掃描 ===")

        

        new_identified = []

        remaining_tags = []

        for i, occupants in enumerate(slots):

            if len(occupants) == 1:

                tag = occupants[0]

                self.log_box.insert(tk.END, f"  時槽 {i}: [成功] 讀取到 {tag}")

                new_identified.append(tag)

            elif len(occupants) > 1:

                self.log_box.insert(tk.END, f"  時槽 {i}: [碰撞] {len(occupants)} 個標籤競爭")

                remaining_tags.extend(occupants)

            else:

                self.log_box.insert(tk.END, f"  時槽 {i}: [空閒]")

        # 從待識別清單中移除成功的標籤

        self.identified.extend(new_identified)

        self.tags = [t for t in self.tags if t not in new_identified]

        

        self.draw_slots(slots)

        self.update_display()

        self.log_box.see(tk.END)

if __name__ == "__main__":

    root = tk.Tk()

    app = SlottedAlohaSim(root)

    root.mainloop()