定位技术在军事侦察、环境监测、医疗等领域具有广泛的应用，锚节点定位在环境监测领域有重要的研究意义。目前，锚节点定位算法主要分为两大类，基于测距range-based算法^[1–2]和非测距range-free算法^[3]。range-based定位算法定位误差较小，但成本较高，需要测量节点间的距离或角度求取节点的位置；range-free算法不需要测量节点间的距离和方位，根据网络连通性等信息实现节点定位，其成本较低，但定位误差较大^[4–5]。

三边测量定位是测距range-based算法应用最为广泛的方法之一。将待定位节点称为目标节点，位置已知的节点称为锚节点^[5]，通常使用目标节点和锚节点之间的几何关系估计目标位置。锚节点布局变化会影响目标节点和锚节点之间的几何关系和估计目标位置。由于采用多个锚节点组合定位，锚节点布局的变化会影响目标节点的定位误差和传感器网络所能提供的“感知”数据的质量^[6–8]。在众多相关文献中,都提到了直接影响定位性能的一个重要因素—锚节点布局，布局是传感器网络领域的基础问题之一^[9–10]。现有的室内定位技术中,减少定位误差，提高定位精度已成为室内定位研究的难点^[11]。因此,研究定位误差和锚节点布局之间的关系对有效监测室内环境具有重要的意义。

现有针对锚节点布局问题的研究中：Yuan^[12]、Wang^[13]等通过一个近似函数和二次规划提出了锚节点布局模型，实现了在可接收时间成本内最小误差的最优布局，但是，没有精确计算误差，主要研究信标节点覆盖的布局优化，没有针对锚节点数量和布局进行研究。Liu^[14]、Yang^[15]、Aomumpa^[16]、Moore^[17]等在三边测量定位算法的基础上提高了定位精度，通过选择放弃一些定位可能不准确的节点提高定位精度。Chen^[18]、夏心江^[19]等在同心圆算法的基础上优化锚节点的选取，将误差因子的影响降到最低。Zhou^[20]、熊志广^[21]、Zhao^[22]等通过分析锚节点的摆放问题使多边定位误差面积最小,并证明了布置锚节点的3个定理。李海成^[23]、赵海^[24]等通过对三角形定位单元区域的误差分析，提出了定位布局单元以及在误差最小情况下定位单元布局的覆盖基定理，但是，这些方法对定位系统性能的分析与证明存在不足，且单一的锚节点选择算法难以适应三角形定位的自身特性。以上文献研究通过不同的锚节点选择方法使得多边测量定位中的定位误差最小，通过近似函数或者基于单元布局计算得到的最优的定位布局、定位误差，而且都是针对规则环境下的布局优化。基于多边测量定位算法，作者提出了一种新的定位误差上限估计方法，该方法通过精确计算得到规则环境和不规则环境下的双锚节点定位误差，并给出一组具有意义的最大多锚节点定位误差的上限，可以通过最小化估计误差和最佳锚节点布局模式的组合最小化这组上限。采用该方法可以比较任意两个锚节点布局之间的最大误差，可以最大限度地减少最大误差及减少测量误差造成的定位误差，为锚节点布局提供一个最优的布局。

1 多边定位误差估计 1.1 多边定位原理

针对三边测量定位算法的定位精度低的问题，Kim等提出了多边测量定位法。多边测量定位法（multilateration）^[25]要求至少获得目标节点与锚节点之间的3个距离信息，原理如图1所示，其中， $ B$ 是目标节点， $ A_1$ 、 $ A_2$ 、 $ A_3$ 、 $ A_4$ 和 $ A_5$ 是定位的锚节点。

1.2 多边定位误差估计原理

图2（a）为理想情况下（误差为零）的三边定位。因为存在测距误差，测距会落在围绕锚节点的一个环内，而不同锚节点环的宽度不一。实际情况下定位误差如图2（b）所示，3个圆环相交围成一个小区域，其中阴影区域的面积表示三边定位误差的大小。

显然，从图2（b）可知，该阴影区域形状复杂，很难获取精确解。 $\varepsilon $ 为测距误差，其计算式如下^[26]：

$\varepsilon = {c_1}{d^2} + {c_2}d + b$

(1)

