文章概览

WSN：Wireless Sensor Network

1

WSN与传统wireless network的区别

设计针对一项特殊任务
能量存储有限
网络结构设计是临时的，时变的
工作在恶劣环境
难以维修
部分节点失效不影响
无需控制中心指导

WSN面对的主要挑战

Energy efficiency
self-management
limited communication range
decentralized management
limited resource (small memory, small CPU … )
security

Medium Access Control

Contention-Free Protocols

基础知识

7 layer：Physical, Data Link, Network, Transport, Session, Presentation, Application.
数据包产生规律：泊松分布随机出现

TDMA

分成很多个time slot

$D=T\left[1+\frac{N}{2(1-\lambda NT)}\right]$

N: sensors
T = P/R: packet transmission time
P: packet size
R: channel capacity(bps)
D: access delay
$\lambda=\frac{1}{T_0}$: Poisson average packet arrival rate

FDMA

一般还是TDMA延迟低

CDMA

cdma的 G chip = 1 bit

Pe 和 Pb

$P_e=\sum_{i=K+1}^P\binom PiP_b^i(1-P_b)^{P-i} = 1 - (1 - P_b)^P$ $P_b=\frac12\operatorname{erfc}(\sqrt{\gamma})$ $\gamma=\frac G{N-1}$

G：CDMA发送G次
N：N nodes
K：错几个算错，一般是一个bit（有时错一两个bit可以被修正，不影响packet error）
P：package里有多少个bit
$\gamma$：SINR 信噪比
$P_b$：bit error probability
$P_e$：packet error probability

Polling

Poll TDMA

Token Passing

pass token

Reservation-Based

first reservation and then data transmission

A: 110

B: 101

Contention-Based Prorocols

ALOHA

侏罗纪公园

直接发送，失败重发

成功率18%

slot-ALOHA

在指定的时间节点发送

成功率36%

CSMA

Carrier Sense：发前吱一声看一眼

分三类：non-persistent, 1-persistent, and p-persistent

CSMA/CD(collision detection)

为啥实现不了

碰撞发生在传输的接收端，发送方将不会察觉到这个碰撞。
half-duplex：不能同时发送和接收数据，因为发送数据声音很大，同一地点接收数据只能接收到自己发送的数据

CSMA/CA

类似 p-persistent CSMA，但是是等一段固定长度（DIFS）加一段随机长度的slot（back off period）再发送。

DIFS是频道在这一段时间都idle，

MACA

如果只查询自己能不能收到信号，只看一眼通道不行，有可能看不到的Hidden Node Problem

RTS/CTS

Exposed node problem：C可以给D发但是收到了B传给A的信号以为通道拥挤（解决：除非收到了隔壁的CTS才说明通道拥挤）

等一段时间，失败就加长等的时间

MACAW

used data sensing（DS）package, send by sender after recieving CTS to inform other nodes of transmission duration.
protect ACK: so that a neighboring sender node will not initiate its own transmission while other sender node is expecting its ACK.

发送数据前，获取发送数据权力的节点在接收到CTS后会发送数据长度。保证其他节点不会在此期间询问。

协议参数

fairness
energy efficiency
- dynamic power management
low latency
high reliability
scalability
adaptability

Routing Protocol

Network Organization

Flat：all nodes are “equal”
Hierarchical：different “roles” for different nodes.
Location-based：nodes rely on location information to decide

Route Discovery

Reactive（on-demand routing）：find route only when needed
Proactive：establish routes before they are needed
Hybrid：protocols with reactive and proactive characteristics

Protocol Operation(not manditory)

Negotiation-based：固定路径
Multi-path：多路都可以
QoS-based：最常见的，选最佳路
Query-based：询问再发送
Coherent-based：提前处理数据

Routing metrics

Dijsktra’s algorithm

Flooding and Gossiping

Flooding

是一种所有人都复读机的情况。
优点：
- simplicity
- guaranteed
缺点：
- heavy traffic
实际使用时有限制：传播次数上限（maximum hop counts）；每人特殊标记（sequence numbers）
存在的问题：一个点复读两次同一个信息（Implosion：A node’s neighbors continue to rebroadcast a packet to the node even when it already has a copy）；不同节点信息内容冗余（Overlap：Senor data contains redundant information）；浪费资源（Resource blindness：Resource constraints are ignored）

Gossiping

是通过每人以一定概率不复读来解决Flooding的一些问题
存在的限制
- 只能解决Implosion
- 还需要确定参数p

Proactive Routing（table-driven routing）

DSDV（Destination-Sequenced Distance Vector）

