基于MOEA/P的无线传感器网络节点部署研究

刘 俊，金世尧，陈未如，彭弗楠*

(1.沈阳化工大学 计算机科学与技术学院，辽宁 沈阳 110142；2.沈阳化工大学 辽宁省化工过程工业智能化技术重点实验室，辽宁 沈阳 110142)

0 引言

如今，无线传感器网络(WSN)在军事、农业、医疗卫生、环境监控、智能家居和照明等方面有很大的潜在应用价值，尤其在无人监测或环境恶劣情况下的事件监测和事件跟踪中显示了很大的优势[1-2]。在这些应用中，往往需要部署成千上万个互连节点用以保证服务质量(QoS)，这种高密度情况下很难找到最佳部署位置。一般来说，评价传感器网络质量的指标大都是相互冲突的，如何部署大量传感器节点以满足多个目标的应用需求成为一个多目标问题[3]。

近年来，研究者提出了许多不同假设、目标和模型的WSN部署方法，其中遗传算法(GA)被大量使用[4-5]。GA大体可以分为3类：基于Pareto支配关系的遗传算法、基于性能指标的遗传算法和基于分解的遗传算法。张亮和黄郡[6]采用了模糊粒子群优化算法，优化目标为感应覆盖率和节点数量，并且采用的感应模型贴近实际情况，取得了不错的结果。胡坚等人[7]针对水质监测无线传感器随机部署网络覆盖率低的问题，采用了一种改进的布谷鸟搜索算法，可以适应水下部署环境，提升了传感器节点部署优化能力。陈欣等人[8]针对无线传感器网络中目标节点部署能力差的问题，提出了基于生物地理学优化算法的节点部署方案。该方案能够在网络中找到满足K-覆盖和M-连通性要求的传感器节点最佳部署位置。这些算法各有各的优势和侧重，但是它们都没有面向目标决策支持在指定方向上进行专门有效的求解。

本文采用的多目标优化算法采用了基于投影面的多目标优化问题进化算法(MOEA/P)，借鉴基于分解的多目标进化算法思想，将目标空间分成投影面和自由维，根据求解需求把投影面分解成多个投影格，并在各个投影格上求解自由维的最优值，从而得到多目标优化问题的最优解。在本算法应用中，可以根据用户的决策方向，有指导地选择相应的投影格进行最优求解，既能够保证求解的精度，又能够保证所得解满足用户决策支持需求。

1 问题描述

1.1 部署空间

本文选用的部署区域为沈阳化工大学致本楼的一个走廊，楼层建筑平面如图1所示，实际部署区域是一个328 m2的走廊,如图2所示。

图2 实际部署区域Fig.2 Actual deployment area

为了解决WSN节点部署优化问题，需要对部署空间精确建模。将部署空间划分成边长为1 m的网格，其中每个单元格的质心可以选择部署传感器节点(Sensor Node)或者汇聚节点(Sink Node)，也可以选择同时部署。另外，选择的部署区域中可能包含不同的障碍，例如墙、地板等。无线电信号通过这些障碍物时会导致信号衰减或者感应阻塞，会影响无线电信号的传播和感应能力。

在选用的部署区域中，存在3种类型的障碍(水泥墙、玻璃窗户和不锈钢防盗门)，为了获得更准确的实验结果，首先测量信号在通过这3种障碍时引起的不同衰减值，测试结果如表1所示。

表1 障碍物衰减实际测量值Tab.1 Actual measurements of obstacle attenuation

定义障碍物为Ok，其中k为障碍物的类型。假设ci,j与ci’,j’为部署空间内的2个单元格，定义ci,j与ci’,j’质心之间连线是否存在障碍Ok的函数为：

(1)

1.2 网络感应覆盖

已有研究证明，实际的传感器节点不会在每个方向上提供相同的感应能力[9]，因此二元感应模型[10-11]并不能代表传感器的真实感应能力。在概率模型中，埃尔夫斯模型[11]考虑了传感器的距离和硬件参数方面的感应退化，代表了更现实的感应能力。此外，埃尔夫斯模型还引入了感应不确定性，更贴近传感器的真实感应情况。因此，本文选择埃尔夫斯概率模型：

