何国钢，邓 平

(西南交通大学信息编码与传输重点实验室，成都610031)

无线传感器网络(WSN，Wireless Sensor Networks)，由于其在军事侦察、交通监管、工农业控制、环境监测、物联网、抢险救灾等领域广阔的应用前景，已经成为国际上备受关注的研究课题之一。在WSN的应用中，一个关键问题是如何获取网络节点的地理位置信息。因此，定位技术是一项非常重要的研究内容。定位算法根据采用的定位信息不同，可分为基于非测距和基于测距定位算法[1－2]。前者通常利用网络的连通性等信息进行定位，而后者则是利用测距装置获得的节点间的距离信息实现定位。由于非测距算法定位精度不理想，基于测距定位算法成为实际应用中采用的主要定位解决方案。然而，在噪声环境下，距离测量值的不准确性会导致测距定位算法定位精度明显下降。因此，研究噪声环境下传感器网络测距定位技术是非常必要的。

无线传感器网络定位问题可以被视为作图实现问题[3]，通过将图中的边作为约束，将其建模成一个半定规划SDP(Semi-Definite Programming)问题，从而实现定位。近年来，部分学者开展了相关的研究工作。文献[4]将节点间点到点的通信连接视为节点位置的几何约束，将定位问题转化为凸优化问题，并通过半定规划进行求解，然而其定位精度不高。与文献[4]非测距方法相比，文献[5]提出了一种基于测距的半定规划定位方法，第一次构造了无线传感器网络定位问题的半定规划松弛模型——fullSDP，该方法需要较少的锚节点即可完成定位。针对fullSDP计算复杂度过高不适合解决较大规模WSN定位问题的缺点，文献[6]将单一的半正定矩阵锥松弛为一系列较小的半正定矩阵锥，进一步松弛了半定规划定位模型，有效地降低了计算复杂度。文献[7]也利用定位问题的稀疏性提出了一种半定规划松弛模型的稀疏版本，提高了解决定位问题的效率。文献[8]则是将半定规划定位问题划分成多个子问题进行求解。为解决大规模WSN定位问题，研究人员也提出了多种分布式半定规划定位算法[9－10]。

1 高斯噪声下WSN半定规划定位

1.1 问题描述

在二维平面中，无线传感器网络中分布着m个锚节点和n个未知节点。假设所有节点的通信范围为半径为R的圆，当节点间的实际距离不大于通信半径时，则两节点能够直接通信。定义分别为未知节点i与锚节点k间距离的真实值和测量值;未知节点 i和 j间距离的真实值和测量值。X={x1，x2，…，xn}∈R2×n表示未知节点矩阵，A={a1，a2，…，am}∈R2×m表示锚节点矩阵。定义矩阵，则无线传感器网络定位问题可以表示为式(1):

其中，eij为第i个元素为1第j个元素为－1的n维列向量;ei为第i个元素为1的n维列向量;Nx表示能够直接通信的未知节点对的集合;Na表示能够直接通信的未知节点与锚节点对的集合。

为解决式(1)中的传感器网络定位问题，文献[5]通过引入松弛变量并应用舒尔补定理将传感器网络定位问题松弛为半定规划问题，得到基于测距的传感器网络定位问题的半定规划松弛模型(fullSDP)[5]:

为进一步提高定位精度，文献[12]提出将半定规划的解作为初始点，使节点沿着节点距离误差的负梯度方向移动，将梯度搜索方法应用到定位问题中，其中目标函数为:

对f进行求导，目标函数f在xi的梯度为:

假设梯度搜索方法的迭代步长为α，则其迭代公式如式(5)。当∂fxi接近零或达到最大迭代次数时，则沿xi方向的搜索结束。

现有研究表明，以式(2)的解作为初始点，梯度搜索方法能有效地改善半定规划的定位结果。然而，当节点间距离测量受噪声影响时，通过式(2)求解得到的节点估计位置将会向锚节点凸包中心汇聚[10]。这种汇聚效应将使部分节点定位误差太大而不适合作为梯度搜索方法的初始解，导致梯度搜索方法改善定位结果的效果不明显，甚至会进一步恶化半定规划的定位结果。

