CT-TDMA：水下传感器网络高效TDMA协议

洪璐，洪锋，李正宝，郭忠文

（中国海洋大学 信息科学与工程学院 计算机科学与技术系，山东 青岛 266100）

1 引言

水下无线传感器网络（UWSN, underwater sensor networks）将采集到的海洋环境数据发送给用户来辅助决策，在环境监测、资源勘探、灾害预警和潜艇探测等民用和军用领域均具有广阔的应用前景[1～3]。

UWSN的重要特点是，主要通信方式只能采用水声通信。这是因为高频无线信号会被海水吸收，光信号也会因海水散射和反射而大量损耗，两者均不能满足水下长距离通信的要求。与无线电信号相比，水声通信的主要特点是：传播时延大，水声信号的传播速率仅为1 500m/s；通信距离长且带宽低，通信距离一般在1～10km级别，通信带宽仅在10kHz级别；误码率高、多途现象和多普勒频移现象均会导致传输错误[4,5]。

由于水声通信的传播时延高和通信距离长，发送端无法判断信道是否冲突；同时，由于低带宽和误码率高的特性，使得 UWSN中每次通信的分组长度必须受到限制。因此，解决UWSN的MAC问题的关键在于接收端判断冲突是否发生。

目前，国内外的研究者在UWSN的MAC问题上展开了深入的研究，主要包括接入竞争控制协议和无冲突接入协议2种。接入竞争控制协议，通过以接收端为中心的虚拟载波监听协议来解决 MAC问题[6～10]，但由于水声通信的时延长，虚拟载波监听的握手机制降低了数据通信时间的比例，导致网络流量较低。

无冲突接入协议主要采用时分复用接入（TDMA），即采用集中式的方式来向 UWSN内各个节点分配通信时间片[11～14]。此类协议可根据数据传输完成需要的时隙数分为2种。第一种TDMA算法要求，一跳范围内的数据传输必须在一个时隙完成，称之为单时隙协议[11,12]。单时隙协议的主要问题在于，为了保证不同距离的节点对在一个时隙内均能完成通信，时隙必须由最大的链路时延决定。时隙的长度是发送帧时和网络中最大链路时延之和，该问题同样影响了网络流量的提高。

为了提高网络流量，研究者提出了允许跨时隙完成数据传输的ST-MAC协议[13]。该协议假设所有的链路时延都是帧时的整数倍，利用启发式规则完成多跳网络的时隙分配，实现了较高的网络流量。

基于时隙的分配本质上是分配各个节点的发送时刻。如果能不采用按时隙分配，而直接在连续时间轴上对每个节点分配发送时刻，将更好地利用UWSN网络中同一接收节点与不同发送节点之间链路时延的差异性，降低接收帧之间的空闲时间，提高网络流量。因此，本文提出了以连续时间分配为出发点的水下传感器网络的 TDMA协议（CT-TDMA, continuous time based TDMA）。

CT-TDMA的核心思想是，每个节点利用收集到的局部网络拓扑信息，以自身的发送行为可能引起的冲突为依据，分布式地计算局部冲突状态图（LCG, local conflict graph）。所有节点按照启发式规则计算自己的优先级，然后根据 LCG图中的所有邻居的优先级顺序完成发送时刻的标定。优先级计算的启发式规则综合了节点的度、负载和链路时延等重要因素，在有效缩短连续时间轴上时刻分配问题的计算时间的同时，保证了 TDMA协议的流量和端到端时延等性能指标。

本文的主要贡献如下。

1) 针对水下传感器网络在MAC层设计上的独特问题——同一接收节点与不同发送节点之间链路时延的差异性不可忽略，设计了以发送端为中心以连续时间为计量单位的冲突状态模型——局部冲突状态图。在此基础上，本文提出了分布式的局部冲突状态图构建算法：每个节点利用以通信半径和干扰半径之和为半径的覆盖圆内的网络拓扑信息，分布式计算局部冲突状态图。

2) 提出了基于启发式规则的水下传感器网络TDMA协议，即节点以其局部冲突状态图为分配依据，以节点的度、负载和链路时延计算优先级，按照优先级顺序进行发送时刻标定。该启发式算法有效缩短了连续时间轴上时刻分配问题的运行时间。

3) CT-TDMA协议采用基于连续时间的接入分配算法，与基于时隙的 TDMA协议相比，缩短了目的端的接收帧之间的空闲时间，提高了接收端的信道利用率及整个网络的流量。模拟实验证明：在实验时间段内，CT-TDMA方案与以ST-MAC为代表的TDMA方案相比，网络流量提高了20%，数据分组的端到端时延降低了18%；与由全局知识所计算出的最优分配策略相比，网络流量达到了80%，数据分组的端到端时延仅延长了12%。

