一种选择性重传、握手和时隙的水下介质访问控制协议

摘要

本发明公开了基于握手、时隙及选择性重传的一种高效、低数据包冲突概率的水下介质访问控制协议，有效解决了当前水下通信长延时及高错误概率的现状。本协议具有三个特点：（1）通过握手来避免冲突：可以有效解决暴露/隐藏终端（exposed/hidden terminal）问题，且本协议一次握手可以发送多个数据包，在长传输延迟的网络环境（如水下无线网络）下具有更高效率；（2）采用时隙机制来减小冲突窗口：在无线网络中，冲突窗口大小和数据包冲突概率具有正相关的关系，因此，本协议时隙机制可将冲突窗口减半，从而大大降低数据包冲突概率；（3）采用选择性重传：降低了成功发送一个数据包所需要的平均时间；在给定的网络丢包率条件下，可降低网络能耗、提高网络效率。

说明书

技术领域

本发明涉及一种高效水下介质访问控制协议，尤其涉及一种选择性重传、握手和时隙的水下介质访问控制协议，属于水下通信、水声通信、多跳协同网络以及信息传输等技术领域。

背景技术

在网络协议中，介质访问控制协议负责在一个共享的信道中提供点对点的数据通讯。对于无线通讯而言，相邻网络节点共享一个信道，当它们同时发送数据时，会对彼此造成干扰，引起数据包接收的失败，也称数据包冲突。为了解决这一问题，介质访问控制协议应运而生。它是数据链路层的一个子层，主要用来改善数据链路层的数据包冲突问题，并与此同时尽量提高信道利用率和网络吞吐率。

文献“J. –H. Cui, J. Kong, M. Gerla, and S. Zhou, “Challenges: building scalable mobile underwater wireless sensor networks for aquatic applications,” IEEE Network, Special Issue on Wireless Sensor Networking, vol. 20, no. 3, pp. 12-18, May 2006. ”和文献“M. Chitre, S. Shahabudeen, and M. Stojanovic, “Underwater acoustic communication and networks: Recent advanced ans future challenges,” Marine Technology Society Journal, no. 1, pp.103-116, 2006. ”详细阐述了水下通信网络的显著进展。虽然有大量的网络设计，但是网络协议的实现和实际测试还几乎没有，尤其是海洋实测研究。水声网络通信协议最具挑战的特点就是长的传输延时，高错误概率及动态拓扑。除此之外，协议实现，测试及评估也遇到更大困难。协议需要通过在控制水声调制器的微控制器上实现。为了测试多个水声网络节点，需要部署单节点重达几百磅的多个节点，通常，铺设8个节点就需要花一天时间。因此，大部分的网络协议都没有经过实际网络测试。

水声通信网络的接入协议，主要有随机接入和协作机制两类。文献“N. Chirdchoo, W. -S. Soh, and K. C. Chua, “Aloha-based MAC protocols with collision avoidance for underwater acoustic networks,” in Proceedings of IEEE INFOCOM, 2007. ”为基于Aloha的协议采用随机信道接入机制。随机接入协议会引入最小负载的控制包；因此，通常会产生更多碰撞。为了避免碰撞，需要在传输前进行对话。

文献“M. Molins and M. Stojanovic, “Slotted fama: a mac protocol for underwater acoustic networks,” in Proceedings of MTS/IEEE OCEANS, 2006. ”采用基于RTS/CTS的握手及时隙设计来避免冲突。文献“X. Guo, M. R. Frater, and M.J. Ryan,”Design of a propagation-delay-tolerant MAC protocol for underwater acoustic sensor networks,” in IEEE Journal of Oceanic Engineering, 2009.”提出了一种改进的握手机制。通过精确设计延迟传输CTS及数据包，可以使用传播延迟间隙，文中提出的APCAP协议能够提高总数据传输的效率。

除了握手机制以外，文献“A. A. Syed, W. Ye, and J. Heidemann,”T-Lohi: A new class of MAC protocols for underwater acoustic sensor networks,” in Proceedings of IEEE INFOCOM, 2008.”采用随机退避机制，显著降低网络拥塞及碰撞概率。通过分析，上述方法已被证明有效，因此，成为目前MAC协议中应用最为广泛的。

