第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
论文研究-基于粒子群优化的NLOS环境的节点定位算法 .pdf
中国科技论文在线
http://www.paper.edu.cn
基于粒子群优化的 NLOS 环境的节点定位
算法
文 恬，余小平，贾 勇
(成都理工大学信息科学与技术学院，成都 610059)
摘要：无线传感网络的非视距 NLOS(Non-line-of-sight)环境是影响测距定位精度的重要因素，
提 出 了 基 于 粒 子 群 优 化 PSO(Particle Swarm Optimization) 的 NLOS 环 境 的 节 点 定 位
NLOS+PSO 算法。NLOS+PSO 算法采取惯性权重的非线性调整策略，提高了算法的收敛速
度，同时，对目标值进行排序，摒弃性能差的粒子，可降低计算量。实验数据表明，在非视
距环境中，所提出的 NLOS+PSO 算法可提高定位精度，抑制 NLOS 测距误差，提高收敛速
度。
关键词：无线传感网络；定位；粒子群优化算法；非视距；惯性权重
中图分类号：TP393 文献标识码：A
Particle swarm optimization-based node localization
algorithm in non-line-of-sight environment
(College of Information Science & Technology, Chengdu University of Technology,
Wen Tian, Yu Xiaoping, Jia Yong
Chengdu 610059, China)
Abstract：Non-line-of-sight (NLOS) environment in wireless sensor network is key issue for the
precision in localization. A particle swarm optimization-based node localization algorithm in
Non-line-of-sight environment is proposed (marked as NLOS+PSO algorithm). The non-linear inertia
weight strategy is applied in NLOS+PSO algorithm to improve the convergence rate. In addition, the
fitness is sorted and particle with low performance is discard to reduce the computation. Simulation
results show that NLOS+PSO algorithm presents better localization precision and can effectively
suppress NLOS ranging-error to improve the convergence rate.
Keywords: wireless sensor network; localization; Particle Swarm Optimization; Non-line-of-sight;
inertia weight
为了完成特定的任务，可在环境中部署一系列的节点从而形成无线传感网(Wireless
Sensor Networks，WSNs)[1]。每个节点装备一个无线收发器、微型处理器以及一系列的传感
器，用于发现邻居节点并测量相应的距离。此外，还存在额外功能的特殊节点，如移动节点、
全球定位系统 (Global Position systems，GPS)。对于环境遥感、结构监察以及移动目标跟踪
等 WSNs 应用，定位成为一个关键技术。由于大多数应用依赖于准确的定位，在 WSNs 中
设计有效的定位算法非常关键。
尽管 GPS 是应用最广泛的定位服务，但是却受到成本、功耗和扩展性等问题的限制[2]。
为此，研究人员进行了大量的研究，提出了大量的定位算法。已提出的定位算法主要分为基
于测距的定位和基于非测距的定位两类。
基于测距的定位先利用通信参数信息进行测距，再利用三角算法进行定位。常用的测距
技术有到达时间 TOA(Time of Arrival)、到达时间差 TDOA(Time Different of Arrival)以及接收
信号强度 RSSI(Radio Signal Strength Indicator)等。
非测距的定位算法利用网络连通性等信息进行定位，如 DV-Hop 算法[3]、APIT 算法[4]
以及 MDS-MAP 算法[5]等。
相比于非测距定位算法，测距定位算法利用距离信息进行定位，定位精度较高，但是需
要额外的硬件设备。
测距的准确性对测距定位算法有直接的影响。然而，无线环境测距受到非视距环境的影
基金项目：国家级大学生创新创业计划项目（201410616016）
作者简介：文恬(1993—)，男，硕士研究生，主要研究方向为信息工程
通讯联系人：余小平，副教授，主要研究方向为电路与系统，电子与通信，yxpsc@126.com
-1-
中国科技论文在线
http://www.paper.edu.cn
响。大量的研究分析表明，非视距误差是测距定位的主要误差来源。文献[6]提出了基于最
大后验概率估计的定位算法，首先利用最大后验概率估计对测距误差进行非视距检测，摒弃
误差大的测距结果，然后利用加权最小二乘进行定位。尽管该算法定位精度较高，但是检测
NLOS 误差复杂、功耗较大。文献[7]提出了一种降低 NLOS 误差影响的定位算法，首先通
过最小二乘法估计每组测距的残差，然后依据残差大小对定位结果加权，进而降低 NLOS
误差对定位精度的影响。文献[8]提出了基于最小二乘的合作定位算法，解决了 NLOS 误差
问题，但是该算法的定位精度不高。
上述的这些定位算法存在计算复杂或定位精度不高的问题，研究人员着力寻找占用资源
少、定位精度高的定位算法。粒子群优化 PSO(Particle Swarm Optimization)算法是一个不错
的选择[9]。本文将 PSO 算法应用于非视距环境中的无线传感网络节点定位，提出了基于粒
子群优化的 NLOS 环境的节点定位算法(记为 NLOS+PSO 算法)，对基于粒子群中的惯性权
重进行改进，进而降低非视距对定位精度的影响，并提高算法的收敛速度。
1 约束条件及问描述题
a
a
A
[
}M
,
和
{1, 2,
p p
T
T
1
2
M N
+ }
M
x y
,
i
i
ν
M
{ +1,
p
(
i
j
。锚节点
1.1 系统模型
考虑一个分布于二维空间的有 M 个未知节点和 N 个锚节点的无线定位网络，设定
+ 2,
,
分别为未知节点集和锚节点集。未知节点
i 的 位 置 标 识 为
。 相 应 地 ， M 个 未 知 节 点 的 位 置 矢 量 为
)
p
的位置标识为
对于每对节点，考虑 R 组测距值进行距离估计。节点 i 和节点 j 的真实距离为 dij。第 n
个测距值对 dij 的距离值为 ：
式中， [ ]
测距偏差，且均值 { [ ]}
b n n
(1)
[ ] + [ ]
1, 2,
,
ij
ijz n ～
Ν
)
ij(
ijz n 为零均值的高斯测量噪声，且 [ ]
0,
； [ ]
2
b n
。
Var{ [ ]}
2
ij
ij
R
ijb n 为因NLOS导致的
,x y 。
i
；方差
E b n
d n
[ ]
ˆ
ij
p
]M
z n
ij
L
i
p
i
+
p
i
(
)
A
T
ij
ij
j
为 了 解 决 LS 定 位 问 题 [10] ， 引 用 R 个 测 距 值 的 样 本 均 值 有 ：
d
ˆ
ij
d n
[ ]
ˆ
ij
(2)
b
ij
p
i
p
z
R
ij
j
1
R
n
=1
式中，
z
ij
R
1
R
n
=1
z n
[ ]
ij
b
ij
；
R
1
R
n
=1
b n
[ ]
ij
。
NLOS 偏差变量 [ ]
ijb n 为独立同分布的随机变量，利用 [ ]
ijb n
ijd nˆ 的无偏差样本方差估计 [ ]
的方差，有：
1
1
2
n
)
(
1
R
d
ˆ
ij
ˆ
2
ij
2
ij
(3)
d n
ˆ
[ ]
ij
N
1.2 问题描述
本文以最小二乘法为例，阐述 NLOS 测距误码对定位的影响。设定 xi 表示 i 个未知节
点位置，并且
x 。位置矢量 p 的 LS 协作定位的位置估计 ˆp：
]M
T
x
x
T
2
[
argmin
x R
∈
2
f
ˆ =p
其中：
f
LS
x
( )
i
ν
a
j ν
a
ν
A
c
ij
2
ij
2
ij
x
T
1
x
( )
LS
(4)
d
(
ˆ
ij
b
ˆ
ij
x
i
x
j
)
2
(5)
-2-
中国科技论文在线
http://www.paper.edu.cn
式中， ijbˆ为偏差估计； ijc 为连接因子。如果节点 i 和 j 能够连接， ijc =1；否则 ijc =0。此外，
如果是在 LOS 环境中， ijbˆ 为无偏差估计， { }ij
E b ˆ
ij
。
文献[11-13]提出了众多缓解 NLOS 测距的偏差影响的方案。
n 对 p 估计有直接影响，而在实际环境中，
从式(4)和(5)可看出，NLOS 偏差变量 [
i jb
]
NLOS 的测距偏差是不可避免的。因此，在 NLOS 环境中，定位算法必须考虑 NLOS 的测
距偏差。为此，本文提出面向 NLOS 环境的 WSN 的基于粒子群优化算法 NLOS+PSO，以
缓解 NLOS 测距偏差对位置估计的影响，从而提高定位精度。
2 NLOS+PSO 算法
分析可知，测距过程中一定存在 NLOS 的测距偏差，并且该偏差对位置估计有直接的
影响。因此，所提出的 NLOS+PSO 算法就是从已有的测距中，选择较准确的测距数据，丢
弃误差的数据，从而提高定位精度。接下来，首先分析传统粒子群优化算法原理，随后提出
其改进算法。
粒子群优化算法首先在某特定区域随机地选择一组位置坐标，并将该组位置坐标作为初
始粒子；然后将初始粒子代入目标函数，进而计算适应度；最后获取粒子的最优位置和整个
种群当前的最优位置。
2.1 粒子群优化算法原理
假 定 第 i 个 粒 子 位 置 坐 标 为
,
,
2
为粒子速度，其迭代方式为：
， 其 中 r 表 示 空 间 维 度 ；
(
)
x
i
1
x
ir
x
i
x
i
(
)
,
k
( +1)
i
rand(
1
1
k
( )
i
p
best
i
k
( ))
x
i
g
rand (
2
best
2
g
x
i
( ))
k
(6)
x
i
k
( )
i
k
( + 1)
k
( + 1)
(7)
x
i
式中，k 为迭代次数； 1 和 2 为加速度系数； 1
为惯性权重系数； besti
子全局最优位置。
此外，适应度表示粒子到每个锚节点之间的距离与测距结果的平均误差值，其值为：
rand 分别为两个 0～1 的随机数；
g 表示当前群体所有粒
p 表示第第 i 个粒子经历的个体最优位置； best g
rand 和 2
f
x y
( , )
1
M
N
i
1
( (
x
x
i
)
2
(
x
)
2
y
i
d
i
)
(8)
式中， id 表示粒子离锚节点 i 的测距值。适应度是粒子群优化算法的重要参数，直接影响定
位精度。
2.2 粒子优化算法的改进
为了提高粒子优化算法的定位精度，NLOS+PSO 算法对惯性权重系数进行了优化。惯
性权重系数越大，粒子速度越大，全局搜索能力也越强；反之则局部搜索能力强。为此，将
惯性权重函数定义为：
k
( )
(
min
max
)exp
h
(
2
k
iter
max
2
)
min
(9)
iter 表示迭代的最大次数。
式中，h 表示扩展常系数；k 表示当前的迭代次数； max 和 min 分别表示惯性权重系数的最
大值和最小值； max
调整扩展常系数 h 的值可改变惯性权重函数的非线性。研究表明，h=0.2 时，粒子群优
化算法的收敛速度最快。h 分别为 0.1、0.2 和 0.3 时，惯性权重函数随迭代次数的变化情况
如图 1 所示。
-3-
中国科技论文在线
http://www.paper.edu.cn
0.9
0.85
0.8
0.75
0.7
0.65
0.6
0.55
0.5
0.45
重
权
性
惯
0.4
0
5
10
15
h=0.1
h=0.2
h=0.3
30
35
40
45
50
20
25
迭代次数k
图 1 惯性权重函数
从图 1 可知，惯性权重函数随迭代次数的增加迅速递减。在迭代初期，惯性权重以凸
函数递减，有利于全局搜索最优解。随着迭代次数的增加，惯性权重函数以凹函数递减，有
利于算法的收敛。整个曲线变化逼近于凹函数递减曲线，与文献[14]的结论吻合。在凹函数
递减情况下，调整惯性权重凹函数递减，可得到最优的定位性能。
收敛速度也是表示粒子群优化算法的重要性能，为了提高收敛速度，可对粒子的速度和
位置进行优劣排序，每次迭代，摒弃一半性能较差的粒子，将性能较好的另一半粒子进入下
一轮迭代，有：
s f
(
sort
(1:
N
))
x
sort
sort
N
2
N
2
:
:
N
N
x
sort
sort
1 :
1:
N
2
N
2
(10)
和 sort 分别为排序后的粒子位置和速度集合。
s f
(
(1 :
式中， sort
2.3 NLOS+PSO 算法流程
N 为选择函数； sortx
))
依据以上分析，首先提出 NLOS+PSO 算法的初始参数，再计算每个粒子的目标函数，
然后存储粒子的个体最优适值 bestp 和全局最优适值 bestg ，并通过对惯性权重函数的调整，反
复迭代，筛选出最优的测距数据。所提出的 NLOS+PSO 算法伪代码如下：
(1) initialize itermax,c1,c2,and /*初始参数*/
(2) for each particle i do
(3) for each dimension r do /*每一维数据*/
(4) initialize vi randomly: vmin≤vi≤vmax
(5) End for
(6) End for
(7) for (k=0;kƒ(T) then
(9) for each particle i do
(10) compute ƒ(xi)
(11) If ƒ(xi)<ƒ(
besti
(12) for each dimension r do
p
(13)
besti
(14) End for
(15) End if
(16) If ƒ(xi)<ƒ(gbest) then
(17) for each dimension r do
p
(18)
best g
(19) End for
(20) End if
) then
= xi
= xi
g
-4-
http://www.paper.edu.cn
中国科技论文在线
(21) update by (11)
(22) for each particle i do
(23) for each dimension r do
(24) compute velocity vi(k+1) by (8)
(25) restrict vi to vmin≤vi≤vmax
(26) compute position xi(k+1) by (9)
(27) End for
(28) End if
(29) sort ƒ(xi) from best to worst
(30) End while
3 系统仿真
3.1 系统参数
利用 Matlab 建立仿真系统，并分析算法性能。80 个传感节点分布于100 m 100 m
区
域。其中，锚节点个数在 5～30 之间变化;另外，节点通信范围=30 m；加速度系数1 和2
为 1.494；惯性权重系数的最大值和最小值分别为 max
；最大迭代次数
。每次实验独立重复 100 次，取平均值作为最终的仿
iter
真数据。
此外，选择平均定位误差 avge 作为性能指标，有：
50 ；粒子最大速度 max
和 min
10
0.9
0.4
max
m
(
x
i
(
y
i
y
ˆ
i
2
)
2
)
x
ˆ
i
mγ
式中，xi 、yi 表示第 i 个节点的真实位置； iˆx 、 iˆy 为估计位置；m 表示已定位的未知节点个
数。
3.2 仿真结果
(11)
e
avg
=1
i
为了更充分地分析算法性能，选择 LS、IMR 和传统的粒子群算法 PSO 进行仿真比较。
(1) 平均定位误差
10 个具有偏差的锚节点所占百分比为 0%时，平均定位误差随 NLOS 偏差的变化曲线如
图 2 所示。
e
差
误
位
定
均
平
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
4
LS
IMR
PSO
NLOS+PSO
4.5
5
5.5
6
6.5
NLOS
测距误差
(m)
7
图 2 平均定位误差随 NLOS 误差变化曲线
从图 2 可知，随着 NLOS 误差的增加，所有算法的平均定位误差呈增加趋。其中 LS 算
法的波动最大，当 NLOS 误差达到 7 m 时，LS 算法的平均定位误差已高达 65%，而其他的
IMR、PSO 和 NLOS+PSO 算法平均定位误差的变化较平衡，其中 NLOS+PSO 算法的平均定
位误差最小，表明提高了在 NLOS 环境中的定位精度。
-5-
中国科技论文在线
http://www.paper.edu.cn
在 NLOS 偏差服从均值为 6，标准差为 1 的高斯分布环境中，平均定位误差随锚节点个
数的变化情况如图 3 所示。
LS
IMR
PSO
NLOS+PSO
e
差
误
位
定
均
平
0.6
0.55
0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
5
10
15
20
25
锚节点个数
图 3 平均定位误差随锚节点个数的变化曲线
30
从图 3 可知，平均定位误差随锚节点个数的增加呈下降趋势。但是本文所提出的
NLOS+PSO 算法的定位精度更高，原因在于 NLOS+PSO 算法进行区域约束，锚节点越多，
对未知节点的区域估计越准确。
(2)迭代次数
迭代次数是考量算法的重要性能，为此，分析传统的 PSO 和本文所提 NLOS+PSO 算法
的迭代次数性能。
迭代次数对算法性能的影响如图 4 所示。
40
30
20
10
数
次
代
迭
0
10
60
40
20
数
次
代
迭
PSO
NLOS+PSO
15
20
锚节点个数
PSO
NLOS+PSO
25
0
4
5
6
7
误差
(m)
NLOS
8
9
10
图 4 迭代次数对算法性能的影响
图 4 表示 NLOS 偏差服从 4～8 m 均匀分布，锚节点个数分别为 10、15、20、25 时，
迭代次数对算法性能的影响；以及锚节点个数为 15，NLOS 偏差分别为 4 m、6 m 和 8 m 时，
迭代次数对算法性能的影响算法。
从图 4 可知，本文所提出的 NLOS+PSO 算法的迭代次数远少于 PSO。这主要是通过对
惯性权值的更新，加速了算法的收敛。
(3) 时间
相同迭代次数时，各算法的耗时如表 1 所示。从表 1 可知，LS 算法的耗时最长， PSO
耕时最短，而本文所提出的 NLOS+PSO 算法的耗时略多于 PSO。原因在于 NLOS+PSO 算
法的惯性权重在形式上更为复杂，增加了计算量。
算法
LS
IMR
PSO
NLOS+PSO
表 1 算法耗时 (单位：毫秒)
迭代次数
10
41.19
29.23
30.92
34.02
100
93.36
52.23
40.18
42.38
1
39.82
31.82
23.82
30.14
-6-
中国科技论文在线
4 总 结
http://www.paper.edu.cn
本文针对 NLOS 测距误差，提出了基于粒子群优化 PSO 的 NLOS 环境的节点定位算法，
并将粒子群优化算法引用至无线传感网络定位。首先对粒子群优化算法的参数进行了改进，
对惯性权重进行非线性调整，提高了算法的收敛速度；另外，对目标值进行排序，降低了计
算量。仿真结果表明，本文所提出的算法降低了 NLOS 误差的影响，提高了定位精度。今
后将研究适应度函数的选取，合理地构造适应度函数，进一步提高算法的定位准确性。
参考文献（Reference）
[1] Hackmann G, Castaneda N. A holistic approach to decentralized structural damage localization using wireless
sensor networks[J]. Computer Communications, 2012, 36(1): 29-41.
[2] 王行甫, 刘志强, 黄秋原. WSN 中一种改进的边界盒定位算法[J].计算机工程, 2011, 37(20): 57-59.
Wang Xingfu, Liu Zhiqiang, Huang Qiuyuan. Improved bounding-box localization algorithm in WSN[J].
Computer Engineering, 2011, 37(20):57-59. (in Chinese)
[3] Niculescu D, Nath B. DV based positioning in ad hoc networks[J]. Telecommunication Systems, 2003, 22(1-4):
267-280.
[4] He Tian, Huang Chengdu, Blum B M. Range-free localization schemes in large scale sensor networks[J].
Mobile Computing and Networking, 2013,14(2): 81-95.
[5]Shang Yi, Ruml W, Zhang Ying. Localization from mere connectivity[J]. Mobile Ad Hoc Networking and
Computing, 2011,12(5):201-212.
[6]Lui K W K, So H C, Ma W K. Maximum a posteriori approach to time-of-arrival-based localization in
non-line-of-sight environment[J]. IEEE Transactions on Vehicular Technology, 2010, 59(3): 1517-1523.
[7] Chen Pengchao.A non-line-of-sight error mitigation algorithm in location estimation[J]. IEEE Wireless
Communications and Networking Conference. IEEE, 1999: 316-320.
[8] Nguyen T V, Jeong Y, Shin H, et al. Least square cooperative localization[J]. IEEE Transactions on Vehicular
Technology, 2015, 64(4): 1318-1330.
[9] Chan F K W, So H C. Accurate distributed range-based positioning algorithm for wireless sensor networks[J].
IEEE Transactions on Signal Processing, 2009, 57(10): 4100-4105.
[10] Larsson E G, Danev D. Accuracy comparison of LS and squared-range LS for source localization [J]. IEEE
Transactions on Signal Processing, 2010, 58(2): 916-923.
[11] Marano S, Gifford W M, Wymeersch H, et al. NLOS identification and mitigation for localization based on
UWB experimental data[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(7): 1026-1035.
[12] Wymeersch H, Maranò S, Gifford W M, et al. A machine learning approach to ranging error mitigation for
UWB localization[J]. IEEE Transactions on Communications, 2012, 60(6): 1719-1728.
[13] Decarli N, Guerra A, Conti A, et al. Non-regenerative relaying for network localization [J]. IEEE
Transactions on Wireless Communications, 2014, 13(1): 174-185.
[14]Dardari D. Threshold-based time-of-arrival estimators in UWB dense multipath channels[J]. IEEE
Transactions on Communications, 2008, 56(8): 1366-1378.
-7-
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