本文其余部分组织如下：第2节对CT-TDMA设计方案进行详细介绍；第3节分析CT-TDMA的仿真实验结果，第4节概述近几年UWSN的MAC问题的相关研究成；第5节是结束语。

2 CT-TDMA设计

本节首先通过示例说明CT-TDMA的设计出发点，进而对基于连续时间的冲突状态模型——局部冲突状态图进行了详细说明。其次详细介绍CT-TDMA的执行过程，并给出关键函数和过程的伪代码描述。然后讨论了CT-TDMA中用于判断节点接入优先级的启发式规则。最后，结合实例来展示CT-TDMA的运行过程和运行结果。

2.1 设计出发点

解决UWSN的MAC问题的关键在于，唯有接收端才能判断数据分组冲突是否发生。如图1(a)所示，节点A和B向节点C发送数据。设DAC和DBC为链路AC和BC的传播时延且DAC＜DBC，T为数据分组发送时间即帧时，ta和tb为节点A和B的传输时刻。

在陆地传感器网络中，由于无线电信号的传播时延可以忽略，因此TDMA方案的时隙长度为T。只要由发送端A和B选择不同的时隙发送即可避免冲突。然而，UWSN的链路的传播时延不可忽略，为了保证相邻时隙发送的帧无冲突，在本例中时隙长度至少为DBC+T。因此，接收端C接收到的帧序列在时间轴将变得稀疏，如图1(b)所示。

图1 TDMA不同策略下的发送时间的分配

而理想的TDMA效果应如图1(c)所示，A选择ta时刻发送数据帧，则该帧到达C的时刻为ta+DAC。为使得C接收到的帧序列间的空闲尽可能小，那么B发送的帧到达C的时刻应为ta+DAC+T（即A发送帧的帧尾和B发送帧的帧头相接），所以B节点的发送时刻应为tb=ta+DAC+T-DBC。

图1给出了UWSN网络的普通拓扑情况。该例说明基于连续时间的接入分配相比于基于时隙的TDMA方案，能够提高接收端的流量。基于连续时间的分配充分利用了UWSN的链路时延长和数据分组短的特性，这正是CT-TDMA设计的出发点。

2.2 连续冲突状态模型

为了清晰地描述CT-TDMA的连续冲突状态模型，本节首先对运行环境做一些基本设定。

1) 使用圆型通信和干扰模型，即节点的通信范围和干扰范围都是一个以自己为圆心的圆。网络中节点都是同构的，具有相同的通信半径 RT(transmission radius)和干扰半径RI(interference radius)。传感器网络中的干扰半径 RI是对节点信号的干扰覆盖范围的一种描述：当源节点进行发送时，以源节点为圆心、RI为半径的覆盖圆内的所有节点都由于源节点发送数据所带来的干扰，而不能正常接收来自其他节点的数据分组[15,16]。RI在网络部署前进行测定，并与通信半径一样作为协议的初始化参数进行设定。

2) 节点通过时钟同步算法，保证足够的同步精确度。

CT-TDMA的连续冲突状态模型包括局部冲突状态图和禁止时间计算规则。其关键术语的定义如下。

定义1 覆盖范围函数Cov(N, R)：以节点N为圆心，以R为半径的区域。如节点N(xn, yn)通信范围 Cov(N, RT)={(x,y)|(x-xn)2+(y-yn)2≤RT2}；干扰范围Cov(N, RI)={(x,y)|(x-xn)2+(y-yn)2≤RI2}

定义 2 求取某区域内的节点集的操作 Nodeset(C)：C为水下传感器网络的某个部署区域，操作返回属于该区域的节点集，即Nodeset(C)={N| (xn,yn)∈C}。

定义 3 冲突：节点不能够同时发送和接收，不能够同时接收2个以上的数据分组，所有违反这2条原则的发送和接收均称为冲突。以图2为例，如果i和j的信号同时到达k，k将无法正常接收i的数据分组；如果i的信号到达k时k正在发送，k也无法正常接收i的数据分组，此2种情形均称为冲突。

定义 4 冲突邻居、冲突目标节点：节点之间的冲突关系是网络物理拓扑和逻辑拓扑的直接反映。设N为网络中的任一发送节点，节点N的发送操作对周围节点可能造成的冲突主要表现在：对于不同于N的节点M而言，如果存在节点P，满足P的位置在物理拓扑中位于M和N其中一个节点的通信范围内，同时位于另一节点的干扰范围内，并且，在逻辑拓扑中存在链路N-＞P或者M-＞P，那么P节点在接收N或者M其中一个节点的数据分组时，可能会受到来自另一节点的发送信号的干扰而无法接收，即在P点形成冲突。

