2023.12.25-2023.12.31

在陆地无线传感器网络中，传播时延可以忽略不计，数据包到达的时间与发送节点和接收节点的空间位置无关，只取决于数据包的发送时间。由于水下传输具有较长的传播延迟，UWSN的数据包到达接收节点的时间是发送时间和空间位置的二元函数；即数据到达接收节点的时间既与数据发送的时间有关，也与发送节点和接收节点的相对位置有关，因此存在时空（ST）不确定性，这对传输调度提出了很大的挑战。针对UWSN中时空不确定性引起的节点调度问题，本文提出一种基于簇的时空MAC调度协议（CSS-MAC）。

本文提出了一种基于簇的时空MAC调度协议(CS-MAC)。首先，根据节点传播范围内的簇头个数定义簇头系数。然后，根据簇头系数越大的节点越早发送的基本思想，提出了一种确定干扰节点的算法。其次，根据节点间的冲突关系，提出了一种生成时空冲突图的新算法(ST-CG)。最后，通过两跳范围内节点的发送优先级和发送时间信息的交互作用，提出了一种分布式传输时刻分配算法。在初始化过程中，本文提出了一种分簇算法，保证每个簇头节点不在另一个节点的传播范围内。

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

1）由于簇头系数大的节点的传输不受簇头系数小的节点传输的影响，因此该算法尽可能避免了单个节点多次禁止次数的限制，大大简化了ST-CG。在ST-CG的基础上，提供了节点发送优先级的计算公式，提高了网络的并发传输性能。

2）由于水下环境能源有限，仅依靠传感器的电池电源提供能量是不够的，而水声调制解调器具有较高的能源效率。因此，在UWSN中安装水声调制解调器是非常有必要的。由于水声调制解调器的层次分簇特性，它在MAC协议的设计中起着至关重要的作用。因此，本文针对所提出的MAC协议提出了一种新的分簇算法。

1. 网络模型

图1  网络模型

如图1所示，节点随机分布在某个海域，通过后面将提供的分簇算法进行自主分簇。分簇后，成员节点与簇头节点之间存在单跳距离，簇头节点不在彼此的传播范围内。本文仅考虑从成员节点到簇头节点的传输。

本文提出的MAC协议旨在解决时空不确定性的调度问题。节点调度本质上是安排节点发送数据的时间，避免接收节点发生冲突。数据包到达接收节点的时间可以被认为是发送时间和节点传播延迟的二元函数。因此，只要获得节点的位置分布和水声传播速度，就可以计算节点之间的传播延迟并开始调度。

事实上，节点只需收集与其范围内所有簇头的成员节点相关的传播时延信息，并维护传播时延信息表。如图2所示，假设成员节点C1,1具有簇头节点H1，则H1的成员节点还包括C1,2,C1,3。在其传播范围内还有另外两个簇头节点H2,H3，对应的成员节点分别为C2,1,C2,2,C2,3和C3,1,C3,2,C3,3。

图2  单个节点的本地拓扑

在网络初始化阶段，各成员节点通过信息交换在本地维护传播时延信息表。具体方法是：在初始化阶段分簇后，每个节点向网络广播自己的位置信息和簇头信息；每个簇头节点收集网络中的广播信息，并计算每个成员节点到自己的传播时延信息。一段时间后，簇头节点将收集到的成员节点的时延信息广播给网络。每个簇头节点的成员节点收集广播信息，并基于收集的信息维护时延信息表。

2. CSS-MAC协议设计

在初始化阶段，节点之间交换信息。节点按照分簇算法1进行自主分簇。分簇后，每个成员节点收集其两跳范围内节点的位置信息，并在本地维护传播时延信息表。

（1）分簇算法

在部署节点之前，选择一个节点作为主簇头节点，并将其与其余普通节点（ON）部署在目标海域。如图3所示，分簇过程分为两个阶段：通知阶段和分簇阶段。分簇阶段由多个相同的帧组成，每个帧包含簇头确认和簇成员确认两部分。每个阶段足够长，使得节点能够接收到其传播范围内所有节点发送的信息。事实上，每个阶段由若干个时隙组成，具体时隙数量由节点数量决定。

图3  分簇过程的帧结构

N1,N2,…,Nn 为普通节点，N 为主簇头节点，ON是普通节点的集合，预簇头节点（PCH）是预簇头节点的集合，预簇成员节点（PCM）是预簇成员节点的集合。

