WSN中结合双层编码和JPSO的多约束Steiner树算法

常峰

（乐山师范学院 物理与电子工程学院，四川 乐山　614004）

WSN中结合双层编码和JPSO的多约束Steiner树算法

常峰

（乐山师范学院 物理与电子工程学院，四川 乐山614004）

聚合树是无线传感器网络（WSN）中的一种典型的数据聚合技术。针对多目标约束的Steiner树问题（MCSTP），提出一种基于双层编码机制（TE）和跳跃粒子群优化（JPSO）的启发式算法构建最优树结构。首先，选择总能耗、网络寿命、收敛时间和通信干扰作为优化约束目标。然后，根据提出的双层编码方案对生成树的解进行编码，同时利用跳跃粒子群优化算法寻找帕累托最优解。最后，利用提出的混合适应度函数找出近似最优树结构。实验结果表明，JPSO-TE方法可以产生近似最优的树结构，具有高效性和可行性。

无线传感器网络；多约束Steiner树；跳跃粒子群优化；双层编码

0　引　言

无线传感器网络（Wireless Sensor Network，WSN）是由多个静态传感器组成，通过无线介质连接，执行物理世界的分布式感知、数据处理和决策［1］。由于传感器经常密集部署，使得相邻节点所采集的数据存在一定的冗余，如果直接从源节点向sink节点传输数据，会导致很高的通信负载。因此，在传输过程中需要进行数据聚合。聚合树作为一种典型的技术广泛应用于事件聚合中，源节点发送原始数据给中继节点，中继节点消除冗余数据，再将聚合结果转发给其他中继节点，直到到达sink节点［2］。然而，选择哪些传感器作为中继节点可以抽象描述为一种NP-完全的组合优化问题，称为Steiner树问题（SteinerTree Problem，STP）［3］。即在一个给定的加权图中找出一个包含所有终端（sink和源节点）的最小权值的连通子图。为了得到有效的聚合树，多个性能指标被用来构建树结构，其中，能源消耗、收敛时间、网络寿命和通道信号干扰是常见的性能标准［4-5］。当需要考虑多个约束时，建立聚合树就变成一个多目标约束优化问题。为了找出有效的树结构，文献［6］提出了一种基于最小生成树算法的近似算法：MST-1tRNP算法。它的目的是解决WSN中的中继节点问题，也就是STP，但其优化目标单一，只可以产生总链路成本最低的树结构。文献［7］提出另一种基于遗传算法的近似算法：M-REST算法，解决多目标的中继节点问题。然而，其模型中没有考虑数据聚合功能，且只考虑了两个目标。此外，在这种结构中，编码方案效率低，需要特定的破圈法来保持解的可行性。

本文将多目标优化和Steiner树的组合问题称为多目标约束优化Steiner树问题（Multi-constraint Optimization STP，MCSTP）。提出一种基于特定双层编码（Two-Layer Encoding，TE）机制和跳跃粒子群优化（Jump Particle Swarm Optimization，JPSO）的启发式算法（JPSO-TE），在多项式时间内找出MCSTP问题的近似最优解。

1　问题描述和定义

为了分析MCSTP模型，本文假设网络拓扑结构是静态的，两个节点之间的通信链路是对称的，且每个节点的传输距离有限，聚合功能在生成树的中间节点上自动执行。

1.1网络模型

WSN可建模为一个无向图G（V，E ），其中V是传感器的集合，并均匀或随机地分布在监测区域，|V|值为n，E表示节点之间的连接。设定源节点的数量为m（m＼＜n），网络中只有一个sink节点，网络中的中继节点可被视为Steiner节点SN（|SN|≤（n-m）），生成树被定义为Tree（Vm+SN，Em+SN）。此外，一些没有源数据的传感器节点也可以用来中继数据。

1.2多目标约束优化

多目标约束优化是一种期望多个目标函数得到平等处理的框架模型。在大部分文献中，只考虑一个或两个目标，其中最常见的是能耗和延迟，忽视了其他重要的目标。本文对常见的应用需求进行总结，选择出四个最重要的目标，描述如下。