式中， $ c_1$ 、 $ c_2$ 、 $ b$ 为常数。

2 锚节点定位误差估计 2.1 锚节点定位误差估计数学原理

多边测量法中，至少3点可以唯一确定一个目标节点的位置，从两个圆环的相交中能得到两个目标节点的可能位置^[23]。由两个锚节点的曲线交点定义目标节点的位置；目标节点根据两个锚节点坐标关系可以确定一个面积相对较大的误差区域；当目标节点获得另外一个锚节点信息后，根据这3个锚节点和未知节点之间的几何约束关系，可以得到一个更准确的误差区域。当采用3个锚节点进行定位时，若任意两个圆环交叉面积最小，则三边定位的相交区域会更小，定位精度更高。但是，采用三边测量定位时，误差区域形状不规则，面积计算困难且不精确；采用多边测量定位时，误差面积更加复杂，计算难度也更大。

图3中，区域1的面积为两个锚节点定位误差，区域2的面积为3个锚节点定位误差。因为测距误差 $\varepsilon $ 非常小，所以区域2面积无限接近于区域1面积，且区域1的面积可以精确计算。

多锚节点误差区域 $\varOmega $ 是锚节点两两相交区域的交集，其面积 ${S\!\!_\varOmega }$ 小于等于两个锚节点的相交面积 ${S\!\!_\varOmega }_{_{ij}}$ 的最小值。

