改进二进制粒子群优化的节点选择算法

魏声云,张 静,郭 虹,李 鸥

(解放军信息工程大学信息与系统工程学院,河南郑州 450001)



改进二进制粒子群优化的节点选择算法

魏声云,张 静,郭 虹,李 鸥

(解放军信息工程大学信息与系统工程学院,河南郑州 450001)

摘要:针对无线传感器网络多目标跟踪节点选择问题,提出了一种最大化跟踪精度的二进制粒子群优化节点选择算法.该算法基于目标的预测位置,以费舍尔信息矩阵的迹为精度度量,构建节点优化选择模型,提出了二进制粒子群优化的改进形式,并用于节点选择模型的求解.改进的二进制粒子群优化算法采用矢量的二进制编码方式、约束满足的循环移位种群初始化方法,带V型转换函数的位置更新规则,并设计了引导因子引导粒子群的进化.仿真结果表明,所提出的节点选择算法能够有效地应用于多目标跟踪问题,与基本的二进制粒子群优化算法和遗传算法相比,改进的二进制粒子群优化算法能够在全局寻优和局部探索间取得平衡,且能有效地避免局部最优,对较大规模的网络具有很强的适用性.

关键词:无线传感器网络;节点选择;二进制粒子群优化;费舍尔信息矩阵

无线传感器网络(Wireless Sensor Networks,WSN)是集成了监测、控制以及无线通信的网络系统,在军事侦察、环境监测、目标跟踪、空间探索和灾难抢险等特殊领域具有广阔的应用前景.特别是网络的分布式信息处理、快速展开、抗毁性强等特点,使得机动目标跟踪成为了WSN最具代表性的应用之一[1].跟踪的目的是为了获取目标的运动轨迹,尽量多的节点协同跟踪目标能够提高跟踪性能,但也会带来更多的能量消耗[2].由于节点选择问题的组合特性,当网络规模较大,需要选择的节点数较多时,节点选择是一个NP难问题.随着WSN的广泛应用,节点选择问题成为了传感器管理领域的研究热点.

近年来,国内外学者针对节点选择问题提出了众多的方法和策略.文献[3-4]均以几何精度衰减因子为目标函数,采用贪婪策略构建活跃节点.文献[5]将后验克拉美罗下界作为传感器选择和优化的准则,采用穷举搜索的方法为单个目标选择参与跟踪的节点,该方法在节点数较小的情况下是有效的.而针对大规模的传感器网络,文献[6]提出了一种基于牡丹树的低能耗的节点休眠调度算法;文献[7]提出了基于广义信息增益的目标跟踪节点选择算法,算法采用布尔二次规划理论对优化模型进行求解;文献[8]研究了面向多目标跟踪的分布式节点选择问题,将初始的0-1整数规划问题松弛处理,转换成凸优化问题,采用梯度投影搜索算法作为求解策略,获得原问题的次优解.针对规划方法计算量随着网络规模变大而急剧增加的问题,文献[9]提出将二进制粒子群优化(Binary Particle Swarm Optimization,BPSO)算法引入节点选择问题中;文献[10]提出了基于粒子群算法(Particle Swarm Optimization,PSO)的传感器调度方法.以上两类算法面临的共同问题是:算法容易陷入局部最优,而且,在网络规模较大时,难以保证算法在可接受的时间范围内找到满意解.

笔者研究多目标跟踪节点选择算法,以费舍尔信息矩阵的迹[11]为准则,设计了一个基于改进二进制粒子群优化(Modified Binary Particle Swarm Optimization,MBPSO)的多目标跟踪实时节点选择算法.其主要贡献有:构建了通用的目标跟踪节点选择闭环体系结构,在此结构下建立了以费舍尔信息矩阵(Fisher Information Matrix,FIM)的迹为精度度量的多目标跟踪节点选择模型;对基本BPSO算法从加快收敛速度和避免陷入局部最优两个方面进行了改进,结合多目标跟踪节点选择问题,提出了粒子的矢量编码方式,并采用循环移位的方法对种群进行初始化,引入V型转换函数构建粒子的位置更新规则,分析了BPSO陷入局部最优的根本原因,提出了带引导因子的搜索策略;实现了目标跟踪过程中的节点实时选择,并验证了算法的有效性.

