东北大学学报:自然科学版  2018, Vol. 39 Issue (7): 913-917  
0

引用本文 [复制中英文]

黄越洋, 井元伟, 张嗣瀛, 石元博. 基于样本均值和中位值的粒子群优化定位算法[J]. 东北大学学报:自然科学版, 2018, 39(7): 913-917.
[复制中文]
HUANG Yue-yang, JING Yuan-wei, ZHANG Si-ying, SHI Yuan-bo. Particle Swarm Optimization Localization Algorithm Based on Sample Mean and Median[J]. Journal of Northeastern University Nature Science, 2018, 39(7): 913-917. DOI: 10.12068/j.issn.1005-3026.2018.07.001.
[复制英文]

基金项目

国家自然科学基金资助项目(61473073, 61773108)

作者简介

黄越洋(1981-),女,辽宁抚顺人,东北大学博士研究生;
井元伟(1956-),男,辽宁沈阳人,东北大学教授,博士生导师;
张嗣瀛(1925-),男,山东章丘人,东北大学教授,博士生导师,中国科学院院士。

文章历史

收稿日期:2017-03-21
基于样本均值和中位值的粒子群优化定位算法
黄越洋1,2, 井元伟1, 张嗣瀛1, 石元博1    
1. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 辽宁石油化工大学 信息与控制工程学院, 辽宁 抚顺 113001
摘要:针对室内LOS/NLOS混合环境, 提出基于假设检验的方法确定NLOS状态, 并采用具有收缩因子的粒子群优化算法进行定位.在采样值存在异常情况时, 样本中位值性能优于样本均值.因此, 在LOS和NLOS状态下, 分别采用样本均值和样本中位值建立最小平方误差代价函数.为了增强算法的全局和局部搜索能力, 在粒子群优化算法的基础上引入收缩因子.仿真实验表明, 在NLOS遮挡比较严重的情况下, 所提出的基于样本均值和样本中位值改进的粒子群优化定位算法较只采用样本均值改进的粒子群优化算法和一般的粒子群优化算法定位精度高.
关键词定位    非视距    样本均值    样本中值    粒子群优化    
Particle Swarm Optimization Localization Algorithm Based on Sample Mean and Median
HUANG Yue-yang1,2, JING Yuan-wei1, ZHANG Si-ying1, SHI Yuan-bo1    
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Information and Control Engineering, Liaoning Shihua University, Fushun 113001, China
Corresponding author: HUANG Yue-yang, E-mail: huangyueyang_1981@126.com
Abstract: The non-line-of-sight(NLOS)state was determined by the method of hypothesis testing for indoor line-of-sight/non-line-of-sight (LOS/NLOS) hybrid environment. And particle swarm optimization algorithm with shrinkage factor was used to locate. When the sampling value was abnormal, the performance of sample median was better than sample mean. Minimum square error cost functions of the sample mean and sample median were established in LOS and NLOS state. In order to enhance the global and local search ability of the algorithm, the shrinkage factor was introduced on the basis of particle swarm optimization algorithm. Simulation results show that the improved particle swarm optimization algorithm based on sample mean and median (IPSOSMM)has higher localization accuracy than that of the improved particle swarm optimization algorithm based on sample mean (IPSOSM)and the general particle swarm optimization algorithm when the NLOS block is serious.
Key Words: localization    non-line of sight    sample mean    sample median    particle swarm optimization    

无线传感器网络定位技术在过去的几十年里已经得到迅猛发展, 所涉及到的领域有雷达、声呐、航海、全球卫星定位系统等.定位估计问题已经被大量文献所探究[1-3], 但是仍然有许多没有解决的问题.其中一个关键的问题就是关于稠密、杂乱的非视距环境下的室内定位问题.非视距的出现将会大大影响定位精度.