$\left\{\begin{aligned}& \varepsilon \propto {S\!\!_\varOmega }, \\& \varepsilon < {\varepsilon _{\min }}, \\& \varOmega = {\varOmega _{{\rm{12}}}} \cap {\varOmega _{\rm{2}}}_{\rm{3}} \cap {\varOmega _{\rm{2}}}_{\rm{4}} \cap \cdots \cap {\varOmega _{ij}}, \\ & {S\!\!_\varOmega } \le {S\!\!_\varOmega }_{_{ij}}, \\ & {S\!\!_\varOmega } \le \min ({S\!\!_\varOmega }_{_{ij}}) \end{aligned} \right.$

(2)

因此，将 ${S\!\!_\varOmega }_{_{ij}}$ 作为误差 ${S\!\!_\varOmega }$ 的上限，基于此，作者提出利用两个锚节点的误差面积 ${S\!\!_\varOmega }_{_{ij}}$ 求取定位误差的上限，通过优化算法使误差上限最小，以保证全局定位误差最小。

2.2 不同状态的锚节点定位误差估计分析

在对无线传感器定位误差进行分析时，假设误差是由测距误差引起的，不考虑其他因素。

假设空间有 $n$ 个锚节点，最大感知覆盖半径为 $R$ ，即具体的锚节点覆盖半径 ${r_1}$ 、 ${r_2}$ 在小于等于 $R$ 的范围内。 ${r_1}$ 、 ${r_2}$ 是在理想情况下，传感器与目标节点距离在平面的投影半径； ${r_{10}}$ 、 ${r_{11}}$ 、 ${r_{20}}$ 、 ${r_{22}}$ 是在现实情况下，传感器与目标节点距离在平面的实际投影半径。根据 ${r_{20}}$ 、 ${r_{22}}$ 与 $d$ 的关系将定位误差估计分成3种状态，由第2.2.1、2.2.2、2.2.3节公式可计算出两个锚节点定位一个目标节点的定位误差。

2.2.1 状态1下的误差求取

当 ${r_{20}} < d$ 时，误差求取状态为图4所示。其中：两锚节点的覆盖范围半径分别为 ${r_1}$ 、 ${r_2}$ 。假设误差范围为 $\varepsilon $ ，因为误差的影响，覆盖半径会有变化； $d$ 为实际距离（单位均为cm）；误差为图中阴影部分的面积，两个锚节点圆环的交叠几何区域面积（如图3所示的区域1面积）。由于两个锚节点覆盖范围半径的不同，会有图4（a）～（d）这4种情况。

这4种情况的定位误差求取方法一样，故以图4（a）为例说明。

${d_m}$ 为圆心欧式距离（即 $ \left\{{B_1}\left( {{x_1},{y_1}} \right),{B_2}\left( {{x_2},{y_2}} \right), \cdots ,\right.$ $\left. {B_i}\left( {{x_i},{y_i}} \right), \cdots ,{B_n}\left( {{x_n},{y_n}} \right) \right\}$ 中任意两个锚节点的距离），计算式如下：

${d_m} = \sqrt {{{\left( {{x_i}{\rm{ - }}{x_j}} \right)}^2} + {{\left( {{y_i}{\rm{ - }}{y_j}} \right)}^2}} $

(3)

式中， $m = {\rm{C}}_n^2$ 。

${r_1}$ 、 ${r_2}$ 分别为锚节点 ${B_i}({x_i},{y_i})$ 和锚节点 ${B_j}({x_j},{y_j})$ 到目标节点 $A_i$ 的距离在地面的投影，即覆盖半径，计算公式如下：

$\left\{ \begin{aligned}& {r_1} = \sqrt {{{\left( {{x_i} - {A_i}x} \right)}^2}{\rm{ + }}{{\left( {{y_i} - {A_i}y} \right)}^2}} , \\ & {r_2} = \sqrt {{{\left( {{x_j} - {A_i}x} \right)}^2}{\rm{ + }}{{\left( {{y_j} - {A_i}y} \right)}^2}} \end{aligned} \right.$

(4)

式中， ${A_i}x$ 、 ${A_i}y$ 分别为目标节点 ${A_i}$ 的 $x$ 、 $y$ 坐标。

在绝对环境下， ${D_i}$ 、 ${D_j}$ 分别为锚节点 ${B_i}$ 、 ${B_j}$ 到目标节点 ${A_i}$ 的绝对距离，计算式如下：

$\left\{ \begin{aligned}& {D_i} = \sqrt {{r_1}^2 + {h^2}} ,\\& {D_j} = \sqrt {{r_2}^2 + {h^2}} \end{aligned} \right.$

(5)

式中， $ h$ 为锚节点布局面与目标节点之间高度。

真实环境下，由于测距误差 $\varepsilon $ 的影响，锚节点 ${B_i}$ 到目标节点 ${A_i}$ 的距离会产生会发生偏差。在测距误差 $\varepsilon $ 影响下， ${D_{ie}}$ 、 ${D_{ii}}$ 分别为锚节点 ${B_i}$ 到目标节点 ${A_i}$ 的最大和最小真实距离,也即在测距误差 $\varepsilon $ 的影响下形成的真实距离的区域范围。同理， ${D\!_{je}}$ 、 ${D\!_{jj}}$ 分别是在测距误差 $\varepsilon $ 影响下锚节点 ${B_j}$ 到目标节点 ${A_i}$ 的最大和最小真实距离。计算式如下：

$\left\{ \begin{aligned}& {D_{ie}} = {D_i} + \varepsilon , \\& {D_{ii}} = {D_i} - \varepsilon , \\& {D\!_{je}} = {D_j} + \varepsilon , \\& {D\!_{jj}} = {D_j} - \varepsilon \end{aligned} \right.$

(6)

在真实环境下，由于锚节点到目标节点的距离发生了变化，锚节点 ${B_i}({x_i},{y_i})$ 和锚节点 ${B_j}({x_j},{y_j})$ 分别到目标节点 ${A_i}$ 的距离在地面的投影也会发生变化。 ${r_{11}}$ 为锚节点 ${B_i}$ 到目标节点 ${A_i}$ 在最大真实距离 ${D_{ie}}$ 情况下的投影半径， ${r_{10}}$ 为锚节点 $B_i$ 到目标节点 ${A_i}$ 在最小真实距离 ${D_{ii}}$ 情况下的投影半径，即 ${r_{11}}$ 和 ${r_{10}}$ 分别为真实环境下锚节点 ${B_i}({x_i},{y_i})$ 到目标节点 ${A_i}$ 的距离在地面的最大和最小覆盖半径。

$\left\{ \begin{aligned}& {r_{10}} = \sqrt {D_{ii}^2 - {h^2}} ,\\& {r_{11}} = \sqrt {D_{ie}^2 - {h^2}}\end{aligned} \right.$

(7)

同理， ${r_{22}}$ 、 ${r_{20}}$ 分别是真实环境下锚节点 ${B_j}({x_j},{y_j})$ 到目标节点 ${A_i}$ 的距离在地面的最大和最小覆盖半径。

${\theta _{{\rm{ab1}}}}$ 表示 $\angle {A_1}{O_1}{B_1}$ ，它是由 ${r_{11}}$ 、 ${r_{11}}$ 、 ${A_1}{B_1}$ 组成的三角形 ${A_1}{O_1}{B_1}$ 中边 ${A_1}{B_1}$ 所对应的角，其中， ${A_1}$ 、 ${B_1}$ 是以 ${O_1}$ 为圆心、 ${r_{11}}$ 为半径的圆与以 ${O_2}$ 为圆心、 ${r_{22}}$ 为半径的圆的两个交点； ${\theta _{{\rm{ab2}}}}$ 表示 $\angle {A_1}{O_2}{B_1}$ ，计算式如下：

$\left\{ \begin{aligned}& {\theta _{{\rm{ab1}}}} = {\rm{arccos}}\sqrt {\frac{{{{{\rm{(}}{r_{11}^2} + {d^2}{\rm{ - }}{r_{22}^2}{\rm{)}}}^2}}}{{{\rm{2}}{r_{11}^2}{d^2}}} - 1} , \\ & {\theta _{{\rm{ab2}}}} = {\rm{arccos}}\sqrt {\frac{{{{{\rm{(}}{r_{22}^2} + {d^2}{\rm{ - }}{r_{11}^2}{\rm{)}}}^2}}}{{{\rm{2}}{r_{22}^2}{d^2}}} - 1} \end{aligned} \right.$

(8)

式中， $ d$ 表示两个锚节点的距离。

类似地， ${\theta _{{\rm{ad1}}}}$ 表示 $\angle {A_2}{O_1}{B_2}$ ， ${\theta _{{\rm{ad2}}}}$ 表示 $\angle {A_2}{O_2}{B_2}$ ， ${\theta _{{\rm{cb1}}}}$ 表示 $\angle {A_3}{O_1}{B_3}$ ， ${\theta _{{\rm{cb2}}}}$ 表示 $\angle {A_3}{O_2}{B_3}$ ， ${\theta _{{\rm{cd1}}}}$ 表示 $\angle {A_4}{O_1}{B_4}$ ， ${\theta _{{\rm{cd2}}}}$ 表示 $\angle {A_4}{O_2}{B_4}$ 。

${S\!\!_{\rm ab}}$ 表示圆心为 ${O_1}$ 、半径为 ${r_{11}}$ 的圆与圆心为 ${O_2}$ 、半径为 ${r_{22}}$ 的圆的相交几何区域面积； ${S\!\!_{\rm cd}}$ 表示圆心为 ${O_1}$ 、半径为 ${r_{10}}$ 的圆与圆心为 ${O_2}$ 、半径为 ${r_{20}}$ 的圆的相交几何区域面积； ${S\!\!_{\rm cb}}$ 表示圆心为 ${O_1}$ 、半径为 ${r_{11}}$ 的圆与圆心为 ${O_2}$ 、半径为 ${r_{20}}$ 的圆的相交几何区域面积； ${S\!\!_{\rm ad}}$ 表示圆心为 ${O_1}$ 、半径为 ${r_{10}}$ 的圆与圆心为 ${O_2}$ 、半径为 ${r_{22}}$ 的圆的相交几何区域面积； ${S_{}}$ 表示两个锚节点圆环的交叠几何区域面积，如图3所示的区域1面积、图4所示的阴影部分面积，即误差的大小。计算式如下：

$\left\{ \begin{aligned}& {S\!\!_{\rm ab}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{{\rm{a}}{{\rm{b}}_{\rm{1}}}}}{\rm{ - }}r_{11}^{\rm{2}}{\rm{sin}}\;{\theta _{{\rm{a}}{{\rm{b}}_1}}} + r_{22}^2{\theta _{\rm a{b_2}}}{\rm{ - }}r_{22}^{\rm{2}}{\rm{sin}}\;{\theta _{{\rm{a}}{{\rm{b}}_2}}}} \right], \\& {S\!\!_{\rm cd}} = \frac{1}{2}\left[ {r_{10}^2{\theta _{{\rm{c}}{{\rm{d}}_{\rm{1}}}}}{\rm{ - }}r_{10}^{\rm{2}}{\rm{sin}}\;{\theta _{{\rm{c}}{{\rm{d}}_1}}} + r_{20}^2{\theta _{\rm c{d_2}}}{\rm{ - }}r_{20}^{\rm{2}}{\rm{sin}}\;{\theta _{{\rm{c}}{{\rm{d}}_2}}}} \right], \\& {S\!\!_{\rm ad}} = \frac{1}{2}\left[ {r_{10}^2{\theta _{{\rm{a}}{{\rm{d}}_{\rm{1}}}}}{\rm{ - }}r_{10}^{\rm{2}}{\rm{sin}}\;{\theta _{{\rm{a}}{{\rm{d}}_1}}} + r_{22}^2{\theta _{\rm a{d_2}}}{\rm{ - }}r_{22}^{\rm{2}}{\rm{sin}}\;{\theta _{{\rm{a}}{{\rm{d}}_2}}}} \right], \\& {S\!\!_{\rm cb}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{{\rm{c}}{{\rm{b}}_{\rm{1}}}}}{\rm{ - }}r_{11}^{\rm{2}}{\rm{sin}}\;{\theta _{{\rm{c}}{{\rm{b}}_1}}} + r_{20}^2{\theta _{{\rm{c}}{{\rm{b}}_{\rm{2}}}}}{\rm{ - }}r_{20}^{\rm{2}}{\rm{sin}}\;{\theta _{{{\operatorname{cb} }_2}}}} \right], \\& S = {S\!\!_{\rm ab}} - {S\!\!_{\rm ad}} - {S\!\!_{\rm cb}} + {S\!\!_{\rm cd}} \end{aligned} \right.$

(9)

2.2.2 状态2下的误差求取

当 ${r_{20}} > d$ 、 ${r_{22}} < d$ 时，两个锚节点的覆盖半径不同导致存在两种误差求取状况，两个锚节点分布状态如图5（a）、（b）所示，定位误差为图5阴影部分的面积。

图5（a）、（b）的计算公式如式（10）、（11）所示：

$\left\{ \begin{aligned}& {\theta _{\rm ab11}} = 2 \times {\text{π}} - {\theta _{\rm ab1}},\\& {S\!\!_{{\rm{ab}}}} = \frac{1}{2}r_{11}^2{\theta _{\rm ab11}} - \frac{1}{2}r_{22}^2{\theta _{\rm ab2}} + 2 \times {S\!\!_1},\\& {S\!\!_{{\rm{cd}}}} = \frac{1}{2}r_{10}^2{\theta _{\rm cd11}} - \frac{1}{2}r_{20}^2{\theta _{\rm cd2}} + 2 \times {S\!\!_3},\\& {S\!\!_{\rm ad}} = \frac{1}{2}r_{10}^2{\theta _{\rm ad11}} - \frac{1}{2}r_{22}^2{\theta _{\rm ad2}} + 2 \times {S\!\!_2},\\& {S\!\!_{\rm cb}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{\rm cb1}} - r_{11}^2\sin {\theta _{\rm cb1}} + r_{20}^2{\theta _{\rm cb2}} - r_{20}^2\sin {\theta _{\rm cb2}}} \right],\\& S = {S\!\!_1} - {S\!\!_{\rm cb}} - {S\!\!_{\rm ab}} - {S\!\!_{\rm cd}} + {S\!\!_{\rm ad}}\end{aligned} \right.$

(10)

式中， ${S\!_1}$ 表示由 ${r_1}$ 、 ${r_2}$ 、 $d$ 这3条边组成的三角形的面积， ${S\!_2}$ 、 ${S\!_3}$ 类似。

$ \left\{ \begin{aligned}& {p_4} = {r_{11}} + {r_{20}} + d,\\& {S\!_4} = {p_4} \times ({p_4} - r_{11}^{}) \times ({p_4} - {r_{20}}) \times (p_4^{} - d),\\ & {S\!\!_{{\rm{\rm ab}}}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{\rm \rm ab1}} - r_{11}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm ab1}} + r_{22}^2{\theta _{\rm ab2}}{\rm{ - }}r_{22}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm ab2}}} \right],\\& {S\!\!_{\rm cd}} = \frac{1}{2}\left[ {r_{10}^2{\theta _{\rm cd1}}{\rm{ - }}r_{10}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cd1}} + r_{20}^2{\theta _{\rm cd2}}{\rm{ - }}r_{20}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm \rm cd2}}} \right],\\& {S\!\!_{\rm ad}} = \frac{1}{2}r_{10}^2{\theta _{\rm ad11}}{\rm{ - }}\frac{1}{2}r_{22}^{\rm{2}}{\theta _{\rm ad2}} + 2 \times {S\!\!_2},\\& {S\!\!_{{\rm{cb}}}} = \frac{1}{2}r_{20}^2{\theta _{\rm cb22}}{\rm{ - }}\frac{1}{2}r_{11}^{\rm{2}}{\theta _{{\rm{cb1}}}} + 2 \times {S\!\!_4},\\& S = {S\!_{\rm ab}} - {S\!_{\rm cb}} - {S\!_2} - {S\!_{\rm cd}} + {S\!_{\rm ad}}\end{aligned} \right. $