1 目标跟踪节点选择问题

图1 目标跟踪节点选择闭环体系结构

目标跟踪节点选择是指利用有限的传感器资源,以网络效能为目标函数,在每个采样时间动态地选择合理的传感器组合对目标进行跟踪.节点选择的核心问题是建立节点选择的优化模型,并采用高效的求解方法对模型进行求解,目标跟踪节点选择闭环体系结构如图1所示.

2 节点的优化选择模型

以最大化所有目标的跟踪精度为目标,采用基于FIM的机制对跟踪精度进行度量.目标跟踪的目的是在每一时间步长内对目标进行精确的定位,定位的精度与任务节点集的观测信息密切相关,FIM越大,表明观测信息对定位精度的贡献越大[12],因此,最大化跟踪精度可以转化成最大化FIM.在建立节点选择优化模型之前,首先给出两个相关的二进制变量的定义.

对目标k的任务节点集Gk(t)的FIM表示为

其中,(dk,i,φk,i)表示与目标k预测位置(px,k,py,k)相关的节点i的极坐标位置,由于FIM为矩阵形式,不方便后续的优化分析,文献[13]证明了对Jk和对det{Jk}的优化问题是等价的,且最大化det{Jk}与最小化1det{Jk}是等价的,因此,1det{Jk}可以反映定位均方误差(Mean Square Error,MSE)的大小.

因此,跟踪精度与参与跟踪的节点数目、目标与节点间的距离、角度分集以及观测噪声有关.

为了保证跟踪质量,假设同一时刻跟踪每个目标的节点数为m,一个节点同一时刻最多只能跟踪一个目标.因此,目标跟踪节点选择问题的优化模型为

节点选择实际完成的是多个目标与多个节点的配对,目标函数是复杂且非线性的,同时,具有多个约束条件.当网络规模较大时,节点选择是NP难的组合优化问题,特别是在实时性要求高的目标跟踪系统中,传统的搜索算法很难在可接受的时间范围内找到满意解,因此引入群智能算法对问题进行求解.

3 基于MBPSO的节点选择算法

面向目标跟踪的节点选择是一个离散空间的寻优问题.由于节点选择需要在较短的时间内完成,因此,对算法寻优速度和稳定性要求很高,与其他搜索算法相比,BPSO具有收敛速度较快、易于实现等优点,在已有的离散空间寻优问题研究中[14],证明了具有较好的寻优效果.

3.1 基本BPSO算法

BPSO是基于种群和适应度两个基本概念的寻优算法,每个粒子代表问题的一个可行解,具有速度和位置两个描述量.采用一组参数和符号描述BPSO算法,可以表示为

在基本BPSO算法中,随着迭代的进行,粒子的随机游走现象增加,使得算法收敛速度变慢,容易陷入局部最优[15].为了将BPSO算法应用于求解多目标跟踪节点选择问题,笔者提出的MBPSO算法分别从加快收敛速度和避免陷入局部最优两个方面对算法进行改进.

3.2 MBPSO算法及其在节点选择问题中的应用

图2 粒子的编码结构

3.2.1 粒子编码方式和初始化方法

为了降低粒子群的维数,避免矩阵编码导致粒子的搜索空间过大的问题,利用节点感知范围有限这个约束条件,得到目标暴露范围内的节点数Nk,对目标与节点对应关系矩阵进行稀疏处理,采用矢量的方式对粒子进行编码,粒子的编码结构如图2所示.

