基于传播误差最小原理的锚节点数量受限时的定位方法

摘要

本发明提供一种基于传播误差最小原理的锚节点数量受限时的定位方法，包括以下步骤：步骤1，收集每个新节点的邻居节点的位置信息；步骤2，测量新节点和每个邻居节点之间的距离，得到各距离的估计误差；步骤3，从邻居节点的位置信息中，选择具有最小传播估计误差的节点；步骤4，利用选择好的邻居节点的位置信息和距离，来计算新节点位置和估计误差。本发明选择有用的邻节点，包括锚节点和常规节点，适合用于锚节点的数目很少的情况下，以新节点和邻居节点的传播误差最小原理来计算新节点的位置。

说明书

技术领域

本发明涉及位置感知领域，特别是一种基于传播误差最小原理的锚节点数量受限时的定位新方法。

背景技术

位置感知已经成为包括位置跟踪、地图、基于路由的定位、覆盖管理、协同信号处理和其它许多无线网络应用的重要特征。例如，基于路由协议的定位中，它的路由和数据转发都是有确定地理位置的。如果节点的位置可以更准确地定位，则网络的数据传输效率会更高。

然而，由于成本和能量的限制，并不是所有的节点都有类似GPS接收器这样的可靠的位置信息来源。由于GPS需要与卫星时钟精确同步，因此在每个节点上添加GPS的解决方案，并不适合用于大规模的无线网络(RSSI based location estimation in wireless sensors networks,Al Alawi,R.Dept.of Elect.&Electron.Eng.,Univ.of Bahrain,Isa Town,Bahrain,Networks(ICON),201117^th IE)。因此，定位系统通常是由部分经由GPS或手动放置、已知坐标系的点(以下称为锚)，发送这些位置信息给网络中的其它常规节点来构成的。当有足够多的邻居锚节点时，节点的位置将通过计算交叉区域来得到。然而，当锚节点的数目很少，在通信范围内的平均值不大于3个锚，传统的方法是无法工作的。

发明内容

为了克服现有技术存在的问题，本发明提供一种当已知的锚节点数量受限时的定位新方法。选择有用的邻节点，包括锚节点和常规节点，以新节点和邻居节点的传播误差最小原理来计算新节点的位置。

一种基于传播误差最小原理的锚节点数量受限时的定位方法，包括以下步骤：

步骤1，收集每个新节点的邻居节点的位置信息，包括位置坐标和估计坐标的误差；

步骤2，采用接收信号强度方法测量新节点和每个邻居节点之间的距离，并得到估计误差；

步骤3，从邻居节点的位置信息中，基于最小传播估计误差的计算规则选择具有最小传播估计误差的节点；

步骤4，利用选择好的邻居节点的位置信息和距离，来计算新节点位置和估计误差。

本发明与现有技术相比，具有以下优点：本发明考虑到锚节点的移动性，所述算法能够动态融合所记录的节点的信息，而不需要过多的交换数据或算法信息。根据选择邻居节点的位置和估计误差信息，新节点可以计算出自己的位置和误差估计信息并将它们广播到锚节点比较少的邻居节点上。

下面结合说明书附图，对本发明做进一步描述。

附图说明

图1为本发明方法流程图：

图2为本发明新节点从邻居节点收集位置信息示意图；

图3为本发明基于RSSI的距离估计示意图；

图4为本发明基于两个相邻节点坐标的位置计算新节点位置信息的示意图。

具体实施方式

本发明采用MEPLE(Minimized Error Propagation Localization Method based on Error Estimation)定位方法计算新的未知节点的位置信息。

结合图1，一种基于传播误差最小原理的锚节点数量受限时的定位方法，包括以下步骤：

步骤1，收集每个新节点的邻居节点的位置信息，邻居节点为在接收机信号灵敏度范围内，所能收到的节点；

步骤2，测量新节点和每个邻居节点之间的距离，得到各距离的估计误差；

步骤3，从邻居节点的位置信息中，选择具有最小传播估计误差的节点；

步骤4，利用选择好的邻居节点的位置信息和距离，来计算新节点位置和估计误差。

