基于水声传感网络的树形拓扑混合MAC协议*

类延增，刘广钟，徐 明（上海海事大学　信息工程学院，上海 201306）

基于水声传感网络的树形拓扑混合MAC协议*

类延增，刘广钟，徐 明
（上海海事大学信息工程学院，上海 201306）

鉴于水下传感网络的长时延、低带宽的特点，设计有效的水下无线网络的通信传输协议很有必要。提出一种树形拓扑结构的结合基于竞争和基于分配两种模式的混合策略，减少了水声通信中的握手次数，即减少了RTS/CTS请求的发送次数，利用组播、LRU预留时间策略提高了传输效率，整合了网络通信中ACK包和数据包的发送，既能使所有节点间实现自由通信，又能提高网络吞吐量、节约能耗。

水声传感网络；组播；加密；延长阶段；保留时间

0　引言

如今“智慧城市”、“智慧港口”、“智慧家居”等概念不断提出并完善，其中无线通信技术作为一条核心纽带联通了客户与无线设备，陆地无线通信技术的成熟，带动了水下无线传感技术的发展。无线传感技术在海洋环境检测、海底矿物探测、海洋水下搜寻、海洋数据采集、水下机器人作业任务中都起到重要的作用。

水声通信是目前水下传感技术的主要方式，存在传播时延长、带宽有限这两个主要不足，除此之外，流动性、水流速度、水的混浊程度等都对通信能力造成影响，使得水声传感网络的吞吐量变低、误码率变高、通信质量下降。水声通信协议的研究旨在通过协议避免冲突的发生，提高通信效率，节约通信能量。水声通信协议与陆地无线传感网络一样，主要分为基于竞争和基于分配的两大类。

［1］是基于树形拓扑结构实现的，该协议引入了马尔可夫决策过程，使每个子节点通过马尔可夫决策过程决定下一次传输需要的传送时长，发出请求，父节点结合自身时间片和子节点请求安排合理的传送时间和时长，子节点分配进行数据的传送，均衡节点的负载，使网络达到平衡。ROSS［2］也是一个在树形分层拓扑中设计的协议，通过引入睡眠模式实现节能，利用自上而下的时间片决策确定各个节点的传送时间片，时间片决策达到平衡后，每个周期按照平衡时的状态循环工作。ROSS协议的实现简便易懂，缺点是协议的环境是完全静态的网络，无法动态地调整网络状态，在ROSS协议中，也没有采用ACK应答机制。但此协议减少了握手次数，实现了节能效果。这两个协议作为树形网络的典型代表，都只是实现了单向传输，无法实现簇内节点的通信。

S-FAMA［3］、ST-MAC［4］、ESC［5］、R-MAC［6］等协议也都在水声通信环境中实现了优秀的效果，其中S-FAMA着力解决了隐藏终端的问题，通过对RTS/CTS设置保留时间，达到避免隐藏终端冲突的问题。这些协议大都允许网络节点的自由通信，频繁的握手使得需要在耗能方面做出妥协。

1　相关分析

在树形拓扑中，要实现一个簇集的簇内通信，经过对比设计，在拓扑结构中增加一个簇首节点，称这个节点为内簇首节点，原来的簇首称作外簇首节点，分别利用不同的簇首进行簇内和簇外通信，拓扑结构如图1所示。

图1　改造后的簇结构

协议Ordered-CSMA［7］中提出，无线传感信号是同心圆状的发射波，一个节点在向其中远端节点发送完信息后，不需要等待其接收完毕，即可向近端节点发出信号。如图2所示，AB的距离小于AC的距离，A节点可以先向C节点发送数据，A节点发送完后，不需要等待C节点接收完数据信息，可以紧接着向B节点发送数据，两部分数据可以同时到达目的节点而不发生冲突，比传统收到确认信息后再次发出要节省时间。

图2　无线信号传播示意图

