工程科学与技术   2018, Vol. 50 Issue (5): 167-175
基于定位误差估计的锚节点布局优化
吴晓军1,2, 孙维彤1, 刘昊文1, 张浩3, 路纲2, 张玉梅2     
1. 陕西师范大学 现代教学技术教育部重点实验室,陕西 西安 710062;
2. 陕西师范大学 计算机科学学院,陕西 西安 710062;
3. 西安工业大学 自动化学院,陕西 西安 710072
基金项目: 国家重点研发计划资助项目(2017YFB1402102);国家自然科学基金资助项目(11772178;11872036;11502133);陕西省自然科学基础研究计划资助项目(2017JM6103);中央高校基本科研业务费专项资金资助项目(2018CBLY007)
摘要: 大多数现有研究忽略了室内定位系统的最佳锚节点布局问题,传统多边测量定位算法误差分析中,存在误差面积不规则、计算困难等问题,作者提出了一种实现最小定位误差的锚节点布局方法。使用几何分析和实验分析相组合的方法研究定位误差和锚节点布局之间的关系,通过几何面积关系精确计算了双锚节点定位误差,提出了一种新的误差上限估计方法,这一误差上限反映了锚节点的位置和锚节点处的误差,可以用于比较任意两个锚节点布局之间的最大误差,描述误差的立体分布。引入耗散均匀搜索粒子群算法(dissipative uniform search particle swarm optimization,DUPSO),提出了一种新的多锚节点空间布局优化算法,找到了一种可以最大限度减少最大定位误差的最优布局。为了验证本文方法适用于各种规则、不规则环境以及不同数量锚节点最优布局的求解,仿真实现了不同数目锚节点和不同环境下锚节点的最优布局,并对不同的锚节点布局方法进行了比较。实验结果表明,使用锚节点的最佳布局,室内定位系统可以获得更高的定位精度。本文的布局优化算法是通用的,在实践中具有可行性和有效性。
关键词: 锚节点布局    布局优化    多边测量定位    误差上限估计    
Optimization of Anchor Node Layout Based on Positioning Error Estimation
WU Xiaojun1,2, SUN Weitong1, LIU Haowen1, ZHANG Hao3, LU Gang2, ZHANG Yumei2     
1. Key Lab. of Modern Teaching Technol., Ministry of Education Shaanxi Normal Univ., Xi’an 710062, China;
2. School of Computer Sci., Shaanxi Normal Univ., Xi’an 710062, China;
3. School of Automation, Northwestern Polytechnical Univ., Xi’an 710072, China
Abstract: In order to solve the problem of optimal anchor node layout in indoor positioning system, an anchor node layout method was proposed in this paper by deploying anchor nodes to achieve the minimum positioning error. Based on the multi-measurement positioning algorithm, for the problems of irregular measurement area, difficulty in calculation and so on, a combination of geometric analysis and experimental analysis was used to study the relationship between positioning error and the layout of anchor nodes. The positioning error of double-anchor nodes was accurately calculated by the geometric area relationship, and a new error upper limit estimation method was proposed for node positioning error. This error upper limit reflected the position of the anchor node and the error at the anchor node. The maximum error between any two anchor node layouts was compared and the three-dimensional distribution of errors was presented. Then, in this paper, DUPSO (dissipative uniform search particle swarm optimization) algorithm was introduced, a new multi-anchor node spatial layout optimization algorithm was proposed, and an optimal layout that can minimize the maximum positioning error was found. In order to verify that the algorithm of this paper is applicable to the solution of various rules, irregular environments and the optimal layout of different number of anchor nodes, the optimal layout of anchor nodes and different numbers of anchor nodes in different environments and the layout of different anchor nodes were simulated, and the layout methods of different anchor nodes were compared. The experimental results showed that with the optimal layout of the anchor nodes, the indoor positioning system can obtain higher positioning accuracy. The layout optimization algorithm presented in the paper is universal, feasible and effective in practice.
Key words: anchor nodes layout    layout optimization    multi-measurement positioning    error upper limit estimation    

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

