水下无线传感器网络路由算法概述

李梅菊 徐涛 贾继洋

【摘要】    本文首先对水下无线传感器网络与陆地无线传感器网络的区别进行了调查;其次，分析了水下無线传感器网络的拓扑架构以及网络分层;最后，对目前存在的水下无线传感器网络路由算法进行了研究，总结出不同种类路由算法存在的问题，基于位置的路由算法存在精确定位的问题，位置独立的路由算法难以兼顾网络各方面的性能，簇结构的路由算法无法解决传感器节点能耗不均的问题，基于智能水下机器人的路由算法中网络搭建的经济成本高。本文的研究可以为以后设计专门的适用于水下无线传感器网络的路由算法提供参考。

【关键词】    水下无线传感器网络    路由算法    地理路由    簇     水下机器人

引言：

近些年，发现更多的水下资源以代替逐渐减少的有限的陆地资源，成为了众多学者的研究目标。水下无线传感器网络在地震、海啸预警、生态系统监测、石油钻探和军事监视方面的应用也同样被关注。水下传感器网络由于其特殊的运行环境，成为了探索水下资源最有效的方法，从而引起了学者们的极大兴趣。而传感器技术的发展为水下无线传感器网络的发展奠定了技术基础，随着国家对海洋资源的重视程度加强，在政策层面，水下传感器网络的发展具有着前所未有的机遇。然而，由于水下无线传感器网络工作环境的特殊，光的散射、折射及多普勒效应，导致光信号在水下衰减很快;而电磁波的快速衰减也不适合在水下进行通信;从而在水下传感器网络中使用声音信号进行通信。

由于水下无线传感器网络使用声音信号进行通信，且通信环境较为复杂，使其具有如下一些不同于陆地网络的特点[2]：

1.有限的能量。由于水下传感器网络工作在水下，节点配置的电池很难更换，且电池无法使用太阳能充电。因此，一旦电池能量耗尽，节点死亡。

2.定位困难。水下传感器网络精确定位困难主要有两方面原因：1） 在陆地网络中，用的最多的定位技术为GPS 定位，但由于在水下GPS信号衰减太大，无法使用在水下;2）水下传感器网络中，节点随着水流的移动而移动，而非固定的位置，因此在动态的拓扑结构中，无法根据最初的位置确定变动后的拓扑结构。

3.信号传播延时大。陆地网络中，信号的传播速度为 3×108米/秒，水下无线传感器网络中，信号传播速度为1500米/秒。因此，水下无线传感器网络中信号的传播速度比陆地无线传感器网络信号传播速度慢五个数量级。

4.布置稀疏。由于水下无线传感器网络节点昂贵，因此很少布置备用节点，一旦某个节点死亡，没有其他节点可以备用。

5.误码率高。水下无线传感器网络通信环境复杂、拓扑中出现空洞、数据在传输过程易碰撞等原因，导致其丢包率较高，从而误码率增大。

由于上述原因，导致陆地上使用的路由算法无法直接应用在水下无线传感器网络中。因此，设计专门适用于水下无线传感器网络的路由算法对于水下无线传感器网络技术的发展有着至关重要的作用。

鉴于此，接下来，本文从如下几方面对水下无线传感器网络进行了归纳分析：

1.介绍了水下无线传感器网络的架构，概括调查了网络各层核心技术;

2.研究了不同类型的水下无线传感器网络路由算法，并分析了各类算法的优缺点;

3.最后，总结了全文，并对未来工作进行了展望。

一、水下无线传感器网络基本架构

网络是设计路由算法的基本依据，因此在具体了解路由算法之前，首先调查研究水下无线传感器网络的基本架构至关重要。本节从水下无线传感器网络的拓扑结构和网络分层两个方面分析水下无线传感器网络的基本架构。

1.1  网络拓扑架构

水下无线传感器网络拓扑结构通常有两种，三维结构和二维结构。

1.1.1二维网络拓扑架构

二维拓扑架构的水下无线传感器网络主要用于水下环境的监控、灾难预警等应用场景。典型的二维水下无线传感器网络由固定在水底的水下传感器节点和水面上的一个或者多个sink节点组成。水面上的sink节点主要负责中继水下传感器节点收到的数据，发送到地面上的数据服务中心。水下传感器节点之间以及水下传感器与sink节点之间进行通信用的是声音信号，sink 节点与陆地上的数据中心用电磁波信号进行通信。因此，sink节点装有声音信号调制器和光信号调制器，而水下传感器节点只装有光信号调制器。

