基于MACAW的分簇轮转调度式水声传感网MAC协议*

鲍万松，刘广钟

(上海海事大学 信息工程学院，上海 201306)

基于MACAW的分簇轮转调度式水声传感网MAC协议*

鲍万松，刘广钟

(上海海事大学 信息工程学院，上海 201306)

针对当前水声传感器网络长时延和低信道利用率的特点，改进传统的水声通信网MAC协议MACAW协议，设计出一种新型的分簇轮转调度式MAC协议CRD-MACAW协议。该协议通过网络初始化和网络动态更新对部署在网络中的传感器节点按照一定机制进行分簇，网络中的数据传输则分为簇内传输和簇间传输。簇内传输采用分簇时网络管理节点所分配的轮转顺序进行，节点与节点之间无需发送RTS帧和CTS帧；簇间传输则是通过各个簇首节点之间采用MACAW协议来进行的，最终网络数据汇聚到网络管理节点供分析使用。仿真结果表明，该协议与传统的MACAW协议相比，在网络节点增多、节点整体分布较为分散时，能够有效降低传输时延，提高信道利用率。

水声传感网；MAC协议；分簇；轮转调度；CRD-MACAW协议；MACAW协议

0 引言

近年来，随着海洋探索的不断发展，水声传感器网络的研究成为热点和前沿[1-2]。水声传感器网络是部署在水下环境当中的无线传感器网络[3]。由于水下通信环境极其复杂，与陆上无线电通信相比，水声通信存在着传输带宽有限、误码率高、传输时延长、信道利用率低、噪声等多种问题，这些问题对水声传感器网络传输协议的设计和实现构成挑战。

在水下通信中，水声通信是唯一可行的技术[4]。声波的传输速率约为1 500 m/s，比陆上无线电波传输速率低五个数量级。加上复杂的水下通信环境，现阶段基于竞争的MAC协议有较好的研究前景。本文在基于竞争的MAC协议MACAW协议基础上提出了一种分簇轮转调度式水声传感器网络MAC协议：CRD-MACAW(Clustering Rotation Dispatching MACAW)协议。该协议很好地解决了在复杂水声通信环境中传感器网络规模较大并且节点分布局部集中、整体分散情况下的长传输时延问题，能够更好地适用于海底勘探、海洋环境监测、海洋生物种群分布、海底导航等领域。

1 相关工作

在研究CRD-MACAW协议之前，首先分析目前性能较优的水声传感网MAC协议，主要是基于竞争的MAC协议，有文献[5]和文献[6]中提到的ALOHA协议以及文献[7]提到的CSMA协议。由于上述协议是基础协议，这里不做过多介绍。主要介绍以下两种协议：MACA协议和MACAW协议。

MACA协议是一种基于握手机制的水声传感网MAC协议[8-9]。当发送节点有数据发送时，不是立即发送数据，而是先发送RTS包作为握手信号给接收节点，接收节点收到RTS包时给发送节点返回一个CTS包，发送节点收到CTS包时才开始发送DATA包。MACA协议一定程度上减少了数据包的冲突，提高了信道利用率。但是繁琐的控制包传输消耗了大量的时间，增加了网络时延，并且数据传输完毕时，该协议没有设置确认机制，也影响了数据传输准确率。

图1 MACAW协议传输流程

MACAW(MACA-Wireless)协议[10]是在MACA协议基础上提出的改良协议。它在MACA协议的基础上通过增加ACK包实现了数据帧确认功能，提高了网络传输可靠性和吞吐量，图1给出了MACAW协议的传输流程。但是，当水下传感器网络规模变大、节点增多并且节点分布不均匀时，大量的RTS、CTS和ACK包将会消耗更多的传输时延，从而增加了网络传输整体时延。本文所提出的CRD-MACAW协议在MACAW协议的基础上进行了改进，以更好地解决上述问题。

2 CRD-MACAW协议设计

CRD-MACAW协议的基本思想是：将分布在水下传感器网络中的节点按照特定机制进行分簇，数据传输随之分为簇内传输和簇间传输。簇内传输采用轮转调度机制，簇间传输采用MACAW协议。

2.1 网络初始化与分簇

