一种用于水声通信网的全动态TDMA协议

杨 文 李 霞

(东南大学信息科学与工程学院，南京 210096)

水声通信网在海洋信息采集、环境监测、灾难预报、辅助导航、军事监视等领域有着重要的应用［1］.目前，水下通信通常采用声波作为传输媒介，但是水声信道具有长传播延时、可用带宽窄、发送速率低、时变多径复杂等［1-2］不同于陆面无线信道的特性，这使得水声通信网MAC层协议设计面临巨大的挑战.

针对水声网络的特点，许多学者提出了各种不同的MAC协议，主要分为竞争类和分配类［3］两大类.竞争类MAC协议的设计重点在于如何有效地避免碰撞和协调竞争，而分配类MAC协议的设计重点在于如何高效地分配信道资源和防止干扰;两类协议都可以引入合适的能量控制策略.

文献［4］在 FAMA［5］协议的基础上提出了时隙FAMA协议，它综合了CSMA和时隙Aloha协议的基本特点来获得较高的吞吐量，但没有考虑能量有效性问题，并且其吞吐量随节点数目的增加而减少.文献［6］提出了一种分布式节能的MAC协议，它通过有效地减少碰撞次数来达到节能的目的，但只适合工作在均匀分布的低网络负载下.文献［7］提出的R-MAC协议通过RTS/CTS预定方式占用发射时隙，有效地避免了数据包碰撞，但是控制包的较大开销造成带宽和能量利用效率低下.文献［8］提出了一种称为 Tone-Lohi的 MAC协议，它采用Tone预订方式来取代传统的RTS/CTS预订方式，具有吞吐量高且能量节省的优良性能，但性能受网络负载和节点分布密度的影响，特别是对于高负载、低密度的网络，其信道利用率和丢包率之间存在突出的矛盾.

由此可见，用于水声通信网的大多数MAC协议都是在通信效率和能量效率之间进行取舍，而且有些协议的性能还依赖于网络负载或网络规模.由于水声通信的信道环境恶劣，又没有通用的网络结构模型，无法像陆面无线通信一样设计高性能的通用MAC协议，所以应从特定的应用场合出发，选择或设计合适的网络结构模型，再充分利用网络拓扑信息以设计既高效又节能的MAC协议.文献［2］针对沿岸水下监视(underwater littoral surveillance)这一典型应用，设计了一种网络拓扑结构，它适用于狭长或纵深区域监测等场合.本文基于这种网络结构提出了一种全动态TDMA协议(FDTDMA)，并在不同的网络负载下与加入了混合回复和固定睡眠机制的TDMA协议进行仿真比较，结果表明，前者的通信效率和能量效用均比后者高出20%以上.

1 FD-TDMA协议

1.1 协议特点

传统的TDMA协议的时隙是固定分配的，每个节点都只在分配给自己的时隙里发送数据，在其他时间接收数据或者处于空闲状态，其优点是节省能量，缺点是在负载分布不均衡的情况下，大量时隙被浪费，信道利用率低.另外，固定时隙的TDMA协议需要严格的时间同步;同时，网络节点间的最大距离决定各节点的时隙长度，距离差异会导致时间浪费.为保留TDMA协议的优点，同时改进其不足，本文的FD-TDMA协议引入了以下机制:

1)全动态时隙调度 全动态是指每个节点的时隙起点，即进入发送时隙的时间是动态变化的，且占用的时隙长度也是动态变化的.

2)往返调度(round-trip scheduling) 有2个调度方向，且交替循环变化.

3)混合式回复 携带回复(在所发的数据帧中携带对收到数据的确认信息)和专门回复(发确认信息帧)按需使用.

4)保守睡眠 尽量晚入眠且及早醒来，以保证既不耽误时隙调度的进度，也不错过接收来帧.

引入全动态时隙调度机制是为了使协议适应不同的负载情况，且更高效地利用信道资源，而动态调度需要依赖于相邻节点的发送情况，所以调度过程只能在空间上连续进行，因而采用往返调度方式.由于水声信道的长传播延时特性，单独发送回复需要较大的额外时间开销，这直接影响了网络的吞吐量性能，另一方面，为了保证数据交付的效率，应让数据的发送者能在一个往返调度周期内知道数据是否成功传递，所以引入混合式回复机制.睡眠的目的是为了节能，但是为了不影响动态时隙调度的正常推进，因而采用保守的睡眠机制.

1.2 概要描述

FD-TDMA协议的设计基于以下前提假设:

1)节点都采用广播发送方式，且全向发射，但只有相邻节点才能收到.

