一种基于能量均衡的水声通信网混合树路由算法

谭盛彪　彭凌峰

摘 要：水声通信网在军事、能源、自然灾害预防和处理等方面均具有巨大的应用潜力。针对当前水声通信网按需路由算法存在网络开销大、能量不均衡的问题，提出了旨在改善网络整体性能的HTREB算法。通过采用洪泛抑制与优先使用剩余能量均方差较大的节点进行路由查找，来减少控制分组的转发，并均衡节点能量。基于Opnet软件进行了仿真。结果表明，与现有按需路由算法相比，HTREB算法降低了网络开销8.08% ～ 29.32%、端到端平均能耗4.70% ～ 19.86%、平均端到端延时30.58% ～ 71.63%，延长了网络生存期29.61%以上。因此，HTREB算法明显改善了系统的整体性能。

关键词：水声通信网；路由算法；网络开销；能量均衡；链路权值

中图分类号：TN929.3，TP393 文献标识码：A 文章编号：2095-2163（2015）01-

Abstract： UACN have great application potential in military， energy source， prevention and treatment of natural disasters. The current on-demand routing algorithms have some problems such as high network overhead and unbalanced energy consumption. To solve these problems， HTREB algorithm is suggested to improve the total performance of the networks. Based on the flooding suppression， nodes with more residual energy is preferred to find the routing， and then to reduce forwarding of controlled packets and to balance the energy consumption between nodes. The algorithm is simulated based on the software Opnet. Results show that 8.08% ～ 29.32% of network overhead， 4.70% ～ 19.86% of average end-to-end energy consumption， 30.58% ～ 71.63% of the average end-to-end delay are reduced， compared to the current on-demand routing algorithms. Furthermore， the network lifetime is prolonged by at least 29.61%. Therefore， the total performance of the system is evidently improved through our algorithm.

Key words： UACN； Hybrid-tree Routing Algorithm； Network Overhead； Energy Balance； Link Weight

0 引 言

水声通信网（UACN）是在一定水下区域内，通过固定或移动传感器节点获取水下信息，并对节点进行声学通信和组网，再以无线形式将信息传送到岸上控制中心的智能网络[1-2]。这是当前唯一可在水下进行远程信息传输的通信形式，且在军事、环境、能源、自然灾害防治等方面均已表现出良好的应用潜力，因此受到了普遍重视与高度关注[3]。同时，又随着物理层MIMO技术的日益成熟，近年来的水声网络也相应获得了长足的进步和可观的发展 [4-8]。

如今，UACN主要采用按需路由算法及其相应的改进算法。具体来说，文献[9]提出了无线自组网按需距离矢量（AODV）路由算法。该算法使用目的序列号来防止路由死循环。但是，AODV通过采用洪泛寻路和HELLO消息来维护路由，却造成了过多的控制开销。同时，还有文献[10]结合AODV算法和地理位置路由算法，提出了一种定向搜索（DSAODV）路由算法。该算法利用地理位置信息约束请求分组RREQ查找的范围，使得RREQ只在最优的路径方向上传播，从而减少了网络拥塞和路由开销，并提高了网络吞吐量。但是，DSAODV算法通过节点的位置信息和网络节点疏密来设定和计算转发角度，则需要水下定位技术的支持，因此限制了其应用。上述算法在广播寻路分组RREQ的过程中均使用了洪泛操作，导致了冗余开销。更重要的是，这些算法在建立路由时并未考虑节点能量的均衡，这就明显影响了算法的效率和网络的寿命。此外，文献[11]则提出了一种基于均衡网络业务的拓扑优化控制路由算法，综合考虑了节点的剩余能量、网络业务量和边缘路径条件，从而降低了节点的能量消耗，避免了网络节点过早死亡，进一步提升了网络吞吐量，而且也延长了网络寿命。但是，该算法选择剩余能量较多的节点来转发数据，而未考虑网络的平均剩余能量，因此上加重了某些节点的负载量，容易造成网络拥塞。基于此，又有文献[12]提出一种按需多播树路由算法（MAODV），可以支持各种密切协作的应用业务，有效节省了带宽资源，且对于每一个数据分组均有着更好的整体控制和传输能力。但是，MAODV对于频繁变化的网络拓扑结构，其分组投递率将会下降；同时，节点通过全网广播加入多播树，也随即增加了网络开销。综合以上分析，本文拟提出旨在改善网络整体性能的一种基于能量均衡的混合树路由（HTREB）算法。通过建立混合树网络拓扑图，采用洪泛抑制，综合考虑平均剩余能量（优先使用剩余能量均方差较大的节点）来进行路由查找，由此而减少控制分组的转发，并均衡节点能量，以最终获得网络整体性能的提升。

1 网络模型