利用这个特征，在子节点发出外部通信数据后，紧跟着发送内部通信的数据，内簇首负责接收内部通信的数据，而外簇首负责接收需要发送到簇外和汇聚节点的信息，同理，内外簇首任何一个可以先发送信息，当另一个探测到信息发送完后可以紧接着发出自己的信息。内节点需要协调多个簇内节点间的信息，假设每个子节点的信息单独传送，需要多次握手协商、传送，这里采用组播方式，所有簇内子节点接收同一个信息包，每个子节点根据自己的信息分别留取和分析属于自己的数据段，但是存在多个子节点给同一个兄弟节点发送信息的情况，内簇首需要对接收到的信息进行整合，把目的地址相同的数据整合在同一数据段发送。考虑到信息安全问题，后面需要论述加密机制。

在水下环境中，通信节点具有时空流动性，节点与簇首节点间的距离容易出现变动，就使得节点与簇首节点间的距离存在不确定性。针对这个问题，让两个簇首节点位置上无限靠近，在时间上采取相邻发送，取极限状态，采用同一个簇首来完成内外信息的交互，如图3所示即是最终采用的簇结构。

图3　树形拓扑的一个簇集

2　协议设计

根据ROSS和Z-MAC［8］的冲突避免机制，如图4所示，本协议在 RTS/CTS初始化阶段，简单地采用自上而下的交叉的TDMA有序分配，为每个节点分配发送RTS请求的时间片，分配完成后，在以后每个发送周期中都固定不变。每个节点需要发送数据时，在向簇首节点发送RTS包申请时间片时，只能在其分配好的RTS申请时间点发送RTS包。簇首节点根据具体的子节点请求和节点间的距离，合理分配数据传输的时间片。

图4　簇集通信初始化示意图

考虑到信息传输的安全性，在网络拓扑结构初始化时，每个子节点都需要把自己的公有密钥发送给簇首节点，簇首节点和子节点之间建立非对称加密算法，目的是在内部通信阶段，簇首节点针对不同子节点的信息，利用其公钥进行加密，每个收到信息的子节点通过自己的私钥对信息进行解密，避免了节点恶意获取其他节点信息。

数据包的格式如图5所示。在这种数据包格式下，在包头标记中，需要表明每个节点的顺序，而且包含了每个节点的数据长度，方便获取属于自己的数据段。其中，每个子节点信息经过整理，包含了多个发送方的数据和标记信息等。其中，Distart表示属于第 i个节点的数据的物理起始位置，Ltag是包头标记信息的长度，Lj、Li表示第j个和第 i个节点的数据长度，相应的 Diend表示第 i节点数据的结束位置。

图5　簇首数据包格式

本协议只为发送RTS请求的节点分配数据发送时间片，其他时间处于睡眠状态。为了实现这个目标的同时减少握手的能耗，采用预留时间片机制。与协议SFAMA［3］和CSMA/CA中预留时间的概念不同，本协议采用的预留时间片策略，将横向扩展改为纵向扩展，即预留的时间不是在本次的传输时长上延长，而是在次数上进行预留。在这个时间周期内，如果子节点B向簇首节点发送请求并得到了许可，在接下来的n个时间周期中，默认节点B不需要再次发送请求就可以直接进行传输，称B节点处于延长阶段。只是簇首节点还要在RTS/ CTS阶段进入监听状态，而子节点在未收到时间片终结信号的情况下，可以处于睡眠状态。

有新的节点发出传输请求时，采用内存管理中用到的经典算法——LRU算法。LRU（Least Recently Used），最近最久未使用算法，在内存分配时，因为内存空间有限，一些资源不方便一次性全部调入内存中，LRU算法把内存中距离现在最长时间未使用的资源空间替换为接下来需要用到的新的资源，以剔除掉最没有可能传输数据的节点。

具体优先级别规定如下：

Pidle〉Pextend〉Pfirst（3）其中，Pidle是空闲阶段优先级，Pextend是延长阶段的优先级，Pfirst表示首次正常传输的优先级。当对比的优先级相同时，需要看节点申请连接的顺序，最早申请连接的节点具有最高优先级，最容易被替换。

实现算法的伪代码如下：