首先，在网络初始化之前预先设定一个网络管理节点。网络管理节点拥有三方面功能，第一是对网络采取一定机制进行分簇；第二是作为整个网络的数据汇聚节点；第三是负责网络动态更新。

网络初始化时，网络中各个节点广播自己的发送时间和节点标识。管理节点根据各个节点的发送时间与广播信息的接收时间来计算管理节点与网络中各个节点的距离l，并根据l和信号到达的角度α来对网络中的节点进行分簇。分簇时l和α的值选取范围根据网络部署现状进行随机设定。例如间距在、信号到达角度在<α1，α3>之间的节点为一个簇，间距在、信号到达角度在<α2，α5>之间的节点为另外一个簇。这里需要强调的是，l和α的取值上限预先给定。

分簇完成后管理节点为每个簇设置一个簇号N，同时结合节点标识为各个节点设置标号。这个标号是由簇号N和l来确定的，并且按照l由小到大依次排列，即N1、N2、N3…Ni。这里将每个簇中标号为N1的节点指定为该簇的簇首节点。簇首节点的功能就是本簇内数据汇聚以及簇间通信。分簇完成后，管理节点把节点标号广播出去，使网络中的各个节点都能得知自己的标号、自己所在簇的簇号、簇内成员节点的个数和簇首节点，同时也能够区分出其他簇中的节点。各个节点都会记录下自己的标号。图2和图3显示出网络初始化之前的原始状态和网络初始化之后的分簇状态。

图2 网络原始状态 图3 网络初始化之后的分簇状态

2.2 轮转调度设计

在上节所述的网络初始化完成以后，网络中各个节点被分在各个簇内，而且每个节点都有自己的标号。每个簇中按照标号(Ni、Ni-1、Ni-2…N1)排列的顺序，亦即l由大到小的排列就是簇内节点的轮转传输顺序，而且是经过优化的数据传输顺序，网络中节点收到管理节点广播信息之后会记录该轮转顺序。

下面讨论轮转调度设计。

第一，轮转调度流程。轮转传输在各个簇内进行，一个轮转顺序代表一个传输时间。网络初始化之后只有每个簇内轮转顺序第一的节点处于激活状态，其他成员节点均处于等待状态。每个节点只有接收到自己上级节点的触发指令时，才被激活，开始进行数据传输。当簇内一个源节点有数据需要发送并且收到上级节点触发指令时，直接将封装有触发指令的DATA包发送给它的下级节点，同时启动ACK信号接收定时器。当下级节点成功收到DATA包时被激活，立即返回上级节点一个ACK包用以确认数据包成功接收，同时将自己缓存当中的DATA包传输给它的下级节点，以此类推，直到数据成功到达簇首节点。簇首节点会将该数据以MACAW协议传输给其他簇首节点或者网络管理节点。同时，簇内传输依然按照轮转顺序进行。如果在ACK接收时间内源节点未收到其下级节点返回的ACK确认包，则采用时间退避算法进行数据重传。当重传次数达到重传阈值时认为该节点死亡或发生错误，会有相应的容错机制来进行处理，下文中将会详述。这里需要强调的是，每个簇的DATA包中触发指令片段包含了目的节点标号，当其他簇内节点收到不同簇内节点的数据包时，通过辨别节点标号中的簇号来选择是否接收。当簇号不同时，直接丢弃该数据，因此不同簇内的节点间无法进行数据传输。簇与簇之间只有簇首节点采用握手机制进行数据传输。图4给出了CRD-MACAW协议的传输流程。

图4 CRD-MACAW协议传输流程

第二，触发指令设计。簇内节点进行数据传输时，如果一个节点被激活，而该节点缓存区内无数据需要传输，那么此时轮转将会停止，从而造成网络陷入不必要的局部停滞状态，这显然是不合理的。这里，在每个节点的数据帧中加入简短的触发指令片段，触发指令片段中包括较短的触发片段和下一级节点标号等。当一个节点被激活时，如果该节点无数据传输，那么它将自己的触发指令发送给它的下级节点，当它的下级节点收到该触发指令时，立即发送自己的数据，并返回ACK信息给该发送节点，从而避免了网络陷入局部停滞状态。

