---
# System prepended metadata

title: 無線通訊網路
tags: [courses meow]

---

# 無線通訊網路
###### 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 傳遞模式

```graphviz
digraph {
  AP -> STA1
  AP -> STA2
}
```
```
一張時間圖
```
![](https://i.imgur.com/PqOCaWc.png)

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

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

### PCF
```sequence
AP -> STA: DL
STA -> AP: ACK
AP -> STA: polling
STA -> AP: UL
AP -> STA: ACK
```
> AP (Access Point)
> STA (Station)

#### **Piggy back**

![](https://i.imgur.com/ewpqYN1.png)

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

### DCF

![](https://i.imgur.com/Ta13Ddm.png)
![](https://i.imgur.com/qoJoi4O.png)

```
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


![](https://i.imgur.com/KIwHIrv.png)

### 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 幫忙傳遞訊息
![](https://i.imgur.com/befHcYL.png)

![](https://i.imgur.com/AnlKqGV.png)
> 架設 IOT 時，會先用 FFD 連接主要線路，周圍再放置一大堆 RFD


![](https://i.imgur.com/MdoGGju.png)
> 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)
![](https://i.imgur.com/5PK1gqa.png)
> 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
![](https://i.imgur.com/fBeW7WK.png)

---
# 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 來得知"往某方向移動，距離的變化"
- 多個三角形做交集來得知自己的位置
![](https://i.imgur.com/xVYV1V1.png =400x)


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

![](https://i.imgur.com/RE3NKFJ.png =400x)
![](https://i.imgur.com/wT08z9Z.png =400x)

:::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 要給出自己的位置之訊，要給
  - 重心位置
  - 各角度的範圍
![](https://i.imgur.com/BkQVYXJ.png =400x)
> 求交集時，每隔 pie(圓弧) 分別做檢查
![](https://i.imgur.com/9AhV6TV.png =400x)

- 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 連結
:::