每周文章分享-172

近年来，水声传感器网络在海洋资源开发、环境勘探、地震监测等各个领域得到了广泛的应用，取得了很大的进展。为了保持良好的调度性能，分簇算法和多路访问控制(MAC)协议被广泛应用于传感器网络，以提高网络效率。然而，现有的算法和协议仍然存在许多不足。例如，分簇和MAC不追求相同的指标；分簇背景过于理想化，因此这些MAC协议可能不能很好地整合现有的分簇算法；较少考虑簇间和簇内切换调度；簇内的集中式拓扑、单向信息流等条件没有得到充分利用。本文致力于解决这些问题。通过同时考虑节点流量和距离，合理地设计了簇的结构，并基于这种结构，设计了一个空闲时间间隔最小的无冲突握手协议。

本文提出了一种分簇算法和与之配套的 MAC 协议。为了降低时延，提高簇头的一致性，在分簇算法中采用了以下策略：1) 减少大流量节点的冗余传输；2) 合理更换重传节点；3) 减少空闲时间；4) 同时考虑流量和距离等因素设定分簇权重；5) 随着分簇的进行设置递减的距离系数。MAC协议在充分利用上述分簇算法形成的分簇结构和集中式网络的特点的基础上：1) 实现了中心节点的无间隙调度；2) 通过修改清除发送(CTS)包结构，在不影响网络功能的情况下取消确认字符(ACK)信号；3) 设计空闲或移动节点的加入分簇策略，完成分簇维护。

1.非均匀流量水声传感器网络分簇算法

由于流量会直接影响节点的传输时延，因此本文首先考虑每个节点的流量。设节点流量为x，其权重系数为α，则将节点(i)自身的权重设置为：

图1  大流量示意图

如图1所示，与使用流量较小的节点作为簇头相比，使用流量较大的节点可以减少大任务节点的一跳转发过程。因此，本文希望流量较大的节点的权重更高。考虑到多个节点，从上面的权重设计中节省的延迟收益是：

上式给出了使用大流量节点作为簇头节点和使用小流量节点作为簇头节点两种情况下的时延差异。其中τ_p(j)和τ_p(j)是两种情况下成员节点j和簇头节点之间的传播延迟。t_i和t_k分别是两种情况下簇头的传输时延，t_delay2和t′_delay2是簇头和汇聚节点之间的传播时延。

当簇头与多个簇内成员节点通信时，采用控制包复用协议的网络往往具有较好的效率。如图2和图3所示，四个成员节点依次向簇头节点发送请求发送(RTS)信号。簇头收到所有RTS信号后，将传输时间分配给需要发送数据信号的节点。在这个过程中，如果簇头有附近的成员节点，可以节省CTS包后的间隔时间，如图2中的红圈所示。此外，本文还考虑了当较早向簇头发送数据的节点(图3中的节点1)只需要发送少量信息(小于传播延迟差)时。这种情况将导致产生空闲时隙(图3中的红圈)，即使节点3在接收到CTS包之后将定时器设置为零。因此，本文也希望离簇头更近的节点能够有更多的流量。

图2  信息流示意图

图3  信息流示意图（短包）

根据上述思想，在考虑距离因素后，将其节点权重y2设置为：

一方面，本文利用流量权重系数α来衡量和调整节点自身流量对簇头的影响。另一方面，在距离影响成反比的情况下，使用距离权重系数β来衡量和调整相邻节点流量的影响。同时，流量与距离的比率能够很好地反映图2和图3中的考虑场景。

因此，在同一簇中，所有其他节点的流量会影响基于距离的簇头权重。也就是说，簇中成员节点生成的权重之和如下所示

最后，总权重W设置为节点自身权重与其作为簇头的簇权重之和，可以通过以下方式计算：

本文希望簇之间没有重叠时，簇头距离和通信距离需要满足以下公式，又考虑到簇头节点的一致性，本文设置了一个逐渐减小的系数ε：

对于簇网络，为了避免不同簇之间的干扰，传统算法可能会直接对每个簇使用不同的频段。然而，对于多节点网络，这种方法可能会造成大量的频段浪费。因此，本文仅在以下两种情况下使用不同的频段。

1）簇的重叠部分存在节点，如图4(a)所示。

2）相邻簇中存在相互影响的节点，如图4(b)所示。

图4  不同簇的频段选择 (a)重叠区域中的节点 (b)成员节点之间的碰撞

