摘 要：节点定位问题在无线传感器网络和Ad-hoc 网络中受到广泛的关注。多径、多址干
扰和非视距（NLOS）问题是影响定位精度的主要问题，尤其是NLOS 问题。可以采用机器
学习中的支持向量回归（SVR）的方法进行定位来降低NLOS 误差。但它的定位结果也受
到一定的NLOS 影响，精度不高。为了进一步降低NLOS 误差的影响，本文提出了一种基
于直推式回归的定位算法，它与SVR 不同，即它不是用已知样本点中带有一定NLOS 误差
的TOA 信息归纳出与其坐标相对应的一个函数关系式，而是直接从待定位节点的TOA 出
发，利用信标节点的坐标和TOA 信息并借用核函数直接推出未知节点的位置。这样就极大
程度上减少了NLOS 误差的影响，相应地也进一步提高了定位的精度。
关键词：定位；TOA；NLOS；支持向量回归；直推式回归
中图分类号：TP39
1. 引言
节点定位问题在无线传感器网络和Ad-hoc 网络中受到广泛的关注。近年来，国内外的
专家和研究机构在这方面已经做了大量的研究工作，并提出了许多定位算法。比较常用的定
位技术包括到达时间(TOA)，到达角度(AOA)，到达时间差(TDOA)，信号强度(SS)。多径、
非视距(NLOS)传输和多址干扰是定位误差的主要来源，特别是NLOS 传输，这给定位技术
提出了挑战。目前，文献[1-3]研究如何降低NLOS 传输所造成的误差，但是定位精度还不够
精确。为了减轻NLOS 的影响，提高定位精度，文献[4,5]将定位嵌入到机器学习框架内，引
入支持向量回归（SVR）实现定位。此方法假定无线电信号特征如TOA、SS 等与节点位置
坐标存在一定的关系，通过实际测量不同位置(坐标已知)的无线电信号特征，利用机器学习
的方法估计无线电信号特征与节点位置坐标的关系来实现节点位置估计，其原理如图１所
示。此算法的优点是即使训练样本数目很小，在一定程度上能很好的解决定位问题，并在一
定的NLOS 环境下降低了NLOS 传输对定位误差的不良影响。但它的不足之处[6]在于：它试
图利用训练样本中节点的坐标和TOA 值归纳出一个判别函数，然后将未知节点到参考节点
TOA 值代入此关系式估计出未知节点的位置，使得它对可能的整个样本空间分布有一个尽
可能小的期望判别误差。
图1 支持向量回归（SVR）进行定位的算法思想
1 本文得到高等学校博士学科点专项科研基金项目（20060532024，20070532089）的资助。
代写论文
- 2 -
图2 直推式回归进行定位的算法思想
然而在许多实际问题中，我们的目的仅仅是对一些特定的样本进行定位，希望能够对这
一特定待定位节点集获得尽可能小的定位误差。如果把这一特定待定位节点集加入到未知节
点的位置估计、优化等整个定位过程中，则不但可以对这一特定的待定位节点集获得良好的
定位效果，而且可以在很大程度上提高原有归纳式学习算法的推广性能，弥补了归纳式学习
算法因训练数据过少而带来的不足。这就是直推式学习的基本思想[6]，如图２所示。因此针
对用SVR 进行定位的不足，本文提出了一种新的基于直推式回归的定位算法。此算法大致
分为两个阶段，第一个阶段是用直推式回归的思想对未知节点进行位置估计，第二个阶段对
估计出的节点位置进行全局优化，进一步减小估计误差，提高定位精度。
本文的结构如下：第二节简述了直推式回归的思想，第三节是对定位模型的问题描述，
第四节详细阐述了直推式回归定位算法，并在第五节给出了实验分析，最后得出结论。
2. 直推式回归的思想
直推式学习最多的是用在机器学习中分类器的设计，用它来建立一种直接从已知样本出
发对特定的未知样本进行识别和分类的方法和原则。相对于传统的归纳和演绎推理，这种推
理方法在文献[8]中被称为直推式学习(transductive inference)。
直推式回归是基于直推式学习的思想，它是从未知样本的位置信息出发，利用已知样本
的位置和标签信息直接推出未知样本的标签[9]。并且直推式回归方法的主要优点是利用少量
的已知样本的信息可以对大量的未知标签的样本进行估计，由于无标签样本的数量较多，所
以能够较有标签样本更好地刻画整个样本空间上的数据特性，从而使训练出的分类器具有更
好的推广性能。并且计算量主要取决于少量的已知样本数，因此具有很好的性能[6,9]。
而定位是用训练样本中的已知节点（锚节点）的位置与射频特征信息和待定位节点到各
已知节点的距离信息，如到各锚节点的TOA、RSSI 等，对待定位节点进行位置估计。因此，
可以考虑把直推式回归的思想引入到节点的定位中来，用以解决节点的定位问题。
3. 定位问题描述
假设此定位模型中总样本X 中有m+u 个样本点，从中任取m 个作为训练样本，其训练
样本集的形式如下：
(x1,y1),..,(xm,ym)∈X
其中， n
i x ∈ R , (1≤i≤m+u) 表示第i 个节点相对于锚节点的射频特征向量，例如到各锚节
点的传输时延(TOA)或者信号强度(RSSI)等，本文采用TOA，而2 ,(1 ) iy∈R ≤i≤m表示锚
代写论文
- 3 -
节点的位置坐标。剩下的u 个未知坐标的节点xm+1,..,xm+u ∈X作为测试样本集。我们的
目的就是：精确地估计测试样本集中样本的坐标i y ，(m+1≤i≤m+u)。
对于回归估计中实值函数的一个假设空间H，假设一个h∈H, 0R (h)定义为整个样本
的均方差， R.(h)定义为训练样本的均方差， R(h)为测试样本的均方差。其表达式如下：
2
0
1
( ) 1 ( ( ) )
m u
i i
i
Rh hx y
m u
+
=
= .
+ Σ ， 2
1
.( ) 1 ( ( ) )
m
i i
i
Rh hx y
m =
= Σ . ， 2
1
( ) 1 ( ( ) )
m u
i i
i m
Rh hx y
u
+
= +
= Σ .
4. 直推式回归定位算法
这个算法的主要思想是直接利用待定位节点的射频特征向量――未知节点到已知参考
节点的TOA，对未知节点的位置进行估计。此算法分两个阶段。第一个阶段是基于未知节
点到已知参考节点的TOA，和训练样本集中每个节点的坐标与它的TOA 值，借用核函数[7]，
直接估计出未知节点i x 的坐标i y （i=m+1,..,m+u）。第二个阶段，寻找一个最优全局
假设h，使得已知样本点坐标和第一阶段估计出来的节点的坐标匹配，误差最小。
4.1 局部估计
定义Φ 为从特征空间X 到向量空间F 的映射，即Φ：Rn→F 。任取半径r ≥ 0 ,并固
定r，对于任一个' u x ∈ X ( u X 为测试样本集)，以Φ(x')为中心以r 为半径画圆，记作：
Β(Φ(x'),r)，这就定义了每个未知节点的像的邻域，如图３所示。对于训练样本集中的
m x ∈ X ( m X 为训练样本集)，它的像Φ(x)落在Φ(x')的邻域Β(Φ(x'),r)内有助于对x ' 的
位置进行估计。
半径r 取值越大，落在Β(Φ(x'),r)邻域内的已知节点的像就越多，估计出的未知节点
的坐标就越精确。相反，半径r 取值越小，估计出的未知节点坐标误差越大，但计算量变小。
对于固定的半径r，若在' u x ∈ X 的邻域Β(Φ(x'),r)内没有一个m x ∈ X 的像Φ(x)落在此
内，则把x ' 从此阶段删除掉。
Φ(x') r
1 Φ(x)
2 Φ(x )
3 Φ(x)
图3 以r 为半径以Φ(x')为圆心的Φ(x')的邻域( ' u x ∈ X )
代写论文
- 4 -
基于x ' 邻域Β(Φ(x'),r)内的点，如图３所示，有多种方法来确定对' u x ∈ X 的坐标进
行估计。一个简单的方法是对x ' 邻域内的点的坐标x y 求加权平均。而它们的权值W 被定义
为Φ(x)到Φ(x')的距离的倒数，或者当正定核K 与Φ 相关时它们的权值W 为K(x,x')（其
中m x ∈ X ， ' u x ∈ X ）。因此，在Φ(x')邻域内已知节点的像集不为空时，即
{ [1, ]: ( ) ( ( '), )} i I= i∈ m Φx ∈Β Φx r ≠.， ' u x ∈ X 的位置估计x' y 被定义为：
'
i i
x
i I i i
y w y
∈ w
= Σ Σ 其中， 1 ( ') ( ) i i w. = Φx.Φx ≤r 或( ', ) i i w=K x x
4.2 全局优化
算法的第二个阶段是选择一个假设h∈H（H 为回归估计中实值函数的一个假设空间），
使它既能满足训练节点的坐标，又能满足在第一阶段估计出来的节点的坐标。考虑下面的目
标函数：
2 2 2
1 1
( ( ) ) ' ( ( ) )
m mu
i i i i
i im
G w C hx y C hx y
+
= =+
= + Σ . + Σ .
其中，h 是一带权向量w∈F的线性函数：.x∈X,h(x)=w.Φ(x)，C ≥ 0 和C'≥0是正
则化参数。目标函数的第三项限制了估计误差，此约束明显地利用了所有待定位节点的坐标
信息，限制了在这些位置上假设的范围。下面给出目标函数的求解方法。
定义N 为特征空间的维数， W∈RN×2 为权值矩阵， 矩阵Y∈Rm×2 ，它的元素为训练
样本集中已知节点的坐标，矩阵Y'∈Ru×2 ，它的元素为测试样本集（即待定位节点集）中
未知节点的估计坐标i y ，定义矩阵1 [ ( ), , ( )] N m
m X= Φx .. Φx ∈R× ， ( ) i Φ x 为训练样本集
中节点i x 的像，1 i ≤ x ≤ m，同理，定义矩阵1 ' [ ( ), , ( )] N u
m mu X x x R ×
+ + = Φ .. Φ ∈ ，它的列
为待定位节点集中未知节点i x 的像( ) i Φ x ，m+1≤i≤m+u。G 被重写为：
2 2 2 G= W +C XTW.Y +C' X'TW.Y'
G 是凸的且可微，它的梯度为：
.G=2W+2CX(XTW.Y)+2C'X'(X'TW.Y')
.G = 0 时的W 使G 取得最小值，且( T ' ' 'T)
NI +CXX +CX X 是可逆的，故W 的表达式
为： ( T ' ' 'T)1( ' ' ')
N W= I +CXX +CX X . CXY+CXY
然后计算X 'T W 得到未知节点的最终的估计位置。
给定一个核K ， x 的核特征向量是一个m 维的向量为：
1 ( ) [ ( , ), , ( , )]T
m Φx =Kxx ..Kxx ，并且1 [ ( ), , ( )] N m
m X= Φx .. Φx ∈R×
代写论文
- 5 -
因此特征空间的维数N=m。相对于较小的m 即使u 非常大，由于核函数的使用，这
种方法仍然有较好的计算性能。
5. 实验分析
为了验证此定位方法的有效性，与支持向量回归（SVR）定位方法在相同仿真环境下进
行了比较。
在此实验中用椭圆散射模型来产生节点的TOA 数据[10]。并且调用了SVR 工具箱，其
中工具箱中的一些参数分别设置为：核函数采用径向基核函数（ker=”rbf”），C = 200 且
ε -insensitive 损失函数中取ε =1。
在10×10区域内随机布置了20 个信标节点和25 个未知节点，虚线区域内的三个节点
分别表示同一个待定位节点用此两种方法估计出的节点位置比较，其中，红色星号节点代表
待定位节点的真实位置，黑色加号节点代表用直推式回归方法估计出的节点位置，蓝色圆圈
节点代表用SVR 方法估计出的节点位置，如图4 所示。从表１可以看出用直推式回归比用
SVR 方法更能提高定位的精度。
表1 用SVR 和直推式回归方法定位的均方差比较
未知节点个数 SVR 均方差 直推式回归均方差
Num=5 7.20 7.08
Num=10 7.20 6.94
Num=15 7.20 6.80
Num=20 7.20 6.73
Num=25 7.20 6.58
0 2 4 6 8 10
0
2
4
6
8
10
x coordinate
y coordinate
real position
Transductive Regression
SVR
图4 用SVR 和直推式回归估计出的节点位置比较
局部估计阶段用到的参数r，在此实验中我们设置r=3。其中半径越大定位精度越高；
相反，半径越小定位误差越大，但计算量相应的减小。优化阶段用到的参数C 和C '的值与
核函数中σ 的值可由交叉验证获得。logσ 的取值对定位误差也有一定的影响，图5 显示了
代写论文
- 6 -
logσ 取不同的值时这两种方法对定位误差的影响。由于我们选用的核函数是径向基核函数,
随着logσ 取不同的值，这两条误差曲线图都近似地服从抛物线分布， 如图5 所示。logσ
的最佳取值为logσ = 0.7 ，此时两种定位方法的误差均达到最小。
0.2 0.4 0.6 0.8 1 1.2
6
6.5
7
7.5
Log sigma
Test Error
Transductive Regression
SVR
图5 logσ 对定位误差的影响
为了验证直推式回归方法比较适用于未知节点数比较多的情况，实验中我们分别选取了
几组数量不同的未知节点集进行对比，结果如图6 所示。由图可知，在直推式回归定位方法
中，未知节点数量越多，定位误差越小，相应的定位精度越高；而在SVR 定位方法中，由
于是用信标节点的坐标和其到各个参考节点的TOA 信息先估计出一个函数关系式，再由此
关系式和未知节点到参考节点的TOA 信息计算出未知节点的位置，因此未知节点数量的变
化对此方法没有影响。
5 10 15 20 25
6.4
6.5
6.6
6.7
6.8
6.9
7
7.1
7.2
7.3
7.4
Test Set Size
Test Error
Transductive Regression
SVR
图6 未知节点个数变化对定位误差的影响
6. 结论
本文提出了一种基于直推式回归的定位算法，此算法分为两个阶段，第一阶段利用训练
集中节点的坐标和TOA 信息及待定位节点集中各节点到参考节点的TOA 信息，借用kernel
函数对未知节点进行估计；第二阶段对估计出的节点位置进行全局优化，进一步减小误差，
代写论文
- 7 -
提高定位的精度。由实验可知，此算法比用SVR 进行定位更能提高定位的精度，并且此算
法比较适用于未知节点数目比较大的情况，测试样本集越大，此算法的性能越明显。
参考文献
[1] Miao Honglei, Yu Kegen and M.J. Juntti. Positioning for NLOS Propagation: Algorithm Derivations and
Cramer-Rao Bounds [J]. IEEE Transaction on Vehicular Technology, 2007.9, 56(5):2568-2580.
[2] J. Schroeder, S. Galler, K. Kyamakya, et al. NLOS detection algorithms for Ultra-Wideband localization [A].
4th Workshop on Positioning, Navigation and Communication 2007(WPNC’07) [C], Hannover, Germany. 2007,
pp:159-166.
[3]Lin Cha-Hwa, Cheng Juin-Yi, and Wu Chien-Nan. Mobile location estimation by density-based clustering for
NLOS environments [A]. Proceedings of the 20th International Conference on Advanced Information Networking
and Applications(AINA’06) [C],2006, 1(6):1-6.
[4] Wu Zhi-li, Li Chun-hung, Joseph Kee-Yin Ng, et al. Location Estimation via Support Vector Regression [J].
IEEE Transaction on Mobile Computing, March 2007,6(3):311-321.
[5] S. Gezici, H. Kobayashi and H. V. Poor. A new approach to mobile position tracking [A]. Proc. IEEE Sarnoff
Symposium On Advances in Wired and Wireless Communications [C]. Ewing, NJ, March 11-12, 2003. 204-207.
[6]陈毅松，汪国平，董士海.基于支持向量机的渐进直推式分类学习[J].软件学报，2003，14（3）：451－
460.
[7] Bernhard Scholkopf and Alex Smola. Learning with Kernels[M]. MIT Press: Cambridge, MA, 2002.
[8] Vladimir N. Vapnik. Statistical Learning Theory[M]. Wiley-Interscience, New York,1998.
[9] Cortes Corinna, Mohri Mehryar. On Transductive Regression [A]. Neural Information Processing Systems
(NIPS 2006) [C]. Volume to appear, Vancouver, Canada, 2006. MIT Press.
[10] R.B. Ertel and J.H. Reed, Angle and time of arrival statistics for circular and elliptical scattering models[J].
IEEE J. Selected Areas in Communications, 1999,17(11):1829-1840.
A Localization Method Based on Transductive Regression
Zeng Fanzi1, Tian Yukun1, Li Chaoting2
1. Institute for Computer and Communication, Hunan University, Changsha（410012）
2.Institute for Information, Guangzhou (510033)
Abstract
The problem of node localization is paid extensive attention in the wireless sensor network and ad-hoc
network. Multiple paths、multiple-address interference and NLOS problem are the main problems for
affecting the localization precision, especially the NLOS problem. It may use the support vector
regression (SVR) method of the machine learning for localization to reduce the NLOS error. But the
localization result is also affected by NLOS, and the localization precision is low. In order to further
degrade the effect of NLOS error, this paper presents a localization algorithm based on the
transductive regression. It is different from SVR, that is, It doesn’t use the TOA message with some
NLOS error of the beacon nodes to induce the function versus their positions, but it directly starts from
TOA of the unknown sensor nodes, and uses the coordinates and TOA message of the beacon nodes
and kernel function to derive the positions of the unknown nodes. So it largely reduces the effect of the
NLOS error, accordingly further improves the localization precision.
Keywords：localization; TOA; NLOS; support vector regression; transductive regression【本站部分论文来自网络和数据库，如果无意中侵犯原作者的版权，请作者及时联系我站，我站将立刻删除。本站提供全面的代写论文、论文代写、代写代发等业务，代写毕业论文、代写职称论文等服务，全心全意，欢迎咨询！】
减小字体
增大字体