基于斯坦纳树的雷场网络大面积损坏修复策略

董文，方向，范磊，杨力，雷志刚

(1.解放军理工大学 野战工程学院，江苏 南京210007;2.中华人民共和国公安部 警卫局防爆安检中心，北京100031)

0 引言

智能雷场一般通过人工布设预先设置在具有一定正面、纵深和布雷密度的场地。如图1所示，以无线传感器网络为基础的雷场网络在战场环境下易受到敌方爆破扫雷、电磁扫雷等破坏性攻击，而导致大面积的雷场节点通信功能损坏，网络被分割成若干个互不相连的部分，智能雷场失去了整体协调攻击地面装甲目标的能力。

图1 被分割为数个互不相连的部分的受损雷场网络示意图Fig.1 Articulation of a damaged minefield network that was partitioned into multiple disjoint segments

在传统无线传感器网络中，当少量节点损坏时，通常采用调大节点功率的方式来愈合失效拓扑。然而遭受大面积节点损坏的雷场网络却无法通过该方式来愈合拓扑。目前各国都在研制具有自主移动能力的节点［1-3］，称之为中续节点。该类节点在网络完好的情况下处于休眠状态，当网络遭到破坏时，能够按照特定策略迁移至指定位置替代受损节点，由该类节点进行的拓扑修复不仅能够使全局拓扑恢复连通性，还能让恢复的网络通信路径长度变短，从而更加节省网络能耗。目前关于网络拓扑修复的研究较为薄弱，文献［4］采用STP-MSP 算法建立一颗包含网络节点和斯坦纳(Steiner)点的Steiner 树，选择并调度一些节点移动到这些Steiner 点上，从而修复网络拓扑。文献［5］采用近似算法，首先找到各相邻片区的最优Steiner 点位置，再对各点使用质心量算方法获取最优解，解决水下无线传感器网络的拓扑修复问题。文献［6］针对网络中某个节点失效而造成网络连接中断的情况，采用启发式算法CRR 指导对失效节点的邻居节点向指定地点移动，从而恢复网络连通性，并且恢复后的网络拥有更好的负载均衡性。

离散量子粒子群优化算法是由Yang 等于2004年提出的［7］，是量子粒子群优化算法在离散问题上的改进算法。算法将量子粒子群算法中的粒子离散化，成为离散的粒子矢量。蛙跳优化算法在离散问题上的应用是由Martinez-Garcia 等于2008年提出的［8］，蛙跳优化算法的原理是，将整个青蛙群体按照一定规则划分成若干个子群，子群独立进化，一定阶段后，再融合在一起，重新划分后再独立进化，直到满足结束条件。二者都采用组织社会行为代替进化算法的自然选择机制，但在算法表现方面有着不同的特点。离散量子粒子群优化算法(QDPSO)简洁效率高，局部搜索速度快，但会由于粒子在运动过程中产生惰性而发生早熟收敛，导致陷入局部最优解。蛙跳优化(JFO)的局部搜索速度较慢，但其采用多种群的进化方法，拥有优良的全局搜索性能。蛙跳和离散量子粒子群混合优化(JF-QDPSO)算法采用二者相结合的方法，利用QDPSO 算法进行子群内部局部搜索，利用JFO 的多子群进化方法进行子群间的混选，跳出局部最优，以达到收敛速度快及全局搜索性能好的目的。

本文针对网络节点受到大面积损坏的情况，将网络拓扑愈合问题映射到斯坦纳最小树(SMT)问题，通过引入JF-QDPSO 算法求解中续节点位置，修复网络拓扑。该策略采用群体智能算法，具有执行简单、计算时间短以及恢复后的网络平均通信链路小等优点，具有较强的实用性。

1 问题描述及转化

设智能雷场网络中共有N 个具有移动和定位能力的中续节点，当网络遭到攻击被分割成数个互不连通的部分后，需要启动中续节点来代替受损节点修复网络拓扑。这里忽略智能雷场节点随即抛洒布设的情况，仅考虑人工定点布设节点。就该问题而言，扮演替代角色的中续节点的位置选取至关重要，节点的迁移行为不仅需要恢复受损拓扑，更能使修复的网络节省能耗，缩短网络通信链路长度，因此智能雷场网络修复问题可归结为最优化网络拓扑的中续节点位置选取问题。对于此类连通数个被分割的部分形成通路的最优问题，通常都被归为SMT［9-10］问题。

