山风笔记集

WSN 无线传感器网络笔记

1 介绍
- 略
2 物理层
- 面临的挑战
  - 有限的带宽
  - 有限的传输范围
  - 信号衰减
  - 多径散射
  - 干扰
- 信源编码
  - 将模拟信号转化为数字信号
- 信道编码
  - 减轻（或消除）噪声和干扰对数字信号传输的影响，增强鲁棒性
    - 检测与校正
    - 前向纠错与重传
    - 冗余编码
  - 提供错误检测以及前向纠错 (FEC) 机制
- 调制
  - 将基带信号转换为带通信号
- 香农公式
  - C = B·log2(S/N)
  - 信噪比 SNR = S/N
  - SNRdb = 10 · log10(SNR)
  - 信干噪比
- 路径损耗
- 遮蔽
- 多径衰落
3 MAC协议
- 多用户环境下介质访问控制技术
- 信道访问控制方式
  - 基于分配
    - 固定信道分配
      - FDMA 频分多址接入
        Frequency
      - TDMA 时分多址接入
        Time
      - CDMA 码分多址接入
        Code
    - 动态信道分配
      - 轮询
      - 令牌环
  - 基于竞争
    - ALOHA
      - 随机等待时间
    - CSMA 载波监听多路访问
      Carrier Sense Multiple Access
      - CSMA/CA 碰撞避免
        CA - Collsion Avoidance
        IEEE 802.11 MAC 很常用
        
        选择Wmax
      - CSMA/CD 冲突检测
        Collision Detection
- 隐藏终端（可以解决）
  - 由于监听到的信道空闲而不是真的空闲，故引发冲突
  - 解决方法：进行一次握手（RTS、CTS）
- 暴露终端（解决不了）
  - 由于监听到的信道忙而不是真的忙，故其可以传输而不传输
- WSN MAC
  - 基于竞争
    - S-MAC
      周期性侦听/睡眠调度
      - 周期性侦听/睡眠的工作方式（能量）
      - 一致性的睡眠调度机制（空闲侦听）
      - 流量自适应的侦听机制（减少延迟）
      - 消息分割和突发传递（控制消息和消息延迟）
    - T-MAC
      流量自适应的侦听/睡眠调度
      - S-MAC改进
      - RTS→CTS→DATA→ACK
      - 根据通信流量动态调整活动的时间，用突发的方式发送信息，减少空闲侦听的时间
      - 早睡问题
        
        未来发送请求
        
        满缓冲区优先
    - Sift-MAC
      - 原理
        采用CW值固定的窗口
        
        不等概率选择时槽，在不同时槽采用不同选择概率
      - 适用于分簇结构
      - 以簇头一直处于侦听状态换取较低延迟
  - 基于时分复用（TDMA）
    - 缺点
      - 要求严格的时间同步
      - 网络扩展性不好
    - 基于分簇
4 WSN路由协议
是一套将数据从源节点传输到目的机制
- 特点
  - 自组织的网络（随机部署）
  - 数据的冗余性（多节点监测同一事件）
  - 基于局部拓扑信息（硬件限制）
  - 网络功能（数据收集）
  - 以数据为中心
- 平面路由协议
  - DD路由算法 Directed Diffusion
    基于查询的路由
    - 兴趣扩散
      - Sink汇聚节点发送兴趣消息洪泛给其他节点
    - 梯度建立
      - 成本最小化
      - 信息梯度
        包含下一跳节点、时间戳、信息采集相关内容
    - 数据传播
    - 路径加强
    - 优点
      - 数据中心路由，定义不同任务类型/目标区域消息
      - 路径加强机制可显著提高数据传输的速率
      - 周期性路由：能量的均衡消耗
    - 缺点
      - 周期性的洪泛机制: 能量和时间开销都比较大
      - 节点需要维护一个兴趣消息列表，代价较大
  - 能量感知路由
    基于节点的可用能量（PowerAvailable，PA）或传输路径上链路的能量需求选择数据的发送路径
    - 可用能量（Power Available，PA）
    - 目标
      - 均衡消耗节点能量增加网络的生存期，根据节点的可用能量或传输路径上的能量需求，选择数据转发路径
    - 方法
      - 在源和目的之间建立多条路径，根据能量因素给每条路径赋予被选择使用的概率
      - 在发送数据时，基于概率随机选择其中的一条路径
    - 结果
      - 没有一条路径一直在传送数据，防止一条路径上节点能量消耗过快