文献“C. Petrioli, R. Petroccia, and J. Potter, “Performance evaluation of underwater MAC protocols: From simulation to at-sea testing,” in Proceedings of MTS/IEEE OCEANS, May 2012.”阐述了水下实测与仿真的差距，主要体现在仿真对于水下环境的动态估计能力有限，导致实测与仿真结果存在很大差距。

综上所述，我们知道了水下无线网络通信具有自身特殊性，导致传统的介质访问控制协议无法高效工作，存在若干技术局限。

首先，针对地面有线网络设计的介质访问控制协议一般采用载波侦听技术来监测冲突。由于无线网络通讯硬件大多工作在单工状态，没法同时进行数据发送和载波侦听。因此，以带冲突检测的载波监听多路访问技术（CSMA/CD）为代表的协议没法有效工作。

其次，针对地面无线网络设计的介质访问控制协议没有考虑水下无线网络特有的长信号传播时延。这导致以载波监听多路访问/冲突避免（CSMA/CA）为代表的协议在水下环境下难以取得满意的性能。

本申请文件致力于提出一种用于水声网络通信的高效协作传输协议。所提协议已经经过部署于实际海洋环境网络节点的测试，具有非常重要的实践指导价值。

发明内容

本发明的目的在于通过设计握手、时隙及选择性重传策略，提出一种冲突避免的水下介质访问控制技术，降低水下无线网络通信的数据包冲突概率和提升网络传输效率。

本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”是通过以下技术方案实现的。

假设节点i和节点i+1分别是数据源节点和目的节点；节点i-1和节点i+2分别是源节点和目的节点的一跳邻居节点，它们可以分别侦听到源节点i和目的节点i+1的数据传输；且假设时间轴被划分为等长的时隙：时隙长度是一个可以被用户指定的参数，其取值和物理层设备的工作特性相关，建议值为网络中点对点传输的最长信号传输延时加上物理层的传播时延。

本申请中有RTS、CTS、HDR、NACK及ACK五种控制包：其中，RTS控制包和CTS控制包用于握手；HDR控制包是新型控制包，在传输控制包或重新传输数据包之前，从源节点发送到目的节点，其承载着数据包数目信息，同时用于选择重传及碰撞避免：一方面，通知目的节点欲传输的数据包数量，使得接收节点可以构建NACK或ACK控制包；另一方面，相邻节点也可以根据侦听到的数据包数量信息，选择相应的退避时间。上述所有五种建立连接用的控制包，其发送都必须在一个时隙的开始时。

具体实施步骤如下：

步骤一、当源节点i欲向目的节点i+1传输数据时，在下一时隙的开始时刻，源节点i首先发出一个“请求发送”（RTS）控制包；

其中，所述的RTS控制包中的信息包括目的节点i+1的编号（ID）、要发送的数据包个数以及数据长度。

步骤二、若节点i-1侦听到RTS控制包后，将进行退避(Backoff)，以免造成节点i处数据包冲突；与此同时，当目的节点i+1收到RTS控制包后，它在下一时隙的开始时刻，用“允许发送”（CTS）控制包进行应答；

其中，所述的CTS控制包中的信息包括源节点i的ID、要接收的数据包个数以及数据长度。

步骤三、与步骤二类似，若节点i+1听到CTS控制包信息之后，同样会进行退避(Backoff)，以避免造成冲突；CTS控制包被源节点i收到以后，在下一时隙的开始时刻，源节点i发送一个清单包（HDR）控制包；

其中，所述的清单控制包包含了要传输的数据包个数和每个数据包的ID。

步骤四、源节点i连续、顺序发送步骤三节点i发送的HDR控制包所指示的数据包到目的节点i+1；

其中，步骤四中的连续、顺序发送的数据包可占据多个时隙。

步骤五、当目的节点i+1接收完毕之后，比较HDR控制包中源节点打算发送的数据包编号以及实际收到的数据包编号。根据比较结果，选择下述A或B步骤执行：