对于节点N来说，其干扰范围内的所有邻居都有可能由于节点N的发送而成为冲突发生点。因此，节点N的冲突目标节点和冲突邻居定义如下：

当节点P、M同时满足下列拓扑条件时，节点P是节点N的冲突目标节点，节点M是节点N的冲突邻居：

① 物理拓扑条件：

P∈Nodeset(Cov(N, RT)∩Cov(M, RI)) ||

P∈Nodeset(Cov(N, RI)∩Cov(M, RT))

② 逻辑拓扑条件：(N-＞P) || (M-＞P)

该定义说明，节点的冲突邻居必位于它的(RI+RT)的覆盖范围内。如图2中，节点k处于节点i的通信范围和节点j的干扰范围内，同时链路i-＞k存在，因此节点j是节点i的冲突邻居，节点k为相应的冲突目标节点。对于节点n来说，节点n和节点i相距较远，且两者的通信范围和干扰范围的交集范围内不存在节点，因此不满足上述定义中的物理拓扑条件，所以节点n不是节点i的冲突邻居。

图2 节点i的局部网络拓扑结构

定义5 局部冲突状态图（LCG，local conflict graph）：节点i的冲突状态图是一个以节点i为中心的带权多重图，描述所有和i的发送行为有关的冲突。LCG中的顶点为i及其所有的冲突邻居。LCG图中边的权值定义为：如果节点j为节点i的冲突邻居，其冲突目标节点为k，且链路ik和jk的时延分别为Dik和Djk，则边i-j的权值为

为了表达式的一般性，定义 Dii=0。

Wij(k)用来描述节点i和节点j发送的数据在接收点k产生冲突的状态。Wij(k)取正值表示，如果节点i选择比节点j早Wij(k)的时间进行发送，则会在k产生冲突。相应地，如果Wij(k)为负值，表示节点i选择比节点j晚|Wij(k)|的时间进行发送时会产生冲突。由于节点的所有冲突邻居均位于该节点的LCG中，因此冲突邻居也就是节点的LCG邻居。

以图2为例，节点k是节点i和节点j的冲突目标节点，那么节点i的LCG图中存在边i-j，权值为 Wij(k)=Dik-Djk=-0.2。其含义为：如果节点 i选择比节点j晚0.2s进行发送，则在节点k将同时接收到节点i的发送信号和节点j发向其他节点的数据信号的干扰能量，从而发生冲突。

对于节点i和节点k来说，Nodeset(Cov(i,RT)∩Cov(k, RI))={i , k}，并且仅链路i-＞k存在，由定义4可得，节点k既是节点i的冲突邻居，也是节点i和节点k冲突的目标节点，且Wik(k)=Wik-Wkk= 3.2。这说明如果节点i选择比节点k早3.2s进行发送，那么当节点i的数据信号到达节点k时，节点k正在向其他节点发送信号，无法接收节点i的数据，产生冲突。

再分析节点i和节点 f的冲突情况，由定义4的物理条件得到，Nodeset(Cov(i, RT)∩Cov(f, RI))={i,k, f}。由于链路i-＞f不存在，根据定义4的逻辑拓扑条件，f不是冲突目标节点。该论断的含义是，f不接收i的数据分组，因此i发送的信号到达f时，f可以进行发送，即在f节点处不会产生i和f的冲突。但是链路i-＞k存在，说明k是i和f的冲突目标节点，其含义是i和f的信号可能同时到达节点k。同时，链路f-＞i存在，说明i同样是i和f的冲突目标节点，其含义是i在接收f的信号时，不能向其他节点发送数据。因此节点 i的 LCG图中， i和f之间存在2条边，其权值分别为Wif(k)=Dik-Dfk=-2.2和Wif(i)=Dii-Dif= -4.5。

定义6 禁止时间：节点的禁止时间是指在时间轴上的一个时间片段内，节点不能够选择发送时刻，否则会引起冲突。

为保证2个节点的帧到达目标时不冲突（即在接收端的时间轴上不重叠），对每个发送节点来说均有一段时间不能发送，称为禁止时间。以图3为例，在节点i的LCG中，如果其邻居j选择发送时刻tj，则由节点j决定的节点i的禁止时间定义为(Fl(i,j, k)，Fr(i, j, k))。其中

禁止时间的物理含义为，由于节点j的存在和其发送时刻tj的确定，节点i在(Fl(i, j, k)，Fr(i, j, k))时间段内不能发送数据帧。如图3所示，如果节点i选取的发送时刻大于Fl(i, j, k)，i发送的帧尾将与j发送的帧头在相关接收点k产生冲突；当i选取的发送时刻稍小于Fr(i, j, k)，i发送的帧头将与j发送的帧尾在相关接收点k产生冲突。

图3 禁止时间的计算