每个点存：所有去向、最近节点、总路程、sequence number
添加节点和减少节点
为了解决减少节点的 looping problem，引入sequence number
解决好路慢问题（fluctuations），保存settling time在stable data里，等够两倍传播时间再更新网络。
Install time？

OLSR（Optimized Link State Routing）

用neighbor sensing，定期发送HELLO更新连接状态
用flooding或MPRs

On-Demand Routing

区别在于，知道要找谁和谁的连接，定向找路径

Ad Hoc On-Demand Distance Vector (AODV):

用 hello 传 RREQ 和 RREP，传一通 RREQ 直到目标节点，目标节点回传 RREP，传回发送节点确立传递信息的节点通道。

特点：

只有在需要时才建立
平时不用存 table
初始化慢

Hierarchical Routing

cluster形式的网络，需要选 head，怎么选head就是个问题

Low-Energy Adaptive Clustering Hierarchy (LEACH)

$\sum_{i=1}^NP_i(t)=k\\ P_i(t)=\begin{cases}\dfrac{k}{N-k*(r\bmod N/k)},&C_i(t)=1;\\0,&C_i(t)=0\end{cases}$

。。。没总结了，老师好像没考

Location-Based Routing

Landmark Routing

找周围一次能到的节点、两次。。。依次类推

1号节点周围2次能到的节点集合，记作LM1(1)

Greedy Perimeter Stateless Routing (GPSR)

找路径的方法，具体咋贪的有以下几种方法

Greedy Forwarding：找离目标节点最近的
Nearest with Forwarding Progress (NFP)：找离自己最近的
Most Forwarding Progress within Radius (MFR)：找方向投影最大的节点
Compass Routing：找与目标方向夹角最小的

Localization

注意：

accuracy和precision的区别：accuracy: 10m；precision: 90%

Ranging Techniques

Time of arrival (ToA)

又叫ToF

有 one-way 和 two-way 两种方法

one-way

A节点传给B节点A节点时钟当前时间，B节点用收到信息的B节点时钟时间 - A传的时间，再除以传播速度

two-way

A传B，B再回传A，俩时间取平均

即使俩始终时间不同步也准

Time Difference of Arrival (TDoA)

传两种信号

$\text{time difference}=\text{dist}/v_2-\text{dist}/v_1\\ \text{distance} =\frac{(v_1v_2)}{(v_1-v_2)}\times(t_4-t_2-t_{wait})$

无需时钟同步
t4 和 t2 都在B节点接收到
不用等第二个信号，随即传就行，快
但是需要两种hardware来传两种信号

Received Signal Strength (RSS)

通过信号强度估算距离

$\frac{P_{r}}{P_{t}}=G_{t}G_{r}\frac{\lambda^{2}}{(4\pi)^{2}R^{2}}$

Gt 是 transmitter antenna gain，Gr 是 receiver antenna gain，λ 是 wavelength of transmitted signal。

但实际上，由于多径传播效应、反射、噪声等因素，距离与衰减不是平方关系，而在3到5之间，用n表示

$\alpha=\frac{G_tG_r\lambda^2}{(4\pi)^2}\\ R=\sqrt[n]{\frac{\alpha P_t}{P_r}}$

补充：dB转换W

$dB = 10 log_{10}P$

Range-based localization

前面讲了计算距离，现在通过距离计算xyz坐标

Trilateration

通过(不在同一直线的，已知位置的)三个点，到指定点的三个距离，确定一个点

不过由于误差，三个圆可能无法相较于一个点，因此要估算

$\left.A=\left[\begin{array}{cc}2(x_n-x_1)&2(y_n-y_1)\\2(x_n-x_2)&2(y_n-y_2)\\\vdots&\vdots\\2(x_n-x_{n-1})&2(y_n-y_{n-1})\end{array}\right.\right]\\b=\left[\begin{array}{cc}r_1^2-r_n^2-x_1^2-y_1^2+x_n^2+y_n^2\\r_2^2-r_n^2-x_2^2-y_2^2+x_n^2+y_n^2\\\vdots\\r_{n-1}^2-r_n^2-x_{n-1}^2-y_{n-1}^2+x_n^2+y_n^2\end{array}\right]\\ x=\text{arg min}\|b-A\mathbf{x}\|^2\\ x=(A^TA)^{-1}A^Tb.$

后面又讲了啥没看懂

Triangulation（AoA）

用两个角度，确定一个点

GPS-based localization

Fully operational global navigation satellite system (GNSS)
Has three main competitors: Galileo, Beidou, GLONASS

Range-free localization

Ad Hoc Positioning System (APS)

计算单位节点距离，即 correction factor，来估算

