武汉大学学报(理学版) 2017, Vol. 63 Issue (6): 506-512
0

文章信息

代声发, 黄启俊, 马启明
DAI Shengfa, HUANG Qijun, MA Qiming
基于粒子群算法的闪电定位网优化布站
Sites Distribution Optimization of Lightning Location Network Based on Particle Swarm Optimization
武汉大学学报(理学版), 2017, 63(6): 506-512
Journal of Wuhan University(Natural Science Edition), 2017, 63(6): 506-512
http://dx.doi.org/10.14188/j.1671-8836.2017.06.007

文章历史

收稿日期:2017-01-20
基于粒子群算法的闪电定位网优化布站
代声发1, 黄启俊1, 马启明2    
1. 武汉大学 物理科学与技术学院, 湖北 武汉 430072;
2. 中国科学院 电工研究所, 北京 100080
摘要:闪电监测网探测站的位置分布对定位精度具有重要影响, 如何布置站点使得监测网具有最佳的定位精度是监测网设计时必须考虑的问题.在分析三维闪电定位算法和点位误差的基础上, 引入最优化思想, 提出了一种优化布站模型.利用粒子群算法能够求解得到该模型的定量化结果, 该结果保证了目标监测区域的平均误差最小.在广西壮族自治区三维闪电监测网站点位置分布设计应用中, 利用该模型仿真得到定位网内水平误差为200m, 误差得到明显降低.本文提出的模型可以为三维闪电监测网合理布置站点提供支撑, 能有效提高监测网定位精度.
关键词闪电定位     精度分析     优化布站     粒子群算法    
Sites Distribution Optimization of Lightning Location Network Based on Particle Swarm Optimization
DAI Shengfa1, HUANG Qijun1, MA Qiming2    
1. School of Physics and Technology, Wuhan University, Wuhan 430072, Hubei, China;
2. Institute of Electrical Engineering of the Chinese Academy of Sciences, Beijing 100080, China
Abstract: The distribution of the sites of lightning monitoring network has important influence on the positioning accuracy.How to distribute sites is a basic question in the design of lightning monitoring network. This paper puts forward a model with optimization theory on the base of the 3-D lightning localization algorithm and accuracy analysis to achieve optimized sites distribution. Quantitative results of the distribution optimization can be given via particle swarm optimization (PSO) algorithm, which can ensure the average positioning accuracy in the network is at the mininum. In the application of 3-D lightning monitoring network design in Guangxi autonomous region, the calculation results showed that the horizontal average error is about 200m which shows an obvious decrease in error.The model can present quantitative results.Calculation results show that the efficiency of the model in site distribution optimization of 3-D lightning monitoring network, which can greatly improve positioning accuracy.
Key words: lightning location     accuracy analysis     distribution optimization     particle swarm optimization (PSO) algorithm    
0 引言

闪电是自然界中频繁发生的一种自然现象, 发生的过程中伴随有强烈的声、光、电等现象.随着各行各业的信息化带来的电子设备使用增多,闪电造成的灾害和经济损失也越来越大, 各个部门也越来越重视对闪电的监测[1].对闪电的监测定位结果可以为气象、电力、航空航天等部门服务, 同时也为研究闪电这一自然现象提供原始数据[2].

闪电监测网利用多个时间同步的探测站,来记录闪电电磁辐射信号到达时间和方向, 然后根据到达时间和方向计算出闪电的发生位置和时间[3].定位精度是评价闪电定位网系统性能最重要的指标之一,定位误差增大就会降低监测定位结果的应用价值[4].几何精度因子(geometric dilution of precision, GDOP)分析是最常用的误差分析方法.在GPS授时、地形地貌、大地电导率等因素引起的观测量误差给定的情况下,监测网的站点位置分布也是重要的误差来源,合理的布站方式能够有效的提高定位精度.张萍等[5]以理论推导的方式讨论了在云闪定位系统中定位精度与图形因素的关系,得出云闪定位精度与闪电发生点以及探测站组成的多面体形状有关.田彩霞[6]讨论了在4个站点情况下,星型、菱形等典型布站方式的误差分布特征,得出星型布站总体误差最小;刘洋等[7]得出星型布站下,基线长度越大定位精度越高.但这些研究只得出了四站时差定位下的定性结论,没有给出定量化的结果,所得结果也不能直接应用到多站点情况.