随机初始化种群方法虽然操作简单,但是,初始种群中单个粒子的位置矢量中为1的位数可能会远远大于期望的数量,这会导致初始的适应度函数值过大,从而影响算法的收敛速度.为了减小粒子群初始的搜索空间,同时增加初始种群的多样性,文中设计了一种与约束条件相适应的种群初始化方法(Constraint-Adaptive Population Initialization,CAPI).CAPI实现过程为:首先,通过随机生成的方式,使种群中第一个粒子x01中元素1的个数等于m Na,与约束条件相适应;然后,通过循环移位操作,产生种群中剩余个体的位置,得到初始的种群位置.循环移位操作的数学描述为

3.2.2 考虑粒子绝对速度的位置更新规则

WSN目标跟踪的实时性与搜索算法的收敛速度息息相关.在粒子实际迭代过程中,粒子的绝对速度越大,粒子远离全局最优位置的概率就越大,而S型转换函数并未体现这一规律[16].因此,MBPSO采用V型转换函数以适应粒子的进化,粒子根据自身当前的位置、速度、到自身最佳位置的距离以及到全局最优位置的距离来完成速度和位置的更新,以保证节点选择能够在可行的时间内完成.更新规则如下:

3.2.3 带引导因子的搜索策略

搜索算法摆脱局部最优的能力能够直接反应任务节点执行跟踪任务的质量,局部搜索能力越强,跟踪精度越高.当BPSO算法陷入局部最优时,种群的进化处于停滞状态,若粒子群最终的位置为G*,如果粒子群在进化过程中没有找到比Gbest更优的位置,则所有的粒子将向G*聚拢,但此时的G*并不是全局最优位置.这种聚拢现象是导致BPSO算法陷入局部最优的根本原因.为了使BPSO中的粒子摆脱局部最优,有如下两种方法:使粒子在向G*聚拢的过程中,找到比Gbest更优的位置;改变当前的Glbest,使向G*聚拢的粒子改变搜索方向,寻找新的搜索空间,从而提高算法的局部搜索能力.针对方法,文献[17]提出了带极值扰动的简化PSO算法,然而,针对不同的问题,添加扰动的停滞步数阈值很难确定,阈值过小,可能影响粒子群的正常进化;阈值过大,算法摆脱局部最优的效果不明显.同时,极值扰动具有很强的随机性,粒子的运动空间越大,种群跳出局部最优的可能性越小.笔者针对第种方法,受蝙蝠算法[18]中的局部搜索策略的启发,设计了带引导因子的粒子群搜索策略.该策略的基本思想是:定义全局搜索引导因子和局部搜索引导因子,在粒子向G*聚拢的过程中,根据两个引导因子,在Glbest附近进行随机搜索,以加快收敛速度和避免局部最优.以下给出两个引导因子的定义及更新方式.

其中,α为全局搜索引导因子,表示粒子群搜索方向改变的概率,α在算法的前期具有较大的值,使粒子的搜索空间具有多样性,保证粒子群的全局搜索能力,而在算法的中后期逐渐变小.β为局部搜索引导因子,表示粒子进行局部搜索的概率,β在算法的前期具有较小的值,而后逐渐变大,以增强粒子局部搜索的能力,α0p和βmax分别为全局引导因子的初值和局部引导因子的最大值.

3.2.4 带惩罚因子的适应度函数设计

由于节点选择是一个具有约束条件的优化问题,目标函数不能直接作为适应度函数.采用不依赖种群进化的静态罚函数法将约束问题转化成无约束问题,将增加了惩罚项的目标函数作为适应度函数,定义惩罚因子ξ1和ξ2.则目标跟踪节点选择问题的适应度函数表达式为

3.2.5 算法步骤

步骤1 初始化WSN和MBPSO算法的参数.

步骤2 采用二进制方式对每个粒子进行编码,并利用CAPI方法初始化粒子群.

步骤5 判断循环是否终止.若终止,执行步骤6;否则,执行步骤3.

步骤6 输出全局最优位置Gbest,构建任务节点集.

4 仿真实验与结果分析

