基于改进MPA 的分层无线传感器网络优化部署*

陈 龙金可仲蔡雪冰唐震洲

(温州大学计算机与人工智能学院，浙江 温州325035)

近年来，无线传感器(Wireless Sensor Networks，WSNs)因其广泛的应用而得到学术界和工业界的关注[1]。 其中，分层的无线传感网络由于具有可扩展性、高效通信和容错等优点而被广泛应用于大型无线传感器网络中。 在层次结构中，整个网络一般包括感知层和汇聚层。 感知层用于感知监测目标，生成感知数据，并发往汇聚层。 而汇聚层主要用于接收多个感知层采集的相关数据，汇聚这些数据并与其他汇聚层节点以多跳的方式进行通信。

感知层节点往往是一个能量受限系统。 因此，节能并尽可能地延长其工作时间，对于整个网络的性能和生存时间起着至关重要的作用[2]。 已有工作表明，无线传感器节点的主要能耗在于数据的发送与接收[3]。 而汇聚层节点的部署位置，则对感知层节点的发射功率起到决定性影响。 因此，汇聚层节点的拓扑优化对整个网络的性能会产生至关重要的影响，与之相关的研究也被广泛的展开。 文献[4]考虑感测质量，能耗和连接性因素，在有限的通信范围和网络寿命约束条件下，优化传感器节点的部署。 文献[5]对能量收集传感器节点的数量和位置进行优化，以期用最少的节点实现监测区域的全覆盖、与汇聚节点的全连接以及能量收支平衡。 文献[6]通过模糊推理机制选择合适的簇头大大降低了网络的能耗。 文献[7]提出一种基于非合作博弈理论的无线传感器网络覆盖控制算法，算法提供合理的网络节点覆盖率并保证能量效率。 文献[8]为了有效提高无线传感器网络的节点覆盖率，提出一种基于混合策略改进蚁狮算法的网络覆盖优化方法。 文献[9]提出了一种基于改进鲸鱼优化算法的网络覆盖优化策略，有效减少了传感器节点冗余。文献[10]提出了一种基于第二代快速非支配遗传算法的多目标优化方案，将汇聚层节点的数量和总功率进行联合优化，显著减少汇聚层节点的数量，并降低了汇聚层节点的总功率。

然而，根据对相关文献的追踪，我们发现有关三维的分层无线传感器网络的优化部署机制却鲜有报道。 为此，本文研究三维环境下分层无线传感器网络中汇聚层节点的优化部署。 具体而言，即在保证感知层节点与汇聚层节点全连接的前提下，通过联合优化所有汇聚层节点的部署位置和所有感知层节点的发射功率，使得所有感知层节点的发射功率总和最小。 为了平衡感知层节点之间的能耗，本文进一步引入了感知层节点间能耗平衡约束。 另外，本文还综合考虑部署环境中不同障碍物对无线信号传播的衰减。

考虑到上述优化问题是NP-hard 的，本文采用群智能算法来寻求问题的近似最优解。 近几年，随着群智能算法的蓬勃发展，其已经被广泛地运用于复杂工程优化问题的求解[11-14]。 在众多群智能算法中，海洋捕食者算法(Marine Predators Algorithm，MPA)[15]是2020 年提出的一种新算法。 MPA 通过布朗和莱维两种策略之间的权衡模拟海洋捕食者寻找猎物的最佳觅食机制。 相比于其他群智能算法，MPA 具有参数少，收敛速度快，原理简单，并行性，易于实现等优点，并已经被用来解决连续优化的相关问题，取得了十分优越的结果[16-17]。 因此，本文选择MPA 算法来求解上述优化问题。 然而，MPA也存在着全局搜索能力较差的缺点。 针对此问题，本文在MPA 中引入混沌序列，提出了一种改进的MPA 算法，称为TMPA(Tent-Marine Predators Algorithm)。 TMPA 利用Tent 混沌序列的遍历性和混沌特性，增强了算法全局搜索能力，有效提高了算法的收敛速度。 实验结果表明，本文所提出的基于TMPA 的WSN 优化部署机制能够大幅降低网络中感知层节点的总能耗，促进感知层节点间的能耗平衡，延长网络的生存时间。

