基于AUVs的水下移动无线传感器网络愈合算法

梁文辉，董 强，何 明，陈秋丽，丁晨璐

LIANG Wenhui1，2,DONG Qiang1,HE Ming1,CHEN Qiuli1,DING Chenlu3

1.解放军理工大学 指挥信息系统学院，南京210007

2.解放军61345 部队

3.解放军理工大学 第六十三研究所，南京210007

1.College of Command Information Systems,PLA Science and Technology University,Nanjing 210007,China

2.61345 Troops,PLA,China

3.The 63rd Research Institute,PLA Science and Technology University,Nanjing 210007,China

1 引言

水下移动无线传感器网络（Mobile Underwater Wireless Sensor Networks，MUWSNs）应用于水下复杂环境，传感器易受水下生物、水流等外力因素影响发生位置迁移；且传感器长期受海水腐蚀及浮游生物的附着，逐渐降低灵敏度，易出现节点失效[1]。为推动MUWSNs在水下重要领域应用，高效、合理的拓扑愈合算法至关重要[2]。

目前，针对MUWSNs 拓扑愈合方面的研究成果很少，文献[3]提出拓扑愈合算法TCS-CA，通过恢复失效节点单跳邻居间可达性来实现拓扑自愈，但该算法适用于地面无线传感器网络，在MUWSNs 中并不适合；文献[4]针对无线传感器网络中出现的覆盖洞区域，通过播撒第二代节点的方式修复覆盖洞区域，但播撒的随机性不能完全保证覆盖洞区域能够获得足够数量用于修复的新节点；文献[5]利用已知网络拓扑的几何规则，赋予失效节点在离开前决定其邻居节点移动行为的能力，但这对失效节点提出了很高的要求，较难实现；文献[6]引入AUV 节点，提出基于满Steiner 树问题的拓扑愈合算法，但未对失效节点发现和AUV 选择等问题做具体的研究，且该方法基于二维平面，难以应用在水下三维环境中。

针对上述问题，本文提出一种基于自主式水下航行器（AUV）[7-9]的MUWSNs 愈合算法，充分考虑水流对MUWSNs 网络拓扑的影响，构建水下实体移动模型，利用AUVs的自主移动性对MUWSNs失效拓扑进行愈合。

2 网络建模及问题描述

2.1 网络建模

在目标监测区域D中，不均匀地分布了M个需监测的目标事件，在区域D中部署N个传感器节点和K个AUV 节点，传感器与AUV 均为全向感知，最大感知半径分别为rs与，最大通信半径分别为rc与。为便于研究和计算，传感器和AUV 均采用布尔感知模型。假设初始MUWSNs 网络拓扑中传感器节点在目标监测区域D中完成了非均匀部署，网络全局连通，整个网络对目标事件集的覆盖率达到90%以上；AUVs 分布密度与传感器节点分布密度相匹配[10]。受水下外力因素影响，会出现节点故障或网络失效，则需AUVs 进行拓扑愈合。

将MUWSNs拓扑抽象为一个三维空间的无向图，传感器节点si的邻居集合为Λ(si)，邻居节点数为Nneigh(si)，感知半径为rs(si)，覆盖范围为Nsensor(si)={ej|d(ej,si)≤rs(si),j=1,2,…,m}；si能量为e(si)，失效节点标记为sf，对失效节点进行替代的AUV标记为af，AUV速度为VAUV。

为便于模型分析，给出符合实际应用的假设：

假设1水下传感器节点具备辅助定位系统，能够知道自身位置及邻居节点位置，并通过信息交互获取邻居节点的邻居集合Λ(si)。

假设2AUV 可直接通过水面基站与其他AUV 进行通信，并获取其他AUV 的位置信息。

假设3在整个目标监测任务执行过程中，AUV 能量为+∞，其信息感知收发以及位置移动产生的能耗忽略不计。

假设4K＜＜N，由于AUV造价较高，因此部署数量远少于水下传感器节点部署数量。

假设5，并且AUV 能按需在最大值范围内调节感知半径和通信半径的大小。

假设6在AUV 愈合过程中不会发生新失效。

2.2 水下实体移动建模