第三，容错机制。如果簇内节点死亡之后，轮转传输即将停止，也会造成局部网络停滞。解决该问题的思想是：当一个源节点的下级节点死亡时，或者如上面所述该源节点在重传阈值内没有收到下级节点的ACK信号时，该源节点会发送一个封装有触发指令的信号给簇内其他节点，信号内包括自己的标号和下级节点的标号。簇内其他节点收到该信息时，比对自身标号，并且标号为源节点的下下级节点被激活，开始发送数据。同时，源节点将其下下级节点作为自己新的下级节点，记录在自己下轮数据传输的触发指令中；如果簇首节点死亡之后，簇首节点的上级节点将发送一个广播信息给全网络，告知簇号为N的簇首节点已经死亡。此时，网络中所有节点接收到该广播信息后，则认为簇号为N的源簇首节点的上级节点担任该簇的新簇首节点。至此，容错过程完毕。

2.3 网络动态更新

在水下传感器网络传输过程当中，节点死亡、节点流动、节点被海水腐蚀等情况造成网络中数据传输效率降低或局部停滞。针对此问题，CRD-MACAW协议中的网络管理节点会定期进行网络动态更新，更新过程与网络初始化过程相同。更新后的网络中管理节点会及时清除死亡节点，并进行时间同步，保障各个簇内轮转传输正常有序进行。

2.4 无误包重传时延

前文提到，CRD-MACAW协议由于分簇和轮转调度机制而省去了繁杂的RTS包和CTS包传输从而节省了大量的传输时间，提高了网络吞吐量和信道利用率。本节和2.5节着重介绍无误包重传时延和带误包重传时延两种情况下CRD-MACAW协议和MACAW协议对比。其中使用的参数名和意义如表1所示。

表1 文中使用的参数名和意义

首先，在MACAW协议中，n跳节点的平均传输时延为：

(1)

其中，Ds-d是源节点到目的节点的距离，由于每跳数据传输都需要RTS包、CTS包、DATA包和ACK包进行一次交换，故总传输距离是4Ds-d。

MACAW协议中，n跳节点的总传输时延是：

TW=nTeq-W

(2)

在CRD-MACAW协议中分为极端情况和一般情况。极端情况在网络传输中出现的概率非常小，甚至可以忽略不计。在此要分别进行讨论。

极端情况：网络中数据传输路径只经过每个簇的簇首节点，直到网络管理节点，不在簇内进行传输。此时n跳网络传输的总时延与MACAW协议相同：

Te-C=TW

(3)

一般情况：网络中数据传输既经过簇首节点，又经过簇内节点。此时，在n跳网络中经过的节点总数为n+1个。设经过簇首节点的个数为m+1个，其中包括网络管理节点；设经过簇内节点的个数为g个。那么易知簇间传输的总条数为m跳，簇内传输的总跳数为g跳。并且有：

m+g=n

(4)

此时，网络传输的总时延为：

(5)

其中，由于簇内传输时每跳数据传输只需要DATA包和ACK包共两次交换，簇间传输时与MACAW协议相同，需要四次交换，故源节点到目的节点传输总距离为(2g+4m)/n倍的Ds-d。从式(5)可知，当g=0时，也就是当网络传输遇到上述极端情况时，两种协议的网络传输总时延相同。

2.5 带误包重传时延

本节介绍带误包重传情况下的两种协议网络时延。需要声明的是，CRD-MACAW协议和MACAW协议在数据包需要重传时，均采用二进制指数回退机制。CRD-MACAW协议中分为簇内数据包重传和簇间数据包重传两种情况。设第一次回退时间为t，回退次数为x；设两个簇内节点间的距离为L1，两个簇间节点间距离为L2。则CRD-MACAW协议中簇内传输时重传增加时延为：

(6)

簇间传输时重传增加时延为：

t·(2x-1)+xTother

(7)

那么，在CRD-MACAW协议中，重传增加的总时延为：

(8)

在MACAW协议中，设两个节点间距离为L，那么发生重传时，重传增加的时延为：

t·(2x-1)+xTother

(9)

由式(6)～式(9)可知，当传感器网络不中节点增多、节点分布较为分散时，CRD-MACAW协议由于其加入分簇和轮转调度机制，省去了大量RTS包和CTS包的传输，在理论上比MACAW协议要节省重传时延。

