2024年3月20日发(作者：琴闵)

第３３卷第２期　

２０１２年２月　

通信学报　

Ｖ０ｌ３３　ＮＯ．２　

Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｆｅｂｒｕａｒｙ２０１２　

ＣＴ．ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　

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

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

摘要：针对水下无线传感器网络（ＵＷＳＮ，ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ）提出以发送端为中心以连续时间为计量　

单位的冲突状态模型——局部冲突状态图及其分布式构建算法，并在此基础上设计了基于启发式规则的水下传感　

器网络ＴＤＭＡ协议（ＣＴ－ＴＤＭＡ，ｃｏｎｔｉｎｕｏｕｓ　ｔｉｍｅ　ｂａｓｅｄ　ＴＤＭＡ）。ＣＴ－ＴＤＭＡ利用ＵＷＳＮ中同一接收节点与不同　

发送节点之问链路时延的差异性，减少在目的端的接收帧之间的空闲时间，从而提高网络流量；基于启发式规则　

的分配算法，能有效缩短连续时间轴上的时刻分配所花费的时间。模拟实验证明：ＣＴ—ＴＤＭＡ与以ＳＴ．ＭＡＣ为代　

表的按时隙分配的ＴＤＭＡ方案相比，网络流量提高了２０％，数据分组的端到端时延降低了１８％；与由全局知识　

所计算出的最优分配策略相比，网络流量达到了８０％，端到端时延仅延长了１２％。　

关键词：水下传感器网络；ＭＡＣ协议；ＴＤＭＡ；ＳＴ．ＭＡＣ　

中图分类号：ＴＰ２１２．９　文献标识码：Ａ　文章编号：１０００－４３６Ｘ（２０１２）０２—０１６４－１１　

ＣＴ—ＴＤＭＡ：ｅｆｆｉｃｉｅｎｔ　ＴＤＭＡ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　

ＨＯＮＧ　Ｌｕ，ＨＯＮＧ　Ｆｅｎｇ，ＬＩ　Ｚｈｅｎｇ—ｂａｏ，ＧＵＯ　Ｚｈｏｎｇ—ｗｅｎ　

（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｍｒＳｃｉｅｎｃｅ，ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎ　ＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＯｃｅａｎＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎａ，Ｑｉｎｇｄａｏ２６６１００，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｉｍｅｄ　ａｔ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｉｔｃ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｓ（ｋＵＷＳＮ），ａ　ｎｏｖｅｌ　ｓｅｎｄｅｒ　ｂａｓｅｄ　ｃｏｎｆｌｉｃｔ　ｍｏｄｅｌ　ｗｉｔｈ　ｈｅ　ｔｓｃｈｅｍｅｓ　

ｏｆａｌｌｃａｔｏｉｎｇ　ｃｏｎｔｉｎｕｏｕｓｔｉｍｅｗａｓ　ｐｒｅｓｅｎｔｄ，ｉｅｎｃｌｕｄｉｎｇｌｏｃａｌ　ｃｏｎｌｉｆｃｔｇｒａｐｈ（ＬＣＧ）ａｎｄ　ａｄｉｓｔｒｉｂｕｔｅａｌｇｏｒｉｔｈｍｔｏ　ｇｅｎｅｒａｔｅ　

ＬＣＧ．Ｍｏｒｅｏｖｅｒ，ＣＴ－ＴＤＭＡ，ａｎ　ｅｆｆｉｃｉｅｎｔ　ＴＤＭＡ　ｐｒｏｔｃｏｌｏ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｃｏｎｆｌｉｃｔ　ｍｏｄｅｌ　Ｗａｓ　ａｌｓｏ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｕｓｅｄ　

ｈｅｕｒｉｓｔｉｃｐｒｉｏｒｉｔｙ　ｒｕｌｅｓｔｏ　ａｌｌｏｃａｔｅｔｒａｎｓｍｉｔｔｉｎｇｍｏｍｅｎｔｓｆｏｒａｌｌｎｏｄｅｓ．ＣＴ－ＴＤＭＡ　ｅｘｐｌｏｉｓｔｔｈｅ　ｄｉｖｅｒｓｉｔｙｏｆｐｒｏｐａｇａｔｉｏｎｄｅｌａｙｏｆ　

ｄｉｆｆｅｒｅｎｔｌｉｎｋｓｉｎＵＷＳＮｔｏ　ｄｅｃｒｅａｓｅｔｈｅｉｄｌｅｔｉｍｅｂｅｔｗｅｅｎｐａｃｋｅｔｓ　ａｔｔｈｅ　ｓａｍｅ　ｒｅｃｅｉｖｉｎｇ　ｎｏｄｅ，ｗｈｉｃｈｈｅｌｐｓｉｎｉｍｐｒｏｖｉｎｇｔｈｅ　

ｔｈｒｏｕｇｈｐｕｔ．Ａｎｄ　ａ　ｈｅｕｒｉｓｔｉｃ　ｓｃｈｅｄｕｌｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｐｐｌｉｄ　ｅｔｏ　ｓｈｏｒｔｅｎ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ａｌｌｏｃａｔｉｎｇ　ｃｏｎｔｉｎｕｏｕｓ　ｔｉｍｅ　ｆｏｒ　ｅａｃｈ　ｎｏｄｅ．　

Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｌｔｕｓ　ｓｈｏｗｔｈａｔ，ｃｏｍｐａｒｅｄｗｉｈｔｔｒａｄｉｔｉｏｎａｌＴＤＭＡｐｒｏｔｏｃｏｌｓ　ｓｕｃｈａｓＳＴ－ＡＣ，ｎｅｔＭｗｏｒｋｔｈｒｏｕｇｈｐｕｔｏｆＣＴ－ＴＤＭＡ　

ｈａｓｉｎｃｒｅａｓｅｄ　２０％ａｎｄ　ｅｎｄｔｏ　ｅｎｄｄｅｌａｙｈａｓｄｅｃｒｅａｓｅｄ　１８％：ｃｏｍｐａｒｅｄｔｏｔｈｅｔｈｅｏｒｅｔｉｃａｌｌｙｏｐｔｉｍａｌｓｃｈｅｍｅｗｉｔｈｇｌｏｂａｌｋｎｏｗｌ－　

ｅｄｇｅ，ＣＴ－ＴＤＭＡｈａｓａｃｈｉｅｖｅｄ８０％ｎｅｔｗｏｒｋｔｈｒｏｕｇｈｐｕｔａｎｄｔｈｅｅｎｄｔｏｅｎｄｄｅｌａｙｉｓｏｎｌｙ　１２％ｌｏｎｇｅｒ．　

Ｋｅｙ　ｗｏｒｄｓ：ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ；ＭＡＣ　ｐｒｏｔｏｃｏｌｓ；ＴＤＭＡ，ＳＴ—ＭＡＣ　

言　

水下无线传感器网络（ＵＷＳＮ，ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　

ｎｅｔｗｏｒｋｓ）将采集到的海洋环境数据发送给用户来辅　

收稿日期：２０１０—０６—１７；修回日期：２０１０—１１—１８　

蒌　溢　探　

ＵＷＳＮ的重要特点是，主要通信方式只能采用　

水声通信。这是因为高频无线信号会被海水吸收，　

基金项目：国家自然科学基金资助项目（６０７０３０８２，６０８７３２４８，６０９３３０１１，６０９７０１２９）；青岛市科技发展计划基金资助项目　

（１０—３—４—１・６－ｊｃｈ１　

Ｆｏｕｎｄａｔｉｏｎ　Ｉｔｅｍｓ：Ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒｌａ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（６０７０３０８２，６０８７３２４８，６０９３３０１１，６０９７０１２９）；Ｓｃｉｅｎｃｅ　ｎｄ　ａ

Ｔｅｃｈｎｏｌｏｇｙ　Ｄｅｖｅｌｏｐｍｅｎｔ　Ｐｒｏｇｒａｍ　ｏｆ　Ｑｉｎｇｄａｏ（１０－３—４－１－６￣ｃｈ）　

第２期　洪璐等：ＣＴ．ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１６５・　

光信号也会因海水散射和反射而大量损耗，两者均　

不能满足水下长距离通信的要求。与无线电信号相　

比，水声通信的主要特点是：传播时延大，水声信　

号的传播速率仅为１　５００ｍ／ｓ；通信距离长且带宽低，　

通信距离一般在１～１０ｋｍ级别，通信带宽仅在１０ｋＨｚ　

级别；误码率高、多途现象和多普勒频移现象均会　

导致传输错误　。　

由于水声通信的传播时延高和通信距离长，发　

送端无法判断信道是否冲突；同时，由于低带宽和　

误码率高的特性，使得ＵＷＳＮ中每次通信的分组　

长度必须受到限制。因此，解决ＵＷＳＮ的ＭＡＣ问　

题的关键在于接收端判断冲突是否发生。　

目前，国内外的研究者在ｕｗＳＮ的ＭＡＣ问题　

上展开了深入的研究，主要包括接入竞争控制协议　

和无冲突接入协议２种。接入竞争控制协议，通过　

以接收端为中心的虚拟载波监听协议来解决ＭＡＣ　

问题【６　们，但由于水声通信的时延长，虚拟载波监　

听的握手机制降低了数据通信时间的比例，导致网　

络流量较低。　

无冲突接入协议主要采用时分复用接入（１［１　Ａ），　

即采用集中式的方式来向ＵＷＳＮ内各个节点分配　

通信时间片Ｉｌ卜Ｈ】。此类协议可根据数据传输完成需　

要的时隙数分为２种。第一种ＴＤＭＡ算法要求，　

一

跳范围内的数据传输必须在一个时隙完成，称之　

为单时隙协议Ｉ１　’１２］ｏ单时隙协议的主要问题在于，　

为了保证不同距离的节点对在一个时隙内均能完　

成通信，时隙必须由最大的链路时延决定。时隙的　

长度是发送帧时和网络中最大链路时延之和，该问　

题同样影响了网络流量的提高。　

为了提高网络流量，研究者提出了允许跨时隙　

完成数据传输的ＳＴ－ＭＡＣ协议Ｉｌ　。该协议假设所有　

的链路时延都是帧时的整数倍，利用启发式规则完　

成多跳网络的时隙分配，实现了较高的网络流量。　

基于时隙的分配本质上是分配各个节点的发　

送时刻。如果能不采用按时隙分配，而直接在连续　

时间轴上对每个节点分配发送时刻，将更好地利用　

ＵＷＳＮ网络中同一接收节点与不同发送节点之间　

链路时延的差异性，降低接收帧之间的空闲时间，　

提高网络流量。因此，本文提出了以连续时间分配　

为出发点的水下传感器网络的ＴＤＭＡ协议　

（ＣＴ—ＴＤＭＡ，ｃｏｎｔｉｎｕｏｕｓ　ｔｉｍｅ　ｂａｓｅｄ　ＴＤＭＡ）。　

ＣＴ—ＴＤＭＡ的核心思想是，每个节点利用收集　

到的局部网络拓扑信息，以自身的发送行为可能引　

起的冲突为依据，分布式地计算局部冲突状态图　

（ＬＣＧ，ｌｏｃａｌ　ｃｏｎｆｌｉｃｔ　ｇｒａｐｈ）。所有节点按照启发式　

规则计算自己的优先级，然后根据ＬＣＧ图中的所　

有邻居的优先级顺序完成发送时刻的标定。优先级　

计算的启发式规则综合了节点的度、负载和链路时　

延等重要因素，在有效缩短连续时间轴上时刻分配　

问题的计算时间的同时，保证了ＴＤＭＡ协议的流　

量和端到端时延等性能指标。　

本文的主要贡献如下。　

１）针对水下传感器网络在ＭＡＣ层设计上的独　

特问题——同一接收节点与不同发送节点之间链路　

时延的差异性不可忽略，设计了以发送端为中心以　

连续时间为计量单位的冲突状态模型——局部冲突　

状态图。在此基础上，本文提出了分布式的局部冲突　

状态图构建算法：每个节点利用以通信半径和干扰　

半径之和为半径的覆盖圆内的网络拓扑信息，分布　

式计算局部冲突状态图。　

２）提出了基于启发式规则的水下传感器网络　

ＴＤＭＡ协议，即节点以其局部冲突状态图为分配依　

据，以节点的度、负载和链路时延计算优先级，按　

照优先级顺序进行发送时刻标定。该启发式算法有　

效缩短了连续时间轴上时刻分配问题的运行时间。　

３）ＣＴ—ＴＤＭＡ协议采用基于连续时间的接入分　

配算法，与基于时隙的ＴＤＭＡ协议相比，缩短了　

目的端的接收帧之间的空闲时间，提高了接收端的　

信道利用率及整个网络的流量。模拟实验证明：在　

实验时间段内，ＣＴ．ＴＤＭＡ方案与以ＳＴ—ＭＡＣ为代　

表的ＴＤＭＡ方案相比，网络流量提高了２０％，数　

据分组的端到端时延降低了１８％；与由全局知识所　

计算出的最优分配策略相比，网络流量达到了　

８０％，数据分组的端到端时延仅延长了１２％。　

本文其余部分组织如下：第２节对ＣＴ．ＴＤＭＡ　

设计方案进行详细介绍；第３节分析ＣＴ＿ＴＩ）ＭＡ的　

仿真实验结果，第４节概述近几年ＵＷＳＮ的ＭＡＣ　

问题的相关研究成；第５节是结束语。　

２　ＣＴ．　ｒＤＭ＿Ａ设计　

本节首先通过示例说明ＣＴ。ＴＤＭＡ的设计出发　

点，进而对基于连续时间的冲突状态模型——局部　

冲突状态图进行了详细说明。其次详细介绍　

ＣＴ—ＴＤＭＡ的执行过程，并给出关键函数和过程的　

伪代码描述。然后讨论了ＣＴ－ＴＤＭＡ中用于判断节　

点接入优先级的启发式规则。最后，结合实例来展　

通信学报　第３３卷　

示ＣＴ—ＴＤＭＡ的运行过程和运行结果。　

２．１设计出发点　

解决ＵＷＳＮ的ＭＡＣ问题的关键在于，唯有接　

收端才能判断数据分组冲突是否发生。如图１（ａ）所　

示，节点Ａ和　向节点Ｃ发送数据。设　ｃ和Ｄ　ｃ　

为链路ＡＣ和ＢＣ的传播时延且ＤａＧ＜ＤＢｃ，Ｔ为数　

据分组发送时间即帧时，　和ｔｂ为节点Ａ和　的传　

输时刻。　

在陆地传感器网络中，由于无线电信号的传播　

时延可以忽略，因此ＴＤＭＡ方案的时隙长度为　

只要由发送端Ａ和　选择不同的时隙发送即可避免　

冲突。然而，ＵＷＳＮ的链路的传播时延不可忽略，　

为了保证相邻时隙发送的帧无冲突，在本例中时隙　

长度至少为ＤＢｃ＋丁。因此，接收端ｃ接收到的帧序　

列在时间轴将变得稀疏，如图１（ｂ）所示。　

Ｃ　

（ａ）Ｎ络拓扑　

÷—　

ｃ　ｃ—　

：　：　，，　，，　：　，　，一　

Ｂ

ｊ

：

口　

：‘ｂ　

ｉ

：

口　

（ｂ）时隙分配的ＴＤＭＡ　（ｃ）连续时间分配的ＴＤＭＡ　

图１　ＴＤＭＡ不同策略下的发送时间的分配　

而理想的ＴＤＭＡ效果应如图１（ｃ）所示，Ａ选择　

时刻发送数据帧，则该帧到达Ｃ的时刻为ｔａ＋ＤＡｃ。　

为使得Ｃ接收到的帧序列间的空闲尽可能小，那么　

发送的帧到达Ｃ的时刻应为　＋　ｃ＋　（即Ａ发　

送帧的帧尾和曰发送帧的帧头相接），所以日节点　

的发送时刻应为ｔｂ＝ｔａ＋Ｄａｃ＋　ｉｃ。　

图ｌ给出了ＵＷＳＮ网络的普通拓扑情况。该　

例说明基于连续时问的接入分配相比于基于时隙的　

ＴＤＭＡ方案，能够提高接收端的流量。基于连续时间　

的分配充分利用了ＵＷＳＮ的链路时延长和数据分组　

短的特性，这正是ＣＴ．ＴＤＭＡ设计的出发点。　

２．２连续冲突状态模型　

为了清晰地描述ＣＴ．ＴＤＭＡ的连续冲突状态模　

型，本节首先对运行环境做一些基本设定。　

１）使用圆型通信和干扰模型，即节点的通信范　

围和干扰范围都是一个以自己为圆心的圆。网络中　

节点都是同构的，具有相同的通信半径Ｒ　（ｔｒａｎｓ．　

ｍｉｓｓｉｏｎ　ｒａｄｉｕｓ）和干扰半径ＲＩ（ｉｎｔｅｒｆｅｒｅｎｃｅ　ｒａｄｉｕｓ）。　

传感器网络中的干扰半径尺Ｉ是对节点信号的干扰　

覆盖范围的一种描述：当源节点进行发送时，以源　

节点为圆心、ＲＩ为半径的覆盖圆内的所有节点都由　

于源节点发送数据所带来的干扰，而不能正常接收　

来自其他节点的数据分组【１　１６］ｏ　ＲＩ在网络部署前进　

行测定，并与通信半径一样作为协议的初始化参数　

进行设定。　

２）节点通过时钟同步算法，保证足够的同步精　

确度。　

ＣＴ—ＴＤＭＡ的连续冲突状态模型包括局部冲突状　

态图和禁止时间计算规则。其关键术语的定义如下。　

定义１覆盖范围函数Ｃｏｖ（Ｎ，　）：以节点Ⅳ为　

圆心，以　为半径的区域。如节点Ⅳ　，Ｙｎ）通信范　

围Ｃｏｖ（Ｎ，ＲＴ）＝｛　，ｙ）ｌ（ｘ．　）　＋　一Ｙ　）　≤　Ｔ２ｌ；干扰范　

围Ｃｏｖ（Ｎ，尺Ｉ）＝｛（ｘ，ｙ）ｌ（ｘ－ｘｏ）　＋（）＇－Ｙ　）　≤　Ｉ　｝　

