WSN Crash Course 无线传感器网络速成笔记

2025-12-23 17:56 已完更.

我们将自底向上地介绍 WSN 的 \(4\) 层, 注意对比与计算机网络的 OSI Model (Figure 1) 的差异.

Figure 1: Computer Network OSI Model. WSN 有下面的 \(4\) 层, 但协议和侧重点非常不一样.

1 WSN Fundamentals

1.1 WSN Node Architecture (必考)

• 必备 \(4\) 个模块 (Figure 2):
  • Sensing Unit 传感单元: 比如温度传感器, 还有用来数字化的 ADC.
  • Processing Unit 处理单元: 你可以用一个 STM32 (有 CPU, 有 memory 即可).
  • Transceiver Unit 收发单元: 你可以用一个 wifi 模块 (自带 antenna).
  • Power Unit 电源单元: 电池, 为所有部分供电.
• 下面的模块可选:
  • Location finding system: GPS.
  • Mobilizer: 有时 node 需要移动, 这个用来控制移动, 会消耗大量能量!
  • Power generator: 比如太阳能电池板.

Figure 2: Generic diagram of hardware components of a Sensor

1.2 Fault Tolerance 容错

Fault tolerance: 在部分传感器节点损坏、死机、没电、外界干扰的情况下, 整个无线传感器网络仍然能够继续完成其核心功能的能力.

• 影响因素: 节点密度、网络拓扑、路由协议 (包括能量管理).

Figure 3: 提高容错的方法

2 PHY (Physical Layer) 物理层

物理层负责决定信号具体以什么方式存在以及频率、电压等参数.

• Wireless medium 无线传输介质
  • Radio Frequencies (RF) (使用最多, 本篇只关注这个)
    • \(3 \text{ Hz to } 300\text{ GHz}\)
    • ISM (Industrial, Scientific, and Medical) bands: RF 频段中为工业、科研、医疗保留的频段, 用户可以无需许可证在功率范围内自由使用.
    • Main techs:
      • Narrowband 窄带
      • Spread Spectrum 扩频
      • Ultra-Wideband (UWB) 超宽带
  • Optical
  • Acoustic
  • Magnetic Induction Techniques

2.1 Path Loss and Received Power

• Friis 传输公式: 在自由空间 (no shadowing, no multipath) 中, 设 TX 和 RX 之间距离为 \(d\), TX 发射功率为 \(P_t\), 空间电磁能量经 RX 转换后出现在接收端口的可用功率为 \(P_r\). TX/RX 的方向性增益¹为 \(G_t, G_r\). 波长为 \(\lambda\). 则有: \[ P_r = P_t G_t G_r \left( \frac{\lambda}{4 \pi d} \right)^2. \tag{1}\]
  • 很多时候默认 \(G_t = G_r = 1\) (各向同性天线).
  • \(\lambda\) 和 频率 \(f\) 的关系: \(\boxed{c = \lambda f}\).
  • “Minimum received power requirement is \(-60\) dBm” 中 dBm 是以 \(1 \text{ mW}\) 为基准的功率单位, 设 \(P \text{ mW} = x \text{ dBm}\), 则: \[\boxed{x = 10 \log_{10} \frac{P}{1 \text{ mW}}}\]

¹ \(G_t(\theta, \phi)\) 定义为该方向的辐射功率密度 除以 同功率各向同性天线的功率密度.

EXAMPLE: 套 Friis 传输公式

Question

Solution

Assumptions: Free space, isotropic antennas (\(G_t = G_r = 1\)).

Given: - \(P_r = -60 \text{ dBm} = 10^{-6} \text{ mW}\) - \(d = 100 \text{ m}\) - \(\lambda = c / f = (3 \times 10^8) / (3 \times 10^9) = 0.1 \text{ m}\)

From Equation 1, we have:

\[ P_t = P_r \cdot \left( \frac{4 \pi d}{\lambda} \right)^2 = 10^{-6} \cdot \left( \frac{4 \pi \times 100}{0.1} \right)^2 = 157.9 \text{ mW}. \]

2.2 Spread Spectrum 扩频

• DSSS 直接序列扩频 (Direct Sequence Spread Spectrum)
  • DSSS 通过将原始二进制信息 (Baseband) 异或上一串快速变化的 PN chip (见 Figure 4) 来提高基带带宽 (因为时域变化更快, 频域带宽会更宽).
    • PN chip 比特率高于原始信号比特率!
  • PN chip (Pseudo-Noise chip) sequence 伪随机码片, TX/RX 会产生相同的 PN 序列来进行扩频和解扩.
    • 只有知道 PN 序列的 RX 才能正确解扩.

  

  Figure 4: DSSS 示意图 (中间调制的过程忽略了) [1]

Modulation in brief

Figure 5: 注意区分数字调制和模拟调制 [2], 另外 Digital carrier 我们之前接触地很少.

