0 引　言

由于海洋环境复杂、干扰因素较多，传统的单节点定位已经无法满足需求，存在“看不清”的现象，而分布式协同定位技术由于其独特的优势，日益受到研究者的关注。例如在舰船编队或集群作业过程中，各船舶之间可以相互通信并共享位置信息，利用这些信息，结合舰船的动态模型和环境参数可显著提高系统的定位精度和作业效率，对于深化作业、辅助导航以及特定任务的执行都有重要意义^[1]。但传统的定位算法对节点依赖程度高，若编队中存在故障船舶，系统的定位精度、可靠性以及鲁棒性会显著下降。本文所提算法将离群检测技术应用于加权融合定位技术中，可有效增强系统的容错能力，使其保持较高的定位精度和可靠性。

近年来，国内外研究人员针对分布式定位研究取得了一定的成果。蒋俊正等^[2]提出一种基于改进牛顿法的分布式定位算法。该算法首先将传感器区域划分为若干个重叠子区域，将每个子区域定位问题归结为一个无约束的优化问题，然后使用分布式算法估计子区域中LU节点的位置并进行局部融合。徐莎莎等^[3]提出一种基于交替修正牛顿法的分布式定位算法。该算法首先将无线传感器网络表示的无向图划分成多个部分重叠的子图，其次根据第一步结果和测距信息采用修正牛顿法更新锚节点位置，最后未知节点再根据相对准确的锚节点位置更新估计位置。桑志远^[4]基于目标方位、时延、时延差以及多普勒频率偏移等参数实现联合观测目标定位。王玉针^[5]对高斯牛顿迭代法存在缺陷，设计一种将多节点解算的角度信息进行融合的定位算法。Shang等^[6]提出一种MDS-MAP算法，首先预设一个节点来建立方程，再将其余节点两两间距离代入方程，解出坐标系下所有节点的位置坐标。总之，分布式定位技术在水声定位领域具有重要地位。其高精度、高可靠性的特点使其在多个领域具有广泛的应用前景。但由于水下环境复杂多变，可能导致声呐系统节点失效，定位精度下降，因此各种预技术应运而生，聚类技术由于其计算量小、准确率高而得到广泛应用。

Chandola等^[7]介绍了离群点检测背景和研究意义，描述了各类经典算法的特点，重点分析了离群点检测在各个领域的应用并对未来发展方向进行展望。刘财辉^[8]分析归纳了代表性强的基于邻近性的离群点检测方法的优缺点，指出它们存在的问题和未来发展方向。陈豫禹等^[9]提出一种基于网格密度峰值的测向交叉定位算法，将网格划分和密度峰值聚类引入测向交叉定位中，并结合Hough变换制定了一种挑选类簇中心的规则。李轶针^[10]对RSSI测距误差较大的现象，提出一种基于MEA-BP神经网络与模糊C均值聚类的加权定位算法，进一步提高加权质心定位算法精度。朱文豪^[11]提出一种基于目标函数的局部离群点检测方法FOLOF（FCM Objective function based LOF），通过实验，证明该方法提高了检测精度，减少了运行时间，改善了聚类效果。本文正是利用LOF算法的聚类性，对三边定位测量结果进行融合聚类，然后找到误差较大定位点对应的分布式节点并将其剔除，从而实现节点失效情况下的高精度稳健定位。

1 三边定位测量模型与原理

三边定位技术是一种基于距离的定位方法。其基本原理是利用3个已知位置的参考点与待定位点之间的距离关系，通过数学计算来确定待定位点的位置^[12]。如图1所示，通过测量目标点到3个已知点的距离，可以建立3个以已知点为圆心、以距离为半径的圆，然后求解这3个圆或球面的交点，即为目标点的位置。

假设3个已知节点A、B、C，其坐标分别为$ ({x_1},{y_1}) $、$ ({x_2},{y_2}) $、$ ({x_3},{y_3}) $，目标点P的坐标为$ (x,y) $，目标点P到3个已知节点的距离分别为$ {d_1} $、$ {d_2} $和$ {d_3} $。距离公式为：