A）若一致，则表明所有数据包传输成功，目的节点i+1向源节点i发送一个应答（ACK）控制包，转至步骤八。

B）若不一致，则表明有数据包丢失，目的节点i+1向源节点i发送一个否定应答（NACK）控制包，转到步骤六。

其中，所述的NACK控制包中列出没有传输成功的数据包编号。

步骤六、若收到NACK控制包，源节点i在确定哪些数据包丢失后，在下一个时隙开始时刻，发送一个HDR控制包到目的节点i+1；

其中，所述的HDR控制包含重新传输的数据包个数及其编号。

步骤七、源节点i重新发送步骤六中源节点i发送的HDR控制包指示的数据包到目的节点i+1，转至步骤五；

步骤八、至此，源节点i向目的节点i+1传输信息完毕。转至步骤一，开始下一轮的信息传输。

本发明的关键技术点有如下四条：

（1）通过握手来避免冲突，解决暴露/隐藏终端（exposed/hidden terminal）问题；

（2）一次握手可以发送多个数据包，以适应长传输延时的网络环境；

（3）用时隙来减小冲突窗口，减低数据包冲突概率；

（4）采用选择性重传，在给定丢包率下，在统计上降低成功发送一个数据包所需要的平均时间，大大提高了网络效率。

有益效果

本发明是一种基于握手、时隙及选择性重传的水下介质访问控制协议，具有如下有益效果：

1. 本协议通过握手来避免冲突，可以有效解决隐藏/暴露终端（exposed/hidden terminal）问题。

2. 本协议一次握手可以发送多个数据包，在长传输延时的网络环境（如水下无线网络）下具有更高效率。

3. 本协议采用了时隙来减小冲突窗口。在无线网络中，冲突窗口大小和数据包冲突概率具有正相关的关系。理论上来说，采用时隙可以将冲突窗口减半，可以大大降低数据包冲突概率。

4. 采用选择性重传可以降低网络能耗，提高网络效率，在给网络定丢包率下，在统计上降低成功发送一个数据包所需要的平均时间。

附图说明

图1是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”和实施例1中系统工作的流程示意图。

图2是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例2中四节点网络的平均传输延时示意图。

图3是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例2中七节点网络的平均传输延时示意图。

图4是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例2中八节点网络的平均传输延时示意图。

图5是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例2中四节点网络的单跳队列时延与单跳数据包的包传递时间的关系示意图；

其中，图中的“队列时延”对应单跳队列时延；而“总传输时延”对应着单跳数据包的包传递时间。

图6是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例2中七节点网络的单跳队列时延与单跳数据包的包传递时间的关系示意图；

其中，图6中的图示说明与图5相同。

图7是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例2中八节点网络的单跳队列时延与单跳数据包的包传递时间的关系示意图；

其中，图7中的图示说明与图5相同。

图8是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例3中端到端传输延时的示意图。

图9是本发明“一种选择性重传、握手和时隙的水下介质访问控制协议”实施例3中端到端吞吐量的示意图。

具体实施方式

下面结合附图1、图2和图3以及实施例对本发明做进一步说明和详细描述。

在本发明指出的协议中，我们把时间轴划分为等长的时隙。时隙的长度是一个可以用户指定的参数，其取值和物理层设备的工作特性相关，建议值为网络中点对点传输的最长信号传输时延加上物理层的传播延时。所有建立连接用的控制包（例如RTS/CTS/HDR）的发送都必须在一个时隙的开始时。

本协议的工作流程如图1所示。假设节点i和节点i+1分别是数据源节点和目的节点。图1中节点i-1和节点i+1分别代表源节点i和目的节点i+1的一跳邻居节点，这些一跳邻居节点可以为一个或多个，本申请为简单起见，只列出一个；它们可以分别侦听到源节点i和目的节点i+1发送的控制包和数据包传输。

当源节点i打算向目的节点i+1传输数据时，在下一时隙的开始时刻，它首先发出一个“请求发送”（RTS）控制包。RTS控制包中的信息包括目的节点i+1的编号（ID），要发送的数据包个数，以及数据长度。节点i-1侦听到RTS控制包。之后，将进行退避(Backoff)，以避免造成冲突。