定义1 给定图G =(V，E)，V 为图G 的节点集，E 为图G 的边集，费用函数C:E→R+，R+为正实数，目标节点集D⊆V.则SMT 为从图G 中找出连通D 中所有节点的最小生成树，即使树的费用最小，则该最小生成树称为SMT.

然而，根据智能雷场网络通信的特殊性，需要规定每个连通节点间的距离d(i，j)最多不能超过通信距离R，且费用函数C 的最小值即为所形成的连通网络通信链路长度最小值。

定义2 抽象受损智能雷场网络为图G =(V，E，C).其中:V 表示节点集，E 表示节点间的无线链路集合，C 为费用函数，表示所有无线链路的总长度。满足:eij表示节点i，j 之间的链路，目标节点集D⊆V.因此，智能雷场网络大面积受损修复问题被转化为:确定中续节点的位置，使得在图G 中能够形成一个连通所有目标节点的子树T，且所有无线链路总长度最小，即

2 基于区域网格模型的JF-QDPSO 算法

2.1 标准粒子群算法

粒子群算法是由Kennedy 等［11］提出的一种智能优化算法，优点为算法简洁，易于实现，且没有梯度信息。该算法通过初始一群随机粒子(每个粒子代表着一个潜在解)，并利用迭代方式，使每个粒子向自身找到的最好位置和群体中最好粒子靠近，从而搜索最优解。标准粒子群算法迭代过程如下

式中:vij为第i 个粒子j 维的飞行速度;xij为粒子位置;k 为迭代次数;r1和r2为［0，1］之间的随机数;c1和c2为加速因子;pbest是粒子i 迄今为止搜索到的最优位置;gbest为整个粒子群迄今位置搜索到的最优位置。

2.2 雷场网络模型

本文关注的核心问题是中续节点的放置位置，假若雷场网络中节点随意放置，会使得算法的搜索空间无限大，不利于实际工程问题的解决。为了缩小算法搜索空间规模，本文将雷场网络的节点放置网格化。图2显示了网格型的智能雷场网络结构，中续节点的可能放置位置必须在网格交点处，且单位网格长度等于节点间通信距离R.

2.3 蛙跳和离散量子粒子群混合优化算法

通过将雷场区域网格化，放置中续节点的位置由连续空间变为可供选择的离散点，因此，本文采用QDPSO 和JFO 相结合的算法解决雷场网络修复问题。

JF-QDPSO 算法的粒子群表述为

图2 基于网格模型的雷场网络结构Fig.2 Grid-based minefield network architecture

式中:S 为整个青蛙种群;K 为子群数量;m 为单个子群所包含的粒子规模;Xki表示单个粒子位置。在智能雷场网络大面积受损修复问题中，单个粒子位置由一串离散的二进制码表示Xki=［xki1，xki2，…，］，n 为中间节点的数量，此处xkij只能取0 或者1.当xkij取1 时，表示中间节点j 被选择为中续节点的放置位置，当xkij取0 时，则在该节点处不放置中续节点。

JF-QDPSO 不采用标准粒子群算法的粒子飞行速度来更新粒子，取而代之的是粒子从一个可行解跳跃到另外一个可行解。每个粒子Xi跳跃到下一时刻位置Xi+1由以下3 种变量决定:该粒子迄今为止搜索到的最好位置b;子群内部所有粒子迄今为止搜索到的最好位置gi;整个种群所有粒子迄今为止搜索到的最好位置g*.

本文提出的算法1～3 显示了JF-QSPSO 求解雷场网络大面积损坏修复问题的具体细节。算法1 是算法的主体结构，算法2 保证经过每次跳跃过程后Xi+1也是问题的可行解，算法3 起到本地搜索的作用，在满足问题可行解的前提下尽可能多的除去被选中的中续节点。

