资源描述：
《求解无线传感器网络定位的半定规划松驰法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第30卷第1期太原科技大学学报Vo.l30No.12009年2月JOURNALOFTAIYUANUNIVERSITYOFSCIENCEANDTECHNOLOGYFeb.2009文章编号:1673-2057(2009)01-0072-05求解无线传感器网络定位的半定规划松驰法1121马宗刚,成央金,邓胜岳,张美芳(1湘潭大学数学与计算科学学院,湖南湘潭411105;2湖南工业大学理学院,湖南株州412008)摘要:利用半定规划松驰法对无线传感器网络进行初始定位。由于半定规划松驰内点法产生的解具有高秩性,因此结合梯度局部搜索法,进一步改善
2、半定规划松驰解。计算机仿真结果证明:半定规划松驰方法具有良好的可行性和有效性。关键词:传感器网络定位;半定规划;松驰;梯度局部搜索中图分类号:O2111文献标识码:A无线传感器网络定位问题是欧几里得距离矩都为零的向量;Rank表示矩阵的秩。阵完全问题和图实现问题的一个变形,在通常状况[1]1半定规划模型下,传感器网络定位是一个NP完全问题。Bis[2,3]was.P和Ye.Y第一次构造了无线传感器网络定11无测量误差的半定规划松驰模型[4]位问题的半定规划松驰模型,而WangZhizhuo等首先描述一下无线传感器网络定位问题:已知
3、进一步松驰了这种半定规划松驰模型。由于半定m个锚点(也称信标节点)a,a,&,aRd,它们12m规划松驰法是无线传感器网络定位的近似算法,半d的位置是已知的,n个未知节点x1,x2,&,xnR,[5,6]定规划内点法产生的解具有高秩性,所以产生-它们的位置就是所求的;dik表示某个未知节点xi与的松驰解或许不是最优解,甚至不是可行解。在实某个锚点xk之间的欧几里得距离,dij表示两个未知际应用中,也不可避免出现测量误差或者测量的不节点xi和xj之间的欧几里得距离,设Nx={(i,j)
4、确定性,这往往导致半定规划松驰解在更高维空间-就使得目标函数
5、值达到最小。因此以半定规划松dij∋r,i6、dik∋r},其中r为固定驰解为节点的初始位置,结合梯度局部搜索法进一参数,也称无线电测距离。因此无线传感器网络定dn步改善这些解,使之接近于最优解。位问题就是求解[x1,x2,&,xn]R使得:n22在文章中引入一些数学记号:R表示n维欧氏%xi-xj%=dij!(i,j)Nx;TTnnn-空间;x和A分别表示xR和AR的转置;22%xi-ak%=dik!(i,k)Na(1)+sn表示n阶对称半正定矩阵;A0表示A为半正定为了简化,我们限定d=2,设X=[x1,
7、x2,&,矩阵;用!∀#表示Frobenius内积,即A∀B==tr(AB)=∃AijBij;对于同阶矩阵A,B,A2nnni,jfindXR,YRT2B表示AB是半正定矩阵;%∀%表示向量的2-s.teijYeij=dij,!(i,j)NxTI-范数或矩阵Frobenius范数%A%F=AA;Id,e,0T2X2(-ak;ei)(-ak;ei)=dik,!(i,k)NaT分别表示dd阶单矩阵,元素都是1的向量及元素XY收稿日期:20080111作者简介:马宗刚(1978-)
8、,男,硕士研究生,主要研究方向为半定规划及其应用。第30卷第1期马宗刚,等:求解无线传感器网络定位的半定规划松驰法73TY=XX(2)规划松驰解,基于网络棱分解后的松驰模型比分解其中,I2表示2维单位矩阵;eij表示第i个元素前的松驰模型运算更快速,适宜求解较大规模无线是1,第j个元素是-1,其余元素都是零的n维向量;传感器网络定位问题。ei表示第i个元素是1其余元素都为零的n维向量;12带测量误差的半定规划松驰模型T2+n(-ak;ei)=(-ak1,-ak2,0,&,0,1,0,&,0)R对于有测量误差的定位问题,通常状
9、况下,没T半定规划松驰方法就是把约束Y=XX变成松驰有解可以满足问题(1),因此可以构造一个最优化TT[7]约束YXX,而线性矩阵不等式YXX等价于问题使测量距离值与估计解产生的距离值之间的I2X)Z=0(3)差最小。假定距离误差是随机产生的,即dij=dij(1TXY)+),其中dij表示节点i与j之间的真实距离,因此半定规划松驰模型的标准形式为:2findZRnnN(0,nf)是一个随机变量,nf是一个误差因子,是T2被用来调整距离不确定性的方差。s.t(0;eij)(0;eij)∀Z=dij,!(i,j)Nx[8]22-Lian
10、g提出了极大似然估计法。设d:RRT2(-ak;ei)(-ak;ei)∀Z=dik,!(i,k)Na∗R是传感器网络节点