本文在多站时差定位迭代算法和GDOP误差分析基础上,引入最优化思想来解决优化站点位置分布问题,旨在找出特定情况下站点位置分布的最优结果.以目标监测区域的平均误差为目标函数,以所有站点的三维坐标为设计变量,建立了优化布站的数学模型.通过粒子群优化算法求解该模型得到目标监测区域平均误差最小时各站点位置的三维坐标.利用本文提出的模型算法求解得到四站时差定位的最优站点位置分布,与田彩霞[6]及刘洋等[7]对四站时差定位站点分布研究得到的定性结果基础上的定量化结果一致.

1 时差定位算法原理与精度分析 1.1 定位算法原理与误差精度分析

图 1所示,闪电监测网由多个时间同步且分布在不同地点的探测站构成,每个探测站对闪电电磁脉冲记录到达时间t(s),方位角θ(°)和俯仰角φ(°)三个观测量,其数学关系如(1)式所示:

(1)
图 1 三维闪电定位原理示意图 Figure 1 The principle of 3-D lightning positioning

(1) 式中(x, y, z, t)为待求的闪电的位置坐标和时间,(ti, θi, φi)为第i个探测站得到的3个观测量.(xi, yi, zi)为第i个探测站的位置坐标,(εti, εθi, εφi)为对应观测量的误差.

(1) 式的方程组表示成矢量形式为

(2)

(2) 式中r为观测量向量,其中每个分量可以为到达时间、方位角、俯仰角任意一种,在时差定位中为到达时间.ε为对应的误差向量,X为待求未知量(x, y, z, t).闪电定位问题即根据(2)式方程组的观测量r求出未知量X.

观测量误差来源有多种因素,一般认为误差服从零均值的正态分布,此时求解得到的闪电发生位置服从多维正态分布,对于三维定位就是一个误差椭球[3].该误差椭球协方差矩阵可表示为

(3)

它惟一决定了误差椭球,描述了该点的误差情况[4].定义几何精度因子为

(4)

后文的建模和计算都用GDOP作为空间点位的误差大小.

1.2 三维时差定位多站迭代解法

由于测向误差随距离增大线性增加,测时误差相对测向误差要小很多,使用测时数据进行定位精度更高.三维闪电定位需要计算出闪电的位置和发生时间,共有(x, y, z, t)4个未知数.当超过4个站点接受到数据时,只使用到达时间来计算定位.时差迭代算法具有计算速度快、实时性强等特点[8, 9].利用泰勒级数对(2)式非线性方程组在某个初始值X0处展开,只保留一次项,形成的线性方程组如下所示:

(5)

(5) 式中D相当于方程组中各偏导函数取X0处的值,即

(6)

其中X=(x1, x2, …, xn), X=X0n表示未知数的个数,在时差定位中有(x, y, z, t) 4个未知数,m表示方程个数,通常mn,在第k次迭代中,令ΔYk=rF(Xk),Dk=D(X=Xk),(5)式方程组变为

(7)

(7) 式中ΔXk=XXk,在时差定位中(7)式具体为

(8)

(8) 式中(xk, yk, zk, tk)是Xk的各分量, dki为(xk, yk, zk)到(xi, yi, zi)直线距离.求解(8)式的方程组时,不能直接用伪逆法,还要考虑每个方程的权重.设Wk为ΔYk的协方差矩阵,在时差定位中为对角矩阵,W=diag[c2σt2, c2σt2, …, c2σt2]n×nk无关,其中σt2为测时误差的方差.进一步得到:

(9)

解(9)式得到ΔkX, 由k+1XXk+Xk得到下一个迭代值, 循环迭代直到结果收敛或满足精度要求.

迭代算法的初始值必须在收敛域之内, 且离目标值越近收敛越快.多站时差定位用Koshak的线性化方法求解得到的解做为迭代算法的初始值[10, 11].由(1)式中时差方程可得:

(10)

观察(10)式,用i为0和i为其他值的两个方程相减消去二次项,整理得到线性方程组如下所示:

(11)

(11)式中Ri2=xi2+yi2+zi2,用伪逆法解(11)式可得方程组的解(x, y, z, t).但该解不能做为定位结果,因为(11)式各方程在线性化过程中,权重已经发生变化,且各个方程彼此相关,协方差矩阵不再是对角矩阵,但它离真实解很近,可以作为优良的迭代初始值.

1.3 点位协方差矩阵计算和GDOP分析

点位协方差矩阵和GDOP是分析定位误差重要的方法之一,通常观测量的协方差矩阵是已知的,可以通过未知量和观测量的关系求解出未知量的协方差矩阵.在上述迭代算法中,观测量和未知量的关系线性化为DΔXY.当结果收敛到估计值时,ΔX, ΔY就可以看做是未知量和观测量的误差.已知ΔY的协方差矩阵为W,矩阵D也是已知,根据误差传播原理, 可以算出ΔX的协方差矩阵

(12)

PX包含了时间t的误差,取出其中(x, y, z)三维部分即可得出空间任意点位误差椭球的协方差矩阵P和GDOP.

2 优化布站模型与粒子群优化算法 2.1 优化布站模型

优化布站要解决的问题是确定总体误差最小时每个站点的位置.用最优化思想来表达,优化布站建模需要一个变量x能够确定每个站点的位置,一个目标函数f(x)反应总体误差水平以及x满足的一些约束条件.

图 2为优化布站模型示意图.

图 2 三维定位优化布站模型示意图 上方红色矩形部分为目标监测区域D,下方蓝色立方体为站点空间约束区域,其中的红色实心点为待优化站点 Figure 2 The model of 3-D sites distribution optimization

模型中设计变量x需能够描述所有待优化站点坐标,考虑到坐标系之间可以通过平移和旋转进行转化, 令一个站点位置在原点处,从而减少变量维数.以四站为例,令s0(x0, y0, z0)坐标为(0, 0, 0), 其余各站坐标构成变量x

(13)

通常用一定高度平面上的误差等高线来反应特定站网的误差水平,可以用该平面误差平均值作为f(x),考虑到平面积分的复杂性,进一步用该平面中目标监测区域上均匀分布的若干点的平均误差作为目标函数,即

(14)

(14)式中s为目标区域D中选取的点.同时设计变量x还有一定约束条件,每个站点都有空间约束.

2.2 粒子群优化算法

粒子群优化算法模拟鸟类觅食的过程中存在互相通信行为,在解空间中搜索最优结果.在粒子群算法搜索中, 每个粒子都是l维解空间当中的一个点, 具有自己的位置x和速度v.每个位置对应一个适应函数值f(x).假设每个粒子具有记忆能力,能够记录自身搜索得到的最优位置和适应函数值以及整个群体搜索过程中得到的最优位置和适应函数值.粒子飞行过程中根据这两个最优值不断更新自身速度, 向最优解靠拢.设群体中粒子数量为N, 速度和位置的更新公式如下:

(15)

(15)式中,i表示第i个粒子,上标k表示第k次迭代,vixi表示第i个粒子的速度和位置,rand是随机数,在[0, 1]之间取值.Pi表示第i个粒子的搜索到的最优位置,G表示整个群体搜索到的最优位置.c1c2是加速因子,通常取数值2.w是惯性因子,取值小于1,可以取常数,数值较大时算法全局搜索能力强,数值小时收敛的快,为了让算法前期具有较好全局搜索能力,又能加快后期收敛,我们选择动态的ww(k)随着迭代次数从0.9线性递减到0.4[12~14].

粒子群算法进行优化布站的过程中的位置变量x,适应函数f(x)分别对应优化布站模型中设计变量及目标函数.模型中约束条件同样是位置变量x的约束条件,速度变量v及其范围由x以及范围确定.粒子群算法求解时在xv的范围中随机初始化每个粒子初始值.粒子群算法不需要梯度信息,稳定性好,收敛快, 适合求解优化布站问题.

3 仿真结果与对比分析