2)相邻节点所发送的数据帧刚到达本节点，物理层只需再经过一段接收控制帧所需的时间就足以将“有帧到来”的信息通知到MAC层，而不需要等到将数据帧接收完之后.

3)网络是静态的，其参数(包括网络节点数、节点编号、相邻节点间的最大和最小距离等)都在网络工作前已确定.

FD-TDMA协议中，节点所发送的帧包括数据帧(D帧)和控制帧，控制帧又分为回复帧(A帧)和通知帧(I帧).对所有帧，节点都只在自己的发送时隙中发送，而在其邻居节点的发送时隙里接收.各帧的发送规则如下:

1)D帧 所有的数据帧到来后都在缓冲队列中排队，节点进入自己的时隙后再发送.

2)A帧 对收到的数据帧尽早给予回复，即如果本节点从上次退出发送状态到本次进入发送状态这段时间内，收到了发给自己的数据帧，那么在本次发送时隙里将发送所有确认(ACK)信息;若此时本节点没有数据需要发送，则专门发送一个包含所有ACK信息的回复帧(A帧)，若有数据需要发送，则将所有ACK信息携带在D帧中发送.

3)I帧 用于保证网络的时隙调度正常往前推进.如果最近(即与本节点的编号相差1)的前续节点没有发任何帧，且接下来本节点进入自己的发送时隙后也没有D帧或A帧需要发送，则发送I帧以通知其后续节点:时隙调度已经推进到本节点.这也有助于其前续节点尽早进入睡眠状态.

网络的时隙调度顺序如图1所示.在一个往返调度周期中，端节点(0和7)只占用时隙一次，对其而言调度方向不变，而其他节点则2次进入发送时隙，并且2次的调度方向相反.

图1 网络的时隙调度顺序

网络中各节点内部的状态转移过程如图2所示，各节点通过维护自己的状态进程来实现网络的动态时隙调度.节点状态进程的算法如下:

①节点在初始化状态中配置网络参数，初始化等待时间(即相对于当前时刻，将在等待状态中停留的时间)，并初始化调度方向(节点0为反向，其他节点为正向)，再进入等待状态.

②节点在等待状态中根据其前续节点的发送情况，更新等待时间，若收到了最近的前续节点发送的信息，则还需初始化接收时间(即相对于当前时刻，将在接收状态中停留的时间)，而在最后的等待时间过去之后便进入发送状态.

③按上述规则发送D帧、或A帧、或I帧，并在发送之前初始化接收时间，发送后立即进入接收状态;若没有信息需要发送，则不发送任何帧，直接进入接收状态.

图2 节点的状态转移

④在接收状态根据后续节点的发送情况，更新接收时间，而在最后的接收时间过去后，改变调度方向(端节点0和7的调度方向保持不变，其他节点的调度方向相反)，确定睡眠时间(即相对于当前时刻，将在睡眠状态中停留的时间)，进入睡眠状态(只有定时时钟在走，节点无收发功能).

⑤睡眠结束时发生定时中断，初始化等待时间，进入等待状态，执行步骤②.

每个节点都进行着上述状态转移过程，动态并实时地维护着自己的等待时间、接收时间和睡眠时间，而在自己的发送时隙到来(等待时间为0)时进入发送状态.在任意时刻始终只有不多于一个节点处于发送状态，占用了发送时隙，其前续节点和后续节点分别处于接收状态和等待状态，而非邻居节点则处于睡眠状态或者等待状态(由于保守睡眠的缘故).图3展示了在某一时刻网络中各节点所处的状态，如网络调度方向为0，当节点3处于发送状态时，节点1和节点2处于接收状态，节点4和节点5处于等待状态，其他节点处于睡眠状态.

图3 时隙调度过程中某一时刻的节点状态示意图

1.3 算法

要保证全网节点协调、有序、高效地工作，关键在于接收时间tr、睡眠时间ts和等待时间tw的计算.计算这3个时间完全基于1.2节中的3个前提假设，并需确定如下参数:

数据帧单跳最大传输时延为

控制帧单跳最大传输时延为

邻节点距离极差时延为

式中，Dmax和Dmin分别为相邻节点的最大距离和最小距离;Ld为数据帧长度;Lc为控制帧(短帧)的长度;R为发送速率;V为传播速度;δ是为了补偿时钟定时偏差和传播速度的时变性而设的时间裕度.设网络中的节点总数为M，节点编号顺序如图3所示，最大的节点编号为N=M－1.

1.3.1 接收时间tr的初始化与更新

接收时间的初始化是在等待或者发送状态中进行的.如果在等待状态中收到最近(与本节点的编号相差1)的前续节点发送的帧，则接收时间初始化为

