The Network Link Layer: WSNs 泛洪和DSR动态源路由协议

网络层如何将数据包从S——>D ?

1. Flooding 泛洪

Flooding 是一种无控制广播机制，节点收到数据包后，会将数据包原封不动地转发给所有邻居节点，这样数据包会一层层扩散，最终抵达目标节点（比如汇聚节点 sink）

Node C may receive packets from G and H, but does not forward it again. 节点C可以接收来自G和H的报文，但不会再转发。

序列号，防止多次转发

Sequence numbers are usually used to avoid the possibility of forwarding the same packet several times. 序列号通常用于避免多次转发同一数据包的可能性。

为了避免节点反复转发同一个数据包，每个数据包通常会带有一个序列号（sequence number）。
每个节点会记录自己已经看过（接收过）的序列号；
当收到一个数据包时，如果这个序列号已经处理过了，就不会再次转发，从而减少冗余和避免网络风暴。

Eg：
假设节点 A 发送一个数据包，带有序列号 42；
节点 B 收到后记录“我收到过 seq=42”，然后转发；
节点 C 收到两个版本的 seq=42（一个从 A，另一个从 B），但它会只处理第一次收到的版本，忽略其余的重复副本。

Nodes J and K both broadcast packet to node D. 节点J和K都向节点D广播数据包。
Since nodes J and K are hidden from each other, their transmissions may collide. The packet may not be delivered to node D at all, despite the use of flooding.
由于节点J和K是相互隐藏的，它们的传输可能会发生碰撞。 尽管使用了泛洪，但数据包可能根本不会被传递到节点D。

Node D does not forward the packet, because node D is the intended destination.
节点 D 不转发数据包，因为节点 D 是预期目标。

目标节点不转发

Destination node (D) does not forward the packet.
当目的节点 D 收到数据包后，它就不会再转发该包了；因为包已经到达目的地，无需再广播或传播下去。
这是防止 Flooding 无限扩散的一个终止条件。

泛洪完成

Pros and cons of flooding 泛洪的优缺点

Pros 优点

1. Simplicity（简单）
   ➤ 实现简单，不需要复杂的路由表或路径维护。
2. Efficient when rate of transmission is low（当发送频率低时效率较高）
   特别适合发送 小数据包（small packets）
   ➤ 适用于偶发性事件或告警场景。
3. Higher reliability of data delivery （更高的数据传输可靠性）
   packets may be delivered to the destination over multiple paths 数据包可以通过多个路径传送到目的地 → 多路径冗余机制
   ➤ 提高传输成功率，抗网络中断能力强。

Cons 缺点

1. Potential high overhead（潜在高开销）
   data packets may be delivered to too many nodes 数据包可能被送到过多的节点 → 造成大量冗余传输。
2. Waste of bandwidth and energy（带宽和能量的浪费）
   ➤ WSN 中节点电量有限，重复广播会快速耗尽电池。
3. Potential lower reliability of data delivery（在 MAC 层可能导致传输失败）
   原因是多个**隐藏节点（hidden nodes）**可能同时向目标发送数据，造成冲突
   ➤ 即便路径多，但 MAC 冲突会影响整体可靠性。

2. DSR 动态源路由协议

Dynamic Source Routing protocol（动态源路由协议）
DSR 是一种按需（on-demand）的路由协议，专为无线自组织网络（如无线传感器网络、移动自组网络）设计，它让源节点在数据包中携带完整路径，不需要中间节点维护全局路由表。

DSR 工作机制

白话简述

S——>D
S 泛洪广播RR包，找寻节点D；
D被各路泛洪收到RR包后，发送RRp包，单播原路返回S；
S收到RRp包后，单播按RRp包中的路径发送数据包给D。

Find Route （找寻路径）

DSR : S——>D

• based on flooding to find new routes 基于泛洪寻找路由
• RR packets flooded by source node (S) 泛洪的包叫 RR包
• Destination node (D) replies with a RouteReply (RRp) packet upon receiving the first RR packet 当目标节点 D 收到第一个 RR 包后，会发送一个 Route Reply（RRp）回应包

Type: RRp
Source: S
Destination: D
Route Record: [S, E, F, J, D] ← 这是关键！
Hop Count: 5

• RRp是从D反转Route Record的路径，单播逐跳回到S

• S 发数据包： When S sends a data packet to D, the discovered route is included in the packet header 一旦源节点要发送实际的数据，它会把发现的完整路径写入数据包头部，这个过程叫做：
  🔁 Source Routing（源路由）
  所有中间节点不需要维护路由表，只需读数据包头中包含的完整路径即可转发。

Note: RR 包中还包含TTL（Time-To-Live）：存活时间，防止 RR 无限传播，起到限制泛洪范围的作用。