$ \left\{ {\begin{array}{*{20}{c}} {{d_1} = {{(x - {x_1})}^2} + {{(y - {y_1})}^2}}，\\ {{d_2} = {{(x - {x_2})}^2} + {{(y - {y_2})}^2}} ，\\ {{d_3} = {{(x - {x_3})}^2} + {{(y - {y_3})}^2}} 。\end{array}} \right. $

(1)

以上述非线性方程组第一个等式作为参考，利用后2个等式减去参考等式的方法，消除方程组中的二次项，完成非线性方程组至线性方程组的转化：

$ \begin{split}& ({x_i} - {x_1})x + ({y_i} - {y_1})y = \\ &\quad\frac{1}{2}({d_1} - {d_i} - {x_1} - {y_1} + {x_i} + {y_i}),\ i = 2,{\text{3}}。\end{split} $

(2)

将上式写成矩阵形式：

$ {\boldsymbol{AX}} = {\boldsymbol{b}}。$

(3)

式中：$ \boldsymbol{A}=\left[\begin{array}{*{20}{c}}x_2-x_1 & y_2-y_1 \\ x_3-x_1 & y_3-y_1\end{array}\right] $；$ \boldsymbol{X}=\left[\begin{array}{*{20}{c}}x \\ y\end{array}\right] $；$ \boldsymbol{b}=\dfrac{1}{2}\times \left[\begin{array}{*{20}{c}}d_1-d_2-x_1-y_1+x_2+y_2 \\ d_1-d_3-x_1-y_1+x_3+y_3\end{array}\right] $。

通过求解上述方程可以确定目标最终位置。假设目标位置为(400 m，200 m)，设置10个声呐探测节点，各探测节点仿真参数设置如表1所示，其中节点9为加入的故障节点。

利用三边定位技术解算可得目标定位结果分布如图2所示。可知，若系统存在故障节点，直接利用三边定位技术获取的多个定位结果中存在误差较大结果。如果直接对上述定位结果进行融合，则会导致系统定位精度下降。因此本文研究基于LOF的离群点检测技术和加权融合定位技术，从而提高系统整体定位精度。

2 基于LOF的离群节点检测

基于LOF的分布式定位算法流程如下：（1）利用三边定位技术估计出所有位置点；2）根据LOF算法对位置点进行聚类；3）筛选误差较大的节点信息并剔除；4）剩余节点采用加权融合定位技术估计目标最终位置。

图3为在二维数据集下，正常点和离群点的分布情况。可以看出，C₁和C₂中数据点较多且分布比较密集，那么就认为C₁和C₂中的数据点为正常点。C₃中数据点较少且密集程度低于C₁、C₂，则认为它离群，认为C₃中的点均为离群点。图中其余点P₁、P₂、P₃、P₄、P₅不属于任何数据集，但点P₅靠近C₂的边界区域，为局部离群点；其余点不靠近任何数据集，为全局离群点。

本文利用LOF聚类技术分析离群点，该算法具体过程如下：

定义1　$ p $点的$ k{\text{-}} $距离。用$ {k_{dist}}(p) $表示数据点$ p $的$ k{\text{-}} $距离。它表示数据点$ p $与数据点$ o $的距离$ d(p,o) $，其中数据点$ o $满足：不少于$ k $个点$ o' $，使得$ d(p,o') \leqslant d(p,o) $；且不多于$ k - 1 $个点$ o'' $，使得$ d(p,o'') < d(p,o) $。可见，$ {k_{dist}}(p) $数值大小可以反映出数据点$ p $周围点密度的大小。$ {k_{dist}}(p) $的值越小，说明数据点$ p $周围密度越大；反之，$ {k_{dist}}(p) $的值越大，说明数据$ p $周围密度越小。