本文后续章节的安排如下:章节Ⅱ介绍了优化问题的数学模型；章节Ⅲ介绍了基于混沌序列改进的TMPA 算法；章节Ⅳ通过仿真实验论述了改进的算法；章节Ⅴ对本文的研究内容进行了总结。

1 系统模型

分层无线传感器网络的典型网络结构如图1 所示。 感知层节点(Sensing Node，SN)负责信息的收集，汇聚层节点(Convergence Node，CN)负责将多个感知层节点收集的信息进行聚合，并在不同的汇聚层节点之间通过多跳方式进行信息通讯。 本文假设待覆盖的3D 无线传感器区域为M，感知层和汇聚层节点随机分布到M中。

令SN＝{SN1，SN2，SN3，…，SNns}为感知层节点集合，其中ns表示感知层节点的数量，SNi＝{xi，yi，zi}为第i个感知层节点的位置。CN＝{CN1，CN2，CN3，…，CNnc}表示汇聚层节点集合，nc为汇聚层节点总数，CNj＝{xj，yj，zj}表示第j个汇聚层节点的位置信息。 本文假设所有汇聚层节点都有相同的接收灵敏度αo。

图1 分层无线传感器网络结构

无线信号在传播过程中，不仅存在路径损耗，而且也会在穿透障碍物时遭受到损耗。 本文无线信号的传播由如下公式给出:

本文引入如下布尔表达式l(SNi，CNj)，i∈[1，ns]，j∈[1，nc]来判断SNi是否与CNj之间存在有效的链路，即SNi是否有效覆盖CNj，具体表达式如下:

式中:pi表示第i个感知层节点的发射功率。 为了能够完整的收集数据，需要确保任一个感知节点都能够与一个汇聚节点之间存在着有效的链路。 为此，我们定义整个网络的连接率为:

显然，当所有感知节点都能够与汇聚节点之间存在着有效的链路时，LΩ＝1，即感知层实现了全连接。

另一方面，我们引入感知层节点发射功率的标准差来衡量感知层节点之间的能耗均衡性，即:

综上本文的优化问题可以概括为:在保证连接率为100%的前提下，通过联合优化所有汇聚层节点的部署位置和所有感知层节点的发射功率，使得所有感知层节点的发射功率总和最小。 并使得所有感知节点之间发射功率的标准差尽可能小，从而达到节能和能耗平衡延长网络寿命的目的。 上述优化问题的可定义如下:

式中:ε为给定的标准差阈值，约束条件C1约束了SN 与CN 实现全连接，C2约束了所有SN 的发射功率要达到能量均衡，C3约束了所有SN 的发射功率范围。

2 基于TMPA 算法的汇聚层拓扑优化

2.1 MPA 算法

MPA 算法主要涉及两种运动策略选择，莱维飞行[18]和布朗运动策略[19]。

莱维飞行是一种随机行走，使用如下函数根据莱维分布生成随机数:

式中:RL表示基于莱维分布的随机数，a～N(0，)，b～N(0，1)，λ＝1.5，σa由如下公式计算:

式中:Γ代表伽马函数，对于整数λ，Γ(1＋λ)＝λ!。

布朗运动是一种随机过程，他们是来自均值为0，方差为1 的高斯分布。

根据达尔文适者生存理论，自然界中顶级捕食者在寻找食物时更具有竞争力，我们用Ttop表示顶级捕食者。 将其复制n次以构建捕食者矩阵E，表示如下:

另一个具有与捕食者矩阵相同维度的矩阵是猎物矩阵。 捕食者用该矩阵来更新自己的位置。 猎物矩阵表示如下:

式中:Xi＝[Xi，1，Xi，2，…，Xi，d]，Xi，j表示猎物矩阵第i个体的第j维度。 用如下公式初始化猎物矩阵:

式中:Xmin，Xmax为优化问题中解空间的下界和上界，rand( )为(0，1)中的随机数。 计算每个捕食者个体的适应度，最优解被指定为顶级捕食者。

MPA 将整个算法过程分为三个阶段。 我们用当前迭代次数k和最大迭代次数Mmax比较来映射。

2.1.1 MPA 算法第一阶段

此阶段主要用于解空间的全局搜索。 具体过程如下:

式中:θ＝0.5 是一个常数，S表示猎物移动步长，R是(0，1)中均匀随机数向量。RB是基于标准正态分布的向量，用其表示布朗运动。 ⊗表示向量中元素依次相乘。

2.1.2 MPA 算法第二阶段

此阶段由对解空间的全局搜索转向对解空间的当前最优解位置进行局部搜索过渡。 具体过程如下:

式中:RL是基于莱维分布的随机数向量，表示莱维飞行，由式(6)计算。 CF 根据k的增加会发生改变，由如下公式计算:

式中:k表示当前迭代次数，CF 作为控制捕食者移动步长的自适应参数。

2.1.3 MPA 算法第三阶段

此阶段主要对于解空间当前最优解位置进行局部搜索。 具体过程如下:

2.1.4 MPA 算法FADs 效应

FA Ds(Fish Aggregating Devices)效应主要用来跳出算法局部最优解。 FADs 效应数学表达式如下:

式中:FA＝0.2，U是二进制向量包括0 和1。 通过在(0，1) 中生成一个随机向量，将向量中的数值与FA进行比较，若数值大于FA则将此数值更改为0，反之将其数值更改为1。r是(0，1) 中的随机数，r1 和r2 下标表示猎物矩阵的随机索引向量。

2.2 基于Tent 映射的MPA 优化算法

为了进一步增加MPA 算法的搜索能力，本文将Tent 混沌序列引入MPA 算法中，利用混沌序列的特性有效提高MPA 算法的最优解位置局部搜索能力。混沌运动是非重复的，因此比随机搜索具有更高的搜索速度。 混沌具有伪随机性、遍历性和对初值敏感的特性。 Tent 映射和Logistic 映射是被广泛研究的一维混沌动态系统。 文献[20]通过严格的数学推理证明了Tent 映射的遍历均匀性和收敛速度均优于Logistic 映射，因此本文选择Tent 混沌映射。为了避免Tent 混沌序列中小周期和不稳定周期点现象的发生影响算法的性能，本文采用文献[21]中的改进表达式:

上式通过贝努利移位变换后表示为:

式中:Nt表示Tent 序列的长度，t＝1，2，…，Nt为混沌元素的索引，mod1 表示取除数小数点后的数值。

我们在顶级捕食者中随机取一维数据，对所取位置进行一维混沌遍历搜索。 通过一维混沌遍历搜索可以找到更好的解，同时保持最优解的最优维信息。 我们将此过程称为Tent 混沌一维扰动策略，其表达式如下:

值得注意的是，MPA 算法的计算复杂度为O[Mmax×(n×d＋cof1×n)][15]，其中，cof1为函数评估的计算代价。 TMPA 算法由于引进了Tent 混沌序列，其计算复杂度为O[Mmax×(n×d＋cof1×n＋cof2×Nt)]，其中cof2为Tent 混沌扰动计算代价。

本文将TMPA 算法引入分层无线传感器网络优化问题。 其中，每个捕食者个体对应一种CN 位置部署方式。 算法具体步骤如下:

S1 获取无线传感器网络的布置区域，设定区域内的障碍物以及其衰减值。

S2 将CN 的位置坐标(x，y，z)设置为种群中的一个个体。 令种群的数量为n，算法寻优的最大迭代次数为Mmax。 第k次迭代过程中，第j个猎物群 体 的 定 义 为:其 中为汇聚节点的坐标向量。

S3 初始化猎物矩阵，由如下公式计算:

