面向能量和链路优化的水声移动传感器网络路由协议设计

葛志远,张森林,刘妹琴

(1.浙江大学电气工程学院,浙江杭州 310027;2.浙江大学工业控制技术国家重点实验室,浙江杭州 310027)

1 引言

海洋面积广阔、资源丰富.近年来,随着水声通信技术的发展,水声移动传感器网络因其广泛的应用而受到越来越多的关注,如海洋数据收集、资源和污染监测、水下环境探测、辅助导航和战术监视等海洋资源探索监测和安全防护领域[1-3].同时,水下环境的复杂性和多变性、资源有限性等为水声移动传感器网络协议设计与发展带来了巨大的挑战[4-5].

水声移动传感器网络(mobile underwater acoustic sensor network,MUASN)主要由多个水声通信传感器节点构成,单个水声通信传感器节点都承载了数据采集及传输的功能.水声移动传感器网络的特点主要有:1)传播时延高且不定.声波在水中的传播速度约为1500 m/s,与无线电波的传输速率相比低5个数量级[6],因此,水声移动传感器网络节点之间的水声通信存在较大的传播时延.且水声通信时受海水物理特性,如温度、压强等的影响,声波受到的传输衰减不同,存在时空不定性,因此,声波通信传播时延具有不确定性.2)可用带宽窄.声波传输衰减受传输距离和声波频率的共同限制.同时,水下环境中低中频噪声普遍存在,极大影响了声波传输的准确性.因此,MUASN的可用带宽窄,典型水声通信节点的工作频率在几赫兹到几十千赫兹之间.3)传输不稳定且误码率高.受声源节点和接收端节点的相对运动造成的多普勒效应及海底海面反射产生的多条传播路径的多径效应影响,声波信号会产生畸变并受到严重的码间干扰[7],造成水声通信时传输不稳定性,进而导致较高的误码率.4)能量受限.受水下恶劣环境影响,水下传感器及水声通信节点一般采用一次性电池供电且电池难以更换,若节点电池能量不足以完成收发数据,将导致节点宕机脱离网络,使得MUASN形成网络黑洞,进而导致网络瘫痪[8].

路由作为MUASN中在源节点与接收节点中选择合适路径转发数据包并进行路径维护的一个基本问题,将直接影响到水声通信的稳定性和能量利用的高效性和均衡性,进而影响MUASN的各项性能指标.对MUASN来说,水声移动传感器网络易受到水下环境噪音影响的特性、节点随机移动及其带来的多普勒效应影响,导致路由路径发生断裂,进而需进行路由修复甚至再次路由发现,进一步占用大量带宽,消耗巨额能量,造成网络拥堵,使得网络各项性能指标降低,如吞吐量下降、时延增大、丢包率增大和网络生命周期减短等[9-10].因此,在路由选择机制中应充分考虑链路稳定性的影响.而网络路由路径的稳定性往往取决于网络节点之间的相对距离.而且,在MUASN中,电池更换难度高,且频繁更换电池会使得设备维护代价增大,故网络节点在各种状态下及各种状态下的转换,都由有限电量的一次性电池供应.因此,如何避免链路断裂以高效地利用有限能源显得尤为重要.同时,能量的极端利用会导致网络黑洞的形成,影响水声移动传感器网络的正常功能.如AODV协议采用的最小跳数路由选择机制.在水声通信节点收发功率固定的网络中,节点的声波通信范围固定,故最小跳数算法往往选取的路由路径是在所有可用的路由路径中最小跳数路径是总传输功率最低的传输路径.因此,最小跳数算法易造成某一关键位置节点的能量过分消耗,从而脱离网络[11].对于拓扑动态变化的稀疏网络中,节点的移动很难形成节点的交换,一旦网络中的某些关键位置节点过早耗尽能量,形成网络黑洞,节点的移动也很难补足网络黑洞的空缺.因此,MUASN中的路由路径选择机制也应充分考虑水声传感器内部剩余能量的影响.在选择路由路径时通过尽量避免节点剩余能量较少的节点来作为下一跳节点,尽可能最大化延长整个网络的寿命周期.