用Matlab对四站定位进行仿真计算.仿真时测时精度σt=100 ns,x为三个站点的坐标,f(x)为目标区域平均误差,粒子数N=20,站点空间约束区域为[-100 km, 100 km; -100 km, 100 km; -3 km, 3 km].x每个分量范围对应空间约束区域取值,v分量范围为对应的x分量范围的1/5.对不同定位高度和目标区域迭代100次得到最后结果如表 1所示.

表1 不同条件下四站优化布站仿真结果 Table 1 Four sites optimal simulation results under different conditions
序号 目标区域/km 定位高度/km S1位置/km S2位置/km S3位置/km 平均误差/km
1 [-50, 50;-50, 50] 5 (28.481, 100.000, 3.000) (-100.000, -28.481, 3.000) (100.000, -100.000, 3.000) 1.320
2 [-50, 50;-50, 50] 10 (100.000, -100.000, 3.000) (-100.000, -28.004, 3.000) (28.009, 100.000, 3.000) 1.291
3 [-50, 50;-50, 50] 20 (100.000, -100.000, 3.000) (28.614, 100.000, 3.000) (-100.000, -28.614, 3.000) 0.455
4 [-150, 150;-150, 150] 5 (-100.000, -100.000, 2.527) (100.000, 0.045, 2.888) (-100.000, 100.000, 2.526) 4.270
5 [-150, 150;-150, 150] 10 (100.000, 0.000, 3.000) (-100.000, -100.000, 3.000) (-100.000, 100.000, 3.000) 2.373
6 [-150, 150;-150, 150] 20 (-100.000, -100.000, 3.000) (-100.000, 100.000, 3.000) (100.000, 0.000, 3.000) 1.384

表 1中数据可以看出,同一目标区域不同高度的最优化布站结果基本相同(站点平面约束区域和目标区域都为正方形,实际有四个对称的最优站点分布方法).得到序号(1, 2, 3)组网内(目标区域小于站点平面约束区域)和(4, 5, 6)组网外的最优布站结构如图 3所示.

图 3 最优布站平面结构示意图 (a)网内优化布站结果;(b)网外优化布站结果 Figure 3 Plane structure of the optimal distribution (a) The optimal simulation results within the network; (b) The optimal simulation results outside the network

两组最优布站位置都在约束区域的边界上,大致形状是一个星型结构,同基线越长精度越高以及星型分布总体误差最小两条定性结论[6, 7]一致,验证了优化算法模型的正确性,同时该模型能够在定性结论基础上给出定量化结果.由每组的总体平均误差大小随雷电发生高度的变化可以看出,定位误差在5 km到20 km范围内随定位高度增加逐渐减小.

除了能够给出定量化结果外,时差定位算法和优化模型中设计变量选取都能自然扩展到多站情况, 目标函数f(x)在选取时,可以对监测网内的重点区域如机场, 卫星发射场等区域的误差乘以一个权重因子来提高重点区域精度,粒子群算法的求解中也可以很方便地根据实际情况对设计变量x添加其他约束条件, 能够更加灵活有效的应用到实际闪电监测网的站点位置分布设计当中.

4 三维闪电监测网站点位置分布设计应用

广西三维闪电监测网设计时计划在广西壮族自治区范围内布置20个站点实现对整个自治区的闪电监测.在站址选择前利用基于粒子群算法的优化模型进行仿真得到最优站点位置.仿真时测时精度σt=100 ns,闪电发生高度10 km,x为待优化站点坐标,f(x)为广西壮族自治区内均匀分布的若干点位平均误差.其他相关参数同四站仿真.需要注意的两点, 一是上述算法模型是在直角坐标系(XYZ)下进行的,对于实际应用中采用的是大地坐标系(BLH),计算时需要先把大地坐标转换到直角坐标,完成计算再后转回大地坐标[15];二是尽管测时误差随传播距离增加很小,但随距离增加信号会衰减,探测站可能因此无法接收到信号, 实际计算时除了空间范围约束外,还增加了另一个约束条件,即计算点位误差时只有距离该点位距离250 km之内的站点参与计算.250 km之外的探测站默认接收不到信号.