式中:Lx，Ly，Lz分别为部署区域的长，宽和高。

S4 在第k次迭代时，根据当前CN 和SN 的位置，计算在连接率为1 的情况下每个SN 的最低发射功率:

式中:pi，k表示第k次迭代时第i个感知层节点的发射功率。 显然，pi，k＝β＋αo，i＝1，2，…，ns。 令为Pk向量所有元素的均值。 我们随机生成一个和Pk相同维度的向量，并取向量和P对应位置中较大的数据组成向量Pmin。 将所得到的Pmin代入如下适应度函数:

式中:η为不满足约束条件下的惩罚因子，不满足中三个约束的任何一个，则惩罚因子是一个充分大的正整数，反之为0。

S5 根据所求的适应度函数值，求出适应度最优的个体作为顶级捕食者Ttop，利用公式对其进行Tent 混沌一维扰动策略。 比较扰动前后个体的适应度，取适应度低的个体。

S6 将顶级捕食者复制n次构建捕食者矩阵。

S7 利用式(11)～式(13)、式(15)实现CN 位置的优化。

S8 再次求出适应度最优的个体作为顶级捕食者Ttop，利用式(18)对其进行Tent 混沌一维扰动策略。比较扰动前后个体的适应度，取适应度低的个体。

S9 执行FADs 效应，k＝k＋1。 若k≤Mmax，则返回S4。

S10 输出最优的CN 位置坐标和所有SN 的发射功率。

3 仿真优化结果

3.1 TMPA 性能评估

本文首先对所提出的TMPA 算法的性能进行评估。 本文采用9 个不同类型的基准函数进行测试，其中包括3 个高维单峰函数TF1-TF3，3 个高维多峰函数TF4-TF6，3 个混合函数TF7-TF9。 如表1所示。 运行测试的系统环境如下:Intel(R)Core(TM)i7-8700 CPU，主频为3.20 GHz，内存为16.00 GB，Windows 10 系统和MATLAB R2019a。 实验中的种群大小为50，最大迭代次数为500 次。 为了避免实验数据的偶然性，各基准函数独立运行30 次，并将各个算法所求得的函数最优值的平均值与标准差作为最终的评价指标。

表1 基准函数信息

考虑到文献[15]中已将MPA 与其他群智能算法(包括遗传算法、粒子群算法、引力搜索算法、布谷鸟搜索算法、樽海鞘算法、协方差矩阵适应演化策略算法、适应差分进化算法、基于欧氏邻域的集成正弦微分协方差矩阵自适应算法)进行了性能对比，并证明了MPA 优于这些算法。 因此，本文额外选取了鲸鱼优化算法[22]和果蝇优化算法[23]作为比较对象。 测试结果表明:对于所有的测试函数，TMPA 算法所求函数最优值的平均值和标准差都优于MPA。这同样可以充分地说明TMPA 也优于文献[15]中所对比的群智能算法。 而对于本文对比的算法，除了TF1，TF2，TF6这三个函数的平均值和标准差略低于鲸鱼优化算法，其余实验结果都优于对比的算法。

TMPA 算法高效的寻优能力与TMPA 算法的特性有关。 TMPA 可以对最优解的某一维度进行一维混沌遍历搜索。 通过一维混沌遍历可以找到更好的解，同时保持最优解的最优维信息，这种改动大大提高了MPA 算法的寻优精度与稳定性。

表2 基准函数优化结果比较

3.2 基于TMPA 的分层WSN 优化部署机制的性能测试

本文考虑100 m×100 m×10 m 的部署区域M，其中感知层节点随机散布到M 中，汇聚层节点均匀分布到M 中。 如图2 所示，其中菱形点是汇聚层节点，圆点是感知层节点，图中存在三种不同的障碍物。 除了特别说明，本文实验仿真所采用的参数如表3 所示。

图2 仿真区域初始化

表3 仿真实验参数值