人力资源管理系统主要是采用B/S(Browser/Server)架构即浏览器／服务器架构为支撑，该架构是随着英特网技术的兴起，并对C/S架构进行改进的一种优化架构。此外，在B/S架构下，用户所有的工作界面均是运用WWW浏览器来实现整个的，也有极少一部分事务逻辑是通过前端(Browser)实现的，但是大多数事务逻辑都运用服务器端(Server)来实现，进而形成完整的三层架构。和传统架构相比，这种架构优势非常明显，主要表现为维护运行方法较为简便、快捷，能够从不同地域和不同的人员进行自由选择，并运用不同的接入方式来完成数据访问与操作工作。

1.2 最大分散度SDP定位算法

为解决fullSDP在噪声环境下存在的问题，本文借鉴文献[13]中非测距定位算法中分散度的概念，在测距定位中，定义分散度SD(Scatteredness Degree)为所有未知节点与锚节点质心间的距离的均方值，即:

假设节点间的测量距离受高斯噪声影响，则:

利用节点间距离的测量值和噪声的标准差，可以确定节点间距离的一个上界，如式(8):

将最大化网络分散度作为目标函数，式(8)作为约束条件，传感器网络定位问题可以表示为如式(9)的最优化问题。

由高斯分布的性质可知，部分节点间的距离不满足式(8)，即存在误差。为此，加入松弛变量βij和βik，则最优化问题式(9)的目标函数中应包含最小化误差项，如式(10):

其中，p(η)是定义的目标函数平衡因子，其值与网络平均连通度η有关。根据仿真与数值分析，p(η)可以由式(11)确定。

将最优化问题(9)表示为矩阵形式，并将其松弛为半定规划模型，则最大分散度半定规划定位算法MSDSDP(Maximum Scatteredness Degree SDP)如式(12):

为了进一步提高定位精度，同样将作为初始点进行梯度搜索，以期进一步提高定位精度。

2 仿真与分析

假设无线传感器网络60个未知节点随机分布在一个1×1的正方形区域中，锚节点的分布和通信半径R将在具体的仿真实验中说明。节点间距离的测量值通过式(13)得到。

2.1 仿真实验1

设置锚节点个数为8，噪声因子为0.2，通信半径为0.25，仿真结果如图1所示。由图可以看出，MSDSDP能在一定程度上克服fullSDP节点估计位置向锚节点凸包中心汇聚的问题。图1中圆圈表示未知节点真实位置，星型表示未知节点估计位置，直线表示定位误差，棱形表示锚节点。

图1 两种算法仿真结果示意图

2.2 仿真实验2

本实验研究通信半径R的影响。设置锚节点个数为8，噪声因子为0.2，通信半径 R分别设为0.2，0.25，0.3，0.35，0.4(连通度分别为 7.22，10.93，14.95，19.63，25.03)，仿真结果如图 2 所示。由图可以看出，MSDSDP的定位精度优于fullSDP，尤其是在低连通度情况下。图2显示，在低连通度下出现了梯度搜索方法使fullSDP定位结果恶化的情况;MSDSDP的解比fullSDP更适合用于梯度搜索方法的初始解。

图2 通信半径R对MSDSDP的影响

2.3 仿真实验3

本实验研究噪声因子的影响。设置锚节点个数为8，通信半径为0.25，仿真结果如图3所示。图中可以看出，MSDSDP随着噪声的增大，定位精度逐渐下降，但是明显优于fullSDP及其梯度搜索后的定位精度。图3表明，MSDSDP结合梯度搜索方法能够很好地解决高斯噪声下传感器网络定位问题，并再一次表明MSDSDP的解比fullSDP更适合用于梯度搜索方法的初始解。

图3 噪声因子对MSDSDP的影响

