基于混合式的松弛规划优化的鲁棒定位算法

李 多，王晓红，郑 浩

（1.吉林师范大学 信息网络中心，吉林 四平136000；2.吉林师范大学 数学学院，吉林 四平136000）

0 引 言

准确地获取节点的位置信息是多数传感网络的应用中的基本要求［1］。例如，目标跟踪、探测、协作传感以及能量有效路由 （energy－efficient routing）［2，3］，这些应用均需节点的位置信息。常用的传感定位方案就是先获取锚节点的位置信息，再利用传感节点与锚节点的测距信息估计传感节点的位置。测距信息可通过测量接受信号强度RSS（received signal strength）［4，5］、信号到达角度［6］以及信号到达时间TOA （time of arrival）［7，8］获取，从而通过准确的测距信息实施对传感节点的定位［9］。

研究人员针对传感网络定位问题，提出了许多方案［10－13］。文献 ［10］中提出了一种基于二阶锥规划的新时差定位算法，该算法将位置估计问题转化为二阶锥规划问题，再利用泰勒级数展开法估计节点最终的位置；文献［14］采用加权最小二乘WLSM （weighted least square method）估计节点的位置，但是该方案依赖初始值的精度，否则算法无法收敛。

另一种方案就是基于凸优松弛技术，该类算法是将定位问题非凸优问题转为为一个凸优化问题，然后运用凸优化理论中的二阶锥规划SOCP （second order cone programming）［15，16］、半定规划SDP （semi－definite programming）松驰方法求解节点的位置。然而，若存在量测噪声，SDP和SOCP仅能获取次优解 （suboptimal solutions）。

Tseng［16］针对传感网定位问题，对SOCP 和SDP 进行了深入的研究，并分析了SOCP 和SDP 的解集的关系。Tseng分析得出SDP和SOCP 间存在复杂度和定位精度间的折衷。相比于SOCP，SDP松弛更紧，其定位也更精确。而SOCP具有更低的复杂度，求解时间更短。

多数传感器定位算法均假设能获取锚节点的准确位置，并通过这些锚节点的准确位置信息，估计余下传感节点位置。然而，在多数环境中，这个假设难以满足，由于噪声污染，难以获取锚节点的准确位置。反过来，锚节点位置的不确定性影响对传感节点位置的估计。为此，文献 ［17］针对未知锚节点位置条件下，提出基于SDP 的凸优松弛的鲁棒传感节点定位算法。具体而言，由两项构成最大似然估计，第一项反映了测量关系，其常分为鲁棒和非鲁棒优化；第二项是锚节点位置，其需要不论测量值存在多大的误差下找到可靠的定位算法，然而，该算法计算复杂度高、计算时间过长。

为此，针对锚节点位置不明确的环境下，提出基于半定规划SDP和二阶锥规划SOCP 混合式的松驰规划求解定位问题的优化方案，记为R＿SOCP＋SDP。根据最大似然估计原则建立定位估计的鲁棒SOCP （RSOCP）、鲁棒SDP（RSDP）优化函数，然后分析SOCP与SDP间的关系，并充分考虑SOCP的计算复杂度低、SDP 的定位精度高的特点，建立R＿SOCP＋SDP凸优化函数，最后运用凸优化理论的松弛规划技术估计节点的位置。仿真结果表明，R＿SOCP＋SDP能够在不明确锚节点位置的环境下，提供准确的节点定位，并降低系统的计算复杂度。

1 定位模型

假定传感网络由一系列的锚节点和普通传感节点组成。Na、Ns分别表示锚节点集和普通节点集。网络中所有节点集表示为N ，且N ＝Na∪Ns。矢量包含所有节点i的坐标，i∈N 。此外，网络中锚节点的个数为k，且k ＝。网络中节点总数为m，即m ＝。

利用无方向图 （undirected graph）G ＝（N，ε）表示传感网络，其中N 表示所有节点集，ε表示链路集。如果节点i、j 是邻居，即它们在彼此的通信范围Rc内，＝链路（i，j）∈ε。类似文献 ［16］，假定ε不包含锚节点与锚节点构建的链路。由于存在量测噪声，节点i、j间的距离的估计值dij如式 （1）所示

式中：eij——测量误差，零均值高斯变量，且方差。设定集合D 表示量测误差集

1.1 基于准确的锚节点位置的普通节点定位

先假定网络已知锚节点位置。给定锚节点位置xoi，i∈Na，量测误差集D，依据最大似然估计原则估计普通节点的位置，xi，i∈Ns，如式 （3）所示

式 （2）的优化属于非凸优问题，需应用SOCP和SDP将其转为凸优问题，进而估计节点位置。

1.2 基于不准确的锚节点位置的普通节点定位