采用主频为2.4 GHz的PC机在MATLAB环境下对算法进行一系列的仿真.采用k-means算法使WSN中节点均匀分布于200 m×200 m的正方形区域内,参考文献[3-4,10],实验参数设置如下:rs=50 m;考虑网络中的目标数为2,目标的初始位置分别为(45,45)和(145,145),节点数默认为90,且σ2w=0.05;目标采用CV模型,滤波算法采用无迹卡尔曼滤波,目标的初始状态为[43,43,2,2]以及[152,152,-2,-2],初始协方差矩阵均为0.001×diag[1,1,0,0];c1=c2=2,nop=30,Max_Iter=200,wmax=0.9,wmin=0.4,α0p=0.5,βmax=0.3,ξ1=ξ2=200.GA的参数设置为:种群规模设置为nop=30,精英个体数为4,最大循环次数Max_Iter=200,交叉概率和变异概率分别为0.7和0.02.实验次数n=50,且每次实验独立进行,实验结果取多次实验的平均值.

4.2 仿真结果分析

图3是m值和节点数量对MBPSO性能的影响.由图3(a)可知,随着m值的增加,平均适应度函数值变小,这是因为观测节点数越多,任务节点集获取关于目标的信息量增加,跟踪精度变高.然而,适应度函数值的增量是逐渐变小的,这是由于m值增大到一定数值时,节点获得信息逐渐变得冗余.因此,综合考虑精度、能量消耗和通信负载等因素,文中选取m=3.由图3(b)可知,随着节点数量的增加,平均适应度函数值变小,这是由于网络中节点密度变大,可供选择的节点数增加,有利于提高目标跟踪精度.此外,随着m值和节点数量的增加,MBPSO算法的收敛速度并没有变慢,这表明算法的适应性较强.

图4为GA、BPSO-CSP[9]、IBPSO[19]和MBPSO的收敛性能对比结果.由图可知,BSPO前期收敛速度

4.1 性能评价指标与仿真环境设置

为了验证笔者所提算法的有效性,在目标跟踪体系结构下,针对节点的优化选择问题,将所提的MBPSO算法与遗传算法(Genetic Algorithm,GA)和文献[9]算法(记为BPSO-CSP)进行对比和分析.并采用收敛性能、平均百分偏差和跟踪误差3个指标对算法进行评价.其中,平均百分偏差表示n次实验在截止时刻获得的解ft(i)与客观最优解ft0间的偏差(实验分析中的ft0由大量的仿真实验得到),其值越小,算法的性能越好.跟踪误差采用均方根误差(Root-Mean-Square Error,RMSE)来度量.平均百分偏差的计算式为最快,容易陷入局部最优,这是由于BPSO-CSP在迭代过程中,粒子容易出现聚集现象,导致种群进化停滞.GA前期收敛速度最慢,后期也容易陷入早熟,这是因为GA中的变异操作虽然能够以一定的概率使算法跳出局部最优,但是,需要经过较多的迭代次数.MBPSO在20～50次迭代中,平均适应度函数大于BPSOCSP,这是算法在前期依然有一定的概率进行局部搜索,对前期的平均收敛速度有一定的影响,但是,MBPSO在全局寻优和局部搜索间取得了较好的平衡.在循环数为50次和100次左右时,MBPSO获得了BPSO-CSP和GA在200次迭代所获得的适应度函数值,如果采用平均适应度函数来评价算法的复杂度,那么,MBPSO的时间复杂度为BPSO-CSP的1/4,GA和IBPSO的1/2.

图3 m值和节点数对算法性能的影响

图4 不同算法的收敛曲线　

图5 不同节点数下算法的平均百分偏差

图5是循环数l=200时,3个算法的平均百分偏差的比较结果.由图可知,随着节点数的增加,GA、IBPSO和BPSO-CSP的平均百分偏差均变大,但是MBPSO的平均百分偏差基本未变,始终保持在2%以内.这表明,随着网络规模的增大,MBPSO始终能够找到优质的解.