定义２求取某区域内的节点集的操作Ｎｏｄｅ．　

ｓｅｔ（ｃ）：Ｃ为水下传感器网络的某个部署区域，操作　

返回属于该区域的节点集，即Ｎｏｄｅｓｅｔ（Ｃ）＝｛ⅣＩ（Ｘｎ，Ｙ　）　

∈Ｃ｝。　

定义３冲突：节点不能够同时发送和接收，　

不能够同时接收２个以上的数据分组，所有违反这　

２条原则的发送和接收均称为冲突。以图２为例，　

如果ｉ和

．

ｆ的信号同时到达ｋ，ｋ将无法正常接收ｆ　

的数据分组；如果ｉ的信号到达ｋ时ｋ正在发送，ｋ　

也无法正常接收ｉ的数据分组，此２种情形均称为　

冲突。　

定义４冲突邻居、冲突目标节点：节点之间　

的冲突关系是网络物理拓扑和逻辑拓扑的直接反　

映。设Ⅳ为网络中的任一发送节点，节点Ⅳ的发送　

操作对周围节点可能造成的冲突主要表现在：对于　

不同于Ⅳ的节点　而言，如果存在节点Ｐ，满足Ｐ　

的位置在物理拓扑中位于Ｍ和Ⅳ其中一个节点的　

通信范围内，同时位于另一节点的干扰范围内，并　

且，在逻辑拓扑中存在链路Ｎ一＞Ｐ或者Ｍ一＞Ｐ，那　

么Ｐ节点在接收Ⅳ或者Ｍ其中一个节点的数据分　

组时，可能会受到来自另一节点的发送信号的干扰　

而无法接收，即在Ｐ点形成冲突。　

对于节点Ⅳ来说，其干扰范围内的所有邻居都　

有可能由于节点Ⅳ的发送而成为冲突发生点。因此，　

节点Ⅳ的冲突目标节点和冲突邻居定义如下：　

当节点Ｐ、Ｍ同时满足下列拓扑条件时，节点　

第２期　洪璐等：ＣＴ—ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１６７・　

Ｐ是节点Ｊ７ｖ的冲突目标节点，节点　是节点Ｊ７ｖ的　

冲突邻居：　

中，因此冲突邻居也就是节点的ＬＣＧ邻居。　

以图２为例，节点ｋ是节点ｆ和节点７的冲突　

．

①物理拓扑条件：　

尸∈Ｎｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，ＲＴ）ｎ　Ｃｏｖ（Ｍ，ＲＯ）ｌｌ　

ｐ　Ｅ　Ｎｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，ＲＩ）ｎ　Ｃｏｖ（Ｍ，　Ｔ））　

目标节点，那么节点ｉ的ＬＣＧ图中存在边ｆ＿７，权　

值为Ｗｉｊ（ｋ）＝Ｄ　一Ｄ　一０．２。其含义为：如果节点　

选择比节点ｆ晚０．２ｓ进行发送，则在节点ｋ将同时　

接收到节点ｉ的发送信号和节点，发向其他节点的　

．

②逻辑拓扑条件：　一＞Ｐ）ｌＪ（　一＞尸）　

该定义说明，节点的冲突邻居必位于它的　

（ＲＩ＋尺Ｔ）的覆盖范围内。如图２中，节点ｋ处于节点　

数据信号的干扰能量，从而发生冲突。　

对于节点ｉ和节点ｋ来说，Ｎｏｄｅｓｅｔ（Ｃｏｖ（ｉ，ＲＴ）ｎ　

Ｃｏｖ（ｋ，ＲＩ））＝｛ｆ，ｋ｝，并且仅链路ｆ一＞足存在，由定义　ｆ的通信范围和节点７的干扰范围内，同时链路ｆ一＞足　

存在，因此节点７是节点ｆ的冲突邻居，节点ｋ为　

相应的冲突目标节点。对于节点ｎ来说，节点ｎ和　

节点ｆ相距较远，且两者的通信范围和干扰范围的　

交集范围内不存在节点，因此不满足上述定义中的　

物理拓扑条件，所以节点ｎ不是节点ｆ的冲突邻居。　

图２节点ｉ的局部网络拓扑结构　

定义５局部冲突状态图（ＬＣＧ，ｌｏｃａｌ　ｃｏｎｆｌｉｃｔ　

ｇｒａｐｈ）：节点ｉ的冲突状态图是一个以节点ｉ为中　

心的带权多重图，描述所有和ｆ的发送行为有关的　

冲突。ＬＣＧ中的顶点为ｉ及其所有的冲突邻居。ＬＣＧ　

图中边的权值定义为：如果节点

．

７为节点ｉ的冲突　

邻居，其冲突目标节点为ｋ，且链路　和

．　

的时延　

分别为Ｄｉｋ和Ｄ　，则边ｆ＿７的权值为　

（　）＝Ｄｉｋ—Ｄｊｋ　（１）　

为了表达式的一般性，定义Ｄ　０。　

ｆ（　用来描述节点ｉ和节点

．

７发送的数据在接　

收点ｋ产生冲突的状态。　肚）取正值表示，如果节　

点ｉ选择比节点

．

７早　肚）的时间进行发送，则会在　

ｋ产生冲突。相应地，如果　，（Ｄ为负值，表示节点　

ｉ选择比节点

．

７晚１ｗｏ（ｋ）ｌ的时间进行发送时会产生冲　

突。由于节点的所有冲突邻居均位于该节点的ＬＣＧ　

４可得，节点ｋ既是节点ｉ的冲突邻居，也是节点ｆ　

和节点ｋ冲突的目标节点，且　（　）＝ｗ＝ｆ　一　３．２。　

这说明如果节点ｉ选择比节点ｋ早３．２ｓ进行发送，　

那么当节点ｉ的数据信号到达节点ｋ时，节点ｋ正　

在向其他节点发送信号，无法接收节点ｉ的数据，　

产生冲突。　

再分析节点ｉ和节点厂的冲突情况，由定义４　

的物理条件得到，Ｎｏｄｅｓｅｔ（Ｃｏｖ（ｉ，ＲＴ）ｎ　Ｃｏｖ（ｆ，ＲＩ））：｛ｆ，　

忌，

．

ｎ。由于链路ｆ一　厂不存在，根据定义４的逻辑拓　

扑条件，．厂不是冲突目标节点。该论断的含义是，．厂　

不接收ｉ的数据分组，因此ｉ发送的信号到达．厂时，　

．

厂可以进行发送，即在．厂节点处不会产生ｉ和．厂的冲　

突。但是链路ｆ一＞　存在，说明ｋ是ｆ和厂的冲突目　

标节点，其含义是ｆ和厂的信号可能同时到达节点ｋ。　

同时，链路　＞ｆ存在，说明ｆ同样是ｉ和．厂的冲突　

目标节点，其含义是ｉ在接收Ｉ厂的信号时，不能向　

其他节点发送数据。因此节点ｆ的ＬＣＧ图中，　ｉ　

和

．

厂之间存在２条边，其权值分别为ｗｉ￣ｋ）＝Ｄｉｋ－Ｄｓ＇ｋ　

＝－

２．２和Ｗｉｊ（ｉ）＝Ｄｉｉ－Ｄｉｆ＝－４．５。　

定义６禁止时间：节点的禁止时间是指在时间　

轴上的一个时间片段内，节点不能够选择发送时　

刻，否则会引起冲突。　

为保证２个节点的帧到达目标时不冲突（即在　

接收端的时间轴上不重叠），对每个发送节点来说　

均有一段时间不能发送，称为禁止时间。以图３为　

例，在节点ｆ的ＬＣＧ中，如果其邻居７选择发送时　

刻ｔｊ，则由节点

．

７决定的节点ｉ的禁止时间定义为（Ｆｌ（ｉ，　

，　，　

（　，Ｊ，　）。其中　

（ｆ，Ｊ，足）＝ｔ　一　，（ｋ）一Ｔ　（２）　

（　，．『，足）＝ｔ　一ｗｉ　（七）＋Ｔ　（３）　

禁止时间的物理含义为，由于节点７的存在和　

其发送时刻ｔｓ的确定，节点ｉ在（Ｆｌ（ｉ，Ｊ，足），Ｆｒ（ｉ，　，　）　

时间段内不能发送数据帧。如图３所示，如果节点　

・１６８・　通信学报　第３３卷　

ｆ选取的发送时刻大于　（ｆ，ｊｆ，　，ｆ发送的帧尾将与　

发送的帧头在相关接收点ｋ产生冲突；当ｆ选取的　

发送时刻稍小于Ｆｒ（ｉ，Ｊ，　，ｆ发送的帧头将与．『发送　

的帧尾在相关接收点ｋ产生冲突。　

Ｉ—————午　—１ｌ　————禁●■止●●时■■间■　ｌ■＝■●＝■｝寸　—　—————————————１　

图３禁止时间的计算　

以图２中的节点ｆ和．７的冲突为例，　＝一０．２，　

假设节点．／选择第２ｓ发送（　＝２），帧时Ｔ＝ｌｓ，则根　

据式（２）和式（３）可得节点．７给节点ｆ带来的禁止时间　

为（１．２，３．２）。以节点ｆ和

．

厂为例，根据前面的分析，　

冲突状态图中边ｆ＿厂的权值有２个，因此假设．厂选　

择０ｓ开始发送，根据公式计算出的－厂给ｆ带来的禁　

止时间也是２段，为（３．５，５．５）ｕ（１．２，３．２）。　

２．３　ＣＴ．ＴＤＭＡ的主要算法　

本节首先介绍局部冲突状态图的生成过程，然　

后介绍ＣＴ—ＴＤＭＡ的算法流程。ＣＴ—ＴＤＭＡ可以适　

用于任何网络拓扑结构，但为了简化说明，本节针　

对最广泛使用的树形拓扑结构进行介绍。　

２．３．１　ＬＣＧ生成算法　

在初始化阶段，每个节点ｆ收集Ｃｏｖ（ｉ，ｅｒ＋尺Ｉ）　

范围内的邻居节点的地理位置信息和逻辑链路信　

息，并计算其冲突区域内所有节点对的信号传播时　

延，得到以该节点为中心的局部网络拓扑结构。对　

于位于节点通信半径之外的邻居，节点通过多跳传　

输的方式获得其对应邻居的相关信息。在计算得到　

Ｃｏｖ（ｆ，Ｒｒ＋尺Ｉ）内的局部网络拓扑结构后，节点运行　

ｃｒｅａｔｅＬＣＧ０函数，按照定义５中给出的规则生成自　

己的ＬＣＧ。　

利用定义４验证

．

７是否是ｆ的冲突邻居。ＰＴＣ０　

和ＬＴＣ０函数用来对节点是否符合冲突的物理拓扑　

条件（ｐｈｙｓｉｃａｌ　ｔｏｐｏｌｏｇｙ　ｃｏｎｄｉｉｔｏｎ）和逻辑拓扑条件　

（１ｏｇｉｃａｌ　ｔｏｐｏｌｏｇｙ　ｃｏｎｄｉｉｔｏｎ）进行判定。针对每一个邻　

居

．

７进行分析：如果存在某个节点ｋ，使得ｋ、Ｊ符　

合冲突的２个条件，满足节点．７是节点ｆ的冲突邻　

居，ｋ是ｊ和

．

７冲突的目标节点，则计算　

Ｗｕ（ｋ）＝Ｄ　一Ｄ豫，并记录到ｆ的ＬＣＧ中。　

算法１　ｃｒｅａｔｅＬＣＧ　０　

１）Ｉｎｐｕｔ：ｖ（ｉ）　

２）Ｏｕｔｐｕｔ：Ｓｔ￣ｃ（ｉ）　

３）ＰＴＣ（Ｎ，Ｐ，　｛　／／物理拓扑条件判定　

４）ｉｆ（ＰＥＮｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，Ｒｒ）ｆ３　Ｃｏｖ（Ｍ，蜀））ｌ　ｌ

ＰＥＮｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，　ｎＣｏｖ（Ｍ，　））　

５１　ｒｅｔｕｒｎ　ｔｒｕｅ　

６、ｅｌｓｅ　

７）　ｒｅｔｕｒｎｆａｌｓｅ　

８）　｝　

９）ＬＴＣ（Ｎ，Ｐ，＾　｛　，／逻辑拓扑条件判定　

ｌｏ）ｉｆ（］Ｎ－＞Ｐ　ＩＩｊＭ－＞Ｐ）　

１１）　ｅｒｔｕｍ　ｔｒｕｅ　

１２）ｅｌｓｅ　

１３）　ｒｅｔｕｒｎｆａｌｓｅ　

１４）｝　

ｃｒｅａｔｅＬＣＧ０　

１５）ｎｅｗ　ＶＬＣＧ＝’，（ｆ）；／／Ｃｏｖ（Ｎ，　邻居顶　

点集　

１６）ｗｈｉｌｅ（　ｃＧ！＝ｎｕｌ１）｛　

１７）　ＶｊＥ’，（ｆ）／／￣，－ｊ－论边ｆ　的情况　

１８）　ＶＬＣＧ＝　Ｇ—Ｕ｝　

１９）　ｎｅｗ　Ｖ’＝’，（ｆ）ＩＩ以下逐个节点分析，ｉ　

节点和．『节点是否会在’，（ｆ）中的节点产生冲突　

２０）　ｗｈｉｌｅ（Ｖ’：＝ｎｕｌ）１｛　，，遍历所有可能的　

冲突目标节点　

２１１　Ｖ七∈Ｖ’　

２２）　Ｖ’＝　’－｛ｋ｝　

２３）　ｆ（ＰＴＣ（ｉ，ｋ，ｊ）＝ｔｒｕｅ＆＆ＬＴＣ（ｉ，ｋ，　

ｊ）＝ｔｒｕｅ）｛　，／冲突邻居和冲突目标节点判定　

２４）　Ｗｕ（ｋ）：Ｄ　ＤＬｋ　

２５）　Ｓｔａｃｋ（ｉ）＝Ｓｔｃｃ（ｉ）Ｕ｛Ｗｕ（ｋ）｝　／／将ｆ　

节点和．『节点的一条边的权值记录到ＳＬＣＧ中　

２６）　）／／ｅｎｄ　ｉｆ　

２７）　｝／／ｅｎｄｗｈｉｌｅ（　’！＝ｎＵ／）１　

２８））　／／ｅｎｄ　ｗｈｉｌｅ（ＶＬｃＧ！＝ｎｕｌ）１　

２９）ｒｅｔｕｒｎＳｔｃ￣（ｉ）　

令’，（ｆ）是节点ｆ的所有Ｃｏｖ（Ｉ，ＲＴ＋尺Ｉ）内的邻居　

节点的集合，Ｓｔｃｃ（ｉ）为ｆ的冲突状态图内所有的边　

的权值集合，算法１描述了节点局部冲突状态图的　

生成过程。　

以图２的拓扑为例，节点ｉ运行ｃｒｅａｔｅＬＣＧ０算　

法后，生成的ＬＣＧ如图４所示。根据前面的分析，　

第２期　洪璐等：ＣＩ＂ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１６９・　

节点．厂和ｆ冲突的目标节点有２个，根据定义５计　

算出边ｆ＿厂有２个权值，因此在局部冲突状态图中　

体现为具有不同权值的多重边。如果２个节点对会　

在多个节点处产生冲突，则ＬＣＧ图中这２个节点　

对之间就会有多重边，且多重边的个数即为冲突目　

标节点的个数。因此，由于节点冲突的多样性，ＬＣＧ　

为带权的多重图。　

ｈ　

图４节点ｉ的局部冲突状态图（ＬｃＧ）　

２．３．２　ＣＴ—ＴＤＭＡ算法流程　

每个节点生成自己的ＬｃＧ图后，就根据由ＬＣＧ　

图每条边所对应的各个禁止时间，来选择自己的发　

送时刻。即选择和所有禁止时间不冲突的最早时　

刻，作为自己的发送时刻。　

但是，当前节点的发送时刻的确定，取决于其　

ＬＣＧ邻居的发送时刻。ＣＴ—ＴＤＭＡ采用优先级和随　

机选择相结合的方式，安排节点的发送时刻标定顺　

序。即优先级最高的节点最先选择发送时刻，选择　

的基本策略是在所有可用的时间段内选择一个最　

早的时间点（选择的过程称为标定）。如果ＬＣＧ　

图中所有未标定节点的优先级相同，各个节点随机　

选择发送时刻。优先级的计算方法，将直接影响　

ＣＴ—ＴＤＭＡ的执行效率。本节先介绍ＣＴ—ＴＤＭＡ的　

算法流程，而计算优先级的启发式规则将在２．３．３　

节中进行讨论。　

ＣＴ—ＴＤＭＡ的完整算法流程包括以下７步。　

１）节点生成自己的ＬＣＧ并计算自己的标定优　

先级。　

２）每个节点向所有的ＬＣＧ邻居广播自己的标　

定优先级，并将自己的状态置为“ｕｎｌａｂｅｌｅｄ”。然　

后，每个节点以分布式方式运行３）～６）步。　

３）如果当前节点在其ＬＣＧ图中的所有未标定　

邻居中拥有最高的优先级，则节点根据由ＬＣＧ得　

到的所有禁止时间段，选择最早的可发送时刻作为　

自己的发送时刻，并将其广播给所有的ＬＣＧ邻居，　

并将状态置为“ｌａｂｅｌｅｄ”。　

４）如果当前节点的所有未标定邻居中存在优　

先级高于自己的邻居，则等待优先级高的节点先标　

定，等待接收相关节点的发送时刻结果并更新自己　

的禁止时间，返回第３）步。　

５）如果当前节点在其ＬＣＧ图中与其他未标定　

的节点拥有相同的优先级，则该节点在时间轴上除　

禁止时间之外的时刻随机选择其发送时刻，并广播　

给所有同优先级的未标定状态的ＬＣＧ邻居。　

６）随机标定的节点选定发送时刻并与所有同　

优先级邻居交换选定结果后，运行Ｊｕｄｇｅ０￣数判断　

是否会产生冲突，若无冲突，则置为“ｌａｂｅｌｅｄ”，　

否则置为“ｕｎｌａｂｅｌｅｄ”，并返回第５）步。　