优化MUASN路由协议,提高有限能量的利用率,加强网络路径稳定性,也成为众多学者研究的重点.在能量均衡方面,文献[12]提出了一种基于节能路径的路由协议,通过在初始能量中减去计算得到的收发和丢失的能量得到节点剩余能量,并通过剩余能量进行路由选择.由于网络节点本身存在能量消耗,因此采用这种方法会导致节点能量误差累加,并不能有效获取路由路径上节点能量的准确信息.文献[13]提出了一种基于能量平衡改进路由协议,该协议将能量成本函数引入路由选择机制中,并采用改进HELLO报文,通过次优多跳路径,有效地延长了整个网络的生命周期.在路由链路稳定方面,文献[14]提出了MDAAODV(mobilityanddirectionawaread-hocondemand distance vector routing protocol)路由协议,该协议在不考虑路由能量和性能的因素下,主要基于节点速度和方向进行路由选择,避免选择高速移动或移动至远处的节点加入路由.这种方式有效地保证了路由路径的稳定,但是并不适用于稀疏的且拓扑变化较快的网络.为了综合考虑能量均衡及路径稳定性,文献[15]采用了能量与移动感知路由,降低了网络稳定性和节点移动的复杂性.该协议主要通过多点中继的选择,保障了高速率地从源节点到目的节点的网络链路连接和网络稳定性.文献[16]根据节点传输信息,采用指数平滑的方式对节点间链路质量进行预测,并通过由节点剩余能量和链路质量决定的节点质量因子选择邻居节点,有效提高节点传输成功率,均衡网络能量.但是由于没有考虑跳数问题,无法达到该链路功耗的相对最优.

本文主要对MUASN中的按需平面距离向量路由协议(ad hoc on-demand distance vector routing,AODV)进行研究,在原协议的基础上引入了存在能量阈值的能量指标和以距离为基准的距离指标,并综合考量了能量指标、距离指标与跳数,对网络路由路径的状态进行综合评估.当节点能量低于能量阈值时,节点将不参与路由协议的路由发现过程.仿真结果表明,该方法有效地提升网络整体的数据量,均衡了水声移动传感器网络各节点的能量消耗,延长了网络的生存周期.

2 协议描述

AODV是一种为快速移动分布式自组网络设计的按需反应式路由协议.当源节点存在通信需求时,源节点以多播形式向网络中的节点发送路由控制帧.中间节点接收到源节点发送的路由控制帧后,判断是否存在到目的节点的路由路径或是否本身是目标节点,根据判断结果返回路由回应或转发路由控制帧.在路由目的节点可达时,建立相应路由路径,若非出现路由路径断裂导致目的节点不可达或路由存在时间超过该路由路径的生存周期的情况,路由路径将一直被设定为可用状态.在该协议中,节点无需记录整个网络的拓扑状态,只需记录与所有目的节点间的路由信息和相邻节点的连通状态.

2.1 场景设定

本文主要以二维动态拓扑的MUASN为研究对象.每个水声通信传感器节点在水下固定区域内随机分布,每个节点存在内置能量电池,其主要设定为:1)每个水声通信传感器节点存在独立的ID号,ID号用于在通信过程中唯一确认发送方和接收方,且每个水声通信机都可以作为主机或路由器使用[17];2)每个水声通信传感器节点都以半双工方式收发数据;3)除了用于与终端连接作为接收节点与数据发送节点外,其余节点在MUASN中的地位相同,都有可能成为中间节点;4)每个水声通信传感器节点初始能量相同;5)每个水声通信传感器节点收发数据的功率为定值,且每个节点设定的接收功率相同,节点的接收功率与文献[18]设定的网络能耗相同;6)若声波功率高于水声通信传感器节点的载波监听接收阈值功率,则该接收节点可正常接收声波信号;7)每个水声通信传感器节点都在设定区域内随机分布并以随机的速度与方向移动;8)水声通信传感器节点的移动速度受限于一定速度范围,且最大速度远小于声波速度,因此忽略声波的多普勒频移影响.

2.2 AODV路由帧

