武刚^1,2, 吴成东¹
1. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 沈阳大学 信息工程学院, 辽宁 沈阳 110044
收稿日期：2018-12-19
基金项目：国家重点研发计划项目(2017YBF1300900)；国家自然科学基金资助项目(61973063)；国家自然科学基金与深圳市联合基金资助项目(U1713216)。
作者简介：武刚(1978-), 男, 辽宁丹东人, 东北大学博士研究生;
吴成东(1960-), 男, 辽宁大连人, 东北大学教授，博士生导师。

摘要：针对无线传感器网络节点定位, 在最大似然估计(MLE)基础上提出了一种半定规划(SDP)的优化算法.结合有效的锚节点位置选择和比率范围设定, 在放宽非凸约束的基础上, 采用SDP求解算法, 有效减少了误差的影响, 得到被测节点的实际位置.改变锚节点的位置可以有效解决锚节点凸壳外的节点位置估计不精准问题.仿真结果表明, 提出的SDP算法对未知节点的位置实现了高精度定位, 改进了凸优化方法.
关键词：无线传感器网络半定规划最大似然估计估计位置锚节点
Location Algorithm of Wireless Sensor Network Nodes Based on Semi-definite Programming
WU Gang^1,2, WU Cheng-dong¹
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Information Engineering, Shenyang University, Shenyang 110044, China
Corresponding author: WU Gang, E-mail: hugwg@163.com
Abstract: Aiming at node localizations of wireless sensor network(WSN), a semi-definite programming(SDP)optimization algorithm based on the maximum likelihood estimation(MLE)was proposed. Combining the effective anchor node position selection and ratio range setting, the SDP algorithm was used to relax the non-convex constraints, effectively reduce the impact of errors and get the actual position of measurement nodes. Changing the position of the anchor node can effectively solve the problem of inaccurate estimation of nodes outside the convex hull of the anchor node. The simulation results showed that the proposed SDP algorithm achieves high-precision in the position estimation of unknown nodes, and improves the convex optimization method.
Key words: wireless sensor networksemi-definite programmingmaximum likelihood estimationestimated positionanchor node
随着电子、通信和传感器技术的发展, 以及计算能力的提高, 无线传感器网络(WSN, wireless sensor network)变得越来越重要^[1].无线传感器网络技术在军事、民用、医疗、环境监测等领域发挥了极其重要的作用, 越来越多的出版物关注这一主题.
在关于WSN参数信息的研究领域中, 位置信息是至关重要的环节.节点定位问题是许多其他后续应用(监控数据、路由选择等)的前提.目前的研究技术包括:接收信号强度指示器(RSSI)、到达时间(TOA)、到达时间差(TDOA)、到达角(AOA)、最大似然估计(MLE)、残差检验及高斯混合模型等算法.自适应卡尔曼滤波算法对无线传感器网络中节点的定位得到了较好的估计值^[2].Tomic等^[3]提出了RSS-AOA定位算法; Guvenc等^[4]基于TOA的无线定位和非视距缓解技术的研究, 在非视距环境下具有较好的定位精度.胡楠等^[5]提出了一种基于严格残差选择的非视距定位算法, 利用该算法进行定位得到了较好的定位精度和鲁棒性.崔玮等^[6]提出了基于高斯混合模型的非视距定位算法结合优选残杀加权算法对获得的距离值进行定位估计，得到了很好的目标节点坐标估计值.
通过以上文献可以看出, 误差的削弱向着低计算量及快速收敛的方向发展，但由于测量的精度、处理器、每个节点的功率和内存限制, 得到距离信息的误差是真实存在的.而正在开发节点定位的技术中, 相邻节点之间的距离和角度的测量是主要的观测点.本文所提出的SDP算法, 在不需要获得相邻节点之间的距离和角度的情况下, 以最大似然估计模型为基础, 结合SDP算法, 通过降低维数, 利用已知锚节点的位置和传感器的估计位置可以快速有效地减轻误差对测量精度的影响, 并实现良好的定位精度.
1 最大似然估计及其SDP算法1.1 系统模型在传感器网络R²中, 有m个锚节点和n个传感器, 任意1个锚节点的位置定义为a_k, k=1, 2, …, m; 传感器节点的位置定义为x_i, k=1, 2, …, n.在本文中, k为锚节点位置, i, j为未知节点位置.d_ji为传感器x_j和x_i之间的欧几里得距离; d_jk为传感器x_j和锚节点a_k之间的欧几里得距离.
因此, R²中的定位问题可以表述为给定的m个锚节点的位置为a_k, k=1, 2, …, m, 测量距离为d_ji, (j, i)∈N_x), d_jk((j, k)∈N_a), 确定n个传感器节点的位置x_i, j=1, 2, …, n, 即

(1)

(2)

可将式(1), (2)表达为

(3)

(4)

设X=(x₁, x₂, …, x_n), 为2×n矩阵, X∈R^2×n, Y∈R^n×n,

(5)

