水下传感器网络中基于空间网格区域划分的贪婪路由方法

摘要

本发明涉及一种水下传感器网络中基于空间网格区域划分的贪婪路由方法，包括三个阶段：(1)选择下一跳区域阶段：将水下三维网络监测区域视为一个立方体，等量划分为若干个小正方体区域，源节点根据自身位置和信息最终所要被传输到达的目的节点的位置信息，选择一个最优转发区域；(2)目标区域内选择节点进行贪婪转发阶段：考虑节点剩余能量、占空比睡眠机制以及可信度等衡量标准选择下一跳醒着的节点，保证整个网络连通；(3)优化路径阶段：发现路径环时，通过引入基于标签的优化策略来消除路径环，达到选择最优路径的目的。本发明考虑了在水下传感器网络中路由区域的划分和节点的可信度，增加了路由的可靠性和可扩展性，提高了网络的性能。

说明书

技术领域

本发明属于水下三维无线传感器网络领域，具体地本发明涉及水下传感器网络中基于空间网格区域划分的贪婪路由方法，寻找可靠的多条路径，并选择最优路径。 

背景技术

目前，随着开发海洋的进程进一步加快，水下传感器网络成为一个新的研究热点，它在海洋环境采样、环境监测、灾害预警、辅助航行和战术分布监视中发挥了越来越大的作用。目前，学者们提出很多关于水下的路由算法，但是大多数都是单路径且没有考虑占空比机制以及节点可信度。 

目前针对水下三维无线传感区域网络路由的相关研究如下： 

Peng Xie等人在2006年的《Networking2006.Networking Technologies,Services,and Protocols;Performance of Computer and Communication Networks;Mobile and Wireless Communications Systems》上发表文章“VBF:Vector-Based Forwarding Protocol for Underwater Sensor Networks”，文中提出一种基于向量转发的水下路由协议。在路由过程中，每个数据包中会包含路由信息，而各个节点不需要保存状态信息。所有传感器节点产生或者转发的数据总在一个类似于管道的路径传输，只有接近这个虚拟管道的节点能够转发数据。该算法是第一个基于地理位置的水下路由协议。该算法带宽低，延迟大，并且没有考虑链路质量，在节点密度低的区域可能无法找到接近虚拟管道的路径导致数据包传送率严重降低。且网络易受管道半径的影响等缺点。为了改善这些缺点，Nicolas Nicolaout等人在2007年《OCEANS》的文章“Improving the robustness of location-based routing for Underwater Sensor networks”中继续提出HH-VBF协议，该协议延续了虚拟管道传输的思路，改进之处在于把从source到sink的一条直达管道改进为每一跳视为一个管道。然而这两种算法需要事先确定一个路由“管道”半径，这使得算法在具体应用中，要求用户设置路由“管道”半径很不方便。 

Yan H等人在2008年《NETWORKING2008Ad Hoc and Sensor Networks,Wireless Networks,Next Generation Internet》中提出的DBR路由写于“DBR: depth-based routing for underwater sensor networks”，提出利用深度传感器感知的深度信息进行简单的贪婪转发，但在稀疏网络环境以及链路丢包率较高的情况下为了保证一定的数据包传输率需要重传冗余数据包造成额外的能量消耗。且层次路由扩展性较好，但是簇的维护开销较大，并且关键节点的失效对路由效率的影响较大。Guangzhong,Liu等人在2010年对其进行了改进提出了DBMR算法，该算法本身还是一种基于深度的多跳路由算法，源节点以一定的半径广播路由探测信号，收到广播信号的节点只有自身的深度小于源节点时才应答；源节点选择最先应答的节点作为下一跳节点，直到将数据传送给sink节点。该算法在一定程度上弥补了二维网络路由算法的缺陷，但是路由构造过程中控制开销较大。 

Wu,Xiaobing,等人在2010年的《Computer Communications and Networks(ICCCN)》上发表的“Energy-Efficient and Topology-Aware Routing for Underwater Sensor Networks”中提出了一种依赖于拓扑信息的路由方法。具体来说是邻居节点的信息度量值，同样是一种简化的贪婪算法。算法通过周期性的呼唤消息包，让每个节点保留一个degree信息，依据该degree信息来选择下一跳转发节点。这样的算法适用于密集的网络，能量消耗相对也比较低；但是由于水下网络中的节点存在随机的移动性，保证degree信息表存在一定的难度。 