- 集群结构的路由协议
  网络分层路由
  - LEACH
    - 簇头选择算法
      - 节点随机产生一个0~1的数
      - 数值小于T(n)则称为head簇头（未当选过）
        
        P: 需要的Head的百分比
        
        r: 当前round
        
        n: 节点（n∈G）
        
        G: 没有做过Head的节点集合
      - 每个Head使用CSMA MAC协议通知全体节点，包含自己的ID
      - 节点就近选择Head，通过CSMA发送加入请求，包含自己的ID
      - 使用TDMA（时分复用）调度信息
    - 优点
      - 优化了传输数据所需能量
      - 优化了网络中的数据量
    - 缺点
      - 节点硬件需要支持射频功率自适应调整
      - 无法保证簇头节点能遍及整个网络
- 地理信息路由协议
  - GEAR路由
    - 应用
      - 到特定区域的路由
    - 前提
      - 已知目标区域的位置信息
      - 节点知道自己位置信息和剩余能量
      - 节点间无线链路是对称的
    - 两步路由
      将查询命令传输到查询区域查询区域内传输到所有节点
    - 选路依据 F (N, R) = a · Distance(N, R) + (1 - a) · Left_Energy(N)
    - 传送方式
      - 洪泛（节点较少）
      - 迭代地理转发（节点较多时效果好点）
    - 路由空洞
  - GSPR
- 其他
  - 多路径
5 WSN拓扑控制
- 节点功率控制
  动态调整节点的发送功率，在保证网络拓扑结构连通需求的基础上，降低节点的发送功率，延长整个网络的生存时间。当传感器节点部署在二维或三维空间中，功率控制问题是一个NP难的问题
  - 基于节点度的算法
    节点度:节点单跳邻居节点的个数
    - 本地平均算法 LMA
      - 检查邻居个数，控制在一个范围内
    - 本地邻居平均算法 LMN
      - 相比LMA，将邻居个数放入自己的信息中，然后将所有邻居的邻居数求平均值作为自己的邻居数
      - 即“自己的邻居平均有多少邻居”
  - 基于邻近图的算法
- 睡眠调度
- 层次型拓扑结构
  - LEACH
- 作用
  - 可以延长WSN的生命周期
  - 可有效减弱节点间通信干扰，提高通信效率
  - 为路由协议的实施提供基础数据
  - 可以更好地进行数据融合及有利于提高网络的鲁棒性
6 定位技术
- 计算节点位置
  - 三边测量估计法
    - 已知A、B、C三个节点的坐标，以及它们到节点D的距离
  - 三角测量估计法
    - 已知A、B、C三个节点的坐标、节点D相对于节点A、B、C的角度
    - 转化为三边测量（图中三条虚线长度相等作为圆半径，应用余弦定理）
  - 极大似然估计法
- WSN定位机制
  - 基于距离的定位机制
    - TOA
      已知信号的传播速度，根据信号的传播时间来计算节点间的距离，然后利用三边或者极大似然估计法等计算出节点的位置
    - TDOA
      
      发送节点同时发送两种不同传播速度的无线信号，接收节点根据两种信号到达时间差以及已知这两种信号的传播速度，计算两个节点之间的距离，再通过已有基本的定位算法计算出节点的位置
      - 推导方式
        C1 = Dist / T1
        
        C2 = Dist / T2
        
        1/C2 - 1/C1 = (1/Dist)·(T2 - T1)
        
        Dist = (T2 - T1) · ( C1·C2 / (C1 - C2) )
  - 距离无关的定位机制
    - DV-Hop 距离向量-跳段定位算法
      - 基本思想
        计算未知节点与信标节点的最小跳数
        跳数类似于同心圆传播（数字为跳数）
        
        估计平均每跳的距离
        每个信标节点根据记录的其他信标节点的位置信息和相距跳数，估计平均每跳的实际距离
        
        信标节点将计算的每跳平均距离用带有生存周期字段的分组广播至网络中，未知节点仅仅记录接收到的第一个每跳平均距离，并转发给邻居节点
        
        利用最小跳数乘以平均每跳距离，得到未知节点与信标节点之间的估计距离
        
        利用三边测量法或极大似然估计法计算未知节点的坐标
      - 例子
        
        信标节点L2计算的每跳平均距离为 (40+75) / (2+5)
        
        A从L2获得每跳平均距离（L2离A最近），则节点A与三个信标节点之间的距离分别为
        L1：3*16.42
        
        L2：2*16.42
        
        L3：3*16.42
    - APIT 近似三角形内点测试算法
      Approximate Point-In-Triangulation Test
      - 基本思想
        首先确定多个包含未知节点的三角形区域
        
        这些三角形区域的交集是一个多边形，它确定了更小的包含未知节点的区域
        
        计算这个多边形区域的质心，并将质心作为未知节点的位置
      - 原理 —— PIT原理
        假如存在一个方向，节点M沿着这个方向移动会同时远离或接近顶点A、B、C，那么节点M位于三角形ABC外
        
        否则，节点M位于三角形ABC内
