无线传感器网络节点定位的可行方向算法

无线传感器网络节点定位的可行方向算法

常小凯

(兰州理工大学理学院, 甘肃 兰州 730050)

摘要：利用变换X VVT将平面无线传感器网络节点定位的半定松弛问题转换为非线性规划问题，提出了解决非线性规划化问题的可行方向算法。并取V的列数为2阻止高秩解的产生。对通过稀疏图的边提高计算效率。数值实验表明，此算法是行之有效的。 关键词: 无线传感器网络定位; 低秩分解; 可行方向算法; L-BFGS方法; 中图分类号：TP393 文献标志码：A

A Nonlinear Programming Algorithm for Solving Sensor

Network Localization

CHANG Xiaokai

（Science of college, Lanzhou University of Technology, Lanzhou, 730050, China）

Abstract: Semidefinite programming (SDP) relaxation of the sensor network localization (SNL) problem is reformed to be a nonlinear programming (NLP) problem by using the change of variables X VVT. Feasible direction algorithm for solving the NLP problem is proposed. The number of columns of V is chosen to be equal 2, so as to avoid the higher dimensional solutions. Computational efficiency is improved by exploiting the sparsity of graph. Numerical experiments show that our methods are efficient and robust.

Keywords: sensor network localization; low-rank factorization; feasible direction algorithm; limited memory BFGS.

无线传感器网络在军事部署，战场实时监控，环境科学，医疗护理，商业管理，追踪与监控等领域，特别是国家军事部门有非常广泛的应用。自从20世纪70年代Wen H K和Clifford D F提出智能变送器的概念（基于这种概念的网络被称之为第一代传感器网络）以来，无线传感器网络吸引了很多专家学者的注意力， 对大规模无线传感器网络节点定位的有效算法以及在不同领域的应用进行了相应的研究，并取得了很多有价值的结论。

无线传感器网络节点定位是一种图实现问题。设无向图G表示无线传感器网络，包含m个锚节点ak(k 1, ,m)和n个未知节点xi(i 1, ,n)。两个未知节点xj和xi之间的欧式距离为dture，测量距离为dji（dji dture ji），未知节点xj与锚节点ak之间的欧式距离

jiji为dture，测量距离为djk（djk dture jk），其中 ij是测量误差。在计算中，只能利用测jkjk量距离来代替真实距离。

通常情况下，并不是任何节点之间可以通信，也就是说，并不是任何节点都是相连的，

只有在某一个范围之内才可以相连。设节点的通信半径为rd，取

Nx (xj,xi):xj xi dji rd， (1) Na (xj,ak):xj ak djk rd， (2)

分别表示未知节点之间、未知节点与锚节点之间可以相连的连接节点对的集合，那么，无线传感器网络节点定位问题就可以表述为下面的多项式优化问题：

x1, ,xn

minp(x):

(j,i) Nx

x x

j

2

i

d

2ji

2

(j,k) Na

x a

j

2

k

d

2jk

。 (3)

2

nn

为便于描述，S记为n阶实对称矩阵空间，S中的标准内积A B tr(ATB)。

X0（X 0）表示X是半正定（正定）矩阵。 n m记为n m阶实矩阵空间。ei表示

第i个元素为1其余元素均为0的列向量。A(i,j),(k,h)表示由矩阵A的第i~j行、第k~h列

)是全部元素组成的矩阵。vec(A)表示由n m阶矩阵A的列叠成n m维列向量。mat(

vec( )的逆运算。0n m记为n m阶零矩阵。

取R [x1,x2, ,xn] 2 n，并且

I2

X T

R

则有

2

R

， (4) RTR

2

xj xi

其中

Aji X， xj ak Ajk X (5)

Aji (0;ej ei)(0;ej ei)T， (j,i) Nx， (6) Ajk ( ak;ej)( ak;ej)T， (j,k) Na。 (7)

文献[1-3]首次提出了解决无线传感器网络节点定位的半定规划算法，其半定规划模型如

下：

min 0 X

s.t. Aji X dji, (j,i) Nx

Ajk X djk, (j,k) Na (8) I

X 2T

R

R 0Y

TT

把条件Y RR松弛为YRR，并利用分块技术，有效地解决未知节点大于1000的

定位问题。 在此基础上，很多专家学者获得相关的理论和改进方法[4-7]。

结合等式（5），并利用半定松弛可以把多项式优化问题（3）转化为如下半定规划问题：

min

11222

(A X d) (Ajk X d2 jijijk)

2(j,i) Nx2(j,k) Na。 (9)

X0

s.t X(1,2),(1,2) I2,

目前内点算法是解决半定规划的有效算法，可是内点算法产生的是最大秩解。当 ij 0,即距离的测量有误差时，或者对于不具备唯一定位的问题，内点算法获得的解具有高秩性，

不是准确定位。甚至平面内的刚性图，可能无法通过内点算法求解半定规划而获得准确定位。下面将问题（9）转换为非线性规划，可以用解决非线性规划的一些算法进行求解定位问题。

1 非线性规划模型

1.1 非线性规划问题

半定规划问题（9）解决的最大困难是约束X 0，即自变量的半正定约束。S. Burer等人在文献[8-10]中利用变换X VVT把半正定约束的自变量X转化为无约束的自变量V，将半定规划转换为非线性规划，提出了增广Lagrange算法，数值试验表明此方法在计算时间上优于内点算法。问题（9）的约束X 0等价于X VVT，V R型（9）等价的非线性规划模型为：

(n 2) (n 2)

。因此，与模

min

11T222

(A VV d) (Ajk VVT d2 jijijk)2(j,i) Nx2(j,k) Na。 (10)

s.t (VVT)(1,2),(1,2) I2, V (2 n) (2 n)

如果距离的测量没有误差，并且非线性规划问题（10）的解的秩为2，则（4）中的

R [x1,x2, ,xn] 2 n就是未知结点的准确定位值，此时Y RTR。因此本文取

V R(n 2) 2，即V的列数为2，模型（10）可以写为如下形式：

min

112T22

(Aji VVT d2) (A VV d jijkjk)2(j,i) Nx2(j,k) Na 。 (11)

s.t (VVT)(1,2),(1,2) I2, V (2 n) 2

虽然，模型（11）是在距离的测量没有误差的假设下提出来的，但是，此模型当测量距离有

误差时，也能获得有效地结果。因为模型（11）的目标是获得最小的估计位置与真实位置之

true

间“偏差”，当测量距离有较小的误差时（ ij 0.1dij），仍然能得到有效的估计位置。后

面的数值试验也说明了估计位置的有效性。

1.2 非线性规划模型的稀疏

取网络图G(V,E)，V表示图的节点集（由锚节点和未知节点组成的集合），E表示图的边集（在通信范围之内的边）。即

V {ak:k 1, ,m} {xi:i 1, ,n}，E Na Nx。

然而要准确地获得未知节点的位置，需要足够的距离信息，而且每一个未知节点必须直接或间接地与锚节点相连接。如果半径rd过小，则会因为没有足够的距离信息而导致定位失败； 而半径rd过大，则造成计算效率的降低。而且由于现有技术的限制，距离的测量总是有限的。因此，对于不同的定位需要选择适当的半径，以获得最准确的定 …… 此处隐藏：9460字，全部文档内容请下载后查看。喜欢就下载吧 ……