设本节点2在等待状态中收到了其最近的前续节点1发送的信息，这时接收时间的初始化要以本节点2进入发送状态后不发送信息这一最坏情况来计算，以保证正常情况下本节点在这个初始化时间内必将收到后续节点的信息.节点2收到节点1的信息后，会作最保守的估计(节点3可能要晚TΔ才收到节点1的信息)，而节点3收到节点1的信息后，也会作最保守的估计(节点2可能要晚TΔ才收到节点1的信息)，所以节点3要在收到节点1的信息后再等(TΔ+Tc)才能判断节点2没发信息，然后进入发送状态发送信息.再过时间Tc后，本节点2就足以收到节点3的信息.所以，节点2在等待状态中收到了其最近的前续节点1发送的信息后将接收时间初始化为TΔ+(Tc+TΔ)+Tc，即式(4).

如果在发送状态发送了D帧，则在发送之前将接收时间初始化为

但是，对于正向调度的节点(N－1)和反向调度的节点1来说，因为其后续节点只有一个，所以接收时间的初始化值更小，即

设本节点2进入发送状态后有数据需要发送，这时对接收时间的初始化要以后续节点3进入发送状态后不发送信息这一最坏情况来计算.本节点2的数据帧从发送开始，经过时间Td后，必将被后续节点3和节点4接收，而节点4收到后会作最保守的估计(节点3可能要晚TΔ才能收到)，所以节点4在收到节点2的数据帧后要再等(TΔ+Tc)才能判断节点3没发信息，然后进入发送状态发送信息，再过时间Tc后，本节点2就足以收到节点4的信息.所以本节点2在发送状态中发送D帧之前，应将接收时间初始化为Td+(TΔ+Tc)+Tc，即式(5).同理，易推得式(6).

如果在发送状态发送了A帧或者I帧，则接收时间初始化为

同样，此时对于正向调度的节点(N－1)和反向调度的节点1来说，接收时间的初始化值更小，即

接收时间的上述初始化可以保证当链路发生局部异常时，节点的状态转移仍能正常进行，而不至于当链路恢复正常后，时隙调度陷入混乱.

接收时间的更新在接收状态中进行，节点进入接收状态后在上述初始化的接收时间内等后续节点发送的帧，如果在这个时间结束时还没等到，则退出接收状态进入睡眠状态;否则按下列算法更新接收时间:

①若收到最近的后续节点发送的帧，则接收时间更新为

继而进行新的等待－更新过程.但是，对于正向调度的节点(N－1)和反向调度的节点1来说，因其后续节点只有一个，此时接收时间应更新为0，因而立即进入睡眠状态.

②若收到次近的后续节点发送的帧，则接收时间更新为0，因而立即进入睡眠状态.1.3.2 睡眠时间ts的确定

参考图3，当网络调度方向为0时，节点i(＜5)经过了自己的发送时隙后，要等到其后续节点(i+1)和(i+2)的发送时隙过去之后才进入睡眠(此时节点i已由正向调度进入反向调度时期，节点(i+1)和(i+2)成为其前续节点)，而又要在节点(i+2)和(i+1)进入发送时隙之前醒来;又由于是保守睡眠，所以要以最快的情况(即i在睡眠时期，网络中只有I帧传送)计算ts.因此，节点i在其反向调度时期的睡眠时间为

而由于节点5和节点6是端节点7的邻节点，其睡眠时间都为0.

由以上可归纳，节点j在反向调度时期的睡眠时间为

类似地，节点j在正向调度时期的睡眠时间为ts(j)=max{(2j－5)Tc，0} 0 ＜ j≤N (12)1.3.3 等待时间tw的初始化与更新

在初始化状态中，等待时间的初始化值为

在睡眠结束后进入等待状态之前，等待时间的初始化与睡眠时间的计算过程类似，不同的是:因为要保证在其前续节点进入发送时隙后，本节点必须处于等待状态，直至前续节点的发送时隙已经过去，所以这里要以最慢的情况(即自从本节点进入睡眠状态之后，网络中进入发送时隙的每个节点都发了D帧)来计算.因而，节点j(＜N－2)在反向调度时期的等待时间应初始化为

同样，因为节点(N－2)和节点(N－1)是端节点N的邻居节点，所以在反向调度时期其等待时间应分别初始化为

类似地，节点j(＞2)在正向调度时期的等待时间应初始化为

而因为节点2和节点1是端节点0的邻居节点，所以在正向调度时期其等待时间应分别初始化为

端节点0始终处于反向调度时期，端节点N始终处于正向调度时期.此外需说明的是，初始化等待时间可以保证当因链路或者多个相邻节点失效而导致动态调度无法正常推进时，网络不至于完全瘫痪，而是以接近固定时隙TDMA的性能水平保持工作状态.