当目的节点i+1收到RTS控制包后，它在下一时隙的开始时刻，用“允许发送”（CTS）控制包进行应答。CTS控制包中的信息包括源节点ID，要接收的数据包个数，以及数据长度。节点i+1听到控制包之后，同样会进行退避(Backoff)，以避免造成冲突。

当CTS控制包被源节点i收到以后，在下一时隙的开始时刻，该节点i首先发送一个清单包（HDR）控制包。这个控制包中包含了要传输的数据包个数和每个数据包的ID。之后源节点i便连续的顺序发送数据包。这些数据包可以占据多个时隙。为简单起见，本实施例发送3个数据包，数据包ID分别为1、2和3，如图1中所示。

当目的节点i+1接收完毕之后，比较HDR控制包中源节点i打算发送的数据包编号，以及实际收到的数据包编号。如果一致，则发送一个应答（ACK）控制包。反之，则表明有数据包丢失，于是向源节点i发送一个否定应答（NACK）控制包。NACK包中列出没有传输成功的数据包编号。本实施例2中，因为数据包2传输错误比较的结果是不一致，因此目的节点i+1向源节点发送NACK控制包，控制包中包含丢失数据包ID及丢失个数。本实施例2中丢失数据包为1个，丢失数据包ID为2。

源节点i如果收到ACK控制包，表明所有数据传输成功，可以开始下一轮的信道竞争。如果收到NACK控制包，源节点i查看控制包中的信息，得到数据包的ID编号。之后，源节点i在下一个时隙开始时刻，发送一个HDR控制包，列出要重新发送的数据包个数及其编号，紧接着便开始数据重传。本实施例2中，源节点i收到的是NACK控制包，得知丢失数据包的编号为2；接下来源节点i在下一时隙开始时刻，发送一个HDR控制包，列出要重新发送的数据包个数，1个及其编号2，紧接着便开始重新传输数据包ID为2的数据包。

本发明提出的“一种选择性重传、握手和时隙的水下介质访问控制协议”的状态机描述如下：

主要包含发送及接收两个线程，分别对应发送过程和接收过程。

对于发送线程：起初，传输数据的源节点i处于IDLE状态。如果需要传输一或多个数据包，进入SENDING_RTS状态，发送RTS进入WAIT_CTS状态。如果CTS控制包没有被目的节点i+1接收到，源节点i将转换到SENDER_BACKOFF状态，并且节点i-1进行相应的退避。否则，节点i转换到SENDING_HDR状态，发送HDR控制包，其后接着传输数据（DATA）包，进入WAIT_SRQ状态。在WAIT_SRQ状态，若超时或接收到NACK控制包后，节点重新回到SENDING_HDR状态，并且启动重新传输。另一方面，如果接收到ACK控制包，或者进入IDLE_BACKOFF状态或者进入IDLE状态，依赖于是否有其他的退避（BACKOFF）要求。

对于接收线程：接收的RTS控制包推进节点i+1进入到SENDING_CTS状态，节点i回复CTS控制包并进入到WAIT_HDR状态。接收到HDR控制包后，进入DATA_RX状态来收集进来的数据包。节点i进入SENDING_SRQ状态，并发送NACK控制包或者ACK控制包依赖于接收到的数据包数量。若接收到的数据包数量不够，节点i则进入WAIT_HDR状态，重新传输；若接收到的数据包数量够，则节点i进入IDLE状态。在IDLE状态，节点i侦听RTS/CTS/HDR/NACK控制包，迫使节点i-1及节点i+1进入IDLE_BACKOFF状态，把相关信息嵌入到控制包期间，一跳邻居节点i-1及节点i+1保持静默。

本协议的节点一共有三种行为。如果其队列中没有需要传输的数据包；就处于IDLE状态。否则，节点执行如下两种行为：

A）一方面，若节点被通知有可能碰撞或者因RTS/CTS控制包丢失而握手失败，此节点就执行退避（Backoff），此种情况下，包在节点中排列，我们称此种类型行为的时间间隔为“队列时延”；