７）ＬＣＧ图中的所有节点状态均为“ｌａｂｅｌｄｅ”时，　

算法结束。　

算法２　Ｌａｂｅｌ（）　

Ｉｎｉｔｉａｌｉｚａｔｉｏｎ：　

ｌ　１　Ｓ￣（ｉ）＝ｎｕｌｌ；Ｓｔ（ｉ）＝ｕｎｌａｂｅｌｅｄ　

２）　（ｆ）＝Ｕ　ｉｓ　ｆ’Ｓ　ＬＣＧ　ｎｅｉｇｈｂｏｒ｝　

Ｌａｂｅｌ（）　

３）　ｗｈｉｌｅ（３ｊ　Ｅ　Ｓｕ　（ｆ），Ｐ（ｆ）＜Ｐ（，））｛　，／顺序标　

定，节点优先级非最高，等待并接收其他节点标定　

结果　

４）　ｒｅｃｅｖｅ　ｎｏｄｅｊ’Ｓ　ｓｅｌｅｃｔｉｏｎ　ｔｉ　

５）　Ｓｃ（ｉ）＝Ｓｃ（ｉ）　Ｕ｝　

６）　（ｆ）＝　（ｆ）－Ｕ｝　

７、）　ｃａｌｃｕｌａｔｅＦ￣ｉ，ｊ，　Ｆ　，｝。　｜｜诗舆禁　阗　

８）｝／／ｅｎｄ　ｗｈｉｌｅ　

９）ｌｏｏｐ：　

１０）ｉｆ（３ｊ　Ｅ　ＩＳ　（ｆ），Ｐ（ｆ）＝Ｐ（『））｛　

，／优先级相同则随机标定　

１　１）　ｃｈｏｏｓｅ　ｔｉ　ｒａｎｄｏｍｌｙ　ｏｎ　ａｖａｉｌａｂｌｅ　ｔｉｍｅ　ａｘｌｅ　

１　２）　ｓｅｎｄ　ｔ／ａｎｄ　ｒｅｃｅｉｖｅ　ｏｔｈｅｒ　ｎｏｄｅｓ’ｔｒａｎｓｍｉｔ—　

ｔｉｎｇ　ｍｏｍｅｎｔｓ　

１３）　ｆｏｒ　ｅａｃｈｊ（ｊＥ　Ｓｕ　（ｆ）＆＆Ｐ（ｆ）＝Ｐ（『））　

ｃａｌｃｕｌａｔｅ　Ｆｔ（ｉ，　，　ａｎｄ　Ｆｒ（ｉ，Ｊ，　

１４）　ｉｆ（Ｊｕｄｇｅ（）＝ｆａｌｓｅ）　

１５）　ｃｏｎｔｉｎｕｅ　ｌｏｏｐ　

１６）　ｅｌｓｅ　ｆ　’　

１７）　Ｓｔ（ｉ）＝ｌａｂｅｌｅｄ　

１８）　ｒｅｔｕｒｎｔｉ　

通信学报　第３３卷　

ｌ９）　｝　

２０）｝／／随机标定结束　

２１）ｅｌｓｅｆ／／节点自己的优先级最高，开始标定　

２２）　＝０／／从０开始寻找最早的可用时间　

２３）　ｆｏｒ　ｅａｃｈｊ∈Ｓ　（１）｛　

２４）　ｉｆＦｌ（ｉ，　，ｋ）＜ｔｉ＜Ｆｒ（ｉ，　，Ｄ）／／如果当前的　

ｔｉ位于禁止时间内，则增大ｔｉ　

２５）ｔｉ＝Ｆ　ｆ，．『，　

２６）　｝　

２７）｝　

２８）　（ｆ）＝ｌａｂｅｌｅｄ　

２９）ｒｅｔｕｒｎｔｉ　

节点使用Ｌａｂｅｌ（）函数实现标定功能，即上面的　

３）～６）步，Ｊｕｄｇｅ（）函数被Ｌａｂｅｌ（）调用，用来判断一次　

随机选择时间以后是否会产生冲突。在随机标定　

中，节点获得邻居随机选定的时刻后仍然使用定义　

６计算禁止时间。Ｊｕｄｇｅ（）￣数判断冲突的方式是，　

如果节点自己随机选定的时刻处于计算出的“禁止　

时间”之内，则认为会产生冲突，此次随机标定即　

作废，节点及其邻居重新进行随机标定。　

定义　（ｆ）为节点ｉ的已经标定的ＬＣＧ邻居集　

合，　（　）为节点　的所有未标定的ＬＣＧ邻居的集合，　

Ｓｔ（ｉ）为节点ｆ的标定状态（１ａｂｅｌｅｄ或ｕｎｌａｂｅｌｅｄ），Ｐ（ｉ）　

为节点ｆ的标定优先级。算法２和算法３分别给出　

了Ｌａｂｅｌ０￣Ｊｕｄｇｅ（）ｉ￣数的伪代码描述。　

在Ｌａｂｅｌ（）函数中引入随机标定的设计，是因为　

在某些网络中可能存在大量节点的优先级相同。虽　

然可以采用节点ＩＤ等强制优先级方式，但类似的　

优先级策略对优化最终的总传输时间没有帮助。随　

机标定可以减少算法的执行时间。比如，在极端的　

网络拓扑条件下（如线形、星形），当节点的优先　

级均相同时，顺序标定算法的时间复杂度为Ｏ（ｎ）　

而随机标定的时间复杂度为Ｏ（１ｏｇｎ）　＂　。其中，ｎ为　

网络中的节点个数。　

算法３　Ｊｕｄｇｅ（）　

１）Ｉｎｐｕｔ：ｔｉ，Ｓ　（ｉ），　ｆ）　

２１　Ｏｕｔｐｕｔ：ｔｒｕｅ　ｏｒｆａｌｓｅ　

Ｊｕｄｇｅ（）　

３）Ｂｏｏｌｅａｎ　Ｂ＝ｔｒｕｅ　

４）ｆｏｒｅａｃｈｊ∈Ｓｕ　（ｆ）｛　

５）ｉｆ（ｊ　∈　ｆ），　（　，‘『，　＜ｔｉ＜Ｆｒ（ｉ，‘『，　）　

６、　Ｂ＝ｆａｌｓｅ　

７）　｝　

８）ｒｅｔｕｒｎＢ　

２．３．３标定优先级确定　

在ＵＷＳＮ环境下，对于所有节点的连续时间　

的接入分配，等价于一个连续轴上的分布式着色　

问题，因此确定最优全局分配策略是ＮＰ—ｈａｒｄ问　

题。于是，在上一小节介绍的ＣＴ．ＴＤＭＡ算法流　

程中，使用了按照优先级顺序进行标定的算法。　

这样，优先级的确定直接影响ＣＴ—ＴＤＭＡ算法本　

身的执行效率。本节对优先级的计算方法进行详　

细说明。　

ＣＴ—ＴＤＭＡ的算法目的是提高网络流量，即所　

有节点均发送一次数据所使用的总时间越短越好。　

针对这个设计目标，提出重要性依次降低的３条启　

发式的优先级制定规则如下。　

１）在冲突状态图中拥有最大度的节点应该优　

先分配发送时刻。节点的度越大意味着它潜在的冲　

突节点越多。度最大的节点首先分配发送时间，可　

以使受其影响的大量节点的禁止时间尽可能地靠　

前，从而缩短最后算法选定的总时间。　

２）负载较重的节点优先发送。负载较重的节点　

优先发送有助于缩短每个分组端到端的平均时延，　

实现网络的公平性。　

３）网络中拥有较大链路时延的节点优先发送。　

时延较高的链路如果发送的较晚，到达目标时的时　

间就会更晚。而优先分配时延较高的链路，使得高　

时延的链路早发送，低时延的链路晚发送，有助于　

提高节点的传输并行度。　

以上述３条启发式规则为依据，可以实现定量　

计算节点的优先级指标。Ｐ（ｆ）表示节点ｉ的标定优先　

级，采用式（４）进行计算。式（４）中使用的主要变量定　

义为：　为ｉ在它自己的ＬＣＧ图中的度，　。一为节　

点缓冲区的大小，厶为节点ｆ的缓冲区队列长度。　

定义从节点ｉ到基站的传输路径上的下一跳节点ｋ　

为节点ｉ的父节点，Ｄ　为节点ｉ到其父节点ｋ的链　

路传播时延。定义Ｄ　是整个网络中的最大的链路　

传播时延，即网络中距离最长的一跳链路长度与水　

声信号的传播速度的比值，该值在网络部署时可以　

进行估计并设定在所有节点中。由于ＣＴ—ＴＤＭＡ协　

议运行的环境为静态网络，该值在协议运行过程中　

不会改变。而且，该值仅涉及到优先级的计算，对　

于所有节点的计算效果是等价的，因此该值的估计　

精度对于本文提出的ＣＴ．ＴＤＭＡ协议的运行效果没　

有直接影响。　

第２期　洪璐等：ＣＴ．ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１７１・　

Ｐ（ｉ）＝ｄｆ×工　＋厶十｛　（４）　

Ｄ节点的更长，因此Ａ节点的负载最重，优先级　

３条启发式规则的重要性在式（４）中直接体现：　

拥有最大度的节点拥有最高的标定优先级；如果节　

点的度相同则负载较重的节点优先级高；如果节点　

的负载也相同，则拥有最长链路时延的节点优先级　

高。当网络的拓扑结构，节点负载等条件不发生变　

化时，网络可以根据ＣＴ—ＴＤＭＡ计算出的调度顺序　

持续的运行。而当网络拓扑结构或者节点负载等条　

件发生变化时，即节点的标定优先级发生变化时，　

协议将在整个网络重新运行，以保持节点的发送时　

间分配始终为当前的最优策略。　

２．４算法实例　

为了清晰地说明ＣＴ—ＴＤＭＡ的基本思想、工作　

流程及特点，本节给出一个简单的网络实例进行说　

明，如图５（ａ）所示。链路上的标记为该条链路的时　

延（单位为Ｓ），设帧时　为１ｓ。　

各节点首先运行ｃｒｅａｔｅＬＣＧ０函数生成自己　

的局部冲突状态图，４个节点的ＬＣＧ如图５（ｂ）　

所示。　

Ｄ　

（ａ）网络拓扑　

ＬｃＧ　）

副　Ｃ

ＬＣＧ　）ＬＣＧ（Ｃ）　

（ｂ）各节点局部冲突状态　

Ａ　

Ｉ　Ｉ　Ｉ　　ＩＩ　Ｉ　Ｉ　

Ｂ　

Ｉ　Ｉ　Ｉ　　ＩＩ　Ｉ　ｌ　

Ｄ　亨－｛—＿＿｝—寸—十—　

ｃ　＝　—｝＿’｝　

（ｃ）标定顺序和结果　

图５　ＣＴ—ＴＤＭＡ的执行过程　

（实线表示逻辑链路，虚线表示点到点之间的时延）　

然后，所有节点计算自己的优先级。在图５（ｂ）　

中４个节点的度相同，在所有节点产生数据分组　

的频率相同的情况下，对于Ａ节点来说，它不仅　

要发送自己的数据分组，还要转发来自曰和Ｄ　

的分组，Ａ节点的缓冲区队列长度必将比　、Ｃ、　

最高。曰、Ｃ、Ｄ负载相同，因此按链路的时延排　

序，相关链路时延高者优先级高，最终标定顺序　

为Ａ、　、　、Ｃ。　

因此，Ａ首先选择０时刻并广播给　、Ｃ、Ｄ。　

日根据公式计算出Ａ对Ｂ的禁止时间为（一３．９，一１．９）　

ｕ（一４．５，一２．５），所以　也可选择０时刻。Ｄ根据Ａ　

和Ｂ的标定结果，计算Ａ和　对自己的禁止时间为　

（一５，一３）ｕ（一１．５，０．５），于是Ｄ选择自己的发送时刻　

为０．５。最后，ｃ计算Ａ、Ｂ、Ｄ对自己带来的禁止　

时间为（一２．７，一０．７）Ｕ（０．２，２．２）Ｕ（一０．８，１．２），Ｃ选择　

自己的发送时刻为２．２ｓ。４个节点的正数禁止时间　

在图５（ｃ）中给出。禁止时间的负数部分不影响节点　

发送时刻的选择，故未给出。最后，　、Ｂ、Ｃ和Ｄ　

４个节点分别确定自己的发送时刻为０ｓ、０ｓ、２．２ｓ　

和０．５ｓ。　

本例说明，ＣＴ—ＴＤＭＡ提高了数据发送的并行　

度。例如，．Ａ和口节点都在０时刻发送而不会冲突，　

这在传统的ＷＳＮ中是无法实现的。ＵＷＳＮ正是由　

于传播时延高、通信距离长和数据分组短，导致了　

不同发送节点的数据分组到达接收端的时刻存在　

差异。ＣＴ．ＴＤＭＡ利用ＵＷＳＮ的这种特性，避免了　

冲突，提高了网络中数据传输的并行度，达到提高　

网络流量的目的。　

３仿真　

本节介绍ＣＴ—ＴＤＭＡ的仿真结果，并对算法的　

性能进行分析和对比。使用了ＭＡＴＬＡＢ等软件对　

算法进行了仿真，在仿真过程中，帧时　设定为ｌｓ，　

节点的通信半径为３　０００ｍ，干扰半径为３　５００ｍ，网　

络包括从５个节点到６０个节点的４种规模。根据　

网络规模的变化，节点被部署在最大１２ｋｍｘ１２ｋｍ　

的范围内，通过随机部署的方式，利用部署密度限　

制节点和邻居节点之间的距离在４５０ｍ到３　０００ｍ之　

间。因为水声信号的速度为１　５００ｍ／ｓ，所以网络中　

链路的时延被控制在０．３ｓ～２ｓ之间。　

由于网络拓扑结构对节点的传输并行度有重　

要影响，因此对比了一般的网络拓扑结构（节点随　

机投放并自组织成树形拓扑结构），以及特殊的星　

形、线形和网格，共４种拓扑结构对算法的影响。　

在４种拓扑结构下，均采用４种网络规模完成了ｌ６　

组实验。在仿真中使用平均每秒钟整个网络发送的　

有效信息量作为评价网络流量的指标，即节点发送　

通信学报　第３３卷　

的数据信息字节数。ＳＴ—ＭＡＣ帧长度为４５ｂｙｔｅｔ　】　

（４０ｂｙｔｅ有效数据），ＣＴ—ＴＤＭＡ的帧长度为１０５ｂｙｔｅ　

（１００ｂｙｔｅ有效数据）。在仿真中模拟了４种不同的接　

入分配算法。　

１）Ｏｐｔｉｍａｌ：实验网络部署情况下的理论上最　

优的分配策略，该策略能够最大限度地利用信道和　

提高节点的传输并行度，为其他算法提供理论的最　

佳上界。最优策略的求解，即针对实验环境下的网　

络拓扑，在所有可能的节点接入方案中，选取全部　

节点的一轮接入时间最短的接入方案。　

２）ＣＴ—ＴＤＭＡ：本文提出的分配策略。　

３）ＳＴ—ＭＡＣ：文献【１３】提出的跨时隙ＴＤＭＡ分　

配策略。　

４）Ｓ—ＴＤＭＡ：传统的ＵＷＳＮ单时隙ＴＤＭＡ。　

图６中对比了４种调度算法在４种不同网络拓扑　

结构下的流量情况。可以看出，网络拓扑结构对流量　

有明显的影响，线形、树形、网格到星形网络流量依　

次降低，这是由于随着拓扑的变化节点的密度逐渐增　

一　ｓ＿　奎）／嘲蟾燎匿　

加，即共享同一个信道的节点数目越来越多，因此能　

够同时并行传输的节点数目就变得越来越少。除星形　

拓扑之外，在其他拓扑结构和协议下，网络流量均随　

着网络规模的增加而增加。星形拓扑结构表现特殊的　

原因是，在该环境中所有节点均一跳传向基站，因此　

任意２个节点均互为冲突邻居，所有的节点共享同一　

个信道，无法提高数据传输的并行度。　

图６显示，当网络规模较小时，ＣＴ—ＴＤＭＡ　

和ＳＴ—ＭＡＣ均能够达到或接近理论最优的效果。　

当网络规模逐渐增大时，ＣＴ—ＴＤＭＡ和ＳＴ—ＭＡＣ　

的流量均不能达到理论最优值，但ＣＴ—ＴＤＭＡ的　

性能始终优于ＳＴ—ＭＡＣ（平均高２０％以上），并　

达到理论最优值的８０％左右。而Ｓ—ＴＤＭＡ的表　

现最差，因为该方案较长的时隙给接收端带来大　

量空闲时间。　

ＣＴ—ＴＤＭＡ优于ＳＴ—ＭＡＣ的原因在于，　

ＳＴ—ＭＡＣ采用时隙调度策略为节点分配发送时间，　

这种策略规定节点只能在每个时隙的开始时刻发　

送帧。此外，ＳＴ—ＭＡＣ要求所有链路时延是帧时的　

整数倍。为了确保这一点，ＳＴ．ＭＡＣ协议中的分组　

长度必须尽可能小，进一步引起帧中有效数据比例　

下降。其原因是，虽然帧长度缩短，帧中的校验和　

确认位并不减少。ＣＴ—ＴＤＭＡ采用连续时间分配策　

略，并不需要ＳＴ—ＭＡＣ的上述设定，因此可以应用　

更长的数据帧，从而提高了网络流量。　

网络规模（星形拓扑）　

（ａ】星形拓扑下的流量　

网络规模（线形拓扑）　

（ｂ）线形网络拓扑下的流量　

网络规模（网格拓扑）　

（ｃ）网格拓扑下的流量　

网络规模（树形拓扑）　

（ｄ】树形拓扑结构下的流量　

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

第２期　洪璐等：ＣＴ－ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１７３・　

图７记录了４种协议在一般网络情况即树形拓　

扑结构下的端到端时延情况。传感器网络的数据传　

输模式为所有的节点向基站传输数据，因此端到端　

时延即为数据分组从源节点到基站的传播时延。从　

图７可以看出，随着网络规模的增大，节点到基站　

的平均跳数增加，端到端时延也相应增加。由于　

