Delay Tolerant Networks – DTNs 延迟容忍网络架构

归属
Delay Tolerant Networks – DTNs 延迟容忍网络
- 应用实例
- - 例子 1：瑞典北部的萨米人 (Saami reindeer herders)
  - 例子 2：太平洋中的动物传感网络
DTNs路由方式——存储&转发
DTNs移动模型
- Random walk 随机游走
- - Gauss-Markov Mobility 高斯-马尔可夫移动性
- Random waypoint 随机航点
Epidemic Routing（流行病路由）——DTNs框架下的路由协议
PRoPHET路由协议——DTNs框架下的流行病改进路由协议
- 核心思想
- 概率更新公式
- 📊 与 Epidemic Routing 对比
- PRoPHET 协议 — 传递性 (Transitivity)
- - 概率更新公式
- PRoPHET 协议（以及 DTN 路由）中的“权衡 (Trade-off)”
- - 多复制 vs 少复制
  - 设置阈值 (Threshold) 转发
  - 解决方案
- 具体实例

归属

延迟容忍网络不属于Data-centric / Hierarchical / Geographical / QoS-based这 4 类里的任何一个。

Data-centric / Hierarchical / Geographical / QoS-based 默认网络端到端连通、可以逐跳转发；而 DTN 的前提恰好相反：长时延、间歇性连接，用 store–carry–forward（存-携-转）的“机会式/容断”路由范式。所以它通常被单列为 Delay/Disruption-Tolerant（Opportunistic）路由 一大类。

Delay Tolerant Networks – DTNs 延迟容忍网络

DTN（Delay/Disruption Tolerant Networks，延迟/容断网络）是一类能够在高时延、大误码率、频繁断连、甚至无持续端到端路径的环境下仍然提供数据传输服务的网络体系结构。

核心特征：
采用 store–carry–forward（存储–携带–转发）的路由模式：
当节点之间没有即时可用的链路时，节点会先将消息存储在本地缓存中；
当未来遇到合适的转发机会（例如节点移动到有连接的位置），再将消息转发出去；
通过多次这样的“存–携–转”，最终消息能够到达目的地。

应用实例

DTN – 间歇性连接的 WSN（或自组织网络），其中信息路由延迟是可以容忍的，→存储和转发

例子 1：瑞典北部的萨米人 (Saami reindeer herders)

环境：生活在北极圈附近，地广人稀，通信设施不足。
做法：在雪地摩托上装移动中继，牧民移动时携带数据。
应用：牧民的电子邮件、网页缓存等数据通过“存–携–转”的方式带回网络覆盖区，再投递。
👉 说明 DTN 可用于偏远地区人群的基本通信服务。

例子 2：太平洋中的动物传感网络

环境：给海豹、鲸鱼等动物佩戴温度/位置传感器，帮助测量海洋温度
问题：动物在大洋中移动，节点之间的连接是间歇性的。
做法：利用动物偶尔相遇时交换/转发数据，最终把数据带到基站（sink）
👉 说明 DTN 可利用“节点移动+偶遇”来完成数据收集。

DTNs路由方式——存储&转发

类似于邮政服务→存储和转发,节点的移动性可以被利用

在这里插入图片描述

DTNs移动模型

Random walk 随机游走

节点选择移动方向，介于 0 和 $2 π$ 之间，以及给定分布的速度; 例如，均匀、正态分布。
节点以该速度沿该方向（公式如下) 移动指定距离或一段时间。在此期间结束时，节点重复此过程。

在这里插入图片描述

Gauss-Markov Mobility 高斯-马尔可夫移动性

节点的速度和方向在第 $n$ 时刻由前一时刻、均值以及随机变量共同决定：

$sn=αsn−1+(1−α)sˉ+1−α2sxn−1s_n = \alpha s_{n-1} + (1-\alpha)\bar{s} + \sqrt{1-\alpha^2}\,s_{x_{n-1}}$

$dn=αdn−1+(1−α)dˉ+1−α2dxn−1d_n = \alpha d_{n-1} + (1-\alpha)\bar{d} + \sqrt{1-\alpha^2}\,d_{x_{n-1}}$