如图6，B点发送了新的数据连接请求，簇首节点A在检索自己的接收时间后，发现没有合适的空闲时间分配给B节点，D节点正处于延长阶段，而D节点在本周期没有发送数据，簇首节点只能处于空等状态。A节点检索对比后发现，可以把D节点的时间段经过调整分配给B节点传送数据。A节点在接下来进行组播，要在给D节点的数据包中说明下个阶段开始断开其连接，而在给B节点的数据中，说明给B节点协调的传送时间。

图6　一个典型的时间阶段

总结本协议的特点，首先协议基于树形分层拓扑结构使得网络中节点的信息交换分区域聚合，在小区域内达到较高的通信效率，对LEACH协议和ROSS协议经过改进后，实现了网络中各节点相互通信的要求；利用簇首和子节点把簇内通信信息和簇外通信信息进行整合，簇首的加密组播模式避免了信号冲突、重复多次握手的耗能浪费；传输阶段舍弃了ROSS中完全静态的任务循环重复模式，采用预留时间片模式，在尽量减少握手的情况下，保持网络中节点的高效通信。协议中用到了LRU算法，定义协议名称为LRU-MAC。

3　模拟对比

在MATLAB中用实验验证协议的效果，对比RMAC和ROSS的模拟环境，将一个数据包仿真的接收消耗、发送消耗和睡眠消耗分别设定为13 mW、24 mW和15 μW，传输一个数据帧的速率为1 000 kb/s，水声传播速度为 1 500 m/s。RTS包包含请求地址、位置信息等，大小为 100 bit，数据帧大小为 2 000 bit，每个周期为200 ms。

通过实验模拟，首先确定LRU算法中n的合适数值。经对比，网络平均耗能和网络吞吐量方面的性能会随着n值的增大而提高，这是因为n值变大，协议中平均的RTS请求变少，平均握手次数减少，使得耗能和吞吐量开始变优。但当n值过大时会造成LRU算法频繁置换，耗能和吞吐量方面的性能反而会下降，如图7、图8所示，可以看到在模拟环境中，当n取值为4时，吞吐量和网络耗能处于最佳状态。

图7　n取不同值时的平均耗能

图8　n取不同值时的平均吞吐量

本协议通过模拟实验，在吞吐量和能耗方面与RMAC和 ROSS两个协议作了对比。ROSS只是在静态环境中实现，在能耗上是省去了每个周期发送RTS和ACK包的能耗，但其无法实现簇内节点的通信，在功能全面的协议中，本协议在平均吞吐量和能耗上有明显的改进。具体对比如图9、图10所示。

图9　不同协议间的平均耗能

图9中，R-MAC初始化网络不需要所有的节点都发送初始化数据包，初始组网耗能相对于ROSS和LRU-MAC较少，而ROSS和LRU-MAC的初始化是相似的，子节点都需要向簇首节点发送信息，耗能都比RMAC高。随着网络负载增大，R-MAC需要频繁地进行握手、避免冲突、探测信道，耗能迅速上升并超过其他两个协议，而ROSS作为静态网络不需要再次握手，能耗相对平稳。LRU-MAC需要偶尔握手，它的耗能虽然比ROSS高，但比可以自由通信的同类协议R-MAC要节约耗能。

本协议结合无线信号同方向依次传播不会发生碰撞的特性，采用组播、LRU预留时间片策略，在吞吐量和耗能方面进行了优化。LRU-MAC协议减少了每次单独发送RTS和ACK包的负载，在平均吞吐量方面对比于ROSS、R-MAC协议都有很大的提升，在能耗方面明显比R-MAC要优秀，虽然ROSS平均能耗较小，但本协议在簇首节点传输给子节点的信息中整合了ACK包，减小了数据传输的误码率。

4　结论

本文提出并设计了一种新的LRU-MAC协议，该协议结合传统水下无线传感网络和典型的树形分层拓扑网络各取所长设计而成，在总体上以减少节点间的握手次数、空闲时间休眠为手段，通过实验对比，证明新的协议在网络平均吞吐量和平均耗能方面都有改进，表现良好，最重要的一点是，本协议突破了传统树形分层拓扑网络只单向传输的特点，同时实现了簇内和簇外传输。

