团队科研成果分享-14

研究背景

水下物联网在海洋资源探测和环境监测方面具有广阔的研究前景。使用IOUT可以更有效地获取海洋环境信息，对海洋资源开发和科学研究产生重大影响。在IOUT中，节点通常是随机部署的，没有任何预先分配的网络拓扑。因此，节点不能在不知道其周围存在的邻居节点的情况下建立用于数据传输的通信链路。在现有的水声通信研究中，节点多采用全向方式传输数据，与全向方式相比，定向传输将发射功率集中在有限的波束宽度内，在相同发射功率条件下增加了信号传输距离，减少了相邻通信之间的干扰，增加了空间复用的机会。因此，本研究致力于研究IOUT中的邻居发现问题。

关键技术

本研究针对邻居发现问题展开研究。该算法由两部分组成：一个基本的基于仲裁系统的邻居发现算法(QSND)和一个自适应的基于强化学习的邻居发现算法(RLND)。首先，采用C-torus Quorum系统设计了一种定向收发信机波束扫描序列，完成初始邻居发现。然后，研究了一种基于强化学习的自适应波束调整方法，根据邻居推荐和先验知识调整待扫描方向波束的数量，从而减少邻居发现所需的时隙数

该方法的创新和贡献如下：

1）提出了一种基于C-torus Quorum的邻居发现(QSND)算法，利用C环法定人数系统设计定向波束的扫描序列，实现节点的波束对准。 

2）研究了一种基于自适应强化学习的邻居发现(RLND)算法，该算法根据先验信息和邻居推荐知识自适应调整待扫描波束数，从而加快邻居发现过程。

3）仿真结果表明，该算法可以大大缩短邻居发现的过程，提高邻居发现的效率。

算法介绍

1. 基于C-torus Quorum的邻居发现(QSND)算法

图1 不同Quorum之间的比较

如图1所示为不同Quorum之间的比较，仅给出两个定向波束的时隙选择。每个小方格表示一个时隙，整个矩形表示一个周期。绿色和橙色块表示分配给两个不同波束的活动时隙，红色块表示它们的重叠时隙。本文采用一种经典的基于竞争的水下MAC协议UWAN-MAC来传输邻居发现包。相邻节点可以在重叠的时隙中执行波束对准，发送握手数据，从而发现彼此。

如图1(a)所示，波束数用N表示，则Grid Quorum创建了N×N时隙矩阵，随机选择一个行和一个列时隙作为一个波束的活动时隙，然后再随机选择其他不重复的行和列时隙作为其他波束的活动时隙，直到分配完所有波束的所有时隙。在用红色块表示的重叠时隙{29,33}中，相邻节点的波束可以对齐以进行邻居发现。显然，基于Grid Quorum设计的时隙矩阵维数较大，存在许多无法利用的空闲时隙，用其设计邻居发现的波束扫描序列会引入较长的发现延迟。

Torus Quorum在Grid的基础上，将矩阵大小缩小一半，且遵循环面的原理，将网格最右边的列绕回到最左边。选取任意一列的元素，加上其右侧⌈n/2⌉列中每列任取一个元素构成一个Quorum。同样保证了不同Quorum之间具有两个相交元素，但是其在设计右侧选择时隙时，仅考虑随机在每列选择一个时隙，如果相邻两个Quorum在右侧选择了相同时隙，会造成Quorum的冗余。如在图1(b)，如果两个相邻节点选择同一时隙13，则表示两个节点可以在重叠时隙中进行邻居发现，以发现彼此。但是，如果有2个以上的相邻节点选择同一时隙，则意味着将有多个节点在同一时隙执行邻居发现包传输。在这种情况下，类似于隐藏终端的问题，时隙的冗余引入了不可避免的分组传输冲突。

C-torus Quorum是在Torus quorum的基础上，对右侧元素的选择进行了改进。它随机不重复选取某一列，然后在其后随机选择某行选取连续的⌈n/2⌉个元素构成一个quorum，同样保证了邻居发现的确定性，且占空比最优。

图2 基于C-torus Quorum的邻居发现算法

在支持定向传输的IOUT中，成功的邻居发现需要满足以下三个条件:

•相邻节点的活动波束在同一时隙内相互对齐，如图5中节点n1的第i个波束和节点n2的第j个波束；因此，本研究采用C-torus Quorum来设计每个定向波束的有效时隙。

•相邻节点的发送和接收模式在彼此对齐的活动波束内匹配，这意味着一个节点处于发送状态，另一个处于接收状态。

•处于发送和接收状态的相邻节点之间的握手成功。

首先，基于C-Torus Quorum设计了活动时隙。对于所有节点，相同方向的波束被分配相同的时隙序列。如图2(a)所示，节点n1的第i个波束和节点n2的第j+k个波束在同一方向上，将在同一时隙中工作。例如，如图2(b)所示，为节点n1的第i个波束和节点n2的第j+k个波束分配的活动时隙为{1,9,10,11,12,13,17,25}。为节点n1的第i+k个波束和节点n2的第j个波束分配的有效时隙为{3,11,19,27,28,29,30,31}，因此两个节点可以获得至少一个重叠时隙（如第11个时隙）通过握手机制执行邻居发现。