AODV路由协议通过对路由请求帧RREQ、路由应答帧RREP、路由应答帧RREP-ACK、路由错误帧RERR和HELLO链路监测帧这4种路由控制消息帧的协调控制,实现路由路径的发现、链路维护等功能.当源节点不存在达到目的节点的有效路由时,将发出路由请求帧,其中以源节点记录下的目的节点序列号大1作为新的链路请求序列号,避免形成环路.中间节点以自身记录下的相应目的节点序列号是否大于路由请求帧中序列号来判断是否更新自身路由表.RREP应答帧是由目的节点或存在到达目的节点有效路由的中间节点发出的,以便中间节点和源节点建立指向目的节点的前向路由.RREP-ACK帧用于回复RREP帧以确认自身节点收到了发送节点的RREP路由应答帧.当节点路由链路断裂或邻居节点不可达时,节点通过单播、重复单播或广播的形式发送RERR错误帧来进行路由链路的修复.HELLO帧用于发现维护本地节点的相邻节点及其连接状态信息,是一个TTL为1的路由应答帧.其中路由请求帧格式如表1所示.

表1 RREQ路由数据帧格式Table 1 Routing data frame format of RREQ

路由请求帧格式主要包括了类型、标志位、跳数、目的节点的IP地址和节点序列号、源节点的IP地址和节点序列号.RREP应答帧与RREQ请求帧类似.

2.3 路由路径建立过程

AODV路由路径建立过程主要如下:

1)当MUASN中的源节点存在到达网络中某一节点的数据传输需求时,若该节点不存在到目的节点的有效路由,则源节点将产生ID值和源节点序列号加1作为新的序列号的路由请求帧,并洪泛广播至各个邻居节点.源节点若在固定时间内没有接收到相应的路由应答帧,将多次发送路由请求帧,且每次发送时增加TTL,扩大请求帧传输范围.

2)中间节点在收到源节点发送的路由请求帧后,若路由请求帧的序列号大于该中间节点记录的到目的节点的序列号,则将路由请求帧中的信息,如跳数、序列号、源节点IP和序列号等,写入到达相应目的节点的路由表中,建立到源节点IP地址的反向路由,以便在接收到RREP应答帧时使用.否则,表示该路由请求帧中的信息陈旧落后或已经接收到过该路由请求帧,中间节点将丢弃该路由帧信息.若在路由发现时间内重复收到相同信息的路由请求帧,则选择路由请求帧内跳数更少的路由信息,写入到相应目的节点的路由表中.

3)在中间节点建立反向路由后,若该节点为目的节点,则该节点将自身序列号加1作为路由应答帧的序列号,并根据建立的反向路由单播回送跳数为0的路由应答帧以建立正向路由.若节点存在到达目的节点的路由路径,且该路径记录的目的节点序列号有效且大于信宿节点的序列号,该节点将路由表中记录的目的节点序列号作为路由应答帧的序列号,根据反向路由单播跳数为到达目的节点跳数的路由应答帧.否则,该中间节点将更新路由请求帧的跳数,继续洪泛转发路由请求帧.

4)当中间节点接收到路由应答帧时,该节点将路由应答中的信息,如跳数、序列号、目的节点IP和序列号等,写入到以目的节点为目标的路由表中,建立到目的节点IP地址的正向路由.并根据之前建立的反向路由继续单播路由应答帧,直到源节点.

5)若中间节点通过反向路由转发一个可能错误或者为单向的路由应答帧,则该节点将标记标志位以提醒正向路由中该节点上一跳的节点在接收路由应答帧后回复RREP-ACK帧以确认收到路由应答帧.在源节点接收到路由应答帧后,若接收到多个不同路径的路由应答帧,将比较各路由应答帧的跳数,选择其中跳数最小的路径作为发送数据包的路由路径.

图1为AODV路由路径建立过程示意图,在图1中,设定节点1为发送节点,若节点1没有到节点8的路由,且节点1有数据包需要发送至节点8,节点1通过广播路由请求帧到节点2、节点3、节点4中.假设以上3个节点中,只有节点2与节点3在通信范围内,则以上3个节点由于不是目的节点,会继续转发路由请求帧到相邻节点中,其中节点2会继续转发路由请求帧到节点3中,若中间节点都没有到达节点9的路由路径,则路由请求帧会由节点6和节点7分别到达目的节点8,总共可能会建立6条反向路由.根据这6条反向路由,目的节点会单播回复路由应答报文,通过各路径的中间节点到达源节点1.其中6条路径对应跳数分别为3,4,5.源节点将选择最短路径,即跳数为3的路径,作为发送数据包的路径.