(11)

式中， ${p_4}$ 表示由 ${r_{11}}$ 、 ${r_{20}}$ 、 $d$ 这3条边组成的三角形的周长。

2.2.3 状态3下的误差求取

当 ${r_{22}} > d$ 时，由于两个锚节点覆盖范围半径的不同导致阴影部分面积的求取差别，有以下3种锚节点误差求取状态，如图6所示。

图6（a）、（b）、（c）的面积计算公式如式（12）、（13）、（14）所示：

$ \left\{ \begin{aligned}& {S\!\!_{\rm ab}} = \frac{1}{2}r_{11}^2{\theta _{\rm ab11}}{\rm{ - }}\frac{1}{2}r_{22}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm ab2}} + 2 \times {S\!\!_1},\\& {S\!\!_{\rm ad}} = \frac{1}{2}r_{10}^2{\theta _{\rm ad11}}{\rm{ - }}\frac{1}{2}r_{22}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm ad2}} + 2 \times {S\!\!_2},\\& {S\!\!_{\rm cd}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{\rm cd1}}{\rm{ - }}r_{10}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cd1}} + r_{20}^2{\theta _{\rm cd2}}{\rm{ - }}r_{20}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cd2}}} \right],\\& {S\!\!_{\rm cb}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{\rm cb1}}{\rm{ - }}r_{11}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cb1}} + r_{20}^2{\theta _{\rm cb2}}{\rm{ - }}r_{20}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cb2}}} \right],\\& S = {S\!\!_1} - {S\!\!_{\rm ab}} - {S\!\!_{\rm cb}} - {S\!\!_2} + {S\!\!_{\rm ad}} + {S\!\!_{\rm cd}}\end{aligned} \right. $