仿真所得站点最优布站位置如图 4所示,其中红色五角星表示已确定站点位置,蓝色五角星表示待优化的站点位置.仿真得到的具体位置往往不具备现实条件,通常是在最优站点位置附近寻找能够提供通信条件且有人代为管理的地点,如气象等部门的野外观测站点.因此最优仿真过程分多步完成,第一次仿真时20个站点均为待优化站点,根据仿真结果确定部分站点后,再对剩余站点继续优化仿真,图中为最后一次仿真结果.

图 4同时给出了广西三维闪电监测网水平误差(即GDOP的平面分量,实际工作中更加关注的是闪电位置的经纬度)分布,从中可以看出,监测网内大部分区域误差在200 m以下,与田彩霞等[6]得到的江苏三维闪电监测网水平误差300 m相比有50%的提高,优化布站模型实际应用效果明显,能够有效提高监测网定位精度.

图 4 广西三维闪电监测网水平误差分布图 Figure 4 Horizontal error distribution of the lightning monitoring network in Guangxi autonomous region

广西三维闪电监测网的实际站点位置和仿真站点位置如表 2所示,实际站点位置同仿真站点位置比较,除了天峨,三江,富川,梧州4个站点有误差外,其他16个站点位置均一一对应.

表2 广西三维闪电监测网站点信息表 Table 2 Sites information of 3-D lightning monitoring network in Guangxi autonomous region
站点序号 站点名称 实际纬度/°N 实际经度/°E 仿真纬度/°N 仿真经度/°E
1 环江站 24.8126 108.2605 24.8126 108.2605
2 富川站 24.8151 111.2710 23.8171 111.5712
3 田阳站 23.7363 106.9152 23.7363 106.9152
4 东兴站 21.5628 107.9517 21.5628 107.9517
5 隆林站 24.7784 105.3373 24.7784 105.3373
6 陆川站 22.3227 110.2690 22.3227 110.2690
7 梧州站 23.4780 111.3040 23.3762 111.3271
8 桂平站 23.3959 110.0839 23.3959 110.0839
9 三江站 25.7897 109.6028 25.7423 109.4562
10 天峨站 24.9719 107.1912 25.1683 107.0843
11 全州站 25.9347 111.0663 25.9347 111.0663
12 永福站 24.9871 109.9934 24.9871 109.9934
13 来宾站 23.7458 109.2267 23.7458 109.2267
14 北海站 21.4567 109.1360 21.4567 109.1360
15 横县站 22.6948 109.2580 22.6948 109.2580
16 都安站 23.9379 108.1062 23.9379 108.1062
17 那坡站 23.4156 105.8379 23.4156 105.8379
18 蒙山站 24.2037 110.5109 24.2037 110.5109
19 南宁站 22.7843 108.5473 22.7843 108.5473
20 龙州站 22.3424 106.8640 22.3424 106.8640
5 结论

本文在闪电定位算法和精度分析的基础上,提出了一种基于粒子群算法的优化布站模型, 该模型能够求解闪电监测网站点位置的最优分布方式.利用该模型对四站时差定位进行仿真,仿真结果验证了其他学者在四站布站方式下得出定性结论,同时该算法模型能够给出定量化结果,且能适应多站情况和处理约束条件,能更灵活有效的应用到工程实践当中.

在广西三维闪电监测网站点位置分布设计中,利用本文提出的模型有效的完成了优化布站.仿真所得站点位置分布使得监测网在自治区内绝大部分地区水平误差达到200 m以下,定位精度得到明显提升,算法模型为广西三维闪电监测网站址选择提供依据,在应用中取得了较好的效果.