算法首先产生一个规模为m 的子群S，初始化粒子X1为［1，1，…，1］，因此X1必然是该问题的一个可行解。在的每一次迭代过程中，原先粒子位置Xi经过一次随机跳跃，变成另外一个可行解Xi+1.随机跳跃过程是由一个在0 和1 之间的随机数ξ 控制的，算法等概率的在Xi、bi、gi、g*之中选择一个数为selected.随后执行Combine(Xi，selected)(见算法2)将粒子Xi与被选择粒子selected 结合起来。这里运用到了comp(Xi)的概念［12］，它表示至少包含一个目标节点的斯坦纳连通图，当且仅当comp(Xi)=1 时，Xi才是问题的一个可行解。算法2 首先在［0，num(|Xi|)］之间选择一个随机数ψ，随后从集合|Xi|随机删除一个中续节点，或者从集合selected 中随机增加一个节点为中续节点，此操作循环ψ 次后终止。随后更新Xi及comp(Xi)，如果Xi是非可行解时(comp(Xi)＞1)，随机添加一个节点为中续节点，直到得到可行解(comp(Xi)=1).算法3 起到了一个本地搜索的作用，在不影响解可行性的前提下，尽量缩小中续节点数量。本地搜索之后，变量(bi，gi，g*)都会被更新，用到下一次循环当中。这里，循环的次数可以理解为子群的数量，当循环次数达到指定的子群数量或者得到了满意的g*，则循环中止，输出斯坦纳树T.

1)算法1:蛙跳和离散量子粒子群混合优化算法求解雷场网络大面积损坏快速修复问题。

输入:网格划分后的连通权重图G =(V，E，C)，其中包含了n 个顶点，l 条边，以及Q⊆V 个目标节点;

输出:连通所有目标节点且权重值最小的斯坦纳树T;

初始化:令|Xi|为中续节点的集合，即|Xi| ={xij=1/xij，j =［1，n］};令C(Xi)为粒子Xi的适应度函数，C(Xi)=随机产生子群Sk粒子规模m，Sk=［Xk1，Xk2，…，Xkm］.

-运行算法2Combine(Xi，selected)，将粒子Xi与被选择粒子selected 结合起来;

-运行算法3Local-Search(i，Xi)，进行本地局部搜索;

until 达到循环中止条件;

-输出斯坦纳树T=G(|g*|，E(|g*|))，其中E(|g*|)为连接g*中的中续节点且边长小于等于通信距离R 的边。

2)算法2:Combine(Xi，selected)

-令comp(Xi)为至少包含一个目标节点的斯坦纳连通图;令num(|Xi|)为集合|Xi|中中续节点的数量;在［0，num(|Xi|)］之间选择一个随机数:ψ←Random(0，num(|Xi|));

3 仿真实验

平均链路长度和平均计算时间是评价雷场网络修复算法的重要参数。链路长度短说明在能够保证重建网络连通的前提下，运用的节点数量少，且修复后的网络通信能耗小，生存周期长;计算时间少则表明算法执行时间短，算法效率高。

为了验证JF-QDPSO 的性能，针对中间节点数{100，400}和目标节点数{5，8，10}6 个样本，对SMT-MSP［10］(Steiner minimum tree with minimum number of Steiner points)、QDPSO 和JF-QDPSO 进行比较，其中JF-QDPSO 的种群规模为100，分成20 个子群，最大迭代数1 000.PC 机平台为Pentium 4 CPU，主频1.43 GHz，内存1 GB，操作系统使用Windows XP，利用Visual C + +6.0 语言编程实现。表1给出了SMT-MSP、QDPSO 和JF-QDPSO 对六个样本仿真计算100 次得出的平均网路链路长度和平均计算时间。从表1中可以看出:JF-QDPSO 和QDPSO 不仅从计算结果，而且在计算时间上也远远胜过SMT-MSP，这表明离散量子粒子群算法比启发式算法SMT-MSP 简洁高效，且能够更好的应用于雷场网路拓扑修复中。此外，从JF-QDPSO 与QDPSO的比较来看，JF-QDPSO 在求解结果上比QDPSO 更优，然后求解速度上却因多子群间的协作进化而略低于QDPSO.

