基于遗传退火算法的水下传感器部署优化方法＊

胡 炜 曾 斌

（海军工程大学管理工程系 武汉 430033）

基于遗传退火算法的水下传感器部署优化方法＊

胡 炜 曾 斌

（海军工程大学管理工程系 武汉 430033）

水下传感器部署是构建水下传感器网络从而对重点海域可能的敌方水下入侵行为进行监测预警的关键环节。利用a－hoc网络中经典网格拓扑结构对传感器节点部署进行规划。分析水声环境复杂性，采用Urick的声纳效能系列公式，将节点穿透网格单元的信号强度转化为适应度，运用遗传退火算法对传感器节点部署进行优化，有效提高了部署区域的适应度值，进而提升了整体网络性能。通过Matlab仿真验证了混合算法的可行性和优越性。

部署；网格拓扑结构；信号强度；适应度；遗传退火算法

Class NumberTP212

1 引言

近年来，随着海洋建设的快速发展，海上威胁日益严峻。特别是在面临来自水下威胁时，主要手段还是依靠舰船自携的声纳或反潜直升机，难以形成全天候、大范围的警戒体系。为了弥补水下监测能力的不足，需要建立水下传感器监测网络来提升在重点海域、重点目标区域对敌方入侵的监测水平。这样的海域往往是海上一块重点探测区域或者一个具有军事用途（高价值目标）的港口近海区域，然而在这样的区域设计水下传感器网络带来的困难有：水声环境复杂和声波衰减迅速。传感器的探测及通信性能受影响因素多且变化大，不易计算。此外，对于设计者来说，传感器的数量以及部署这些传感器所带来的高额成本也是必须考虑的重要因素。目前，在节点部署方面，赵小敏等［1］在AIO（area of interest）不规则前提下，提出了基于Delaunay三角化与网格的传感器随机部署法；Linfeng Liu等［2］提出了一种建立在水下信号不规则基础上的传感器网络拓扑结构控制模型；Erick F.Golen［3］则在给定概率条件下将监测区域分割成不同子区域，在考虑单向博弈行为的基础上采用遗传算法求解节点部署的最优解。

本文在Golen的基础上，充分考虑到水声环境的复杂性，将水声环境划分为六个主要影响因素，在Urick的被动声纳探测效能公式基础上，采用ad－hoc网络中网格拓扑结构作为传感器网络结构，进而将部署区域分割为各网格单元，运用改进的遗传退火混合算法对节点部署策略进行优化，进而提升传感器在部署区域的整体探测性能［4～6］。

2 遗传退火混合算法优势特点

首先，遗传算法作为一种优化方法，存在以下主要几点局限性：

1）单一的遗传算法编码无法全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，但这样算法计算的时间必然增加；2）遗传算法容易出现过早收敛；3）像其他算法一样，遗传算法也容易陷入局部极值。

相比之下，模拟退火算法作为一种随机搜索算法具有以下几个优势：1）与局部搜索法相比，模拟退火法能以一定概率接受恶化解从而扩大搜索空间，使迭代过程易跳出局部最优陷阱，增大搜索到全局最优解的机；2）理论上模拟退火法搜索到全局最优解的概率为1，合理选取冷却温度梯度和进度范围，模拟退火法能在有效的时间内获得较高质量的全局最优解。

综合上述所列的两种算法的特点，针对单一遗传算法存在的先天性缺点，利用模拟退火算法的优点，针对性的对遗传算法进行改进。在遗传算法的交叉和变异过程中引入模拟退火的Metropolis接受准则，这样不仅能够缩短算法的运行时间，也可以有效避免单一遗传算法容易陷入局部极值和过早收敛的问题。

3 水下传感器部署混合优化算法实现

3.1 水声环境特点

针对某一个重点海域（如附有高价值军事用途的港口或海上某一片重点监测区域），水下地理环境的复杂性、介质对信号的吸收、水声环境噪声等都对传感器探测和通信性能造成重要干扰（如探测和通信有效范围降低、传感器节点间数据传输延迟增加以及数据传输速率受限等）。此外，水下间歇性产生的气泡和海底地震产生的冲击波也会对传感器性能，尤其是网络整体的通信链接效能造成间歇干扰。

为了充分描述针对监测敌方入侵而建立的水下传感器网络的水声环境特点以及所带来的影响，这里将它们划分为六个主要影响因子：1）探测范围；2）通信范围；3）成本；4）链路冗余；5）范围依赖因子；6）敌方入侵的可能性。