• FHSS 频率跳变扩频 (Frequency Hopping Spread Spectrum)
  • 通过在多个频率间跳变来实现扩频. 跳变的频率中心由 PN chip 控制 (不再是异或了).
    • PN chip 的符号率与原始信息的符号率的大小不一定谁大, 若 PN chip 变化很慢, 称为 Slow FHSS (Figure 6), 反之为 Fast FHSS (Figure 7).
    • Chip duration: Figure 6 中的 \(T_c\).
    • Fast FHSS 的抗干扰能力更强! 因为一般 jamming 都是窄带 (攻击起来省能量哈哈), 只要击中一个调制 symbol 的中心频率, 那么这个 symbol 就会被破坏掉. 而 Fast FHSS 在一个调制 symbol 内会跳变多个频率, 破坏它需要跳好几次频率, 而且跳的还要跟 PN chip 跳的一样, 因此被击中的概率更低.
  • FHSS 之后可以 FSK 也可以 ASK 调制 (调制分类见 Figure 5)!
  • 以 Figure 6 为例, 若 FHSS 与 FSK 结合, 则设计两个重要参数 \(M, k\):
    • \(M = 4\): FSK 符号数量. 每次 FSK 以 \(f_c\) 为中心有 \(4\) 个偏移的频率 (即 \(4\) 个 symbol, 每个承载 \(2\) bit 信息).
    • \(k = 2\): PN 分组长度, 代表有 \(4\) 个不同的 \(f_c\).
    • 注意区分用于跳频的中心频率 \(f_c\) 和用来调制的偏移频率!

Figure 6: Slow FHSS

Figure 7: Fast FHSS

2.3 UWB (Ultra-Wideband) 超宽带

• Motivation: UWB 采用完全不同的路线, 它不用载波, 直接在时间轴上发送非常短的脉冲 (ns 级别), 自然地由 Fourier 变换知, 这种短脉冲在频域上会有非常宽的带宽! 由于无需维持稳定的高频载波, UWB 传输功耗非常低.
  • 但是 UWB 的传输距离 \(<10 \text{ m}\).

3 Data Link Layer 数据链路层

3.1 LLC (Logical Link Control) 逻辑链路控制子层

LLC 提供统一接口给网络层.

• Frame management 帧管理
  • Byte Count 字节计数: 在帧头部存储帧的字节数.
    • 问题: 若字节数出错, 则会 out of sync.
  • Flag Bytes + Byte Stuffing 标志字节 + 转义符: 为了解决 frame 之间的同步 (分割) 问题, 在每个 frame 的头尾添加特殊的 flag byte (如 0b01111110). 若这个 flag byte 出现在 frame 内部, 则在它前面添加一个转义符 (ESC, escape byte). 若 ESC 本身出现在 frame 内部, 则也在它前面添加一个 ESC.

3.2 MAC (Medium Access Control) 介质访问控制子层

MAC 子层非常接近物理层, 控制物理层什么时候发、发多久.

• Broadcast channel 广播信道 (Multiaccess channel / random access channel)
  • 在一个广播信道上, 同一时间、同一频段、同一空间接收点只能有一个节点发送数据, 否则会发生碰撞 (collision).
• MAC Protocol: 用来控制物理层什么时候发、发多久的协议.
  • Contention-free 非竞争型
    • Static channel allocation 静态信道分配:
      • FDMA (每个人固定分配一个频段).
      • TDMA (每个人固定分配一个时间片).
      • CDMA (每个人固定分配一个信号空间的方向).
    • Dynamic channel allocation 动态信道分配:
      • Polling 轮询.
      • Token Passing 令牌传递.
      • Reservation 预约.
  • Contention-based 竞争型
    • ALOHA (见 Figure 9 和 Figure 10)
      • Pure ALOHA: 随时 (async) 想发就发, 撞了重来.
      • Slotted ALOHA: 时间分成一个个时隙 (sync), 只能在时隙开始时发, 撞了重来.
        • Question:「\(10\%\) of the slots are idle」, \(G\) 是多少? (见例题 Figure 13)!
    • CSMA (Carrier Sense Multiple Access) 载波监听多路访问: 先听一听, 没人说话再发.
      • CSMA/CD (Collision Detection, 一般用于有线网络): 有线网信号衰减慢, 有人说话大家听得很清楚. 所以先听, 没人再发; 发的同时继续听, 撞了立即停, 并且发 jamming signal 通知其它节点现在发会撞; 等一个随机时间 (会这个随机时间的范围会随着碰撞次数的增加指数增加, 但是不会一直增加) 后重发.
      • CSMA/CA (Collision Avoidance, 一般用于无线网络 WLAN): 无线网中别人发的信号衰减很快, 远的话几乎区分不了信号和噪声. 也是先听, 感觉没人后不急着发, 等一个随机时间再发 (backoff 退避), 发的过程中就听不了了 (因为自己的声音太大). 如果在规定时间内收到 ACK 则成功, 否则推断发生了冲突, 重发.
        • 现实情况是上面的方案处理 Hidden node problem 隐藏站问题 和 Exposed node problem 暴露站问题 (Figure 8) 的效率很低. 我们在 CSMA/CA 中加入一个可选协议:
        • RTS/CTS + NAV (Network allocation vector): 在正式发送数据前, 先发 Request to Send 请求发送, 对方收到后广播一个 Clear to Send 确认可以发送的信号, 这两个信号中都带有从现在开始到这次通信完成所需的时间长度, 收到 RTS 或 CTS 的节点会将这个时间段内的信道标记为忙 (更新 NAV), 避免在这段时间内发送数据造成冲突 (Figure 12). 这样做并不会解决隐蔽站问题, 但能大大降低冲突概率.
    • MACA (Multiple Access with Collision Avoidance) 多路访问与碰撞避免: 先举手再说话.
    • MACAW (MACA with ACK) 带确认的多路访问与碰撞避免: 先举手再说话, 说完还要等确认 (MACA 的改进版).