图6为文中算法与经典的全局节点选择(Global Node Selection,GNS)算法[4]、GA和BPSO-CSP的跟踪平均RMSE结果.由图可知,基于MBPSO的节点选择算法性能是最优的,这是因为基于MBPSO的节点选择算法能够以最大的概率找到最适合跟踪目标的任务节点集,使跟踪误差最小.

图6 不同采样周期的平均RMSE

5 结束语

针对无线传感器网络多目标跟踪的节点选择问题,构建了通用的节点选择闭环体系结构,提出了一种基于改进二进制粒子群优化的实时节点选择算法.该算法以最大化跟踪精度为目标,采用FIM迹的形式构建优化模型,引入群智能方法对模型进行了求解.分析了BPSO算法容易陷入局部最优的原因,提出了BPSO的改进形式.MBPSO采用了矢量编码方式,结合约束条件,利用循环移位操作初始化种群,压缩了粒子的搜索空间,增加了种群的多样性;同时,设计了带引导因子的搜索策略.仿真结果表明,笔者所提的基于MBPSO的节点选择算法是有效的,该算法能够在全局寻优和局部探索间取得平衡,且有效地避免了局部最优,对较大规模的网络具有很强的适用性.下一步的研究工作重点是分布式跟踪结构下,考虑跟踪精度、能量均衡和能量消耗的节点选择算法.

参考文献:

[1]AKYILDIZ I F,SU W,SANKARASUBRAMANIAM Y,et al.Wireless Sensor Network:a Survey[J].Computer Networks,2002,38(4):393-422.

[2]DEMIGHA O,HIDOUCI W K,AHMED T.On Energy Efficiency in Collaborative Target Tracking in Wireless Sensor Network:a Review[J].IEEE Communications Surveys& Tutorials,2013,15(3):1210-1221.

[3]ZOGHI M,KAHAEI M H.Adaptive Sensor Selection in Wireless Sensor Networks for Target Tracking[J].IET Signal Processing,2010,4(5):530-536.

[4]KAPLAN L M.Global Node Selection for Localization in a Distributed Sensor Network[J].IEEE Transactions on Aerospace and Electronic Systems,2006,42(1):113-135.

[5]杨小军.基于性能边界和量化数据的WSN目标跟踪传感器选择算法[J].电子学报,2014,42(6):1081-1085.YANG Xiaojun.Sensor Selection for Target Tracking in Wireless Sensor Networks Based on Performance Bounds and Quantized Data[J].Acta Electronica Sinica,2014,42(6):1081-1085.

[6]齐小刚,陆赞赞,郑耿忠,等.一种低能耗低时延的休眠调度算法[J].西安电子科技大学学报,2015,42(1):125-129.QI Xiaogang,LU Zanzan,ZHENG Gengzhong,et al.Low-power and Low-delay Sleep Scheduling Algorithm Based on the Data Aggregation Tree[J].Journal of Xidian University,2015,42(1):125-129.

[7]SHEN X J,VARSHNEY P K.Sensor Selection Based on Generalized Information Gain for Target Tracking in Large Sensor Networks[J].IEEE Transactions on Signal Processing,2014,62(2):363-375.

[8]FU Y Y,LING Q,TIAN Z.Distributed Sensor Allocation for Multi-target Tracking in Wireless Sensor Networks[J].IEEE Transactions on Aerospace and Electronic Systems,2012,48(4):3538-3552.

[9]NAEEM M,PAREEK U,LEE D C.Swarm Intelligence for Sensor Selection Problems[J].IEEE Sensors Journal,2012,12(8):2577-2585.

[10]李国辉,冯明月,易先清.基于分群粒子群的传感器调度方法[J].系统工程与电子技术,2010,32(3):598-602.LI Guohui,FENG Mingyue,YI Xianqing.Sensor Scheduling Method Based on Grouping Particle Swarm Optimization [J].Systems Engineering and Electronics,2010,32(3):598-602.