ＣＴ—ＴＤＭＡ使用了连续时间分配策略，在接收节点　

处缩短了帧与帧之间的空闲时间，提高了传输效　

率，其平均端到端时延比ＳＴ—ＭＡＣ降低了约１８％，　

并且只比理论最优策略的时延高１２％。可见，　

ＣＴ—ＴＤＭＡ不仅网络流量要高于传统协议，平均的　

端到端时延也更低，实时性更好。　

翟　

释　

鬲　

孵　

霍　

露　

１碧－　

网络规模　

图７　４种协议的平均端到端时延　

从计算代价的角度分析，ＳＴ—ＭＡＣ为集中式算　

法，需要从所有的全局调度方案中寻找最优方案，　

而ＣＴ—ＴＤＭＡ采用分布式的调度策略，每个节点的　

计算代价都比ＳＴ—ＭＡｃ小很多，因此计算时问更　

短。从能量消耗的角度分析，ＳＴ—ＭＡＣ和ＣＴ—ＴＤＭＡ　

均属于ＴＤＭＡ协议，数据传输阶段没有冲突，因　

此能量效率都很高。额外的能量消耗仅在于协议的　

初始化阶段，ＳＴ—ＭＡＣ需要基站收集全网络的信息　

和分发调度策略，ＣＴ—ＴＤＭＡ仅需要各个节点与其　

Ｃｏｖ（ＲＩ＋ＲＴ）范围内的邻居进行信息交换。当网络规　

模急剧增大时，ＳＴ－ＭＡＣ洪泛和广播的通信开销要　

远大于ＣＴ—ＴＤＭＡ的分布式信息交互。　

４相关工作　

近年来，ＵＷＳＮ的ＭＡＣ问题由于水声通信的　

独特特点引起广泛关注。相关研究成果可分为基于　

竞争的接入控制协议和无冲突的接入协议２类。　

接入竞争控制协议，通过以接收端为中心的虚　

拟载波监听协议来解决ＭＡＣ问题。文献【９】使用　

ＲＴＳ／ＣＴＳ握手机制来建立信道预约。节点通过截获　

邻居信息的方式计算各个邻居节点的忙时间，然后　

在这段时间内停止侦听信道。文献【６】研究了水声信　

道特征对Ａｌｏｈａ协议的影响，进而提出水声通信的　

冲突状态具有时空不确定性的特点。文献［８】和文献　

［１０］基于Ａｌｏｈａ协议，使用一个短帧来预约信道，　

避免数据分组的冲突。Ｔ—Ｌｏｈｉ协议　针对水声信道　

冲突的时空不确定性设计了一个特殊的退避算法，　

在高负载的环境中具有较高的流量。　

无冲突的接入协议基于ＴＤＭＡ和ＣＤＭＡ。针　

对ＵＷＳＮ设计的ＴＤＭＡ协议分为单时隙和跨时隙　

２种，单时隙协议要求一跳范围内的数据传输必须　

在一个时隙完成。ＵＷＡＮ—ＭＡＣ［１１１允许节点随机地　

选择时隙进行传输。文献【１２１提出的混合协议将　

ＴＤＭＡ和竞争协议相结合，充分利用了竞争协议时　

延较低而ＴＤＭＡ流量较高的优点。　

跨时隙的协议允许使用多个时隙完成数据分　

组传输。最近提出的ＳＴ—ＭＡＣ【ｌｊ＿ｊ是第一个跨时隙的　

ＴＤＭＡ协议，该协议以整个网络的冲突状态图为基　

础，采用集中式算法计算各个节点的最优发送时　

隙。ＳＴ—ＭＡＣ需要收集全局信息并且假设网络中的　

任意链路时延都是发送帧时的整数倍，通过分配时　

隙的方式，使得不同节点的帧到达目的端的时隙不　

相同（即不会产生冲突）。该协议的时隙长度比传　

统协议要短的多，利用链路时延的差异性减少了接　

收帧之间的空闲时间，与传统的单时隙的ＴＤＭＡ　

相比提高了网络流量。本文提出的ＣＴ．ＴＤＭＡ和　

ＳＴ—ＭＡＣ相比，不依赖于时延与帧时关系的假设，　

并且采用连续时间的分配方式代替时隙分配，减少　

了信道空闲时间，提高了网络流量。　

除了ＴＤＭＡ之外，研究者还提出了针对水下　

环境的改进ＣＤＭＡ协议Ｉｌ。’　１，文献【ｌ９】提出的混合　

协议使用对节点分簇的策略，簇内节点通信使用　

ＴＤＭＡ协议，不同的簇之问的节点通信则使用　

ＣＤＭＡ协议。然而目前在ＵＷＳＮ中使用ＣＤＭＡ协　

议还面临很多困难，对大规模的传感器节点分配伪　

随机码是一项艰巨的挑战，此外，水声通信中使用　

ＣＤＭＡ的远近效应问题也没有得到很好地解、决Ｉ埽Ｊ。　

５结束语　

针对水下无线传感器网络时延高、带宽低和误　

码率高的特性，本文提出了以发送端为中心以连续　

时间为计量单位的冲突状态模型——局部冲突状态　

・１７４・　通信学报　第３３卷　

图（ＬＣＧ）及其分布式构建算法，并在此基础上设　

计了基于启发式规则的水下传感器网络ＴＤＭＡ协　

ＩＥＥＥ　ＩＮＦＯＣＯＭ［Ｃ］．Ａｎｃｈｏｒａｇｅ，Ａｌｓｋａ，ＵＳＡ，２００７．ａ２２７１—２２７５．　

【１　１］ＰＡＲＫ　Ｍ，ＲＯＤＯＰＬＵ　Ｖ．ＵＷＡＮ—ＭＡＣ：ａｎ　ｅｎｅｒｇｙ－ｅｆｉｃｉｆｅｎｔ　ＭＡＣ　

ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｗｉｍｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ　

Ｊｏｕｒｎａｌ　ｏｆＯｃｅａｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００７，３２（３）：７１０—７２０．　

［１２］ＫＵＲＴＩＳ　Ｉ，ＫＲＥＤＯ　Ｂ，ＭＯＨＡＰＡＴＲＡ　Ｐ．Ａ　ｈｙｂｒｉｄ　ｍｅｄｉｕｍ　ａｃｃｅｓｓ　

议。ＣＴ．ＴＤＭＡ利用ＵＷＳＮ中同一接收节点与不同　

发送节点之间链路时延的差异性，与现有协议相比　

进一步减少了节点接收帧序列的空闲时间，提高了　

网络流量。并且，基于启发式规则的分配算法，有　

效缩短了节点在连续时间轴上进行时刻分配的运　

行时间。仿真表明，与ＳＴ—ＭＡＣ和Ｓ—ＴＤＭＡ等基　

ｃｏｎｔｒｏｌ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＡＣＭ　

ＷＵＷＮＥＴ［Ｃ］．Ｍｏｎｔｒｄａｌ，Ｑｕｄｂｅｃ，Ｃａｎａｄａ，２００７．３３—４Ｏ．　

【１３】ＨＳＵ　Ｃ　Ｃ，ＬＡＩ　Ｋ　Ｆ，ＣＨＯＵ　Ｃ　Ｆ．ＳＴ—ＭＡＣ：ｓｐａｔｉｌ—ａｔｅｍｐｏｒａｌ　ＭＡＣ　

ｓｃｈｅｄｕｌｉｎｇ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＩＥＥＥ　ＩＮＦＯ—　

于时隙分配的水下传感器网络ＴＤＭＡ协议相比，　

ＣＴ．ＴＤＭＡ能够实现更高的网络流量和更低的端到　

端传播时延。　

参考文献：　

［１】李建中，高宏．无线传感网络的研究进展［Ｊ】．计算机研究与发展，　

２００８，４５（１）：１－１５．　

ＬＩ　Ｊ　ｚ．ＧＡＯ　Ｈ．Ｒｅｓｅａｒｃｈ　ｐｒｏｇｒｅｓｓ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．　

Ｊｏｕｒｎａｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００８，４５（１）：１－１５．　

［２１李瑞芳，李仁发，罗娟．无线多媒体传感器网络ＭＡＣ协议研究综　

述［Ｊ］．通信学报，２００８，２９（８）：１１１－１２３．　

ＬＩ　Ｒ　Ｆ，ＬＩ　Ｒ　Ｆ，ＬＵＯ　Ｊ．Ｒｅｓｅａｒｃｈ　ｒｅｖｉｅｗ　ｏｎ　ＭＡＣ　ｐｒｏｔｏｃｏｌｓ　ｏｆ　ｗｉｒｅ—　

ｌｅｓｓ　ｍｕｌｔｉｍｅｄｉａ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００８．　

２９（８）：１１１－１２３．　

［３］ＨＥＩＤＥＭＡＮＮ　Ｊ，ＬＩ　Ｙ，ＳＹＥＤ　Ａ．Ｒｅｓｅａｒｃｈ　ｃｈａｌｌｅｎｇｅｓ　ａｎｄ　ａｐｐｌｉｃａ－　

ｉｔｏｎｓ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｉｎｇ【Ａ】．Ｐｒｏｃ　ＷＣＮＣｆＣ】．Ｌａｓ　

Ｖｅｇａｓ，ＮＶ，ＵＳＡ，２００６．２２８－２３５．　

［４］ＳＹＥＤ　Ａ，ＨＥＩＤＥＭＡＮＮ　Ｊ．Ｔｉｍｅ　ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｆｏｒ　ｈｉｇｈ　ｌａｔｅｎｃｙ　

ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＩＮＦＯＣＯＭ　２００６［Ｃ］．Ｂａｒｃｅｌｏｎａ，Ｃａｔａｌｕｎｙａ，　

Ｓｐａｉｎ，２００６．１－１２．　

［５】ＨＡＲＲＩＳ　Ａ　Ｆ　ＩＩＩ，ＳＴＯＪＡＮＯＶＩＣ　Ｍ，ＺＯＲＺＩ　Ｍ．Ｗｈｅｎ　ｕｎｄｅｒｗａｔｅｒ　

ａｃｏｕｓｔｉｃ　ｎｏｄｅｓ　ｓｈｏｕｌｄ　ｓｌｅｅｐ　ｗｉｔｈ　ｏｎｅ　ｅｙｅ　ｏｐｅｎ：Ｉｄｌｅ・ｔｉｍｅ　ｐｏｗｅｒ　ｍａｎ—　

ａｇｅｍｅｎｔ　ｉｎ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ【Ａ】．Ｐｒｏｃ　ＡＣＭ　ＷＵＷＮＥＴ［Ｃ］．　

Ｌｏｓ　Ａｎｇｅｌｅｓ，ＣＡ，ＵＳＡ，２００６．１０５—１０８．　

【６］ＳＹＥＤ　Ａ，ＹＥ　Ｗ，ＨＥＩＤＥＭＡＮＮ　Ｊ．Ｕｎｄｅｒｓｔａｎｄｉｎｇ　ｓｐａｔｉａｌ－ｔｅｍｐｏｒｌａ　

ｕｎｃｅｒｔｉａｎｔｙ　ｉｎ　ｍｅｄｉｕｍ　ａｃｃｅｓｓ　ｗｉｔｈ　ＡＬＯＨＡ　ｐｒｏｔｏｃｏｌｓ［Ａ］．Ｐｒｏｃ　ＡＣＭ　

ＷＵＷＮＥＴ［Ｃ］．Ｍｏｎｔｒｄａｌ，Ｑｕｄｂｅｃ，Ｃａｎａｄａ，２００７．４１—４８．　

［７］　ＳＹＥＤ　Ａ，ＹＥ　Ｗ，ＨＥＩＤＥＭＡＮＮ　Ｊ．Ｔ－ｌｏｈｉ：ａ　ｎｅｗ　ｃｌｓａｓ　ｏｆ　ＭＡＣ　ｐｒｏ．　

ｔｏｃｏｌｓ　ｆｏｒ　ｕｎｄｅ－ｗｒａｔｅｒ　ａｃｏｕｓｔｉｃ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．ＩＥＥＥ　ＩＮＦＯ．　

ＣＯＭ［Ｃ］．Ｐｈｏｅｎｉｘ，ＡＺ，ＵＳＡ，２００８．２３１—２３５．　

［８】ＧＵＯ　Ｘ，ＦＲＡＴＥＲ　Ｍ，ＲＹＡＮ　Ｍ．Ａ　ｐｒｏｐａｇａｔｉｏｎ—ｄｅｌａｙ－ｔｏｌｅｒａｎｔ　ｃｏｌｌｉ—　

ｓｉｏｎ　ａｖｏｉｄａｎｃｅ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．　

ＯＣＥＡＮＳ　２００６一Ａｓｉａ　Ｐａｃｉｉｆｃ［Ｃ］．Ｓｉｎｇａｐｏｒｅ，２００６．１—６．　

［９】ＭＯＬＩＮＳ　Ｍ，ＳＴＯＪＡＮＯＶＩＣ　Ｍ．Ｓｌｏｔｔｅｄ　ＦＡＭＡ：ａ　ＭＡＣ　ｐｒｏｔｏｃｏｌ　ｏｆｒ　

ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．ＯＣＥＡＮＳ　２００６－Ａｓｉａ　Ｐａｃｉｆｉｃ［Ｃ］．　

Ｓｉｎｇａｐｏｒｅ，２００６．１・７．　

［１Ｏ】ＣＨＩＲＤＣＨＯＯ　Ｎ，ＳＯＨ　Ｗ，ＣＨＵＡ　Ｋ．Ａｌｏｈａ－ｂａｓｅｄ　ＭＡＣ　ｐｒｏｔｏｃｏｌｓ　

ｗｉｔｈ　ｃｏｌｌｉｓｉｏｎ　ａｖｏｉｄａｎｃｅ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　

ＣＯＭ［Ｃ］．Ｒｉｏ　ｄｅ　Ｊａｎｅｉｒｏ，Ｂｒａｚｉｌ，２００９．１８２７　１８３５．　

［１４】ＨＯＮＧ　Ｌ，ＨＯＮＧ　Ｆ，ＧＵＯ　Ｚ　Ｗ．Ａ　ＴＤＭＡ．ｂａｓ酣ＭＡＣ　ｐｒｏｔｏｃｏｌ　ｉｎ　

ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｔｈｅ　４ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

Ｗｉｒｅｌｅｓｓ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎｅｔｗｏｒｋｉｎｇ，ａｎｄ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　

（ＷＩＣＯＭ’Ｏ８）【Ｃ］．Ｄａｌｉｎａ，Ｃｈｉｎａ，２００８．１—４．　

［１５］ＤＯＷＮＥＹ　Ｐ．Ｔｈｅ　Ｂｅｈａｖｉｏｒ　ｏｆ　ａ　Ｆｌｏｏｄｉｎｇ　Ｐｒｏｔｏｃｏｌ　ｉｎ　ａ　Ｗｉｒｅｌｅｓｓ　

Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋ［Ｒ］．Ｒｅｐｏｒｔ　ｆｏｒ　ｔｈｅ　Ｈｏｎｏｕｒｓ　Ｐｒｏｇｒａｍｍｅ　ｏｆ　ｈｔｅ　Ｓｃｈｏｏｌ　

ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，ｔｈｅ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　

Ｗｅｓｔｅｒｎ　Ａｕｓｔｒｌａｉａ，２００３．　

［１６］ＬＩＵ　ＹＨ，ＬＩＯＮＥＬ　Ｍ．Ｎｉ：ａ　ｇｅｎｅｒａｌｉｚｅｄ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｔｏｐｏｌｏｇｙ　ｃｏｎｔｒｏｌ　

ｏｆｒ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．１ＮＦＯＣＯＭ　２００９［Ｃ］．Ｒｉｏ　ｄｅ　Ｊａｎｅｉｒｏ，　

Ｂｒａｚｉｌ，２００９．２７７６—２７８０．　

［１７］ＬＵＢＹ　Ｍ．Ａ　ｓｉｍｐｌｅ　ｐａｒａｌｌｅｌ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｍａｘｉｍａｌ　ｉｎｄｅｐｅｎｄｅｎｔ　

ｓｅｔ　ｐｒｏｂｌｅｍ［Ｊ］．ＳＩＡＭ　Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｐｕｔｉｎｇ，１９８６，１５（４）：１０３６—１０５３．　

［１８］ＴＡＮ　Ｈ　Ｘ，ＳＥＡＨ　Ｗ　Ｋ　Ｇ．Ｄｉｓｔｒｉｂｕｔｅｄ　ＣＤＭＡ—ｂａｓｅｄ　ＭＡＣ　ｐｒｏｔｏｃｏｌ　

ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．ＬＣＮ［Ｃ］．Ｃｌｏｎｔａｒｆ　Ｃａｓｔｌｅ，Ｄｕｂｌｉｎ，　

Ｉｒｅｌａｎｄ．２００７．２６—３６．　

［１９】ＳＡＬＶＡ—ＧＡＲＡＵ　Ｆ，ＳＴＯＪＡＮＯＶＩＣ　Ｍ．Ｍｕｌｔｉ．ｃｌｕｓｔｅｒ　ｐｒｏｔｏｃｏｌ　ｏｆｒ　ａｄ　

ｈｏｃ　ｍｏｂｉｌｅ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＩＥＥＥ　Ｏｃｅａｎｓ　

Ｃｏｎｆ［Ｃ］．Ｓａｎ　Ｄｉｅｇｏ，ＣＡ，ＵＳＡ，２００３．９１—９８．　

作者简介：　

洪璐（１９８４一），　男，山东济宁人，中　

国海洋大学博士生，　主要研究方向为传感　

器网络和容迟网络。　

洪锋（１９７７一），男，山东青岛人，中国海洋大学副教　

授，主要研究方向为传感器网络、对等计算和网格计算。　

李正宝（１９８１．），男，山东济宁人，中国海洋大学博　

士生，主要研究方向为传感器网络和容迟网络。　

郭忠文（１９６５一），男，山东青岛人，中国海洋大学教　

授、博士生导师，主要研究方向为传感器网络和海洋信息分　

布式处理技术。　

2024年3月20日发(作者：琴闵)

第３３卷第２期　

２０１２年２月　

通信学报　