三边测量定位是测距range-based算法应用最为广泛的方法之一。将待定位节点称为目标节点,位置已知的节点称为锚节点[5],通常使用目标节点和锚节点之间的几何关系估计目标位置。锚节点布局变化会影响目标节点和锚节点之间的几何关系和估计目标位置。由于采用多个锚节点组合定位,锚节点布局的变化会影响目标节点的定位误差和传感器网络所能提供的“感知”数据的质量[68]。在众多相关文献中,都提到了直接影响定位性能的一个重要因素—锚节点布局,布局是传感器网络领域的基础问题之一[910]。现有的室内定位技术中,减少定位误差,提高定位精度已成为室内定位研究的难点[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 多边定位原理 Fig. 1 Multilateral positioning principle

1.2 多边定位误差估计原理

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

图2 三边定位情况 Fig. 2 Situation of trilateral positioning

显然,从图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的面积可以精确计算。

图3 两边定位误差和三边定位误差的对比 Fig. 3 Comparison of two-side positioning error and three-edge positioning error

多锚节点误差区域 $\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 两个锚节点的定位误差(状态1) Fig. 4 Positioning error of two anchor nodes (status 1)

这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 两个锚节点的定位误差(状态2) Fig. 5 Positioning error of two anchor nodes (status 2)

图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 两个锚节点的定位误差(状态3) Fig. 6 Positioning error of two anchor nodes (status 3)

图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$

图7 节点分布示意图 Fig. 7 Sketch map of node distribution

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

图8 定位误差分布3维图 Fig. 8 Three-dimensional map of positioning error distribution

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。

图9 锚节点最优布局节点分布 Fig. 9 Optimal layout node distribution of thirty algorithms and anchor nodes

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

图10 不同布局算法定位误差与锚节点数的关系 Fig. 10 Relationship of positioning error on different layout anchor nodes

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

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

图11 不规则环境下20个锚节点最优布局节点分布 Fig. 11 Optimal layout node distribution of twenty nodes in irregular environment

5 结 论

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

参考文献
[1]
Shahra E Q,Sheltami T R,Shakshuki E. A comparative study of range-free and range-based localization protocols for wireless sensor network:Sing COOJA simulator[J]. International Journal of Distributed Systems and Technologies, 2017, 8(1): 1-16. DOI:10.4018/IJDST.2017010101
[2]
Moreno-Salinas D,Crasta N,Ribeiro M,et al. Integrated motion planning,control,and estimationfor range-based marine vehicle positioning and target localization[J]. IFAC-PapersOnLine, 2016, 49(23): 34-40. DOI:10.1016/j.ifacol.2016.10.318
[3]
Liao Zhuolan,Wang Jianxin,Zhang Shigeng,et al. Minimizing movement for target coverage and network connectivity in mobile sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(7): 1971-1983. DOI:10.1109/TPDS.2014.2333011
[4]
Mao G,Fidan B,Anderson B D O. Wireless sensor network localization techniques[J]. Computer Networks, 2007, 51(10): 2529-2553. DOI:10.1016/j.comnet.2006.11.018
[5]
孙利民.无线传感网络[M].北京:清华大学出版社,2005:135–155.
[6]
Song Shuang,Qiu Xiaoxiao,Wang Jiaole,et al. Design and optimization strategy of sensor array layout for magnetic localization system[J]. IEEE Sensors Journal, 2017, 17(6): 1849-1857. DOI:10.1109/JSEN.2017.2652470
[7]
Muhammad Farooq-i-Azam,Muhammad N A.Location and position estimation in wireless sensor networks[M]//Wireless Sensor Networks:Current Status and Future Trends.Boca Raton:CRC Press,2013:179–214.
[8]
Domingo-Perez F,Lazaro-Galilea J L,Wieser A,et al. Sensor placement determination for range-difference positioning using evolutionary multi-objective optimization[J]. Expert Systems with Applications, 2016, 47(C): 95-105. DOI:10.1016/j.eswa.2015.11.008
[9]
Huang Rui,Záruba G V.Beacon deployment for sensor network localization[C]//Proceedings of the 2007 Wireless Communications and NETWORKING Conference.Hong Kong:IEEE,2007:3188–3193.
[10]
Meng Wei,Xie Lihua,Xiao Wendong. Optimal TDOA sensor-pair placement with uncertainty in source location[J]. IEEE Transactions on Vehicular Technology, 2016, 65(11): 9260-9271. DOI:10.1109/TVT.2016.2516031
[11]
Chen Yingying,Francisco J A,Trappe W,et al.A practical approach to landmark deployment for indoor localization[C]//Proceedings of the 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks,2006(SECON’06).Reston:IEEE,2006:365–373.
[12]
Yuan Zimu,Li Wei,Xu Zhiwei,et al.Beacon node placement for minimal localization error[EB/OL].(2017-07-10)[2015-03-29].https://arxiv.org/abs/1503.08404.
[13]
Wang Riming,Shen Baihua,Liu Yang.Optimization of sensor deployment for localization accuracy improvement[C]//Proceedings of the 2016 IEEE International Conference on Consumer Electronics-China (ICCE-China).Guangzhou:IEEE,2016:1–4.
[14]
Liu Juan,Zhang Ying,Zhao Feng.Robust distributed node localization with error management[C]//Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York:ACM,2006:250–261.
[15]
Yang Zheng,Liu Yunhao. Quality of trilateration:Confidence-based iterative localization[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(5): 631-640. DOI:10.1109/TPDS.2009.90
[16]
Aomumpai S,Kondee K,Prommak C,et al.Optimal placement of reference nodes for wirelessindoor positioning systems[C]//Proceedings of the 2014 11th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology.Nakhon Ratchasim:IEEE,2014:1–6.
[17]
Moore D,Leonard J,Rus D,et al.Robust distributed network localization with noisy range measurements[C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.New York:ACM,2004:50–61.
[18]
Chen Yourong,Lu Siyi,Chen Junjie,et al. Node localization algorithm of wireless sensor networks with mobile beacon node[J]. Peer-to-Peer Networking and Applications, 2017, 10(3): 795-807. DOI:10.1007/s12083-016-0522-8
[19]
Xia Xinjiang,Hu Gang,Wang Yehua. Study on improved algorithm based on concentric circles localization[J]. Computer Science, 2012, 39(6): 68-71. [夏心江,胡钢,王烨华. 基于同心圆定位算法的改进算法研究[J]. 计算机科学, 2012, 39(6): 68-71. DOI:10.3969/j.issn.1002-137X.2012.06.017]
[20]
Zhou Yan,Zhao Hai,Zhang Jun,et al. Location error analysis of pervasive computing[J]. Acta Electronica Sinica, 2009, 37(2): 382-386.
[21]
Xiong Zhiguang,Shi Weiren,Xu Lei,et al. Trilateration localization algorithm based on weighted disposal[J]. Computer Engineering and Applications, 2010, 46(22): 99-102. [熊志广,石为人,许磊,等. 基于加权处理的三边测量定位算法[J]. 计算机工程与应用, 2010, 46(22): 99-102. DOI:10.3778/j.issn.1002-8331.2010.22.030]
[22]
Zhao Hai,Sun Peigang,Zhang Wenbo,et al. Research on reference nodes placement and selection of ubiquitous computing locating service[J]. Frontiers of Electrical and Electronic Engineering, 2007, 2(1): 13-22. DOI:10.1007/s11460-007-0003-1
[23]
Li Haicheng,Zhang Rui,Zhou Yan. Research on deployment of locating unit in ubiquitous computing[J]. Computer Science, 2010, 37(1): 142-145. [李海成,张锐,周艳. 普适计算中定位单元布局研究[J]. 计算机科学, 2010, 37(1): 142-145. DOI:10.3969/j.issn.1002-137X.2010.01.034]
[24]
Sun Peigang,Zhao Hai,Zhang Wenbo,et al. Research on reference nodes placement and selection of ubiquitious computing locating service[J]. Acta Electronica Sinica, 2006, 34(8): 1456-1463. [孙佩刚,赵海,张文波,等. 普适计算中定位服务的参考点布置及选择算法[J]. 电子学报, 2006, 34(8): 1456-1463. DOI:10.3321/j.issn:0372-2112.2006.08.020]
[25]
Kim S W,Lee B T. Scalable DV-Hop localization algorithm with constrained multilateration for wireless sensor network[J]. IEICE Transactions on Communications, 2009, E92.B(10): 3075-3078. DOI:10.1587/transcom.E92.B.3075
[26]
Zhao Hao,Zhang Kuan,Zhu Jian,et al. Error analysis and improvement of ultrasonic distance measuring based on TDOA[J]. Journal of Northeastern University(Natural Science), 2011, 32(6): 802-805. [赵海,张宽,朱剑,等. 基于TDOA的超声波测距误差分析与改进[J]. 东北大学学报(自然科学版), 2011, 32(6): 802-805. DOI:10.3969/j.issn.1005-3026.2011.06.011]
[27]
Wu Xiaojun,Yang Zhanzhong,Zhao Ming. A uniform searching particle swarm optimization algorithm[J]. Acta Electronica Sinica, 2011, 39(6): 1261-1266. [吴晓军,杨战中,赵明. 均匀搜索粒子群算法[J]. 电子学报, 2011, 39(6): 1261-1266.]