(2)

式中，d为事件与传感器的距离；γ和β为传感器硬件参数；Rmin和Rmax分别为100%感应半径和最大感应半径。

本文研究的网络拓扑结构为星形结构，每个传感器在其感应范围内监测事件并且向距离最近的汇聚节点共享信息。为了使得出部署方案更加灵活，本文根据用户的偏好来评估感应覆盖范围。假设Pcov为用户可以接受的感应概率，si,j为距离单元格ci,j最近的传感器节点位置，d(ci,j,si,j)为单元格ci,j到传感器节点si,j的欧式距离，通过式(3)可以得出P(d(ci,j,si,j))即为ci,j被si,j感应的概率。感应覆盖矩阵cov(ci,j)可以表示为：

(3)

假设部署区域是由X个单元格构成，本文采用的感应覆盖率PS为：

(4)

1.3 网络连通性

目前文献中最常用的连通模型有3种：FSPL[12]，1SM[13]和MWF[14]。FSPL模型基础的传播模型适用于理想化环境，只考虑了光线对无线电传播的影响；1SM则一般不考虑室内环境；而WMF考虑了因墙壁和地板穿透引起的衰减，并且易于实施。本文选择WMF作为实验的无线电传播模型。假设L0为参考距离1 m处的衰减，3种类型障碍引起的衰减为a(Ok)，η为路径损耗因子，节点ni,j与ni′,j′之间路径损耗为：

(5)

在无线电传播过程中，假设信号发射点为bi′,j′,该点发射信号强度为PTX，接收点为ni，j,该点接收信号强度为RSSI(i,j)，发射信号强度与接收信号强度之间的关系表示为：

RSSI(i,j)=PTX-PL(bi′,j′,ni,j)。

(6)

通过式(6)可以看出，如果单元格ni，j中计算出的RSSI(i，j)大于良好通信所需的最低信号强度Ptsh，则在对应矩阵位置取1，否则取0，可以得出连通性矩阵：

(7)

进一步得到部署区域X的连通率PSK为：

(8)

在WSN中，连通性往往作为目标之一加入算法进行优化，而本文将连通性作为MOEA/P算法的约束条件，因为连通性是保证部署方案有效性的前提条件，如果节点之间不连通，则感应数据不能正常进行传输，部署方案将无意义。

1.4 部署成本

WSN中需要考虑成本问题。假设一个感应节点的安装成本和采购成本之和为CS，一个汇聚节点的采购和安装成本为CSK，‖S‖为部署的传感器节点总量，‖SK‖为部署的汇聚节点总量，该区域部署成本为：

CostX=CS×‖S‖+CSK×‖SK‖。

(9)

由于在部署过程中成本是固定的，为了简化计算，假设部署感应节点的成本与部署汇聚节点的成本相同，基于部署空间的定义，可以得出部署成本的矩阵为：

(10)

然后得到部署成本的计算公式为：

CostX=∑i∑jD(i,j)。

(11)

1.5 过度覆盖

在实际部署情况中，一个单元格可能在多个传感器的感应覆盖范围内，造成覆盖冗余，这种情况称为过度覆盖[15]。一般情况下，部署过程中应该尽量减少过度覆盖的范围，也就是使覆盖冗余最小化，以避免能源浪费和降低部署成本。过度覆盖矩阵可以表示为：

(12)

过度覆盖率Pov是过度覆盖单元格数量与总单元数量的比率：

(13)

但是在一些特定的应用场景中，比如火山检测，有些应用需要用K个传感器来覆盖一个单元格，称为K-覆盖(K-cov)。通过保证K-覆盖率，即使K-1个节点出现故障，部署空间仍然被覆盖。K-覆盖的矩阵可以表示为：

(14)

K-覆盖率为：

(15)

2 MOEA/P

2.1 MOEA/P相关概念

为了统一计算尺度，保证在各个目标方向上的计算均衡，需要进行目标空间归一化[16]，这是许多算法都采用的方式。本文此后讨论的目标向量值都缺省设定为归一化后的值。为了减少所得解的数量，得到有一定代表性的较小的解集。MOEA/P[17]将目标空间分解为2部分：投影面和自由维。