下面讨论带误包重传情况下的网络总时延。在水下传感器网络中，造成误包的主要原因是冲突和误码率。针对MACAW协议和CRD-MACAW协议而言，造成误包的绝大部分原因是误码率。而且CRD-MACAW协议中簇内传输无法产生冲突，故网络中发生冲突的几率很小。在此，只讨论由误码率引起的误包重传。结合2.2节可知，CRD-MACAW协议与MACAW协议一样用ACK信号作为确认信号传输给其上级节点，那么两种协议的误码率PE=1-(1-Pe)LACK，因此，在网络中存在一定误码率且具有重传机制的情况下，MACAW协议的总时延为：

(10)

那么，CRD-MACAW协议的总时延为：

(11)

3 CRD-MACAW协议仿真

本文采用NS-2网络平台[11-12]基础下的Aqua-Sim水声传感网络模拟器[13]作为CRD-MACAW协议的仿真工具。仿真过程中重点对比CRD-MACAW协议与MACAW协议在传输时延上的性能。

3.1 仿真条件

本仿真实验中重要讨论传输节点间平均间距以及节点数量对传输时延的影响。仿真采用的部分参数如下：数据帧长度2 000 bit，RTS包、CTS包和ACK包的长度均为200 bit，数据传输速率为20 000 b/s，节点最大重传次数为5次，误码率为10-5。节点间平均间距和节点数量会在仿真中给出，仿真环境为水声环境。

3.2 仿真结果分析

图5和图6分别是传感器节点平均间距和节点数量对传输时延的影响。由图5可以看出，当节点数量给定为10个时，随着节点平均间距的增大，CRD-MACAW协议和MACAW协议传输时延都在增大，但是CRD-MACAW协议在节点平均间距不断增大时呈现出传输时延增长速率逐渐减缓的趋势，而MACAW协议传输时延的增长速率不断增大；同时，整个过程CRD-MACAW协议比MACAW协议传输时延平均小约26.4%，而且差距越来越大。这是因为，随着节点间距的增大，采用CRD-MACAW协议时簇内传输由于轮转调度机制而省去了大量的控制帧传输，从而节约了时间；相反，采用MACAW协议传输时，随着节点平均间距增大，大量RTS、CTS包需要不断长距离传输，大幅增大了传输时延。

由图6可以看出，当节点平均间距给定在1 500 m，随着节点数量的增大，CRD-MACAW协议和MACAW协议的传输时延都在增长，但是前者增长速率逐渐减缓，后者增长速率持续增大。整个过程CRD-MACAW协议的传输时延比MACAW协议传输时延平均小约31.2%，而且差距越来越大。这说明，随着节点数量的增长，采用CRD-MACAW协议传输时，落在簇内传输的概率较大，簇内传输由于轮转调度机制而节省了大量传输时延，采用MACAW协议时则随着节点数量增多，控制报文的传输次数也相应增多，从而提高了传输时延。

通过图5和图6的对比可知，在水声传感器网络中，当网络规模变大、节点数量增多、节点分布较分散时，CRD-MACAW协议在传输时延上明显优于MACAW协议。

图5 节点个数给定，节点间平均间距对传输时延的影响

图6 节点间平均间距给定，节点数量对传输时延的影响

4 结论

传统的水声传感网MAC协议MACAW协议在MACA协议的基础上通过增加了ACK确认机制，在一定程度上提高了数据传输效率和传输可靠性。本文提出的CRD-MACAW协议在MACAW协议的基础上通过分簇和轮转调度的方式使簇内传输过程减少了大量RTS包和CTS包，节省了大量传输时间；同时保留了ACK确认机制，保持了MACAW协议的优点。仿真结果表明，在传感器网络中节点数量增多、节点整体分布较为分散且局部集中的情况下，与MACAW协议相比，CRD-MACAW协议明显减少了传输时延，提高了信道利用率。CRD-MACAW协议更适合应用于海底导航、海洋环境监测和灾害预警等水声通信领域。

本文未来工作应着力于网络规模较大时分层协议的设计，以不断优化CRD-MACAW协议来研究上层路由协议，使二者能够在通信过程中达到较高的契合度，从而加强网络资源的利用，降低网络时延，进一步提高信道利用率。

[1] RICE J, CREBER B, FLETCHER C, et al. Evolution of seaweb underwater acoustic networking[C]. Oceans 2000 MTS/IEEE Conference and Exhibition, 2000:2007-2017.