Liu G和Wei C在2011年的《Multimedia Technology(ICMT)》上的文章“A new multi-path routing protocol based on cluster for underwater acoustic sensor networks”中提到了一种新的HMR-LEACH算法。该算法类似于一种LEACH算法的改进，也是一种基于簇的水下三维路由算法。该算法改进了簇头的选取办法，采用了多跳代替单跳，同时将能量和距离作为选取簇头的参数，给每条路径分配一个权重值来分配传输的可能性。该算法采用了多跳思想，也缓和了单条路径能耗过多的情形，一定程度上延长了网络寿命。然而没有提出节点睡眠机制对网络拓扑的影响。 

Lee S等人在2012年《Ubiquitous and Future Networks(ICUFN)》发表文章“A unicast based gradient routing protocol for asynchronous duty-cycling UWSNs”，提到了睡眠调度算法对路由算法的影响。该算法是一种基于单播的梯度路由算法，依赖于单播传输用占空比睡眠机制来更新邻居节点的梯度值，算法也分为两个阶段：初始化阶段和维护阶段。该算法中的梯度值，也就是一种权重值，它的大小是根据节点的剩余能量，没有将节点可信度等作为参考数值。 

因此，目前水下传感器网络路由中普遍存在的问题是： 

1、大多数没有考虑转发区域的划分策略。网格区域划分方法可以更好的节省网络能耗，从而增加网络寿命。 

2、没有将节点可信度以及水下环境的特殊性作为度量标准。节点的可信度极大程度上决定了链路的稳定性和可靠性。 

3、没有考虑网络在占空比睡眠调动机制情况下的情形。目前研究的传感器网络为了节省能耗，都引入睡眠占空比机制。大多数算法没有考虑此因素而无法达到节省能耗的目的。 

发明内容

本发明的目的是为了解决目前水下传感器网络的路由算法在网络区域划分和节点可信度方面的不足，此外还提出一种新的水下传感器网络中基于空间网格区域划分的贪婪路由方法，提出了一种可信度高，可扩展性强的三维路由算法。 

为了达到上述目的，本发明提供了水下传感器网络中基于空间网格区域划分的贪婪路由方法。 

一种水下传感器网络中基于空间网格区域划分的贪婪路由方法，包括三个阶段： 

（1）选择下一跳区域阶段：对于任意普通转发节点，当其选取下一跳转发节点时，首先确定下一跳转发节点所在的小正方体区域； 

（2）目标区域内选择节点进行贪婪转发阶段：转发节点执行睡眠调度，周期性地被睡眠和唤醒；在选择的目标小正方体区域中，按照转发贪婪规则选择下一跳醒着的节点，完成转发路径发现过程； 

（3）优化路径阶段：对发现的路径进行路径优化，选择最优路径。 

上述水下传感器网络可以等效成一个三维模型，它具有的特征为： 

(2a)整个水下三维网络空间被等效为一个立方体，按照魔方式划分法将立方体划分为若干个相同的小正方体区域，每个小正方体内含有的传感器节点的个数取决于网络中的节点密度和节点分布的随机性，信息将要传达的目的节点位于立方体上表面的中心处； 

(2b)任意两个相邻的小正方体区域中的任意两个普通节点，均可以相互通信，相邻包括面相邻、线相邻和点相邻，故所述步骤(2a)中，划分单位小正方体边长d与节点传输半径r的关系为 

$d=\frac{\sqrt{12}}{12}r.$

上述阶段(2)普通节点在选取下一跳转发节点时，转发贪婪规则具体步骤为： 

(3a)当一个普通源节点有数据信息需要发送，首先按照地理位置信息，确定自身的位置坐标、节点自身所在小正方体以及与当前小正方体相邻的小正方体位置坐标； 