以图2中的节点i和j的冲突为例，Wij(k)= -0.2，假设节点j选择第2s发送(tj=2)，帧时T=1s，则根据式(2)和式(3)可得节点j给节点i带来的禁止时间为(1.2, 3.2)。以节点i和f为例，根据前面的分析，冲突状态图中边i-f的权值有2个，因此假设f选择0s开始发送，根据公式计算出的f给i带来的禁止时间也是2段，为(3.5, 5.5)∪(1.2, 3.2)。

2.3 CT-TDMA的主要算法

本节首先介绍局部冲突状态图的生成过程，然后介绍CT-TDMA的算法流程。CT-TDMA可以适用于任何网络拓扑结构，但为了简化说明，本节针对最广泛使用的树形拓扑结构进行介绍。

2.3.1 LCG生成算法

在初始化阶段，每个节点i收集Cov(i，RT+RI)范围内的邻居节点的地理位置信息和逻辑链路信息，并计算其冲突区域内所有节点对的信号传播时延，得到以该节点为中心的局部网络拓扑结构。对于位于节点通信半径之外的邻居，节点通过多跳传输的方式获得其对应邻居的相关信息。在计算得到Cov (i，RT+RI)内的局部网络拓扑结构后，节点运行createLCG()函数，按照定义5中给出的规则生成自己的LCG。

利用定义4验证j是否是i的冲突邻居。PTC()和 LTC()函数用来对节点是否符合冲突的物理拓扑条件(physical topology condition)和逻辑拓扑条件(logical topology condition)进行判定。针对每一个邻居j进行分析：如果存在某个节点k，使得k、j符合冲突的2个条件，满足节点j是节点i的冲突邻居，k是 i和 j冲突的目标节点，则计算Wij(k)=Dik-Djk，并记录到i的LCG中。

算法1 createLCG ()

令V(i)是节点i的所有Cov(I, RT+RI)内的邻居节点的集合，SLCG(i)为 i的冲突状态图内所有的边的权值集合，算法1描述了节点局部冲突状态图的生成过程。

以图2的拓扑为例，节点i运行createLCG()算法后，生成的LCG如图4所示。根据前面的分析，节点f和i冲突的目标节点有2个，根据定义5计算出边i-f有2个权值，因此在局部冲突状态图中体现为具有不同权值的多重边。如果2个节点对会在多个节点处产生冲突，则LCG图中这2个节点对之间就会有多重边，且多重边的个数即为冲突目标节点的个数。因此，由于节点冲突的多样性，LCG为带权的多重图。

图4 节点i的局部冲突状态图（LCG）

2.3.2 CT-TDMA算法流程

每个节点生成自己的LCG图后，就根据由LCG图每条边所对应的各个禁止时间，来选择自己的发送时刻。即选择和所有禁止时间不冲突的最早时刻，作为自己的发送时刻。

但是，当前节点的发送时刻的确定，取决于其LCG邻居的发送时刻。CT-TDMA采用优先级和随机选择相结合的方式，安排节点的发送时刻标定顺序。即优先级最高的节点最先选择发送时刻，选择的基本策略是在所有可用的时间段内选择一个最早的时间点（选择的过程称为标定）。如果 LCG图中所有未标定节点的优先级相同，各个节点随机选择发送时刻。优先级的计算方法，将直接影响CT-TDMA的执行效率。本节先介绍CT-TDMA的算法流程，而计算优先级的启发式规则将在 2.3.3节中进行讨论。

CT-TDMA的完整算法流程包括以下7步。

1) 节点生成自己的LCG并计算自己的标定优先级。

2) 每个节点向所有的LCG邻居广播自己的标定优先级，并将自己的状态置为“unlabeled”。然后，每个节点以分布式方式运行3)～6)步。

3) 如果当前节点在其LCG图中的所有未标定邻居中拥有最高的优先级，则节点根据由 LCG得到的所有禁止时间段，选择最早的可发送时刻作为自己的发送时刻，并将其广播给所有的LCG邻居，并将状态置为“labeled”。

4) 如果当前节点的所有未标定邻居中存在优先级高于自己的邻居，则等待优先级高的节点先标定，等待接收相关节点的发送时刻结果并更新自己的禁止时间，返回第3)步。

5) 如果当前节点在其LCG图中与其他未标定的节点拥有相同的优先级，则该节点在时间轴上除禁止时间之外的时刻随机选择其发送时刻，并广播给所有同优先级的未标定状态的LCG邻居。

6) 随机标定的节点选定发送时刻并与所有同优先级邻居交换选定结果后，运行Judge()函数判断是否会产生冲突，若无冲突，则置为“labeled”，否则置为“unlabeled”，并返回第5)步。

7) LCG图中的所有节点状态均为“labeled”时，算法结束。

算法2 Label()

