Slotted ALOHA(時槽化 ALOHA)

Slotted ALOHA(時槽化 ALOHA)

它得名於它是在 1970 年代為夏威夷的資料傳輸無線電網路 **ALOHANET** 而開發的事實。

源自於 https://www.geeksforgeeks.org/computer-networks/what-is-slotted-aloha/ 

https://github.com/sjkywalker/slotted-aloha-simulator/blob/master/aloha.py 

時槽化 ALOHA 背後的核心思想是將通訊頻道劃分成固定長度的時間時槽 (time slots)，並且只允許每個工作站在時槽的起始時刻開始傳輸。

協定	允許傳輸時間	碰撞間隔 (Collision Interval)	最大吞吐量 (Throughput, Smax​)
純 ALOHA (Pure ALOHA)	隨時	2 (兩倍封包傳輸時間)	18.4% (1/(2e))
時槽化 ALOHA (Slotted ALOHA)	僅在時槽開始	1 (一倍封包傳輸時間)	36.8%

時槽化 ALOHA 的應用雖然它很少在現代的大型網路中被使用，但 Slotted ALOHA 仍然應用於： 衛星通訊系統  無線感測網路 (WSN)   RFID 標籤通訊系統   作為 乙太網 (Ethernet)  和 Wi-Fi 中的 載波偵聽多重存取 (CSMA) 協定 的基礎

好的，這是對 Slotted ALOHA 應用場景的翻譯與說明：

---

翻譯與說明 💡

英文原文 (English Text)	中文翻譯 (Chinese Translation)
Applications of Slotted ALOHA	時槽化 ALOHA 的應用
While rarely used in modern large-scale networks, Slotted ALOHA is still applied in:	雖然它很少在現代的大型網路中被使用，但 Slotted ALOHA 仍然應用於：
Satellite communication systems	衛星通訊系統
Wireless sensor networks	無線感測網路 (WSN)
RFID tag communication systems	RFID 標籤通訊系統
As a foundation for CSMA (Carrier Sense Multiple Access) protocols in Ethernet and Wi-Fi.	作為 乙太網 (Ethernet) 和 Wi-Fi 中的 載波偵聽多重存取 (CSMA) 協定 的基礎。

---

應用場景解析 📡

Slotted ALOHA 的主要優勢在於其簡單的實作和分散式的控制機制。雖然其最大理論效率 (36.8%) 低於許多現代協定，但在以下幾個特定場景中，它的簡單性使其仍然具有實用價值：

1. 衛星通訊系統 (Satellite Communication Systems)

   衛星系統通常具有長傳播延遲。在這種高延遲環境中，像 CSMA 這樣需要即時「偵聽」頻道（載波偵聽）的協定會效率低下。ALOHA 協定不需要偵聽，因此適合用於衛星發射站與衛星之間的隨機存取。

2. 無線感測網路 (Wireless Sensor Networks, WSN)

   WSN 中的感測器通常是低功耗、低成本且運算能力有限的裝置。Slotted ALOHA 的簡單機制對硬體要求低，能節省功測器在複雜協定計算上耗費的電力。

3. RFID 標籤通訊系統 (RFID Tag Communication Systems)

   這是一個最常見的應用，與您提供的 PDF 內容高度相關。

   • 原因： RFID 標籤通常是被動式（無電池）或半主動式，它們需要一個簡單且高效的方式在多個標籤同時回應讀取器時解決防碰撞 (Anticollision) 問題。

   • 機制： 讀取器 (Reader) 充當同步控制中心，發送時槽同步訊號給標籤。當多個標籤在同一時槽傳輸其識別碼 (ID) 發生碰撞後，它們會使用 Slotted ALOHA 的原理（如您模擬的隨機後退機制）來決定下一次嘗試傳輸的時間，直到單個標籤成功回應為止。

4. CSMA 協定的基礎 (Foundation for CSMA)

   載波偵聽多重存取 (CSMA) 協定，例如用於 Wi-Fi ($802.11$) 的 CSMA/CA 和用於乙太網 ($802.3$) 的 CSMA/CD，都是在 ALOHA 的隨機存取基礎上加入了「載波偵聽」（先聽後說）的機制。這表示 Slotted ALOHA 協定奠定了隨機存取協定中處理多個使用者共享單一頻寬的基礎原理。

import tkinter as tk

from tkinter import ttk, messagebox, scrolledtext

import random

import matplotlib.pyplot as plt

from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg

# ----------------------------------------------------

# 📌 Matplotlib 中文設定：解決圖表中文亂碼問題

# ----------------------------------------------------