在实际环境中，难以准确地获取锚节点的位置。在多数场景中是通过全球定位系统GPS （global positioning system）获取准确的锚节点位置，这必然存在测量误差。因此，假定获取的锚节点i不准确的位置ai，如式 （4）所示

针对式 （4），采用最大似然估计原则MLE （maximum likelihood estimation）算法估计，i∈N 。概率如式 （5）所示

结合式 （5），对普通节点实施鲁棒估计，如式 （6）所示

类似于式 （3），式 （5）为非凸优问题。为此，利用SOCP策略，将式 （6）进行转换

其中gij＝。定义矢量u联合多个变量，如式 （8）所示

为此，对式 （7）进行转换，如式 （9）～式 （13）所示

最后，为了满足SOCP 型将约束项式 （13）转为不等式 （14），从而通过凸优SOCP 松弛技术解决鲁棒定位问题，如式 （14）所示

将式 （10）替换式 （13），致使式 （9）变换标准的SOCP，就可通过内点算法 （interior point）算法［18］进行求解。

2 鲁棒的SOCP与SDP的定位问题

本小节，分析式 （9）与鲁棒SDP的表达式［17］的关系，同时提出R＿SOCP＋SDP方案，该混合方案是对SDP准确性和SOCP的复杂性的一种弹性折衷。

2.1 SOCP与SDP间的关系

针对SOCP 和SDP，文献 ［16］分析SOCP 的解数集（Solution set）包含SDP 解数集。这说明SDP 提供更窄求解区域。本小节，针对未能准确获取锚节点位置的环境下，分析式 （9）所示的SOCP和SDP间关系，并将此条件下的SOCP和SDP，称为鲁棒 （robust）的SOCP和SDP，分别记为RSOCP、RSDP。

引入2×m 矩阵X，其ith列元素设定为xi，并且令Y＝利用SDP［17］，得到鲁棒式的RSDP表达式，如式 （15）～式 （22）所示

接下来的命题显示了分析式 （9）所示的RSOCP 和式（15）SDP间关系。

令Ssdp＝｛X，Y，｛Ξi｝，｛γij｝，｛rij｝｝表示鲁棒的RSDP（式 （16）～式 （22））的可行解。因此，变量集Ssocp＝｛｛x′i｝，｛qij｝，｛tij｝，｛si｝，υ｝可定义

上述的定义形成了RSOCP （式 （9））的可行解。此外，鲁棒式RSDP （式 （15））的修整后优化值υ′sdp＝其大于或等于RSOCP （式 （9））的优化值

其中υ0为式 （23）定义的值。

命题显示：若满足式 （25），RSDP解集包含于RSOCP解集内。相比于RSOCP，RSDP提供更窄的解集区域。

由于克拉美－拉奥下界CRLB （Cramer－Rao lower bound）与使用的算法独立，依据文献 ［17］的噪声模型，计算鲁棒定位问题的CRLB。具体地，通过Fisher information 矩阵F 的反转矩阵中的对角元素，可计算定位变量的CRLB，如式 （26）所示

2.2 RSOCP和RSDP的混合

为了提供准确性与复杂性的折衷的定位方案，可以将鲁棒的RSOCP和RSDP 进行混合。通过将节点集N 分为Nsocp、Nsdp两个子集，并针对相应的测距信息运行RSOCP和RSDP方案，如式 （27）所示

其中N、ε、D 的下标 ‘sdp’和 ‘socp’分别表示属于RSDP和RSOCP的节点集、链路和测距。在通常情况下，无需使Nsocp、Nsdp两个子集完全独立，即Nsocp∩Nsdp≠0。

考虑总体性能，即计算复杂度和定位精度，需要将所有节点有效地分配给Nsocp、Nsdp两个子集。为此，提出RSOCP和RSDP的混合算法R＿SOCP＋SDP。该算法要比SDP计算复杂度低、比SOCP定位精度高。

（1）将所有的节点分配Nsocp，即Nsocp＝N ，求解SOCP式 （9）；

（2）设置Nsdp＝｛i s.t （i，j）∈ε：（i，j） ｝∪Na，这表明求解SDP，是基于链路集之外的节点和锚节点的并集。

与文献 ［14］提出的算法相比，式 （14）更具有普遍性，从这个意义上讲，允许提出的混合算法R＿SOCP＋SDP满足Nsocp∩Nsdp≠0。显然，提出的混合算法R＿SOCP＋SDP的计算复杂度高于SOCP。但是，提出的混合算法R＿SOCP＋SDP 中，SDP 需要仅通过非紧密节点（non－tight nodes）求解，其通常为网络中总节点的10 至20%［16］，比标准的SDP通过网络所有节点求解，极大地降低了计算复杂度。