7 时间同步技术
- 按网络应用深度分类
  - 时序确定
    判断事件发生的先后顺序，对本地时间的要求比较低，只需要知道本节点与其余节点的相对时间即可
  - 相对同步
    节点维护自己的本地时钟，周期性地获取其邻居节点与本节点的时钟偏移，实现本节点与邻居节点的时间同步
  - 绝对同步
    所有节点的本地时间严格同步，等同于标准时间，这种情况对节点的要求最高，因此实现也最为复杂
- 按参考时间来源分类
  - 外同步
    标准参考时间来自于外部
  - 内同步
    参考时间来自于网络内部某个节点的时间
- 时间参数
  - 时钟偏移
    本地时间与真实时间的差值
  - 时钟漂移
    本地时间变化速率与1的差值
- 时间计数方式
  - 硬件时钟模式
    利用晶振来实现时间的计数
  - 软件时钟模式
    采用虚拟的软件时钟来实现时钟的计数
- 需要满足的要求
  - 能量有限
  - 可扩展
  - 稳定性
- 技术问题
  - 传播延迟不可预测
    - 发送时间：发送方用于组装并将报文换交给发送方MAC层的时间
    - 访问时间：指在发送方MAC层从获得报文后到获取无线信道发送权的等待时间
    - 传送时间：发送方发送报文的时间，报文的第一个字节开始发送到发送完最后一个字节的时间
    - 传播时间：报文从发送方以电磁波的形式传送到接收方所花费的时间
    - 接收时间：接收方接收报文的时间。它和传送时间完全相同，具有确定性
    - 接受时间：用于处理接收到的报文的时间
  - 高能效
  - 可扩展、健壮
- 同步机制
  - 发送者-接收者同步模式
    发送者发送带有时间戳的同步包给接收者，同步接收者的时间
  - 接收者-接收者同步模式
    多个接收者利用发送者发送的同步包在若干接收者之间进行同步，缩短了关键路径，避免发送者到接收者的关键路径过长而导致的不准确的传输延迟估计
    - RBS 参考广播同步
      Reference Broadcast Synchronization
      - 工作机制
        发送节点周期性地向接收节点发送参考报文
        
        广播域内的接收节点都将收到该参考报文，并各自记录收到该报文的时刻
        
        接收者们通过交换本地时间戳信息，这样这一组节点就可以计算出它们之间的时钟偏差
      - RBS算法中广播的时间同步消息与真实的时间戳信息并无多大关系，它也不关心准确的发送和接收时间，而只关心报文传输的差值，RBS同步算法完全排除了发送时间和接收时间的干扰
  - TPSN 双向报文交换协议
    Timing-sync Protocol for Sensor Networks
    - 层次发现阶段
    - 时间同步阶段
      - 双向报文机制
        
        根据TPSN报文交换协议，我们规定T1和T4为节点A的时间，T2和T3为节点B的时间
        
        节点A在T1向节点B发送一个同步报文
        
        节点B在收到该报文后，记录下接收到该报文的时刻T2，并立刻向节点A发回一个应答报文，将时刻T2和该报文的发送时刻T3嵌入到应答报文中
        
        当节点A收到该应答报文后，记录下此时刻T4
        
        我们假设当节点A在T1时刻，A和B的时间偏移为Δ
        
        因为T1到T4两个报文发送的时间非常短，我们可以认为Δ没有变化
        
        假设报文的传输延迟都是相同且对称的，均为d，那么有
        T2=T1+Δ+d
        
        T4=T3−Δ+d
        
        这两个方程联立可解得
        Δ = [(T2 - T1) - (T4 - T3)] / 2
        
        d = [(T2 - T1) + (T4 - T3)] / 2