Ｖ０ｌ３３　ＮＯ．２　

Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｆｅｂｒｕａｒｙ２０１２　

ＣＴ．ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　

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

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

摘要：针对水下无线传感器网络（ＵＷＳＮ，ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ）提出以发送端为中心以连续时间为计量　

单位的冲突状态模型——局部冲突状态图及其分布式构建算法，并在此基础上设计了基于启发式规则的水下传感　

器网络ＴＤＭＡ协议（ＣＴ－ＴＤＭＡ，ｃｏｎｔｉｎｕｏｕｓ　ｔｉｍｅ　ｂａｓｅｄ　ＴＤＭＡ）。ＣＴ－ＴＤＭＡ利用ＵＷＳＮ中同一接收节点与不同　

发送节点之问链路时延的差异性，减少在目的端的接收帧之间的空闲时间，从而提高网络流量；基于启发式规则　

的分配算法，能有效缩短连续时间轴上的时刻分配所花费的时间。模拟实验证明：ＣＴ—ＴＤＭＡ与以ＳＴ．ＭＡＣ为代　

表的按时隙分配的ＴＤＭＡ方案相比，网络流量提高了２０％，数据分组的端到端时延降低了１８％；与由全局知识　

所计算出的最优分配策略相比，网络流量达到了８０％，端到端时延仅延长了１２％。　

关键词：水下传感器网络；ＭＡＣ协议；ＴＤＭＡ；ＳＴ．ＭＡＣ　

中图分类号：ＴＰ２１２．９　文献标识码：Ａ　文章编号：１０００－４３６Ｘ（２０１２）０２—０１６４－１１　

ＣＴ—ＴＤＭＡ：ｅｆｆｉｃｉｅｎｔ　ＴＤＭＡ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　

ＨＯＮＧ　Ｌｕ，ＨＯＮＧ　Ｆｅｎｇ，ＬＩ　Ｚｈｅｎｇ—ｂａｏ，ＧＵＯ　Ｚｈｏｎｇ—ｗｅｎ　

（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｍｒＳｃｉｅｎｃｅ，ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎ　ＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＯｃｅａｎＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎａ，Ｑｉｎｇｄａｏ２６６１００，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｉｍｅｄ　ａｔ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｉｔｃ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｓ（ｋＵＷＳＮ），ａ　ｎｏｖｅｌ　ｓｅｎｄｅｒ　ｂａｓｅｄ　ｃｏｎｆｌｉｃｔ　ｍｏｄｅｌ　ｗｉｔｈ　ｈｅ　ｔｓｃｈｅｍｅｓ　

ｏｆａｌｌｃａｔｏｉｎｇ　ｃｏｎｔｉｎｕｏｕｓｔｉｍｅｗａｓ　ｐｒｅｓｅｎｔｄ，ｉｅｎｃｌｕｄｉｎｇｌｏｃａｌ　ｃｏｎｌｉｆｃｔｇｒａｐｈ（ＬＣＧ）ａｎｄ　ａｄｉｓｔｒｉｂｕｔｅａｌｇｏｒｉｔｈｍｔｏ　ｇｅｎｅｒａｔｅ　

ＬＣＧ．Ｍｏｒｅｏｖｅｒ，ＣＴ－ＴＤＭＡ，ａｎ　ｅｆｆｉｃｉｅｎｔ　ＴＤＭＡ　ｐｒｏｔｃｏｌｏ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｃｏｎｆｌｉｃｔ　ｍｏｄｅｌ　Ｗａｓ　ａｌｓｏ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｕｓｅｄ　

ｈｅｕｒｉｓｔｉｃｐｒｉｏｒｉｔｙ　ｒｕｌｅｓｔｏ　ａｌｌｏｃａｔｅｔｒａｎｓｍｉｔｔｉｎｇｍｏｍｅｎｔｓｆｏｒａｌｌｎｏｄｅｓ．ＣＴ－ＴＤＭＡ　ｅｘｐｌｏｉｓｔｔｈｅ　ｄｉｖｅｒｓｉｔｙｏｆｐｒｏｐａｇａｔｉｏｎｄｅｌａｙｏｆ　

ｄｉｆｆｅｒｅｎｔｌｉｎｋｓｉｎＵＷＳＮｔｏ　ｄｅｃｒｅａｓｅｔｈｅｉｄｌｅｔｉｍｅｂｅｔｗｅｅｎｐａｃｋｅｔｓ　ａｔｔｈｅ　ｓａｍｅ　ｒｅｃｅｉｖｉｎｇ　ｎｏｄｅ，ｗｈｉｃｈｈｅｌｐｓｉｎｉｍｐｒｏｖｉｎｇｔｈｅ　

ｔｈｒｏｕｇｈｐｕｔ．Ａｎｄ　ａ　ｈｅｕｒｉｓｔｉｃ　ｓｃｈｅｄｕｌｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｐｐｌｉｄ　ｅｔｏ　ｓｈｏｒｔｅｎ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ａｌｌｏｃａｔｉｎｇ　ｃｏｎｔｉｎｕｏｕｓ　ｔｉｍｅ　ｆｏｒ　ｅａｃｈ　ｎｏｄｅ．　

Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｌｔｕｓ　ｓｈｏｗｔｈａｔ，ｃｏｍｐａｒｅｄｗｉｈｔｔｒａｄｉｔｉｏｎａｌＴＤＭＡｐｒｏｔｏｃｏｌｓ　ｓｕｃｈａｓＳＴ－ＡＣ，ｎｅｔＭｗｏｒｋｔｈｒｏｕｇｈｐｕｔｏｆＣＴ－ＴＤＭＡ　

ｈａｓｉｎｃｒｅａｓｅｄ　２０％ａｎｄ　ｅｎｄｔｏ　ｅｎｄｄｅｌａｙｈａｓｄｅｃｒｅａｓｅｄ　１８％：ｃｏｍｐａｒｅｄｔｏｔｈｅｔｈｅｏｒｅｔｉｃａｌｌｙｏｐｔｉｍａｌｓｃｈｅｍｅｗｉｔｈｇｌｏｂａｌｋｎｏｗｌ－　

ｅｄｇｅ，ＣＴ－ＴＤＭＡｈａｓａｃｈｉｅｖｅｄ８０％ｎｅｔｗｏｒｋｔｈｒｏｕｇｈｐｕｔａｎｄｔｈｅｅｎｄｔｏｅｎｄｄｅｌａｙｉｓｏｎｌｙ　１２％ｌｏｎｇｅｒ．　

Ｋｅｙ　ｗｏｒｄｓ：ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ；ＭＡＣ　ｐｒｏｔｏｃｏｌｓ；ＴＤＭＡ，ＳＴ—ＭＡＣ　

言　

水下无线传感器网络（ＵＷＳＮ，ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　

ｎｅｔｗｏｒｋｓ）将采集到的海洋环境数据发送给用户来辅　

收稿日期：２０１０—０６—１７；修回日期：２０１０—１１—１８　

蒌　溢　探　

ＵＷＳＮ的重要特点是，主要通信方式只能采用　

水声通信。这是因为高频无线信号会被海水吸收，　

基金项目：国家自然科学基金资助项目（６０７０３０８２，６０８７３２４８，６０９３３０１１，６０９７０１２９）；青岛市科技发展计划基金资助项目　

（１０—３—４—１・６－ｊｃｈ１　

Ｆｏｕｎｄａｔｉｏｎ　Ｉｔｅｍｓ：Ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒｌａ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（６０７０３０８２，６０８７３２４８，６０９３３０１１，６０９７０１２９）；Ｓｃｉｅｎｃｅ　ｎｄ　ａ

Ｔｅｃｈｎｏｌｏｇｙ　Ｄｅｖｅｌｏｐｍｅｎｔ　Ｐｒｏｇｒａｍ　ｏｆ　Ｑｉｎｇｄａｏ（１０－３—４－１－６￣ｃｈ）　

第２期　洪璐等：ＣＴ．ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１６５・　

光信号也会因海水散射和反射而大量损耗，两者均　

不能满足水下长距离通信的要求。与无线电信号相　

比，水声通信的主要特点是：传播时延大，水声信　

号的传播速率仅为１　５００ｍ／ｓ；通信距离长且带宽低，　

通信距离一般在１～１０ｋｍ级别，通信带宽仅在１０ｋＨｚ　

级别；误码率高、多途现象和多普勒频移现象均会　

导致传输错误　。　

由于水声通信的传播时延高和通信距离长，发　

送端无法判断信道是否冲突；同时，由于低带宽和　

误码率高的特性，使得ＵＷＳＮ中每次通信的分组　

长度必须受到限制。因此，解决ＵＷＳＮ的ＭＡＣ问　

题的关键在于接收端判断冲突是否发生。　

目前，国内外的研究者在ｕｗＳＮ的ＭＡＣ问题　

上展开了深入的研究，主要包括接入竞争控制协议　

和无冲突接入协议２种。接入竞争控制协议，通过　

以接收端为中心的虚拟载波监听协议来解决ＭＡＣ　

问题【６　们，但由于水声通信的时延长，虚拟载波监　

听的握手机制降低了数据通信时间的比例，导致网　

络流量较低。　

无冲突接入协议主要采用时分复用接入（１［１　Ａ），　

即采用集中式的方式来向ＵＷＳＮ内各个节点分配　

通信时间片Ｉｌ卜Ｈ】。此类协议可根据数据传输完成需　

要的时隙数分为２种。第一种ＴＤＭＡ算法要求，　

一

跳范围内的数据传输必须在一个时隙完成，称之　

为单时隙协议Ｉ１　’１２］ｏ单时隙协议的主要问题在于，　

为了保证不同距离的节点对在一个时隙内均能完　

成通信，时隙必须由最大的链路时延决定。时隙的　

长度是发送帧时和网络中最大链路时延之和，该问　

题同样影响了网络流量的提高。　

为了提高网络流量，研究者提出了允许跨时隙　

完成数据传输的ＳＴ－ＭＡＣ协议Ｉｌ　。该协议假设所有　

的链路时延都是帧时的整数倍，利用启发式规则完　

成多跳网络的时隙分配，实现了较高的网络流量。　

基于时隙的分配本质上是分配各个节点的发　

送时刻。如果能不采用按时隙分配，而直接在连续　

时间轴上对每个节点分配发送时刻，将更好地利用　

ＵＷＳＮ网络中同一接收节点与不同发送节点之间　

链路时延的差异性，降低接收帧之间的空闲时间，　

提高网络流量。因此，本文提出了以连续时间分配　

为出发点的水下传感器网络的ＴＤＭＡ协议　

（ＣＴ—ＴＤＭＡ，ｃｏｎｔｉｎｕｏｕｓ　ｔｉｍｅ　ｂａｓｅｄ　ＴＤＭＡ）。　

ＣＴ—ＴＤＭＡ的核心思想是，每个节点利用收集　

到的局部网络拓扑信息，以自身的发送行为可能引　

起的冲突为依据，分布式地计算局部冲突状态图　

（ＬＣＧ，ｌｏｃａｌ　ｃｏｎｆｌｉｃｔ　ｇｒａｐｈ）。所有节点按照启发式　

规则计算自己的优先级，然后根据ＬＣＧ图中的所　

有邻居的优先级顺序完成发送时刻的标定。优先级　

计算的启发式规则综合了节点的度、负载和链路时　

延等重要因素，在有效缩短连续时间轴上时刻分配　

问题的计算时间的同时，保证了ＴＤＭＡ协议的流　

量和端到端时延等性能指标。　

本文的主要贡献如下。　

１）针对水下传感器网络在ＭＡＣ层设计上的独　

特问题——同一接收节点与不同发送节点之间链路　

时延的差异性不可忽略，设计了以发送端为中心以　

连续时间为计量单位的冲突状态模型——局部冲突　

状态图。在此基础上，本文提出了分布式的局部冲突　

状态图构建算法：每个节点利用以通信半径和干扰　

半径之和为半径的覆盖圆内的网络拓扑信息，分布　

式计算局部冲突状态图。　

２）提出了基于启发式规则的水下传感器网络　

ＴＤＭＡ协议，即节点以其局部冲突状态图为分配依　

据，以节点的度、负载和链路时延计算优先级，按　

照优先级顺序进行发送时刻标定。该启发式算法有　

效缩短了连续时间轴上时刻分配问题的运行时间。　

３）ＣＴ—ＴＤＭＡ协议采用基于连续时间的接入分　

配算法，与基于时隙的ＴＤＭＡ协议相比，缩短了　

目的端的接收帧之间的空闲时间，提高了接收端的　

信道利用率及整个网络的流量。模拟实验证明：在　

实验时间段内，ＣＴ．ＴＤＭＡ方案与以ＳＴ—ＭＡＣ为代　

表的ＴＤＭＡ方案相比，网络流量提高了２０％，数　

据分组的端到端时延降低了１８％；与由全局知识所　

计算出的最优分配策略相比，网络流量达到了　

８０％，数据分组的端到端时延仅延长了１２％。　

本文其余部分组织如下：第２节对ＣＴ．ＴＤＭＡ　

设计方案进行详细介绍；第３节分析ＣＴ＿ＴＩ）ＭＡ的　

仿真实验结果，第４节概述近几年ＵＷＳＮ的ＭＡＣ　

问题的相关研究成；第５节是结束语。　

２　ＣＴ．　ｒＤＭ＿Ａ设计　

本节首先通过示例说明ＣＴ。ＴＤＭＡ的设计出发　

点，进而对基于连续时间的冲突状态模型——局部　

冲突状态图进行了详细说明。其次详细介绍　

ＣＴ—ＴＤＭＡ的执行过程，并给出关键函数和过程的　

伪代码描述。然后讨论了ＣＴ－ＴＤＭＡ中用于判断节　

点接入优先级的启发式规则。最后，结合实例来展　

通信学报　第３３卷　

示ＣＴ—ＴＤＭＡ的运行过程和运行结果。　

２．１设计出发点　

解决ＵＷＳＮ的ＭＡＣ问题的关键在于，唯有接　

收端才能判断数据分组冲突是否发生。如图１（ａ）所　

示，节点Ａ和　向节点Ｃ发送数据。设　ｃ和Ｄ　ｃ　

为链路ＡＣ和ＢＣ的传播时延且ＤａＧ＜ＤＢｃ，Ｔ为数　

据分组发送时间即帧时，　和ｔｂ为节点Ａ和　的传　

输时刻。　

在陆地传感器网络中，由于无线电信号的传播　

时延可以忽略，因此ＴＤＭＡ方案的时隙长度为　

只要由发送端Ａ和　选择不同的时隙发送即可避免　

冲突。然而，ＵＷＳＮ的链路的传播时延不可忽略，　

为了保证相邻时隙发送的帧无冲突，在本例中时隙　

长度至少为ＤＢｃ＋丁。因此，接收端ｃ接收到的帧序　

列在时间轴将变得稀疏，如图１（ｂ）所示。　

Ｃ　

（ａ）Ｎ络拓扑　

÷—　

ｃ　ｃ—　

：　：　，，　，，　：　，　，一　

Ｂ

ｊ

：

口　

：‘ｂ　

ｉ

：

口　

（ｂ）时隙分配的ＴＤＭＡ　（ｃ）连续时间分配的ＴＤＭＡ　

图１　ＴＤＭＡ不同策略下的发送时间的分配　

而理想的ＴＤＭＡ效果应如图１（ｃ）所示，Ａ选择　

时刻发送数据帧，则该帧到达Ｃ的时刻为ｔａ＋ＤＡｃ。　

为使得Ｃ接收到的帧序列间的空闲尽可能小，那么　

发送的帧到达Ｃ的时刻应为　＋　ｃ＋　（即Ａ发　

送帧的帧尾和曰发送帧的帧头相接），所以日节点　

的发送时刻应为ｔｂ＝ｔａ＋Ｄａｃ＋　ｉｃ。　

图ｌ给出了ＵＷＳＮ网络的普通拓扑情况。该　

例说明基于连续时问的接入分配相比于基于时隙的　

ＴＤＭＡ方案，能够提高接收端的流量。基于连续时间　

的分配充分利用了ＵＷＳＮ的链路时延长和数据分组　

短的特性，这正是ＣＴ．ＴＤＭＡ设计的出发点。　

２．２连续冲突状态模型　

为了清晰地描述ＣＴ．ＴＤＭＡ的连续冲突状态模　

型，本节首先对运行环境做一些基本设定。　

１）使用圆型通信和干扰模型，即节点的通信范　

围和干扰范围都是一个以自己为圆心的圆。网络中　

节点都是同构的，具有相同的通信半径Ｒ　（ｔｒａｎｓ．　

ｍｉｓｓｉｏｎ　ｒａｄｉｕｓ）和干扰半径ＲＩ（ｉｎｔｅｒｆｅｒｅｎｃｅ　ｒａｄｉｕｓ）。　

传感器网络中的干扰半径尺Ｉ是对节点信号的干扰　

覆盖范围的一种描述：当源节点进行发送时，以源　

节点为圆心、ＲＩ为半径的覆盖圆内的所有节点都由　

于源节点发送数据所带来的干扰，而不能正常接收　

来自其他节点的数据分组【１　１６］ｏ　ＲＩ在网络部署前进　

行测定，并与通信半径一样作为协议的初始化参数　

进行设定。　

２）节点通过时钟同步算法，保证足够的同步精　

确度。　

ＣＴ—ＴＤＭＡ的连续冲突状态模型包括局部冲突状　

态图和禁止时间计算规则。其关键术语的定义如下。　

定义１覆盖范围函数Ｃｏｖ（Ｎ，　）：以节点Ⅳ为　

圆心，以　为半径的区域。如节点Ⅳ　，Ｙｎ）通信范　

围Ｃｏｖ（Ｎ，ＲＴ）＝｛　，ｙ）ｌ（ｘ．　）　＋　一Ｙ　）　≤　Ｔ２ｌ；干扰范　

围Ｃｏｖ（Ｎ，尺Ｉ）＝｛（ｘ，ｙ）ｌ（ｘ－ｘｏ）　＋（）＇－Ｙ　）　≤　Ｉ　｝　

定义２求取某区域内的节点集的操作Ｎｏｄｅ．　

ｓｅｔ（ｃ）：Ｃ为水下传感器网络的某个部署区域，操作　