定义1投影面：根据目标决策需求选取部分主要目标维构成投影面(Projection Plane)，投影面上的各目标维称为投影维(Projection Dimension)。

投影面P是多目标函数集F的纯子集，即P⊂F。一般选取前m-1维目标作为投影面进行算法实验分析，但是在WSN中，投影维的设置与应用需求有关，重要的目标被设置成投影维并分段，个体被进一步分格细化，再经过自由维筛选可以得到更优的解。

例如在要求高覆盖率低成本的监控场景中，覆盖率目标和成本目标非常重要，这两维会被优先设置为投影维。对于二目标优化问题，投影面就是一条坐标轴；对于三目标优化问题，投影维就是2个目标构成的一个坐标面，如图3所示。

图3 三维目标下自由维与投影面的关系Fig.3 Relationship between free dimension and projection plane under three-dimensional objectives

定义2自由维：除投影面外的目标空间其他维称为自由维(Free Dimension，fd)，由所有自由维所组成的集合称为自由维集(Free Dimension Set，D)。

本文对于给定目标解向量F在投影面上的投影记为Fp，在自由维集上的投影记为Fd。自由维的设置同样需要考虑部署环境。

定义3投影格：将投影面分割成一个个子面，称为投影格(Projection Grid，PG)，用其核心点作为标识向量——投影格向量(Projection Grid Vector，Vg)，下面将投影格向量简称为投影格。Vg由组成投影面的各维度值构成。

本文实验采用的MOEA/P算法求得落在指定投影面上的目标向量后，以该投影面所限定的目标子空间进化求解自由维最优解。为此给出如下定义和定理。

2.2 个体编码

假设ci,j为待部署区域中的任意一个单元格，i和j分别对应部署区域的横坐标和纵坐标，单元格内未部署节点用0来表示，部署传感器节点用1来表示，部署汇聚节点用2来表示，同时部署传感器节点与汇聚节点用3来表示，从形式上来说，ci,j内部署情况可能有4种：

①ci,j=<0>，单元格内无节点部署；

②ci,j=<1>，单元格内部署一个传感器节点；

③ci,j=<2>，单元格内部署一个汇聚节点；

④ci,j=<3>，单元格内同时部署了一个传感器节点和一个汇聚节点。

假设部署区域如图4所示。

该部署区域的染色体表示为[0，2，3，1，0，1]。

2.3 目标空间划分及初始化种群

目标决策空间的设定将最优化求解空间设定到了一个较小的范围之内，可以大大缩小计算时间并提高计算精度。投影面选定之后，需要根据投影格边长对投影面进行分割，以便进一步求解。投影格由相应的投影格标识向量所标定，对投影面进行分割就是要生成相应的投影格向量，其算法如下。

MOEA/P算法框架输入:·多目标问题MOP;·结束条件;·DS:目标决策空间(投影面)设定;·ω:投影格边长;·ε:投影格影响半径(容忍量);·S:初始种群大小。输出:目标解集OP过程:·步骤 1) 目标空间划分 根据DS确定MOP投影面及投影范围,并将之分割成边长为F的多个投影格PGs; 设目标解集OP为空。·步骤 2) 在每个投影格上求非ε-Pareto投影格支配解 对于PGs的每一个投影格,执行步骤2.1^2.3: 步骤 2.1) 初始化种群 初始化长度为S的种群G,构造种群中个体并初始个体基因序列,保证所有个体满足MOP约束条件; 对种群G每个个体进行初始计算,得到相应的目标函数值。 步骤 2.2) 种群进化: 如果满足结束条件,转步骤2.3; 设置新一代备选列表GenPOOL; 分别对种群G中的个体进化操作; 计算每一个新生成个体并根据适度优先关系并将之按序加入GenPOOL中; 令G=GenPOOL; 对G进行截断操作; 重复本步骤2.2。 步骤 2.3) 提交进化结果 将G中所有非ε-Pareto投影格支配个体提交到OP,并保证不与OP中任何现有个体相互Pareto支配。若存在Pareto支配关系对,从OP中删去被支配的个体。 步骤 3) 输出OP