在二维水下无线传感器网络拓扑结构中，水下传感器节点通过单跳的方式与水面上的sink节点进行通信，当研究区域较深时，这样的方式存在两方面的问题：一方面信号的传播距离太长，随着距离增加，信号衰减变大，因此，产生误码或者丢包的概率增加;另一方面，由于水下节点能量有限，长距离传输需要更大的发射功率，节点能耗更大，缩短网络寿命。

1.1.2三维网络拓扑结构

如上文所述，二维网络拓扑结构不适合在研究区域比较大的网络中使用。同时，当需要采集水下环境中不同深度的环境样本值时，需要在不同深度布置传感器。因此，在现实生活中，三维网络的应用更为广泛，且三维网络架构与实际研究更吻合。三维网络在二维网络的基础上进行了改进完善，除了水的底部和表面上的sink节点，不同深度都布置有水下传感器节点。水下节点与水面上的Sink节点通信通过多跳方式。水下传感器节点既可以作为源节点收集数据也可以作为中继节点转发数据。

1.2水下无线传感器网络分层架构

水下无线传感器网络包括物理层、链路层、网络层、传输层和应用层，这与陆地无线传感器网络的结构相同，不同的是两种网络在各层使用的协议。目前水下无线传感器网络技术的主要研究集中在物理层、链路层、网络层、传输层。

在物理层，通过研究光信号、电磁波信号以及声音信号，已经确定声音信号是最适合于在水下传播信息的。而噪声和衰减对信号传播成功率有着较大的影响。物理层的性能影响着网络的整体设计，频率分配的不同导致网络的物理特性不同，高的信号频率引起较大的衰减，但干扰会降低。

链路层中如何找出一种有效的方法实现多用户的资源共享依然是水下无线传感器网络研究的热点。时分多址和频分多址已经被尝试用在水下无线传感器网络中。由于水下传感器网络的时间同步仍是研究热点，不要求时间同步的CDMA结合功率控制技术的MAC层协议已经提出，且可以抵抗多径效应。

传输层协议的设计对网络的性能影响较大。由于水下无线传感器网络带宽非常有限，且误码率高，陆地无线传感器网络使用的TCP协议无法在水下无线传感器网络中使用。目前研究显示，网络编码和前向纠错技术应用在水下无线传感器网络中效果较好。

网络层作为水下无线传感器网络尤为重要的一层，路由算法的设计对网络的网络寿命、延时等起着决定性作用。因此，如何根据水下无线传感器网络的特点，设计专门的路由算法是目前研究的热点。详细情况见第2节。

二、路由算法分析

为了改进水下无线传感器网络的性能，在网络层面，学者们设计了不同的路由算法。其中，最为典型的是2008年cui等提出的DBR 路由算法[2]，DBR路由算法的提出为水下无线传感器网络独立于位置信息的路由算法奠定了基础。在DBR算法中，只有比自身深度值小的传感器节点有资格作为转发节点，为了减少冗余转发，节点依据深度设定抑制转发时间，具有最小深度值的节点，抑制时间最短，当其他节点听到已经有节点转发了当前数据包便不再转发该数据包。而2006年提出的VBF 算法，奠定了矢量路由的基础。在VBF算法中，源节点与水面上的sink 节点建立矢量，只有在矢量半径内的节点有资格作为转发节点，半径内节点根据自身到矢量中心的距离，计算转发数据的抑制时间，从而抑制冗余转发。随着陆地机器人技术的发展，智能水下机器人（Automatic underwater vehicle，AUV）被引入到水下无线传感器网络中，AUV作为收集水下传感器节点数据的核心，可以大大节省水下传感器网络的能量。在文献[3]中提出，使用跨层的路由技术，结合MAC层，引入编码技术，该路由算法对于降低数据包误码率有一定帮助。在2018年，我们团队设计的基于和声搜索的路由算法[4]，在创建路由的过程中，引入了和声搜索算法，使用和声搜索算法进行簇分配，使得簇内节点之间以及不同簇的簇首之间的能量得到均衡。在2019年，在分析DBR及改进的DBR算法优缺点的基础上，本团队设计了基于竖直角度的最短路径路由算法[5]。