图3 显示了汇聚层节点总个数为24，感知层节点总个数为200 的情况下，经过500 次迭代计算后，MPA 和TMPA 的算法收敛图。 我们可以看出，MPA算法在375 次迭代附近达到了收敛，而TMPA 算法在第75 次迭代附近就已经达到了收敛并且感知层节点发射功率总和更低。 这表明TMPA 比MPA 具有更强的收敛性能。 图4 则显示了经过优化以后的汇聚层节点的分布及其与感知层节点之间的连接情况。

图3 TMPA 和MPA 算法收敛曲线对比图

图4 TMPA 算法优化网络数据连接图

我们将经过优化部署后的节点功耗和连接率与传统均匀部署情况下的节点功耗和连接率进行了对比。 对比结果见表4。 从中我们可以看出，nc为24时，经过本文所提出的优化部署机制优化后，当保证连接率为100% 时， 感知层节点的总功率为423.64 mW，仅为传统均匀部署方案下的46.91%。随后，我们考察当感知层节点总发射功率同样为423.64 mW 时，均匀部署的覆盖率。 为此，我们以0.001 mW 为步长，逐渐增加感知层节点的发射功率。 对于任一个感知层节点，当能够与某一个汇聚层节点连通时，其发射功率就停止增加。 直到所有的功率分配完为止。 此时，均匀部署情况下，连接率仅为66%。 即，本文所提出的优化部署机制能够将连接率提高34%。

此外，在保证100%的连接率的前提下，我们考察了nc为30 和36 时，TMPA 和MPA 优化部署情况。 表4 数据表明，nc为30 和36 时，TMPA 优化部署相对于MPA 部署，感知层节点总功率都下降了约15%。 实验结果也体现了TMPA 优化部署相对于原算法高效的寻优能力。 我们同样考察了nc为30 和36 的情况下，感知层节点总发射功率同样为275.09 mW 和235.25 mW 时，均匀部署的覆盖率。此时，均匀部署情况下，连接率仅为49%和45.5%。经过TMPA 优化部署后的连接率能得到极大的提升。

表4 汇聚层节点位置部署方案对比

我们进一步评估了网络节点存活率。 假设每个感知层节点都具有相同的总能量(1×104J)，且每个感知层节点每秒进行10 ms 的数据传输。 我们比较均匀部署和TMPA 算法优化情况下节点的存活率情况。

图5 不同部署情况下感知层节点存活率图

若感知层节点的能量损耗完毕，则认定此感知层节点死亡。 假设当整个网络中有30%的感知层节点死亡，则此网络不能继续工作。 仿真具体结果如图5 所示。 可以发现，经过优化部署后的网络中，节点死亡的速率显著慢于均匀部署的情况。 均匀部署的网络在大约2.8×106s 后将停止工作，而TMPA算法优化后的网络则能够持续工作到5.65×106s，生存时间提高了2 倍。

4 总结

为了降低分层无线传感器网络中感知节点的能耗，以及提高感知节点间的能耗平衡，以延长网络的生存时间。 本文主要研究了3D 环境下分层无线传感器网络优化部署机制，即在保证感知层节点全连接的前提下，以感知层节点间发射功率平衡性为约束。 通过对汇聚层节点部署位置和感知层节点发射功率的 联合优化，使得感知层节点总发射功率最小。

本文首先建立了上述问题的数学优化模型。 为了求解这个优化问题，本文在MPA 算法的基础上，引入Tent 混沌映射，提出了TMPA 算法。 9 个基准函数的测试结果表明TMPA 比MPA 具有更强的收敛能力。 然后，我们提出了基于TMPA 的3D 环境下分层无线传感器网络优化部署机制。 实验结果表明，该优化部署机制能够极大降低网络中感知层节点的总能耗，促进感知层节点间的能耗平衡，延长网络的生存时间。

在后续的工作中，我们将进一步考虑将汇聚层节点的数量联合感知层节点的位置和发射功率对传感器网络做进一步的优化，使本文所提算法能够应用于更多的场景。