(3b)根据地理位置坐标信息，进行一系列判断，确定一个目标小正方体区域，在该区域中选择下一跳醒着的节点； 

(3c)当确定了下一跳节点所在的小正方体区域，则按照权利要求1中的(2)选取下一跳醒着的节点。 

上述步骤(3b)中目的节点在自身位置的方向范围分为以下四种情况： 

(4a)若当前节点是位于立方体区域的八个顶角处时，目的节点与它自身的小正方体相对位置有十种：在立方体区域内与当前小正方体面相邻的三个小正方体、与当前小正方体线相邻的一个小正方体、与当前小正方体点相邻的三个小正方体以及分别与当前小正方体面相邻的三个小正方体延伸方向上的面相邻的三个小正方体； 

(4b)若当前节点是位于立方体区域的十二条棱位置且非顶角处时，目的节点与它自身的小正方体相对位置有十五种：在立方体区域内与当前小正方体面相邻的四个小正方体、与当前小正方体线相邻的五个小正方体、与当前小正方体点相邻的两个小正方体以及分别与当前小正方体面相邻的四个小正方体延伸方向上的面相邻的四个小正方体； 

(4c)若当前节点是位于立方体区域的表面且非顶角、非棱处，目的节点与它自身的小正方体相对位置有二十二种：在立方体区域内与当前小正方体面相邻的五个小正方体、与当前小正方体线相邻的八个小正方体、与当前小正方体点相邻的四个小正方体以及分别与当前小正方体面相邻的五个小正方体延伸方向上的面相邻的五个小正方体； 

(4d)若当前节点是位于立方体区域内部，即非顶角、非棱处且非表面区域，目的节点与它自身的小正方体相对位置有三十二种：在立方体区域内与当前小正方体面相邻的六个小正方体、与当前小正方体线相邻的十二个小正方体、与当前小正方体点相邻的八个小正方体以及分别与当前小正方体面相邻的六个小正方体延伸方向上的面相邻的六个小正方体； 

具体的情况取决于当前小正方体区域在整个三维立方体网络中的位置。 

上述步骤(3c)中确定小正方体区域的规则为： 

(5a)根据地理位置坐标(x_i,y_i,z_i)信息，分别计算节点自身所在小正方体各个相邻小正方体质心与目的节点的欧氏距离； 

(5b)确定了多个欧氏距离值后，按照从小到大顺序排列，选择欧氏距离最小的小正方体，这个小正方体区域即为寻求下一跳节点的范围区域。 

上述步骤(3d)中选取下一跳节点的贪婪规则为： 

(6a)每个节点都在执行睡眠调度机制；只有在当前处于醒着的节点中，才有可能被选取下一跳节点； 

(6b)每个节点被赋予一个权重值，这个值反映了节点的优劣性且决定了节点当选下一跳转发节点的可能性。权重值借鉴美国电气和电子工程师协会的IP性能度量工作组定义的internet网络性能功能度量指标，本发明简化定义水下传感网络的权重值的三大指标为：时延、链路损耗和剩余能量； 

(6c)若选择的小正方体内不存在可用节点，那么选择欧氏距离次小的小正方体作为寻求下一跳节点的范围区域，直到寻找到一个小正方体内存在可用节点。若所有相邻的小正方体区域内均不存在可用节点，则对当前小正方体进行标记，标记自身为不可用区域。 

上述阶段(3)中当在进行路径优化时： 

路由发现阶段查找由源节点到基站的路径后，路由优化阶段负责对该路径进行优化，消除路径中可能存在的路径环，引入TPGF算法中的基于标签的优化策略，其步骤包括： 

(7a)给已发现的路径中每个节点依次分配一个递减的标签号； 

(7b)由基站通过此未优化路径反向发送确认帧至源节点，路径中任意节点只能将确认帧转发给与自身具有相同路径号和具有最大标签号的节点，并清除未选中的节点上的标签号和路径序号。 

与现有路由方法相比，本发明所具有的积极效果是： 

1、能够在水下三维传感器网络中发现从源节点到信息所要传输到达的目的节点的路径，尽可能实现贪婪算法传输路径最优化； 