示例

源节点 S 不知道怎么走去 D，于是它广播一个 “我找 D” 的消息，叫做 Route Request（简称 RR）

RR = [ Source = S, Destination = D, TraversedRoute = S ]

邻居 E 收到后更新路径，再发出去：

RR = [ Source = S, Destination = D, TraversedRoute = [ S , E ] ]

→ F 收到后，发出去的RR包：

RR = [ Source = S, Destination = D, TraversedRoute = [ S , E , F ] ]

→ J 收到后，发出去的RR包：

RR = [ Source = S, Destination = D, TraversedRoute = [ S , E , F , J ] ]

→ D 收到第一个RR后，立即发出去的RRP包（单播）：

Type: RRp
Source: S
Destination: D
Route Record: [S, E, F, J, D] ← 这是关键！
Hop Count: 5

这只是发包方向是反方向。但 RRp 包内部仍然携带的是原始的“正向路径”

DSR 协议的改进机制

Promiscuous mode（混杂模式）+ 路由缓存（Caching）

Promiscuous Mode（混杂模式）？
节点不仅接收发给它自己的数据包，还顺便偷听网络中其他经过它的数据包，从中学习路由信息，并放入缓存。

节点缓存

Intermediate nodes in a path can learn about routes to other destinations and store this information in a cache. 路径中的中间节点可以了解到其他目的地的路线并将此信息存储在自己的缓存中。

偷听并缓存只能发生在RRp中，不能发生在RR中

Eg:

对于这条路径 RRp = [ S-E-F-J-D ]
S 缓存 [ S-E-F-J-D ]，[ S-E-F-J ]，[ S-E-F ]，[ S-E ]
E 缓存 [ E-F-J-D ]，[ E-F-J ]，[E-F ]
F 缓存 [ F-J-D ]，[ F-J ]
J 缓存 [ J-D ]

缓存发送

Upon receiving an RR packet, nodes can send back an RRp packet with the full route stored in their cache.
当中间节点收到一个RR包的时候，如果他的缓存中有前往这个节点的记录，他会直接发送这个RRp包。

DSR 的一个优化机制：
中间节点利用缓存（cache）来提前响应，避免 RR 包一直传到 D，减少网络开销。
这种情况叫做：“Reply from Cache”（从缓存中回复）

Eg :

S 广播了一个 RR 包，当前路径为 [S, A, B]
节点 B 收到这个 RR，如果 B 的缓存中已经存有 B → X → Y → D 这样的路径。它就可以直接拼接得到：
S → A → B → X → Y → D
然后 B 构造一个 RRp，把这个完整路径回发给 S

Link breakages in DSR 链路中断

背景设定

之前数据是通过路径 [S → E → F → J → D] 来传输的。现在，J 想把数据发给 D 时，发现 J 到 D 的链路坏了（红色叉），这叫做：
❌ 链路断裂（Broken Link）

🔺 图中红色内容 ，Route Error（RE）包

RE [J–D]
表示：J 发现 J → D 这条链路坏了。

DSR 中的标准处理方式

🔁 1. J 发送 Route Error（RE）包回源节点 S
路径：J → F → E → S
图中虚线箭头：J 把错误信息往回传给 S。

🔁 2. 中间节点沿途更新自己的缓存（cache），所有收到这个 RE 包的节点（比如 F、E、S）都会删除包含链路 J–D 的路径；

🔁 3. S 如果还有其他备选路径（缓存中）：就尝试其他路径发数据；如果没有可用路径，S 就重新广播 RR 包（重新找路）。

多路径机制（Multiple Routes）

三条不同的 Route Reply（RRp）到达源节点 S：

目的节点D的RRp
RRp1 = [S–E–F–J] 绿色
RRp2 = [S–C–G–K] 红色

RRp3 = 从 G 的缓存中得出的路径，G 就不等 D 回复了，直接提前反馈（蓝色箭头）

📌 文本说明解读：
🔹 中间节点也可以发送 RRp：如果它有缓存（如 G），就可以替 D 回应，减少时延。
🔹 目的节点 D 可以对多个 RR 发多个 RRp 回应：每收到一个 RR，就发一个 RRp，最终 S 会收到多个 RRp。
🔹 S 收到多个 RRp 后，可以选择最优路径：
比如根据：跳数（hop 数）最少，路径稳定性，延迟、能量等

词汇说明

overhead 开销
adv.
在头顶上方，在空中
adj.
头顶上的，在空中的，高架的；（驱动装置）顶置式的；经费的，管理费用的
n.
<美>经常开支，营运费用

overhear
v.
无意中听到，偷听到

intermediate

adj.
居中的，中间的；中等程度的，中级的
n.
中级水平者，中级学生；中间事物；（化合物）中间体