3.2 部署区域的节点拓扑结构

网格拓扑（mesh）结构的概念在无线传感器网络中，特别是a－hoc网络中具有重要意义。网格的划分为整个网络提供了多种通信链接路径以此来增强连通性能［7］。

图1 网格结构的节点连接示意图

一个网格拓扑结构的连接冗余度可以由最小分割集的大小来决定，即为了分割该网络所必须移除的节点之间的连接数量。例如在某次间歇性环境影响下，节点f和d以及f和c之间的连接间断，那么该网格拓扑结构就被分割成了两个部分。若此时i节点获得了探测数据，那么数据是无法传输到a节点（假设临近某个数据中转站）的。Stoer将图论的方法应用到如何定量一块网格区域的最小分割集大小［9］。那么，不难从逻辑上推理出：某一网格区域的最小分割集大小越高，该区域所在传感器节点的探测范围在某种程度上就越大［6］。

3.3 算法描述

第一步：初始种群构建

在二维直角坐标系中，传感器部署区域表示为一系列N个二维传感器位置坐标集：

G是染色体，每一个传感器节点的二维坐标就是一个基因。起初，部署区域可以根据经验数据库里的水声环境累积数据，采用一种学习算法（如自组织适应图）划分为具有相似水声环境的多个子区域，各子区域是可以独立优化且在算法开始前区域里已经包含了固定数量的传感器。假设rc为传感器节点的有效通信半径。起始传感器节点被随机部署在一个位置上，下一个传感器的部署的位置需要满足以下条件：

drand和θ为两传感器节点之间的随机距离和水平基准角度。

第二步：区域评估和适应度计算

节点随机部署完毕后，各划分区域内传感器节点之间的无向连接图就生成了。根据网状拓扑结构最小分割集大小的定义、水声环境的优劣程度定义一个最小分割集阈值（MCSS）。假设MCSS阈值为3，传感器部署区域MCSS值只有2，那么该区域的适应度即为0，以此阻止它进入下一代遗传种群中。

若分割子区域满足阈值限定条件后，将整个部署区域分割成边长为1个标准单位的方形网格单元组。根据文献［2～5］和Urick的被动声纳传感器效能公式有：

当信号穿透强度为0时，表明敌方在该网格单元里被瞬时或固定探测发现的概率为0.5。很显然，当信号穿透强度越高，固定探测发现（probability of detection，POD）的概率就越高［6］。

式（4）表示对某个位置（i，j）上的网格单元来说，信号穿透强度大小应该取区域当中N个传感器信号穿透强度里的最大值。

式（5）～（7）在文献［5］中用来将网格单元的信号穿透强度转换为POD。其中，式（5），式（6）表示的是一个六维多项式曲线拟合方法，A＝［1，0.0705，0.04223，0.00927，0.000152，0.000277，0.00000431］公式（7）中，SD为正太分布的标准偏差，一般值取6dB。

只要每个网格单元的信号穿透强度转换为POD，那么传感器部署全区域的适应度就可以表示为

α是全区域的长度，β为宽度。α、β值的大小决定了在二维坐标系中X轴和Y轴方向上有多少网格单元。

很显然，当适应度值增加，传感器在部署区域的整体表现性能也随之提升。

第三步：设计选择算子，移除相对较低的适配值的个体

计算个体的适应度，选择使用比例算子，即假设种群数量为W，个体i的适应度为Fni，则个体i被选中的概率为

随机产生（0，1］之间的随机数，如果个体Pi大于或等于该随机数，则被选中，小于则被淘汰［10］。

第四步：交叉操作并应用模拟退火的Metropolis接受准则（选择H（xi）＝（1－Fn（xi））作为目标函数）生成新种群。

将新种群的染色体进行交叉操作，在给定交叉概率条件下交叉基因（即传感器位置坐标）随机选择，用于交叉操作的基因数量限制在［1，2／N（取下限）］之间。

图2 交叉操作示例图

分别计算交叉前父代个体a和个体b的适应度值分别为Fn（a）和Fn（b），交叉后子代个体a′和个体b′的适应度值为Fn（a′）和Fn（b′），根据上述模拟退火的Metropolis接受准则可得：

随机产生一个随机数random（r）∈（0，1］，判断满足条件生成新种群，执行下一步，否则重新返回。

第五步：对第四步得到的新种群执行变异操作，同样也将Metropolis接受准则应用到变异操作中，得到新种群。