处理非视距问题的方法主要包含两个方面:非视距辨识和非视距削弱.近年来已经有许多学者在定位算法方面作了大量研究, 并取得了一定的成果.文献[4]采用假设检验的方法确定非视距(non-line-of-sight, NLOS)状态, 并采用视距(line-of-sight, LOS)环境下的测量数据对节点进行定位.文献[5]采用一阶马尔可夫模型来估计节点的NLOS状态, 并采用带有边界约束的粒子滤波方法对节点进行定位.文献[6]不需要先验知识, 只需采用残差对所有测量距离加权, 并自适应地搜索带有最小残差的最大子集进行定位.文献[7]利用高斯混合模型对含有非视距测量信息进行训练, 并采用优选残差加权算法进行定位.文献[8]根据不同环境下的传播概率与概率密度函数建立目标函数, 并采用粒子群优化算法进行定位.

上述研究在处理非视距定位方面取得了一定的进展.但是在NLOS遮挡比较严重情况下, 提高测距质量的研究还比较少.采样均值在正态分布下是个有效的估计器, 性能优越于中位值估计的精度.然而, 当采样值存在异常值时, 采样均值的性能将大大退化.本文采用到达时间(time-of-arrival, TOA)方法对未知节点进行测量, 并且采用假设检验的方法来辨识测量距离中是否有NLOS存在.在LOS和NLOS状态下, 分别采用样本均值和样本中位值建立最小残差代价函数, 并且采用具有收缩因子的粒子群优化算法对未知节点进行定位.

1 系统模型 1.1 测量模型

基于无线传感器网络的节点定位系统由M个信标节点和1个未知节点组成.未知节点和信标节点采用TOA的测量方法获得距离信息.假设第i个信标节点的位置坐标为(xi, yi), i=1, 2, …, M.在LOS/NLOS环境下, 测量方程可以表示为

(1)

其中: 为第i个信标节点与未知节点第j次测量距离; 为第i个信标节点与未知节点真实的距离; nLOS, i, j为LOS环境下的测量噪声, 服从均值为0, 方差为σLOS2的高斯分布, 即nLOS, i, j~N(0, σLOS2); nNLOS, i, j为NLOS环境下的测量噪声, 服从均值为μ, 方差为σNLOS2的高斯分布, 即nNLOS, i, j~N(μ, σNLOS2), 不同信标节点的测量误差是相互独立的; M为信标节点的个数; P为测量次数.

1.2 样本中位值

在LOS环境下, 采用样本均值作为测量值测量精度较高.假设某个上升序列中有P个元素{d1d2, …, dP}, 那么样本均值可以表示为.在NLOS环境下, 信标节点和未知节点之间因通信受到阻碍, 使得测量值存在正的偏差, 传感器性能严重退化, 造成定位精度降低.采用样本中位值代替样本均值能阻止由于测量不精确所带来的不利影响[9].中位值是样本集上升序列的中心值.假设某个上升序列中有P个元素{d1, d2, …, dP}, 如果P为奇数, 那么中位值可以表示为median{d1, d2, …, dP}=d((P+1)/2); 如果P为偶数, 那么中位值可以表示为median{d1, d2, …, dP}=(d(P/2)+d(P/2+1))/2.

2 LOS/NLOS状态的确定

在LOS环境下, 传感器多次测量的样本均值和单次测量的样本差异很小, 但在NLOS环境下却很大.因此采用下面的假设检验法来确定测量值中是否有NLOS误差的存在.

定义如下:

(2)
(3)

其中:σi2为测量样本的无偏估计; 为样本均值; γ为门限值, 通过大量实验取为0.4.当σi2γ, 第i个信标节点与未知节点的通信状态为NLOS;当σi2 < γ, 第i个信标节点与未知节点的通信状态为LOS.

3 基于粒子群优化的无线传感器网络NLOS定位算法

辨识信标节点和未知节点测量状态后, 将对未知节点进行定位估计.为了降低计算复杂度, 本文将求解未知节点位置的计算问题转换为利用粒子群算法进行优化的过程, 通过计算最小平方误差代价函数的最小值, 求得未知节点的最佳位置估计.