(12)

$ \left\{ {\begin{aligned}& {{S\!\!_{\rm ab}} = \frac{1}{2}r_{11}^2{\theta _{{\rm{\rm ab11}}}} - \frac{1}{2}r_{22}^2{\theta _{\rm ab}}_2 + 2 \times {S\!\!_1},}\\& {{S\!\!_{\rm ad}} = \frac{1}{2}r_{10}^2{\theta _{{\rm{\rm ad11}}}} - \frac{1}{2}r_{22}^2{\theta _{\rm ad}}_2 + 2 \times {S\!\!_2},}\\& {{S\!\!_{\rm cb}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{\rm cb1}}{\rm{ - }}r_{11}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cb1}} + r_{20}^2{\theta _{\rm cb2}}{\rm{ - }}r_{20}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cb2}}} \right],}\\& {S = {S\!\!_1} - {S\!\!_{\rm cb}} - {S\!\!_{\rm ab}} - {S\!\!_2} + {S\!\!_{\rm ad}}}\end{aligned}} \right. $

(13)

$ \left\{ \begin{aligned}& {S\!\!_{\rm ab}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{\rm ab1}}{\rm{ - }}r_{11}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm ab1}} + r_{22}^2{\theta _{\rm ab2}}{\rm{ - }}r_{22}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm ab2}}} \right],\\& {S\!\!_{\rm ad}} = \frac{1}{2}r_{10}^2{\theta _{{\rm{\rm ad11}}}} - \frac{1}{2}r_{22}^2{\theta _{\rm ad}}_2 + 2 \times {S\!\!_2},\\& {S\!\!_{\rm cb}} = \frac{1}{2}\left[ {r_{11}^2{\theta _{\rm cb1}}{\rm{ - }}r_{11}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cb1}} + r_{20}^2{\theta _{\rm cb2}}{\rm{ - }}r_{20}^{\rm{2}}{\rm{sin}}\;{\theta _{\rm cb2}}} \right],\\& S = {S\!\!_{\rm ab}} - {S\!\!_{\rm cb}} - {S\!\!_2} + {S\!\!_{\rm ad}}\end{aligned} \right. $