返回属于该区域的节点集，即Ｎｏｄｅｓｅｔ（Ｃ）＝｛ⅣＩ（Ｘｎ，Ｙ　）　

∈Ｃ｝。　

定义３冲突：节点不能够同时发送和接收，　

不能够同时接收２个以上的数据分组，所有违反这　

２条原则的发送和接收均称为冲突。以图２为例，　

如果ｉ和

．

ｆ的信号同时到达ｋ，ｋ将无法正常接收ｆ　

的数据分组；如果ｉ的信号到达ｋ时ｋ正在发送，ｋ　

也无法正常接收ｉ的数据分组，此２种情形均称为　

冲突。　

定义４冲突邻居、冲突目标节点：节点之间　

的冲突关系是网络物理拓扑和逻辑拓扑的直接反　

映。设Ⅳ为网络中的任一发送节点，节点Ⅳ的发送　

操作对周围节点可能造成的冲突主要表现在：对于　

不同于Ⅳ的节点　而言，如果存在节点Ｐ，满足Ｐ　

的位置在物理拓扑中位于Ｍ和Ⅳ其中一个节点的　

通信范围内，同时位于另一节点的干扰范围内，并　

且，在逻辑拓扑中存在链路Ｎ一＞Ｐ或者Ｍ一＞Ｐ，那　

么Ｐ节点在接收Ⅳ或者Ｍ其中一个节点的数据分　

组时，可能会受到来自另一节点的发送信号的干扰　

而无法接收，即在Ｐ点形成冲突。　

对于节点Ⅳ来说，其干扰范围内的所有邻居都　

有可能由于节点Ⅳ的发送而成为冲突发生点。因此，　

节点Ⅳ的冲突目标节点和冲突邻居定义如下：　

当节点Ｐ、Ｍ同时满足下列拓扑条件时，节点　

第２期　洪璐等：ＣＴ—ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１６７・　

Ｐ是节点Ｊ７ｖ的冲突目标节点，节点　是节点Ｊ７ｖ的　

冲突邻居：　

中，因此冲突邻居也就是节点的ＬＣＧ邻居。　

以图２为例，节点ｋ是节点ｆ和节点７的冲突　

．

①物理拓扑条件：　

尸∈Ｎｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，ＲＴ）ｎ　Ｃｏｖ（Ｍ，ＲＯ）ｌｌ　

ｐ　Ｅ　Ｎｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，ＲＩ）ｎ　Ｃｏｖ（Ｍ，　Ｔ））　

目标节点，那么节点ｉ的ＬＣＧ图中存在边ｆ＿７，权　

值为Ｗｉｊ（ｋ）＝Ｄ　一Ｄ　一０．２。其含义为：如果节点　

选择比节点ｆ晚０．２ｓ进行发送，则在节点ｋ将同时　

接收到节点ｉ的发送信号和节点，发向其他节点的　

．

②逻辑拓扑条件：　一＞Ｐ）ｌＪ（　一＞尸）　

该定义说明，节点的冲突邻居必位于它的　

（ＲＩ＋尺Ｔ）的覆盖范围内。如图２中，节点ｋ处于节点　

数据信号的干扰能量，从而发生冲突。　

对于节点ｉ和节点ｋ来说，Ｎｏｄｅｓｅｔ（Ｃｏｖ（ｉ，ＲＴ）ｎ　

Ｃｏｖ（ｋ，ＲＩ））＝｛ｆ，ｋ｝，并且仅链路ｆ一＞足存在，由定义　ｆ的通信范围和节点７的干扰范围内，同时链路ｆ一＞足　

存在，因此节点７是节点ｆ的冲突邻居，节点ｋ为　

相应的冲突目标节点。对于节点ｎ来说，节点ｎ和　

节点ｆ相距较远，且两者的通信范围和干扰范围的　

交集范围内不存在节点，因此不满足上述定义中的　

物理拓扑条件，所以节点ｎ不是节点ｆ的冲突邻居。　

图２节点ｉ的局部网络拓扑结构　

定义５局部冲突状态图（ＬＣＧ，ｌｏｃａｌ　ｃｏｎｆｌｉｃｔ　

ｇｒａｐｈ）：节点ｉ的冲突状态图是一个以节点ｉ为中　

心的带权多重图，描述所有和ｆ的发送行为有关的　

冲突。ＬＣＧ中的顶点为ｉ及其所有的冲突邻居。ＬＣＧ　

图中边的权值定义为：如果节点

．

７为节点ｉ的冲突　

邻居，其冲突目标节点为ｋ，且链路　和

．　

的时延　

分别为Ｄｉｋ和Ｄ　，则边ｆ＿７的权值为　

（　）＝Ｄｉｋ—Ｄｊｋ　（１）　

为了表达式的一般性，定义Ｄ　０。　

ｆ（　用来描述节点ｉ和节点

．

７发送的数据在接　

收点ｋ产生冲突的状态。　肚）取正值表示，如果节　

点ｉ选择比节点

．

７早　肚）的时间进行发送，则会在　

ｋ产生冲突。相应地，如果　，（Ｄ为负值，表示节点　

ｉ选择比节点

．

７晚１ｗｏ（ｋ）ｌ的时间进行发送时会产生冲　

突。由于节点的所有冲突邻居均位于该节点的ＬＣＧ　

４可得，节点ｋ既是节点ｉ的冲突邻居，也是节点ｆ　

和节点ｋ冲突的目标节点，且　（　）＝ｗ＝ｆ　一　３．２。　

这说明如果节点ｉ选择比节点ｋ早３．２ｓ进行发送，　

那么当节点ｉ的数据信号到达节点ｋ时，节点ｋ正　

在向其他节点发送信号，无法接收节点ｉ的数据，　

产生冲突。　

再分析节点ｉ和节点厂的冲突情况，由定义４　

的物理条件得到，Ｎｏｄｅｓｅｔ（Ｃｏｖ（ｉ，ＲＴ）ｎ　Ｃｏｖ（ｆ，ＲＩ））：｛ｆ，　

忌，

．

ｎ。由于链路ｆ一　厂不存在，根据定义４的逻辑拓　

扑条件，．厂不是冲突目标节点。该论断的含义是，．厂　

不接收ｉ的数据分组，因此ｉ发送的信号到达．厂时，　

．

厂可以进行发送，即在．厂节点处不会产生ｉ和．厂的冲　

突。但是链路ｆ一＞　存在，说明ｋ是ｆ和厂的冲突目　

标节点，其含义是ｆ和厂的信号可能同时到达节点ｋ。　

同时，链路　＞ｆ存在，说明ｆ同样是ｉ和．厂的冲突　

目标节点，其含义是ｉ在接收Ｉ厂的信号时，不能向　

其他节点发送数据。因此节点ｆ的ＬＣＧ图中，　ｉ　

和

．

厂之间存在２条边，其权值分别为ｗｉ￣ｋ）＝Ｄｉｋ－Ｄｓ＇ｋ　

＝－

２．２和Ｗｉｊ（ｉ）＝Ｄｉｉ－Ｄｉｆ＝－４．５。　

定义６禁止时间：节点的禁止时间是指在时间　

轴上的一个时间片段内，节点不能够选择发送时　

刻，否则会引起冲突。　

为保证２个节点的帧到达目标时不冲突（即在　

接收端的时间轴上不重叠），对每个发送节点来说　

均有一段时间不能发送，称为禁止时间。以图３为　

例，在节点ｆ的ＬＣＧ中，如果其邻居７选择发送时　

刻ｔｊ，则由节点

．

７决定的节点ｉ的禁止时间定义为（Ｆｌ（ｉ，　

，　，　

（　，Ｊ，　）。其中　

（ｆ，Ｊ，足）＝ｔ　一　，（ｋ）一Ｔ　（２）　

（　，．『，足）＝ｔ　一ｗｉ　（七）＋Ｔ　（３）　

禁止时间的物理含义为，由于节点７的存在和　

其发送时刻ｔｓ的确定，节点ｉ在（Ｆｌ（ｉ，Ｊ，足），Ｆｒ（ｉ，　，　）　

时间段内不能发送数据帧。如图３所示，如果节点　

・１６８・　通信学报　第３３卷　

ｆ选取的发送时刻大于　（ｆ，ｊｆ，　，ｆ发送的帧尾将与　

发送的帧头在相关接收点ｋ产生冲突；当ｆ选取的　

发送时刻稍小于Ｆｒ（ｉ，Ｊ，　，ｆ发送的帧头将与．『发送　

的帧尾在相关接收点ｋ产生冲突。　

Ｉ—————午　—１ｌ　————禁●■止●●时■■间■　ｌ■＝■●＝■｝寸　—　—————————————１　

图３禁止时间的计算　

以图２中的节点ｆ和．７的冲突为例，　＝一０．２，　

假设节点．／选择第２ｓ发送（　＝２），帧时Ｔ＝ｌｓ，则根　

据式（２）和式（３）可得节点．７给节点ｆ带来的禁止时间　

为（１．２，３．２）。以节点ｆ和

．

厂为例，根据前面的分析，　

冲突状态图中边ｆ＿厂的权值有２个，因此假设．厂选　

择０ｓ开始发送，根据公式计算出的－厂给ｆ带来的禁　

止时间也是２段，为（３．５，５．５）ｕ（１．２，３．２）。　

２．３　ＣＴ．ＴＤＭＡ的主要算法　

本节首先介绍局部冲突状态图的生成过程，然　

后介绍ＣＴ—ＴＤＭＡ的算法流程。ＣＴ—ＴＤＭＡ可以适　

用于任何网络拓扑结构，但为了简化说明，本节针　

对最广泛使用的树形拓扑结构进行介绍。　

２．３．１　ＬＣＧ生成算法　

在初始化阶段，每个节点ｆ收集Ｃｏｖ（ｉ，ｅｒ＋尺Ｉ）　

范围内的邻居节点的地理位置信息和逻辑链路信　

息，并计算其冲突区域内所有节点对的信号传播时　

延，得到以该节点为中心的局部网络拓扑结构。对　

于位于节点通信半径之外的邻居，节点通过多跳传　

输的方式获得其对应邻居的相关信息。在计算得到　

Ｃｏｖ（ｆ，Ｒｒ＋尺Ｉ）内的局部网络拓扑结构后，节点运行　

ｃｒｅａｔｅＬＣＧ０函数，按照定义５中给出的规则生成自　

己的ＬＣＧ。　

利用定义４验证

．

７是否是ｆ的冲突邻居。ＰＴＣ０　

和ＬＴＣ０函数用来对节点是否符合冲突的物理拓扑　

条件（ｐｈｙｓｉｃａｌ　ｔｏｐｏｌｏｇｙ　ｃｏｎｄｉｉｔｏｎ）和逻辑拓扑条件　

（１ｏｇｉｃａｌ　ｔｏｐｏｌｏｇｙ　ｃｏｎｄｉｉｔｏｎ）进行判定。针对每一个邻　

居

．

７进行分析：如果存在某个节点ｋ，使得ｋ、Ｊ符　

合冲突的２个条件，满足节点．７是节点ｆ的冲突邻　

居，ｋ是ｊ和

．

７冲突的目标节点，则计算　

Ｗｕ（ｋ）＝Ｄ　一Ｄ豫，并记录到ｆ的ＬＣＧ中。　

算法１　ｃｒｅａｔｅＬＣＧ　０　

１）Ｉｎｐｕｔ：ｖ（ｉ）　

２）Ｏｕｔｐｕｔ：Ｓｔ￣ｃ（ｉ）　

３）ＰＴＣ（Ｎ，Ｐ，　｛　／／物理拓扑条件判定　

４）ｉｆ（ＰＥＮｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，Ｒｒ）ｆ３　Ｃｏｖ（Ｍ，蜀））ｌ　ｌ

ＰＥＮｏｄｅｓｅｔ（Ｃｏｖ（Ｎ，　ｎＣｏｖ（Ｍ，　））　

５１　ｒｅｔｕｒｎ　ｔｒｕｅ　

６、ｅｌｓｅ　

７）　ｒｅｔｕｒｎｆａｌｓｅ　

８）　｝　

９）ＬＴＣ（Ｎ，Ｐ，＾　｛　，／逻辑拓扑条件判定　

ｌｏ）ｉｆ（］Ｎ－＞Ｐ　ＩＩｊＭ－＞Ｐ）　

１１）　ｅｒｔｕｍ　ｔｒｕｅ　

１２）ｅｌｓｅ　

１３）　ｒｅｔｕｒｎｆａｌｓｅ　

１４）｝　

ｃｒｅａｔｅＬＣＧ０　

１５）ｎｅｗ　ＶＬＣＧ＝’，（ｆ）；／／Ｃｏｖ（Ｎ，　邻居顶　

点集　

１６）ｗｈｉｌｅ（　ｃＧ！＝ｎｕｌ１）｛　

１７）　ＶｊＥ’，（ｆ）／／￣，－ｊ－论边ｆ　的情况　

１８）　ＶＬＣＧ＝　Ｇ—Ｕ｝　

１９）　ｎｅｗ　Ｖ’＝’，（ｆ）ＩＩ以下逐个节点分析，ｉ　

节点和．『节点是否会在’，（ｆ）中的节点产生冲突　

２０）　ｗｈｉｌｅ（Ｖ’：＝ｎｕｌ）１｛　，，遍历所有可能的　

冲突目标节点　

２１１　Ｖ七∈Ｖ’　

２２）　Ｖ’＝　’－｛ｋ｝　

２３）　ｆ（ＰＴＣ（ｉ，ｋ，ｊ）＝ｔｒｕｅ＆＆ＬＴＣ（ｉ，ｋ，　

ｊ）＝ｔｒｕｅ）｛　，／冲突邻居和冲突目标节点判定　

２４）　Ｗｕ（ｋ）：Ｄ　ＤＬｋ　

２５）　Ｓｔａｃｋ（ｉ）＝Ｓｔｃｃ（ｉ）Ｕ｛Ｗｕ（ｋ）｝　／／将ｆ　

节点和．『节点的一条边的权值记录到ＳＬＣＧ中　

２６）　）／／ｅｎｄ　ｉｆ　

２７）　｝／／ｅｎｄｗｈｉｌｅ（　’！＝ｎＵ／）１　

２８））　／／ｅｎｄ　ｗｈｉｌｅ（ＶＬｃＧ！＝ｎｕｌ）１　

２９）ｒｅｔｕｒｎＳｔｃ￣（ｉ）　

令’，（ｆ）是节点ｆ的所有Ｃｏｖ（Ｉ，ＲＴ＋尺Ｉ）内的邻居　

节点的集合，Ｓｔｃｃ（ｉ）为ｆ的冲突状态图内所有的边　

的权值集合，算法１描述了节点局部冲突状态图的　

生成过程。　

以图２的拓扑为例，节点ｉ运行ｃｒｅａｔｅＬＣＧ０算　

法后，生成的ＬＣＧ如图４所示。根据前面的分析，　

第２期　洪璐等：ＣＩ＂ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１６９・　

节点．厂和ｆ冲突的目标节点有２个，根据定义５计　

算出边ｆ＿厂有２个权值，因此在局部冲突状态图中　

体现为具有不同权值的多重边。如果２个节点对会　

在多个节点处产生冲突，则ＬＣＧ图中这２个节点　

对之间就会有多重边，且多重边的个数即为冲突目　

标节点的个数。因此，由于节点冲突的多样性，ＬＣＧ　

为带权的多重图。　

ｈ　

图４节点ｉ的局部冲突状态图（ＬｃＧ）　

２．３．２　ＣＴ—ＴＤＭＡ算法流程　

每个节点生成自己的ＬｃＧ图后，就根据由ＬＣＧ　

图每条边所对应的各个禁止时间，来选择自己的发　

送时刻。即选择和所有禁止时间不冲突的最早时　

刻，作为自己的发送时刻。　

但是，当前节点的发送时刻的确定，取决于其　

ＬＣＧ邻居的发送时刻。ＣＴ—ＴＤＭＡ采用优先级和随　

机选择相结合的方式，安排节点的发送时刻标定顺　

序。即优先级最高的节点最先选择发送时刻，选择　

的基本策略是在所有可用的时间段内选择一个最　

早的时间点（选择的过程称为标定）。如果ＬＣＧ　

图中所有未标定节点的优先级相同，各个节点随机　

选择发送时刻。优先级的计算方法，将直接影响　

ＣＴ—ＴＤＭＡ的执行效率。本节先介绍ＣＴ—ＴＤＭＡ的　

算法流程，而计算优先级的启发式规则将在２．３．３　

节中进行讨论。　

ＣＴ—ＴＤＭＡ的完整算法流程包括以下７步。　

１）节点生成自己的ＬＣＧ并计算自己的标定优　

先级。　

２）每个节点向所有的ＬＣＧ邻居广播自己的标　

定优先级，并将自己的状态置为“ｕｎｌａｂｅｌｅｄ”。然　

后，每个节点以分布式方式运行３）～６）步。　

３）如果当前节点在其ＬＣＧ图中的所有未标定　

邻居中拥有最高的优先级，则节点根据由ＬＣＧ得　

到的所有禁止时间段，选择最早的可发送时刻作为　

自己的发送时刻，并将其广播给所有的ＬＣＧ邻居，　

并将状态置为“ｌａｂｅｌｅｄ”。　

４）如果当前节点的所有未标定邻居中存在优　

先级高于自己的邻居，则等待优先级高的节点先标　

定，等待接收相关节点的发送时刻结果并更新自己　

的禁止时间，返回第３）步。　

５）如果当前节点在其ＬＣＧ图中与其他未标定　

的节点拥有相同的优先级，则该节点在时间轴上除　

禁止时间之外的时刻随机选择其发送时刻，并广播　

给所有同优先级的未标定状态的ＬＣＧ邻居。　

６）随机标定的节点选定发送时刻并与所有同　

优先级邻居交换选定结果后，运行Ｊｕｄｇｅ０￣数判断　

是否会产生冲突，若无冲突，则置为“ｌａｂｅｌｅｄ”，　

否则置为“ｕｎｌａｂｅｌｅｄ”，并返回第５）步。　

７）ＬＣＧ图中的所有节点状态均为“ｌａｂｅｌｄｅ”时，　

算法结束。　