# 設置支援中文的字體 (適用於 Windows/大多數系統)

# 如果您運行時仍顯示方框，請將 'Microsoft JhengHei' 替換為您系統中可用的中文字體。

plt.rcParams['font.sans-serif'] = ['Microsoft JhengHei', 'SimHei', 'Arial Unicode MS'] 

# 解決負號 '-' 顯示為方塊的問題

plt.rcParams['axes.unicode_minus'] = False 

# -------------------- Slotted ALOHA 模擬核心 --------------------

class classNode:

    """代表一個轉發器節點 (Transponder Node)"""

    def __init__(self, ttl):

        # Time-To-Live (TTL): 重新傳輸前剩餘的時隙數

        self.ttl = ttl

        

    def tick(self):

        """在每個時隙將 TTL 減 1"""

        self.ttl = self.ttl - 1

def simulate_aloha(N_start, N_end, window_sizes, tslots, log_area):

    """

    執行 Slotted ALOHA 模擬並返回繪圖數據。

    

    Args:

        N_start (int): 節點數範圍的起始值。

        N_end (int): 節點數範圍的結束值。

        window_sizes (list): 要模擬的視窗大小列表 (W)。

        tslots (int): 總時隙數。

        log_area (scrolledtext.ScrolledText): 用於輸出日誌的 Tkinter 文本元件。

        

    Returns:

        list: 包含每個視窗大小的 [Nlist, selist, label] 數據列表。

    """

    

    # 設置隨機種子

    random.seed()

    

    plot_data = []

    # 清空日誌區域並允許寫入

    log_area.config(state=tk.NORMAL)

    log_area.delete(1.0, tk.END)

    

    for window_size in window_sizes:

        Nlist = []

        selist = []

        

        log_area.insert(tk.END, f"--- 視窗大小 (W): {window_size:2d} ---\n")

        for N in range(N_start, N_end + 1):

            # 根據視窗大小初始化 N 個節點，TTL 在 [0, W-1] 之間

            snode = [classNode(random.randrange(0, window_size)) for _ in range(N)]

            successful_slots = 0

            

            # 進行 TSLOTS 次時隙模擬

            for _ in range(tslots):

                transmitted_nodes = []

    

                # 檢查並處理傳輸/倒數

                for i in range(N):

                    if not snode[i].ttl:

                        transmitted_nodes.append(i)

                        # 傳輸後設置新的 TTL

                        snode[i].ttl = random.randrange(0, window_size)

                    else:

                        # TTL 倒數

                        snode[i].tick()

                num_transmitted = len(transmitted_nodes)

                if num_transmitted == 1:

                    # 成功傳輸 (吞吐量 S = 1)

                    successful_slots += 1

                elif num_transmitted > 1:

                    # 碰撞 (Collision)：多個 (len > 1) 節點同時傳輸

                    for j in transmitted_nodes:

                        # 碰撞節點重新選擇一個隨機的 TTL 進行重傳

                        snode[j].ttl = random.randrange(0, window_size)

                

            # 計算時隙效率 (Slot Efficiency)

            slot_efficiency = (successful_slots / float(tslots))

            

            log_area.insert(tk.END, f"N = {N:2d}: {slot_efficiency:.6f}\n")

            

            Nlist.append(N)

            selist.append(slot_efficiency)

        

        plot_data.append([Nlist, selist, f'W = {window_size}'])

        log_area.insert(tk.END, "\n")

    # 設置日誌區域為唯讀

    log_area.config(state=tk.DISABLED)

    return plot_data

# -------------------- Tkinter 應用程式 --------------------