2、将网络区域划分、水下环境以及节点可信度纳入路由考虑因素，提高了路由算法的可靠度； 

3、避免了路径环问题。 

附图说明

图1为本发明中水下三维网络的等效图； 

图2为本发明中节点传输半径和小正方体边长的关系； 

图3为普通节点的传输范围和该节点所属小正方体的示意图； 

图4为为普通节点的传输范围和该节点所属邻居小正方体的示意图； 

图5为路径发现阶段示意图； 

图6为路径回退阶段示意图。 

具体实施方式

下面结合附图和实施例对本发明进一步说明。 

一种水下传感器网络中基于空间网格区域划分的贪婪路由方法，包括三个阶段： 

（1）选择下一跳区域阶段：对于任意普通转发节点，当其选取下一跳转发节点时，首先确定下一跳转发节点所在的小正方体区域； 

（2）目标区域内选择节点进行贪婪转发阶段：转发节点执行睡眠调度，周期性地被睡眠和唤醒；在选择的目标小正方体区域中，按照转发贪婪规则选择下一跳醒着的节点，完成转发路径发现过程； 

（3）优化路径阶段：对发现的路径进行路径优化，选择最优路径。 

水下传感器网络可以等效成一个三维模型，它具有的特征为： 

如图1所示，整个水下传感器网络的三维空间被等效为一个立方体，按照魔方式划分法将立方体划分为若干个相同的小正方体区域，每个小正方体内含有的传感器节点的个数取决于网络中的节点密度和节点分布的随机性；每个小正方体有一个唯一确定的ID。目的节点处于立方体上表面的中心处。假设任意两个相邻的小正方体区域中的任意两个普通节点可以相互通信。小正方体的边长可以和节点的传输半径r有相对应的约束关系。 

任意两个相邻的小正方体区域中的任意两个普通节点，均可以相互通信，如图2所示，描绘了节点最小传输半径r与小正方体的边长d的关系。由此可以计算出节点传输半径和小正方体边长的关系为 

(2d)²+(2d)²+(2d)²＝r²

则当且仅当 

$d=\frac{\sqrt{12}}{12}r$

时，才能保证任意相邻的小正方体的任意两个节点都可以相互通信。 

阶段(2)普通节点在选取下一跳转发节点时，转发贪婪规则具体步骤为： 

(3a)当一个普通源节点有数据信息需要发送，首先按照地理位置信息，确定自身的位置坐标、节点自身所在小正方体以及与当前小正方体相邻的小正方体位置坐标； 

(3b)根据地理位置坐标信息，进行一系列判断，确定一个目标小正方体区域，在该区域中选择下一跳醒着的节点； 

(3c)当确定了下一跳节点所在的小正方体区域，则按照权利要求1中的(2)选取下一跳醒着的节点。 

步骤(3b)中目的节点在自身位置的方向范围分为以下四种情况： 

(4a)若当前节点是位于立方体区域的八个顶角处时，目的节点与它自身的小正方体相对位置有十种：在立方体区域内与当前小正方体面相邻的三个小正方体、与当前小正方体线相邻的一个小正方体、与当前小正方体点相邻的三个小正方体以及分别与当前小正方体面相邻的三个小正方体延伸方向上的面相邻的三个小正方体； 

(4b)若当前节点是位于立方体区域的十二条棱位置且非顶角处时，目的节点与它自身的小正方体相对位置有十五种：在立方体区域内与当前小正方体面相邻的四个小正方体、与当前小正方体线相邻的五个小正方体、与当前小正方体点相邻的两个小正方体以及分别与当前小正方体面相邻的四个小正方体延伸方向上的面相邻的四个小正方体； 

(4c)若当前节点是位于立方体区域的表面且非顶角、非棱处，目的节点与它自身的小正方体相对位置有二十二种：在立方体区域内与当前小正方体面相邻的五个小正方体、与当前小正方体线相邻的八个小正方体、与当前小正方体点相邻的四个小正方体以及分别与当前小正方体面相邻的五个小正方体延伸方向上的面相邻的五个小正方体； 