结合图2，步骤1中的邻居节点位置信息包括位置坐标和估计坐标的误差 其中(x_k,y_k)为第k个邻居节点的位置信息坐标，为第k个邻居节点的估计坐标的误差，d_k是第k个邻居节点与新节点之间的距离。

结合图3，步骤2采用接收信号强度方法测量新节点和每个邻居节点之间的距离，并得到估计误差，具体过程为：

步骤2.1，测量第k个邻居节点的信号强度指标RSSI_k；

步骤2.2，对第k个邻居节点使用距离和功率之间的映射公式来计算估计距离，映射公式为P_r(dBm)＝A-10·n·lgr。根据映射公式有新节点与第k个节点之间的估计距离其中ρ(RSSI_k)是RSSI_k和估计距离的映射函数，A为在距离一米时的信号强度，n为衰减系数；根据该公式能够同时得到各距离的估计误差

步骤3中采用最小传播估计误差(MEPLE)的计算规则选择具有最小传播估计误差的节点，计算规则为

$\mathrm{Pair}(i,j)=\underset{\{i,j\in (1..k),i\ne j\}}{\arg \min }\{\Gamma (x_i,y_i,d_i,{\sigma }_{x_i,}{\sigma }_{y_i,}{\sigma }_{d_i,}{x}_j,y_j,d_j,{\sigma }_{x_j,}{\sigma }_{y_j,}{\sigma }_{d_j})\}$

其中

$\left(\begin{array}{c}\Gamma (x_i,y_i,d_i,{\sigma }_{x_i},{\sigma }_{y_i},{\sigma }_{d_i},x_j,y_j,d_j,{\sigma }_{x_j},{\sigma }_{y_j},{\sigma }_{d_j})\\ =[({\left(\frac{\partial F_x}{\partial x_i}\right)}^2+{\left(\frac{\partial F_y}{\partial x_i}\right)}^2)·{{\sigma }_{x_i}}^2+({\left(\frac{\partial F_x}{\partial y_i}\right)}^2+{\left(\frac{\partial F_y}{\partial y_i}\right)}^2)·{{\sigma }_{y_i}}^2+({\left(\frac{\partial F_x}{\partial d_i}\right)}^2+{\left(\frac{\partial F_y}{\partial d_i}\right)}^2){·{\sigma }_{d_i}}^2]\\ +[({\left(\frac{\partial F_x}{\partial x_j}\right)}^2+{\left(\frac{\partial F_y}{\partial x_j}\right)}^2)·{{\sigma }_{x_j}}^2+({\left(\frac{\partial F_x}{\partial y_j}\right)}^2+{\left(\frac{\partial F_y}{\partial y_j}\right)}^2)·{{\sigma }_{y_j}}^2+({\left(\frac{\partial F_x}{\partial d_j}\right)}^2+{\left(\frac{\partial F_y}{\partial d_j}\right)}^2)·{{\sigma }_{d_j}}^2]\end{array}\right)$

函数F()为方程组$\left(\begin{array}{c}{(x-x_i)}^2+{(y-y_i)}^2={d_i}^2\\ {(x-x_j)}^2+{(y-y_j)}^2={d_j}^2\end{array}\right),$其中(x,y)是新节点的位置信息坐标。

MEPLE的误差传播计算原理如下：

位置估计误差(σ_x,σ_y)可以通过如下计算：

$\left(\begin{array}{c}{\sigma }_x=\sqrt{[{(\frac{\partial F_x}{\partial x_i}·{\sigma }_{x_i})}^2+{(\frac{\partial F_x}{\partial y_i}·{\sigma }_{y_i})}^2+{(\frac{\partial F_x}{\partial d_i}·{\sigma }_{d_i})}^2]+[{(\frac{\partial F_x}{\partial x_j}·{\sigma }_{x_j})}^2+{(\frac{\partial F_x}{\partial y_j}·{\sigma }_{y_j})}^2+{(\frac{\partial F_x}{\partial d_j}·{\sigma }_{d_j})}^2]}\\ {\sigma }_y=\sqrt{[{(\frac{\partial F_y}{\partial x_i}·{\sigma }_{x_i})}^2+{(\frac{\partial F_y}{\partial y_i}·{\sigma }_{y_i})}^2+{(\frac{\partial F_y}{\partial d_i}·{\sigma }_{d_i})}^2]+[{(\frac{\partial F_y}{\partial x_j}·{\sigma }_{x_j})}^2+{(\frac{\partial F_y}{\partial y_j}·{\sigma }_{y_j})}^2+{(\frac{\partial F_y}{\partial d_j}·{\sigma }_{d_j})}^2]}\end{array}\right)$