节点使用Label()函数实现标定功能，即上面的3)～6)步，Judge()函数被 Label()调用，用来判断一次随机选择时间以后是否会产生冲突。在随机标定中，节点获得邻居随机选定的时刻后仍然使用定义6计算禁止时间。Judge()函数判断冲突的方式是，如果节点自己随机选定的时刻处于计算出的“禁止时间”之内，则认为会产生冲突，此次随机标定即作废，节点及其邻居重新进行随机标定。

定义 Sc(i)为节点 i的已经标定的 LCG邻居集合，Suc(i)为节点i的所有未标定的LCG邻居的集合，ST(i)为节点i的标定状态(labeled或unlabeled)，P(i)为节点i的标定优先级。算法2和算法3分别给出了Label()和Judge()函数的伪代码描述。

在Label()函数中引入随机标定的设计，是因为在某些网络中可能存在大量节点的优先级相同。虽然可以采用节点 ID等强制优先级方式，但类似的优先级策略对优化最终的总传输时间没有帮助。随机标定可以减少算法的执行时间。比如，在极端的网络拓扑条件下（如线形、星形），当节点的优先级均相同时，顺序标定算法的时间复杂度为 O(n)而随机标定的时间复杂度为O(logn)[17]。其中，n为网络中的节点个数。

算法3 Judge()

2.3.3 标定优先级确定

在 UWSN环境下，对于所有节点的连续时间的接入分配，等价于一个连续轴上的分布式着色问题，因此确定最优全局分配策略是 NP-hard问题。于是，在上一小节介绍的CT-TDMA算法流程中，使用了按照优先级顺序进行标定的算法。这样，优先级的确定直接影响CT-TDMA算法本身的执行效率。本节对优先级的计算方法进行详细说明。

CT-TDMA的算法目的是提高网络流量，即所有节点均发送一次数据所使用的总时间越短越好。针对这个设计目标，提出重要性依次降低的3条启发式的优先级制定规则如下。

1) 在冲突状态图中拥有最大度的节点应该优先分配发送时刻。节点的度越大意味着它潜在的冲突节点越多。度最大的节点首先分配发送时间，可以使受其影响的大量节点的禁止时间尽可能地靠前，从而缩短最后算法选定的总时间。

2)负载较重的节点优先发送。负载较重的节点优先发送有助于缩短每个分组端到端的平均时延，实现网络的公平性。

3)网络中拥有较大链路时延的节点优先发送。时延较高的链路如果发送的较晚，到达目标时的时间就会更晚。而优先分配时延较高的链路，使得高时延的链路早发送，低时延的链路晚发送，有助于提高节点的传输并行度。

以上述3条启发式规则为依据，可以实现定量计算节点的优先级指标。P(i)表示节点i的标定优先级，采用式(4)进行计算。式(4)中使用的主要变量定义为：di为i在它自己的LCG图中的度，Lmax为节点缓冲区的大小，Li为节点i的缓冲区队列长度。定义从节点 i到基站的传输路径上的下一跳节点 k为节点i的父节点，Dik为节点i到其父节点k的链路传播时延。定义Dmax是整个网络中的最大的链路传播时延，即网络中距离最长的一跳链路长度与水声信号的传播速度的比值，该值在网络部署时可以进行估计并设定在所有节点中。由于CT-TDMA协议运行的环境为静态网络，该值在协议运行过程中不会改变。而且，该值仅涉及到优先级的计算，对于所有节点的计算效果是等价的，因此该值的估计精度对于本文提出的CT-TDMA协议的运行效果没有直接影响。

3条启发式规则的重要性在式(4)中直接体现：拥有最大度的节点拥有最高的标定优先级；如果节点的度相同则负载较重的节点优先级高；如果节点的负载也相同，则拥有最长链路时延的节点优先级高。当网络的拓扑结构，节点负载等条件不发生变化时，网络可以根据CT-TDMA计算出的调度顺序持续的运行。而当网络拓扑结构或者节点负载等条件发生变化时，即节点的标定优先级发生变化时，协议将在整个网络重新运行，以保持节点的发送时间分配始终为当前的最优策略。

2.4 算法实例

为了清晰地说明CT-TDMA的基本思想、工作流程及特点，本节给出一个简单的网络实例进行说明，如图5(a)所示。链路上的标记为该条链路的时延（单位为s），设帧时T为1s。

各节点首先运行 createLCG()函数生成自己的局部冲突状态图，4个节点的LCG如图5(b)所示。

图5 CT-TDMA的执行过程(实线表示逻辑链路，虚线表示点到点之间的时延)