路由算法按照不同的标准有不同的分类方法。本节分别依据是否需要位置信息以及算法的技术特点对目前存在的水下无线传感器网络路由算法进行分析。

2.1  基于位置的路由算法

基于位置的路由算法中，以已知位置信息为前提，比较典型的是VBF路由算法。从第2节的介绍中，不难发现，VBF对转发节点的位置有较大的限制，因此在稀疏网络中，如果半径设置的太小，会由于节点找不到下一跳导致数据包丢失。同时，由于在VBF中仅仅依据到达矢量中心的距离判断转发节点，没有引入其他参数，对于通信环境复杂的水下传感器网络是远远不够的。针对VBF的缺点，文献[6]提出了HHVBF，该算法用每一跳之间建立矢量代替VBF中从源节点到sink节点建立矢量，以使得在选择下一跳时，每个节点可以根据自身周围节点密度确定矢量半径大小。因此，HHVBF算法中，只要存在邻居节点，都可以将数据包转发出去，提高了报的交付率。但是，HHVBF算法中节点转发数据包是依赖于等待时间，易出现多个节点转发同一个数据包，因而不仅浪费能量而且增大了延时。为了降低上述几个协议中丢包率高的问题，DFR 協议被提出，DFR中，参与转发的节点数量可以通过改变广播角的大小动态调整。为了进一步增强数据传输的可靠性，2017年Nadeem J等提出了2hop-AHH-VBF算法[8]，该算法中节点可以获取两跳节点信息，避免数据被转发到空白区域。2020年，AVH-AHH-VBF算法被提出，该算法中，sink节点智能地移动，有效地均衡了靠近sink节点的能量。

基于位置的路由算法前提条件是能够精确获取水下无线传感器网络节点的位置信息，而水下无线传感器网络的精确定位目前仍然是研究热点。

2.2  位置独立的路由算法

位置独立的路由算法主要是指不依赖于具体的位置信息设计的路由，DBR 作为比较早期的独立于位置的路由算法，有一些不足之处，如在选择下一跳节点时只依据深度差值、转发过程中有隐藏终端的出现、系统延时较长。针对DBR协议中未考虑能量的问题，2011年，Wahid 等提出了EEDBR，EEDBR将剩余能量与深度值结合作为选择下一跳节点的参考指标。随后，M.Jafri 等设计了AMCTD算法，算法中通过设置深度阈值抑制转发节点数量，为了避免上层节点过多消耗能量，引入快递节点。该算法对数据敏感的应用性能较差。因此，2014年，一种改进的AMCTD算法I-AMCTD出现[9]。I-AMCTD中设置了软硬结合的能量阈值。2016年， WDFAD-DBR算法被提出，该算法中结合邻居节点的深度差和转发区域的划分确定转发节点。2018年，我们团队提出了SPRVA路由算法，算法中结合节点剩余能量和邻居节点在竖直方向上的夹角确定最佳下一跳，不仅节省能量，且缩短了数据传输的延时。2019年 ，EBER2算法被提出。算法中，结合剩余能量和转发节点的潜在转发节点数量确定下一跳节点，一方面有助于能量的均衡，另一方面有助于降低数据传输的丢包率。

位置独立的路由算法往往是以牺牲一方面的性能为代价以取得另一方面性能的提升。

2.3  AUV輔助下的路由算法

由于水下传感器节点能量有限，且上层节点能耗更大，一些学者在路由过程引入了水下机器人，即AUV。2008年Paley D 等提出了GCCS[10]，该系统中，每个滑行器装有传感器节点，滑行器在水下收集数据，周期性地到水面上与sink节点进行通信，为水下机器人的发展提供了基本思想。2012年，AURP 算法被提出，算法中AUV作为网关与sink节点通信的中继，当网关死亡时，距离AUV最近的传感器节点作为网关。该算法一定程度能够节省网络能量，但能量均衡问题仍然存在。2015年，Javaid N等提出了AEDG算法[12]，该算法中多个AUV 按照预定的轨迹运动，且限制了每个网关负责的传感器节点数量。Maqsood H等在2016年提出了多播路由算法AUV按照预定的轨迹收集数据[13]。