图1 AODV路由路径建立过程Fig.1 Establishment of AODV route path

3 改进AODV协议

3.1 链路优化策略

对于MUASN而言,路由路径的平均长度与路由的稳定性紧密相连.常规AODV路由协议通常采用最小跳数作为选择路由路径的依据,而这常常代表着该路由路径的平均长度最长,故路由路径上相邻节点可能处于或靠近节点通信范围临界点处.当两个节点的相对距离接近节点的通信半径时,节点随机移动产生的微小位移都可能影响路由链路,导致其发生断裂.因此,跳数最小路由路径选择机制很可能会导致选择路径稳定性较差的路由路径,进而造成网络性能下降.由于路由路径稳定性与相邻节点的相对距离有直接关系,采用相邻节点的相对距离定量表示相邻节点之间的传输稳定性.本文利用路由路径质量指标(link quality index,LQI)来反应相邻节点之间数据传输的稳定性,其值越大则该相邻节点之间的传输稳定性越高.由节点相对距离决定的路由路径指标如下:

其中:Dij表示相邻节点之间的欧式距离;R表示节点的最大通信距离半径.

在式(1)中,相邻节点之间的相对距离(用欧式距离表示)越短,路由路径的质量指标值越高,稳定性越强.当相邻节点的欧式距离大于最大通信距离半径时,说明相邻节点数据传输不可达,相应路径稳定性为0.为表示整条路由路径的稳定性,将对该路由路径上每一跳的路径质量指标进行叠加.

3.2 能量优化策略

在MUASN中,根据路由路径选择机制的不同,可以将路由的能量优化改进策略分为两种.第1种是根据每条路径所消耗的能量大小选择路由.在不考虑数据包重传的情况下,这种算法以路由路径花费的传输功率为选择标准,在所有可用路由路径中,选择传输能耗最低的一条作为传输路径.第2种是根据网络生存周期选择路由.这种算法主要以MUASN中某一时刻节点的剩余能量为依据,在选择路由路径时选择相对能量较多的节点为下一跳节点,从而避免处于关键位置的节点过早耗尽能量,延长网络的生存时间.本文主要以上述两种能量优化策略并存的方式来研究路由协议的能量优化.

对于单个节点而言,本文引入了能量阈值u来表示该节点的能量状态,当节点的剩余能量低于能量阈值时,该节点将不参与路由发现过程,即不会加入网络中任何一条新建立的路由路径中,只保持该节点路由表中的已有路由路径进行数据转发.将节点剩余能量高于能量阈值的能量称为能量裕度,能量裕度与总能量高于能量阈值的能量之比为能量裕度值,其值越高,则该节点的能量越充裕.其表达式为

其中:E表示能量裕度值;u表示能量阈值;Eres表示该节点当前能量值;Etoal表示该节点的能量总量.为表示整条路由的能量状态,将对该路由路径上除源节点外的每一个节点的能量状态进行叠加.

3.3 基于能量和链路的改进策略

为了综合考虑路由路径稳定与网络能量均衡问题并平衡能量与路径稳定两个因素的比重问题,给路径质量指标LQI和反应节点能量状态的能量裕度值E分配了不同的权值.将不同权值下节点路径质量指标和能量裕度值构成的值称为单跳支持值EL,其表达式如下:

其中β和α值分别是路径质量指标LQI和能量裕度值E的权重.

将路由上的每一跳形成的支持值累积得到路径支持值ELN.为了考虑在能量充裕且链路较短时的整体链路的能量消耗,即根据传输功率选择路由机制,引入了跳数限制.其表达式如下:

其中:ELH为综合考虑了能量裕度值、链路稳定和跳数的路由支持值;HOP为该路由路径的跳数.路由支持值越大,则表示该路由路径更容易被选择.