根据目标决策空间(投影面)确定多目标问题MOP投影面及投影范围，并将之分割成边长为F的多个投影格PGs；设目标解集OP为空。初始化长度为S的种群G，构造种群中的个体并初始个体基因序列，保证所有个体满足MOP约束条件,本文实验的约束条件是连通性。

2.4 进化计算

由于多目标优化问题最优解在大部分空间的连续性，MOEA/P算法的进化计算采取“计划生育模式”：

① 按个体排序优先次序，从1～0确定各个种群个体的选择概率，进入到下一代的备选列表中；

② 每个个体要与其他个体交叉繁殖2个后代，使这2个后代分别继承父母的前后2段不同基因；

③ 每个个体在所有基因位(决策变量)上都有变异的机会，使得个体可以能够有机会跳出本地局限寻求全局最优；

④ 引入一种新的变异机制——振荡，它使得每个个体在所有基因位上都有一次机会以原基因位值为中心的上下振荡，以逐步向最优解靠近；

⑤ 所有新生成的个体都应满足MOP约束条件才能进入下一代的备选列表中；

⑥ 当一次进化没有得到足够多的有效新个体时，进化将提前结束。

2.5 算法框架

投影维设置方案平均运行时间/s(偏差)平均IGD(偏差)平均出现解的个数设置成本和过度覆盖率为投影维110.624(6.368)9.807(2.348)28.5设置成本和覆盖率为投影维116.666(2.866)9.652(1.658)32.1设置覆盖率和过度覆盖率为投影维153.653(8.823)28.957(4.06)6.42

3 实验与讨论

本文实验设备是一台配备Intel(R) Core(TM) i7-5700U CPU，2.4 GHz处理器和12 GB内存的电脑。将连通性作为约束条件，将成本、覆盖率和过度覆盖率作为MOEA/P算法的3个目标进行优化。在运行模拟部署之前，WSN决策者必须指定不同的参数，例如部署空间坐标及其特征、节点类型、所使用的协议、考虑的拓扑和设计者偏好等，这些参数被格式化为算法的初始条件。

本文实验区域选择的是一块328 m2的区域，采用的感知模型是埃尔弗斯概率模型，γ设置为0.1，β设置为2.2。无线电传播模型选择修正后的WMF模型，为了匹配实际测量值，η设置为1.7。一般部署目标是实现成本最小、覆盖率最大，在此需求下，第1次实验将任意2个目标作为投影维且均分为3段，这样投影格数量固定在9个，种群大小和迭代次数均设置成200，运行20次取均值对比讨论投影维与自由维最佳设定。作为对比，事先将本文提出的模型用MOEA/D算法执行20次(种群大小与迭代次数设置为2 000)，选出最好的一组解作为Pareto前沿计算反向迭代距离(IGD)来比较好坏。

在MOEA/P算法介绍中，相对重要的指标被设置为投影维。第1次实验的3个指标中，成本和覆盖率是最受用户所关注的，应该被设置为投影维如表2所示。从表2可以看出，成本和覆盖率作为投影维时解集质量和分布性最好，证实了这一点，故本文在后续实验将成本和覆盖率作为投影维。

表2 设置不同投影维结果对比Tab.2 Comparison of results of setting different projection dimensions

第2次实验同样设置种群大小与迭代次数均为200，运行20次取平均值，讨论投影维不同分段导致的结果。

投影维分段数量不同对结果的影响如表3所示。从表3可以看出，投影维分段越多，投影格格数越多，解空间被划分的越细致，越需要耗时进化，解的质量越好。投影格数量与IGD之间的关系如图5所示。从图5可以看出，当成本分段不小于覆盖性分段时，IGD的值更小，这是因为本文选用的部署区域是328个单元格，部署节点数量的变化范围远小于覆盖单元格数量的变化范围，换句话说，部署节点数量的轻微变化都会对覆盖单元格数量产生较大影响，所以对成本目标(节点数量)的分段适当大于覆盖单元的分段会得到略好的结果。