B）另一方面，若节点感触到冲突行为并且完成了握手，就会接着发送一组数据包，在整组数据包发送前到所有数据包成功接收到之间的时间间隔称为“传输延时”。

对应到图1中，“传输延时”是指源节点i发出RTS控制包并成功握手到目的节点i+1收到“ACK控制包”之间的时间间隔。

需要说明的是，如果RTS/CTS丢失，节点将被迫尝试多次握手，仅在与最近一次RTS/CTS交换相关的延迟被计算为“传输延时”；前次握手消耗的时间被考虑为“队列时延”的一部分。一个单跳数据包的传递时间是“传输延时”和“队列时延”的和。

实施例2

我们还进行了海洋测试来评估本发明“一种基于选择性重传、握手和时隙的水下介质访问控制协议”的性能。

具体来说，主要从“跳-跳性能”（hop-by-hop）及“端-端性能”（end-to-end）来两方面来综合评估本申请提出的网络协议性能。实施例2分析了“跳-跳性能”（hop-by-hop）；而实施例3分析了“端-端性能”（end-to-end）。

所测海域布置的节点大致在海深80米处，浪高1.5米到2.5米之间。海域环境受波浪、潮汐、盐度及温度变化影响，也受及各类海洋哺乳动物活动影响。两个相邻节点间距离为1千米（公里，km），发送节点到接收节点间距离为7.3千米（公里，km）。网络拓扑采用应用广泛的弦拓扑（String Topology）结构。部署了9个水声网络节点，节点部署在新泽西海岸边120公里处，每个节点上面配置ATM-885的Teledyne Benthos Modem设备，工作在16kHz到21kHz的频段上，调制速率范围为140bps到2400bps，本实施例选取300bps到600bps范围进行测试，以保证通信可靠性和效率。发送节点在Aqua-NET应用层运行泊松流量产生器，测试过程中，我们设置泊松流量产生器的产生速率为0.005,0.015及0.024。

我们进行了三组成功的测试，调制解调器(modem)的功率等级、操作速率及不同测试的节点数如下表1所示：

表1 三组实测数据

测试序号功率等级操作速率节点数包长度训练长度传输速率11300bps5100B20.01521600bps8200B20.00531300bps9200B20.005

我们组建了5节点、8节点机9节点（对应4跳、7跳及8跳）网络。在所有三组测试中，我们设定Benthos调制器的传输功率至最低电平来保证节点能到达其一跳邻居。考虑到海洋环境复杂、丢包率高，故设定的包长度及数据包个数都比较少。由于端到端间的传输延迟太长，我们在测试中观察到，高的流量产生速率可以很容易覆盖全网络。

RTS控制包及CTS控制包携载着包训练序列长度；HDR控制包含数据包的长度；NACK控制包中包含丢失数据包的数量。假设会被侦听节点i-1侦听到且要传输的数据包总数为N；侦听到RTS控制包后，节点i-1必须保持退避，直至CTS，HDR，DATA及ACK传输完毕。因此，侦听到RTS控制包，退避的时隙数量 可以表达为：

>

其中，前3个时隙是CTS，HDR及ACK；每个占用一个时隙；而（1）公式的第二部分考虑的是数据包的传输延时与传播延时；T是时隙的长度，等于一个控制包的最大传播时延与传输延时的和。

类似的，我们计算侦听到CTS，HDR及NACK到退避的时隙数，如下：

>

>

>

其中，是侦听到CTS退避的时隙数量；是侦听到HDR退避的时隙数量；侦听到NACK退避的时隙数量。

接下来，分析水下通信网络的跳-跳间性能，主要包括单跳包传输延时及影响此延时的因素。

首先，我们测试了不同网络的平均传输时延，如图2、图3和图4所示，其中，图2是4跳网络的平均传输延时，图3是7跳网络的平均传输延时，图4是8跳网络的平均传输延时。传输延时通常包含RTS,CTS，HDR，数据（DATA），重传数据（DATA）、ACK及可能的NACK的传输时延和传播时延两部分。如图2所示，不同跳对应的传输延时呈现很接近的一致，其原因是，数据包丢失极少发生，因而传输延时的方差小。而在不同跳上显示的小方差波动产生于传输距离、海水温度与盐度变化以及声音的传播速度等因素。