式中, I₂为2×2单位矩阵.
1.2 最大似然估计及SDP模型在最大似然估计中, 设d:R²×R²→R为传感器/锚节点或传感器/传感器对之间的距离函数.假设x_j/a_k和x_j/x_i之间存在一些测量误差, 分别由w_jk和w_ji表示.

(6)

(7)

假设w_jk为N(0, σ_jk²)分布, w_ji为N(0, σ_ji²)分布, 其中N(0, σ²)是一个正态随机变量, 具有0均值和方差σ², 且相互独立.设最大似然函数p使用了所有距离测量信息估计X, 即

(8)

将式(8)表达成MLE形式:

(9)

结合式(8)与式(9):

(10)

用式(10)解决式(8)的最大似然估计问题:

(11)

上述目标函数在加权多维缩放^[7]中是一类成本函数的特例, 实际上, 加权多维缩放已经应用于传感器网络定位^[8], 最大似然估计是其中描述的一般成本函数的特定情况, 关键在于如何解决这个(非凸)问题.成本最小化问题可以转化为SDP模型, 通过降低SDP模型的维数来解决.通过使用最大似然估计成本函数来说明该算法, 更复杂的成本函数也可以在SDP框架中处理.
如果测量距离的方差未知, 任何合理的假设都可以适用最大似然估计, 式(11)可等效表达为

(12)

式中: ;
式(12)中的最后一个约束条件可以等效表示为Y≥X^TX, Y的秩为2.通过丢弃秩为2的约束, 式(12)可以被看作为一种SDP形式^[9], 即

(13)

在仿真过程中, 乘法噪声为

(14)

式中:D_ji为实际距离; d_ji为测量距离.那么
由于实际距离未知, 可以使用测量距离d_ji和d_jk估计方差, 因此, 在这种情况下, 式(13)的目标值为

(15)

SDP方法可以扩展到更大类别的距离测量公式的成本函数中.其他类型的约束也很容易集成到SDP框架中.例如, 传感器之间的角度信息已经被用在SDP中进行定位.接下来将讨论一对传感器之间的单一距离测量, 它们之间的信息为间隔或范围的形式, 也就是说两个传感器之间的距离将位于一定的置信区间内.
2 SDP模型的区间表达处理噪声的第二种方法是解决上下限距离测量的SDP可行性问题, 通常, 可以获得的相互距离测量是以间隔而不是单个值来表示的, 即噪声距离测量值，以a_k与x_j之间的上界和下界的置信区间形式表示, 或者以x_i与x_j之间的上界和下界表示.
二次型模型可以定义为矩阵

(16)

因此, 在这个表述中, 最终得到了不等式约束而不是等式约束, SDP模型为

(17)

如果距离测量完全正确(在不等式约束的情况下, 这意味着上限和下限都是相同的, 基本上解决了等式约束问题)并且传感器网络是唯一可定位的, 那么式(5)、式(13)和式(17)解决了真实的传感器位置.如果边界与噪声数据的情况不同, 则模型将返回(由于SDP内点算法的属性)中心解决方案, 即所有可行SDP解决方案的“平均解决方案”.当存在距离噪声时(这是期望的), 可能的位置范围的中心定位是无偏估计.
3 实验结果及分析在定义的50 m×50 m的二维区域随机放置了30个节点, 如果计算两个节点间的距离小于指定比率范围R, R取值范围在[0, 1]之间, 在式(14)中添加随机误差, 即
式中:D_ij为两个节点之间的真实距离; f_n为噪声因子即控制噪声方差量, 在[0, 1]之间; N(0, 1)为标准的正态随机变量.
平均误差估计定义为
式中:n为未知节点的总数; x_j为SDP解决方案中计算得出的估计位置; x_j为第j个节点的真实位置.
在比率范围内的节点称为关联节点.通过改变比率范围的值, 可以改变关联节点的数量和可用距离测量的大小.通过在随机生成未知传感器节点的网络上模拟运行具有不同关联节点的数量, 用距离测量中的噪声方差和锚点数量的算法来评估平均性能.对于特定比率范围的每个配置、锚节点的数量和噪声方差, 算法在30个独立生成的未知传感器节点的网络上运行并计算平均误差.
传感器估计位置与实际位置对比分布如图 1所示.比率范围表示估计位置与锚节点位置之间距离的比值.如果求解器低于该范围, 则任何两个节点之间的距离值都是已知的, 否则它们之间的距离不明确.在30个传感器的随机网络分布中, 设定f_n=0.10, 锚节点的数量为4, 比率范围为0.20, 用原始节点和估计节点之间的偏移来估计位置的偏差, 如图 1a中实线所示.
图 1(Fig. 1)

图 1 传感器估计位置与实际位置分布Fig.1 Estimated position and original position distribution (a)—比率范围为0.20, fn=0.10；(b)—比率范围为0.30, fn=0.10；(c)—比率范围为0.40, fn=0.10；(d)—比率范围为0.40, fn=0.05.