Figure 8: (a) Hidden node problem 隐蔽站问题: Node \(A,B,C\) 的信号覆盖范围如图所示, \(A\) 和 \(C\) 都想跟 \(B\) 交流, 它们各自感觉信道空闲的时候都先退避再发, 但是有一定概率同时对吧? 如果发出来的信息同时到 \(B\) 就产生干扰. 虽然 backoff 的策略多重发几次也许就不同时了, 但是这样效率很低. (b) Exposed node problem 暴露站问题: \(B\) 想和 \(A\) 交流, \(C\) 想和 \(D\) 交流, 但是 \(C\) 在做监听信道的时候发现 \(B\) 正在发送, 所以给 \(D\) 的信息一直发不出去 (实际上可以发, 没有任何问题) [3].

Figure 9: 两种 ALOHA 对比, 红框代表这些包都作废 [4].

Figure 10: \(G\) 就是 Poisson 分布里的 \(\lambda\) (即单位时间 (一般用 frame time 作单位, 即平均一个包被天线发出去的时间) 平均下来会发出多少个包); \(S\) 为平均意义下单位时间成功发出的包数量. 可见同步的吞吐量更高!

Figure 11: RTS/CTS 简单示意 [5]

Figure 12: RTS/CTS 如何与 NAV 协同工作 [6]

EXAMPLE: Slotted ALOHA 由空闲概率算 \(G\)

Figure 13: Question

Solution

结合 Poisson 分布: \[ \boxed{\mathbb{P}(k) = \frac{G^k e^{-G}}{k!}} \tag{2}\]

idle 的概率即 \(k=0\) 的概率: \[ \mathbb{P}(0) = e^{-G} = 10\% \]

由此将 \(G\) 算出来即可.

4 Network Layer 网络层

• 与计算机网络的网络层区别: (相同点都是路由, 即每个节点收到的数据发给谁?)
  • 计算机网络: Address-centric, 每个节点都有唯一的地址 (IP), end-to-end 传输.
  • WSN (后面的子章节会详细介绍各种协议):
    • Data-centric: 节点没有唯一地址, 传输基于包的内容 (payload, 一般会有标注内容的 attribute, 比如「这个包描述温度信息」,「给我多一些温度数据」这种), hop-by-hop 传输.
      • Advantages: 无需管理大量节点地址, 而且可以在中间节点进行数据聚合 (data aggregation), 节省能量和带宽.
      • Drawbacks: Interest flooding 比较消耗能量, 流量不均衡 (sink 附近节点流量大, 容易没电, 这是因为在 Data-centric 中, 各个节点都是等地位的 (flat), 这个问题在下面 Hierarchical Routing 会缓解).
    • Hierarchical routing: 不要再让全部的节点地位一样了, 分成 普通节点 + 少数 Cluster Head (CH) 节点.
      • Advantages: 由于只有少数节点需要直接跟 sink 通信, scalability 更好、能量消耗更少.
      • Drawbacks: 由于 CH 承担很大的通信责任, 一旦坏掉影响很多节点的通信, robustness 更低; 由于 CH 默认要和 sink 直接通信, 网络面积不能太大.
    • Geographic routing: 直接用节点的 GPS 位置来辅助路由.
      • Advantages: 无需路由表, scalability 非常好, 网络的面积可以很大.
      • Drawbacks: 依赖定位精度, GPS 增加额外能耗.
    • QoS-based routing (Quality of Service): 几乎只考虑服务质量 (比如延迟), 能量消耗考虑很少 (比如火灾报警、医疗传感).

Figure 14: Hierarchical routing 中节点的地位是不同的