参考文献
[1]
LOJOU J Y, HONMA N, CUMMINS K L, et al. Latest developments in global and total lightning detection[C]// Lightning (APL), 2011 7th Asia-Pacific International Conference on. New York: IEEE Press, 2011:924-932. DOI: 10.1109/APL.2011.6111048.
[2]
CHEN L W, ZHANG Y J, LU W T, et al. Performance evaluation for a lightning location system based on observations of artificially triggered lightning and natural lightning flashes[J]. Journal of Atmospheric and Oceanic Technology, 2012, 29(12): 1835-1844. DOI:10.1175/JTECH-D-12-00028.1
[3]
张萍, 赵文光. 基于云闪的雷电定位系统的误差分析[J]. 测绘通报, 2009, 28(1): 32-34.
ZHANG P, ZHAO W G. Error analysis of the lightning location system based on cloud-lightning[J]. Bulletin of Surveying and Mapping, 2009, 28(1): 32-34.
[4]
胡志祥. 雷电定位算法与误差分析理论研究[D]. 武汉: 华中科技大学, 2012.
HU Z X. Theoretical Study on Location Algorithm and Error Analysis of Lightning Targets[D]. Wuhan: Huazhong University of Science and Technology, 2012(Ch). http://d.wanfangdata.com.cn/Thesis/D229157
[5]
张萍, 赵文光, 胡志祥, 等. 雷电定位系统云闪定位精度图形因素分析[J]. 武汉大学学报(理学版), 2009, 55(2): 249-252.
ZHANG P, ZHAO W G, HU Z X, et al. Analysis of location accuracy of cloud-flash in a lightning location system by figure factor[J]. Journal of Wuhan University(Natural Science Edition), 2009, 55(2): 249-252. DOI:10.14188/j.1671-8836.2009.02.010
[6]
田彩霞, 黄启俊, 马启明, 等. 江苏省三维闪电定位系统算法仿真[J]. 武汉大学学报(理学版), 2014, 60(2): 115-121.
TIAN C X, HUANG Q J, MA Q M, et al. Algorithm simulation on 3-D lightning location system in Jiangsu province[J]. Journal of Wuhan University(Natural Science Edtion), 2014, 60(2): 115-121. DOI:10.14188/j.1671-8836.2014.02.005
[7]
刘洋, 孙秀斌, 卢舟, 等. 基于测向测时差云闪定位精度分析及布局优化[J]. 成都信息工程学院学报, 2014, 29(5): 496-502.
LIU Y, SUN X B, LU Z, et al. Location accuracy analysis and layout optimization for intracloud lightning based on AOA jointed TDOA[J]. Journal of Chengdu University of Information Technology, 2014, 29(5): 496-502.
[8]
FOY W H. Position-location solutions by taylor-series estimation[J]. IEEE Transaction on Aerospace and Electronic Systems, 1976, AES-12(2): 187-194. DOI:10.1109/TAES.1976.308294
[9]
TORRIERI D J. Statistical theory of passive location systems[J]. IEEE Transactions on Aerospace and Electronic Systems, 1984, AES-20(2): 183-198. DOI:10.1109/TAES.1984.310439
[10]
KOSHAK W J, SOLAKIEWICZ R J, BLAKESLEE R J, et al. North alabama lightning mapping array (LMA): VHF source retrieval algorithm and error analyses[J]. Journal of Atmospheric and Oceanic Technology, 2004, 21(4): 543-558. DOI:10.1175/1520-0426(2004)021<0543:NALMAL>2.0.CO;2
[11]
KOSHAK W J, SOLAKIEWIEZ R J. On the retrieval of lightning radio sources from time-of-arrival data[J]. Journal of Geophysical Research, 1996, 101(D21): 26631-26639. DOI:10.1029/96JD01618
[12]
LUI K W K, ZHENG J, SO H C. Particle swarm optimization for time-difference-of-arrival based localization[C]// Signal Processing Conference, 2007, European. New York: IEEE Press, 2007:414-417.
[13]
POLI R, KENNNEDY J, BLACKWELL T. Particle swarm optimization: An overview[J]. Swarm Intelligence, 2007, 1(1): 33-57. DOI:10.1007/s11721-007-0002-0
[14]
郭源源, 王谦, 梁峰. 基于粒子群算法的车间布局设计[J]. 计算机集成制造, 2012, 18(11): 2476-2484.
GUO Y Y, WANG Q, LIANG F. Facility layout design based on particle swarm optimization[J]. Computer Integrated Manufacturing Systems, 2012, 18(11): 2476-2484. DOI:10.13196/j.cims.2012.11.124.guoyy.022
[15]
黄丁发. GPS卫星导航定位技术与方法[M]. 北京: 科学出版社, 2009: 40.
HUANG D F. Technology and Method of GPS Satellite Navigation and Positioning[M]. Beijing: Science Press, 2009: 40.