无线传感器网络：差错控制（Stop and Wait，Go Back N，Selective Repeat）

编程入门行业动态更新时间:2024-10-25 02:25:54

无线传感器网络：<a href=https://www.elefans.com/category/jswz/34/1734414.html style= 差错控制（Stop and Wait，Go Back N，Selective Repeat）"/>

无线传感器网络：差错控制（Stop and Wait，Go Back N，Selective Repeat）

文章目录

Power control
Automatic repeat request (ARQ)
- Stop and Wait
- Go Back N
- Selective Repeat
Forward error correction (FEC)
Hybrid ARQ (HARQ)
References

严格意义来说，文章中提到的数据包都应为数据帧更为恰当，这里提出，希望不要给大家造成混淆。

Power control

信道可能会造成通信信号的衰减、干扰，从而影响到数据包的准确性。在 WSN 中，低功率的要求使得该问题更为突出。一般来说，我们可以通过调整天线的发射功率来控制节点的有效通信范围。

传输功率的控制可以在无线通信中实现期望的错误率。较高的传输功率可以增加 SNR，因此减小丢包率，但高功率也意味着能耗的增加和节点之间干扰的增大。

功率控制还需要一个较为复杂的协议，实际运行时会增加一定的内存消耗。如果执行逐包（per-packet）的功率控制，那么对于资源有限的节点来说显然是一个很大的开销。

Automatic repeat request (ARQ)

ARQ 错误控制依靠重传丢失或损坏的数据包来保证可靠性，我们会在数据包的有效载荷中添加一个头部字段来指明源节点。

一个低复杂度的错误检测算法（例如，循环冗余校验，CRC）会被用来计算数据包的校验和（checksum），这个校验和会被添加到数据包尾部。接收节点会再次计算收到的数据包的校验和，并将其与数据包中的校验和进行比较。如果结果一致，它就会返回 positive acknowledgement（ACK），否则返回 negative acknowledgement（NACK）。发送节点会设置一个计时器，如果在规定时间内没有收到 ACK 或者 NACK 回应，那么就认为出错或者丢包了，直接进行重传。

ARQ 的主要策略可以概括为以下三种：

Stop and wait
Go back N
Selective repeat

Stop and Wait

一个接着一个传，只有上一个被 ACK 了，才会进行接下来的传输。如果收到了 NACK，那自然要进行重传，可如果 NACK 或者 ACK 在回传过程中丢失了怎么办？答案是设定一个计时器，计时完之后还没有收到任何回复就直接进行重传。

但如果包被成功接收了，但 ACK 直到 timeout 之后才回传回来，此时节点已经将包重传了，这时接收节点可就懵逼了，因为它发送 ACK 之后期望接收到下一个包，此时包来了，但和上一个包一模一样，而它并不知道这是一个新的数据包还是原来的数据包。为了避免接收端收到重复的数据包，我们可以使用序列数字给包标个号。我已经收到 packet 0 了，期望收到 packet 1，结果又来个 packet 0，就直接把这个包丢弃就可以了。

相应的，接收节点可以使用带有 packet number 的确认帧替代直接使用 ACK 和 NACK，来表明我现在期望收到哪个包。

总结一下，在发送端，初始的序列数 SN=0：

从高层接到数据包，并为该数据包标号为 SN；
打包成数据帧，进行传输；
等待确认帧
- 如果收到确认帧，且确认帧序号 RN>SN，那么令 SN=RN，回到步骤 1
- 如果在指定时间内没有收到回复，则回到步骤 2，也就是重传数据包 SN

在接收端，初始的序列号 RN=0：

当从发送端接收到一个无错的数据包，且数据包 SN=RN，那么就将该数据包交付给上层处理，并令 RN += 1；
给发送方回传序列号为 RN 的确认帧

下面我们讨论一下停等协议的效率。

error free scenario，无错情况下：

(上图中的 propagation delay 应为 D P D_P DP)

scenario with error，有错情况下：

不管是否发生错误，效率的计算公式总是 packet transmission time / total time，在有错误的情况下，我们假设错误发生的概率为 p p p，那么这个包需要传输 i i i 次才能成功传输的概率为
p i − 1 ( 1 − p ) p^{i-1}(1-p) pi−1(1−p)
即前 i − 1 i-1 i−1 次都出错了，最后一次传输成功。这 i − 1 i-1 i−1 次每次耗费的时间都为发送节点设置的 timeout 时间， T O TO TO，而最后一次成功传输的时间就是我们上面无错情况下的 S S S。

在平均情况下，我们的传输次数期望值为：
∑ i = 1 ∞ i p i − 1 ( 1 − p ) = 1 1 − p \sum_{i=1}^\infty ip^{i-1}(1-p)=\frac{1}{1-p} i=1∑∞ipi−1(1−p)=1−p1

因此除去一次成功传输耗费的 S S S，剩下的 1 1 − p − 1 = p 1 − p \frac{1}{1-p}-1=\frac{p}{1-p} 1−p1−1=1−pp 次传输都耗费 T O TO TO，所以总时间即为 S + T O p 1 − p S+TO\frac{p}{1-p} S+TO1−pp，效率为
E = D T P S + T O p 1 − p E=\frac{D_{TP}}{S+TO\frac{p}{1-p}} E=S+TO1−ppDTP

Go Back N

停等协议每个轮次只能发送一个数据包，只有当前数据包被 ACK，才可以发送下一个数据包。Go-Back-N 协议利用滑动窗口，使得我们能够一次性发送多个包含在窗口中的数据包。每次最早发送的数据包被确认后，滑动窗口就可以继续滑动，将包含在窗口中的新数据包发送出去。

假设窗口大小为 N N N，对于发送方来说，在数据包 i i i 被确认之前，是不可能发送数据包 i + N i+N i+N 以及之后的数据包的，而接收端的表现和停等协议是差不多一样的。当到达的数据包不是收方期望的 R N RN RN 时，发送方需要重传数据包 R N RN RN 及之后所有的数据包。因此当通信质量差时，Go-Back-N 协议的效率可能很糟糕。

接收方还可以使用叫作累积确认的机制，即不对每个数据包逐一确认，而是等收到一组数据包后累计确认，例如返回 ACKn 表示数据包 n n n 之前的数据包都被成功接收了。这虽然可以减小网络开销，但在某些情况下可能会发生错误。

例如，我们使用三比特的序列号（0~7）。发送方发送数据帧 0 之后收到了 ACK1，然后开始传输数据帧 1，2，3，4，5，6，7，0，并且又收到了 ACK1，问题在于，这个 ACK1 是表明前面发送的数据帧都被正确接收了还是都在传输过程中丢失了，这一点显然无法分辨。

Go-Back-N 协议的效率（无错情况下）：

如图所示，如果 N > S / D T P N>S/D_{TP} N>S/DTP，那么在收到一个包 ACK 的总时间内我们实际上一直在发送数据包，因此效率为 1，如果 N < S / D T P N<S/D_{TP} N<S/DTP，那么我们的效率则直接为 N ∗ D T P / S N*D_{TP}/S N∗DTP/S，所以有
E = min ⁡ { 1 , N ∗ D T P / S } E=\min\{1, N*D_{TP}/S\} E=min{1,N∗DTP/S}