图3 邻居发现的工作模式

然后，为了保证相邻节点的成功握手，设置发送-接收模式，如图3所示，每个节点的波束先编号，同一方向上的标有相同的编号。以4波束定向天线为例，如图3(a)所示，所有光束都逆时针编号，编号表示为{1,2,3,4}。然后在邻居发现过程中，对不同方向的波束分配不同的工作模式。对于数量小于m/2的波束，其中m是定向波束的数量，它们从“发送”模式开始工作。每个时隙被分成三个子时隙。因此，在每个时隙中，工作模式被设置为{发送，接收，发送}。对于数目大于m/2的光束，它们从“接收”模式开始工作。因此，在每个时隙中，工作模式被设置为{接收、发送、接收}。最后，利用三次握手机制来发现对方。如图3(b)所示，n1和n2的模式分别设置为{发送、接收、发送}和{接收、发送、接收}。处于发送状态的节点n1向处于接收状态的邻居n2发送“请求”分组。如果节点n2成功接受请求包，它将向节点n1发送“应答”包。最后，接收应答包的节点n1发送“确认”包以完成三步握手并发现邻居。

很明显，QSND中设计的时隙大小是固定的，不适合动态IOUT。有些时隙不能满足波束对准要求，从而不能执行邻居发现；而另一些时隙即使在邻居发现成功后也要重复扫描，这不仅浪费了能量，而且导致很长的邻居发现延迟。因此，本文进一步研究了一种自适应的最优邻居发现算法。

2. 基于自适应强化学习的邻居发现算法

在基于强化学习的邻居发现(RLND)算法中，设计了自适应调整机制。在每个期望发现周期前，采用基于Nash Q学习的自适应波束调整方法。根据先验知识和邻居推荐知识，自适应调整待扫描波束数，从而调整仲裁序列大小，减少期望发现周期内的时隙数，从而加快邻居发现过程。

（1）先验知识：根据节点在前一次仲裁系统扫描过程中发现的邻居关系，得到节点在每个波束中关于其邻居的先验知识。换句话说，判断节点是否在当前周期的波束中找到了邻居节点。如果发现邻居，则认为当前波束中可能还存在邻居节点，在下一个循环中继续扫描当前波束。奖赏函数设置为该波束中的邻居节点与发现的邻居节点总数的比值。否则，认为该节点在当前波束中没有邻居或已完成邻居发现；然后，在下一个周期忽略当前光束的扫描过程并将其奖励函数设为0。通过这种判断，可以减少波束扫描次数，从而导致期望发现时隙的减少，加快算法的收敛过程。对先验知识的奖励定义如下：

（2）邻居推荐：在动态IOUT中，节点之间的邻居关系随当前洋流等因素变化。节点间的协作和邻居推荐可以帮助节点了解周围可能未发现的邻居节点，从而更快地执行邻居发现过程。在三次握手过程中，节点可以将自己邻居表中发现的邻居节点的信息推荐给其邻居节点。用于邻居推荐的奖励函数定义如下：

基于强化学习的自适应邻居发现：在RLND中，相关定义如下：

状态s_t，多智能体的联合状态空间表示为：

动作a_i，有两种类型的行动:扫描和非扫描，基于当前联合状态和行动选择策略确定联合行动空间：

奖励r，联合奖励函数定义如下：

策略 ，波束基于当前状态确定下一个最佳动作，即是否在下一个循环中扫描。根据奖励判断是否选择当前光束作为下一周期的扫描波束。

将Nash Q函数定义为Agent在下一阶段遵循Nash均衡策略时所获得的期望贴现收益之和，计算如下：

Nash Q学习算法的第一步是在t=0处假设一个随机Q值。在时间t时，代理i识别其当前状态并采取相应的行动以获得正的奖励，然后使用时差算法按以下公式更新Q值：

在每个发现周期内，节点通过学习先验知识和邻居推荐信息，通过Nash Q学习算法获得下一个周期的最优扫描波束序列，并将其作为新的扫描波束序列重新设计，继续执行节点的波束对准过程，直到邻居发现过程完成。

实验结果

首先，基于不同的Quorum系统，如网格法定人数、环面法定人数、C-Torus法定人数，对基本QSND的性能进行了评估。然后选取LAND和ADND对QSND和RLND的邻居发现率、邻居发现时间、能耗等性能进行了比较。

1. 不同Quorum的比较

图4 Neighbor Discovery Ratio vs. Simulation Time

从图4中可以看出，基于C-torus quorum的邻居发现方法比其他两种Quorum的性能要好，能够更快地发现节点周围地邻居节点。相较于Torus Quorum, C-Torus能够提供更好地性能，是因为其在选择后续时隙是的连续性，避免了随机选取可能发生的节点波束冲突，这种冲突不仅浪费导致资源的浪费，而且导致更长的发现延迟。同时可以看出采用C-torus Quorum可以实现比Gird Quorum更短的邻居发现时延，这是因为Gird-Quorum的时隙矩阵大小为n*n；而Torus-Quorum的时隙矩阵大小为n*n/2，能够以更快的速度发现周围的邻居节点，邻居发现时间也就更短。