图4一共有7个数据点$ p、{q_{_1}}、{q_{_2}}、{q_{_3}}、{q_{_4}}、{q_{_5}}、{q_{_6}} $，其中数据点$ p $最近的第3对象是$ {q_{_3}} $，如果$ k = 3 $，根据定义1可知$ {3_{dist}}(p) = d(p,{q_{_3}}) $，也就是说$ p $的3-距离等于2个数据对象间的欧式距离。

定义2　$ p $的$ k{\text{-}} $邻域。用$ {\sigma _k}(p) $表示数据点$ p $的$ k{\text{-}} $邻域。它表示所有满足条件$ d(p,q) \leqslant {k_{dist}}(p) $的数据点$ q $的集合，即：

$ {\sigma _k}(p) = \left\{ {q\left| {d(p,q) \leqslant {k_{dist}}(p)} \right.} \right\}。$

(4)

根据定义2可知，数据点$ p $的$ k{\text{-}} $邻域里的数据个数满足$ N \geqslant k $。

定义3　$ k{\text{-}} $可达距离。数据点$ p $与数据点$ o $之间的可达距离定义如下：

$ reach - dis{t_k}(p,o) = \max \left\{ {{k_{dist}},d(p,o)} \right\}。$

(5)

即数据点$ p $到数据点$ o $的$ k{\text{-}} $可达距离为$ p $的$ k{\text{-}} $距离和两数据点$ p $、$ o $间真实距离的最大值。

如图5所示，根据定义3可知，当$ k = 3 $时，数据点$ p $和$ {p_1} $之间的可达距离就是$ p $的$ k{\text{-}} $距离，而数据点$ p $和$ {p_2} $之间的可达距离就是两点之间的欧式距离。可以看出，$ k $值越大，邻域内数据对象之间的可达距离越相似。

定义4　局部可达密度。用$ lr{d_k}(p) $来表示数据点$ p $的局部可达密度。公式如下：

$ lr{d_k}(p) = {1 \left/ {\left( {\frac{{\displaystyle\sum_{O \in {\sigma _k}(p)} {reach - dis{t_k}(p,o)} }}{{\left| {{\sigma _k}(p)} \right|}}} \right)}\right.} 。$

(6)

即对数据点$ p $的$ k{\text{-}} $邻域内所有点可达距离之和取平均后再取倒数。

根据上述定义，LOF聚类算法中局部离群因子公式如下：

$ \begin{split} LO{F_k}(p) = &\frac{{\displaystyle\sum_{O \in {\sigma _k}(p)} {\left( {lr{d_k}(o)/lr{d_k}(p)} \right)} }}{{\left| {{\sigma _k}(p)} \right|}} = \\ & \frac{{\displaystyle\sum_{O \in {\sigma _k}(p)} {lr{d_k}(o)} }}{{\left| {{\sigma _k}(p)} \right|/lr{d_k}(p)}} 。\end{split} $

(7)

本文利用$ LO{F_k}(p) $定义数据点的离群程度。该值越大，证明数据点的离群程度越高，反之亦然。

图6为数据点$ p $的$ LO{F_k}(p) $随着$ k $值增加情况下的变化情况，可知若数据点$ p $为正常点，随着$ k $值增加，$ LO{F_k}(p) $的值会在1附近波动；若数据点$ p $为离群点，随着$ k $值增加，$ LO{F_k}(p) $的值会逐渐减小。

为了衡量$ LO{F_k}(p) $的变化程度，本文定义斜率累计因子从而区分正常点和离群点。$ {\theta _i}(p) $表示$ LO{F_i}(p) $和$ LO{F_{i + 1}}(p) $之间的距离，则可知两点之间斜率：