2.4 仿真实验4

本实验研究锚节点个数的影响。设置通信半径为0.25，噪声因子为0.2，仿真结果如图4所示。图中显示，半定规划定位方法在锚节点个数很少的情况下也能达到良好的定位精度。然而，MSDSDP在锚节点数量少时，定位精度明显高于fullSDP，并且对锚节点个数具有更好的鲁棒性。

根据文献[5]，fullSDP采用内点法解决n个节点的传感器网络定位问题的计算复杂度为O(n3)。由式(2)和式(12)可以看出，MSDSDP的变量个数和约束条件个数与fullSDP相同，由此推断MSDSDP的计算复杂度也为O(n3)。综上分析可知，相对于fullSDP，MSDSDP在不增加计算复杂度的情况下能够明显提高定位精度。由文献[6]分析知，梯度搜索方法的计算复杂度为O(λn)(λ为迭代搜索次数)，远远小于半定规划的计算复杂度。因此，MSDSDP结合梯度搜索方法能在增加较小代价的情况下定位精度明显得到改善。

图4 锚节点个数对MSDSDP的影响

3 结论

本文提出了一种新的在噪声情况下最大化网络节点分散度的半定规划定位算法(MSDSDP)。该算法能够有效地克服fullSDP中节点向锚节点凸包中心汇聚的问题，定位精度得到有效提高。分析还表明MSDSDP对网络连通度、噪声水平和锚节点个数更具鲁棒性，并且MSDSDP的解更适合作为梯度搜索方法的初始解。因此，MSDSDP结合梯度搜索方法能够适用于具有噪声的实际WSN网络环境中未知节点的定位。

[1]杨凤，史浩山，朱灵波，等.一种基于测距的无线传感器网络智能定位算法[J].传感技术学报，2008，21(1):135－140.

[2]石为人，贾传江，梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感技术学报，2011，24(1):83－87.

[3]Man-Cho So A，Ye Yinyu.Theory of Semidefite Programming for Sensor Network Localization[J].Math Program，2007，109:367－384.

[4]Doherty L，Ghaoui L E，Pister S J.Convex Position Estimation in Wireless Sensor Networks[C]//IEEE Infocom，Anchorage，2001:1655－1663.

[5]Biswas P，Ye Y.Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization[C]//3rd IPSN，Berkeley，2004:46－54.

[6]Wang Zizhuo，Zheng Song，Boydy Stephen，etal.Further Relaxations of the SDP Approach to sensor Network Localization[Z].Dept of Management Science and Engineering，Stanford University，2006.

[7]Sunyoung Kim，Kojima M.Semidefinite Programming Relaxations forSensor Network Localization[C]//IEEE International Symposium on Computer-Aided Control System Design，2010.

[8]Carter M W，Jin H H，Saunders M A，et al.An Adaptive Subproblem Algorithm for Scalable Wireless Sensor Network Localization[J].SIAM，2006，17(4):1102－1128.

[9]Biswas P，Ye Y.A Distributed Method for Solving Semidefinite Programming Arising from Ad Hoc Wireless Sensor Network Localization[R].Dept of Management Science and Engineering，Stanford University，2006.

[10]Shi Q，He C，Chen H，et al.Distributed Wireless Sensor Network Localization via Sequential Greedy Optimization Algorithm[J].IEEE Transactions on Signal Processing，2010，58(6):3328－3340.

[11]Biswas P，Liang T C，Toh K C，et al.Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements[J].IEEE Tran.Auto.Sci.and Eng，2006，3(4):360－371.

[12]Liang T，Wang T，Ye Y.A Gradient Search Method to Round the Semidefinite Programming Relaxation Solution for Ad Hoc Wireless Sensor Network Localization[R].Dept of Management Science and Engineering，Stanford University，2004.

[13]Shi Q，He C.A SDP Approach for Range-Free Localization in Wireless Sensor Networks[C]//IEEE ICC，Beijing，2008:4214－4218.