3 性能分析

本节，通过仿真分析提出的定位算法的性能，并利用Matlab软件内凸优化工具箱CVX 求解R＿SOCP＋SDP 问题和RSDP问题式 （15）。仿真平台为Matlab 2009a，区域为40 m×40 m 的二维区域。采用3.07 GHz的处理器、8GRAM 的计算机实施仿真。

采用均方误差MSE （mean square error）衡量算法的定位性能，如式 （28）所示，并改变噪声方差的值，从而分析算法在不同噪声条件下的定位性能。同时假定对所有链路（i，j）∈ε的噪声方差＝，其中表示单位距离的方差，即长距离的链路具有更大的噪声方差［17］

（1）RSOCP的性能

图1中，三角形、矩形分别表示8个锚节点、10个普通传感节点的位置。RSOCP对锚节点、普通传感节点进行位置估计，图中记为RSOCP－anchor、RSOCP－Sensor。类似，RSDP对锚节点、普通传感节点进行位置估计，图中记为RSDP－anchor、RSDP－Sensor。

图1 RSOCP和RSDP对锚节点、普通传感节点的位置估计

表1 SOCP、RSOCP、RESDP、RSDP的性能对比

从图1 可知，两个鲁棒算法RSOCP、RSDP 均能够较准确地定位锚节点和普通传感节点的位置。针对靠近原始位置（0，0）的节点，RSOCP的估计精度略高于RSDP，例如，图中最小的定位误差是位于（－11.6，－10.8）m。而对于位于边界的节点，RSOCP的估计精度下降，并低于RSDP。这个现象说明一个事实：在RSOCP 中，离锚节点凸壳 （Convex hull）越近的节点其位置估计精度越高。这主要是因为RSOCP 优化的特殊结构。总体上看，RSOCP的总体RMSE 为1.35dBm2，高于RSDP 的总体MSE 的0.50dBm2。这主要是因为RSDP具有更紧的松弛。

表1显示SOCP、RSOCP、RESDP、RSDP定位精度和计算时间。这些数据表明，与SOCP 相比，RSOCP 提高了定位精度，计算时间提升了约0.2s；与RSDP相比，减少了计算时间达到0.74s，表明RSOCP 有效地降低了计算复杂度。

（2）提出的混合算法R＿SOCP＋SDP的性能

图2 R＿SOCP＋SDP的MSE随测距方差的变化曲线 （Ψi ＝－10I2dBm2 ）

从图2可知，R＿SOCP＋SDP在MSE方面的性能优于标准的SOCP以及RSOCP。而RSDP 由于更紧的松弛，其紧逼于R＿SOCP＋SDP。在小于－20dBm2时，没有哪个方案达到CRLB。

图3 R＿SOCP＋SDP的MSE随的变化曲线

从图3可知，所有的定位方案的定位MSE 随噪声方差的增加而上升。相比于标准的SOCP，RSOCP的MSE性能得到显著的提高。此外，标准的SOCP、RSCOP和R－SOCP＋SDP的MSE性能均随的增加而下降。这主要是因为越大，锚节点位置误差大，导致估计其它普通节点的MSE上升。注意到，越大，RSOCP 的MSE 比标准的SOCP下降得越多，这是因为RSOCP能够调整锚节点的位置。从图3 可 知，不 论 何 种 情 况 （＝ ｛－10，0，10｝dBm2），提出的R－SOCP＋SDP 的MSE 最小。越大，MSE下降得越明显。

为了评估方案在大型网络的性能，设定1 000 m×1 000m仿真区 域，且Ψi＝，其中＝｛34，37.5｝dBm2、＝105、＝45。考虑到真实实验环境，假定每条链路断裂率为0.3，并且在链路断裂时，无测距数据传输。针对此场景，进行仿真，仿真结果如图4所示。

图4 R＿SOCP＋SDP的MSE随以及的变化曲线

在仿真过程中，记录了方案的定位时间。RSOCP消耗了37s，比RSDP 的84s提高了近两倍，但是RSOCP 的MSE仅比RSDP 提 高了约2.5dBm2。在＝37.5dBm2时，RSOCP 比RSDP 的MSE 高约1dBm2，并且RSOCP的定位误差在可接受的范围内。在＝37.5dBm2以及＝34dBm2两种情况，提出的R＿SOCP＋SDP的定位误差最小。

4 结束语