3.1 最小残差代价函数

LOS环境下, 最小平方误差代价函数可以定义为

(4)

其中:di为第i个信标节点的样本均值; K为LOS状态的个数.

NLOS环境下, 最小平方误差代价函数定义为

(5)

其中:median dj为第j个信标节点的样本中位值; q为NLOS状态的个数.

综合以上两种情况, 最小平方误差代价函数定义为

(6)
3.2 具有压缩因子的粒子群优化定位算法

目前已经有许多文献从优化计算的角度对粒子群算法进行改进[10-11].由于收缩因子能有效地控制约束微粒的飞行速度, 同时增强算法的局部搜索能力.因此, 本文采用增加收缩因子的粒子群优化算法对未知节点进行定位.

假设粒子群为由N个粒子组成的种群, D为空间的维度, 这里为二维.假设群体中第i个粒子的位置为Xi=(xi1, xi2), 速度为vi=(vi1, vi2), 定义粒子的速度和位置更新方程为

(7)
(8)

其中:k为迭代次数; φ为收缩因子, , C=c1+c2, 且C>4;r1, r2为0~1之间的随机数; pij为粒子i的个体最优解; pg, jk-1为全局最优解.

粒子群优化算法流程如图 1所示.

图 1 粒子群优化算法流程图 Fig.1 Flow chart of the particle swarm optimization algorithm
4 仿真实验及分析

仿真实验中, 在100 m×100 m的室内环境中随机安放5个信标节点和1个未知节点, 并且只有1个障碍物存在.当辨识出NLOS个数为4时, 将所提出的基于样本均值和样本中位值改进的粒子群优化定位算法(IPSOSMM)与只采用样本均值改进的粒子群优化算法(IPSOSM)和一般的粒子群优化算法(PSO)进行对比.本文采用均方根误差(RMSE)作为评价方法的性能指标.

(9)

其中, n为Monte Carlo实验次数, 这里取1 000次.

在仿真实验中默认的仿真参数值如表 1所示.

表 1 默认参数值 Table 1 Default parameter values

图 2描述了LOS测量噪声传播误差标准差σLOS与RMSE间的关系.由图 2可以看出, 当σLOS比较小时, IPSOSMM、IPSOSM算法的RMSE比较接近, 随着σLOS的增加所有算法的RMSE都增大, 但PSO算法的RMSE增大得最快, 相对于其他算法IPSOSMM精度最高.

图 2 LOS测量噪声传播误差标准差σLOS与RMSE间的关系 Fig.2 RMSE versus the standard variance σLOS of LOS propagation error

图 3为NLOS传播误差均值μ与RMSE间的关系.由图 3可知, 随着μ的增加, 所有算法的RMSE都随之增加, 但PSO误差受影响的程度最为严重, IPSOSMM算法受μ影响最小.

图 3 NLOS传播误差均值μ与RMSE间的关系 Fig.3 RMSE versus the mean μ of NLOS propagation error

图 4为NLOS传播误差标准差σNLOS与RMSE间的关系.由图 4可知, 随着σNLOS的增大, 所有算法的RMSE都随之增大, 相对于PSO和IPSOSM算法, IPSOSMM算法的RMSE分别增大16.6%, 3.14%.可见IPSOSMM算法的RMSE最小, 精度最高.

图 4 NLOS传播误差标准差σNLOS与RMSE间的关系 Fig.4 RMSE versus the standard variance σNLOS of NLOS propagation error

图 5为NLOS传播个数的变化与RMSE间的关系.由图 5可以看出, 在信标节点与未知节点之间的通信状态完全是LOS的情况下, IPSOSMM的RMSE较IPSOSM的大, 随着NLOS传播个数的增加, 所有算法的RMSE都随之增大, 在NLOS传播个数接近3时, IPSOSMM的RMSE接近IPSOSM, 随着NLOS传播个数的继续增加, IPSOSMM的RMSE将小于IPSOSM.