方差估计σ定义为：

$\left(\begin{array}{c}{\sigma }^2={{\sigma }_x}^2+{{\sigma }_y}^2\\ =[({\left(\frac{\partial F_x}{\partial x_i}\right)}^2+{\left(\frac{\partial F_y}{\partial x_i}\right)}^2)·{{\sigma }_{x_i}}^2+({\left(\frac{\partial F_x}{\partial y_i}\right)}^2+{\left(\frac{\partial F_y}{\partial y_i}\right)}^2)·{{\sigma }_{y_i}}^2+({\left(\frac{\partial F_x}{\partial d_i}\right)}^2+{\left(\frac{\partial F_y}{\partial d_i}\right)}^2){·{\sigma }_{d_i}}^2]\\ +[({\left(\frac{\partial F_x}{\partial x_j}\right)}^2+{\left(\frac{\partial F_y}{\partial x_j}\right)}^2)·{{\sigma }_{x_j}}^2+({\left(\frac{\partial F_x}{\partial y_j}\right)}^2+{\left(\frac{\partial F_y}{\partial y_j}\right)}^2)·{{\sigma }_{y_j}}^2+({\left(\frac{\partial F_x}{\partial d_j}\right)}^2+{\left(\frac{\partial F_y}{\partial d_j}\right)}^2)·{{\sigma }_{d_j}}^2]\end{array}\right)$

从方程中，我们可以看到，定位的估计误差(σ_x,σ_y)来自三部分组成，具体到一个邻居节点i(x_i,y_i,d_i)：

(1)σ_x为在x方向上，影响因子是

(2)σ_y为在y方向上，影响因子是

(3)σ_d为在d方向上，影响因子是

计算这些影响因素：

有两个邻居的定位信息，那就是：

$\left(\begin{array}{c}{(x-x_i)}^2+{(y-y_i)}^2={d_i}^2\\ {(x-x_j)}^2+{(y-y_j)}^2={d_j}^2\end{array}\right)$

将上公式的对x的偏微分方程，可以得到：

$\left(\begin{array}{c}(x-x_i)\frac{\partial F_x}{\partial x_i}+(y-y_i)\frac{\partial F_y}{\partial x_i}=(x-x_i)\\ (x-x_j)\frac{\partial F_x}{\partial x_i}+(y-y_j)\frac{\partial F_y}{\partial x_i}=0\end{array}\right)$

求解该方程，可以得到：

$\left(\begin{array}{c}\frac{\partial F_x}{\partial x_i}=\frac{(x-x_i)(y-y_i)}{(x-x_i)(y-y_j)-(x-x_j)(y-y_i)}\\ \frac{\partial F_y}{\partial x_i}=\frac{(x-x_i)(x-x_j)}{(x-x_j)(y-y_i)-(x-x_i)(y-y_j)}\end{array}\right)$

用同样的方法，取y和d的偏微分方程，分别可得：

$\left(\begin{array}{c}\frac{\partial F_x}{\partial y_i}=\frac{(y-y_i)(y-y_i)}{(y-y_j)(x-x_i)-(y-y_i)(x-x_j)}\\ \frac{\partial F_y}{\partial y_i}=\frac{(y-y_i)(y-y_j)}{(y-y_i)(x-x_j)-(y-y_j)(x-x_i)}\end{array}\right)$

$\left(\begin{array}{c}\frac{\partial F_x}{\partial d_i}=\frac{d_i(y-y_i)}{(x-x_i)(y-y_j)-(x-x_j)(y-y_i)}\\ \frac{\partial F_y}{\partial d_i}=\frac{d_i(x-x_j)}{(x-x_j)(y-y_i)-(x-x_i)(y-y_j)}\end{array}\right)$