For example, sensor node S uses the correction factor obtained from A2 , that is, 18.6, to estimate its distances to the three anchors by multiplying the correction factor with the hop counts (leading to distances 3 × 18.6 to A1 , 2 × 18.6 to A2 , and 3 × 18.6 to A3 ). Given these distances, trilateration is used to determine the location.

Approximate Point in Triangulation (APIT)

选三个已知点画三角形，判断所求点是否在三角形内，逐步缩小范围

通过“if there exists a direction such that a point adjacent to M is either further or closer to all points simultaneously”判断是否在三角形内

Event-driven localization

Lighthouse Approach

旋转光传感器，扫描灯塔，已知灯塔间距b

$d=\frac b{2\sin(\alpha/2)}\\ \alpha=2\pi\frac{t_{\mathrm{beam}}}{t_{\mathrm{turn}}}$

Multi-sequence Positioning (MSP)

Time Synchronization

C(t) : 时钟的时间
t: 现实时间

参数	概念	公式	描述
clock offset	两个时钟的时间差（偏置）		difference between the local times of two nodes
clock rate	斜率	dC(t)/dt	frequency at which a clock progresses
clock skew	俩时钟的斜率差	\	dC1(t)/dt - dC2(t)/dt\	difference in frequencies
clock drift	与现实时间1的斜率差	dC(t)/dt-1	difference between the ideal clock rate and the actual clock rate

斜率差会导致两时钟偏差越来越大，因此需要定期同步：让慢的时钟加快

定期时间间隔为：

$\tau_{\mathrm{sync}}\leq\frac\delta{2\rho_{\mathrm{max}}}$

$\delta$ 是允许的最大时钟偏差，$\rho$ 是最大的 drift rate，单位是ppm (part per million)

$1ppm = 1 \times 10^{-6}$

调节方法是改变慢时钟的斜率变快。不能直接跳越时间，因为可能会导致错过触发条件。要保证 piecewise continuous 分段连续。

Types of Time Synchronization

外部同步
内部同步

如果外部同步，则必然内部同步，反之不一定。

Accuracy: maximum offset of a clock with respect to reference clock.
Precision: time resolution of a clock or maximum offset between any two clocks.

Time Synchronization in WSNs

。。。

Basics of Time Synchronization

调整时钟同步的方法是：两个两个同步，最终实现全部同步

One-Way Message Exchange

先根据距离计算传播延迟D，再通过发送时间戳、接收时间，反推offset δ

实际中，通常假设D为0或一个常数，很不精确

Two-Way Message Exchange

A从t1发，B在t2接，B又在t3发，A在t4接

$\text{offset}=\frac{(t_2-t_1)-(t_4-t_3)}{2}$

假设两个方向传播延迟相同
假设时钟偏移在测量中没有变化

Receiver-Receiver Synchronization

一个sender，多个reciever，各个reciever之间同步

Lightweight Tree-Based Synchronization (LTS)

两两串联同步，同步误差会叠加。并联同步，同步误差不叠加。所以用树形。

Centralized multi-hop version of LTS

用breadth first search广度优先搜索生成树
一对同步需要2 messages；n个点同步：2n-2 messages

Distributed multi-hop version of LTS

Power Management

Energy is scarce（稀缺的），因为：

nodes are very small in size
impossible to manually change
renewable energy and self-recharging mechanisms

节能方法包括使用节能协议，以及避免资源浪费，这节主要讲后者，主要包括：

local：只影响本节点浪费。节点可能不需要监听信道，可以停止通信
global：影响其他节点浪费。一个节点尝试与不存在的节点建立通道，使用AODV等方法会导致多个其他节点无意义的转发。影响更大。

所以这节讲的主要就是 DPM（dynamic power management）核心在于两点：

选择电源通断
决定系统工作模式

DPM也包括 local 和 global：

local：降低单个节点的能耗。
1. 关闭不必要的子系统
2. 休眠模式
global：
通过控制网络的睡眠状态，降低整体能耗
分拨睡觉和工作

Synchronous Sleeping Schedule

一组节点同时睡眠，睡觉前通知大家。

问题是同步反而会增加能耗。

Asynchronous Sleeping Schedule

所有人都睡觉，谁想发消息前要发一个 preamble

问题是会增长通信耗时

Dynamic Operation Modes

模式切换会花额外功耗
模式切换会花额外时间

Parameter	Value
Pon	10W
Poff	0W
Pon-off	10W
Poff-on	40W
ton-off	1s
toff-on	2s

Policy	Energy	Avg. Latency
Always on	250J	1s
Reactive greedy	240J	3s
Power-aware	140J	2.5s

多想多做，发篇一作