将水声网络抽象为数学模型：G=（V，L）有向图，其中，V表示所有节点的集合，且V={S}∪Vm；S表示水面网关Sink节点，Vm表示所有水声传感节点的集合，；所有无线水声对称双向传输链路的集合L={l1，l2，···，ln}，ln表示网络中第n条链路；具体地，链路的代价可以是链路长度（跳数）、数据传输的时延花费等。

1.1 能量模型

本文能量消耗模型[14]为：当节点A向与之相距的节点B发送k bit的信息时，A消耗的能量由两部分组成，分别是：发射电路损耗和功率放大损耗。即：

式中，表示节点发送k bit信息的发射电路损耗，表示功率放大损耗的距离阈值，则表示节点间的通信距离。若<，功率放大损耗以自由空间模型进行计算；若≥，则需依据多径衰减模型相应计算。另外，和分别表示自由空间模型、多径衰减模型功率放大器的能耗因子。而且，节点接收k bit信息所消耗能量为：

1.2 问题描述

网络中信息的发送、转发和接收均需要消耗节点的能量，因此，UACN网络路由算法将遵循如下准则来进行能量优化：减少不必要的开销，降低节点的能量消耗；均衡网络的能量消耗，避免部分节点过早死亡。但是，现有的UACN网络按需路由算法却存在两个问题，具体分析如下：

（1） 源节点广播RREQ以及中间节点转发无效RREQ，产生了大量冗余的RREQ信息，而这些冗余RREQ信息的收发增加了网络开销，进而增大了k值，就造成了节点的能耗加剧。

（2） 数据传送选路时没有考虑节点的剩余能量均方差因素。若当前节点没有足够的剩余能量，而仍承担转发数据的任务，就会因过度使用而造成电池提前耗尽，由此导致路径的断裂，影响网络通信。

1.3 能量均衡的混合树路由算法设计

针对UACN网络现有的按需路由算法在寻路开销和节点能耗等方面的不足，本文提出一种基于能量均衡的水声通信网混合树路由算法—HTREB。HTREB算法采用洪泛抑制的优化路由建立方式，减少部分控制分组的转发；而且使用节点距离和剩余能量均方差作为选路标准，进而达到能耗均衡效果。

1.3.1 HTREB算法描述

HTREB算法包含邻节点信息的收集与反馈，路由建立及数据转发两个阶段。下面给出每一阶段的具体实现过程。

（1） 邻节点信息的收集与反馈阶段

信息收集：节点定期向一跳范围内的节点发送HELLO分组，接收到HELLO分组的邻居节点获知其可视邻居区内节点的网络地址等信息。

② 信息反馈：节点向其父节点及节点与邻居节点深度最大的公共父节点反馈自己收集的可视邻居信息。

（2） 路由建立阶段

步骤1：当源节点有数据发送时，会首先查询路由表中是否缓存了到目的节点的有效路由。如果是，则使用此路由发送数据分组。否则，将转为步骤2，即源节点开始路由查找过程。

步骤2：源节点欲加入到多播组，则需查找多播路由表中是否可获得父节点信息。如果获得，则选择下一跳单播RREQ到父节点，否则，即向邻居节点及所在分支树的邻居节点的子节点多播RREQ请求分组。

步骤3：中间节点收到RREQ分组，执行以下过程：

① 判断该RREQ的序列号是否大于自己路由项中的序列号或者RREQ的跳数是否小于TTL（Time To Live）阈值。如果是，执行②，否则删除该RREQ分组。

② 若当前节点是源节点的邻树枝节点，则转步骤2处理该RREQ；若当前节点是源节点的子节点，则判断当前节点及其子节点是否有邻树枝节点。如果有，则向其多播RREQ，否则，删除该请求；若当前节点是目的节点的父节点或子节点，通过计算判断自己到目的节点的跳数加上RREQ中的TTL值是否小于TTL阈值。若是，就沿着树路由路径转发该请求直到目的节点，若不是，将删除该请求。

③ 若当前节点是源节点的父节点，但不是源节点和目的节点的公共父节点，也不是源节点和目的节点的最大深度公共父节点的子节点，则转步骤2处理该请求；而若当前节点是源节点和目的节点的最大深度公共父节点的子节点，即需判断当前节点是否有邻树枝节点或与源节点不同树枝的子节点。若为有，则向其多播该请求，否则，就删除该请求。

步骤4：源节点发送的RREQ请求到达目的节点时，如果RREQ历经的跳数未超过TTL阈值，则单播路由回复RREP至源节点。中间节点收到RREP后，更新RREP中相应字段的值，而后沿RREQ传播时建立的反向路径发送RREP给邻节点。源节点收到RREP后，存储链路权值、跳数等信息，完成正向路径的建立。

1.3.2 路由度量新指标—链路权值