• Routing metrics 路由指标 (见 Figure 16)
  • (Min) Number of hops 跳数: 指中继节点 (relay node) 的个数 (不算 source 和 sink).
  • (Min) Energy consumption (per packet) 能量消耗: 每条链路上的能量消耗加起来即可.
  • (Max) Average energy capacity 平均能量容量: relay node 上剩余能量的平均值.
  • (Max) Minimum energy capacity 最小能量容量: relay node 上剩余能量的最小值 (要尽可能大).
  • (Min) Latency 延迟: 每条链路上的延迟加起来即可.
  • (Max) Time to network partition 网络分裂时间: 由于 WSN 中节点由电池供电, 当确定一种路由算法时, 节点上的数值 (电量) 会逐渐消耗, 直到网络中存在两个节点无法通信 (网络分裂). 网络分裂时间越长越好.

EXAMPLE: 找路径题目

Figure 15: 这种找路径的题目就是纯**, 暴力枚举即可

Figure 16: Solution to Figure 15

4.1 Data-centric Routing

• Flooding 洪泛: 每个节点收到包后直接无脑 (blindness) 发给所有的邻居 (广播), 这样几乎可以保证所有的节点都能收到包, 但是这样重复 (overlap) 的数据包会来回发, 大量能量和带宽 (implosion)! 于是自然地:

• Gossiping: 每个节点收到包后, 随机选择一个或几个邻居发包 (而不是全部的邻居). 这样缓解了 implosion, 但是由于随机选择, 网络延迟 (latency) 会变大.

• SPIN (Sensor Protocol for Information via Negotiation): 一系列有握手的协议, 都是基于 SPIN-PP 改良的:

  • SPIN-PP (point-to-point): 节点发之前先广播一个小的即将要发的数据的描述 (ADV (advertisement)), 周围感兴趣的节点则回复一个 REQ (request), 然后对这些节点单播 DATA.
    • SPIN-EC (energy conservation): 在 SPIN-PP 的基础上, 低电量节点不参与握手和数据传输.
    • SPIN-BC (broadcast): 仅仅是把 SPIN-PP 中的单播换成了广播, 节省了能量. 这是因为在无线 WSN 中, 有时很多遍单播的能量比广播一次的能量更大.
    • SPIN-RL (reliable): 在 SPIN-PP 的基础上 (依然是单播哦), 在 DATA 加入了 sequence number, 接收节点收到 DATA 后发 ACK 确认 (如果一段时间内没收到 ACK 则重传).

• Directed Diffusion (DD): 由于 WSN 中节点产生的数据几乎都是要发给 sink 的, 我们先让 sink 广播一个 Interest 消息 (Figure 17 (a)), 这样得到了从 sink 到每个节点的反向路径, 如果要反过来发的话直接将每个箭头反过来即可. 具体来说分为 \(4\) 个步骤:

  • Interest propagation: sink 广播 Interest 消息 (比如「我要 A 区域的大于 \(100^\circ\text{C}\) 的传感信息」), 网络中的节点收到后缓存消息、记录这个 Interest 时从哪个邻居来的 (这样就建立了反向路径), 然后发给剩余的邻居 (其实就是 flooding).
  • Gradient setup: 梯度就是「如果你有这类数据, 该往哪里送」的查找表 (可能是多值的).
  • Reinforcement: 由 sink 发出来选择性地发给节点来强化这些路径 (可能是延迟更小、节点有充足能量的路径), 让以后的数据包尽可能走这些路径.
  • Data delivery.

Figure 17: DD 分为 \(4\) 个步骤 [7].

4.2 Hierarchical Routing

• LEACH (Low-Energy Adaptive Clustering Hierarchy): 主要是每个 cluster 的 head 节点 (CH) 的选取是通过随机的方式动态调整的. 这个协议分为以下几个步骤:

  • Advertisement: 竞选的时候每个节点都有一定概率成为 CH, 如果成为 CH 则向周围广播自己是 CH.
  • Cluster setup: 周围节点可能收到很多个不同 CH 的 advertisement, 它会选择依附信号最强的那个, 这样就形成了很多个 cluster.
  • Schedule creation: 每个 CH 给自己 cluster 中的 node 分配应该什么时候给自己汇报 (如果用 TDMA 的话就是分配时间片).
  • Steady state: cluster 中的节点开始按照 schedule 给 CH 汇报数据 (而不会盲目发, 显著减少能量开销和碰撞), CH 做 aggregation 后直接发给 sink (注意由于 CH 需要直接跟 sink 通信, 而 CH 是随机选的, 这就要求所有节点必须能与 sink 直接通信)

• PEGASIS (Power-Efficient GAthering in Sensor Information Systems)

• TEEN (Threshold-sensitive Energy-Efficient sensor Network)

• APTEEN (AdaPtive TEEN)

5 Transport Layer 传输层