水下实体包括监测区域内事件、传感器以及AUVs，水下实体会随着水流和漩涡等水体流散情况产生运动，从而引起MUWSNs 拓扑的动态变化。水流的运动不是完全随机的过程，结合一种适合流动类型广泛的水流运动模型[11-12]来构建水下实体移动模型，可更准确地模拟MUWSNs真实运行状态。

对于不可压缩的水流来说，其运动可近似为在二维平面内。在流体力学中，这是一个通用的假设[13]。

用ψ表示二维水流运动场，采用式（1）所示的水流喷射模型来描述水流运动情况：

B(t)=A+εcos(ωt)用于调制曲流宽度；A为平均曲流宽度，ε为调制振幅，ω为调制频率，k为单位长度曲流数目，c为曲流向下游移动的相速度。

水下实体在水流场ψ内的运动受两个方向的速度场δ=(u,v)影响，用式（2）表示：

u表示向东的速度场，v表示向北的速度场。用拉格朗日法来描述水下实体在X、Y方向的运动速度，得到式（3）的Hamiltonian 方程：

从上述水下实体移动模型可以看出，坐标为(x,y,z)的水下实体经过时间t后，随水流移动到了位置(x+x′×t,y+y′×t,z)处。对于X、Y坐标相同但Z坐标不同的水下实体，是以相同模式运动的。

3 算法设计

3.1 预处理阶段

（1）AUVs分配

水中AUVs分布密度与传感器分布密度相匹配。发生拓扑失效时，为使距离最近的AUV 实施愈合，需对每个AUV分配一定规模的传感器，对ai∈A来说，所负责的传感器集合表示为Γ(ai)，并且有Γ(ai)∩Γ(aj)=∅,(j≠i)。

图1 演示了AUVs分配时的消息传递流程：

①∀ai∈A，向通信范围内的传感器节点发送报文invite_msg（IDi，Counter），IDi为ai的身份标识，Counter为计数器，记录报文传递次数，若传感器节点总数为N，Counter 初始值设为N-1，报文每传递1 次，Counter 减1，减至0 时，报文失效。

②传感器节点si收到invite_msg（IDi，Counter）报文后，查询自身属性中的AUV_flag标识，若AUV_flag=Null，则修改为AUV_flag=IDi，即si加入集合Γ(ai)，并向ai发送回复报文reply_msg(si)；若AUV_flag ≠Null，表明si已加入Γ(aj),(j≠i)。

图1 AUV 节点分配消息传递流程

③执行Counter=Counter-1，si给邻居集合中其他传感器节点转发invite_msg(IDi,Counter)，它们在收到该报文后，按②中方式处理。

④重复②、③至计数器Counter变为0，报文失效，不再进行传递，此时ai分配完毕。

（2）传感器分组

为便于消息的传递和失效节点的发现，预先对已部署的传感器进行编号并分组，用二元组（SID，GID）表示传感器节点自身编号和所在组号。

①在已部署的传感器节点中随机选择节点si编为1 号，ID 标记为（1，1），1 号为GID1 组的组长。

②若si的邻居节点数为Nneigh(si)，则Λ(si)中的节点依次编号为2,3,…,Nneigh(si)+1，相应的ID 设置为(2,1),(3,1),…,(Nneigh(si)+1,1)。

③1号节点编组完成后，向2号节点发送编组指令报文group_msg(Nneigh(si)+1)，报文中携带了目前已编最大号数Nneigh(si)+1，假设2 号节点为sj，其Λ(sj)中有k个节点已编号并分在了组GID1 中，故对剩余Nneigh(sj)-k个未编号节点进行编号。

④2 号节点完成编组后，向其组长1 号节点发送finish_msg(Nneigh(sj)+Nneigh(si)-k+1) 编组完成报文，携带了目前最大编号信息，1 号节点收到后，向3 号节点group_msg(Nneigh(sj)+Nneigh(si)-k+1)编组指令报文，3号节点开始编组。

⑤依次进行，直到所有传感器节点编组完毕。

3.2 失效感知阶段

失效感知阶段是要及时发现失效位置并告知相应AUV。节点失效情况具体分为两种：

（1）节点编号不同与所在组号，即SID ≠GID

①此类传感器节点以Interval为时间周期向其组长发送签到报文sign_msg（AUV_flag），包含了自身所属AUV 的标识AUV_flag。

