# 無線通訊網路
###### tags: `courses meow`

:::info
無限通訊網路主要在討論 link layer(MAC layer) 和 physical layer
:::
:::info
## info
- [名詞解釋](https://www.thu.edu.tw/wireless/qa.html)
:::

## methods
- pure ALOHA
- slotted ALOHA
- CSMA
- 1 -persistent CSMA
- p-persistent CSMA
- non-persistent CSMA

### conntention based
- MACA
- RTS
- CTS

### Hybrid
- DAMA

# 802.11 傳遞模式

digraph {
  AP -> STA1
  AP -> STA2
}

一張時間圖


802.11 主要包含兩種時段：PCF(輪詢), DCF(競爭)
> PCF: Point Coordination Function
> DCF: Distribute Coordination Function
> 使用 beacon封包 與 CF_END封包 來告知 station 目前的 period

AP(Beacon)
> Beacon 是一種小型封包
> 包含: 此 AP 還有多少對 STA 的 buffer

### PCF

AP -> STA: DL
STA -> AP: ACK
AP -> STA: polling
STA -> AP: UL
AP -> STA: ACK

> AP (Access Point)
> STA (Station)

#### **Piggy back**


> 將複數個封包綁在一起送
> 當 AP 送出 $DL_i$ 後，過了 PIFS 的時間後，第 $i$ 個 station 沒有回覆了話就暫時不管它

### DCF


CF_END -> DIFS(DCF Interfram Space)         -> Random backoff -> data(send/receive) -> ... -> PIFS ->       Beacon
          (宣告有沒有要送，client 發現自己不用收                                                  (搖鈴前的等待)    (搖鈴)
           便可暫時休眠)

priority
<--- DIFS --->
<-- PIFS -->
<-SIFS->

DCF 也有考慮到省電的議題，DIFS + Random backoff 期間會讓收方知道送方要送東西給它，以免發生收方休眠而沒收到封包。
碰撞很浪費資源，會消耗很多額外的電

carrier sense 是一個監聽行為，每次發送封包前都會進行一次，用以確認是否有其他人也送封包。

> 我們最擔心 receiver 的碰撞

> 每次 DCF 都會有一個 STA 成功送到一份 data

<!-- 我聽不懂老師的比喻
STA 是啥 相對 AP 的 client ㄇ
為什麼叫 station why not just call them.... device or client
sender receiver
怎樣算是 “撞”
感覺像是破壞性干涉，畢竟他們是波嘛
應該是station的縮寫吧 無線網路的術語？
搖鈴是哪一個？
beacon -->

<!-- 好熱 -->
#### Random Backoff 機制
每次的 Random 都有一個範圍，而隨著每一次的碰撞發生，這個範圍會不斷變大(每次x2)。

backoff 越大撞得機率越大

## CSMA/CA RTS/CTS
> (**C**arrier **S**ense **M**ultiple **A**ccess with **C**ollision **A**voidance)
> 在有限網路中有類似東西叫 CSMA/CD


### Hidden terminal problem

A -> B
C -> D
但是C節點不知道有人正在傳送資料給B節點，
此時傳送資料給D節點，造成B節點收資料時產生碰撞
- 可以使用 RTS/CTS 解決 (MACA 機制：僅收到 RTS 就可以送封包)

#### Exposed terminal problem

B傳送資料給A，此時C想傳送資料給D。
但是C發現B正在傳送資料，所以C就停止
傳送資料給D。
但事實上C傳送資料給D是不影響AB傳輸的。

## 802.11 省電
### TIM (Traffic Indication Map)

| Association ID | Buffered |
| -------------- | -------- |
| 0 | 1 |
| 1 | 0 |
| 2 | 0 |
> TIM 封包結構，每個 Association ID 都對應一台機器

- TIM record data: Association ID, Buffered(0/1)
> 0 : no data
> 1 : have data
- Machanism
- Listen Beacon
- TIM (0)
-> go to sleep state
- TIM (1)
- PCF
-> waiting AP transmit data
- DCF
- STA send PS-Poll to AP
- AP receive PS-Poll and transmit buffered data

> **PS** mode aka **Power Saving** mode

## IEEE 802.15.4 MAC
> Low Rate Wireless Personal Area Network，LR-WPAN

> Topology 就是節點之間怎麼連的意思
1. Full function device (FFD)
- 功能強大的機器
- Any topology
3. Reduced function device (RFD)
- 功能較弱的機器
- 僅能使用 star topology，仰賴 FFD 幫忙傳遞訊息

> 架設 IOT 時，會先用 FFD 連接主要線路，周圍再放置一大堆 RFD

> PAN (Personal Area Network)
> [blog](https://oldmonkey.pixnet.net/blog/post/264341093)

<!-- Association ID 是固定的嗎？ -->

### Transfer mode
#### Association
> 無線網路很容易發生送出請求卻沒有回應的情況
要連接的時候，會發送一個 Association request，Coordinator 會回應一個 ACK ，內容可能是 Accept or Reject。
:::info
Reject 的原因
- 超過服務數量上限
:::

## Mac protocols for WSN (wireless sensor network)
:::warning
The problems of WSN
- idle listening,
- collision
- overhearing
- control overhead
:::
### **async** methods
> 標紅字

#### S-MAC (sensor-MAC)
- feature
- Energy-Efficient
- in ad hoc network
- peer to peer
- period sleep
- virtual cluster
- 同一個 virtual cluster 內部有自己的睡眠週期
- 多個 virtual cluster 交集處的 station 會在兩邊醒來時醒來
- adaptive listening
> 對小 sensor network 來說 RTS/CTS 很耗資源

#### T-MAC (Time-out mac)
> SMAC 睡眠時間固定
> 因此如果提早沒東西 listen 就提早 sleep

- early sleeping problem
- > 若要 A->B->C->D 傳遞 data， D 會因為一開始沒有 RTS/CTS 而提早 sleep
- > 因此會造成延遲 (要等 D 起床)
- Future request-to-send (FRTS)
- 提早告知 forwarding 後面的成員
- > `Data-send` 為內容無意義封包，目的是避免真正的資料與 FRTS 碰撞
- full-buffer priority
- buffer 滿的人先把自己 buffer 裡的東西送出去，先不管別人的 RTS

#### B-MAC (Berkley mac)
- Goals
- Low power operation
- scalable to large number of nodes
- small code and RAM usage
- **Low Power Listening** (LPL)
- Clear channel assignment (CCA)
- > can be turned on/off
- avoid collision
- preamble
- > a physical layer RF pulse
- 若 receiver 聽到 preamble 就要準備收
- Doesn't need RTS/CTS
- Modeling lifetime

:::success
- power saving method
- self-defined wakeup/sleep interval
- long preamble notification
- Transmit Characteristic
- Contention method through CCA algorithm
> 每個節點自行決定醒睡，不同不
> sender 發出很長的 preamble 去確保 receiver 會被通知道z
:::

#### Wise MAC
> better than SMAC
- TDMA (time division multiple access)
- 大家有自己的醒睡週期
- Non-time sync, but maintain 鄰居醒睡週期表
- Decentralized sleep-listen scheduling
- 大致知鄰居的 sleep/wake 表，可以送比較短的 preamble

- advantage
- no idle listening
- no bpreamble delay (b-mac)
- BUT still have hidden terminal problem

### sync methods

#### TRAMA
> ad hoc network
- Nodes need globally synchronized
- 收集與自己 2 hop內的鄰居資訊
- period
- Random access period
- Scheculed access period
- Adaptive Election Algorithm (AEA)
- 整個 network 有一個 has function
- priority = hash(station_id XOR time_slot)
- 使用權
- Schedule Exchange Protocol

- disadvantage
- delay （因為禿然發生的東東需要等到下一個回合才能送

#### DMAC (data-gathering mac)
> 有點考慮到 routeing
- low latency for convergecast communications
- > convergecast communications (將眾多小 node 的東西收集到 sink 處理)
- > broadcast (Source broadcast 給眾人)
- slot-ALOHA
- data gathering tree

## LECH

### Compare

---
# Localization & Positioning
> Localization: 知道自己附近的地標
> Positioning: 知道自己的座標

- anchor node

### Localization
- methods
- RSSI (Received Signal Strength Indication)
- ToA/TDoA (Time of Arrival/Time Difference of Arrival)
- AoA (Angle of Arrival)
- communication

### Distance estimation
#### ToA (Time of arrival)
- 通常用聲波（因為比較慢，時間誤差影響較少
- 設備接收處理時間影響很大

#### TDOA (Time Difference of Arrival)
- 用兩種不同介質的時間差來測距
- > 像是 ultrasound and radio signal

#### TDOA 基地台定位
- 兩基地台訂出一個雙曲線，多對基地台多對雙曲線，算交集，得自己定位

#### Bounding Box
> 有效距離使用最大圓來估計，（實際有效範圍是不清楚的複雜多邊形)
- 由於測距不準，但是知道每個 anchor 的有效通訊距離，因此如果有收到，便知道自己在此範圍內
- 用多個 anchor 範圍求交集，得自己位置

#### Multihop range estimation
- DV-Hop
- DV-Distance
> 假設 hop 間距離一樣，因此 `hop_distance = count_hop(a1, a2) / distance(a1, a2)`
:::warning
- 但是要在**高密度**的 WSN 內才會準
- "anisotropic/heterogeneous" networks 無法使用
- > 異質性的網路，其 hop distance 不會一樣
:::

#### Iterative multilateration
- 先將可以定位的 node (附近有三個以上的 anchor) 做定位
- 已定位的 node 加入 "Participating nodes"
- Participating nodes 可以被視為一種 anchor

### Localization with a Mobile Beacon
- 有一個會動的 anchor (開飛機之類的

#### APIT (Approximate point in triangle)
- > 重點：判斷自己在不在 3 個 anchor 組成的三角形內
- 如果存在一個方向，自己與三個 anchor 的距離都會加大，那麼自己便會在三角形中
- 透過訪問附近的 node 來得知"往某方向移動，距離的變化"
- 多個三角形做交集來得知自己的位置

#### ==MCL== (Monte-Carlo Localization)
> 由三個範圍圈出自己的範圍
> 由於不清楚自己實際位置，以範圍內取多個點作為自己的可能的位置集合
- 與自己 1 hop 的 anchor
- 在一圓圈內
- 與自己 2 hop 的 anchor
- 在一甜甜圈內
- 與自己上一個位置的 V_max 圈圈內
- 再一圈圈內 （位置是一點集合，圈出的範圍也會有很多個


:::warning
這個方法主要用在機器人身上，他們通常有比較好的算例
對於 sensor network 這個方法的算力資源過大
:::

#### MSL (Mobile and Static sensor network Localization)
- type of anchor
- insiders (一直在)
- outsiders （一直不在
- arrivers （剛近來
- leavvers （剛出去

#### DRLS (Distributed Range-Free Localization Scheme)
> 目的是好算
> Improved Grid-Scan Algorithm

#### IMCL (Improved MCL Localization Scheme)
> 討論如何把 normal node 當成 anchor
> 因為 normal node 只有自己的大略位置，不像真正的 anchor 有精準位置
- Prticipated node 要給出自己的位置之訊，要給
- 重心位置
- 各角度的範圍
> 求交集時，每隔 pie(圓弧) 分別做檢查

- Moving constrain
- 預測移動方向
- > 教授說它覺的這個精準性太低，無法依賴，也許加入 AI 會好一點

# Routing
> ad hoc network 中網路拓普易變動 （有人在移動之類的）
> need ad hoc routing protocols
:::info
- option 1 (always keep)
- **proactive** or table-driven
- option 2 (make up a table when on demand)
- protocols operates **on demand**
- option 3
- Hybird

#### Classfication
- **flat** vs **hierachical**
- data
- have identifier or not
- has position data or not
:::

### Proactive protocols
> 要一直保持 link-state
> 通常是 for mobile network，而非 IoT
- DSDV (Destination Sequence Distance Vector)
- OLSR (Optimized Like State Routing)

:::info
#### DV Routing Protocols(Distance Vector)
:::

#### OLSR (Optimized Like State Routing)
- 每個 node 都要記與自己距離 2 hop 內的連結 sub-graph
- MPRs (multipoint relays) (基本上就是指一個 sub-graph)

#### Fish eye Routing (FSR)
> combine LS(OLSR) &ＤＶ

- like-state rounting protocol
- tasks
- Neighbor Discovery
- say HELLOE every $\sigma$ time
- Information Dissemination
- Route Computation
- > with Djikstra's

> 越遠的人資訊更新的越不頻繁

### Reactive Protocols

#### DSR (???)
> 問題很多，不好用
- RREQ (route request ? ?)
- 用 flooding 來尋找 route
- 可能的問題
- > 有些 node 會 cache 部份 route
- stale route caches
- route 過期
- reply storms
- 過多知道答案的人想回答

#### AODV (Ad hoc On Demand Distance Vector)

- source sequence number
- 分辨這次的 router discover 的新鮮度 （避免回覆過就的 RREQ
- broadacst id: 分辨不同的 RREQ
- node 可以 drop 比較晚到的 RREQ
- expiration timer

#### TORA (? ? ? ?)
> 從 "高處" 往 "低處" 送

#### Gossiping rumor routing
> 跟 flooding 的差異是，有機率不把東西繼續傳下去

### GPSR (Greedy Perimeter Stateless Routing)
- 使用地理位置作為依據來做 routing

# 實驗
:::info
應該會有一份 hackmd 連結
:::