class AlohaSimulatorGUI:

    def __init__(self, master):

        self.master = master

        master.title("Slotted ALOHA 模擬器")

        

        # 預設參數

        self.default_windows = [8, 16, 32]

        

        # 設置主框架

        self.main_frame = ttk.Frame(master, padding="10")

        self.main_frame.pack(fill='both', expand=True)

        

        # --- 1. 參數輸入框架 ---

        self.param_frame = ttk.LabelFrame(self.main_frame, text="模擬參數", padding="10")

        self.param_frame.pack(padx=5, pady=5, fill='x')

        self.create_parameter_inputs()

        # --- 2. 控制按鈕 ---

        self.control_frame = ttk.Frame(self.main_frame)

        self.control_frame.pack(padx=5, pady=5, fill='x')

        self.simulate_button = ttk.Button(self.control_frame, text="▶ 執行模擬並繪圖", command=self.run_simulation)

        self.simulate_button.pack(pady=5)

        

        # --- 3. 結果顯示框架 ---

        self.results_frame = ttk.Frame(self.main_frame)

        self.results_frame.pack(padx=5, pady=5, fill='both', expand=True)

        # 日誌輸出區域 (左側)

        self.log_label = ttk.Label(self.results_frame, text="模擬日誌 (N 與效率):")

        self.log_label.pack(side=tk.LEFT, padx=5, anchor='nw')

        self.log_area = scrolledtext.ScrolledText(self.results_frame, wrap=tk.WORD, width=35, height=20, state=tk.DISABLED)

        self.log_area.pack(side=tk.LEFT, padx=5, fill='y')

        

        # Matplotlib 圖表區域 (右側)

        self.fig, self.ax = plt.subplots(figsize=(6, 4))

        self.canvas = FigureCanvasTkAgg(self.fig, master=self.results_frame)

        self.canvas_widget = self.canvas.get_tk_widget()

        self.canvas_widget.pack(side=tk.RIGHT, fill='both', expand=True)

        self.init_plot()

        

    def create_parameter_inputs(self):

        # N 範圍輸入

        ttk.Label(self.param_frame, text="節點數範圍 (N):").grid(row=0, column=0, sticky='w', pady=2)

        self.n_start_entry = ttk.Entry(self.param_frame, width=5)

        self.n_start_entry.insert(0, "1")

        self.n_start_entry.grid(row=0, column=1, sticky='w', padx=5)

        

        ttk.Label(self.param_frame, text="至").grid(row=0, column=2, sticky='w')

        self.n_end_entry = ttk.Entry(self.param_frame, width=5)

        self.n_end_entry.insert(0, "32")

        self.n_end_entry.grid(row=0, column=3, sticky='w', padx=5)

        

        # TSLOTS 輸入

        ttk.Label(self.param_frame, text="總時隙數 (TSLOTS):").grid(row=1, column=0, sticky='w', pady=2)

        self.tslots_entry = ttk.Entry(self.param_frame, width=10)

        self.tslots_entry.insert(0, "100000")

        self.tslots_entry.grid(row=1, column=1, columnspan=3, sticky='w', padx=5)

        # W 視窗大小輸入

        ttk.Label(self.param_frame, text="視窗大小 (W, 逗號分隔):").grid(row=2, column=0, sticky='w', pady=2)

        self.w_entry = ttk.Entry(self.param_frame, width=20)

        self.w_entry.insert(0, ",".join(map(str, self.default_windows)))

        self.w_entry.grid(row=2, column=1, columnspan=3, sticky='w', padx=5)

    def init_plot(self):

        """初始化空的 Matplotlib 圖表"""

        self.ax.clear()

        self.ax.set_title("Slotted ALOHA 模擬結果")

        self.ax.set_xlabel("# of Nodes (N)")

        self.ax.set_ylabel("Slot Efficiency (Throughput S)")

        self.ax.set_xlim(0, 32)

        self.ax.set_ylim(0, 1)

        self.ax.grid(linestyle='--')

        self.canvas.draw()

        

    def run_simulation(self):

        try:

            # 獲取並驗證輸入

            n_start = int(self.n_start_entry.get())

            n_end = int(self.n_end_entry.get())

            tslots = int(self.tslots_entry.get())

            w_str = self.w_entry.get()

            

            # 確保視窗大小是有效的整數列表

            window_sizes = [int(w.strip()) for w in w_str.split(',') if w.strip().isdigit()]

            if not window_sizes:

                raise ValueError("視窗大小 W 格式無效或為空，請輸入逗號分隔的整數。")

            if n_start >= n_end or n_start < 1 or n_end > 100:

                 raise ValueError("節點範圍 N 必須在 1 到 100 之間，且起始值小於結束值。")

            if tslots < 1000:

                raise ValueError("時隙數 TSLOTS 必須夠大以確保準確性 (建議 >= 10000)。")

        except ValueError as e:

            messagebox.showerror("輸入錯誤", f"請檢查輸入參數：\n{e}")

            return

        

        # 執行模擬

        self.simulate_button.config(state=tk.DISABLED) # 禁用按鈕防止重複點擊

        plot_data = simulate_aloha(n_start, n_end, window_sizes, tslots, self.log_area)

        self.simulate_button.config(state=tk.NORMAL) # 啟用按鈕

        

        # 更新圖表

        self.update_plot(plot_data)

    def update_plot(self, plot_data):

        """根據模擬數據更新 Matplotlib 圖表"""

        self.ax.clear()

        

        for Nlist, selist, label in plot_data:

            self.ax.plot(Nlist, selist, label=label)

            

        # 設定標題、標籤和圖例

        self.ax.set_title("Slotted ALOHA 模擬結果")

        self.ax.set_xlabel("# of Nodes (N)")

        self.ax.set_ylabel("Slot Efficiency (Throughput S)")

        self.ax.legend(loc='upper right')

        

        # 根據實際數據調整 x 軸範圍

        max_n = max([max(d[0]) for d in plot_data]) if plot_data and any(d[0] for d in plot_data) else 32

        

        self.ax.set_xlim(0, max_n)

        self.ax.set_ylim(0, 1)

        self.ax.grid(linestyle='--')

        

        # 重新繪製 canvas

        self.canvas.draw()

