---
title: Random Access 和 各種 MAC 介紹|第六週
tags: 無線與行動網路導論
---
# 各種 MAC / Medium Access Control

在之前講 Multiplexing 的時候，以及上週的 Random Access 開頭，都有提到 MAC 這個名詞
的確，因為 MAC 是一個統稱，因此有各種類型的 MAC [請見維基百科](https://zh.wikipedia.org/zh-tw/%E4%BB%8B%E8%B4%A8%E8%AE%BF%E9%97%AE%E6%8E%A7%E5%88%B6)

## Multiplexing 時的 MAC

那時候的 MAC 是有一個中央來管理的 central control，也就是我們的基地台
由基地台來分配時間、頻段等等資源，所以才會說是 centralized 的 system

## Random Access 的 MAC

這時候因為沒有一個中央管理員分配資源，需要大家各自協調好；也就是個 Distributed 的 system
>要好好的跟周圍的人和平共處

# CSMA / Carrier Sense Multiple Access

回顧上週的部分
Carrier Sense 英文又叫做 Listen before Transmission / Talk 就是傳之前聽聽看

改善了 Aloha 的想傳就傳的特性；但還是偶爾會有collision 發生，因為

如果大家都同時聽了，然後同時發現沒有人在傳，就會變成大家同時一起傳

## 「聽」這件事情很好做

只要把接收器打開來就知道了

而聽得到有兩種情況

- 可以清楚聽得到內容
- 就是你可以知道哪個是誰傳的，來自哪裡等等
- 此時就很明確知道要等他們傳完
- 覺得周圍有人在講話
- 也就是其他人有點遠，導致你不是很清楚知道他們在講甚麼
- 此時就是判斷這些能量有多少
- 到達特定值就判定為是有人正在傳輸

## Back Off 後退 / 退步

這個不是真的時間軸上的後退，而是「晚一點」的意思

這個動作就是 CSMA 的精隨，也是 Random Access 中 Random 的部分

### p - persistence

如果要傳訊號的話，就會隨時都在聽，直到發現頻段「是空的」

1. 此時丟一枚機率是 p 的硬幣，決定要不要傳
2. 如果結果是不要傳的話，就等待「固定時間」
- 如果固定時間也是每個人不一樣的話，就會有更特別的隨機分布

### 1 - persistence

這是 p - persistence 的特列，當 p = 1 的時候
其實就是上面的提到會讓大家相撞的例子


假設 B 跟 C 用了同個協議，都是聽一聽沒人傳之後，就馬上開始傳，就會發生碰撞

### non - persistence

如果要傳訊號的話，會先聽一下，如果頻段「不是空的」

1. 丟一顆隨機骰子，決定要等多久時間
2. 時間到了之後再聽聽看，如果：
- 還是有人在傳，那就丟下一顆骰子，然後再根據骰子等一段隨機時間
- 直到某個臨界值就回報傳不過去
- 如果沒人在傳就可喜可賀，可以傳了

>這就是後來的 Wi-Fi

:::warning
所以可以知道「隨機」分成兩大類

- p 就是要傳的話會一直聽，然後由隨機決定要不要延後特定長度
- 所以這很像很心急要傳訊息一樣
- non 則是要傳的話會先聽一下，有人的話用隨機決定等待時間
- 所以這很像沒有那麼心急要傳訊息一樣

可以發現， p 是聽完後，再以隨機決定要不要等；而 non 則是聽完後，沒有人就可以直接傳

主要差在 non 是各自等待著「隨機的等待時間」才會再去聆聽，所以不會大家都同時一直在聽，也就不會因此同時相撞
:::

---

## 比較


Through Out 是 1 秒內「有幾秒在傳」；Offered Load 提供的流量，也就是有多少傳的人

可以看的 1-P 在人少的時候比 non-P 好，畢竟人少的時候就不容易相撞
反而當人越來越多的時候，就需要 non-p 隨機等待的特性

你問 p-P 在哪？，老師說圖形跟 1-P 一樣，因為多了隨機性，所以比 1-P 適用人多一點的情況，但是人如果太多的話還是很容易打架

---

# Acknowledgement / ACK

之前 CSMA/CD 的 CD，就是去檢查電線上的電壓；如果有同時在傳，電壓會比較高，也就是發生了碰撞，就會重傳

在分散式環境中，不像電線檢測電壓去檢測碰撞這麼好做，要怎麼知道有收到，就是要傳一個「我有收到 / ACK」回去
所以如果沒有收到「我有收到」有可能是真的發生碰撞，或者也有可能是 ACK 沒有傳成功

## 指向性天線的問題

雖然指向性天線的確可以減少或避免上週提到在 RA 會有的各種 node 或是同頻干擾的問題

但是既然要指向，有一個最基本的問題是，你要指向哪裡？
所以指向性的協議，都會「先掃描一下周圍」，因此掃描的時間跟真正的傳輸時間就要取捨

老師說 802.ae 高頻的指向性強

---

# Random MAC 的 Component

一個 Random MAC 的協議，主要由以下三個部分組成

## Contention

搶頻道的方法，也就是每次聽聽看之後決定要不要用頻道的這個行為

- 這就是 RA 獲取傳輸「時段」的方式
- 對，要記得他們用的是同個頻段不同時間
- 基地台會**特別開一個頻段提供 RA 使用**，像現在的 WiFi 或藍芽就是這樣，並且會有個 Power 的限制。

- 另一種會遇到 Contention 的地方是 「Show your interests」
- 當手機**開機要連到基地台**，此時基地台是無法預測你的出現的
- 所以手機跟基地台做「第一次的連線」就是使用 RA，之後才會分配資源給你
- 另外像是當系統**不知道有誰要連進來的時候**
- **或不知道誰在周圍**，**不知道哪些資料會傳過來**
- 像是某些久久才回報一次的感測器

:::warning
總之就是要中央管理之前，需要一些 RA

上面感測器的例子像是 5G 跟之後的協議，有很多 IOT device ，傳輸的**頻率(次數)很低**，很久才傳一次，每次也都少少的資料，所以會特別分配出一個頻道提供 RA 用
:::

## Reservation

當傳了第一個資料成功後，最好就是建立穩固的連線，這就是 Reservation 保留

## Data transmission

上面兩個步驟成功後，進行資料傳輸的部分

## 設計原則

- 要讓傳輸有效率；不能等太久，或是常發生碰撞
- 避免不必要的 contention，減少 collision
- 減少每次 contention 造成 collision 的 花費

---

# DAMA / Demand Assigned Multiple Access

直翻叫做「需求分配多重存取」；而所謂的分配就是上面提到的 Reservation
>DAMA 這個名詞老師說以後不常出現

因為有了保留，所以在保留的時段內**很難會有碰撞**，將效率提高到了 80%
>但是老師說偶爾還是會有

但是因為多了保存的動作，所以**會有延遲**

## 場景

常用於高延遲的情景，像是衛星通訊；如果每次要取得傳輸的時段都用 contention ，會非常耗時

>假設你先傳過去搶搶看時段，結果傳過去的時候發生碰撞，這樣又要再花時間再傳一次
>如果一直碰撞就沒完沒了，一來一回時間消耗很大，不符合剛剛提到的設計原則

## 保留的方法 / 演算法

- 明確的保留 Explicit Reservation
- 如 Reservation-ALOHA
- 不明確的保留 Implicit Reservation
- 如 PRMA
- 保留式 TDMA

## Explicit Reservation -- Reservation-ALOHA

分為兩個模式(modes)?，或者說階段

- 為了獲得「保留 Reservation」的 ALOHA mode
- 先進行的階段
- 會去競爭較小的 reservation slot
- 這就是上面提到的 Contention 部分
- 這時是會發生碰撞的時候
- 保留模式 resevation mode
- ALOHA mode 之後進行的階段
- 根據剛剛 ALOHA 競爭下來的「時間分配結果」
- 每個訊號可以依序獲得保留的時段
- 通常這個獲得保留的時段會比較長
- 這就是上面提到的 Reservation 部分

:::success
可以發現這就是 slotted ALOHA
:::


圖中，前面五個小 slots 就是 ALOHA mode 競爭的階段，用來表達「傳的意願」
後面五個大的 slots 就是傳的時間

所以說原本的 ALOHA contention 跟 transmission 是屬於「同個部分」
這個改進的 protocol 則是把 contention 跟 transmission 給分開

而且因為兩個動作是分開的，所以前面的 slot 比較小會使 collision 的時間變小
>符合設計原則

### 限制

- 每個人都要知道哪些通道保留了給了哪些人，這樣才能知道後續如何保留
- 因為是 slotted aloha ，所以要進行時間的同步

---

# Implicit Reservation -- PRMA / Packet Reservation MA

:::warning
這個回合若傳輸成功，下個回合就還是保留給我；但如果下個回合我沒有用，下下回合就再次開放給大家
:::

**回合制的 time slot**


上面的圖片中，每個 frame 是一個回合，裡面劃分成很多小頻段 slots 給大家用

- Contention
- 每個 frame 如果有空的 slot，大家就會對那個 slot 進行 contention
- 根據 Slotted ALOHA 的原則競爭
- Reservation
- 如果 Contention 後沒有發生 Collision，代表那個人搶成功了
- 這時候就會觸發 Reservation，下一 frame 這個 slot 就會保留給他
- 圖中的紅色方塊代表發生 Collision，所以沒有人可以在下一 frame 使用該 slot
- frame~2~ 的第 7 格，只有 F 進行 Contention，所以他就可以在 frame~3~ 進行傳輸
- 這個被保留的 slot，可以保留到直到某一回合沒有進行傳輸
- 注意上圖中，先空出 slot 一回合，下一回合才會進行 Contention

:::info
上圖是時間去劃分 slot，也就是在一小段時間內分先後；當然你也可以改成切在頻率上
:::

:::success
適合用於音訊的實時保留 / voice / video real-time reservation
:::

## PRMA: voice+data

PRMA 的改進版本；將聲音跟資料分成兩類來傳輸

- Voice 聲音
- 就是採用上面的 PRMA，Implicitly Reservation
- Data 資料
- 保留 RA 模式，這回合搶到，下回合不保留


基本架構跟上面的 PRMA 是一樣的，但是保留制度變成需要今過判斷

- 如果是音訊的話，就啟用保留制度
- 如果是資料的話，不啟用保留制度，採用一般 RA
- 也就是下一回合還是開放給大家使用

當初是設計給打電話的人用，所以保留才只保留在音訊上

:::info
可以注意到有些微不同，就是發生 Collision 後不會等待一回合，而是繼續進行 Contention
:::

---

# Reservation TDMA

這個不完全是 distributed 因為要有個中央進行分配，畢竟是個 TDMA
跟前面 Reservation ALOHA 有點像，有前面用來交換訊息的 slot

- N 個 mini slots
- 每個 MS 各自被基地台分配一個 mini slot
- 用來交換訊息的，告知後面要給我保留多少大的 slot
- N×k 個 data slot
- 主要傳輸的部分，會根據前面的小 slot 提供的訊息，保留對應數量的 data slot 下來
- 但是一個 mini slot 最多只能保留 k 個 data slots

然後其他 MS 可以使用剩餘空的 data slots 傳輸訊息，**依據 round-robin sending scheme**


上圖中有 6 個 mini slots 所以是假設有六台 MS
右邊 12 個 data slots，分別預設給左邊六台 MS 用；也就是說 k=2
但**不一定每次都要全用**，所以**沒有用的會放出來給大家用**

前面的 mini slot 大家會交換訊息，告訴各位自己對應的大 slot 有幾個要用幾個不用

## Round Robin

以上圖為例子，由該回合使用了兩個 data slots 的人進入 round robin ，將剩餘的空格依序分配給那些人

## 缺點

- n 的數量可能是「會變動的」
- 因此會造成這個不太能用
- 所以要用的話 n 不能變動太大
- 彼此要聽得清楚 mini slots 的內容
- 聽不清楚就完了
- **老師說有個前提是不能有 hidden node**
- 畢竟 hidden node 就是有一個人聽不到對面的人

## 優點

不太有碰撞

---

# MACA / Multiple Access with Collision Avoidance

他的名字有 CA，那他要怎麼 CA? 使用「小小訊息 / short signaling packets
」~

## short signaling packets

分為兩個小小訊息

- RTS request to send
- 告訴接收方，「我想要傳」
- 向接收方請求「傳送的權利 right to send」
- 並告訴接收方「傳輸方的地址」
- 還有傳輸的資料大小，也就是在說這份資料可能會傳多久，可以用傳輸速率算出
- CTS clear to sen
- 告訴傳輸方，「場道淨空，可以傳」
- 向傳輸方給予「傳送的權利 right to send」
- 並告訴傳輸方「接收方的地址」

成功發送 RTS，並收到 CTS 後，就可以開始傳資料了

回憶起上面提到的 ACK ，就是比原本的傳 data 跟接收 ACK 多了這兩個步驟

## 廣播

要注意 RTS 跟 CTS 是「**會同時給別人聽的**」，這樣別人就會知道不久後有人會變成發送者或接收者

所以有個重點是**路人也知道你們在幹嘛**

## 協議的優缺點 -- 取捨

### Hidden Node


看任何協議就是要去看他的取捨，看他優點在哪，缺點在哪
像 MACA 的優點就是**減少了 Hidden node problem**，因為兩方都會進行廣播
與此交換得是要多做 RTS 跟 CTS 的動作，會有延遲、能耗等等得


上圖中，A 跟 C 都想傳資料給 B，可是 A 跟 C 是互相聽不到的；圖中 A 先傳 RTS 給 B，然後 B 再廣播 CTS，所以 A 跟 C 同時都會收到 CTS，這樣 C 就會等待他們先傳完

:::warning
注意，上面也是一種 hidden node，要記得 Hidden node 不只有上上面那張得形式。
只要是你聽不到的人，他就算 Hidden node
:::


在**原始的 MACA** 中，Exposed node 也可以解決，因為要各自傳資料的兩個 Node 可以透過 RTS 知道，他附近要傳的人是要傳給誰，並因此知道各自要傳的人，各自都不會影響到，所以就會同時傳


上圖中，B 想要傳資料給 A，A 跟 C 也是互相聽不到的；此時 B 廣播了 RTS 出去，A 跟 C 都聽到了，**所以 C 可以確認 A 跟他是彼此聽不到的**，因此他就可以安心的廣播 RTS

:::info
注意：
IEEE802.11 有各種 MACA 的其他版本，向是只要聽到 RTS 或 CTS 就不傳
有些會造成 Exposed Node
:::

---

# Generalized MACA -- State Diagram

我們來看懂狀態圖


## 發送方

- Idle 閒置
- 若接收到接收方的「傳輸就緒」，會傳輸「RTS」，然後切換到「等待狀態」
- 此時就是等待接收方的許可
- Wait for the right to send 等待狀態
- 若接收到接收方的「CTS」，會傳輸「Data」，然後切換到「等待 ACK」
- 此時就是等待有沒有傳成功
- 若接收到接收方的「接收方忙碌中 RxBusy」，會切換回「閒置」
- 此時要等到接收方有空
- 若遇到「超時 Time-out」，會傳輸「RTS」，並再次跳回「等待狀態」
- 此時就是再次等待接收方的許可(CTS)
- Wait for ACK 等待 ACK
- 若接收到接收方的「ACK」，會切換到「閒置」
- 等待下一次訊息傳輸
- 若遇到「超時 Time-out」或是接收到接收方的「NAK」，會傳輸「RTS」，並切換回「等待狀態」
- 此時就是再次等待接收方的許可(CTS)

## 接收方

- Idle 閒置
- 若接收到傳輸方的「RTS」，會發送「CTS」，並切換到「等待資料」
- 此時就是等待資料傳過來
- Wait for data 等待資料
- 若接收到傳輸方的「data」，會發送「ACK」，並切換到「閒置」
- 等待下一次的傳輸
- 若遇到「超時 Time-out」或是「資料毀損」，會傳輸「NAK」，並切換到「閒置」
- 此時就是傳輸失敗，等待資料再次傳過來
- 如果接收方本身很忙，收到發送方得「RTS」後會傳輸「RxBusy」，並跳回「等待資料」

### Time out

兩方再在接收的時候會遇到的情況，「超時」，就是久久等不到對方的回覆

### RxBusy

原本 MACA 才有， 802.11 的其他版本沒有；接受者向其他人表明我在忙，先不要傳給我

### Nak

原本 MACA 才有， 802.11 的其他版本沒有；等了半天沒有收到，或是收到的是錯的，會回傳這個

---

# MAC Polling

:::warning
介於 TDMA 跟 RA 的 MAC
:::

- 是個主人跟奴隸的架構；
- BS (AP) 是主人
- 很像抽籤的概念，主人會去抽奴隸
- 上面那句話聽起來有點糟糕
- BS 會發送「Poll」給 MS
- 這個 Poll 內容是 MS 的 MAC 地址
- 也就是說 Uplink Transmission 是由 BS(AP) 的 Polling 控制
- 三個重要過程
- Request：MS 請求 Uplink 傳輸
- Poll：BS 在 Polling 的過程會去分配可用的頻帶
- Data：MS 的 Uplink 資料傳輸過程

還是換個正常一點得比喻好了，老師比喻成學生(MS)和老師(BS)

- Request 就是老師我想講話
- Poll 就是老師點了誰講話
- Data 就是開始講話的過程

如果有很多學生想要講話，老師就會抽一個學生起來說
所以抽某個學生起來，讓他說話，只會發生在「讓學生說話」，也就是只會用在「 Uplink 」
而不會發生在「老師跟學生說」，也就是「Downlink」；「Downlink」則會是廣播的形式，或者是休眠的狀態，很像老師對全班問一個問題

:::warning
由於老師點人講話的時候，當下就只有他能講話，也就是把資源完全給他，不管他之後有沒有真的要傳；可能被點到後緊張忘記要說甚麼。

所以才會說介於中央管理的 TDMA 跟 RA 之間
:::
## Polling Protocol Design

:::success
有很多種 Polling 的機制
:::

### 設計的彈性

- 要不要回傳 ACK?
- 能不能 Uplonk Downlink 同時做
- Polling 把人選起來之後，有不同的操作
- 有些會先叫被選的學生，告訴老師要講多久(資料量大小)，講多少內容(所需頻寬)
- 也就是把 Bandwidth Request 跟 Data Transmission 分開

## 種類 1


淺色是 Downlink，也就是 Polling；深色是 Uplink，也就是請求或傳輸資料
總共有三名學生/三隻手機。
在最左邊，也就是時間最一開始，老師點得一號同學，然後一號同學就會回答老師他有多少內容要報告，還有報告大約多久
**然後這時候會先請他坐下，換點下一位二號同學起來**
但是二號說他沒有要報告得；所以老師換點三號同學，三號同學就有要報告得內容。

:::info
所以這個種類的 Polling，是老師先把學生點過一遍，確認有誰要報告，有要報告的要記得先大致講內容、時間。
很像在開班會？但是高中好像從來沒有開過班會...
:::

都點完之後，老師會依剛剛得順序把學生點起來報告，所以他會先點一號同學起來，然後等他報告完；
之後再點三號同學起來，然後等他報告完。之後就很像換個主題再開一次班會，所以老師就會再點一次大家

:::info
所以老師再次點人起來說話得這個動作，就是把時間這個資源先暫時都分配給某個學生。
而且由於剛剛有大致聽了學生的報告時長，所以分配時間就有不同的長短；
老師並不是把全部時間都給某個學生從頭講到底，會去做分配。
:::

:::success
Keep alive 只有某些協議有。
常發生於手機突然沒電，等等情況，這樣基地台沒聽到你的訊息，就知道你應該不在連線了。
很像是開班會伴隨著點名。
:::
## 種類 2


這個種類是 Uplink 跟 Downlink 融合在一起的設計；簡單來說就是看上傳下傳有沒有資料

總共有四種可能

- Poll no data
- BS 告訴 MS 待會**沒有要傳資料給你**
- 像是最左邊兩個都是 no data
- Poll data
- BS 告訴 MS 待會**要傳資料給你**
- Uplink data
- MS 上傳資料給 BS
- 左邊第二個，MS 得知 BS 不會傳東西下來，所以就可以直接傳東西上去
- 然後 BS 就會回傳 ACK
- Downlink data
- BS 下傳資料給 MS
- 左邊第三個，MS 表明了他沒有資料要傳，而 BS 有東西要傳
- 所以 MS 收到後，也會回傳 ACK
- 同時都要傳資料
- 左邊第四個，BS 跟 MS 都要傳資料，但是 MS 聽到 BS 要傳後
- 他會先傳給 BS，原因是因為
- BS 再傳給 MS 的時候，可以順便給他 ACK
- 當然，MS 之後也是要回傳 ACK
- ACK data
- 四種可能有五種情形，是一件很正常的事對吧
- BS 或 MS 表示有接收到資料
- 這個例子中，只要是收的人，都會有 ACK

:::warning
可以看到 Poll 跟 data 並沒有分開
:::

---

# ISMA Inhibit Sense Multiple Access

Inhibit Sense，禁止聆聽；**當前頻段的狀態，會透過一個「Busy tone」** 來告知各位

## Busy tone

一個二元信號，是個規定的狀態；MS 聽了就知道是哪種狀況

- BS 會在頻段沒有空位時 not free，持續發送這個 Busy tone 給 BS (Downlink)
- 聽到這個訊號的 MS，就可以知道當前能不能傳資料
- 如果那個訊號還在發送，MS 就知道不能傳輸資料
- 一旦那個訊號停了，MS 就知道可以傳輸資料了
- 發生碰撞時，BS 也會發送這個 Busy tone 告知 MS 們發生碰撞了
- 如果傳輸成功則會回傳 ACK
- 用於 CDPD

:::info
這個 Busy tone 也用於其系統
:::
:::warning
老師說要記得 busy tone 的概念就好：「想要用很簡單的方法，讓大家知道發生什麼事」。
而這個簡單的方法，就是 Busy tone 這個簡單的 binary siganal
:::

## ISMA ？

- IS
- Idle signal
- ISA
- Idle signal with acknowledgment


上圖可以看到，BS 發送了兩次 Downlink 的 BT，告知現在有空；然後可能有多個 MS 同時聽到有空，所以就一起傳 Uplink，然後就...就 Collision 了。
所以等待碰撞完後，BS 又再次發送一次 BT，而這次似乎就只有一個 MS 傳資料，所以 BS 接收完後發送了一個 ACK 回去

---

# SAMA / Spread Aloha Multiple Access

ALOHA 跟 Spreading Code 的結合；還記得我們的老朋友 Code 嗎？

>老師說沒有很常用


當初 ALOHA 會碰撞，有一個原因是大家傳輸得時間太長，然後就重疊到了。
所以這裡是利用 Code 的 chipping sequence ，把訊號拆成很多小段，這樣就不會互相撞到了。

但是前面講 coding 時是大家用不同的 codes；這裡是用同一個 code，所以就好像把 CDMA 的 CD 給去掉。

## 問題

要找到一個有好的特性的 chipping sequence

:::warning
但是老師說現在大家沒有再用了。
:::

---

# 總結

- Centralized allocation
- 由中央分配資源，分配你可以用哪個頻段、哪些時間、哪個 Code
- 像是 TDMA、CDMA、FDMA 等等
- Uplink 跟 Downlink 部分
- Request/Allocation
- 要求後再分配資源
- 就是中後段提到的 Polling 的部分
- Uplink 部分
- Random Access
就是上週跟這週提到的 CSMA, ALOHA, 802.11 等等