图5 Neighbor Discovery Time vs. the Number of Nodes

如图5所示,对于相同数目的节点，C-torus Quorum减少了邻居发现时间，并且随着节点数目的增加，这种益处变得更加显著。与其他两种Quorum系统相比，Grid Quorum的发现周期大约是其他两种Quorum系统的2倍，并且随着邻居发现的进行，冗余时隙的数量不断增加，从而导致了长尾效应。另一方面，C-torus Quorum与Torus Quorum相比在时隙选择方面有一些改进，这使得波束选择相对更确定并且产生相对更少的冲突，因此其邻居发现时间也更短。

图6 Neighbor Discovery Time vs. Packet Loss

由于复杂的水下环境和噪声等因素的影响，节点在传输数据包的过程中容易出现丢包现象，导致相邻节点之间的握手过程失败，从而无法确定节点的邻居关系。图6比较了不同丢包率下的算法。可以看出，C-Torus Quorum在丢包率较高的情况下具有较好的性能，主要是由于其冗余时隙较少，周期较短。因此，在分组丢失的情况下，分组的重传具有更小的周期间隔，并且能够在更短的时间周期内发现邻居节点。

图7 Comparison of Energy Consumption

 如图7所示，C-Torus Quorum相对于其他两种算法具有较少的波束冲突，并且能够更快地完成相邻节点之间的波束对准，因此消耗的能量相对较小。另外，它具有较少的冗余时隙和较快的邻居发现过程收敛速度，使得节点在邻居发现过程中产生的数据包较少，冗余数据包较少，从而消耗较少的能量。例如，当节点数为200个时，网格法定人数的平均能耗比网格法定人数少20%，比环面法定人数少13%，并且随着节点数的增加，能耗优势更加明显。

2. 算法之间的比较

图8 Neighbor Discovery Ratio vs. Simulation Time

从图8中可以看出，在相同条件下，RLND的邻居发现率最高，能够更快地发现周围的邻居节点，而ADND的邻居发现率次之，QSND的性能最差。这是因为RLND和ADND算法都采用强化学习方法，利用先验知识加快邻居发现过程，而QSND只能按照确定性序列扫描波束，当发现某个波束中的邻居时，仍然要扫描该波束，这导致了大量冗余时隙和较慢的邻居发现效率。此外，LAND算法可以利用环境中的先验知识来加快节点的波束选择，其性能优于QSND算法，而不如RLND和ADND算法。

图9 Neighbor Discovery Time vs. the Number of Nodes

如图9所示，RLND邻居发现时间最短，QSND长尾效应严重。RLND和ADND算法通过使用强化学习来学习节点邻居发现的先验知识，减少了下一个周期需要扫描的波束数，进一步减少了冗余时隙的出现，从而有效避免了长尾效应。此外，RLND还考虑了节点间的协作，使得节点下一周期的波束扫描序列规划得更准确，性能更好。并且注意到随着节点数的增加，节点间的冲突概率增加，导致邻居发现失败，因此算法的整体性能下降。

图10 Neighbor Discovery Time vs. Packet Loss

由于受水下复杂环境、噪声等因素的影响，节点在传输数据包的过程中容易发生丢包，导致握手过程失败，无法确定节点的邻居关系。因此，图10比较了算法在不同丢包率下的性能。实验表明，本文提出的算法能够很好地适应大丢包率的水下环境，缓解了恶劣的水下环境对邻居发现过程的影响。

图11 Comparison of Energy Consumption

水下节点能量有限，图11对节点的能量消耗进行了比较，与对比算法相比，RLND由于邻居发现收敛速度快，在正常握手过程中发送冗余数据包和发送和接收数据包所消耗的能量相对较少。此外，当节点数量增加时，节点分组冲突和传输错误的可能性也增加，这导致能量使用的增加。

总结

针对水下物联网的定向传输问题，本文提出了一种基于仲裁系统的基本邻居发现算法(QSND)和一种基于自适应强化学习的邻居发现算法(RLND)。在QSND中，首先采用C-torus法定人数来设计波束扫描序列，即分配活动时隙，以保证相邻节点的波束在同一活动时隙上能够相互对齐。然后，提出了发送-接收模式，并提出了一种三次握手机制来发现邻居。为了进一步动态调整波束扫描序列和活动时隙，利用Nash-Q学习算法研究了一种自适应邻居发现算法。仿真结果表明，与QSND和其他相关算法相比，RLND在邻居发现率、邻居发现时间和能量消耗等方面都有较好的性能。在每个发现周期中，可以根据先验知识和邻居推荐信息调整需要扫描的波束数，从而调整仲裁序列的大小，限制期望发现周期中的时隙数，减少波束扫描量，同时加速邻居发现。