将比率范围提高到0.30, 传感器估计位置明显接近实际原始位置, 如图 1b所示, 即使有10%的噪声测量误差, 锚节点附近的传感器的估计位置仍然相对准确.当继续提高比率范围到0.40, 由图 1c可知, 在噪声误差为10%的情况下, 锚节点附近传感器估计位置相对是准确的.在图 1d中, 设定f_n=0.05, 锚节点的数量为4, 比率范围0.40, 噪声误差降低到5%, 传感器的估计位置有了明显改善, 几乎都是准确的.
由图 1的对比结果可知, 在不改变噪声因子f_n的情况下, 提高比率范围, 传感器的估计位置有了明显改善, 在比率范围内的点精确度明显提高.由图 1c和1d可知, 在不改变比率范围的情况下, 降低噪声因子f_n, 传感器的估计位置几乎都是准确的.
对于相同的点网络和不同锚节点的位置, 估计是截然不同的, 如图 2所示.
图 2(Fig. 2)

图 2 传感器估计位置与原始位置分布Fig.2 Estimated position and original position distribution (a)—设置内部锚节点；(b)—设置外部锚节点.

在嘈杂的情况下, 需要注意的一点是锚节点位置至关重要.将锚节点放置在网络的周边大大减少了由噪声距离测量引起的估计误差.形成鲜明对比的是, 锚节点凸壳外的点往往估计得很差.使用距离测量在SDP模型中就可以找到精确的估计位置, 而不需要确定锚节点的位置, 这是SDP模型对先前凸优化方法的主要改进.
然而, 在距离测量中引入噪声会降低改进程度.图 1与图 2对比可知:图 1d中锚节点附近在比率范围内的传感器估计位置相对准确; 图 2a中锚节点位于测试区域的内部, 锚节点附近的传感器估计位置得到改善, 而对外围的估计几乎没有得到满意的效果; 图 2b在其他条件相同的情况下, 锚节点的位置在测试区域的外围, 所有传感器的估计位置得到了明显的改善.
在以往所提不同种算法中需要获得相邻节点之间的距离、角度, 信号的到达时间, 信号的强弱等信息用于对传感器节点进行定位, 然而这些信息的获得十分的繁琐.而在本过程中, 只需要设定适当的比率范围值，结合SDP算法得到传感器实际原始位置.
4 结论本文提出了一种在最大似然估计基础上的半定规划传感器估计位置的定位算法.首先利用最大似然估计的模型得出半定规划算法; 再利用锚节点的位置和对传感器的估计位置, 结合SDP算法得到传感器实际位置.把锚节点放置在网络的周边，由噪声距离测量引起的估计误差大大减少; 改变锚节点的位置可有效解决锚节点凸壳外的点估计不精准的问题, 这是SDP模型对先前凸优化方法的主要改进.仿真实验表明使用该方法可有效地对传感器网络中的节点进行定位.
参考文献

[1]	Ou C H. A localization scheme for wireless sensor networks using mobile anchors with directional antennas[J].IEEE Sensors, 2011, 11(7): 1607–1616.DOI:10.1109/JSEN.2010.2102748
[2]	Fang X M, Jiang Z H, Nan L, et al. Noise-aware localization algorithms for wireless sensor networks based on multidimensional scaling and adaptive Kalman filtering[J].Computer Communications, 2017, 10(1): 57–68.
[3]	Tomic S, Beko M, Dinis R. Distributed RSS-AoA based localization with unknown transmit powers[J].IEEE Wireless Communications, 2016, 5(4): 392–395.DOI:10.1109/LWC.2016.2567394
[4]	Guvenc I, Chong C. A survey on TOA based wireless localization and NLOS mitigation techniques[J].IEEE Communications, 2009, 11(3): 107–124.DOI:10.1109/SURV.2009.090308
[5]	胡楠, 吴成东, 刘鹏达, 等. 基于严格残差选择的非视距定位算法[J].东北大学学报(自然科学版), 2016, 37(9): 1221–1224. ( Hu Nan, Wu Cheng-dong, Liu Peng-da, et al. NLOS localization algorithm based on the strict residual[J].Journal of Northeastern University(Natural Science), 2016, 37(9): 1221–1224.DOI:10.3969/j.issn.1005-3026.2016.09.002)
[6]	崔玮, 吴成东, 张云洲, 等. 基于高斯混合模型的非视距定位算法[J].通信学报, 2014, 35(1): 99–106. ( Cui Wei, Wu Cheng-dong, Zhang Yun-zhou, et al. GMM-based localization algorithm under NLOS conditions[J].Journal on Communications, 2014, 35(1): 99–106.DOI:10.3969/j.issn.1000-436x.2014.01.012)
[7]	Doherty L, Laurent E G, Pister K, et al.Convex position estimation in wireless sensor networks[C]//IEEE International Conference on Computer Communications.Beijing, 2001: 1655-1663.
[8]	Jose C, Patwari N, HeroIII A O, et al. Distributed multidimensional scaling with adaptive weighting for node localization in sensor networks[J].Association for Computing Machinery Transactions, 2005, 26(3): 165–173.DOI:10.1145/1138127.1138129
[9]	Lui K W K, Ma W K, So H C, et al. Semidefinite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed[J].IEEE Transactions on Signal Process, 2009, 57(2): 752–763.DOI:10.1109/TSP.2008.2007916