• 与计算机网络的传输层区别:
  • 计算机网络: Transport 层 \(\approx\) TCP/UDP, 侧重从 source 到 destination 的可靠传输 (保证没有丢包)、包的顺序要对.
  • WSN: 考虑由 \(1000\) 个温度传感器组成的网络, 一般只关心数据有没有到中心 (sink) 而不是端到端, 不需要每丢一个包就重传 (不需要 TCP 那么可靠, 当然也看具体场景, 比如 RMST 就要求可靠), 这样会让本来就没多少电的节点耗能爆炸. 每个节点甚至都没有唯一的 ID (计算机网络中的 IP). WSN 的 Transport 层针对不同的应用场景设计了下面很多不同的协议!
• RMST (Reliable Multi-Segment Transport)
  • 目标: 如何以尽量低的能耗, 把Multi-segment数据 (指一整块数据, 但是是被分成多个 segment) 可靠 (所有 segment 都要送到) 地传到 sink?
  • RMST 默认网络层 (Section 4) 用 DD 路由算法
  • 可靠传输机制: 由 NACK 信号保证 (用 ACK 就要发大量的包, 占用大量带宽).
  • 工作模式 (见 Figure 18 和 Figure 19):
    • Non-caching: 节点都没有缓存, 并且丢失的包必须由源节点重传, 易造成网络拥塞和丢包 (这个协议几乎不实用, 一般只是作对照用的).
    • Caching: 一部分中间节点有缓存 (cache node), 这样可以缓解网络拥塞, 但是内存读写会增加能耗开销.

Figure 18: Non-caching RMST 丢失的包必须由源节点重传.

Figure 19: Caching RMST 丢失的包可以由 cache node 重传.

• PSFQ (Pump Slowly, Fetch Quickly)
  • 目标: 信息传递方向跟 RMST 相反, 由 sink 向所有节点广播信息 (比如代码、配置参数等下发), 尽量不要造成拥塞.
  • 工作机制: sink 以较慢的速率注入数据包 (比如每隔 \(T_\min = 100 \text{ ms}\) pump 一个 Figure 20), 节点收到数据包后立即向下一个节点转发, 如果不是按顺序收到, 则向上一个节点发送 NACK 快速获取 (fetch) 丢失的数据包 (所以是 hop-by-hop reliability 而不是 end-to-end)
  • 特点:
    • Scales well.
    • Hop-by-hop reliability (end-to-end may not be reliable).
    • 大网络 latency 很高 (由于注入间隔 \(T_\min\) 的存在).
    • 网络边缘的节点 memory 需要较大 (因为包更容易 out-of-order 到, 需要存下后面的包).

Figure 20: PSFQ 的 quick fetch.

• CODA (Congestion Detection and Avoidance)

  • 目标: 跟 RMST 和 PSFQ 不同, CODA 只关注拥塞控制, 不关心每个包是否送达.
  • 工作机制 (简略): 下游节点会向上游节点发送 suppression message 来通知上游节点降低发送速率.