目标1：最小化树的总能耗。总能源消耗值 f1（x）为树中所有节点的能耗，表达式为：

式中：Cnum表示子节点的数量；ETX，ERX，EDA分别表示节点发送、接收和数据聚合所消耗的能量。

目标2：最大化树的网络寿命。网络的生命周期是指聚合树能够保持正常功能的时间段，即为中继节点的最小寿命。为了方便后续加权比较，定义寿命 f2（x）为真实寿命的倒数，表达式为：

目标3：最小化树聚合的延迟。数据聚合的延迟为从第一个源节点到sink节点传输数据包所需的时间，延迟时间函数 f3（）x表达式为：

目标4：最小化树聚合的通信干扰。链路干扰被定义为受通信影响的节点数量，干扰函数 f4（x）表达式为：

2　提出的JPSO-TE方案

2.1JPSO-TE算法描述

跳跃粒子群优化（JPSO）算法是离散粒子群优化（DPSO）算法的变种。JPSO将更新方程的权重表示为概率，每个粒子在每次迭代中都会向吸引子引导的方向移动，从一个解跳跃至另一个解。

JPSO算法中每个粒子代表一种树结构的解决方案，要解决MCSTP问题，主要的难点是设计高效的编码方案和进化算子。对于MCSTP问题，对编码方案有两个要求。首先，编码可以在不完全图上进化。第二，Steiner树中所涉及的节点编码是可变的，编码不仅可以在所有节点的完整集合上进化，而且在节点的不同子集上也可以进化。为了有效的进化，本文提出利用双层编码方案保证粒子在可行解空间内飞行。JPSO-TE算法如下所述：

算法1：JPSO-TE算法

输入：G（V，E）

输出：Tree

Initialize（P1，P2，…，Pj）；

while找出最优树do

for每个粒子Pjdo

R=random（）；

ifC0＜R≤C0+C1then

flag =match（Pj，Bj，layer1）；

Pj=Particle_Flying（Pj，Bj，flag）；

else ifC0+C1＜Rthen

flag =match（Pj，Gs，layer1）；

Pj=Particle_Flying（Pj，Gs，flag）；

end if

Pj=Particle_Repair（Pj）；

Fitness_Evaluation（Pj）；

Individual_Best（Bj）；

end for

Global_Best（Gs）；

end while

Tree=TCR_Decoder（Gs）；

JPSO-TE算法中，Particle_Flying（粒子飞行）是进化算子，Particle_Repair（粒子修复）用于修剪树形结构，消除当前不合格的叶节点，确保粒子的可行性。TCR_Decoder（TCR解码器）用来将粒子编码转换为树结构。

2.2粒子双层编码

无论树结构怎样变化，它必须遵守一个约束，即生成树的终端必须是sink节点和源节点，所有源节点必须包含在树中，Steiner节点作为中继节点来中继和聚合数据。为了产生细粒度解决方案，本文提出一种双层编码方案，设定节点总数为n，源节点数为m。编码方案示例如图1所示。

图1　生成树编码示例

第一层，以一个二进制字符串作为候选节点的Steiner标志。图 1中，Steiner节点的候选数量为n-m=17，按节点序号排列对其进行二进制编码，1表示相应节点被选为Steiner节点，0表示不被选择。

第二层是在第一层内容的基础上形成的，并完善成可行解。本文在第二层中利用S.M.Soak提出边窗编码（Edge Window Decoder，EWD）方案［8］来编码粒子代表。利用树构建算法（Tree-construction Algorithm，TCR）对子图直接解码，TCR解码器将输入的字符串解码成一个独一无二的生成树。TCR解码过程的例子如图2所示，编码中的数字为节点ID，以相邻两个节点为边构造树，树结构中的所有边不能形成循环结构，如图中虚线所示。若EWD编码长度为2（n-1），则能够表示出所涉及节点NSm（NSn的子集，|NSn|为n）的所有可能Steiner树结构，所以本文定义EWD编码的长度为2（n-1）。