(14)

3 锚节点布局优化方法

锚节点布局属于典型的优化问题，求解难度大，采用一般的方法难以得到精确解。作者采用耗散均匀搜索粒子群算法（dissipative uniform search particle swarm optimization，DUPSO)^[27]进行求解，以提高速度和精度。DUPSO是对基本PSO算法的离散改进，使其能用于离散空间的优化问题，收敛速度更快。本文优化算法不仅可以求解规则环境下的最优布局，还可以求解不规则环境下的最优布局。

3.1 DUPSO算法描述

粒子群优化算法需要设定的参数少、计算简单，所以，使用DUPSO对第2节得出的误差估计算法结果进行优化。粒子初始化为一种锚节点布局，假设粒子群的群体规模为 $maxgen$ ，每个布局里包含 $count$ 个锚节点,在 ${D_{}}$ 维搜索空间中，第 $i$ 个粒子的位置和速度可以分别表示为 ${X_i}$ 和 ${V_i}$ ， $ c$ 、 $ r$ 为常数， $ w$ 为权重。通过适应度函数，迭代数次，群体所发现粒子的最佳位置 $ zbest$ ,再按照式（15）、（16）分别更新粒子的速度和位置：

${V_i}(t + 1) = w{V_i}(t) + c\left[ {r{P_i} + (1 - r){P_g}(t) - {X_i}(t)} \right]$