在HTREB算法中，提出一种新的路由度量指标—链路权值（Link Weight），用于在节点收到不同的路由响应时，优先选择距离更远、剩余能量均方差更大的节点参与路径建立。链路权值定义为：

式中，k1和k2是可变参数，k1+k2=1；di表示节点i与同树枝源节点之间的距离，dj表示节点j与不同树枝源节点之间的距离（0

2 仿真与分析

2.1仿真统计量

仿真统计量涉及网络开销、端到端平均能耗、网络生存期、数据分组平均端到端延时和分组投递率。其中，网络开销是网络中所有节点发送和转发的控制分组比特数和到达目的节点的数据分组比特数与目的节点成功接收的数据分组比特数的比值。端到端平均能耗将具体定义为网络中单个节点能耗与所有节点平均能耗的均方差值。而且，网络生存期即是网络的运行时间。当死亡节点的数量大于等于网络总节点数30%时，判定网络运行截止。在此，数据分组平均端到端延时就是网络中所有数据分组从源节点到达目的节点所消耗的时间与成功接收数据分组个数的比值。分组投递率则指网络中目的节点成功接收的数据分组数与源节点发送数据分组数的比值。

2.2 仿真参数设置

仿真实验使用OPNET 14.5作为软件平台，主要仿真参数设置如表1所示。本文采用由一个网关节点和若干个信息采集节点组成的UACN网络模型，网关节点在场景中心，传感器节点随机均匀分布在网关周围。水下节点物理层采用文献[13]设置的水声信道模型，定义节点的能量都是有限且均为10 J初始能量；当节点剩余能量低于0.5 J时，判定节点死亡；当网络中死亡节点数高于30%时，网络生存期结束。

2.3 仿真结果及分析

图1为网络开销比较，与AODV算法相比，HTREB算法能够有效减少网络开销8.08%（50节点数）～ 29.32%（110节点数）；与MAODV算法相比，HTREB算法减少网络开销0.01%（50节点数）～ 20.76%（110节点数）。主要原因在于，

AODV算法节点存储的路由信息较少，通常使用广播RREQ的方式来进行路由查找以及周期地发送HELLO控制分组来维护路由，如此将导致网络开销过大；MAODV算法和HTREB算法通过发送RREQ路由请求或者查找邻居表来建立数据传输的多播树，避免了全网洪泛查询，同时又减少了控制分组的转发次数；且HTREB算法在寻路过程中利用路由跳数抑制RREQ的洪泛深度，通过相邻树枝的节点信息找到优化路径，减少RREQ的转发，从而进一步降低了网络开销，获得了更高效率。

图2为端到端平均能耗比较。与AODV和MAODV算法相比，HTREB算法降低端到端平均能耗分别为4.70%（50节点数）～ 19.86%（140节点数），2.50%（50节点数）～ 15.53%（140节点数），说明HTREB算法节点的能耗偏离网络平均能耗的程度更小，能量消耗也更为均衡。主要原因在于，AODV算法中，部分中间节点转发数据分组较多，节点能耗偏大，而某些通信量较小的节点，能量消耗将会偏小。因而导致网络中节点能耗速率不均衡，端到端平均能耗较大；MAODV算法则通过建立的树路由限制RREQ的洪泛，减少了网络中冗余的RREQ转发，但在寻路时因未考虑节点当前剩余能量，而过度使用剩余能量均方差较小的节点转发数据分组，另有些剩余能量均方差较大的节点却较少地转发数据分组，由此导致网络中节点能耗不均衡；相应地，HTREB算法即使用链路权值较小的节点作为下一跳，减轻了距离近的“热区”节点的数据分组转发任务，且使其能量消耗速率得到缓解，这就避免了剩余能量均方差较小的节点过早死亡，从而均衡了网络节点能耗；同时，又采用了短跳代替长跳传送分组，节点耗能减少，端到端平均能耗也随即更小。

网络生存期的仿真结果如图3所示。图3显示，与AODV和MAODV算法相比，HTREB算法至少能够延长网络生存期分别为29.61%（20节点数），11.52%（20节点数）。这是因为在AODV算法中，数据分组经常沿着某一条路径到达目的节点，造成部分节点承担较大的负荷量，消耗能量更多，节点死亡就越快；而MAODV算法则广播RREQ分组寻找最短路径生成多播树，并沿树路径发送数据分组。但是MAODV在建路时却未考虑节点当前剩余能量，若剩余能量均方差小的节点继续转发数据，则会加速节点的死亡，甚至网络拓扑的分裂；另外的HTREB算法源节点比较不同路径的链路权值，选择距离远、剩余能量均方差较大的节点，即权值较小的路径建立路由，因而延缓了负荷重的节点死亡，使网络中节点能耗更佳均衡，藉此延长了网络生存期。