图 5 NLOS传播个数的变化与RMSE间的关系 Fig.5 RMSE versus the number of NLOS propagation
5 结语

本文针对室内混合环境下的NLOS定位情况进行研究, 首先基于假设检验方法确定无线传感器网络中通信信号的NLOS状态.然后在LOS/NLOS状态下分别采用样本均值和样本中位值建立最小平方误差代价函数, 并采用具有收缩因子的粒子群优化算法对未知节点进行定位.仿真实验表明在NLOS遮挡比较严重的情况下, 所提出的算法精度较高, 且计算复杂度较低.

参考文献
[1]
Muller C, Alves D I, Uchoa-Filho B F, et al. Improved solution for node location multilateration algorithms in wireless sensor networks[J]. Electronics Letters, 2016, 52(13): 1179–1181. DOI:10.1049/el.2016.0688
[2]
Han S, Gao Z J, Meng W X, et al. Automatic precision control positioning for wireless sensor network[J]. Journal of IEEE Sensors, 2016, 16(7): 2140–2150. DOI:10.1109/JSEN.2015.2506166
[3]
Wu S X, Xu D Y, Wang H G. Adaptive NLOS mitigation location algorithm in wireless cellular network[J]. Wireless Personal Communications, 2015, 84(4): 3143–3156. DOI:10.1007/s11277-015-2791-6
[4]
Cheng L, Wu C D, Zhang U Z, et al. An indoor localization strategy for mini-UAV in presence of obstacles[J]. International Journal of Advanced Robotic Systems, 2012, 9(4): 1–8.
[5]
Wang J, Gao Q H, Yu Y, et al. Toward robust indoor localization based on Bayesian filter using chirp-spread-spectrum ranging[J]. IEEE Transactions on Industrial Electronics, 2012, 59(3): 1622–1628. DOI:10.1109/TIE.2011.2165462
[6]
Qiao T Z, Liu H P. Improved least median of squares localization for non-line-of-sight mitigation[J]. IEEE Communications Letters, 2014, 18(8): 1451–1454. DOI:10.1109/LCOMM.2014.2327952
[7]
崔玮, 吴成东, 张云洲, 等. 基于高斯混合模型的非视距定位算法[J]. 通信学报, 2014, 35(1): 99–106.
( Cui Wei, Wu Cheng-dong, Zhang Yun-zhou, et al. GMM-based localization algorithm under NLOS conditions[J]. Journal on Communications, 2014, 35(1): 99–106. )
[8]
刘韵婷, 张嗣瀛, 井元伟. 基于粒子群优化的无线传感器网络非视距节点定位算法[J]. 控制与决策, 2015, 30(6): 1106–1110.
( Liu Yun-ting, Zhang Si-ying, Jing Yuan-wei. Non-line-of-sight node localization algorithm based on particle swarm optimization for wireless sensor networks[J]. Control and Decision, 2015, 30(6): 1106–1110. )
[9]
Park C H, Chang J H. Robust time-of-arrival source localization employing error covariance of sample mean and sample median in line-of-sight/non-line-of-sight mixture environments[J]. EURASIP Journal on Advances in Signal Processing, 2016, 2016(1): 89–100. DOI:10.1186/s13634-016-0385-4
[10]
张亚明, 史浩山, 陈客松, 等. 一种改进的无线传感器网络优化定位算法[J]. 电子科技大学学报, 2015, 44(3): 357–362.
( Zhang Ya-ming, Shi Hao-shan, Chen Ke-song, et al. An improved optimization localization algorithm in WSNs[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(3): 357–362. )
[11]
Guo H, Low K S, Nguyen H A. Optimizing the localization of a wireless sensor network in real time based on a low-cost microcontroller[J]. IEEE Transactions on Industrial Electronics, 2011, 58(3): 741–749. DOI:10.1109/TIE.2009.2022073