$\begin{split} {\theta '_i}(p) =& \frac{{{\theta _i}(p)}}{{((i + 1) - i)}} =\\ &d(LO{F_i}(p),LO{F_{i + 1}}(p)),\;{\text{ }}i = 1,2, \ldots k - 1。\end{split}$

(8)

将斜率绝对值累计求和后得：

$ S(p,k) = \sum\limits_{i = 1}^{k - 1} {\left| {{{\theta '}_i}(p)} \right|}。$

(9)

由上述分析可知，若$ S(p,k) $值较高证明该点可能为潜在离群点，因此可将所有点的$ S(p,k) $取均值后作为阈值，并以此作为依据判断定位结果是否离群，即$ {\text{sum}}(S(p,k))\mathord{\left/\vphantom{\mathrm{sum}(S(p,k))k}\right.}k $。

利用该方法对定位数据进行处理，可得离群分析结果如图7所示。

图7中“☆”即为离群的定位点，找到离群定位点对应的原始定位信息，结果如图8所示。可以看出，这些点与目标真实位置相距较远，即利用LOF聚类算法可以确定故障节点产生的定位信息。

3 误差节点筛选

每个离群点均对应3个分布式探测节点，统计离群点对应分布式节点集合，并计算各个分布式节点在集合中所占的比例，设定阈值后对比例较大节点进行剔除，然后利用其余节点完成最终定位。

设存在$ n $个离群点$ P $，统计产生$ n $个点的分布式节点$ Q $编号，同时求解各节点所占比例。若产生离群点$ {P_1} $的分布式节点编号为1、2、3，则$ {P}_{1}=\left\{{Q}_{1}、{Q}_{2}、{Q}_{3}\right\} $。以此类推：对上述离群数据进行分析找出对应分布式节点并编号。定义比例因子$ \lambda $：

$ {\lambda _i} = {{{N_i}} \mathord{\left/ {\vphantom {{{N_i}} N}} \right. } N} 。$

(10)

式中：$ N $为离群数据总数；$ {N_i} $为某分布式节点产生离群定位点的次数。计算处理后可知，各节点比例因子如图9所示。

取阈值$ \xi = 0.5 $，从图9可知探测节点9离群比例大于所选阈值，即可判定该节点为故障声呐节点，而节点9恰巧是事先加入较大测距误差的节点。可见当存在一个故障节点时，利用LOF算法可以将其选取出来，便于后续进行目标融合定位。

增加故障节点个数，设置探测节点8的测距结果为294.25 m，其它仿真条件不变，进一步验证本文所提算法的有效性。计算处理后可知，各声呐节点比例因子图如图10所示。

可知，分布式节点8、节点9均被成功筛选出，证明当存在2个测距误差较大的分布式节点时，本文算法仍有效。

4 加权融合定位及拟合验证

在探测节点呈等边三角形分布定位精度最高的基础上，本文将三角形边长和内角信息作为定位算法中的权重因子，完成分布式探测系统三边定位结果的加权融合^[13]。如图11(a)所示，在三角形ABC中，令$ \angle \alpha = \left| {\angle A - {{60}^ \circ }} \right| + \left| {\angle B - {{60}^ \circ }} \right| + \left| {\angle C - {{60}^ \circ }} \right| $。若$ \angle A = \angle B = \angle C = {60^ \circ } $，$ \angle \alpha $为$ {0^ \circ } $，此时为等边三角形，定位精度最高；若三角形ABC构成钝角三角形，且钝角角度逐渐增大，则$ \angle \alpha $也越来越大，3个顶点趋近于一条直线，此种情况会导致定位精度逐渐下降；直至A、B、C三点呈一条直线，此时无法进行目标定位。因此，引入角度加权的概念，加权因子设置为$ {1/{\angle \alpha }} $。

如图11(b)所示，若仅减小AC的长度，系统的定位性能也会受到影响。当AC长度逐渐较小，AB和BC逐渐靠拢，直至A、B、C呈一条直线，此时同样无法进行目标定位。因此，引入边长加权的概念，加权因子设置为 $ L = {{(AB + BC)} / {AC}} $，$ AC $为三角形的最小边长。

分布式探测系统共有$ C_M^3 $种节点选择方法进行定位（$ M $为探测节点个数），三边定位结果分别为$ ({x_1},{y_1}), ({x_2},{y_2}), \cdots ({x_n},{y_n}) $，对应的角度加权因子分别为$ {1 / {\angle {\alpha _1}}}, {1 / {\angle {\alpha _2}}}, \cdots {1 / {\angle {\alpha _n}}} $，边长加权因子分别为$ {L_1},{L_2}, \cdots {L_n} $，则未知节点的坐标可以作如下表示：

$ \left\{ {\begin{array}{*{20}{c}} {x = \dfrac{{{x_1}\dfrac{1}{{\angle {\alpha _1} + {L_1}}} + {x_2}\dfrac{1}{{\angle {\alpha _2} + {L_2}}} + \cdots + {x_n}\dfrac{1}{{\angle {\alpha _n} + {L_n}}}}}{{\dfrac{1}{{\angle {\alpha _1} + {L_1}}} + \dfrac{1}{{\angle {\alpha _2} + {L_2}}} + \cdots + \dfrac{1}{{\angle {\alpha _n} + {L_n}}}}}} ，\\ {y = \dfrac{{{y_1}\dfrac{1}{{\angle {\alpha _1} + {L_1}}} + {y_2}\dfrac{1}{{\angle {\alpha _2} + {L_2}}} + \cdots + {y_n}\dfrac{1}{{\angle {\alpha _n} + {L_n}}}}}{{\dfrac{1}{{\angle {\alpha _1} + {L_1}}} + \dfrac{1}{{\angle {\alpha _2} + {L_2}}} + \cdots + \dfrac{1}{{\angle {\alpha _n} + {L_n}}}}}} 。\end{array}} \right. $

(11)

仿真场景设置为100 m × 100 m的正方形区域，未知目标节点数量50个，探测节点数量20个，均随机生成，测距误差0.5 m，均值融合定位技术与加权融合定位技术相比较，仿真结果如图12和图13所示。其中，“o”为目标实际位置，“*”为目标估计位置。

采用目标实际位置与目标估计位置的欧氏距离，即定位误差标准差来进行系统误差评估，误差$ \sigma $的表达式为：

$ \sigma = \sqrt {{{(x - {x_0})}^2} + {{(y - {y_0})}^2}}。$

(12)

式中：($ {x_0} $,$ {y_0} $)为目标实际位置；($ x $,$ y $)为目标估计位置。

可以看出，相比于均值融合定位，采用加权融合定位技术，在探测节点位置随机分布，定位目标位置随机分布的情况下，目标定位精度更高，平均误差由$ {\sigma _1} \approx 0.88 $降低至$ {\sigma _2} \approx 0.29 $，证明该算法鲁棒性强，更加适用于本文所述定位场景。

为验证本文所提基于LOF的聚类定位技术效果，将节点9的测距误差由0.5 m增加至5 m，其余仿真条件不变，所得仿真结果如图14和图15所示。

对上述结果进行数据分析，可知聚类前定位算法的平均误差为$ {\sigma _1} \approx 1.33 $；聚类后定位算法的平均误差为$ {\sigma _2} \approx 0.32 $；对比计算结果，显然采用本文所提算法具有更小定位误差。

5 结　语

本文研究一种基于LOF聚类的分布式协同定位算法，在传统LOF聚类算法的基础上引入斜率累计因子的概念，以此为衡量标准判断探测结果是否离群，经过仿真分析可知系统存在1个/2个故障节点下该算法均可正常剔除故障点。最后，利用加权融合定位求解目标最终位置，经计算聚类前后平均误差由1.33降低至0.32，有效提升了系统定位精度。且LOF算法相对于其他聚类算法，计算量和复杂度更低，算法的实时处理性能更好，因此可以广泛应用于舰船编队或者集群作业场景下的目标定位，具备较高的安全性和鲁棒性。