在动态拓扑的稀疏MUASN中,对于短路由而言,由于源节点与目的节点可以在小跳数内实现双向链,源节点因路由断裂产生的洪泛现象相较于长路由来说不明显,所以优先考虑短路由下的路由传输功率问题.如式(4)所示,对于跳数较短的路由路径来说,当跳数增加一跳时,将会显著降低路由支持值ELH,若跳数相同时,相对剩余能量多且链路较为稳定的路由链路将决定路由支持值ELH的大小.由于稀疏网络中相邻节点的相对方向改变不大,链路断裂的主要原因在于相邻节点的欧氏距离大于节点通信距离半径.而长路由的断裂会导致以源节点为中心的大面积网络信息洪泛.因此,对长路由而言,选择相对剩余能量较多且链路较为稳定的路由更为重要.在上式中:若在跳数值较高时增加一跳,对于路由支持值ELH的影响并不明显,而能量裕度值和路径质量指标将主要决定路由支持值.

改进后,节点在接收RREQ的流程如图2所示.改进路由协议路径建立的简要过程如下:

图2 节点接收RREQ流程图Fig.2 Flow diagram of receivng RREQ

1)MUASN中源节点想发送数据包给没有有效路由的目的节点,将广播自身序列号加一的路由请求帧RREQ给各邻居节点来寻找目的节点.

2)中间节点在收到源节点发出的RREQ消息后,首先通过hello消息维护的邻居节点距离信息计算出上一跳节点与自身节点的路径质量指标,通过自身节点的剩余能量计算出自身节点的能量裕度值,并加权结合两个指标后与存于RREQ消息中的从源节点到上一跳节点的路径支持值相加,得到从源节点到该节点的路径支持值.若RREQ序列号大于中间节点到目的节点的序列号或者序列号相等但路径支持值更大时,记录下RREQ中信息并建立反向路由.

3)建立反向路由后,若中间节点为目的节点或中间节点有到目的节点的路由路径时,以传统AODV协议改变的序列号写入路由应答帧RREP中,并将该节点到目的节点的路由支持值转换为路径支持值写入RREP中.

4)若中间节点不是源节点,则当中间节点接收到RREP消息时,将自身节点的能量裕度值与和发送RREP消息节点间的路径质量指标值加权到RREP消息中的路径支持值中.

5)当源节点接收到目的节点发送的RREP消息时,将RREP消息中的路径支持值与跳数根据上述公式计算出路由支持值,并从中选择路由支持值最大的路由路径作为发送数据包的路由路径.改进后RREQ路由帧格式如表2所示.

表2 改进后RREQ数据帧格式Table 2 Improved protocol RREQ data frame format

路由请求帧格式主要包括了类型、标志位、跳数、目的节点的IP地址和节点序列号、源节点的IP地址、节点序列号、请求帧生存时间以及路由支持值.关于RREP应答帧和RRER错误帧的改动与RREQ请求帧类似.

4 仿真实验及结果分析

本节在NS2网络仿真平台上,面向各节点随机移动的MUASN运动场景,对AODV路由和基于能量与链路优化策略的改进AODV路由协议进行对比仿真分析.本文将从网络平均剩余能量和同一时刻下节点的宕机数量两个方面对常规AODV协议[16]及改进协议对比分析.其中仿真的硬件环境为Inter Core I5-8400 CPU 2.8 GHz,编程环境包括ns 2.35平台、python 3.5.2、C++等.

4.1 实验场景及参数设置

将由50个传感器节点组成的水声移动传感器网络置于600×600的正方形海域范围内.网络中的50个节点在区域随机分布并向随机方向以一定速度范围内的随机速度进行移动.每个节点的性能参数相同,其中初始能量均为200 J,发送功率为2 w,接收功率为0.75 w,待机功率为8 mw.每个发送节点发送的每个数据包长度为50个字节,以固定波特率的方式进行发送,仿真时间为1000 s.

4.2 节点宕机数量

本节通过ns2中的 flowmonitor对仿真过程中产生的数据及节点状态的变换情况进行记录.在实验过程中,当水声通信机节点的能量不能维持1 s内的数据接收时,则认为该节点已宕机并脱离网络,节点宕机数量随时间的变化如图3所示.其中:图中横坐标为仿真时间,纵坐标为节点宕机数量.