(15)

${X_i}(t + 1) = {X_i}(t) + {V_i}(t + 1)$

(16)

3.2 问题描述和模型

首先，需要确定一个适应度函数，定义适应度函数为式（17），即通过迭代寻找每个布局的最大误差的最小值。

$fitness = \min ({e_{\max }})$

(17)

3.2.1 布局误差的确定

在计算整个布局对目标节点的定位误差时，为了提高计算效率，采用剪枝算法减少时间复杂度。

对于一个目标节点，先比较通信半径 $ R$ 与覆盖半径 ${r_{11}}$ 、 ${r_{12}}$ 和 ${r_{20}}$ 、 ${r_{22}}$ ，若通信半径大于覆盖半径，则舍弃该锚节点，视为该未知节点的无效节点。

假设存在 $ n$ 个锚节点 $\{ {B_1},{B_2},{B_3}, \cdots ,{B_n}\} $ ， $ m$ 个目标节点 $\{ {A_1},{A_2},{A_3}, \cdots ,{A_m}\} $ ，每两个锚节点对一个目标节点 $i$ 的定位存在一个误差面积 ${S\!\!_i}$ ，根据误差公式计算定位误差，剔除误差大的组合，那么，该目标节点的定位误差 ${e_i}$ 为误差面积 ${S\!\!_N}$ 的最小值，即：