②若X组组长si在计时器Timer1内未收到组员sj的签到报文，则向全网发起对sj的寻找报文seek_msg(sj,si)，该报文携带了si和sj的ID。

③网络中节点收到seek_msg(sj,si)后，若不是节点sj，则继续转发，若sj收到该报文，则向si返回feedback_msg（new_GID），包含sj所在新组的GID，si在收到feedback_msg（new_GID）后在组成员列表及邻居集合Λ(si)中将sj删除；若Timer2 内si未收到feedback_msg（new_GID）报文，则证明sj处已发生了拓扑失效，si向sj原所属的AUV发送愈合请求报文recovery_msg（sj，Λ(sj)），且si在组成员列表及邻居集合Λ(si)中删除sj。

（2）本节点即为所在组组长，即SID=GID，另外，编组调整后也可能出现此类节点

①此类节点（这里用s1指代）以Interval为周期向其所属AUV 节点ai发送sign_msg(s1,Λ(s1))签到报文，携带s1位置信息和邻居集合信息。

②若其所属AUV节点ai在Timer1内未收到s1的签到报文，则ai向全网发起对s1的寻找报文seek_msg(s1,ai)，该报文携带了s1和ai的ID。

③若在计时器Timer2 内s1收到了seek_msg(s1,ai)，则向ai返回报文feedback_msg（new_GID），s1及其原邻居节点调整邻居集合Λ及编组；若在计时器Timer2 内未找到s1，则证明s1处发生了拓扑失效，ai将主动进行愈合。

3.3 移动愈合阶段

当AUV 获取了失效位置信息及失效节点邻居集合信息后，选择距失效位置最近的AUV 立即移动进行拓扑愈合，保证移动到失效位置耗时最短。

移动愈合阶段具体过程如下：

（1）移动位置计算。AUV 节点af发现失效节点sf后，用公式（4）计算sf邻居集合Λ(sf)中所有节点的中心位置Lcenter，然后af向Lcenter移动

Lj为节点sj的位置，Nneigh(sf)为sf邻居节点数。

（2）AUV 功率调整。af移动到中心位置Lcenter后，由于AUV 信号发送功率和接收灵敏度比普通传感器高很多，可进行适当减小，降低能耗，保证sf所有邻居通信，完成拓扑愈合。

（3）后续处理。当af完成了对失效拓扑的愈合后，向水面基站发送愈合完成消息，水面基站收到该消息后，将af从AUVs 集合A中删除，并重新进行预处理，将集合A中剩余AUVs 重新分配，并以af作为1 号节点重新对传感器进行编组。

4 仿真与性能分析

采取Monte Carlo实验，进行100轮仿真。在400 m×400 m×400 m 的水下监测区域，随机布置50 个目标事件，用20 个互通的传感器完成对目标事件90%以上的覆盖，部署5 个AUVs。当出现拓扑失效，AUVs 均已用于愈合时，1 次仿真结束。

实验中模型所用参数如表1、表2 所示。

表1 网络模型实验参数

表2 水下实体移动模型实验参数

实验环境部署情况如图2 所示。

图2 水下目标监测区域部署情况

采用基于AUVs 的MUWSNs 拓扑愈合算法的情况（简称AUV-Healing）与不采用愈合算法的情况（简称NO-Healing）进行比较。

图3 显示了两种情况下MUWSNs 的连通性，左图中AUV-Healing 曲线纵坐标基本一直维持在1 处，即使拓扑失效使连通性变为0，也会迅速被AUV 愈合，连通性恢复为1；而右图中的NO-Healing 曲线，当拓扑失效后，连通性将长期处于0，网络不会主动进行愈合，图中大约46 min 时NO-Healing 曲线又变为1，那是因为传感器节点受水流影响移动过程中无意间恢复了网络连通，但很快又失效。

图3 网络连通性比较

为观察传感器通信半径对MUWSNs拓扑可靠性的影响，将传感器通信半径分别设置为30 m、60 m、90 m，在水下实体移动模型影响下进行100轮重复实验，每轮实验运行100 min，统计拓扑失效发生次数，结果如图4所示。

图4 拓扑失效次数与节点通信半径的关系