图3 网络剩余节点数量Fig.3 Number of remaining nodes on the network

从图3网络剩余节点的变化中可以明显看出,在大多数的时间段,改进后协议的网络节点宕机数量都低于常规AODV协议.在仿真初期,改进AODV路由协议由于受到能量均衡路由选择机制的影响,网络中第一个宕机节点出现的时间会慢于常规AODV路由协议.在网络有节点宕机后,改进路由协议中,处于关键位置的网络节点宕机数量下降速率会比常规AODV路由协议稍缓,而在接收接节点宕机后,网络节点宕机数量仍少于常规AODV路由协议.具体来看,AODV路由的首个网络节点宕机时间为250 s左右,仿真结束后,网络中共有10个节点死亡;而基于稳定传输和能量均衡的改进路由协议首次出现网络节点宕机时间为432 s左右,比常规AODV路由协议出现宕机节点的时间晚了约70%,且仿真结束后,网络中宕机节点只有6个.在通信网络中,节点ID为20的节点作为接收节点,在传统协议中宕机时间为261 s,而在改进协议中宕机时间为886 s,极大延缓了接收节点的宕机时间.显然,改进协议在首个节点宕机时间和网络中存活节点数量中的表现都优于AODV路由协议.

4.3 节点平均剩余能量

为了进一步定量描述网络中的能量,本节采用了网络中节点的平均剩余能量对其进行定量表示.每隔100 s对流量监控器中记录下的各节点能量进行叠加并除以节点数,求得每百秒下的节点平均剩余能量.其仿真结果如图4所示,其中:横坐标为仿真时间,纵坐标为节点平均剩余能量.

图4 节点平均剩余能量Fig.4 Average residual energy of nodes

如图4所示,改进后,网络中节点的平均剩余能量在仿真过程中均高于常规AODV的节点平均剩余能量.在仿真初期,由于各节点的初始能量相同,改进后的路由协议在短路由上主要受到跳数的影响,与AODV协议建立的路由路径大致相同,而在长路由上增加了链路影响,可能会导致路由链路的增长.因此,在网络路由初期,可能会出现改进协议消耗能量更多的情况.但随着路由链路的断裂导致重新进行路由修复和路由发现后,这种情况得以缓解并消除.从仿真结果来看,由于AODV协议路由链路断裂比改进协议更加频繁,所以AODV路由需花费大量网络能量在路由路径的重新建立上,因此仿真前期,网络中节点平均剩余能量之差逐渐递增.当AODV协议中接收节点宕机后,改进协议中的接收节点仍在工作,有大量的数据传输能量消耗,因此网络中平均剩余能量之差减小.而当改进协议中的接收节点宕机后,网络中各节点的能量消耗都主要为节点待机及节点路由发现所消耗的能量,节点平均剩余能量减少增量相差不大.当仿真结束后,改进协议下的网络节点平均剩余能量仍高于常规AODV协议.且通过流量监控器对仿真网络中的接收节点接收数据包监测,改进协议后,接收节点成功接收了29826个数据包,比常规AODV协议多959个.

5 总结

本文针对动态拓扑的稀疏MUASN的能耗不均衡且链路不稳定造成的网络路由路径断裂问题,深入研究了路由路径建立过程.通过在表示节点能量状态中引入了能量阈值与能量裕度值算法,定量表示节点在某一时刻的能量状态,并根据路由中各个节点的能量状态进一步改进路由路径选择机制,延长了网络的生存周期.为了缓解节点移动时带来的网络路由路径断裂问题,在路由路径选择机制中增添了根据相邻节点的欧氏距离而定量表示的路由路径质量指标.在路径选择机制中,为在较短路由或可用路由路径状态相似的情况下选择耗能少的路径,引入了传输功率最小算法.实验结果表明,基于能量与路由路径的改进策略能有效提升网络整体数据量和均衡网络节点能量,并延长网络的寿命.本文基于能量与链路改进策略主要目的在于提高链路稳定性并均衡网络各节点中的能量,虽然在一定程度上提高了网络整体数据量,但在网络吞吐量上仍存在提升空间.