Ad Hoc

20230323汪浩东周报

本周主要对于Ad Hoc中的相关问题进行了更深的思考，以期找到其（包括无线场景）的问题，尤其是在与NDN相结合的方面，因为经过小组讨论认为，目前我们仍未搞清楚将大背景移到无线场景下时，会有什么不同以及新的问题的来源及解决方案。

Ad Hoc(无线)场景下的问题（以广播风暴为例）

首先是这个大的背景问题，对于无线以及Ad Hoc这个新场景，其所面临的问题我们始终没有理清楚，以广播风暴为例。

首先，在无线Ad Hoc网络中，因为没有有线连接的支持，以及无线信道的有损性（在Ad hoc中还需要考虑移动性），因此一般采用广播的方式传输包，注意，此处的广播指的是数据链路层，即使用共享广播信道，让所有主机接收同样的包。而这样的广播方式将会带来以下三个问题： #### 冗余 对于冗余这个概念，之前我的理解是：“多个主机对相同的包都进行了广播，从而导致了冗余”，但实际上这个理解是错误的，其真正含义应该为： > “当主机决定将收到的广播消息再次广播给邻居时，它的邻居实际上已经拥有了该消息”

即它的邻居实际上已经收到了来自于其他主机的相同广播消息，再次广播是不必要的，因此称其为“冗余”。具体以下图来说明： 如图所示，B在A的通信范围内，当B收到A的广播消息后，如果其决定再次广播，则能受益的区域（即没有被A广播到的区域）面积为： \[ \text{EAC}=|S_{B-A}| = |S_A|-|S_{A \cap B}| = \pi r^2 - \text{INTC}(d) = \pi r^2 - 4 \int_{d/2}^{r} \sqrt{r^2-x^2} \] 当\(d=r\)时，上式取得最大值，但也仅为\(0.61\pi r^2\)，考虑一般情况，假设B随机处于A的通信范围内任意位置，则可求得EAC的均值为：

\[ \int_0^r \frac{2\pi x \cdot [\pi r^2 - \text{INTC}(x)]}{\pi r^2} dx \approx 0.41\pi r^2\]

再次将场景扩展，考虑在一个主机的通信范围内存在多个主机的情况下，则相应的再次广播能够带来的额外覆盖率EAC比例与主机数\(k\)的关系如下图所示：

由图可见，当\(k\)超过4之后，再次广播所带来的额外覆盖增益已经低于\(0.05\%\)，即此时再次广播明显是冗余的。[^Note] [^Note]:对于并不处于通信范围内的多个主机，当其收到相同广播消息并且向同一节点进行再次广播操作时，这是有必要的，因为可以提升下一节点收到消息的概率，这便体现出了原来的理解的错误之处。

争用

争用实际上应当是广播风暴在Ad hoc中最为致命的一点。如前所述，在广播操作中，多个主机实际上是共享相同的广播信道，因此当多个主机同时想要进行广播操作时，就会产生争用问题。

以两个主机为例，假设B和C都接收到了A的广播消息，则只有当C处于\(S_{A\cap B}\)区域时，会发生争用，其概率为： \[\int_0^r \frac{2 \pi x \cdot text{INTC}(x)/ \pi r^2}{\pi r^2}dx \approx 59\%\] 当此场景扩展到A的通信范围内有\(n\)个主机，则有\(k\)个主机在重播时没有发生争用的概率如图所示： 由图可见，当\(n \geq 6\)时，所有主机都经历争用的概率\(cf(n,0)\)已经超过0.8。

冲突

首先，是CSMA/CA协议，区别于有限局域网中的CSMA/CD协议，在无线环境中，采用的是CA(collision avoidance)，而非CD(collision detection)。无论CSMA/CA还是CSMA/CD，其思想都来源于CSMA(Carrier Sense Multiple Access)，而CSMA实际上来源于Aloha，Aloha的思想可以概括如下：