等待时间的更新在等待状态中进行，节点进入等待状态后在以上初始化的等待时间里等待前续节点发送的帧，如果在这个时间结束时还没等到，则退出等待状态进入发送状态;否则按下列算法更新等待时间:

①若收到的是次近的前续节点发送的帧，则等待时间更新为

继而进行新的等待－更新过程.

②若收到最近的前续节点发送的帧，则将等待时间更新为0，因而立即进入发送状态.

2 FD－TDMA协议仿真及性能分析

2.1 仿真参数与性能指标

主要仿真参数有:节点总数M为8，相邻节点间的最大距离和最小距离分别为1.5和1.0 km，传播速率1.5 km/s;发送速率为2.4 kbit/s;信道带宽12 kHz;调制方式采用QPSK;为了更客观地反映网络性能，采用随机路由方式;控制帧帧长48 bit;时间裕量δ取0;MAC层缓冲队列的容量为20个数据帧;各节点的业务分布为Poisson分布.以上各参数可用来调节网络负载的大小.

本文主要从吞吐量、时延、能量有效性三方面［9］来评价FD-TDMA协议下网络的性能，另外考虑到本协议的动态调度方式，也将平均调度周期作为衡量通信效率的一个指标.

1)吞吐量 为了消除相同输入负载下不同路由跳数对吞吐量统计的影响，用所有节点收到发给自己的数据比特总数除以仿真时间来计算吞吐量.同时，将多跳传递的数据帧作为一种隐性负载(每帧传递跳数越多，隐性负载越大)加到网络负载中去，得到总负载.

2)平均端到端延时 端到端延时通常是指数据帧从源节点的网络层进入MAC层缓存队列开始，至目的节点MAC层将该数据帧传送到网络层时的时间差;考虑到随机路由跳数的影响，这里采用平均单跳内的端到端延时，再对所有数据帧的平均单跳端到端延时求平均，即得平均端到端延时.

3)平均调度周期 同一节点前后2次进入发送时隙的时间间隔的平均值.

4)能量效用 平均单位能量所成功传送的数据比特数.节点在发送、接收、空闲、睡眠时的功率参照文献［10］中WHOI水声Modem的功耗，并根据本文算法稍作调整，再归一化:发送功率为1 W，等待和接收状态的功率为0.01 W，睡眠状态的功率为0.05 mW.

2.2 仿真结果及性能分析

为了重点考察本文FD-TDMA协议中的全动态时隙调度方式对网络性能的提升，这里将FDTDMA协议与同样加入睡眠和混合回复机制的固定时隙TDMA协议进行仿真比较.

1)在高、中、低3种不同的负载下，FD-TDMA协议的网络吞吐量随数据帧与控制帧的帧长比的变化关系如图4所示.FD-TDMA动态调度机制的一个重要特点是本节点在不影响其他节点正常调度的前提下尽可能地抢用其前续节点没有使用的那段发送时间，从而更充分地利用信道资源;又由于水声信道中数据发送速率较低，所以网络吞吐量随着帧长比的增大而显著提高.

图4 FD-TDMA协议的网络吞吐量与帧长比的关系

当帧长比为8时，FD-TDMA和TDMA协议的吞吐量性能随负载的变化关系如图5所示.随着负载的增加，FD-TDMA相对于TDMA的吞吐量性能优势将逐步增大，而当负载足够高(每个时隙里都发送数据)时，这种性能优势保持平稳.对FDTDMA，每个数据帧的传播时间由相邻节点间的实际距离决定;而对TDMA，固定时隙中的传播时间是由相邻节点间的最大距离决定，因此大多数时隙中的部分时间被浪费.根据实际接收情况来进行时隙调度，减少了不必要的时间浪费，这是 FDTDMA动态调度机制的另一重要特点.在给定的网络负载下，这一特点所取得的性能优势由网络中相邻节点间的距离分布决定，而上一特点所取得的性能优势则由帧长比决定.

图5 FD-TDMA与TDMA协议的网络吞吐量比较

结合图4可知，随着帧长比的增大，FD-TDMA相对TDMA的吞吐量性能优势将进一步扩大.帧长比为8时，高负载下前者的吐吞量比后者高出(401.7－330.6)/330.6=21.5%.

2)数据帧与控制帧的帧长比为16时，在高、中、低3种不同的负载下，FD-TDMA的平均调度周期随时间的变化关系如图6所示.平均调度周期随着网络负载的增大而增大，而由于缓冲队列容量的限制，负载足够大时平均调度周期达到最大.此时，固定时隙TDMA的调度周期恒为(48×16/2 400+1 500/1 500)×8=10.56 s，大于 FD-TDMA的平均调度周期的最大值.

