UWSNs移动节点部署优化策略 ①

张海洋， 赵欢欢

(1.滁州学院计算机与信息工程学院，安徽 滁州 239000;2.中国科学技术大学，安徽 合肥 230000)

0 引 言

随着海洋资源开发以及海洋军事的影响，UWSNs已变为近几年国内外研究热门课题。UWSNs通过节点组成网络并实时监测并发送目标区域内的信息到水面基站，再通过卫星或近岸基站将实时信息发给观察者[1]。在UWSNs研究中，监测区域部署是一个基本问题，即如何利用有限的节点部署在目标监测区域，达到网络的最大覆盖度[2]。

布置在水下的静态节点其适应性较差，受复杂水声环境、水生物及水流等影响较大，网络的优化效果较低，不能对目标监测地区达到合理高效的部署效果，容易导致监测盲区或网络失效，而移动节点则能较好的解决这一问题。

概率感知模型，考虑了信号衰减及噪声干扰，比0-1感知模型更适合水下复杂环境。节点si对任意点pj的感知公式为[3]：

(1)

水下节点通常采用水声信号进行相互通信，任意节点si与sj之间的欧氏距离定义为

(2)

如果d(si,sj)小于节点通信半径Rc，则si与sj可直接通信并互为邻居节点。

1 UCGA算法求解UWSNs移动部署问题

GSO是一种较为新颖的群智能优化算法，具备计算速率快、设置参数较少、搜索自适应且易于实现的特征，能够较好地求取全局极值及搜索多极值问题中的多个极值。根据文献仿真验证，萤火虫算法也存在陷入局部最优问题的可能性，但是萤火虫算法具有跳出局部最优的能力，具有更好的全局寻优能力[4]。针对三维UWSNs网络部署的特点，将GSO算法结合混沌思想优化为与三维空间的UWSNs部署环境需求相符的新算法UCGA。

将目标监测区域节点部署方案视为一个求最优值问题，其目的是使网络的覆盖度达到最优值。目标适应度值函数则对应为所有节点的目标水域覆盖面积与监测水域的总面积之比，则目标适应度值函数即覆盖度为[5]：

(3)

UCGA算法具体步骤如下：

步骤一：初始化各参数，根据混沌策略产生取值区间的初始化种群值，比较并从{Xi|i=1,…,N}中选出最优秀的个体向量Xb，随机的生成维数为N的变量Z1=[z1,1,z1,2,…,z1,N]，使用Z1作为混沌变量进行迭代分析，其中z1,N表示混沌序列长度，将Z1与Xb组合用以生成萤火虫种群初始向量Xc，相关公式如下[6]：

Xc=ρ×Z1+(1-ρ)Xb

(4)

(5)

式中，tmax是算法的最高迭代数目，t则是当前到达的迭代数目。

步骤二：依据目标适应度值函数计算其发光亮度；

步骤三：所有萤火虫移位，对每个个体，寻找其周围发光强度高于它的个体并计算它们之间的距离，依据适应度值函数计算出群体的相对亮度及吸引度，然后确定其移动方位并更新位置；

步骤四：由于基本萤火虫算法易陷于早熟并收敛，故选择适应度值较低的个体，利用公式生成相对应的新个体并替换，提升了种群收敛速率，且由于新个体是由logistic映射生成，拥有者随机性，故替换原个体的新萤火虫增加了种群的分布均匀性。

步骤五：通过对比萤火虫个体的适应值和种群位置适应值得出新最优位置和最优适应值，判断最优结果是否大于原种群位置处适应值。若否，则在其感知范围内继续寻找最优解，若是，则将选出的新最优位置作为新的群体位置，即重置种群位置，否则种群个体继续寻找周围最优解，返回步骤二。

2 仿真与评估

假设在三维监控水域内随机布撒了节点，且该网络具备以下性质：所有节点均拥有一致的物理结构，即感知及通信半径完全一致，并采用概率感知模型。

将UCGA算法与Horng等[7]提出的改进GSO算法在Matlab2009上进行对比仿真，将9个节点投放在水下检测区域形成覆盖图形如图1所示，其有效覆盖度为35.72%,目标水域极限覆盖度为12π×Rs3/104=82.75%；经改进GSO进行重新部署后的优化效果如图2所示，其对目标检测水域的有效覆盖度为65.43%；通过UCGA进行优化得到节点分布图如图3所示，其有效覆盖度为72.14%。通过对比可以看出经过优化后UCGA分布效果更加合理，当种群数目即节点数增加的时候，改进GSO的优化效果要低于UCGA算法。

图1 随机部署覆盖图

图2 改进GSO覆盖图

图3 UCGA算法优化图

表1为随机部署、改进GSO、UCGA不同深度水平覆盖度比较，仿真出的不同深度水平截面图如图4、5、6所示，从图表中可以看出，相比改进GSO算法，UCGA算法在z=25m、z=50m、z=75m三种深度的覆盖效果均有较好的提升。

表1 不同深度水平覆盖度比较

图4 随机部署不同深度截面图

图5 改进GSO算法优化后不同深度截面图

图6 UCGA算法优化后不同深度截面图

图7 覆盖度对比图

仿真出的有效覆盖度随着迭代次数增加而变化如图7所示，其中红色曲线为基于UCGA迭代优化曲线，蓝色曲线为改进GSO优化迭代覆盖度曲线，从图里可以看出，UCGA在前期相较于GSO表现出更快的收敛速率，其主要原因在于采取Logistic映射所生成的序列初始化节点，得到质量较优的初始种群解；而GSO则是完全根据随机移动寻优，因此其前期优化速度较慢。UCGA在迭代后期由于混沌扰动性对较优解进行局部搜索以跳出局部极值点，使其在小范围内具备更好的局部寻优能力并收敛于较高覆盖度，UCGA在后期体现出了更好的收敛速率并获得较优的部署覆盖效果。

3 结 语

UWSNs移动节点部署是近几年重点研究课题之一，对节点部署优化可以显著提高其覆盖性能，因而提出基于混沌理论的UCGA对水下移动节点进行部署优化。在节点随机部署阶段UCGA采用Logistic映射所生成的序列初始化传感器节点，并在重部署阶段利用混沌扰动性对适应度值较低的局部搜索以跳出极值点。UCGA弥补了GSO的寻优精度相对较低的问题，仿真实验验证了，UCGA具有较理想的优化效果和较快的收敛速率，因此在未来实际应用中具有一定可行性和有效性。