数据分组平均端到端延时的仿真结果如图4所示。在图4中，与AODV算法相比，HTREB算法能够有效降低分组平均端到端延时30.58%（110节点数）～ 71.63%（20节点数）；与MAODV算法相比，HTREB算法分组平均端到端延时降低1.47%（50节点数）～ 16.75%（20节点数）。主要原因在于，当一条链路断裂，AODV算法需要重新发送RREQ查找路由，且数据分组总是沿着单播路由进行转发、直至到达目的节点，当网络通信业务增大时，容易引起信道冲突，并增加延时；MAODV算法则是通过RREQ分组寻路建立多播树，限制了RREQ的转发次数，因而利于数据分组在树路由节点上的快速传送，并使得时延获得了有效降低；而HTREB算法却借助相邻树枝节点信息进行RREQ寻路，缩短了路由建立时间。且HTREB优先选择链路权值较小的节点进行分组传送，如此既平均了业务流量，又避免了网络拥塞，进而使得分组平均端到端时延进一步减少。

3 结束语

本文提出的HTREB路由算法，采用树路由的单、多播代替广播，限制RREQ分组的转发，并利用邻居节点信息建立路由，在一定程度上减少了网络开销；同时，综合节点的距离和剩余能量均方差两种因素形成链路权值，且将其引入路由参照标准，由此实现节点能量均衡。具体到理论分析及仿真结果即都表明，与AODV和MAODV算法相比较而言，HTREB算法在网络开销，端到端平均能耗，网络生存期和平均端到端延时等方面的性能均已得到了有效改善，因而获得了较为理想的现实研究效果。

参考文献：

[1]AKYILDIZ I F， POMPILI D， MELODIA T. Challenges for efficient communication in underwater acoustic sensor networks[J]. ACM Sigbed Review， 2004， 1（2）： 3-8.

[2]OTHMAN A K， WAN Z A W A， ZEN H， et al. Performance evaluation for network set up and nodes discovery protocol in underwater grid topology networks[C]//Information and Telecommunication Technologies （APSITT）， Kuching， 2010.Piscataway： IEEE， 2010： 1-6.

[3]CUI J H， KONG J， GERLA M， et al. The challenges of building mobile underwater wireless networks for aquatic applications[J]. IEEE Network， 2006， 20（3）： 12-18.

[4]HOU J Y. Mobile Ad Hoc Network of simulation framework based on OPNET[C]//Computer， Mechatronics， Control and Electronic Engineering （CMCE）， Changchun， 2010. Piscataway： IEEE， 2010： 132-135.

[5]REHAN K， QIAO G. A survey of underwater acoustic communication and networking techniques[J]. Research Journal of Applied Sciences， 2013， 5（3）： 778-789.

[6]WANG P， ZHANG X. Energy-efficient relay selection for QoS provisioning in MIMO-based underwater acoustic cooperative wireless sensor networks[C]//Information Sciences and Systems （CISS）， Baltimore， 2013. Washington： IEEE， 2013： 1-6.

[7]REAL G， BEAUJEAN P P， BOUVET P J. MIMO underwater acoustic communications in ports and shallow waters at very high frequency[J]. Journal of Sensor and Actuator Networks， 2013， 2（4）， 700-716.

[8]LI S， WANG W， ZHANG J. Efficient deployment surface area for underwater wireless sensor networks[C]//Cloud Computing and Intelligent Systems （CCIS）， Hangzhou， 2012. Washington： IEEE， 2012： 1083-1086.

[9]GOMEZ C， CATALAN M， MANTECON X， et al. Evaluating performance of real ad-hoc networks using AODV with hello message mechanism for maintaining local connectivity[C]//Personal， Indoor and Mobile Radio Communications （PIMRC）， Berlin， 2005. Piscataway： IEEE， 2005： 1327-1331.

[10]刘旬， 李宇， 张春华， 等. 水声通信网络定向搜索 AODV 协议研究[J]. 应用声学， 2010， 29（6）： 458-465.

[11]FU W， LI D， CHEN J， et al. Topology optimization control with balanced energy and load in underwater Acoustic Sensor Networks[J]. International Journal on Smart Sensing & Intelligent Systems， 2011， 4（1）： 138-159.

[12]SHURDI O， MIHO R， KAMO B， et al. Performance analysis of multicast routing protocols MAODV， ODMRP and ADMR for MANETs[C]//Network-Based Information Systems （NBIS）， Tirana， 2011. Piscataway： IEEE， 2011： 596-601.

[13]WANG C， FANG Y. Channel model simulation for underwater acoustic sensor networks using OPNET[C]//Communication Technology （ICCT）， Nanjing， 2010. Piscataway： IEEE， 2010： 141-144.

[14]LIU Z X， ZHENG Q C， XUE L， et al. Energy and node degree synthesized clustering algorithm for Wireless Sensor Networks[J]. Journal of Software， 2009， 20（sup）： 250-256.