簇头选举过程如图5所示，空闲网络收到汇聚节点的通知信号后开始网络分簇。每个节点计算y1，然后广播它。在接收到其他节点的信息后，节点通过传统的到达时间(TOA)或接收信号强度指示(RSSI)算法(相邻簇头之间的距离也可以通过能量较大的RSSI算法或距离向量(DV)跳跃算法来计算)来计算自己与其他节点的距离，并计算总权重W，并将其广播。每个节点判断其权值是否最大。如果是，则声称它是簇头。如果没有，请等待其他节点广播。假设没有从其他节点接收到广播信息。在这种情况下，通信范围内的权重最大的节点已成为非通信范围内的其他节点的簇成员。其余节点排除当前最大权重节点，重复上述操作，直到分簇完成。当分簇完成时，如果一些节点由于放置位置等原因而无法分簇，则会分别对这些节点进行分簇。

图5  簇头选举流程

2. 基于分簇的水声网络低时延调度MAC协议

（1）簇内MAC协议

基于非均匀流量分簇（BNC-MAC）簇内调度的MAC协议的基本思想如图6所示，其中蓝色代表发送，紫色代表接收。本文希望通过调整不同信号的发送时间来缩小间隔。一方面，延迟发送部分RTS信号，不仅不影响本轮数据的发送时间，而且节省下来的空闲时间可以用于上一轮的数据。由于只需要簇头节点接收数据报文，因此无需考虑簇成员节点之间的DATA接收冲突。同时，如图7所示，可以发现CTS包与RTS包和DATA包没有冲突。并且根据中心化网络的特点：1）CTS包可以给出本轮的结束时间；2）CTS包可以根据上一轮的接收情况判断是否需要重传。这样，通过修改常规CTS包的格式就可以省略ACK。

图6  无间隙调度的基本思想

图7  无冲突说明

本文将每一轮划分为周期信号阶段和非周期信号阶段。在周期信号阶段，节点向簇头发送周期信号和RTS信号。这里，RTS信号不仅是握手的开始，而且还包含关于节点是否具有突发信号以及该信号的大小的信息。在非周期信号阶段，簇头节点根据以下两点设置CTS包的内容：1)是否需要重传周期信息；2)必须接收多少非周期信息。簇头根据上述信息设置各节点的定时器时长，并通过CTS报文发送。之后，各成员节点根据CTS报文设置定时器，发送非周期信号，知道下一轮的时间，定时器设置为

图8  协议流程

（2）簇内部和簇之间的切换调度

本文希望在不影响簇内通信的情况下实现簇间通信，因此采用以下策略。由于节点不能同时接收和发送信号，希望簇之间的RTS不要与簇内的CTS发生冲突。考虑到簇头节点在CTS包之后有一个间隙，希望RTS包在这段时间到达。因此，本文在簇间通信时调整以下两点。

1）报文发送时间：设置发送簇头节点的发送定时器，公式如下：

通过上述定时器的设置，不影响接收节点的新一轮簇内通信，进一步提高了信道利用率。

2）自有CTS包信息：

a) 发送节点：发送节点在发送之前会通过CTS包设置簇中的通信调度。通过判断信息的长度来决定是否设置成员节点的定时器。

b) 接收节点：由于接收节点可以同时接收簇内和簇间不同频段的信息，因此考虑簇间信息的时间小于簇内周期和簇间信息的时间长于簇内周期这两种情况的调度策略。

（3）簇维护

一个合格的网络需要考虑鲁棒性，以进一步延长网络的寿命。本文设计了空闲节点的加入分簇策略。当一个空闲节点处于另一个簇簇头的通信范围内时，它可以通过如下的“三轮循环”策略加入一个新的簇，而不影响原来的簇内通信。

第一轮循环：空闲节点监听来自簇头的信息。在网络分簇阶段，计算簇头节点和簇内成员节点的传播时延，并记录在CTS包的定时器设置中。因此，空闲节点在收到CTS包后，可以通过读取CTS包中的信息来记录簇头节点与簇内成员节点之间的传播时延。由于不进行时间同步，簇节点需要计算簇头与自身之间的传播时延。

第二轮循环：空闲节点根据第一轮获得的信息设置一定的定时器，并在第二轮发送RTS包。簇头收集信息的时间应满足以下要求，以避免信息冲突：

也就是说，使空闲节点的RTS包到达图9中红圈处。

图9  协议流程

第三轮循环：由于簇头节点在第二轮CTS包发送后收到了申请加入簇的空闲节点的RTS信息，因此簇头节点可以将空闲节点标记为成员节点。第三轮，簇头节点会在CTS包中设置新节点的定时器，改变其他节点的定时器，并通过CTS包向全网广播。至此，新节点已成功加入簇。