3)在高、中、低3种不同的负载下，FD-TDMA与TDMA的平均端到端延时性能曲线如图7所示.由以上分析知，FD-TDMA动态调度机制既合理抢用时间，又不无故浪费时间，这必然使其调度进程快于TDMA，所以在不同负载下，FD-TDMA的平均端到端延时都明显比TDMA的小.

图6 FD-TDMA协议的平均调度周期

图7 FD-TDMA与TDMA协议的平均端到端延时比较

吞吐量、平均调度周期和平均端到端延时都是从不同的角度来反映网络的通信效率，其统计结果都表明，FD-TDMA协议的通信效率显著高于TDMA协议.

4)在高、中、低3种不同的负载下，FD-TDMA协议的能量效用随帧长比的变化关系如图8所示.根据能量效用的定义可知，网络工作所消耗的能量中，越多的能量用于发送数据，能量效用就越高.所以，能量效用会随帧长比及网络负载的增加而提高;而当网络负载增到足够大时，能量效用很快达到其上限而不再随帧长比的增大而上升.

当帧长比为8时，FD-TDMA和TDMA的能量效用随网络负载的变化关系如图9所示.由前面分析可知，FD-TDMA的调度进度总比TDMA的调度进度快，若考虑网络中各节点都进入一次发送时隙，那么在相同负载下FD-TDMA和TDMA发送的数据量相等，但是TDMA所花的时间更多.所以，在相同的负载下FD-TDMA的能量效用总高于TDMA.在此对高负载情况下这种性能优势作简单的量化:FD-TDMA与TDMA相比，平均能量效用提高(1.933 －1.528)/1.528=26.5%.

图8 FD-TDMA协议的能量效用与帧长比的关系

图9 FD-TDMA与TDMA协议的能量效用比较

3 结语

针对一种特定拓扑结构的水声网络，同时着眼于通信效率和能量效率2个方面，通过引入动态往返调度、混合式回复和保守睡眠机制，设计了一种全动态时隙调度的TDMA协议即FD-TDMA.通过OPNET仿真，在多个性能指标下与同样引入了睡眠和混合式回复机制的TDMA协议相比，FD-TDMA协议都有着显著的优势.然而，对于本文的FD-TDMA协议，在网络规模扩大、网络结构扩展和时间同步等方面还有需要分析讨论和值得进一步研究的问题.

References)

［1］ Akyildiz I F，Pompili D，Melodia T.Underwater acoustic sensor networks:research challenges［J］.Ad Hoc Networks(Elsevier)，2005，3(3):257-279.

［2］Cardei M.Energy-efficient scheduling and hybrid communication architecture for underwater littoral surveillance［J］.Computer Communications，2006，29(17):3354-3365.

［3］Shah G A.A survey on medium access control in underwater acoustic sensor networks［C］//Advanced Information Networking and Applications Workshops.Bradford，UK，2009:1178-1183.

［4］Molins M，Stojanovic M.Slotted FAMA:a MAC protocol for underwater acoustic networks［C］//Proc of the IEEE OCEANS′06Asia Conference.Singapore，2006:1-7.

［5］ Fullmer C L，Garcia-Luna-Aceves J J.Floor acquisition multiple access(FAMA)for packet-radio networks［C］//Proc of the ACM SIGCOMM′95.Cambridge，MA，USA，1995:262-273.

［6］ Rodoplu V，Park M K.An energy-efficient MAC protocol for underwater wireless acoustic networks［C］//Proc of MTS/IEEE OCEANS′05.Washington，DC，USA，2005:1198-1203.

［7］ Xie P，Cui J H.R-MAC:an energy-efficient MAC protocol for underwater sensor networks［C］//Proc of International Conference on Wireless Algorithms，System，and Applications.Chicago，Illinois，USA，2007:187-198.

［8］Syed A A，Ye W，Heidemann J.T-Lohi:a new class of MAC protocols for underwater acoustic sensor networks，ISI-TR-638［R］.California:USC/Information Sciences Institute，2007.

［9］张海霞，袁东风，马艳波.无线通信跨层设计——从原理到应用［M］.北京:人民邮电出版社，2010:13-17.

［10］HarrisⅢ A F，Stojanovic M，Zorzi M.When underwater acoustic nodes should sleep with one eye open:idle-time power management in underwater sensor networks［C］//Proc of the1st ACM International Workshop on Underwater Networks. Los Angeles， CA，USA，2006:105-108.