• ESRT (Event-to-Sink Reliable Transport)

  • 目标: ESRT 同时关注 拥塞控制 和 (event)可靠性 (在温度预警 WSN 中也许有很多节点传的都是是否火灾的信息, 不需要每个节点的信息都送到 sink, 只要确保火灾发生时这个 event 能被 sink 收到即可).
  • 工作机制 (简略): 事件发生, 多个节点开始上报, sink 在时间窗 \(\tau\) 内统计 \(r_i\) 然后判断是否满足 \(R\). sink 广播控制指令: “所有节点把速率调到 \(f'\)”. 节点收到后调整速率, 进入下一轮 \(\tau\).
    • Dicision interval \(\tau\): sink 每隔 \(\tau\) 时间根据收到包的数量判断一下可靠性.
    • Desired event reliability \(R\): 在一个决策时间窗 \(\tau\) 内, sink 至少需要收到多少个事件相关的数据包 (要提前给定).
    • Observed event reliability \(r_i\): sink 在第 \(i\) 个决策时间窗 \(\tau_i\) 内实际收到的事件相关的数据包数量.
    • Reporting rate \(f\): 所有节点的平均发送速率.

• GARUDA: pulsing-based, 确保单个包送达. (了解即可)

• (RT)\(^2\) (Real-Time Reliable Transport): 强调实时性和能量最小. (了解即可)

6 Error Control 差错控制

Error control 不单独属于计算机网络 / WSN 的某一层. 在 PHY, Data link, Transport 层都可能会用到差错控制技术.

• 处理差错的方法可以分为 \(4\) 种:
  • Power control: 直接提高发射功率.
  • ARQ (Automatic Repeat reQuest): 发送 packet + checksum, 接收端收到后校验, 正确发 ACK, 错误发 NACK 整包重传. 有这几种具体的协议:
    • Stop-and-wait (SW): 等 ACK 再发下一个, 效率极低.
    • Go-Back-N (GBN) / Sliding Window: 引入发送窗口 (Stop-and-wait 变成了窗口大小为 \(1\) 的 GBN). 接收端丢弃不按序到达的包 (而不是缓存), 有累计确认机制. 如果丢包率高的话重传会很多.
    • Selective Repeat (SR): 改进了 GBN, 接收端缓存不按序到达的包, 所以不能有累计确认机制, 只能单独确认每个包. 重传最少, 但是需要 TX/RX 都有较大的缓存.
  • FEC (Forward Error Correction): 不要依赖重传了, 直接在发送端加入冗余信息 (编码, FEC (channel) codes), 期待接收端能自动纠错.
    • BCH
    • Reed-Solomon codes
    • Convolutional codes
  • HARQ (Hybrid ARQ): ARQ 和 FEC 的结合.

Figure 21: GBN 协议

Figure 22: SR 协议

7 Localization 定位

「温度传感器报告 \(80 ^\circ \text{C}\)」 是没有意义的, 「在 A 区域第 3 号设备旁」 才有意义.

7.1 Range-based 依赖距离测量

• Ranging techniques 测距技术
  • RSS (Received Signal Strength) 接收信号强度: 在已知 path-loss model 的情况下, 可通过比较接收信号强度与发射信号强度来估计距离. 如果不是 LoS (对着发), 误差会很大.
  • ToA (Time of Arrival) 到达时间: 利用初中物理 路程 = 光速 × 时间, 知道时间即可算出距离.
    • One-way ToA: 需要 TX 和 RX sync (Figure 23 (a)), 由于光速太快, 需要极高精度的时钟同步!
    • Two-way ToA: 不需要 sync! 但要知道 RX 端的处理时间 (processing delay \(t_3-t_2\) in Figure 23 (b)).
  • TDoA (Time Difference of Arrival) 到达时间差: 不需要 sync! 如 Figure 23 (c), \(t_1\) 发 RF, \(t_3\) 发 sound, 则距离 \[d = (v_1-v_2) \cdot ((t_4-t_2) - (t_3-t_1))\]

  

  Figure 23: (a) One-way ToA; (b) Two-way ToA; (c) TDoA [8]

  • AoA (Angle of Arrival) 到达角度: 单看角度当然不能知道距离, 需要多个节点测量同一个 TX 的 AoA 来三角定位 (Triangulation). 计算相对复杂.
• Range-based protocols
  • Triangulation 三角测量: 见 Figure 24, 两个 anchor node \(A, B\) 相对位置已知, 再测量两个角度即可.
  • Trilateration 三边测量: 见 Figure 25, 三个球相交于一点. GPS 的工作原理 (只不过 GPS 需要 \(4\) 个卫星来同时解出时间偏移).
    • Iterative multilateration 迭代多边测量: 在一个 WSN 系统中, 先用人工或 GPS 确定少量几个 anchor node 相对位置, 然后用 Trilateration 算出其他 node 位置, 这些 node 就变成新的 anchor node … (这种方法会有 Error propagation 问题, 但仍在使用).
    • Collaborative multilateration 协同多边测量: 一个 node 附近不一定会有 \(3\) 个 anchor node, 所有 node 都可以用 Trilateration 开始测量周围的 node 位置, 然后用一些复杂的优化算法来算出所有 node 位置 (更准确).

Figure 24: Triangulation

Figure 25: Trilateration

7.2 Range-free 不依赖距离测量

7.3 Localization style

• Periodic: 周期性地对所有节点进行定位.

• Event-driven: 只有当某个感知事件发生时, 相关节点才触发定位过程.

8 Synchronization 同步

节点 \(A,B\) 的时钟是同步的意思是: 在非狭义相对论的范围内,「12:20」这个时间戳对于 \(A,B\) 节点没有歧义.

• 一些概念:
  • Clock offset: 路程差.「快了 20 s」
  • Clock rate: 速率. 1 s 内这个时钟实际只走了 0.9 s (clock rate = 0.9).
    • Clock skew: 速率差. 两个时钟的 Clock rates difference.
  • Drift rate: 加速度. 一个时钟时快时慢的程度.
• Challenges:
  • Environmental effects: 天太冷影响同步.
  • Energy constraints: 电池没电钟走慢了.
  • Wireless medium and mobility: ACK 信号丢包了.
• Sync methods 同步方法
  • One-way sync 单向同步: Node \(A\) 将发送时刻的时间戳 \(t_1\) 附加在消息中发送给 Node \(B\), 传播时间 \(D\) 很小 (一般忽略或设为常数), \(B\) 在 \(t_2\) 收到. 如果 \(t_2\) 和 \(t_1 + D\) 有差异, 则这个差异就是 clock offset \(\delta\).
  • Two-way sync 双向同步
  • Receiver-receiver sync

9 Security in WSNs

• CIA Model
  • Components:
    • Confidentiality 机密性: 不该看到的人, 看不到数据.
    • Integrity 完整性: 数据在传输过程中不被篡改.
    • Availability 可用性: 正常工作的概率.
  • 在不同的场景中, 这三者的重要性不同.
    • 火灾检测: IA > C
    • 机场生物识别信息收集: CI > A

10 Queuing Theory 排队论

Bernoulli, Poisson, Exponential, Binomial, Geometric, Negative Binomial 分布关系

见 这篇文章, but in brief:

• 连续时间 Bernoulli 过程 \(\iff\) 单位时间到达人数 \(\sim \operatorname{Pois} (\lambda) \iff\) 相邻两次到达时间间隔 \(\sim \operatorname{Exp} (\lambda)\).

• 离散时间 Bernoulli 过程 \(\iff\) 单位时间到达人数 \(\sim B(n,p) \iff\) 相邻两次到达时间间隔 \(\sim G(p)\).

  • 几何分布是负二项分布的特殊情况: \(G(p) \iff NB(1, p)\).

10.1 Kendall’s Notation

\[ A/S/C/K/N/D \]

• \(A\): Arrival model 到达模型, 可选:

  • \(M\): Memoryless (Poisson process).
  • \(E_k\): Erlang distribution (Sum of k i.i.d. exponential R.V.).
  • \(G\): General distribution.

• \(S\): Service model 服务模型, 可选同上.

• \(C\): Number of parallel servers 并行服务器数量 (\(\neq\) number of queues).

• \(K\): Capacity of system 系统容量 (maximum number of people allowed in the system, not queue), 可选:

  • Finite.
  • Infinite (\(\infty\)).

• \(N\): Capacity of calling population (队里的人从哪里来的, 如果是有限的则会影响 arrival rate), 可选同上.

• \(D\): Service discipline 服务方式, 可选:

  • FIFO/FCFS: First In (Come), First Out (Serve).
  • LIFO/LCFS: Last In (Come), First Out (Serve).
  • SIRO: Serve In Random Order.
  • PQ: Priority Queueing.

10.2 Examples

Figure 26: \(M / M / 1 / 7 / \infty / \text{FIFO}\) Queue

Figure 27: \(M / M / 3 / 8 / \infty / \text{FIFO}\) Queue

10.3 Notation of Parameters

• cust.: customer.
• \(\lambda\): Mean arrival rate, 平均来看单位时间会到多少人, \(\mathbb{E} (\# \text{cust. arrived})\) per unit time.
• \(\mu\): Mean service rate, 平均来看单位时间能服务多少人, \(\mathbb{E} (\# \text{cust. served})\) per unit time.
• \(\rho := \lambda / (C \mu)\): Utilization factor / Traffic intensity.
• \(n\): \(\# \text{cust.}\) in the:
  • system: \(n_s\).
  • queue: \(n_q\).
• \(\mathbb{P}_n(t)\): Probability of having \(n\) customers in the system at time \(t\).
  • Write \(\pi_n \equiv \mathbb{P}_n (\infty)\), 平稳后 system 中有 \(n\) 个 cust. 的概率.
• \(W\): \(\mathbb{E}(\text{waiting time})\) per cust. in the:
  • system: \(W_s\), 平均来看每人在系统里待了多久 (计算结果见 Equation 4).
  • queue: \(W_q\), 平均来看每人在队列里待了多久 (计算结果见 Equation 4).
• \(L\): \(\mathbb{E}(\# \text{cust.})\) in the:
  • system²: \(L_s\), 平均来看系统中有多少人 (计算结果见 Equation 3).
  • queue: \(L_q\), 平均来看队列中有多少人 (计算结果见 Equation 4).

² 试卷中这个概念被错误地称为 “Queue length”! 应叫 “System length”.

10.4 \(M / M / 1 / \infty / \infty / \text{FIFO}\) Queue 生灭过程

cust. 到达和离开可以代表生命的诞生和死亡, 因此这种排队过程也叫生灭过程 (birth-death process).

10.4.1 系统中的稳态人数为几何分布

这是一切生灭过程结论的起点!

Geometric Distribution

Theorem 1 平稳后 system (not queue!) 中的人数 \(\pi\) 满足几何分布³: \[\pi+1 \sim G(1-\rho).\]

³ 加一的原因是: 几何分布从 \(1\) 开始, 而 \(\pi\) 的取值从 \(0\) 开始.

Figure 28: 移动到原点的 \(G(p)\) 的 p.m.f. 随 \(p\) 的变化 [9].

• Theorem 1 肯定不显然, 需要离散化然后取极限再让时间 \(t \to \infty\) 来证明 (就像 Poisson 分布的推到一样), omitted here.

• 并且这是一个全局稳定解, 即最终 system 中的分布与队中的初始人数无关!! (可理解为 \(\begin{bmatrix} \pi_0 \\ \pi_1 \\ \pi_2 \\ \vdots \end{bmatrix}\) 为无穷维相空间中的稳定吸引子).

系统中的平均人数

Corollary 1 由 Theorem 1 和 Geometric Distribution 的性质可知: \[\boxed{L_s = \frac{\rho}{1-\rho}} \tag{3}\]

10.4.2 Expectation Space (ES)

这是生灭过程剩余所有结论的直接诱导思想!

• ES 基本思想和局限性:
  • 对于任何随机过程, 很多时候可以将随机性忽略, 让考虑所有量都按照期望稳定存在的 mental picture. 由于没有找到已知的合适的名词, 我们姑且将此称为 Expectation Space 吧.
  • Advantage: ES 可以让很多结论变得显然.
  • Limitation: 对于生灭过程, 若 \(\lambda < \mu\), 若想象成水按速率 \(\lambda\) 流入管道, 流出速率最大值可达 \(\mu\), 则管道里永远也不会留下水, 而后面我们会知道实际上管道里平均来说会留下 \(L_s = \rho / (1-\rho)\) 的水量. 这是因为 cust. 到达和离开是随机的, 有可能一小段时间内有很多 cust. 到达而处理时间又比较长, 这样管道里就会积累一些水.

生灭过程的 Expectation Space 结论

Theorem 2 由 Figure 29:

Figure 29: 生灭过程的 ES.

结合 Corollary 1 显然有:

\[ \begin{aligned} L_s = \lambda W_s &\implies \boxed{W_s = \frac{L_s}{\lambda} = \frac{1}{\mu-\lambda}} \\ W_s - W_q = \frac{1}{\mu} &\implies \boxed{W_q = W_s - \frac{1}{\mu} = \frac{\rho}{\mu - \lambda}} \\ L_q = \lambda W_q &\implies \boxed{L_q = \frac{\rho^2}{1-\rho}}. \end{aligned} \tag{4}\]

10.4.3 其它结论

• Delay bound: 在 steady state 下, 一个随机到达的顾客, 其在 system 中的逗留时间 \(W_s\) 的 c.d.f., \[\mathbb{P}(W_s \leq t) = 1 - e^{-(\mu - \lambda) t}.\]

10.5 \(M / M / 1 / K / \infty / \text{FIFO}\) Queue 有限长队列

我们在这里忽略这种队列的所有推导.

• 稳态系统平均人数 \(L_s\): \[L_s = \frac{1-\rho}{1-\rho^{K+1}} \sum_{j=1}^K j \rho^j.\]

• Blocking probability \(\mathbb{P}_B\): 一旦系统中有 \(K\) 个人了, 新到达的顾客就会被拒绝 (blocked), steady state 下这个概率为: \[\mathbb{P}_B = \frac{1-\rho}{1-\rho^{K+1}} \rho^K.\]

• Carried traffic \(\gamma\): 由于有 blocking, 实际被服务的流量 (carried traffic) 会小于 \(\lambda\): \[\gamma = \lambda (1 - \mathbb{P}_B).\]

References

[1]

A. Hira, N. Sakib, N. Sarker, Md. N. Mollah, S. Mohamed, and M. Rashid, “A novel approach to signal encryption: Improved version of conventional direct sequence spread spectrum scheme,” Advanced Science Letters, vol. 20, Oct. 2014, doi: 10.1166/asl.2014.5684

[2]

W. Contributors, “Signal modulation.” Wikipedia; Wikimedia Foundation, Mar. 2025. Available: https://en.wikipedia.org/wiki/Signal_modulation. [Accessed: Dec. 19, 2025]

[3]

S.-L. Wu, Y.-C. Tseng, and J.-P. Sheu, “Intelligent medium access for mobile ad hoc networks with busy tones and power control,” Selected Areas in Communications, IEEE Journal on, vol. 18, pp. 1647–1657, Oct. 2000, doi: 10.1109/49.872953

[4]

H. Ahn, “Slotted ALOHA protocol.” Hongseo Ahn’s Blog, Apr. 2015. Available: https://honser.github.io/project/2015/04/26/Slotted-ALOHA-Protocol/. [Accessed: Dec. 22, 2025]

[5]

C. Nguyen, A. Mokraoui, P. Duhamel, and L. Nguyen, “Improved time and frequency synchronization algorithm for 802.11aWireless standard based on the SIGNAL field,” REV Journal on Electronics and Communications, vol. 3, Jun. 2013, doi: 10.21553/rev-jec.53

[6]

J. Cho, E. Shitiri, and H.-S. Cho, “Network allocation vector (NAV) optimization for underwater handshaking-based protocols,” Sensors, vol. 17, no. 1, 2017, doi: 10.3390/s17010032. Available: https://www.mdpi.com/1424-8220/17/1/32

[7]

H. Lu, “A novel routing algorithm for hierarchical wireless sensor networks,” Jan. 2013, doi: 10.6084/M9.FIGSHARE.761940

[8]

C. Gkiokas, “Localization of a mobile node in a wireless sensor network: An evaluation of RSSI as a distance metric,” PhD thesis, 2015.

[9]

“Geometric distribution.” Wikipedia, Mar. 2020. Available: https://en.wikipedia.org/wiki/Geometric_distribution. [Accessed: Dec. 22, 2025]