图2　EWD译码过程实例（构建树）

2.3粒子飞行

传统粒子飞行算法是利用特定的进化操作来确保粒子在可行解空间不停的飞行。这个操作可以继承吸引子（当前最佳粒子）的部分树状结构，并探索最佳位置。然而，该操作是单向的，只能改善当前粒子。本文中，将两个编码层的代表粒度进行对比，根据对比结果以不同的方式实现进化操作。当两编码层代表粒度相同时，第一层保持不变，第二层开始以细粒度分级来构建结构。当两个编码层不相同时，进化操作在第一层执行，同时执行额外的操作改善对父辈树结构的继承性。

本文Particle_Flying算法中，Oi是后代，和分别为父辈的第一层和第二层，和分别为最优解的第一层和第二层。如果第一层编码是相同的，则在第二层执行原始EWD进化操作，进行相邻节点自适应交叉和突变。否则，对和进行局部OR操作产生后代Oi的第一层，同时对和解码获得TreePi和TreeBi。在Residual选择中，只有一个边的两个终端都是Oi的Steiner节点，才能被导入边集合Edges。为了更好地继承父代优良结构，根据Intersection和Edges产生一个新的树TreeOi，再将TreeOi转换成EWD编码。最后，形成由两层编码组成的新的子代，其中部分树结构从父辈继承。

2.4适应度函数

适应度函数用来评估解决方案在进化算法中的性能。目前，针对多目标优化有两个传统的适应度函数：帕累托最优度与加权和。帕累托方法只考虑帕累托支配解和非支配解之间的鉴别，没有考虑非支配解之间的差异。加权和方法弥补了这一缺点，然而其对多个目标的权重分配是不合理的。

鉴于以上原因，本文提出一种自适应混合函数来评估解决方案，融合了两个传统适应度函数的优点。如果x是当前可行解，设定第i个目标的当前适应度值为fi（x），和代表第i个目标的最大值和最小值。在每个进化周期后，会更新相关的适应度函数。加权和适应度函数表达式为：

总适应度值为各目标函数的加权和，根据各目标函数 fi（x）的表达式可知，fi（x）值越小越好，即总适应度值越小，整个网络结构性能越好。在加权和的同时，帕累托度函数P（x）被引入作为分段函数。如果x是非支配解，则P（x）=0否则P（x）=1。最终的混合适应度函数是由这两部分组成，其表达式为：

这种混合函数弥补了传统加权函数的局限性，有助于在帕累托前沿获得最佳解决方案。

3　实验及分析

利用NS2仿真工具进行大量实验，评估本文提出的JPSO-TE算法的高效性和可行性。传感器节点被分布在100 m×100 m区域内，其中只有一个sink节点，传感器节点总数和源节点数量都是可变的，每个节点的传输范围为25 m。能耗参数设定为：ERX=k·50 nJ/b，ETX=k·（50+0.1d2）nJ/b，EDA=5 nJ/b，k=4 000 b。

图3中描述了在一个随机分布下，JPSO-TE方法获得的多目标Steiner树结构的例子，其中方节点、圆节点和三角形节点分别表示源节点、中继节点和sink节点。

图3　多目标Steiner树结构

本文将混合适应度值作为衡量多目标优化近似算法的性能指标。不同方法在不同源节点数量下的适应度值如图4所示。图4中，在其他参数不变的情况下，适应度值会随着源节点数目的增加而变大，但增长率会逐渐下降。这是由于越来越多的源节点显示为较高成本，且生成树的尺寸不断增大，各目标函数值增大，造成更高的适应度值。另外，在一定的限制区间内，源节点越多意味着源节点成为中继节点的可能性增加，普通节点被选择作为中继节点的几率减小，这就减缓了适应度值的增长率。与文献［6］和文献［7］方法相比，本文JPSO-TE方法具有最低的适应度值，表明能够构建出更优的树结构。