[2] 刘广钟, 耿伟. 水声传感器网络分簇路由协议研究[J]. 微型机与应用, 2012, 31(8):44-47.

[3] AKYILDIZ I F, POMPILI D, MELODIA T. Underwater acoustic sensor networks: research challenges[J]. Ad Hoc Networks, 2005, 3(3):257-279.

[4] 刘文静. 水声传感器网络MAC协议研究[D]. 大连:大连理工大学, 2015.

[5] Xiao Yang, Zhang Yanping, GIBSON J H, et al. Performance analysis of p-persistent aloha for multi-hop underwater acoustic sensor networks[C]. International Conference on Embedded Software and Systems, IEEE, 2009:305-311.

[6] 王毅,高翔,方世良,等.Aloha-LPD:一种用于水声通信网的MAC协议[J].东南大学学报(自然科学版),2009, 39(1):12-17.

[7] Fang Dong, Li Yu, Huang Haining, et al. A CSMA/CA-based MAC protocol for underwater acoustic networks[C]. International Conference on Wireless Communications Networking and Mobile Computing, IEEE, 2010:1-4.

[8] Zhao Qichao, LAMBERT A, BENSON C R. FS-MACA: a future scheduling MAC protocol in underwater acoustic networks[C]. Proceedings of the International Conference on Underwater Networks & Systems, 2014:1-5.

[9] Guo Xiaoming, FRATER M R, RYAN M J. A propagation-delay-tolerant collision avoidance protocol for underwater acoustic sensor networks[C]. IEEE Oceans OES and MTS, 2007:1-6.

[10] BHARGHAVAN V, DEMERS A, SHENKER S, et al. MACAW: a media access protocol for wireless LAN’s[J]. ACM Sigcomm Computer Communication Review, 2000, 24(4):212-225.

[11] KANTHIMATHI N, DEJEY. Balanced and multi-objective optimized opportunistic routing for underwater sensor networks[J]. Wireless Personal Communications, 2016:1-24.

[12] 石为人, 黄河, 鲜晓东,等. OMNET++与NS2在无线传感器网络仿真中的比较研究[J]. 计算机科学, 2008, 35(10):53-57.

[13] Liu Tongqing, Han Guangjie, Zhu Chuan, et al. Application research on aqua-sim for underwater acoustic sensor networks[J]. Advanced Materials Research, 2012, 605-607:1046-1049.

Clustering rotation dispatching MAC protocol for underwater acoustic sensor network based on MACAW

Bao Wansong, Liu Guangzhong

(College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

Aiming at the long delay but low utilization rate of channels of the present underwater acoustic sensor network, traditional underwater acoustic communication network MAC protocol MACAW has been improved into a new clustering rotation dispatching MAC protocol, CRD-MACAW. This protocol rotates the sensor nodes in the network with certain mechanism through the network initialization and network dynamic updating. And the data transmissions in the network are divided into transmissions in cluster and transmissions between clusters. Transmissions in cluster are done according to the rotating order matched by the managing node in network when clustering. RTS frame and CTS frame need not be sent between nodes, while transmissions between clusters are done using the MACAW protocol between the first nodes of every cluster, and finally the data in the network will be gathered at the managing node in network to be analyzed. The simulated result shows that this protocol can decrease the transmission delay effectively and improve the utilization rate of channels if nodes in the network are increasing and the node distribution is decentralized totally when comparing with the traditional MACAW protocol.

underwater acoustic sensor network; MAC protocol; clustering; rotation dispatching; CRD-MACAW protocol; MACAW protocol

国家自然科学基金(61202370)；上海市教委科研创新项目(12ZZ151)

TN929.3

A

10.19358/j.issn.1674- 7720.2017.16.021

鲍万松，刘广钟.基于MACAW的分簇轮转调度式水声传感网MAC协议[J].微型机与应用，2017,36(16)：73-77.

2017-02-22)

鲍万松(1990-)，男，硕士研究生，主要研究方向：分布式计算与传感器网络。

刘广钟(1962-)，男，博士，教授，主要研究方向：分布式数据库、分布式人工智能、计算机网络技术、网络计算、CIMS技术、物流信息化技术等。