AUV辅助下的路由算法中，由于水下机器人的价格昂贵，网络布置的经济成本增大。

2.4 基于簇的路由算法

LEACH 协议是第一个基于簇的路由算法，应用在陆地无线传感器网络中。随着水下无线传感器网络技术的发展，一些学者试图将LEACH协议用在水下。X.Li 等在2007年设计了适用于水下的LEACH-L，该算法中簇头依据剩余能量而定。Dina等在2014年基于VBF设计了CVBF算法[19]。CVBF中，簇内部的通信使用VBF。2015年，Ying Zhang和Hongliang Sun 在K-Means的算法基础上做了改进用于水下传感器通信，选择K个节点时综合考虑了节点密度、节点深度及剩余能量值，同时，该算法将主簇头和辅助簇头结合，主簇头负责收集簇内节点收集的信息，辅助簇头将主簇头的信息交付给sink 节点。

基于簇的路由算法最大的问题在于簇首与成员节点之间的能量均衡，即使一些学者给出了一些解决思路，但仍然没有完全解决能量均衡问题。

三、结束语

本文主要介绍了水下无线传感器网络的结构及特点，总结了目前存在的水下无线传感器网络路由算法的种类及各类算法的优缺点。在以后的研究过程，可以根据本文总结的各类算法的特点，结合实际应用，设计专门适用于水下无线传感器网络的、有效的路由算法。

参  考  文  献

[1] Ismail N ， Mohamad M M . An Evaluation of Performance of Location-Based and Location-Free Routing Protocols in Underwater Sensor Networks[M]. 2020.

[2] Yan H， Shi Z J， Cui J H. DBR： Depth-Based Routing for Underwater Sensor Networks[J]. Lecture Notes in Computer Science， 2008， 4982：72-86.

[3] Wang H， Wang S， Bu R， et al. A Novel Cross-Layer Routing Protocol Based on Network Coding for Underwater Sensor Networks[J]. Sensors， 2017， 17（8）.

[4] Li M ， Du X ， Peng C . RSHSC-routing algorithm based on simplified harmony search and coding for UWSNs[J]. Journal of Sensors， 2018， 2018（1）：1-13.

[5] Li M ， Du X ， Liu X ， et al. Shortest Path Routing Protocol Based on the Vertical Angle for Underwater Acoustic Networks[J]. Journal of Sensors， 2019， 2019（1， article no. 149）：1-14.

[6] 邵阳. 水声传感器网络路由协议HHVBF的改进研究[D]. 天津大学， 2015.

[7] Hwang D， Kim D. DFR： Directional flooding-based routing protocol for underwater sensor networks[C]//Oceans. IEEE， 2008：1-7.

[8] Wahid A ， Lee S ， Jeong H J ， et al. EEDBR： Energy-Efficient Depth-Based Routing Protocol for Underwater Wireless Sensor Networks[J]. 2011.

[9] Jafri M R， Ahmed S， Javaid N， et al. iAMCTD： Improved Adaptive Mobility of Courier Nodes in Threshold-Optimized DBR Protocol for Underwater Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks， 2014， 2014（3）：259-273.

[10] Paley D A， Zhang F， Leonard N E. Cooperative Control for Ocean Sampling： The Glider Coordinated Control System[J]. IEEE Transactions on Control Systems Technology， 2008， 16（4）：735-744.

[11] Yoon S， Azad A K， Oh H， et al. AURP： An AUV-Aided Underwater Routing Protocol for Underwater Acoustic Sensor Networks[J]. Sensors， 2012， 12（2）：1827-1845.

[12] Ilyas N， Alghamdi T A， Farooq M N， et al. AEDG： AUV-aided Efficient Data Gathering Routing Protocol for Underwater Wireless Sensor Networks[C]// International Conference on Ambient Systems， Networks and Technologies. 2015：568-575.

[13] Maqsood H， Javaid N， Yahya A， et al. MobiL-AUV： AUV-Aided Localization Scheme for Underwater Wireless Sensor Networks[C]// International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing. IEEE， 2016：170-175.

[14] Fan X， Song Y. Improvement on LEACH Protocol of Wireless Sensor Network[C]// International Conference on Sensor Technologies & Applications. 2007.