1）在通知阶段，主簇头节点N广播通知信息，通知网络中的节点自主开始分簇，其传播范围内的节点收到通知信息后，将通知信息转发到网络。这个阶段足够长，使得网络中的所有节点都能收到通知信息。事实上，通知阶段由几个时隙组成。在每个时隙开始时，节点N的传播范围之外的节点收到通知信息后，以一定的概率选择转发。因此，在一个时隙内，网络中的通知信息量相对较少。由于本文的控制包长度较短，因此冲突很小。具体时隙数量由网络规模决定，本文中等于节点数的2.5倍。最后将节点N作为PCH，N传播范围内的节点作为PCM。

2）在簇头确认阶段，公共节点（ON）向网络广播短帧信息，其中包含剩余能量和ID信息。这个阶段也足够长，使得每个普通节点都可以接收到其传播范围内其他ON的剩余能量和ID信息。事实上，簇头确认阶段由几个时隙组成。在每个时隙开始时，公共节点（ON）以一定的概率选择广播。具体时隙数由网络规模决定，本文中等于节点数。如果普通节点Nj在采集到的能量信息中能量最大，则将Nj作为PCH。

3）在簇成员确认阶段，PCH Nj 向网络广播消息，声称自己是预簇头节点。如果PCH Nj的传播范围内的公共节点(ON) Ni接收到该消息，则它将被用作PCM。如果预簇头节点Nj接收到其传播范围内的其他预簇头节点广播的消息，并且Nj的能量比其他预簇头节点少，则Nj将被用作普通节点。

4）重复步骤 2-3。

5）一段时间后，将剩余的ON用作PCH。

6）PCM选择距离它最近的PCH作为它的簇头节点。

（2）确定发送优先级

在网络中，往往存在许多簇头系数相等的节点。下面介绍如何判断哪个节点选择较早的发送时间。首先，簇头系数较高的节点较早发送。

1）当簇头系数相同时，节点首先构建自己的冲突图。冲突图中边越多的节点获得的发送时间越早。边越多，发生的冲突就越多，因此边越多的节点必须确定自己更早的发送时间。

2) 在簇头系数相同、边数相同的节点冲突图中，顶点数较少的节点获得较早的发送时间。较少的顶点意味着某些顶点具有多个边；如果干扰节点先发送，则会造成多次禁止。当边数也相同时，节点与簇头节点的距离越大，发送时间确定得越早，这样可以增加网络中节点的并发传输，从而降低网络延迟。

SPN^(n) (i) 是簇头系数为 n 的节点 i 的发送优先级，定义如下

其中E(i)是节点i的冲突图中的边数；V(i)为节点i的冲突图中的顶点数；Di,H 为该节点与目的节点（簇头节点）之间的距离；R是节点的最大传输半径。通过该式，簇头系数相同的节点可以计算出自己的发送优先级，从而确定自己的发送时间。

（3）分布式传输时刻分配算法

根据干扰节点的定义，节点的干扰节点必须在同一簇头的传输范围内。因此，一个节点可以通过两跳的最大距离获得其干扰节点的信息。换句话说，节点及其干扰节点必须能够通过簇头节点交换信息。因此，一个节点可以依赖其传播范围内的簇头的转发来与其他节点交换信息。在初始化期间，节点将自己的状态标记为“0”。

图4  分布式传输时刻分配

步骤1：节点广播其簇头系数，向簇头和邻居节点发送优先级和状态信息。簇头节点转发接收到的信息。同时，节点接收簇头系数，从邻居节点和簇头节点发送其他节点的优先级和状态信息。

步骤2：在接收到的信息中，节点根据干扰节点的定义找到所有的干扰节点。在状态为0的干扰节点中，如果没有簇头系数大于n的节点，且该节点具有最大的优先级，则该节点计算自己的传输时间，并将状态设置为“1”，最后将传输时间和状态信息广播给邻居节点和簇头节点。

步骤3：如果状态为0的干扰节点中有簇头系数较高的干扰节点，或者存在簇头系数相同但优先级较高的节点，等待一段时间后返回步骤2。

步骤4：重复步骤2和步骤3，直到所有节点的状态都为“1”，即所有节点都确定了自己的传输时间。

通过这些步骤，在经过一段时间的信息交换后，网络中的节点可以根据干扰节点的状态、发送优先级信息和冲突图来确定自己的传输时间。

1. 吞吐量

图5  不同网络负载下的吞吐量变化