(4d)若当前节点是位于立方体区域内部，即非顶角、非棱处且非表面区域，目的节点与它自身的小正方体相对位置有三十二种：在立方体区域内与当前小正方体面相邻的六个小正方体、与当前小正方体线相邻的十二个小正方体、与当前小正方体点相邻的八个小正方体以及分别与当前小正方体面相邻的六个小正方体延伸方向上的面相邻的六个小正方体； 

上述步骤(4d)中所述的普通节点的传输范围和该节点所属小正方体的邻居小正方体如图3、图4所示，图3中的球面包裹的区域表示当前节点的传输范围，其内包含了包括自身小正方体在内的三十三个小正方体，图4中直观地显示了该三十三个小正方体。以该几何体中心的小正方体为基准，存在三十二个与其相邻的小正方体。具体的情况取决于当前小正方体区域在整个三维立方体网络中的位置。 

上述步骤(3c)中确定小正方体区域的规则为： 

(5a)根据地理位置坐标(x_i,y_i,z_i)信息，分别计算节点自身所在小正方体各个相邻小正方体质心与目的节点的欧氏距离； 

(5b)确定了多个欧氏距离值后，按照从小到大顺序排列，选择欧氏距离最小的小正方体，这个小正方体区域即为寻求下一跳节点的范围区域。 

上述步骤(3d)中选取下一跳节点的贪婪规则为： 

(6a)每个节点都在执行睡眠调度机制；只有在当前处于醒着的节点中，才有可能被选取下一跳节点； 

(6b)每个节点被赋予一个权重值，这个值反映了节点的优劣性且决定了节点当选下一跳转发节点的可能性。权重值借鉴美国电气和电子工程师协会的IP性能度量工作组定义的internet网络性能功能度量指标，本发明简化定义水下传感网络的权重值的三大指标为：时延、链路损耗和剩余能量； 

定义：水下传感网络节点的权重值 

$w=\frac{\alpha }{D}+\frac{\beta }{L}+\mathrm{\lambda E}$

上式中，D代表延时，L代表路劲损耗，E代表节点剩余能量，α，β，λ……是系数，介于0-1之间。 

时延又和水下环境和距离等的参数相关。水下声信号的传输延迟为 

D(z,s,t)＝1449.05+45.7*t-5.21*t²+0.23*t³+(1.333-0.126*t+0.009t²)*(s-35)+16.3*z+0.18*z²式中，t＝T/10，T是温度单位是℃，s是盐度单位是ppt，z是深度单位是km。 

水声信道路径损耗函数为 

L＝d^kexp(d*g(f)/10)， 

式中g(f)是吸收系数为 

$g\left(f\right)=0.11\frac{f^2}{1+f^2}+44\frac{f^2}{4100+f^2}+2.75*{10}^{-4}{f}^2+0.003$

式中d为传输距离，k为能量传播因子，一般为2，f为发射中心频率。 

(6c)若选择的小正方体内不存在可用节点，那么选择欧氏距离次小的小正方 体作为寻求下一跳节点的范围区域，直到寻找到一个小正方体内存在可用节点。若所有相邻的小正方体区域内均不存在可用节点，则对当前小正方体进行标记，标记自身为不可用区域。 

上述阶段(3)中当在进行路径优化时： 

路由发现阶段查找由源节点到基站的路径后，路由优化阶段负责对该路径进行优化，消除路径中可能存在的路径环，引入TPGF算法中的基于标签的优化策略，其步骤包括： 

(7a)给已发现的路径中每个节点依次分配一个递减的标签号； 

(7b)由基站通过此未优化路径反向发送确认帧至源节点，路径中任意节点只能将确认帧转发给与自身具有相同路径号和具有最大标签号的节点，并清除未选中的节点上的标签号和路径序号。 

如图5所示，为路径优化实例图，图4为图中路由发现阶段查找的由源节点到目的节点的路径中每个节点依次分配一个递减的标签号-1,-2,...,-9。 

如图6所示，由目的节点通过此未优化路径反向发送确认帧至源节点，路径中任意节点只能将确认帧转发给具有最大标签号的节点，消除路由环路。通过这种路由优化过程可以使源节点到目的节点的路径最短。