被称为在x_i分量上的误差传播系数，被称为在y_i分量上的误差传播系数，被称为在d_i分量上的误差传播系数。

给出函数$\Gamma (x_i{,y}_i,d_i,{\sigma }_{x_i},{\sigma }_{y_i},{\sigma }_{d_i},x_j,y_j,d_j,{\sigma }_{x_j},{\sigma }_{y_j},{\sigma }_{d_j})$的定义。并利用此函数来选择邻居节点对(i,j)，以使给需要计算位置的节点(x,y)带来最小估计误差。

$\left(\begin{array}{c}\Gamma (x_i,y_i,d_i,{\sigma }_{x_i},{\sigma }_{y_i},{\sigma }_{d_i},x_j,y_j,d_j,{\sigma }_{x_j},{\sigma }_{y_j},{\sigma }_{d_j})={\sigma }^2\\ =[({\left(\frac{\partial F_x}{\partial x_i}\right)}^2+{\left(\frac{\partial F_y}{\partial x_i}\right)}^2)·{{\sigma }_{x_i}}^2+({\left(\frac{\partial F_x}{\partial y_i}\right)}^2+{\left(\frac{\partial F_y}{\partial y_i}\right)}^2)·{{\sigma }_{y_i}}^2+({\left(\frac{\partial F_x}{\partial d_i}\right)}^2+{\left(\frac{\partial F_y}{\partial d_i}\right)}^2){·{\sigma }_{d_i}}^2]\\ +[({\left(\frac{\partial F_x}{\partial x_j}\right)}^2+{\left(\frac{\partial F_y}{\partial x_j}\right)}^2)·{{\sigma }_{x_j}}^2+({\left(\frac{\partial F_x}{\partial y_j}\right)}^2+{\left(\frac{\partial F_y}{\partial y_j}\right)}^2)·{{\sigma }_{y_j}}^2+({\left(\frac{\partial F_x}{\partial d_j}\right)}^2+{\left(\frac{\partial F_y}{\partial d_j}\right)}^2)·{{\sigma }_{d_j}}^2]\end{array}\right)$

结合图4，步骤4，选定的邻居节点对(x_i,y_i,d_i)和(x_j,y_j,d_j)作为数据源，计算方程组得到新节点坐标(x,y)：

$\left(\begin{array}{c}{(x-x_i)}^2+{(y-y_i)}^2={d_i}^2\\ {(x-x_j)}^2+{(y-y_j)}^2={d_j}^2\end{array}\right)$

新节点节点(x,y)的估计误差(σ_x,σ_y)为：

$\left(\begin{array}{c}{\sigma }_x=\sqrt{[{(\frac{\partial F_x}{\partial x_i}·{\sigma }_{x_i})}^2+{(\frac{\partial F_x}{\partial y_i}·{\sigma }_{y_i})}^2+{(\frac{\partial F_x}{\partial d_i}·{\sigma }_{d_i})}^2]+[{(\frac{\partial F_x}{\partial x_j}·{\sigma }_{x_j})}^2+{(\frac{\partial F_x}{\partial y_j}·{\sigma }_{y_j})}^2+{(\frac{\partial F_x}{\partial d_j}·{\sigma }_{d_j})}^2]}\\ {\sigma }_y=\sqrt{[{(\frac{\partial F_y}{\partial x_i}·{\sigma }_{x_i})}^2+{(\frac{\partial F_y}{\partial y_i}·{\sigma }_{y_i})}^2+{(\frac{\partial F_y}{\partial d_i}·{\sigma }_{d_i})}^2]+[{(\frac{\partial F_y}{\partial x_j}·{\sigma }_{x_j})}^2+{(\frac{\partial F_y}{\partial y_j}·{\sigma }_{y_j})}^2+{(\frac{\partial F_y}{\partial d_j}·{\sigma }_{d_j})}^2]}\end{array}\right)$

因此，新节点的位置信息是(x,y,σ_x,σ_y)。