$\left\{ \begin{aligned}& {e_i} = {\rm{min}}({S\!\!_1},{S\!\!_2}, \cdots ,{S\!\!_N}),\\& N = {\rm{C}}_n^2 \end{aligned} \right.$

(18)

3.2.2 布局优化目标的确定

锚节点的布局优化问题（optimal layout of anchor nodes，OLAN）可描述为：给定 $ n$ 个锚节点，寻找合适的部署位置使得各个目标节点的误差面积 ${S\!\!_N}$ 最小。设有 $n$ 个移动传感器分布在区域 $S$ 上，每两个锚节点对目标节点都有一个误差面积 ${S\!\!_N}$ ，那么，对于一个目标节点而言，就有 ${\rm{C}}_n^2$ 个定位误差，则该目标节点的定位误差为 ${\rm{C}}_n^2$ 中最小的定位误差 ${\rm{min}}({S\!\!_1},{S\!\!_2}, \cdots ,{S\!\!_N})$ 。布局优化目标要求为满足一定约束条件下的最大定位误差，移动节点根据优化模型移动自身位置，以提高定位精度。布局优化的目标可描述为：

${e_{\max }} = {\rm{max}}({e_i})$

(19)

3.2.3 算法流程

步骤1：初始化所有锚节点坐标 ${B_i} = \{ {B_1},{B_2},{B_3}, \cdots ,{B_n}\} $ 及目标节点坐标 ${A_i} = \{ {A_1},{A_2},{A_3}, \cdots ,{A_m}\} $ 。

步骤2：优选锚节点。计算出每一个目标节点到所有锚节点的距离 ${D_i} = \{ {D_1},{D_2},{D_3}, \cdots ,{D_N}\} $ 及所有锚节点的覆盖半径 ${r_{11}}$ 、 ${r_{10}}$ 和 ${r_{22}}$ 、 ${r_{20}}$ ，比较所有覆盖半径与通信半径 $R$ ，通信半径大于覆盖半径，则对该目标节点的定位是无效的，应舍弃。由此，得到了有效的覆盖半径集合 ${r_i}$ 和相应的距离 ${D_i}$ ，以及有效的锚节点集合 ${B_i}$ 。

步骤3：计算定位误差。将 ${B_i}$ 中的所有有效锚节点任选两个作为一组，挑选出两个锚节点后，按照第3.2节的数学模型计算即可估计出一个未知节点的定位误差，选取所有定位误差中最小的作为该目标节点的定位误差 ${e_i}$ 。其余目标节点误差采用同样的方法可得。最后，采用式（19）计算最大定位误差。

4 仿真实验 4.1 仿真环境

利用MATLAB建立了一个21 m $\times$ 21 m的矩形仿真区域，30个锚节点在该区域内随机分布，441个目标节点均匀分布，图7是锚节点和目标节点的平面分布示意图。同时，每个锚节点的通信半径 $R$ 都相同，设 $R = 20$ 。

图8是锚节点（3，10）、（17，10）对21 $\times$ 21区域内均匀分布的目标节点定位的误差分布，其中，误差为相对误差。

4.2 定位误差的布局优化 4.2.1 规则环境定位误差的布局优化

为了优化布局达到全局最小误差，随机摆放了 $ n$ 个锚节点，441个目标节点均匀分布。通过5 000次迭代，得到最优布局，图9给出了仿真锚节点数为10、20、30时本文算法的最优布局。

由图9可知：锚节点数为10时，其平均误差为4.510 3；锚节点数为20时，其平均误差为1.477 1；锚节点数为30时，其平均误差为0.950 9。

图10为不同布局算法定位误差与锚节点数的关系。由图10可知，采用本文算法优化后的锚节点布局定位精度比均匀布局和随机布局的定位精度高。而且当锚节点超过20时，本文布局优化算法的定位误差变化缓慢，可以满足减少锚节点数的同时保证较高的定位精度。

4.2.2 不规则环境定位误差的布局优化

本文算法不仅可以对规则环境定位误差进行布局优化，还可以对任何环境定位进行布局优化。以两种不规则环境为例，用本文优化算法，通过5 000次迭代，求解最优布局，如图11所示。其中，图11（b）、（d）分别是图11（a）、（c）这两种环境下20个锚节点的最优布局。

5 结　论

针对多边定位误差面积不规则，计算困难等问题，提出了一种误差面积趋近于多边定位误差面积的锚节点误差估计方法，通过锚节点的误差大小评价布局的优劣，准确计算出布局的误差上限，呈现出误差的立体分布；并引入DUPSO优化算法进行布局优化，确定锚节点最优布局。仿真实验结果表明：本文优化算法不仅可以求解规则环境下的最优布局，还可以对不规则环境的布局进行优化；优化后的锚节点布局在一定范围内缩小了定位误差，定位精度高于均匀布局和随机布局的定位精度。本文算法能在保障定位精度的要求下，有效地优化空间锚节点布局，满足定位资源配置优化要求。下一步研究工作为：如何调节通信半径的大小以及锚节点和目标节点数量关系以保证最小的定位误差。