一个aloha节点只要有数据的话，该节点就可以立即发送。当该节点数据发送完之后，其需要等待接收方反馈的ACK。若成功接收到ACK之后，那么这一次传输成功。如果没有收到ACK的话，那么这一次传输失败。该aloha节点会认为网络中还存在另外一个aloha节点也在发送数据，所以造成接收方发生了冲突。最后这些冲突的节点会随机选择一个时间进行退避（backoff），以避免下一次冲突。若冲突节点回退完成，其才可以重新进行发送。

而CSMA相对与Aloha，增添了LBT(listen before talk)机制，即：

CSMA节点在每一次发送之前先监听信道是否是空闲的，如果信道不是空闲的话，那么就不发送数据，等待一会再进行尝试。只有确保是空闲的情况下，才可以发送数据，从而避免打断其他节点正在进行的传输过程。

其可以分为三种模式^[1]：

• 1-persistentes CSMA：“节点需要持续监听信道，一旦节点发现信道空闲后，则立刻发送数据。”
• 0-persistentes CSMA：“节点不连续监听信道，若该时刻节点监听信道为busy，那么等待一段时间后，再次进行监听。若节点该时刻监听信道为空闲，则立刻发送数据。”
• p-persistentes CSMA：“节点需要持续监听信道，一旦发现信道空闲后，节点以p的概率立刻发送数据，以1-p的概率不发送数据。若节点该时刻不发送数据，那么等待一段时间后，再次进行监听，并以p概率再次发送”。

在以上三种CSMA机制中，若节点传输发送冲突，则类似aloha的基本算法，随机等待一个时间之后，再次进行重试。接下来便可以进一步探讨CSMA/CD与CSMA/CA。

在思想上，CSMA/CD类似于1-persistentes CSMA，而CSMA/CA类似于p-persistentes CSMA，即CSMA/CD是持续监听信道，一旦监听到空闲立刻发生数据，在发送数据时依然检测信道是否有冲突，如果有冲突就停止发送并等待一段随机时间后重试；CSMA/CA是在发送数据前检测信道是否空闲，如果空闲则对backoff counter进行减一操作，直至counter为零才可以发送数据并等待确认帧，如果不空闲则挂起counter，等待一段随机时间后重试。两者的对比可参见Difference between CSMA/CA and CSMA/CD - GeeksforGeeks、Carrier Sense Multiple Access (CSMA) - GeeksforGeeks

知道了两者的不同之后，产生了一个新问题：为什么在无线环境下不再执行CD，而是需要更改为CA？

在有线网络中，如果发生冲突，站点可以通过接收信号的能量变化来检测到冲突。因此，它们可以立即停止发送并等待一段随机时间后再重试，这样可以减少冲突的可能性和浪费的带宽。而在无线网络中，由于信号能量的变化很小，站点很难检测到冲突。因此，它们需要等待整个数据包发送完毕后才能知道是否发生了冲突。这样会导致更多的带宽浪费和延迟。所以，在无线网络中，冲突避免更加重要和必要。

隐藏终端和暴露终端

在无线环境下，还有两个很重要的问题，即隐藏终端和暴露终端，如下面两张图所示。

对于隐藏终端问题，可以通过RTS/CTS机制来解决：在发送数据之前，站点先发送一个请求发送（RTS）的信号给接收站点，接收站点回复一个清除发送（CTS）的信号给发送站点和其他邻近站点。这样，其他邻近站点就知道有一个正在进行的传输，并且等待一段时间后再尝试发送，这种方式可以有效地减少隐藏终端问题造成的冲突和带宽浪费。

但需要注意的是，RTS/CTS机制在IEEE 802.11协议中是可选项而非必选项，因为如果 A正在向 B 发送一个小数据包，那么对于 A来说，简单地发送数据包并准备好在它受到干扰时重新发送，比试图阻止这种干扰要便宜得多。

以上所讨论的都是一对一的情况，实际上在802.11中不考虑一对多的情况

1. Difference between 1-persistent, p-persistent and Non-persistent CSMA - GeeksforGeeks ↩︎