表1 3 种算法对不同样本的平均链路长度和计算时间Tab.1 Average link length and computational times with different samples for three algorithms

图3给出了在中间节点数为100，目标节点数为5 的情况下3 种算法的收敛曲线。图中，SMTMSP 在95 代左右才趋近于收敛，且结果最差;QDPSO 在40 代左右就趋近于收敛，但效果一般;JFQDPSO 在60 代左右趋近于收敛，且效果最好，这说明蛙跳算法与离散量子粒子群算法的结合，有效克服了算法陷入局部最优解，体现了其收敛速度快及全局搜索性能好的特点。

图3 3 种算法的收敛曲线Fig.3 Convergence performance for three algorithm

4 结论

本文研究了以无线传感器网络为基础的智能雷场网络大面积损坏拓扑修复问题。将该问题抽象为求解斯坦纳最小树问题，提出了蛙跳和离散量子粒子群混合优化算法。理论和数值仿真证明，该算法充分利用了粒子群算法收敛速度快、局部搜索能力强以及混合蛙跳算法全局寻优能力强、跳出局部最优能力好的特点，较SMT-MSP 算法在平均链路长度上较低了43.2%，在平均计算时间上降低了51.4%.可见，本文所提算法在有效恢复网络拓扑的同时，降低了恢复后网络的通信荷载，延长了网络生存周期。

References)

［1］ Mattias S，Mathias B，Alessandro Si，et al.An autonomous spherical robot for security tasks［C］∥2006 IEEE International Conference on Computational Intelligence for Homeland Security and Personal Safety.AV Alexandria，AV:IEEE，2006:1233 -1236.

［2］ Sugiyama Y，Hirai S.Crawling and jumping by a deformable robot［J］.International Journal of Robotics Research，2006，25(5):603 -620.

［3］ 付梦印，杨毅，朱昊，等.移动机器人组合感知系统及其配准方法改进［J］.兵工学报，2011，32(6):712 -718.FU Meng-yin，YANG Yi，ZHU Hao，et al.Integrated perception system for mobile robot and its improved registration［J］.Acta Armamentarii，2011，32(6):712 -718.(in Chinese)

［4］ Cheng X Z，Du D Z，Wang L S，et al.Relay sensor placement in wireless sensor networks［J］.Wireless Netwroks，2008，14(3):347 -355.

［5］ 刘林峰，刘业.基于满Steiner 树问题的水下无线传感器网络拓扑愈合算法研究［J］.通信学报，2010，31(9):30 -45.LIU Lin-feng，LIU Ye.Study of topology recovery algorithm based on full Steiner minimum tree problem in underwater wireless sensor networks［J］.Journal of Communications，2010，31(9):30 -45.(in Chinese)

［6］ Mohamed Y，Rahul W.Connectivity restoration in wireless sensor networks using Steiner tree approximations［C］∥IEEE Global Telecommunications Conference.Miami:IEEE，2010:1 -5.

［7］ Yang S，Wang M，Jiao L.A quantum particle swarm optimization［C］∥Proceeding of the 2004 IEEE Congress on Evolutionary Computation.Alexandria:IEEE，2004:320 -324.

［8］ Martunez-Garcia F J，Moreno-Perez J A.Jumping frogs optimization:a new swarm method for discrete optimization［C］∥Teth.Rep.DEIOC 3/2008，Dep.Of Statistics，O.R.and Computing.Spain:University of La Laguna，2008:29 -46.

［9］ Lin G，Xue G.Steiner tree problem with minimum number of Steiner points and bounded edge length［J］.Information on Processing Letters，1999，69(2):53 -57.

［10］ Lloyd E L，Xue G.Relay node placement in wireless sensor networks［J］.IEEE Transcations on Computers，2007，56(1):134 -138.

［11］ Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］∥Proceeding of the Sixth International Symposium on Micro Machine and Human Science.Nagoya:Indianapolis Press，1995:39 -43.

［12］ Cerulli R，Fink A.Extensions of the minimum labelling spanning tree problem［J］.Journal of Telecommunications and Information Technology，2006，32(4):39 -45.