图4　不同源节点数量下，三种方案的适应度值

为了独立评估本文提出的编码方案，将现有的两个基于树的编码方案（Prufer编码、边集编码）和本文双层编码方案进行比较。图5所示为三种编码方案下，解的质量的箱线图。JPSO-TE的上四分位数、中位数和下四分位数都较小，表明解决方案接近于理论最优解。同时，JPSO-TE的上下四分位范围较小，意味着粒子的飞行轨迹更集中在最优解周围。这些结果表明了在MCSTP问题中，本文提出的双层编码方案具有高效性。

图5　编码方案的比较

4　结　语

本文将WSN数据融合中寻找最优生成树问题定义为MCSTP。针对实际应用的要求，将四种指标作为聚合树的最终优化目标。提出一种基于JPSO的启发式方法，利用自定义的编码方案和进化操作求解MCSTP问题。仿真实验表明，本文方法可以产生近似最优的树结构，且性能优于其他方法。在今后工作中，将分布式实现JPSO来提高算法的收敛时间。此外，更多的性能指标将被导入多目标优化框架，满足一些特殊的实际要求。

［1］杨银堂，高翔，柴常春，等.一种WSN中的能耗优化动态路由算法［J］.西安电子科技大学学报，2010，37（5）：777-782.

［2］郭新明，赵蔷，蔡军伟.基于覆盖概率模型的无线传感器网络覆盖算法［J］.中国科技论文，2013，8（4）：316-320.

［3］范容，潘雪增，傅建庆，等.基于Steiner树的层次型无线传感器网络安全组播协议［J］.传感技术学报，2011，24（4）：601-608.

［4］YANG J，ZHANG H，LING Y，et al.Task allocation for wireless sensor network using modified binary particle swarm optimization［J］.IEEE sensors journal，2014，14（3）：882-892.

［5］TAN H O，KORPEOGLU I，STOJMENOVIC I.Computing localized power-efficient data aggregation trees for sensor networks［J］.IEEE transactions on parallel and distributed systems，2013，22（3）：489-500.

［6］LIOYD E L，XUE G.Relay node placement in wireless sensor networks［J］.IEEE transactions on computers，2007，56（1）：134-138.

［7］PEREZ A J，LABRADOR M A，WIGHTMAN P M.A multiobjective approach to the relay placement problem in WSNs［C］// Proceedings of 2011 IEEE Wireless Communications and Networking Conference.Cancun：IEEE，2011：475-480.

［8］SOAK S M，CORNE D W，AHN B H.The edge-window-decoder representation for tree-based problems［J］.IEEE transactions on evolutionary computation，2010，10（2）：124-144.

Multi-constraint Steiner tree algorithm combining two-layer encoding with JPSO in WSN

CHANG Feng
（School of Physics and Electronic Engineering，Leshan Normal University，Leshan 614004，China）

The aggregation tree is a typical data aggregation technology in wireless sensor network（WSN）.To solve the multi-constraint optimization Steiner tree problem（MCSTP），a heuristic algorithm based on two-layer encoding（TE）mechanism and jump particle swarm optimization（JPSO）algorithm is proposed to construct the optimal tree structure.The total energy consumption，network lifetime，convergence time and communication interference are selected as the optimal constraint targets.And then，the TE scheme is used to encode the solution of spanning tree，and the JPSO algorithm is used to find the Pareto optimal solution.The proposed hybrid fitness function is used to find out the approximately-optimal tree structure.The experimental results show that the JPSO-TE method can generate the approximately-optimal tree structure，and has high efficiency and feasibility.

WSN；multi-constraint Steiner tree；JPSO；two-layer encoding

TN911-34

A

1004-373X（2016）13-0015-04

10.16652/j.issn.1004-373x.2016.13.004

2015-10-09

国家自然科学基金民航联合基金重点项目（U1233202/F01）

常峰（1980—），男，四川乐山人，硕士，实验师。主要研究方向为传感器网络、自动测试技术及系统集成。