图3 变异操作示例图

随机产生一个随机数random（r）∈（0，1］，判断满足条件生成新种群，执行下一步，否则重新返回。

第六步：将上述生成的新种群赋给初始种群，并判断迭代次数是否达到最大遗传代数，满足则转入第七步，否则转入第四步。

第七步：更新温度和初始种群。若达到终止准则（终止温度），则停止计算，输出最优解。否则，转入第四步。

4 仿真实现

4.1 仿真参数设置

表1 仿真参数设置表

4.2 Matlab仿真结果图

图4 MCSS取值2时的适应度值变化图

图5 MCSS取值为4时的适应度变化图

5 结语

本文对水下传感器网络节点区域优化部署进行研究，在分析六种水下声学环境影响因子的基础上，通过引入a－hoc网络中经典的网格拓扑结构完成了传感器节点的区域初步部署规划，进而利用Urick关于被动声纳水下效能系列公式，将节点穿透网格单元的信号强度转化为适应度值，设计并运用遗传算法和模拟退火相结合的混合算法来对节点部署进行优化。Matlab仿真结果显示了，在不同最小分割集大小的约束下，经过混合算法的优化，对比传统遗传算法，有效提高了区域的适应度值且收敛性更好，进而提升了传感器部署区域的整体表现，证明了混合算法的可行性和优越性。

［1］赵小敏，毛科技，何文秀.感测范围不规则情况下无线传感器网络节点部署算法［J］.软件学报，2012，29（15）：59－68.

［2］Linfeng Liu，Ningshen Zhang，Ye Liu.Reasearch on Arichitecture for Reconfigurable Underwater Sensor Networks［C］／／Proc of IEEE Conf on Networking Sensing and Control.Arizona：IEEE，2005：831－834.

［3］E.F.Golen，N.Shenoy，B.I.Incze.UnderwaterSensor Field Design Using Game Theory［C］／／Military Communications Conference，Orlando，FL，2007（19）：188－199.

［4］Ptan，J.Kurose，B.N.Levine.A Survey of Practical Issues in Underwater Networks［J］.WUWNet，2006（6）：17－24.

［5］R.J.Urick.Principle of Underwater Sound，3rd Edition，Peninsula Publishing，Los Altos，CA，1983：108－117.

［6］Erick F.Golen.Intelligent Deployment Strategies For Passive Underwater Sensor Networks［D］.United States：Golisnano College of Compiting and Information Sciences，Rochester Institute of Technology，2009（4）：323－330.

［7］I.F.Akyildiz，D.Pompili，T.Melodia.Underwater Acoustic Sensor Networkd Research Challenges［J］.Ad Hoc Networkd，2005（5）：189－201.

［8］雷英强，张善文.遗传算法工具箱及应用［M］.西安：西安电子科技大学出版社，2014：37－55.

［9］杨汉桥，林晓辉.遗传算法和模拟退火法寻优能力综述［J］.机械制造与研究，2009，27（4）：73－75.

［10］M.Stoer，F.Wanger.A Simple Min－Cut Algorithm［J］.Journal of the ACM，1997，44（4）：585－591.

An Optimization Method of Underwater Sensors Deployment Based on Genetic and Anneal Algorithm

HU Wei ZENG Bin
（Department of Management and Engineering，Naval University of Engineering，Wuhan 430033）

The deployment of underwater sensors is the key link for establishing an underwater sensor network，which will be used for detecting and early warning the invasion from enemies underwater.The topological structure of the mesh from the classic a－hoc network is used for deploying sensors.The complexity of the underwater acoustic environment is analyzed and a series of formulas of sonar performance from Urick's are used.By this way，the signal excess of grid cells can be transmitted to the value of fitness.Then，genetic and anneal algorithm is used to optimize the deployment of sensors，which can effectively improve the fitness value of deployment area and further improve the overall underwater network performance.The feasibility and superiority of genetic and anneal algorithm are verified through the simulation by Matlab.

deployment，topological structure of the mesh，signal intensity，fitness，genetic and anneal algorithm

TP212DOI：10.3969／j.issn.1672－9730.2015.11.007

2015年5月1日，

2015年6月28日

湖北省基金项目：稀疏动态水下传感器网络优化部署（编号：2011CDD051）资助。

胡炜，男，硕士研究生，研究方向：水下传感器网络。曾斌，男，博士，教授，硕士生导师，研究方向：水下传感器网络、管理信息系统，装备维修。