然后，所有节点计算自己的优先级。在图5(b)中4个节点的度相同，在所有节点产生数据分组的频率相同的情况下，对于A节点来说，它不仅要发送自己的数据分组，还要转发来自 B和 D的分组，A节点的缓冲区队列长度必将比B、C、D节点的更长，因此A节点的负载最重，优先级最高。B、C、D负载相同，因此按链路的时延排序，相关链路时延高者优先级高，最终标定顺序为 A、B、D、C。

因此，A首先选择0时刻并广播给B、C、D。B根据公式计算出A对B的禁止时间为(-3.9, -1.9)∪(-4.5, -2.5)，所以B也可选择0时刻。D根据A和B的标定结果，计算A和B对自己的禁止时间为(-5, -3)∪(-1.5, 0.5)，于是D选择自己的发送时刻为0.5。最后，C计算A、B、D对自己带来的禁止时间为(-2.7, -0.7) ∪(0.2, 2.2) ∪(-0.8, 1.2)，C 选择自己的发送时刻为 2.2s。4个节点的正数禁止时间在图5(c)中给出。禁止时间的负数部分不影响节点发送时刻的选择，故未给出。最后，A、B、C和D 4个节点分别确定自己的发送时刻为 0s、0s、2.2s和0.5s。

本例说明，CT-TDMA提高了数据发送的并行度。例如，A和B节点都在0时刻发送而不会冲突，这在传统的WSN中是无法实现的。UWSN正是由于传播时延高、通信距离长和数据分组短，导致了不同发送节点的数据分组到达接收端的时刻存在差异。CT-TDMA利用UWSN的这种特性，避免了冲突，提高了网络中数据传输的并行度，达到提高网络流量的目的。

3 仿真

本节介绍CT-TDMA的仿真结果，并对算法的性能进行分析和对比。使用了MATLAB等软件对算法进行了仿真，在仿真过程中，帧时T设定为1s，节点的通信半径为3 000m，干扰半径为3 500m，网络包括从5个节点到60个节点的4种规模。根据网络规模的变化，节点被部署在最大 12km×12km的范围内，通过随机部署的方式，利用部署密度限制节点和邻居节点之间的距离在450m到3 000m之间。因为水声信号的速度为1 500m/s，所以网络中链路的时延被控制在0.3s～2s之间。

由于网络拓扑结构对节点的传输并行度有重要影响，因此对比了一般的网络拓扑结构（节点随机投放并自组织成树形拓扑结构），以及特殊的星形、线形和网格，共4种拓扑结构对算法的影响。在4种拓扑结构下，均采用4种网络规模完成了16组实验。在仿真中使用平均每秒钟整个网络发送的有效信息量作为评价网络流量的指标，即节点发送的数据信息字节数。ST-MAC帧长度为 45byte[13](40byte有效数据)，CT-TDMA的帧长度为105byte(100byte有效数据)。在仿真中模拟了4种不同的接入分配算法。

1) Optimal: 实验网络部署情况下的理论上最优的分配策略，该策略能够最大限度地利用信道和提高节点的传输并行度，为其他算法提供理论的最佳上界。最优策略的求解，即针对实验环境下的网络拓扑，在所有可能的节点接入方案中，选取全部节点的一轮接入时间最短的接入方案。

2) CT-TDMA: 本文提出的分配策略。

3) ST-MAC: 文献[13]提出的跨时隙TDMA分配策略。

4) S-TDMA: 传统的UWSN单时隙TDMA。

图6中对比了4种调度算法在4种不同网络拓扑结构下的流量情况。可以看出，网络拓扑结构对流量有明显的影响，线形、树形、网格到星形网络流量依次降低，这是由于随着拓扑的变化节点的密度逐渐增加，即共享同一个信道的节点数目越来越多，因此能够同时并行传输的节点数目就变得越来越少。除星形拓扑之外，在其他拓扑结构和协议下，网络流量均随着网络规模的增加而增加。星形拓扑结构表现特殊的原因是，在该环境中所有节点均一跳传向基站，因此任意2个节点均互为冲突邻居，所有的节点共享同一个信道，无法提高数据传输的并行度。

图 6显示，当网络规模较小时，CT-TDMA和ST-MAC均能够达到或接近理论最优的效果。当网络规模逐渐增大时，CT-TDMA和ST-MAC的流量均不能达到理论最优值，但CT-TDMA的性能始终优于ST-MAC（平均高20%以上），并达到理论最优值的 80%左右。而 S-TDMA的表现最差，因为该方案较长的时隙给接收端带来大量空闲时间。

CT-TDMA优于 ST-MAC的原因在于，ST-MAC采用时隙调度策略为节点分配发送时间，这种策略规定节点只能在每个时隙的开始时刻发送帧。此外，ST-MAC要求所有链路时延是帧时的整数倍。为了确保这一点，ST-MAC协议中的分组长度必须尽可能小，进一步引起帧中有效数据比例下降。其原因是，虽然帧长度缩短，帧中的校验和确认位并不减少。CT-TDMA采用连续时间分配策略，并不需要ST-MAC的上述设定，因此可以应用更长的数据帧，从而提高了网络流量。