if __name__ == "__main__":

    root = tk.Tk()

    app = AlohaSimulatorGUI(root)

    root.mainloop()

程式碼模擬了 Slotted ALOHA 的分散式控制重傳機制。在 Slotted ALOHA 中，理論上的最大吞吐量 Smax 發生在提供的負載 G=1 時，約為 36.8% (1/e) 。

在您模擬中：

• W (Window Size) 代表節點在碰撞後隨機選擇重傳時隙的範圍。

• 當 N (節點數) 較小時，提供的負載 G 較低，通道未充分利用，效率低 。

• 隨著 N 增加，碰撞的機率也會增加 。

• 最佳效率將出現在一個平衡點，此時 N 產生的重傳負載 G 約為 1。您的圖表應該會顯示效率先上升後下降，在 N 較小時，W 越小，效率越高。

優點	說明
更高的效率	最大吞吐量為 $36.8\%$（即 $1/e$），是純 ALOHA ($18.4\%$) 的兩倍。
實作簡單	相較於複雜的現代協定（如 CSMA/CD），其機制簡單，易於為中等流量的系統設計。
更好的碰撞控制	透過同步化，將潛在碰撞的時間間隔減半（從 $2\tau$ 減至 $\tau$），從而降低了碰撞的機率。
低負擔	不需要複雜的協調或過多的控制訊息。

好的，這是對 Slotted ALOHA 協定的假設、優點和缺點的翻譯與整理。

---

時槽化 ALOHA (Slotted ALOHA) 協定整理 📝

協定假設 (Assumptions)

這些假設是 Slotted ALOHA 協定能夠實現其效率提升的基礎要求：

1. 所有訊框尺寸相等 (All frames are of equal size.)¹

   • 所有的資料封包（訊框）都具有相同的長度，因此它們的傳輸時間 ($\tau$) 相同。這是劃分固定時槽的基礎。

2. 時間劃分為與一訊框時間等長的時槽 (Time is divided into slots equal to one frame time.)

   • 通道被劃分為離散的時槽，每個時槽的長度恰好等於一個資料訊框的傳輸時間。

3. 節點僅在時槽開始時傳輸 (Nodes transmit only at the beginning of slots.)²

   • 這是與純 ALOHA 最主要的區別。節點必須等待到時槽的開始點才能發送資料。

4. 所有節點都與時槽邊界同步 (All nodes are synchronized to the slot boundaries.)

   • 網路中的所有裝置（如 RFID 標籤）必須時鐘同步，以便精確地識別和遵守時槽的起始點。

5. 碰撞可在時槽持續時間內偵測到 (Collisions can be detected within the slot duration.)³

   • 假設發送節點或接收器（讀取器）能在當前時槽結束前確認傳輸是否發生了碰撞。

---

協定優點 (Advantages)

優點	說明
更高的效率	最大吞吐量為 $36.8\%$（即 $1/e$），是純 ALOHA ($18.4\%$) 的兩倍。
實作簡單	相較於複雜的現代協定（如 CSMA/CD），其機制簡單，易於為中等流量的系統設計。
更好的碰撞控制	透過同步化，將潛在碰撞的時間間隔減半（從 $2\tau$ 減至 $\tau$），從而降低了碰撞的機率。
低負擔	不需要複雜的協調或過多的控制訊息。

---

協定缺點 (Disadvantages)

缺點	說明
同步負擔	必須在所有節點間維持精確的時鐘同步（通常由讀取器或基地台控制），這增加了系統的複雜性。
碰撞仍然發生	如果兩個或多個裝置在同一個時槽的開始點同時傳輸，碰撞仍然無法避免。
相對於現代協定吞吐量較低	即使在最佳情況下，其效率也僅為 $36.8\%$，遠低於 CSMA/CD (90% 以上) 或 Token Passing 協定。
增加延遲	節點即使準備好傳輸，也必須等待到下一個時槽的開始才能發送，這可能會增加額外的平均延遲（相對於純 ALOHA 隨時可發送）。