算法２　Ｌａｂｅｌ（）　

Ｉｎｉｔｉａｌｉｚａｔｉｏｎ：　

ｌ　１　Ｓ￣（ｉ）＝ｎｕｌｌ；Ｓｔ（ｉ）＝ｕｎｌａｂｅｌｅｄ　

２）　（ｆ）＝Ｕ　ｉｓ　ｆ’Ｓ　ＬＣＧ　ｎｅｉｇｈｂｏｒ｝　

Ｌａｂｅｌ（）　

３）　ｗｈｉｌｅ（３ｊ　Ｅ　Ｓｕ　（ｆ），Ｐ（ｆ）＜Ｐ（，））｛　，／顺序标　

定，节点优先级非最高，等待并接收其他节点标定　

结果　

４）　ｒｅｃｅｖｅ　ｎｏｄｅｊ’Ｓ　ｓｅｌｅｃｔｉｏｎ　ｔｉ　

５）　Ｓｃ（ｉ）＝Ｓｃ（ｉ）　Ｕ｝　

６）　（ｆ）＝　（ｆ）－Ｕ｝　

７、）　ｃａｌｃｕｌａｔｅＦ￣ｉ，ｊ，　Ｆ　，｝。　｜｜诗舆禁　阗　

８）｝／／ｅｎｄ　ｗｈｉｌｅ　

９）ｌｏｏｐ：　

１０）ｉｆ（３ｊ　Ｅ　ＩＳ　（ｆ），Ｐ（ｆ）＝Ｐ（『））｛　

，／优先级相同则随机标定　

１　１）　ｃｈｏｏｓｅ　ｔｉ　ｒａｎｄｏｍｌｙ　ｏｎ　ａｖａｉｌａｂｌｅ　ｔｉｍｅ　ａｘｌｅ　

１　２）　ｓｅｎｄ　ｔ／ａｎｄ　ｒｅｃｅｉｖｅ　ｏｔｈｅｒ　ｎｏｄｅｓ’ｔｒａｎｓｍｉｔ—　

ｔｉｎｇ　ｍｏｍｅｎｔｓ　

１３）　ｆｏｒ　ｅａｃｈｊ（ｊＥ　Ｓｕ　（ｆ）＆＆Ｐ（ｆ）＝Ｐ（『））　

ｃａｌｃｕｌａｔｅ　Ｆｔ（ｉ，　，　ａｎｄ　Ｆｒ（ｉ，Ｊ，　

１４）　ｉｆ（Ｊｕｄｇｅ（）＝ｆａｌｓｅ）　

１５）　ｃｏｎｔｉｎｕｅ　ｌｏｏｐ　

１６）　ｅｌｓｅ　ｆ　’　

１７）　Ｓｔ（ｉ）＝ｌａｂｅｌｅｄ　

１８）　ｒｅｔｕｒｎｔｉ　

通信学报　第３３卷　

ｌ９）　｝　

２０）｝／／随机标定结束　

２１）ｅｌｓｅｆ／／节点自己的优先级最高，开始标定　

２２）　＝０／／从０开始寻找最早的可用时间　

２３）　ｆｏｒ　ｅａｃｈｊ∈Ｓ　（１）｛　

２４）　ｉｆＦｌ（ｉ，　，ｋ）＜ｔｉ＜Ｆｒ（ｉ，　，Ｄ）／／如果当前的　

ｔｉ位于禁止时间内，则增大ｔｉ　

２５）ｔｉ＝Ｆ　ｆ，．『，　

２６）　｝　

２７）｝　

２８）　（ｆ）＝ｌａｂｅｌｅｄ　

２９）ｒｅｔｕｒｎｔｉ　

节点使用Ｌａｂｅｌ（）函数实现标定功能，即上面的　

３）～６）步，Ｊｕｄｇｅ（）函数被Ｌａｂｅｌ（）调用，用来判断一次　

随机选择时间以后是否会产生冲突。在随机标定　

中，节点获得邻居随机选定的时刻后仍然使用定义　

６计算禁止时间。Ｊｕｄｇｅ（）￣数判断冲突的方式是，　

如果节点自己随机选定的时刻处于计算出的“禁止　

时间”之内，则认为会产生冲突，此次随机标定即　

作废，节点及其邻居重新进行随机标定。　

定义　（ｆ）为节点ｉ的已经标定的ＬＣＧ邻居集　

合，　（　）为节点　的所有未标定的ＬＣＧ邻居的集合，　

Ｓｔ（ｉ）为节点ｆ的标定状态（１ａｂｅｌｅｄ或ｕｎｌａｂｅｌｅｄ），Ｐ（ｉ）　

为节点ｆ的标定优先级。算法２和算法３分别给出　

了Ｌａｂｅｌ０￣Ｊｕｄｇｅ（）ｉ￣数的伪代码描述。　

在Ｌａｂｅｌ（）函数中引入随机标定的设计，是因为　

在某些网络中可能存在大量节点的优先级相同。虽　

然可以采用节点ＩＤ等强制优先级方式，但类似的　

优先级策略对优化最终的总传输时间没有帮助。随　

机标定可以减少算法的执行时间。比如，在极端的　

网络拓扑条件下（如线形、星形），当节点的优先　

级均相同时，顺序标定算法的时间复杂度为Ｏ（ｎ）　

而随机标定的时间复杂度为Ｏ（１ｏｇｎ）　＂　。其中，ｎ为　

网络中的节点个数。　

算法３　Ｊｕｄｇｅ（）　

１）Ｉｎｐｕｔ：ｔｉ，Ｓ　（ｉ），　ｆ）　

２１　Ｏｕｔｐｕｔ：ｔｒｕｅ　ｏｒｆａｌｓｅ　

Ｊｕｄｇｅ（）　

３）Ｂｏｏｌｅａｎ　Ｂ＝ｔｒｕｅ　

４）ｆｏｒｅａｃｈｊ∈Ｓｕ　（ｆ）｛　

５）ｉｆ（ｊ　∈　ｆ），　（　，‘『，　＜ｔｉ＜Ｆｒ（ｉ，‘『，　）　

６、　Ｂ＝ｆａｌｓｅ　

７）　｝　

８）ｒｅｔｕｒｎＢ　

２．３．３标定优先级确定　

在ＵＷＳＮ环境下，对于所有节点的连续时间　

的接入分配，等价于一个连续轴上的分布式着色　

问题，因此确定最优全局分配策略是ＮＰ—ｈａｒｄ问　

题。于是，在上一小节介绍的ＣＴ．ＴＤＭＡ算法流　

程中，使用了按照优先级顺序进行标定的算法。　

这样，优先级的确定直接影响ＣＴ—ＴＤＭＡ算法本　

身的执行效率。本节对优先级的计算方法进行详　

细说明。　

ＣＴ—ＴＤＭＡ的算法目的是提高网络流量，即所　

有节点均发送一次数据所使用的总时间越短越好。　

针对这个设计目标，提出重要性依次降低的３条启　

发式的优先级制定规则如下。　

１）在冲突状态图中拥有最大度的节点应该优　

先分配发送时刻。节点的度越大意味着它潜在的冲　

突节点越多。度最大的节点首先分配发送时间，可　

以使受其影响的大量节点的禁止时间尽可能地靠　

前，从而缩短最后算法选定的总时间。　

２）负载较重的节点优先发送。负载较重的节点　

优先发送有助于缩短每个分组端到端的平均时延，　

实现网络的公平性。　

３）网络中拥有较大链路时延的节点优先发送。　

时延较高的链路如果发送的较晚，到达目标时的时　

间就会更晚。而优先分配时延较高的链路，使得高　

时延的链路早发送，低时延的链路晚发送，有助于　

提高节点的传输并行度。　

以上述３条启发式规则为依据，可以实现定量　

计算节点的优先级指标。Ｐ（ｆ）表示节点ｉ的标定优先　

级，采用式（４）进行计算。式（４）中使用的主要变量定　

义为：　为ｉ在它自己的ＬＣＧ图中的度，　。一为节　

点缓冲区的大小，厶为节点ｆ的缓冲区队列长度。　

定义从节点ｉ到基站的传输路径上的下一跳节点ｋ　

为节点ｉ的父节点，Ｄ　为节点ｉ到其父节点ｋ的链　

路传播时延。定义Ｄ　是整个网络中的最大的链路　

传播时延，即网络中距离最长的一跳链路长度与水　

声信号的传播速度的比值，该值在网络部署时可以　

进行估计并设定在所有节点中。由于ＣＴ—ＴＤＭＡ协　

议运行的环境为静态网络，该值在协议运行过程中　

不会改变。而且，该值仅涉及到优先级的计算，对　

于所有节点的计算效果是等价的，因此该值的估计　

精度对于本文提出的ＣＴ．ＴＤＭＡ协议的运行效果没　

有直接影响。　

第２期　洪璐等：ＣＴ．ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１７１・　

Ｐ（ｉ）＝ｄｆ×工　＋厶十｛　（４）　

Ｄ节点的更长，因此Ａ节点的负载最重，优先级　

３条启发式规则的重要性在式（４）中直接体现：　

拥有最大度的节点拥有最高的标定优先级；如果节　

点的度相同则负载较重的节点优先级高；如果节点　

的负载也相同，则拥有最长链路时延的节点优先级　

高。当网络的拓扑结构，节点负载等条件不发生变　

化时，网络可以根据ＣＴ—ＴＤＭＡ计算出的调度顺序　

持续的运行。而当网络拓扑结构或者节点负载等条　

件发生变化时，即节点的标定优先级发生变化时，　

协议将在整个网络重新运行，以保持节点的发送时　

间分配始终为当前的最优策略。　

２．４算法实例　

为了清晰地说明ＣＴ—ＴＤＭＡ的基本思想、工作　

流程及特点，本节给出一个简单的网络实例进行说　

明，如图５（ａ）所示。链路上的标记为该条链路的时　

延（单位为Ｓ），设帧时　为１ｓ。　

各节点首先运行ｃｒｅａｔｅＬＣＧ０函数生成自己　

的局部冲突状态图，４个节点的ＬＣＧ如图５（ｂ）　

所示。　

Ｄ　

（ａ）网络拓扑　

ＬｃＧ　）

副　Ｃ

ＬＣＧ　）ＬＣＧ（Ｃ）　

（ｂ）各节点局部冲突状态　

Ａ　

Ｉ　Ｉ　Ｉ　　ＩＩ　Ｉ　Ｉ　

Ｂ　

Ｉ　Ｉ　Ｉ　　ＩＩ　Ｉ　ｌ　

Ｄ　亨－｛—＿＿｝—寸—十—　

ｃ　＝　—｝＿’｝　

（ｃ）标定顺序和结果　

图５　ＣＴ—ＴＤＭＡ的执行过程　

（实线表示逻辑链路，虚线表示点到点之间的时延）　

然后，所有节点计算自己的优先级。在图５（ｂ）　

中４个节点的度相同，在所有节点产生数据分组　

的频率相同的情况下，对于Ａ节点来说，它不仅　

要发送自己的数据分组，还要转发来自曰和Ｄ　

的分组，Ａ节点的缓冲区队列长度必将比　、Ｃ、　

最高。曰、Ｃ、Ｄ负载相同，因此按链路的时延排　

序，相关链路时延高者优先级高，最终标定顺序　

为Ａ、　、　、Ｃ。　

因此，Ａ首先选择０时刻并广播给　、Ｃ、Ｄ。　

日根据公式计算出Ａ对Ｂ的禁止时间为（一３．９，一１．９）　

ｕ（一４．５，一２．５），所以　也可选择０时刻。Ｄ根据Ａ　

和Ｂ的标定结果，计算Ａ和　对自己的禁止时间为　

（一５，一３）ｕ（一１．５，０．５），于是Ｄ选择自己的发送时刻　

为０．５。最后，ｃ计算Ａ、Ｂ、Ｄ对自己带来的禁止　

时间为（一２．７，一０．７）Ｕ（０．２，２．２）Ｕ（一０．８，１．２），Ｃ选择　

自己的发送时刻为２．２ｓ。４个节点的正数禁止时间　

在图５（ｃ）中给出。禁止时间的负数部分不影响节点　

发送时刻的选择，故未给出。最后，　、Ｂ、Ｃ和Ｄ　

４个节点分别确定自己的发送时刻为０ｓ、０ｓ、２．２ｓ　

和０．５ｓ。　

本例说明，ＣＴ—ＴＤＭＡ提高了数据发送的并行　

度。例如，．Ａ和口节点都在０时刻发送而不会冲突，　

这在传统的ＷＳＮ中是无法实现的。ＵＷＳＮ正是由　

于传播时延高、通信距离长和数据分组短，导致了　

不同发送节点的数据分组到达接收端的时刻存在　

差异。ＣＴ．ＴＤＭＡ利用ＵＷＳＮ的这种特性，避免了　

冲突，提高了网络中数据传输的并行度，达到提高　

网络流量的目的。　

３仿真　

本节介绍ＣＴ—ＴＤＭＡ的仿真结果，并对算法的　

性能进行分析和对比。使用了ＭＡＴＬＡＢ等软件对　

算法进行了仿真，在仿真过程中，帧时　设定为ｌｓ，　

节点的通信半径为３　０００ｍ，干扰半径为３　５００ｍ，网　

络包括从５个节点到６０个节点的４种规模。根据　

网络规模的变化，节点被部署在最大１２ｋｍｘ１２ｋｍ　

的范围内，通过随机部署的方式，利用部署密度限　

制节点和邻居节点之间的距离在４５０ｍ到３　０００ｍ之　

间。因为水声信号的速度为１　５００ｍ／ｓ，所以网络中　

链路的时延被控制在０．３ｓ～２ｓ之间。　

由于网络拓扑结构对节点的传输并行度有重　

要影响，因此对比了一般的网络拓扑结构（节点随　

机投放并自组织成树形拓扑结构），以及特殊的星　

形、线形和网格，共４种拓扑结构对算法的影响。　

在４种拓扑结构下，均采用４种网络规模完成了ｌ６　

组实验。在仿真中使用平均每秒钟整个网络发送的　

有效信息量作为评价网络流量的指标，即节点发送　

通信学报　第３３卷　

的数据信息字节数。ＳＴ—ＭＡＣ帧长度为４５ｂｙｔｅｔ　】　

（４０ｂｙｔｅ有效数据），ＣＴ—ＴＤＭＡ的帧长度为１０５ｂｙｔｅ　

（１００ｂｙｔｅ有效数据）。在仿真中模拟了４种不同的接　

入分配算法。　

１）Ｏｐｔｉｍａｌ：实验网络部署情况下的理论上最　

优的分配策略，该策略能够最大限度地利用信道和　

提高节点的传输并行度，为其他算法提供理论的最　

佳上界。最优策略的求解，即针对实验环境下的网　

络拓扑，在所有可能的节点接入方案中，选取全部　

节点的一轮接入时间最短的接入方案。　

２）ＣＴ—ＴＤＭＡ：本文提出的分配策略。　

３）ＳＴ—ＭＡＣ：文献【１３】提出的跨时隙ＴＤＭＡ分　

配策略。　

４）Ｓ—ＴＤＭＡ：传统的ＵＷＳＮ单时隙ＴＤＭＡ。　

图６中对比了４种调度算法在４种不同网络拓扑　

结构下的流量情况。可以看出，网络拓扑结构对流量　

有明显的影响，线形、树形、网格到星形网络流量依　

次降低，这是由于随着拓扑的变化节点的密度逐渐增　

一　ｓ＿　奎）／嘲蟾燎匿　

加，即共享同一个信道的节点数目越来越多，因此能　

够同时并行传输的节点数目就变得越来越少。除星形　

拓扑之外，在其他拓扑结构和协议下，网络流量均随　

着网络规模的增加而增加。星形拓扑结构表现特殊的　

原因是，在该环境中所有节点均一跳传向基站，因此　

任意２个节点均互为冲突邻居，所有的节点共享同一　

个信道，无法提高数据传输的并行度。　

图６显示，当网络规模较小时，ＣＴ—ＴＤＭＡ　

和ＳＴ—ＭＡＣ均能够达到或接近理论最优的效果。　

当网络规模逐渐增大时，ＣＴ—ＴＤＭＡ和ＳＴ—ＭＡＣ　

的流量均不能达到理论最优值，但ＣＴ—ＴＤＭＡ的　

性能始终优于ＳＴ—ＭＡＣ（平均高２０％以上），并　

达到理论最优值的８０％左右。而Ｓ—ＴＤＭＡ的表　

现最差，因为该方案较长的时隙给接收端带来大　

量空闲时间。　

ＣＴ—ＴＤＭＡ优于ＳＴ—ＭＡＣ的原因在于，　

ＳＴ—ＭＡＣ采用时隙调度策略为节点分配发送时间，　

这种策略规定节点只能在每个时隙的开始时刻发　

送帧。此外，ＳＴ—ＭＡＣ要求所有链路时延是帧时的　

整数倍。为了确保这一点，ＳＴ．ＭＡＣ协议中的分组　

长度必须尽可能小，进一步引起帧中有效数据比例　

下降。其原因是，虽然帧长度缩短，帧中的校验和　

确认位并不减少。ＣＴ—ＴＤＭＡ采用连续时间分配策　

略，并不需要ＳＴ—ＭＡＣ的上述设定，因此可以应用　

更长的数据帧，从而提高了网络流量。　

网络规模（星形拓扑）　

（ａ】星形拓扑下的流量　

网络规模（线形拓扑）　

（ｂ）线形网络拓扑下的流量　

网络规模（网格拓扑）　

（ｃ）网格拓扑下的流量　

网络规模（树形拓扑）　

（ｄ】树形拓扑结构下的流量　

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

第２期　洪璐等：ＣＴ－ＴＤＭＡ：水下传感器网络高效ＴＤＭＡ协议　・１７３・　

图７记录了４种协议在一般网络情况即树形拓　

扑结构下的端到端时延情况。传感器网络的数据传　

输模式为所有的节点向基站传输数据，因此端到端　

时延即为数据分组从源节点到基站的传播时延。从　

图７可以看出，随着网络规模的增大，节点到基站　

的平均跳数增加，端到端时延也相应增加。由于　

ＣＴ—ＴＤＭＡ使用了连续时间分配策略，在接收节点　