图6 4种协议在不同网络规模和拓扑结构下的流量对比

图7记录了4种协议在一般网络情况即树形拓扑结构下的端到端时延情况。传感器网络的数据传输模式为所有的节点向基站传输数据，因此端到端时延即为数据分组从源节点到基站的传播时延。从图7可以看出，随着网络规模的增大，节点到基站的平均跳数增加，端到端时延也相应增加。由于CT-TDMA使用了连续时间分配策略，在接收节点处缩短了帧与帧之间的空闲时间，提高了传输效率，其平均端到端时延比ST-MAC降低了约18%，并且只比理论最优策略的时延高 12%。可见，CT-TDMA不仅网络流量要高于传统协议，平均的端到端时延也更低，实时性更好。

图7 4种协议的平均端到端时延

从计算代价的角度分析，ST-MAC为集中式算法，需要从所有的全局调度方案中寻找最优方案，而CT-TDMA采用分布式的调度策略，每个节点的计算代价都比 ST-MAC小很多，因此计算时间更短。从能量消耗的角度分析，ST-MAC和CT-TDMA均属于 TDMA协议，数据传输阶段没有冲突，因此能量效率都很高。额外的能量消耗仅在于协议的初始化阶段，ST-MAC需要基站收集全网络的信息和分发调度策略，CT-TDMA仅需要各个节点与其Cov(RI+RT)范围内的邻居进行信息交换。当网络规模急剧增大时，ST-MAC洪泛和广播的通信开销要远大于CT-TDMA的分布式信息交互。

4 相关工作

近年来，UWSN的MAC问题由于水声通信的独特特点引起广泛关注。相关研究成果可分为基于竞争的接入控制协议和无冲突的接入协议2类。

接入竞争控制协议，通过以接收端为中心的虚拟载波监听协议来解决 MAC问题。文献[9]使用RTS/CTS握手机制来建立信道预约。节点通过截获邻居信息的方式计算各个邻居节点的忙时间，然后在这段时间内停止侦听信道。文献[6]研究了水声信道特征对Aloha协议的影响，进而提出水声通信的冲突状态具有时空不确定性的特点。文献[8]和文献[10]基于 Aloha协议，使用一个短帧来预约信道，避免数据分组的冲突。T-Lohi协议[7]针对水声信道冲突的时空不确定性设计了一个特殊的退避算法，在高负载的环境中具有较高的流量。

无冲突的接入协议基于TDMA和CDMA。针对UWSN设计的TDMA协议分为单时隙和跨时隙2种，单时隙协议要求一跳范围内的数据传输必须在一个时隙完成。UWAN-MAC[11]允许节点随机地选择时隙进行传输。文献[12]提出的混合协议将TDMA和竞争协议相结合，充分利用了竞争协议时延较低而TDMA流量较高的优点。

跨时隙的协议允许使用多个时隙完成数据分组传输。最近提出的ST-MAC[13]是第一个跨时隙的TDMA协议，该协议以整个网络的冲突状态图为基础，采用集中式算法计算各个节点的最优发送时隙。ST-MAC需要收集全局信息并且假设网络中的任意链路时延都是发送帧时的整数倍，通过分配时隙的方式，使得不同节点的帧到达目的端的时隙不相同（即不会产生冲突）。该协议的时隙长度比传统协议要短的多，利用链路时延的差异性减少了接收帧之间的空闲时间，与传统的单时隙的 TDMA相比提高了网络流量。本文提出的 CT-TDMA和ST-MAC相比，不依赖于时延与帧时关系的假设，并且采用连续时间的分配方式代替时隙分配，减少了信道空闲时间，提高了网络流量。

除了 TDMA之外，研究者还提出了针对水下环境的改进CDMA协议[18,19]，文献[19]提出的混合协议使用对节点分簇的策略，簇内节点通信使用TDMA协议，不同的簇之间的节点通信则使用CDMA协议。然而目前在UWSN中使用CDMA协议还面临很多困难，对大规模的传感器节点分配伪随机码是一项艰巨的挑战，此外，水声通信中使用CDMA的远近效应问题也没有得到很好地解决[18]。

5 结束语

针对水下无线传感器网络时延高、带宽低和误码率高的特性，本文提出了以发送端为中心以连续时间为计量单位的冲突状态模型——局部冲突状态图（LCG）及其分布式构建算法，并在此基础上设计了基于启发式规则的水下传感器网络 TDMA协议。CT-TDMA利用UWSN中同一接收节点与不同发送节点之间链路时延的差异性，与现有协议相比进一步减少了节点接收帧序列的空闲时间，提高了网络流量。并且，基于启发式规则的分配算法，有效缩短了节点在连续时间轴上进行时刻分配的运行时间。仿真表明，与ST-MAC和S-TDMA等基于时隙分配的水下传感器网络 TDMA协议相比，CT-TDMA能够实现更高的网络流量和更低的端到端传播时延。