类似的，从图3和图4我们可以看出：在7跳和8跳网络中，传输延时在保持相对稳定的同时出现了峰值点。翻看测试日志，我们进一步发现，对于7跳网络，传输延时主要出现在5跳处；时延峰值来源于数据包的重传；那条链路的数据包大量丢失，从而触发了相应的选择性重传机制，继而导致大的延迟。因此，影响传输延时的因素是特定跳的链路质量。即当链路质量很差时，数据包的丢失、NACK及ACK控制包引发重传丢失的数据包，导致传输延时增加。

其次，我们测试了“一个单跳数据包的包传递时间”队列时延的关系，如图5到图7所示。与图2到图4所示的单跳传输延时相比，单跳队列时延更大，且是总传输时延的重要组成部分，此处，总传输时延定义为队列时延与传输延时的和，即前面所述的“一个单跳数据包的包传递时间”。如图5所示，一个数据包的队列时延定义为当前节点接收到该数据包到上次RTS控制包发出引发成功握手之间的时间间隔。前述，我们提到数据包的排队，是因为邻居节点侦听到传输正在进行或者有RTS/CTS丢失而握手失败，邻居节点退避而产生的。在测试过程中，发现了引发队列时延另外一个重要因素，即：传输距离的不确定性导致的未预料的碰撞冲突。

在4节点网络测试中，最大的队列时延出现在跳1处，原因是我们采用了0.015的流量产生速率，是三组测试中最高的，即源节点每66秒产生一个数据包。从图6可以看出，“一个单跳数据包的包传递时间”即总传输时延大于150秒。而在跳3和跳4上的数据包到达速率远低于第一跳。高的流量产生速率导致源节点拟发更高频率的RTS控制包，从而导致后续节点的RTS控制包的发送速率提高。

相比之下，从图6和图7种可以发现，7节点网络和8节点网络的总传输时延降低了，原因是流量产生速率被降至0.005。图6中的跳3、跳4及跳5与其他跳相比经历了更大的队列时延。原因是，在弦状网络拓扑结构中，中间节点与边缘节点相比具有更多邻居节点，这些中间节点能够侦听到两个方向的RTS和CTS控制包。与图6类似，图7中的8节点网络中，在跳5出现了异常大的队列时延。这个现象有两个原因：一方面，正在进行的传输会导致邻居节点发送和接收的退避（Backoff）；另一方面，跳5也受如图2到图4所分析的高包丢失概率影响。

实施例2表明，对于网络协议的“跳-跳性能”评估，该实施例仅考虑了单跳的传输延时及队列时延。结果表明，传输延时仅仅受给定跳的链路质量影响。队列时延通常源于退避（Backoff）及握手失败。

然而，传输距离的不确定性能导致极大的侦听负载机碰撞，也能导致队列时延的提高；因此，为降低大的队列时延，我们进一步考虑让一个节点暂时放弃发送机会；这样，具有最短剩余退避（Backoff）时间的相邻节点，可以作为下一时隙第一个传输信息的节点；另一方面，由于队列时延主要取决于传输距离的不确定性，因此，可以考虑通过动态网络拓扑估计而不是事先假定网络拓扑，来降低队列时延。

实施例3

对于网络协议的“端-端性能”评估。本实施例考虑端到端传输延时，吞吐量，传输比例，结果如图8和图9所示。结果表明：传输范围不确定性在大网络中变得严峻，更多节点也导致更多的侦听负载及更大的碰撞概率，从而也导致大的延迟（从图8可以看出）。图9表明，网络节点增多，吞吐量降低。

考虑“端到端传输比例”，4跳，7跳及8跳三种场景都能达到100%传输比例，因为本协议为选择性ARQ机制，故保证了端到端传输的可靠性。

以上所述为本发明的较佳实施例而已，本发明不应该局限于该实施例和附图所公开的内容。凡是不脱离本发明所公开的精神下完成的等效或修改，都落入本发明保护的范围。