但是本协议也存在一些弊端需要克服，比如簇首节点的负载要比普通子节点高很多，容易造成簇首节点比子节点提早完成寿命，这个问题在参考文献［9］中提出了一种解决方法，簇首节点的工作机制也较为复杂，这些问题还要进一步解决。

参考文献

［1］JITHIN J，SAJI A，HOVANNES K，et al.A hybrid MAC protocol with channel-dependent optimized scheduling for clustered underwater acoustic sensor networks［C］.Proceedings of the 8th ACM International Conference on Underwater Networks and Systems，WUWNet 2013，DOI：10.1145/ 2532378.2532382.

［2］Hong Lu，Hong Feng，Yang Bozhen，et al.ROSS：Receiver oriented sleep scheduling for underwater sensor networks ［C］.Proceedings of the 8th ACM International Conference on UnderwaterNetworksand Systems， WUWNet2013，DOI：10.1145/2532378.2532396.

［3］MOLINS M，STOJANOVIC M.Slotted FAMA：A MAC protocol for underwater acoustic networks［C］.16th IEEE International Symposium on the Applications of Ferroelectrics，ISAF，2006，DOI：10.1109/OCEANSAP.2006.4393832.

［4］HSU C C，LAI K F，CHOU C F，et al.ST-MAC：spatial-temporal MAC scheduling for underwater sensor networks［C］.Proceedings IEEE INFOCOM，2009：1827-1835.

［5］Hong Lu，Hong Feng，Guo Zhongwen，et al.ECS：effcient communication scheduling for underwater sensor networks［J］.Sensors，2011，11（3）：2920-2938.

［6］Xie Peng，Cui Junhong.R-MAC：an energy-efficient MAC protocol for underwater sensor networks［C］.In the Second International Conference on Wireless Algorithms，Systems and Applications（WASA 2007），2007：187-195.

［7］Chen Yinjun，Wang Haoli.Ordered CSMA：a collision-free MAC protocol for underwater acoustic networks［C］.Oceans Conference Record（IEEE），2007，Oceans 2007 MTS/IEEE Conference，DOI：10.1109/OCEANS.2007.4449386.

［8］RHEE I，WARRIER A， AIA M，et al.Z-MAC：a hybrid MAC forwirelesssensornetworks［J］.IEEE/ACM Transactions on Networking（TON），2008，16（3）：511-524.

［9］刘广钟，耿伟.水声传感器网络分簇路由协议研究［J］.微型机与应用，2012，31（8）：44-47.

A hybrid MAC protocol in the tree topology based on the underwater acoustic sensor networks

Lei Yanzeng，Liu Guangzhong，Xu Ming
（Information Engineering College，Shanghai Maritime University，Shanghai 201306，China）

According to the features of long delay and low-bandwidth in the underwater sensor networks，designing an effective underwater wireless communication network transporting protocol is necessary.This paper presents a combined protocol in a tree topology，which mixes competition modes and allocation strategy.The strategy reduces underwater acoustic communication handshakes and the numbers of transmissions of RTS/CTS requests by multicast and LRU reservation.That greatly improves transmission efficiency.By integrating the data packet and the ACK packet，the protocol not only achieves freedom communication between all nodes but also improves network throughput and energy-saving effect.

underwater acoustic sensor networks；multicast；encryption；last longer time；reserved time

TN929.3

A

1674-7720（2015）15-0071-04

类延增，刘广钟，徐明.基于水声传感网络的树形拓扑混合MAC协议［J］.微型机与应用，2015，34（15）：71-74.

2015-03-03）

类延增（1989-），男，硕士研究生，主要研究方向：水下声传感网络。

刘广钟（1962-），男，博士，教授，主要研究方向：水下声传感器网络、分布式计算。

徐明（1977-），男，博士，副教授，主要研究方向：水下声传感器网络。

上海市教委创新项目资助（12ZZ151）