处缩短了帧与帧之间的空闲时间，提高了传输效　

率，其平均端到端时延比ＳＴ—ＭＡＣ降低了约１８％，　

并且只比理论最优策略的时延高１２％。可见，　

ＣＴ—ＴＤＭＡ不仅网络流量要高于传统协议，平均的　

端到端时延也更低，实时性更好。　

翟　

释　

鬲　

孵　

霍　

露　

１碧－　

网络规模　

图７　４种协议的平均端到端时延　

从计算代价的角度分析，ＳＴ—ＭＡＣ为集中式算　

法，需要从所有的全局调度方案中寻找最优方案，　

而ＣＴ—ＴＤＭＡ采用分布式的调度策略，每个节点的　

计算代价都比ＳＴ—ＭＡｃ小很多，因此计算时问更　

短。从能量消耗的角度分析，ＳＴ—ＭＡＣ和ＣＴ—ＴＤＭＡ　

均属于ＴＤＭＡ协议，数据传输阶段没有冲突，因　

此能量效率都很高。额外的能量消耗仅在于协议的　

初始化阶段，ＳＴ—ＭＡＣ需要基站收集全网络的信息　

和分发调度策略，ＣＴ—ＴＤＭＡ仅需要各个节点与其　

Ｃｏｖ（ＲＩ＋ＲＴ）范围内的邻居进行信息交换。当网络规　

模急剧增大时，ＳＴ－ＭＡＣ洪泛和广播的通信开销要　

远大于ＣＴ—ＴＤＭＡ的分布式信息交互。　

４相关工作　

近年来，ＵＷＳＮ的ＭＡＣ问题由于水声通信的　

独特特点引起广泛关注。相关研究成果可分为基于　

竞争的接入控制协议和无冲突的接入协议２类。　

接入竞争控制协议，通过以接收端为中心的虚　

拟载波监听协议来解决ＭＡＣ问题。文献【９】使用　

ＲＴＳ／ＣＴＳ握手机制来建立信道预约。节点通过截获　

邻居信息的方式计算各个邻居节点的忙时间，然后　

在这段时间内停止侦听信道。文献【６】研究了水声信　

道特征对Ａｌｏｈａ协议的影响，进而提出水声通信的　

冲突状态具有时空不确定性的特点。文献［８】和文献　

［１０］基于Ａｌｏｈａ协议，使用一个短帧来预约信道，　

避免数据分组的冲突。Ｔ—Ｌｏｈｉ协议　针对水声信道　

冲突的时空不确定性设计了一个特殊的退避算法，　

在高负载的环境中具有较高的流量。　

无冲突的接入协议基于ＴＤＭＡ和ＣＤＭＡ。针　

对ＵＷＳＮ设计的ＴＤＭＡ协议分为单时隙和跨时隙　

２种，单时隙协议要求一跳范围内的数据传输必须　

在一个时隙完成。ＵＷＡＮ—ＭＡＣ［１１１允许节点随机地　

选择时隙进行传输。文献【１２１提出的混合协议将　

ＴＤＭＡ和竞争协议相结合，充分利用了竞争协议时　

延较低而ＴＤＭＡ流量较高的优点。　

跨时隙的协议允许使用多个时隙完成数据分　

组传输。最近提出的ＳＴ—ＭＡＣ【ｌｊ＿ｊ是第一个跨时隙的　

ＴＤＭＡ协议，该协议以整个网络的冲突状态图为基　

础，采用集中式算法计算各个节点的最优发送时　

隙。ＳＴ—ＭＡＣ需要收集全局信息并且假设网络中的　

任意链路时延都是发送帧时的整数倍，通过分配时　

隙的方式，使得不同节点的帧到达目的端的时隙不　

相同（即不会产生冲突）。该协议的时隙长度比传　

统协议要短的多，利用链路时延的差异性减少了接　

收帧之间的空闲时间，与传统的单时隙的ＴＤＭＡ　

相比提高了网络流量。本文提出的ＣＴ．ＴＤＭＡ和　

ＳＴ—ＭＡＣ相比，不依赖于时延与帧时关系的假设，　

并且采用连续时间的分配方式代替时隙分配，减少　

了信道空闲时间，提高了网络流量。　

除了ＴＤＭＡ之外，研究者还提出了针对水下　

环境的改进ＣＤＭＡ协议Ｉｌ。’　１，文献【ｌ９】提出的混合　

协议使用对节点分簇的策略，簇内节点通信使用　

ＴＤＭＡ协议，不同的簇之问的节点通信则使用　

ＣＤＭＡ协议。然而目前在ＵＷＳＮ中使用ＣＤＭＡ协　

议还面临很多困难，对大规模的传感器节点分配伪　

随机码是一项艰巨的挑战，此外，水声通信中使用　

ＣＤＭＡ的远近效应问题也没有得到很好地解、决Ｉ埽Ｊ。　

５结束语　

针对水下无线传感器网络时延高、带宽低和误　

码率高的特性，本文提出了以发送端为中心以连续　

时间为计量单位的冲突状态模型——局部冲突状态　

・１７４・　通信学报　第３３卷　

图（ＬＣＧ）及其分布式构建算法，并在此基础上设　

计了基于启发式规则的水下传感器网络ＴＤＭＡ协　

ＩＥＥＥ　ＩＮＦＯＣＯＭ［Ｃ］．Ａｎｃｈｏｒａｇｅ，Ａｌｓｋａ，ＵＳＡ，２００７．ａ２２７１—２２７５．　

【１　１］ＰＡＲＫ　Ｍ，ＲＯＤＯＰＬＵ　Ｖ．ＵＷＡＮ—ＭＡＣ：ａｎ　ｅｎｅｒｇｙ－ｅｆｉｃｉｆｅｎｔ　ＭＡＣ　

ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｗｉｍｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ　

Ｊｏｕｒｎａｌ　ｏｆＯｃｅａｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００７，３２（３）：７１０—７２０．　

［１２］ＫＵＲＴＩＳ　Ｉ，ＫＲＥＤＯ　Ｂ，ＭＯＨＡＰＡＴＲＡ　Ｐ．Ａ　ｈｙｂｒｉｄ　ｍｅｄｉｕｍ　ａｃｃｅｓｓ　

议。ＣＴ．ＴＤＭＡ利用ＵＷＳＮ中同一接收节点与不同　

发送节点之间链路时延的差异性，与现有协议相比　

进一步减少了节点接收帧序列的空闲时间，提高了　

网络流量。并且，基于启发式规则的分配算法，有　

效缩短了节点在连续时间轴上进行时刻分配的运　

行时间。仿真表明，与ＳＴ—ＭＡＣ和Ｓ—ＴＤＭＡ等基　

ｃｏｎｔｒｏｌ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＡＣＭ　

ＷＵＷＮＥＴ［Ｃ］．Ｍｏｎｔｒｄａｌ，Ｑｕｄｂｅｃ，Ｃａｎａｄａ，２００７．３３—４Ｏ．　

【１３】ＨＳＵ　Ｃ　Ｃ，ＬＡＩ　Ｋ　Ｆ，ＣＨＯＵ　Ｃ　Ｆ．ＳＴ—ＭＡＣ：ｓｐａｔｉｌ—ａｔｅｍｐｏｒａｌ　ＭＡＣ　

ｓｃｈｅｄｕｌｉｎｇ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＩＥＥＥ　ＩＮＦＯ—　

于时隙分配的水下传感器网络ＴＤＭＡ协议相比，　

ＣＴ．ＴＤＭＡ能够实现更高的网络流量和更低的端到　

端传播时延。　

参考文献：　

［１】李建中，高宏．无线传感网络的研究进展［Ｊ】．计算机研究与发展，　

２００８，４５（１）：１－１５．　

ＬＩ　Ｊ　ｚ．ＧＡＯ　Ｈ．Ｒｅｓｅａｒｃｈ　ｐｒｏｇｒｅｓｓ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．　

Ｊｏｕｒｎａｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００８，４５（１）：１－１５．　

［２１李瑞芳，李仁发，罗娟．无线多媒体传感器网络ＭＡＣ协议研究综　

述［Ｊ］．通信学报，２００８，２９（８）：１１１－１２３．　

ＬＩ　Ｒ　Ｆ，ＬＩ　Ｒ　Ｆ，ＬＵＯ　Ｊ．Ｒｅｓｅａｒｃｈ　ｒｅｖｉｅｗ　ｏｎ　ＭＡＣ　ｐｒｏｔｏｃｏｌｓ　ｏｆ　ｗｉｒｅ—　

ｌｅｓｓ　ｍｕｌｔｉｍｅｄｉａ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００８．　

２９（８）：１１１－１２３．　

［３］ＨＥＩＤＥＭＡＮＮ　Ｊ，ＬＩ　Ｙ，ＳＹＥＤ　Ａ．Ｒｅｓｅａｒｃｈ　ｃｈａｌｌｅｎｇｅｓ　ａｎｄ　ａｐｐｌｉｃａ－　

ｉｔｏｎｓ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｉｎｇ【Ａ】．Ｐｒｏｃ　ＷＣＮＣｆＣ】．Ｌａｓ　

Ｖｅｇａｓ，ＮＶ，ＵＳＡ，２００６．２２８－２３５．　

［４］ＳＹＥＤ　Ａ，ＨＥＩＤＥＭＡＮＮ　Ｊ．Ｔｉｍｅ　ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｆｏｒ　ｈｉｇｈ　ｌａｔｅｎｃｙ　

ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＩＮＦＯＣＯＭ　２００６［Ｃ］．Ｂａｒｃｅｌｏｎａ，Ｃａｔａｌｕｎｙａ，　

Ｓｐａｉｎ，２００６．１－１２．　

［５】ＨＡＲＲＩＳ　Ａ　Ｆ　ＩＩＩ，ＳＴＯＪＡＮＯＶＩＣ　Ｍ，ＺＯＲＺＩ　Ｍ．Ｗｈｅｎ　ｕｎｄｅｒｗａｔｅｒ　

ａｃｏｕｓｔｉｃ　ｎｏｄｅｓ　ｓｈｏｕｌｄ　ｓｌｅｅｐ　ｗｉｔｈ　ｏｎｅ　ｅｙｅ　ｏｐｅｎ：Ｉｄｌｅ・ｔｉｍｅ　ｐｏｗｅｒ　ｍａｎ—　

ａｇｅｍｅｎｔ　ｉｎ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ【Ａ】．Ｐｒｏｃ　ＡＣＭ　ＷＵＷＮＥＴ［Ｃ］．　

Ｌｏｓ　Ａｎｇｅｌｅｓ，ＣＡ，ＵＳＡ，２００６．１０５—１０８．　

【６］ＳＹＥＤ　Ａ，ＹＥ　Ｗ，ＨＥＩＤＥＭＡＮＮ　Ｊ．Ｕｎｄｅｒｓｔａｎｄｉｎｇ　ｓｐａｔｉａｌ－ｔｅｍｐｏｒｌａ　

ｕｎｃｅｒｔｉａｎｔｙ　ｉｎ　ｍｅｄｉｕｍ　ａｃｃｅｓｓ　ｗｉｔｈ　ＡＬＯＨＡ　ｐｒｏｔｏｃｏｌｓ［Ａ］．Ｐｒｏｃ　ＡＣＭ　

ＷＵＷＮＥＴ［Ｃ］．Ｍｏｎｔｒｄａｌ，Ｑｕｄｂｅｃ，Ｃａｎａｄａ，２００７．４１—４８．　

［７］　ＳＹＥＤ　Ａ，ＹＥ　Ｗ，ＨＥＩＤＥＭＡＮＮ　Ｊ．Ｔ－ｌｏｈｉ：ａ　ｎｅｗ　ｃｌｓａｓ　ｏｆ　ＭＡＣ　ｐｒｏ．　

ｔｏｃｏｌｓ　ｆｏｒ　ｕｎｄｅ－ｗｒａｔｅｒ　ａｃｏｕｓｔｉｃ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．ＩＥＥＥ　ＩＮＦＯ．　

ＣＯＭ［Ｃ］．Ｐｈｏｅｎｉｘ，ＡＺ，ＵＳＡ，２００８．２３１—２３５．　

［８】ＧＵＯ　Ｘ，ＦＲＡＴＥＲ　Ｍ，ＲＹＡＮ　Ｍ．Ａ　ｐｒｏｐａｇａｔｉｏｎ—ｄｅｌａｙ－ｔｏｌｅｒａｎｔ　ｃｏｌｌｉ—　

ｓｉｏｎ　ａｖｏｉｄａｎｃｅ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．　

ＯＣＥＡＮＳ　２００６一Ａｓｉａ　Ｐａｃｉｉｆｃ［Ｃ］．Ｓｉｎｇａｐｏｒｅ，２００６．１—６．　

［９】ＭＯＬＩＮＳ　Ｍ，ＳＴＯＪＡＮＯＶＩＣ　Ｍ．Ｓｌｏｔｔｅｄ　ＦＡＭＡ：ａ　ＭＡＣ　ｐｒｏｔｏｃｏｌ　ｏｆｒ　

ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．ＯＣＥＡＮＳ　２００６－Ａｓｉａ　Ｐａｃｉｆｉｃ［Ｃ］．　

Ｓｉｎｇａｐｏｒｅ，２００６．１・７．　

［１Ｏ】ＣＨＩＲＤＣＨＯＯ　Ｎ，ＳＯＨ　Ｗ，ＣＨＵＡ　Ｋ．Ａｌｏｈａ－ｂａｓｅｄ　ＭＡＣ　ｐｒｏｔｏｃｏｌｓ　

ｗｉｔｈ　ｃｏｌｌｉｓｉｏｎ　ａｖｏｉｄａｎｃｅ　ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　

ＣＯＭ［Ｃ］．Ｒｉｏ　ｄｅ　Ｊａｎｅｉｒｏ，Ｂｒａｚｉｌ，２００９．１８２７　１８３５．　

［１４】ＨＯＮＧ　Ｌ，ＨＯＮＧ　Ｆ，ＧＵＯ　Ｚ　Ｗ．Ａ　ＴＤＭＡ．ｂａｓ酣ＭＡＣ　ｐｒｏｔｏｃｏｌ　ｉｎ　

ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｔｈｅ　４ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

Ｗｉｒｅｌｅｓｓ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎｅｔｗｏｒｋｉｎｇ，ａｎｄ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　

（ＷＩＣＯＭ’Ｏ８）【Ｃ］．Ｄａｌｉｎａ，Ｃｈｉｎａ，２００８．１—４．　

［１５］ＤＯＷＮＥＹ　Ｐ．Ｔｈｅ　Ｂｅｈａｖｉｏｒ　ｏｆ　ａ　Ｆｌｏｏｄｉｎｇ　Ｐｒｏｔｏｃｏｌ　ｉｎ　ａ　Ｗｉｒｅｌｅｓｓ　

Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋ［Ｒ］．Ｒｅｐｏｒｔ　ｆｏｒ　ｔｈｅ　Ｈｏｎｏｕｒｓ　Ｐｒｏｇｒａｍｍｅ　ｏｆ　ｈｔｅ　Ｓｃｈｏｏｌ　

ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，ｔｈｅ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　

Ｗｅｓｔｅｒｎ　Ａｕｓｔｒｌａｉａ，２００３．　

［１６］ＬＩＵ　ＹＨ，ＬＩＯＮＥＬ　Ｍ．Ｎｉ：ａ　ｇｅｎｅｒａｌｉｚｅｄ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｔｏｐｏｌｏｇｙ　ｃｏｎｔｒｏｌ　

ｏｆｒ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．１ＮＦＯＣＯＭ　２００９［Ｃ］．Ｒｉｏ　ｄｅ　Ｊａｎｅｉｒｏ，　

Ｂｒａｚｉｌ，２００９．２７７６—２７８０．　

［１７］ＬＵＢＹ　Ｍ．Ａ　ｓｉｍｐｌｅ　ｐａｒａｌｌｅｌ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｍａｘｉｍａｌ　ｉｎｄｅｐｅｎｄｅｎｔ　

ｓｅｔ　ｐｒｏｂｌｅｍ［Ｊ］．ＳＩＡＭ　Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｐｕｔｉｎｇ，１９８６，１５（４）：１０３６—１０５３．　

［１８］ＴＡＮ　Ｈ　Ｘ，ＳＥＡＨ　Ｗ　Ｋ　Ｇ．Ｄｉｓｔｒｉｂｕｔｅｄ　ＣＤＭＡ—ｂａｓｅｄ　ＭＡＣ　ｐｒｏｔｏｃｏｌ　

ｆｏｒ　ｕｎｄｅｒｗａｔｅｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ａ］．ＬＣＮ［Ｃ］．Ｃｌｏｎｔａｒｆ　Ｃａｓｔｌｅ，Ｄｕｂｌｉｎ，　

Ｉｒｅｌａｎｄ．２００７．２６—３６．　

［１９】ＳＡＬＶＡ—ＧＡＲＡＵ　Ｆ，ＳＴＯＪＡＮＯＶＩＣ　Ｍ．Ｍｕｌｔｉ．ｃｌｕｓｔｅｒ　ｐｒｏｔｏｃｏｌ　ｏｆｒ　ａｄ　

ｈｏｃ　ｍｏｂｉｌｅ　ｕｎｄｅｒｗａｔｅｒ　ａｃｏｕｓｔｉｃ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ　ＩＥＥＥ　Ｏｃｅａｎｓ　

Ｃｏｎｆ［Ｃ］．Ｓａｎ　Ｄｉｅｇｏ，ＣＡ，ＵＳＡ，２００３．９１—９８．　

作者简介：　

洪璐（１９８４一），　男，山东济宁人，中　

国海洋大学博士生，　主要研究方向为传感　

器网络和容迟网络。　

洪锋（１９７７一），男，山东青岛人，中国海洋大学副教　

授，主要研究方向为传感器网络、对等计算和网格计算。　

李正宝（１９８１．），男，山东济宁人，中国海洋大学博　

士生，主要研究方向为传感器网络和容迟网络。　

郭忠文（１９６５一），男，山东青岛人，中国海洋大学教　

授、博士生导师，主要研究方向为传感器网络和海洋信息分　

布式处理技术。