如图5所示，当网络负载增加时，CSS-MAC的吞吐量逐渐增加并最终稳定，因为当网络负载较低时。有一些节点在该传输数据的时刻没有数据可传输；因此，信道被浪费，吞吐量低。当网络负载增加时，这种情况出现的频率会降低，吞吐量趋于稳定。ST-MAC与CSS-MAC类似；然而，CSS-MAC是基于连续时间来调度节点的，因此CSS-MAC的吞吐量平均比ST-MAC高出约45%。当网络负载增加时，CSSTU-MAC的吞吐量变化与CSSMAC相同。在CSSTU-MAC中，由于簇之间的相互影响，簇之间避免了彼此的传输时间，从而造成信道的浪费。因此，CSS-MAC 的吞吐量比 CSSTU-MAC 高大约 38%。TDMA以固定的方式为节点分配时隙，而CSS-MAC采用连续的时间分配方案，提高了信道的利用率，大大提高了吞吐量。

图6  不同节点数量的吞吐量变化

如图6所示，当节点数量增加时，CSS-MAC的整体吞吐量增加，因为单位时间内传输数据的节点增多。但由于CSS-MAC的调度与节点之间的位置有关，因此在某些情况下吞吐量会下降。ST-MAC 与 CSS-MAC 类似，由于ST-MAC中的时间调度不连续，CSS-MAC总体上具有较高的吞吐量。随着节点数量的增加，CSSTU-MAC的吞吐量整体上也会增加。与CSS-MAC类似，当节点数量变化时，吞吐量会下降，因为它们的调度与节点之间的传播延迟有关。TDMA单位时隙发送的节点数量恒定，因此吞吐量基本恒定，但低于CSS-MAC。

2. 端到端时延

图7  不同网络负载下的端到端时延变化

图8  不同节点数的端到端时延变化

如图7所示，CSS-MAC本质上是一种具有固定分配时间的MAC协议。因此，当网络负载增加时，节点的数据必须等待更长的时间，端到端的延迟增加。ST-MAC、CSSTU-MAC 和 CSS-MAC 本质上是相同的；它们是以固定方式为每个节点分配时间的MAC协议。然而，由于CSS-MAC采用连续的时间分配方案，因此CSS-MAC对于所有节点的一轮通信具有比ST-MAC更短的总分配时间段。CSSTU-MAC在单个簇中使用连续时间分配方案；然而，为了防止不同簇之间的冲突，不同簇避免了彼此的传输时间。导致整体分配的时间比较大，端到端时延比CSS-MAC更大。同样，对于TDAM，由于其时隙分配固定，端到端时延随着网络负载的增加而增加。与CSSMAC相比，TDAM具有更高的端到端延迟。如图8所示，当节点数量增加时，CSS-MAC的端到端延迟减少，因为单位时间内成功传输的数据包数量增多，并且随着节点数量的增加，总传输时间减少。ST-MAC和CSSTU-MAC的端到端时延变化与CSS-MAC相同，但端到端时延比CSS-MAC更长。TDAM的端到端延迟随着节点的增加而缓慢增加，因为当节点较多时，单个数据包的等待时间随着多分配时隙数量的增加而增加。

3. 一轮通信的周期长度

图9  不同节点数的一轮通信周期长度

CSS-MAC、TDMA、ST-MAC、CSSTUMAC本质上都是为节点分配固定的传输时间，区别在于分配方式不同。因此，这四种MAC协议具有不同的传输周期长度，即一轮通信所用的时间。如图9所示，对于不同的节点，CSS-MAC具有最小的周期长度，并且周期长度随着节点的增加而增加，因为当节点越多时，必须为网络中的节点分配更多的时间。然而，由于 CSS-MAC 的性能与节点之间的位置有关，30 个节点的 CSSMAC 的周期长度比 24 个节点的周期长度短。当网络拓扑发生变化时，CSS-MAC的性能会受到影响。其他三种 MAC 协议的周期长度与 CSS-MAC 类似；当节点数量增加时，周期长度通常会增加。类似地，当 ST-MAC 和 CSSTU-MAC 的节点数量增加时，周期长度减少。由于TDMA以固定的方式给节点分配时隙，当节点数量增加时，其周期长度不断增加。

UWSN具有较长的传播时延，给水下网络引入时空不确定性，影响节点调度。针对该问题，本文提出一种基于簇的时空MAC调度协议（CSS-MAC）。CSS-MAC中根据节点之间的碰撞关系提出了一种新的ST-CG算法，尽可能避免单个节点多次禁止次数的限制，大大简化了ST-CG。通过ST-CG，节点可以分布式地确定传输时间，而不需要专门的节点进行调度。所提出的协议降低了ST-CG的复杂性并且不需要额外的节点进行调度。

END

==河海大学网络与安全实验室==

微信搜索：Hohai_Network

联系QQ：1084561742

责任编辑：何宇