[11]THARMARASA R,KIRUBARAJAN T,HERNANDEZ M L,et al.PCRLB-based Multisensor Array Management for Multitarget Tracking[J].IEEE Transactions on Aerospace and Electronic Systems,2007,43(2):539-555.

[12]YANG Z Y,SHI X F,CHEN J M.Optimal Coordination of Mobile Sensors for Target Tracking Under Additive and Multiplicative Noises[J].IEEE Transactions on Industrial Electronics,2014,61(7):3459-3468.

[13]BISHOPK A N,JENSFELT P.An Optimality Analysis of Sensor-Target Geometries for Signal Strength Based Localization[C]//Proceedings of the 5th International Conference on Intelligent Sensors,Sensor Networks and Information Processing.Piscataway:IEEE Computer Society,2009:127-132.

[14]郭文忠,苏金树,陈澄宇,等.无线传感器网络中带复杂联盟的自适应任务分配算法[J].通信学报,2014,35(3):1-10.GUO Wenzhong,SU Jinshu,CHEN Dengyu,et al.Self-adapted Task Allocation Algorithm with Complicated Coalition in Wireless Sensor Network[J].Journal on Communications,2014,35(3):1-10.

[15]YANG J,ZHANG H S,LING Y,et al.Task Allocation for Wireless Sensor Network Using Modified Binary Particle Swarm Optimization[J].IEEE Sensor Journal,2014,14(3):882-891.

[16]MIRJALILI S,LEWIS A.S-shaped versus V-shaped Transfer Functions for Binary Particle Swarm Optimization[J].Swarm and Evolutionary Computation,2013(9):1-14.

[17]胡旺,李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报,2007,18(14):861-868.HU Wang,LI Zhishu.A Simpler and More Effective Particle Swarm Optimization Algorithm[J].Journal of Software,2007,18(14):861-868.

[18]YANG X S.A New Metaheuristic Bat-inspired Algorithm[C]//Proceedings of Nature Inspired Cooperative Strategies for Optimization.Berlin:Springer-Verlag,2010:65-74.

[19]徐春义,肖人彬.一种改进的二进制粒子群算法[J].模式识别与人工智能,2007,20(6):789-793.XU Chunyi,XIAO Renbin.An Improved Binary Particle Swarm Optimizer[J].Pattern Recognition and Artificial Intelligence,2007,20(6):789-793.

(编辑:王 瑞)

Sensor selection algorithm based on modified binary particle swarm optimization

WEI Shengyun,ZHANG Jing,GUO Hong,LI Ou
(Institute of Information System Engineering,Information Engineering Univ.of PLA,Zhengzhou 450001,China)

Abstract:Considering the problem of sensor selection for multi-target tracking in wireless sensor networks (WSN),a sensor selection algorithm based on binary particle swarm optimization(PSO)is proposed to maximize the tracking accuracy.The predicted coordinate of the target and the determinant of the Fisher information matrix(FIM)is used for sensor selection.A modified form of binary particle swarm optimization(MBPSO)is proposed to solve the model,which is designed by employing the binary vector coding manner,constraint satisfaction cyclic shift population initialization method,particle position updating rules with the V-shaped transfer function and guidance factor.Simulation results show that the proposed sensor selection algorithm can be efficiently applied in the multi-target tracking problem.Compared to the basic particle swarm optimization algorithm and genetic algorithm(GA),the modified algorithm achieves a balance between global optimization and local exploration,and can effectively avoid the local optimum.Moreover,the proposed algorithm is suitable for large-scale networks.

Key Words:wireless sensor networks;sensor selection;binary particle swarm optimization;Fisher information matrix

作者简介:魏声云(1989-),男,解放军信息工程大学硕士研究生,E-mail:junyun1002@126.com.

基金项目:国家自然科学基金资助项目(61201380);国家科技重大专项资助项目(2014ZX03006003)

收稿日期:2014-12-19 网络出版时间:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.026

中图分类号:TP393

文献标识码:A

文章编号:1001-2400(2016)02-0150-07

网络出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.023.html