其中：

$s_n$ ：第 $n$ 时刻的速度
$d_n$ ：第 $n$ 时刻的方向
$sˉ,dˉ\bar{s}, \bar{d}$ ：平均速度和平均方向
$s_{x_{n-1}}, d_{x_{n-1}}$ ：来自高斯分布的随机变量（随机性由此项产生）
$α\alpha$ ：调节随机性的参数（ $0$ = 随机游走， $1$ = 线性运动）

Random waypoint 随机航点

每个节点选择特定区域内的随机点作为其目的地，节点以其选定的速度移动到其目的地。当节点到达其目的地时，它会停止一段时间，之后它选择一个新的目的地和速度并恢复移动。
第 $n$ 时刻节点的位置：

$x_n = x_{n-1} + s_{n-1}\cos(d_{n-1})$

$y_n = y_{n-1} + s_{n-1}\sin(d_{n-1})$
其中：

$s_{n-1}$ ：第 $n - 1$ 时刻的速度
$d_{n-1}$ ：第 $n - 1$ 时刻的方向 $[0, 2 π]$
$x, y$ ：坐标位置

Epidemic Routing（流行病路由）——DTNs框架下的路由协议

Based on the theory of epidemic algorithms 基于疫情算法理论
特征：
节点之间相遇时成对交换消息，最终将消息传递到目的地
假设随机移动性模型

核心思想：像病毒传播一样，让消息在节点相遇时被复制并扩散，直到传到目的地。

当两个节点相遇时：
交换 summary vector（各自存有哪些消息的索引）。
根据缺失情况请求和发送消息。

节点缓存（buffer）里保存消息。
在这里插入图片描述
消息简单结构：全网唯一ID用于识别节点，TTL（生存时间）保证消息不要过度泛滥。

在这里插入图片描述
如果缓冲区和 TTL 足够大，则消息会分布在整个网络中，并且传递概率非常高。
如果 TTL = 1，则消息仅传递到目标（如果遇到）

PRoPHET路由协议——DTNs框架下的流行病改进路由协议

PRoPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity)
PRoPHET 是一种 DTN 路由协议，改进自 Epidemic Routing。
它利用 节点历史相遇信息 和 转递性 (transitivity)，计算消息的投递概率，从而选择性复制消息，减少资源消耗。

核心思想

每个节点维护一个投递概率表 $P (a, b)$ ，表示 节点 $a$ 把消息送到节点 $b$ 的可能性。
$\in [0,1]$
当两个节点相遇时，交换：
- Summary Vector（消息摘要）
- Delivery Predictability Vector（投递概率信息）
只把消息交给 投递概率更高 的节点。

概率更新公式

当节点 $a$ 与节点 $b$ 相遇时，更新 $P (a, b)$ ：

$P(a,b)=P(a,b)old+(1−P(a,b)old)×PinitP_{(a,b)} = P_{(a,b)_{old}} + \big(1 - P_{(a,b)_{old}}\big) \times P_{init}$

其中：

$P_{(a,b)_{old}}$ ：旧的投递概率
$P_{init}$ ：初始化常数，每次相遇时增加预测值
相遇次数越多， $P (a, b)$ 越大

📊 与 Epidemic Routing 对比

Epidemic：见面就复制 → 泛洪式扩散，消耗大
PRoPHET：基于概率选择性复制 → 更高效

PRoPHET 协议 — 传递性 (Transitivity)

在 PRoPHET 协议中，如果节点 a 没有直接遇到节点 c，但是它经常遇到节点 b，而节点 b 又经常遇到节点 c，
那么可以认为 a 通过 b 也有一定概率把消息送到 c。这就是 传递性 (transitivity) 的思想。

概率更新公式

$P(a,c)=P(a,c)old+(1−P(a,c)old)×P(a,b)×P(b,c)×βP_{(a,c)} = P_{(a,c)_{old}} + \Big(1 - P_{(a,c)_{old}}\Big) \times P_{(a,b)} \times P_{(b,c)} \times \beta$