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

《无线传感器网络节点定位可行方向算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、无线传感器网络节点定位的可行方向算法常小凯(兰州理工大学理学院,甘肃兰州730050)摘要：利用变换将平面无线传感器网络节点定位的半定松弛问题转换为非线性规划问题，提出了解决非线性规划化问题的可行方向算法。并取的列数为2阻止高秩解的产生。对通过稀疏图的边提高计算效率。数值实验表明，此算法是行之有效的。关键词:无线传感器网络定位;低秩分解;可行方向算法;L-BFGS方法;中图分类号：TP393文献标志码：AANonlinearProgrammingAlgorithmforSolvingSensorNetworkLocalizationCHANGXiaokai（Scienc

2、eofcollege,LanzhouUniversityofTechnology,Lanzhou,730050,China）Abstract:Semidefiniteprogramming(SDP)relaxationofthesensornetworklocalization(SNL)problemisreformedtobeanonlinearprogramming(NLP)problembyusingthechangeofvariables.FeasibledirectionalgorithmforsolvingtheNLPproblemisproposed.Th

3、enumberofcolumnsofVischosentobeequal2,soastoavoidthehigherdimensionalsolutions.Computationalefficiencyisimprovedbyexploitingthesparsityofgraph.Numericalexperimentsshowthatourmethodsareefficientandrobust.Keywords:sensornetworklocalization;low-rankfactorization;feasibledirectionalgorithm;l

4、imitedmemoryBFGS.无线传感器网络在军事部署，战场实时监控，环境科学，医疗护理，商业管理，追踪与监控等领域，特别是国家军事部门有非常广泛的应用。自从20世纪70年代WenHK和CliffordDF提出智能变送器的概念（基于这种概念的网络被称之为第一代传感器网络）以来，无线传感器网络吸引了很多专家学者的注意力，对大规模无线传感器网络节点定位的有效算法以及在不同领域的应用进行了相应的研究，并取得了很多有价值的结论。无线传感器网络节点定位是一种图实现问题。设无向图表示无线传感器网络，包含个锚节点和个未知节点。两个未知节点和之间的欧式距离为，测量距离为（），未知节

5、点与锚节点之间的欧式距离为，测量距离为（），其中是测量误差。在计算中，只能利用测量距离来代替真实距离。通常情况下，并不是任何节点之间可以通信，也就是说，并不是任何节点都是相连的，只有在某一个范围之内才可以相连。设节点的通信半径为，取，(1)，(2)分别表示未知节点之间、未知节点与锚节点之间可以相连的连接节点对的集合，那么，无线传感器网络节点定位问题就可以表述为下面的多项式优化问题：。(3)为便于描述，记为阶实对称矩阵空间，中的标准内积。（）表示是半正定（正定）矩阵。记为阶实矩阵空间。表示第个元素为1其余元素均为0的列向量。表示由矩阵的第行、第列全部元素组成的矩阵。表示由

6、阶矩阵的列叠成维列向量。是的逆运算。记为阶零矩阵。取，并且，(4)则有，(5)其中，，(6)，。(7)文献[1-3]首次提出了解决无线传感器网络节点定位的半定规划算法，其半定规划模型如下：(8)把条件松弛为，并利用分块技术，有效地解决未知节点大于1000的定位问题。在此基础上，很多专家学者获得相关的理论和改进方法[4-7]。结合等式（5），并利用半定松弛可以把多项式优化问题（3）转化为如下半定规划问题：。(9)目前内点算法是解决半定规划的有效算法，可是内点算法产生的是最大秩解。当,即距离的测量有误差时，或者对于不具备唯一定位的问题，内点算法获得的解具有高秩性，不是准确定

7、位。甚至平面内的刚性图，可能无法通过内点算法求解半定规划而获得准确定位。下面将问题（9）转换为非线性规划，可以用解决非线性规划的一些算法进行求解定位问题。1非线性规划模型1.1非线性规划问题半定规划问题（9）解决的最大困难是约束，即自变量的半正定约束。S.Burer等人在文献[8-10]中利用变换把半正定约束的自变量转化为无约束的自变量，将半定规划转换为非线性规划，提出了增广Lagrange算法，数值试验表明此方法在计算时间上优于内点算法。问题（9）的约束等价于，。因此，与模型（9）等价的非线性规划模型为：。(10)如果距离的测量没有误差