针对无线传感网节点定位问题，提出了基于半定规划SDP和二次锥规划SOCP 的混合式的松驰规划求解定位问题的优化方案，记为R＿SOCP＋SDP。通过R＿SOCP＋SDP定位的非凸优问题转化为凸优问题，并利用松驰优化理论求解。首先分析SOCP和SDP间的特点，再针对锚节点位置不确定以及量测噪声环境，依据最大似然估计建立鲁棒的SOCP和SDP目标函数。结合SOCP低计算复杂度和SDP高的定位精度，提出R＿SOCP＋SDP方案。针对不同的场景仿真，结果表明提出的R＿SOCP＋SDP在计算复杂度和定位精度方面具有良好的性能。

［1］ZHANG Shigeng，ZENG Yingpei，CHEN Lijun，et al.Performance evaluation of localization algorithms for mobile sensor networks［J］.Journal of Software，2011，22 （7）：1597－1611 （in Chinese）. ［张士庚，曾英佩，陈力军，等.移动传感器网络中定位算法的性能测评 ［J］.软件学报，2011，22（7）：1597－1611.］

［2］Szewczyk R，Osterweil E，Polastre J，et al.Habitat monitoring with sensor networks ［J］.Commun.ACM，2012，47（5）：34－40.

［3］Javad R，Moradi M，Abdul S.Superior path planning mechanism for mobile beacon－assisted localization in wireless sensor networks［J］.IEEE Sensors Journal，2014，14 （9）：3052－3064.

［4］Patwari N，Ash JN，Kyperountas S，et al.Locating the nodes：Cooperative localization in wireless sensor networks［J］.IEEE Signal Processing Magazine，2010，22 （4）：54－69.

［5］Bahl P，Padmanabhan VN.RADAR：An in－building RFbased user location and tracking system ［C］//In Processing IEEE INFOCOM，2010：775－784.

［6］Naveed S，Mounir G，Kemp H.Optimized low complexity sensor node positioning in wireless sensor networks［J］.IEEE Sensors Journal，2014，14 （1）：39－47.

［7］Mao G，Fidan B，Anderson BDO.Wireless sensor network localization techniques ［J］.Computer Networks，2007，51（10）：2529－2553.

［8］Guvenc I，Chong C.A survey on TOA based wireless localization and NLOS mitigation techniques ［J］.IEEE Communications Surveys ＆Tutorials，2009，11 （3）：107－124.

［9］Yu K，Montillet JP，Rabbachin A，et al.UWB location and tracking for wireless embedded networks ［J］.Elsevier Signal Process，2011，86 （9）：2153－2171.

［10］JIN Jiabao，ZHANG Song，YANG Jingshu.A new TDOA location algorithm based on second order cone programming［J］.Telecommunication Engineering，2014，52 （6）：887－893 （in Chinese）. ［金家保，张颂，杨景曙.一种基于二阶锥规划的新时差定位算法 ［J］.电讯技术，2012，52 （6）：887－893.］

［11］Zhang SG，Cao JN，Chen LJ，et al.Accurate and energy－ef－ficient range－free localization for mobile sensor networks［J］.IEEE Trans on Mobile Computing，2010，9 （6）：897－910.

［12］WANG Qihua，GUO Ge.Semi－definite relaxation programming optimization of localization algorithm based on the arrival time difference ［J］.Journal of Dalian Maritime University，2013，39 （4）：59－62 （in Chinese）. ［王其华，郭戈.基于到达时间差的半定松驰规划优化的定位算法 ［J］.大连海事大学学报，2013，39 （4）：59－62.］

［13］SHI Jie，YANG Desen，SHI Shengguo.A robust localization and identification method of noise sources using second－order cone programming ［J］.Journal of Harbin Engineering University，2011，32 （12）：1549－1558 （in Chinese）. ［时洁，杨德森，时胜国.二阶锥规划在噪声源健定位识别中的应用.哈尔滨工程大学学报，2011，32 （12）：1549－1558.］

［14］Yang L，Ho KC.An approximately efficient TDOA localization algorithm in closed－form for locating multiple disjoint sources with erroneous sensor positions ［J］.IEEE Transactions on Signal Processing，2009，57 （12）：4598－4615.

［15］Srirangarajan S，Tewfik A，Luo ZQ.Distributed sensor network localization using SOCP relaxation ［J］.IEEE Transactions on Wireless Communications，2008，7 （12）：4886－4895.

［16］Tseng P.Second－order cone programming relaxation of sensor network localization ［J］.SIAM Journal Optimization，2007，18 （1）：156－185.

［17］Lui K，Ma WK，So H，et al.Semi－definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed ［J］.IEEE Transactions on Signal Processing，2009，57 （2）：752－763.

［18］Boyd S，Vandenberghe L.Convex optimization ［M］.4th ed.Cambridge University Press，2004.

［19］Pinar O，Joao G，Paulo O.Robust localization of nodes and time－recursive tracking in sensor networks using noisy range measurements［J］.IEEE Transactions on Signal Processing，2011，59 （8）：3930－3943.