[1] 李建中, 高宏. 无线传感网络的研究进展[J]. 计算机研究与发展,2008,45(1): 1-15.LI J Z, GAO H. Research progress of wireless sensor networks[J].Journal of Computer Research and Development, 2008,45 (1): 1-15.

[2] 李瑞芳, 李仁发, 罗娟. 无线多媒体传感器网络 MAC 协议研究综述[J] . 通信学报, 2008,29 (8): 111-123.LI R F, LI R F, LUO J. Research review on MAC protocols of wireless multimedia sensor networks[J]. Journal on Communications, 2008.29 (8): 111-123.

[3] HEIDEMANN J, LI Y, SYED A. Research challenges and applications for underwater sensor networking[A]. Proc WCNC[C]. Las Vegas, NV, USA, 2006.228-235.

[4] SYED A, HEIDEMANN J. Time synchronization for high latency acoustic networks[A]. Proc INFOCOM 2006[C]. Barcelona, Catalunya,Spain, 2006.1-12.

[5] HARRIS A F III, STOJANOVIC M, ZORZI M. When underwater acoustic nodes should sleep with one eye open: Idle-time power management in underwater sensor networks[A]. Proc ACM WUWNET[C].Los Angeles, CA, USA, 2006.105-108.

[6] SYED A, YE W, HEIDEMANN J. Understanding spatial-temporal uncertainty in medium access with ALOHA protocols[A]. Proc ACM WUWNET[C]. Montréal, Québec, Canada, 2007.41-48.

[7] SYED A, YE W, HEIDEMANN J. T-lohi: a new class of MAC protocols for underwater acoustic sensor networks[A]. IEEE INFOCOM[C]. Phoenix, AZ, USA, 2008.231-235.

[8] GUO X, FRATER M, RYAN M. A propagation-delay-tolerant collision avoidance protocol for underwater acoustic sensor networks[A].OCEANS 2006-Asia Pacific[C]. Singapore, 2006.1-6.

[9] MOLINS M, STOJANOVIC M. Slotted FAMA: a MAC protocol for underwater acoustic networks[A]. OCEANS 2006-Asia Pacific[C].Singapore, 2006.1-7.

[10] CHIRDCHOO N, SOH W, CHUA K. Aloha-based MAC protocols with collision avoidance for underwater acoustic networks[A]. Proc IEEE INFOCOM[C]. Anchorage, Alaska, USA, 2007.2271-2275.

[11] PARK M, RODOPLU V. UWAN-MAC: an energy-efficient MAC protocol for underwater acoustic wireless sensor networks[J]. IEEE Journal of Oceanic Engineering, 2007, 32(3): 710-720.

[12] KURTIS I, KREDO B, MOHAPATRA P. A hybrid medium access control protocol for underwater wireless networks[A].Proc ACM WUWNET[C]. Montréal, Québec, Canada, 2007.33-40.

[13] HSU C C, LAI K F, CHOU C F. ST-MAC: spatial-temporal MAC scheduling for underwater sensor networks[A]. Proc IEEE INFOCOM[C]. Rio de Janeiro, Brazil, 2009.1827-1835.

[14] HONG L, HONG F, GUO Z W. A TDMA-based MAC protocol in underwater sensor networks[A]. The 4th International Conference on Wireless Communications, Networking, and Mobile Computing(WICOM’08)[C]. Dalian, China, 2008.1-4.

[15] DOWNEY P. The Behavior of a Flooding Protocol in a Wireless Sensor Network[R]. Report for the Honours Programme of the School of Computer Science and Software Engineering, the University of Western Australia, 2003.

[16] LIU YH, LIONEL M. Ni: a generalized probabilistic topology control for wireless sensor networks[A]. INFOCOM 2009[C]. Rio de Janeiro,Brazil, 2009.2776-2780.

[17] LUBY M. A simple parallel algorithm for the maximal independent set problem[J]. SIAM Journal on Computing, 1986, 15(4):1036-1053.

[18] TAN H X, SEAH W K G. Distributed CDMA-based MAC protocol for underwater sensor networks[A]. LCN[C]. Clontarf Castle, Dublin,Ireland, 2007.26-36.

[19] SALVA-GARAU F, STOJANOVIC M. Multi-cluster protocol for ad hoc mobile underwater acoustic networks[A]. Proc IEEE Oceans Conf[C]. San Diego, CA, USA, 2003.91-98.