从图中可以看出，传感器通信半径越大，MUWSNs拓扑发生失效的次数越少，当rc=90 m 时，对于每轮实验来说，失效发生次数已非常少，仅有的一些失效可能是由于传感器节点移动超出目标监测区域范围而造成的。

5 结束语

MUWSNs所处的水下环境为其赋予了动态演化性，拓扑愈合算法是提高MUWSNs 可靠性的重要手段[14-15]。本文对已有的几个拓扑愈合算法进行了归纳总结，分析了它们的局限性，提出了一种基于AUVs 的MUWSNs愈合算法，并构建了水下实体移动模型，针对水下实体移动引起的拓扑失效，AUVs 能够及时感知并进行快速愈合，极大地提高了MUWSNs 可靠性。仿真实验证明了本文所提愈合算法的正确性和有效性，具备广泛的应用价值。

[1] Heidemann J，Stojanovic M，Zorzi M.Underwater sensor networks：Applications，advances and challenges[J].Philosophical Transactions on the Royal Society A，2012，370：158-175.

[2] Blouin S.Intermission-based adaptive structure estimation of wireless underwater networks[C]//Proceedings of the 10th IEEE International Conference on Networking，Sensing and Control（ICNSC），April 2013，2013：130-135.

[3] 刘林峰，吴家皋，邹志强，等.面向节点失效问题的无线传感器网络拓扑自愈算法[J].东南大学学报，2009，39（4）：695-699.

[4] Wang L，Guo Y，Zhan Y.Security topology control method for wireless sensor networks with node-failure tolerance based on self-regeneration[J].Eurasip Journal of Wireless Communications and Networking，2010，16：1-11.

[5] Sekha A，Manoj B，Murthy C.Dynamic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility[C]//Proceedings of the 3rd IEEE Int’1 Conf on Pervasive Computing and Communications，Kauai，Island，2005，51-60.

[6] 刘林峰，刘业.基于满Steiner 树问题的水下无线传感器网络拓扑愈合算法研究[J].通信学报，2010，31（9）：30-37.

[7] Erol-Kantarci M，Mouftah H T，Oktug S.A survey of architectures and localization techniques for underwater acoustic sensor networks[J].IEEE Commun Surv Tutor，2011，13（3）：487-502.

[8] Liu Linfeng，Liu Ye，Zhang Ningshen.A complex network approach to topology control problem in underwater acoustic sensor networks[J].IEEE Transactions on Parallel and Distributed Systems，2013（1）：1-12.

[9] Caraivan M C，Dache V，Sgarciu V.Common Framework model for multi-purpose underwater data collection devices deployed with remotely operated vehicles[C]//Proceedings of the 7th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems：Technology and Applications，Berlin，Germany，12-14 September，2013：849-854.

[10] Caraivan M，Dache V，Sgârciu V.Simulation scenarios for deploying underwater safe-net sensor networks using remote operated vehicles：Offshore exploration constructions models and sensor deployment methods[C]//Proceedings of the 19th International Conference on Control Systems and Computer Science，2013：419-424.

[11] Caruso A，Paparella，Vieira LFM，et al.The meandering current mobility model and its impact on underwater mobile sensor networks[C]//Proc of INFOCOM 2008.Piscataway，NJ：IEEE，2008：221-229.

[12] Jafri M R，Ahmed S，Javaid N，et al.AMCTD：Adaptive mobility of courier nodes in threshold-optimized DBR protocol for underwater wireless sensor networks[C]//Proceedings of the 8th International Conference on Broadband，Wireless Computing，Communication and Applications，Compiegne，2013：93-99.

[13] 何明，梁文辉，陈国华，等.水下移动无线传感器网络拓扑[J].控制与决策，2013，28（12）：1761-1770.

[14] Cao Jiabao，Dou Jinfeng，Dong Shunle.Design and development of heterogeneous underwater sensor networks[C]//Proceedings of the IEEE 9th International Conference on Mobile Ad-hoc and Sensor Networks（MSN），2013：425-430.

[15] Manjula R B，Sunilkumar S M.Coverage optimization based sensor deployment by using PSO for antisubmarine detection in UWASNs[C]//Proceedings of Ocean Electronics（SYMPOL），2013：15-22.