表3 投影维分段数量不同对结果的影响Tab.3 Impact of different number of projection dimension segments on results

图5 投影格数量与IGD之间的关系Fig.5 Relationship between the number of projection grids and IGD

第3次实验讨论在同样部署区域、同样优化模型中MOEA/P与MOEA/D，NSGAII的比较结果。首先把MOEA/P迭代次数与种群大小均设置成2 000，投影维设置为成本和覆盖性，均分为10段，即100投影格，运行20次取最好的一组解作为真实Pareto前沿，通过Pareto前沿计算IGD和GD。另外使用了C-METRIC指标来评价在相同迭代次数和种群大小情况下算法的好坏。IGD主要通过计算每个在真实Pareto前沿面上的点到算法获取的个体集合之间的最小距离和，来评价算法的收敛性能和分布性能，值越小，算法的综合性能包括收敛性和分布性能越好[18]；GD是从一组候选解指向最近的真实前沿上的点的欧式距离的平均，值越小，算法的收敛性越好[18]；C-METRIC为解集覆盖率，C(A_B)表示B中被A中至少一个解支配的解的百分比[19]。

本次实验MOEA/P中算法设置成本目标和覆盖率目标为投影维，均分为3段。3种算法结果均运行20次取平均值。MOEA/P与MOEA/D，NSGAII算法比较如表4所示。从表4可以看出，在种群大小和迭代次数均为200时，MOEA/D算法执行最快，这是因为MOEA/D通过聚合函数直接把多目标优化问题转化为单目标问题；NSGAII相对来说慢一些，因为NSGAII主要是利用Pareto支配关系进行非支配排序；MOEA/P算法执行较慢，因为需要对解空间进行划分。通过IGD，GD和C-METRIC指标可以看出，MOEA/P的解更贴近真实Pareto前沿，多样性也更好。

表4 MOEA/P与MOEA/D，NSGAII算法比较Tab.4 Comparison of MOEA/P,MOEA/D and NSGAII algorithms

MOEA/P算法支持限定求解空间，第4次实验讨论设置限定空间的目标与目标作为约束条件二者的优劣。以连通性为例，分别将连通性作为目标、约束及同时作为目标和约束3种模型均在种群大小和迭代次数为200的情况下运行，与Pareto前沿进行IGD与GD的计算，结果如表5所示。

表5 目标设置为投影维或约束条件结果对比Tab.5 Comparison of results with objectives set as projection dimensions or constraints

如果连通性目标作为约束条件，在初始化种群时会生成满足约束条件的个体，经过交叉、变异后的新个体再经过筛选之后才能进入种群，这个过程比较耗时。如果采用限定求解空间的连通性目标，初始化种群时会随机生成个体，交叉、变异后生成的新个体进入种群中，迭代完成后，满足目标设定的个体输出，相对来说节省时间。

在要求覆盖性最大，节点全连通，成本与过度覆盖率最小的应用需求下，本文给出了一种部署方案，本方案采用1个sink节点和13个sensor节点；未覆盖单元格17个，覆盖率是94.82%；过度覆盖11个，过度覆盖率为3.35%，主要集中在铁质卷帘门附近，因为这个区域信号衰减比较大，需要适当过度覆盖来保证覆盖范围。节点位置如图6所示。

图6 建议的节点部署方案Fig.6 Proposed node deployment scheme

4 结束语

本文提出了一种解决WSN部署问题的新方法。首先将该问题建模为单约束三目标优化问题，在MOEA/P框架内，目标包括确定无线节点的最佳位置并确保优化传感覆盖范围、连通性、过度覆盖和成本，接着对已有文献采用的方法进行分析和物理模型的改进，最后通过实验来确定投影维的设置和其他参数。这种优化方法可以根据环境、不同应用程序的规范和用户首选项生成最佳部署，根据对多组测试数据进行各种实验对这些模拟进行的分析证实了所提出的方法的可行性和有效性。下一步的工作是引入能耗或者生存周期等指标，利用MOEA/P算法解决三维空间内的节点部署问题。