一种基于到达角度的分布式无线传感网络的节点定位方法

摘要

本发明公开了一种基于到达角度的分布式无线传感网络的节点定位方法，该方法下每个节点无需配备类似指南针的设备来统一局部坐标系的方向，这增加了算法适应场景的能力，在复杂的场景无法配备指南针的时候仍然适用。同时本发明方法是线性的，计算简洁方便，并且具有指数收敛性质，收敛速度快，而且算法能保证全局收敛性，说明随机选取初始估计值的情况下不会陷入局部最优值，算法稳定性好；且本发明只需要两个锚节点，避免了大量安装GPS带来的高价格。

说明书

技术领域

本发明属于无线传感网络技术领域，具体涉及一种基于到达角度的分布式无线传感网络的节点定位方法。

背景技术

在大规模无线传感器网络及多机器人网络的应用中，位置信息在监测地理数据，目标跟踪，提供通信服务等应用中起到非常关键的作用。

在大型无线传感器网络及多机器人网络的应用中，受到节点体积，制造成本和能耗等限制，为所有节点安装全局定位装置如GPS是不实际的，只可能仅有少数节点配备全局定位装置。同时，由于节点的数量巨大以及节点的计算能力有限，让一个节点充当计算中心并获得其他所有节点的测量信息然后计算出节点的位置是不切实际的。因此，考虑使用分布式定位算法，节点只需与邻近节点进行测量和通信，就可以通过算法估计自己的位置，从而充分使用每个节点的计算能力。

到达角度(Angle-of-Arrival，AOA)信息是无线传感网络中最常用的测量信息之一，研究使用到达角度信息的分布式定位算法，在无线传感网络定位领域中具有重大的现实意义。

公开号为CN103841641A的中国专利提出了一种基于到达角度和Gossip算法的无线传感器网络分布式协作定位方法，该方法需要每个未知节点直接连接到多个锚节点(即安装有GPS的节点)。在大型无线传感器网络中，锚节点的数量可能很少，而且传感器网络覆盖区域大，每个节点的通信距离有限，所以每个未知节点不可能直接连接到多个锚节点。

此外，到达角度信息的数值依赖于每个节点自身的局部坐标系，目前的算法一般都假设每个节点配备类似指南针功能的设备，从而每个节点的局部坐标系有着相同的坐标轴方向。但在实际的环境中，存在磁场干扰等诸多因素，为 大型网络中的每个节点配备指南针是不现实的。

发明内容

针对现有技术所存在的上述技术问题，本发明提供了一种基于到达角度的分布式无线传感网络的节点定位方法，能够在每个节点的局部坐标系没有共同坐标轴方向的情况下，仍然能进行定位。

一种基于到达角度的分布式无线传感网络的节点定位方法，包括如下步骤：

(1)对于网络中未安装GPS的任一节点l，确定其邻居节点集合N_l并通过传感器测量节点l坐标系下每个邻居节点至节点l的到达角度；

(2)对于邻居节点集合N_l中的任一节点i，根据所述的到达角度计算节点i相对节点l的角度权重，同时使非邻居节点相对节点l的角度权重均设为0；

(3)根据步骤(1)～(2)遍历网络中所有未安装GPS的节点；对于网络中安装GPS的任一节点s，使其邻居节点或非邻居节点相对节点s的角度权重均设为0；进而根据得到的所有角度权重计算出网络的迭代步长ε；

(4)对于节点l，通过接收其邻居节点所提供的相关信息并根据迭代步长ε，基于以下迭代方程组求解出节点l自身的位置坐标值：

$\left(\begin{array}{c}{p}_l(t+1)=p_l\left(t\right)-ϵ\underset{i\in N_l}{\Sigma }{W}_{il}^{*}{\zeta }_l\left(t\right)+ϵ\underset{i\in N_l}{\Sigma }{W}_{il}^{*}{\zeta }_i\left(t\right)\\ {\zeta }_l(t+1)=-\underset{i\in N_l}{\Sigma }{W}_{li}[p_i\left(t\right)-p_l\left(t\right)]\end{array}\right)$

其中：p_l(t)和p_l(t+1)分别为第t次迭代和第t+1次迭代节点l的位置坐标值，ζ_l(t)和ζ_l(t+1)分别为第t次迭代和第t+1次迭代节点l的辅助变量，W_il为节点l相对节点i的角度权重，为W_il的共轭复数，W_li为节点i相对节点l的角度权重，p_i(t)和ζ_i(t)分别为第t次迭代节点i的位置坐标值和辅助变量，t为迭代次数；若节点i安装有GPS，则其各次迭代下的辅助变量均为0，其各次迭代下的位置坐标值均为其通过GPS测量得到的真实位置坐标数据。

所述的步骤(1)中确定邻居节点集合N_l的方法为：使网络中所有节点进行广播，若节点l收到节点i的广播数据包，则确定节点l与节点i互为邻居节点； 将节点l的所有邻居节点组成邻居节点集合N_l。

所述的步骤(2)中计算节点i相对节点l的角度权重，具体过程如下：

2.1从邻居节点集合N_l中找出所有关于节点i与l的三点邻居组合，所述的三点邻居组合包含节点l、节点i以及另外一个属于邻居节点集合N_l中的节点且这三个节点互为邻居节点；

2.2对于任一三点邻居组合，该组合包含节点l、节点i以及节点j；通过以下算式计算节点l相对节点j的旋转矢量v_jl：

$v_{jl}=\frac{b_{lj}^l}{b_{jl}^j}{e}^{\tau \pi }$

其中：为节点l坐标系下节点j至节点l的到达角度，为节点j坐标系下节点l至节点j的到达角度，τ为虚数单位；

2.3通过以下算式计算节点l坐标系下节点i至节点j的到达角度

$b_{ji}^l=v_{jl}{b}_{ji}^j$

其中：为节点j坐标系下节点i至节点j的到达角度；

2.4使参数q_l＝0，参数通过以下方程组求解出参数q_i：

$\left(\begin{array}{c}\mathrm{Re}\left({\mathrm{\tau b}}_{li}^l{\left(q_i-q_l\right)}^{*}\right)=0\\ \mathrm{Re}\left({\mathrm{\tau b}}_{ji}^l{\left(q_i-q_j\right)}^{*}\right)=0\end{array}\right)$

其中：为节点l坐标系下节点i至节点l的到达角度，Re()表示对()内复数取实部，()^*表示()内复数的共轭；

2.5通过以下公式计算节点j相对节点l的局部角度权重w_lj以及节点i相对节点l的局部角度权重w_li：

$\left(\begin{array}{cc}{w}_{lj}=\frac{e^{-{\mathrm{\tau \theta }}_{lj}}}{{\rho }_{lj}}& w_{li}=-\frac{e^{-{\mathrm{\tau \theta }}_{li}}}{{\rho }_{li}}\end{array}\right)$

其中：θ_lj和ρ_lj分别为(q_j-q_l)内复数的幅角和模，θ_li和ρ_li分别为(q_i-q_l)内复数的幅角和模；

2.6根据步骤2.2～2.5遍历所有三点邻居组合，得到N个关于节点i相对节点l的局部角度权重w_li，进而根据以下公式计算出节点i相对节点l的角度权重W_li：

$W_{li}=\frac{1}{N}{\Sigma }_{n=1}^N{w}_{li}^n$

其中：N为所有关于节点i与l三点邻居组合的种数，为在第n种三点邻居组合中节点i相对节点l的局部角度权重。

所述的步骤(3)中通过以下公式计算网络的迭代步长ε：

$ϵ=\frac{1}{{||H||}_1{||H||}_{\infty }}$

其中：||>1表示L1范数，||>∞表示无穷范数，H为角度权重矩阵。

所述角度权重矩阵H的表达式如下：

其中：W_pk为网络中第k节点相对第p节点的角度权重，第k节点相对其自身的角度权重W_kk＝0，p和k均为自然数且1≤p≤M，1≤k≤M，M为网络中所有节点的个数。

所述的步骤(4)中作为节点l邻居节点的节点i，其向节点l提供的相关信息包括角度权重W_il、位置坐标值p_i(t)和辅助变量ζ_i(t)。

所述的步骤(4)中当迭代收敛或达到最大迭代次数时的p_l(t)即输出作为节点l自身的位置坐标值。

与现有技术相比，本发明的优势在于：每个节点无需配备类似指南针的设备来统一局部坐标系的方向，这增加了算法适应场景的能力，在复杂的场景无 法配备指南针的时候仍然适用。同时本发明方法是线性的，计算简洁方便，并且具有指数收敛性质，收敛速度快，而且算法能保证全局收敛性，说明随机选取初始估计值的情况下不会陷入局部最优值，算法稳定性好；且本发明只需要两个锚节点，避免了大量安装GPS带来的高价格。

附图说明

图1为本发明方法的步骤流程示意图。

图2为无线传感网络的示意图。

图3为本发明定位算法下未知节点从初始估计值到最终估计值的轨迹示意图。

图4为本发明定位算法下未知节点结果关于归一化误差-算法迭代次数的关系曲线图。

具体实施方式

为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技术方案进行详细说明。

如图1所示，本发明基于到达角度的分布式无线传感网络的节点定位方法包括以下步骤：

步骤1，本实施例在80×80的仿真区域内分布8个传感器节点，如图2所示。其中，仿真区域的横向为X轴，纵向为Y轴，锚节点选取为A＝{1,2}，未知节点选取为S＝{3,4,5,6,7,8}，设定各个未知节点的初始位置。

步骤2，针对每个未知节点，确定该未知节点的邻居节点。根据测得的到达角度信息，计算距离权重，并根据角度权重确定迭代步长。

以未知节点l为例进行说明，其中l＝3,4,5,6,7,8。

所有传感器节点进行广播，若未知节点l能接收到节点i发送的广播数据包，则认为传感器节点i与未知节点l相邻，互为邻居节点。未知节点l通过配备的传感器可以感知邻居节点信号的到达方向，从而计算出每个邻居节点到自身的到达角信息。由此，未知节点l可以构建自身的邻居列表N_l。

未知节点l将任意两个邻居节点划分为一组，判断同一组中的邻居节点是否 互为邻居节点，若互为邻居节点，则利用如下方法计算未知节点l与该两个邻居节点的角度权重：

2.1计算局部坐标系的相对旋转。用复数p_l＝x_l+y_lτ来表示传感器节点l的位置，其中x_l和y_l分别代表横坐标和纵坐标。如果两个传感器节点l和j互为邻居，那么两个节点之间的相对旋转按下式计算：

$v_{jl}=\frac{b_{lj}^l}{b_{jl}^j}{e}^{\tau \pi }$

其中：是节点l对节点j的到达角度测量，上标l代表数值是在节点l的坐标系下的数值，即：

$b_{lj}^l=\frac{p_j^l-p_l^l}{\left|p_j^l-p_l^l\right|}$

2.2针对未知节点l及其两个邻居节点i和j，计算：

$b_{ji}^l=v_{jl}{b}_{ji}^j$

设置参数q_l＝0以及并从下列方程中解出q_i：

$\left(\begin{array}{c}\mathrm{Re}\left({\mathrm{\tau b}}_{li}^l{\left(q_i-q_l\right)}^{*}\right)=0\\ \mathrm{Re}\left({\mathrm{\tau b}}_{ji}^l{\left(q_i-q_j\right)}^{*}\right)=0\end{array}\right)$

其中：()^*表示()内复数的共轭，Re()表示对()内复数取实部。由此，未知节点l已经获得(q_l，q_i，q_j)，然后计算局部角度权重w_lj和w_li使得下式成立：

w_lj(q_j-q_l)+w_li(q_i-q_l)＝0

具体计算方法如下，令以及则角度权重按下式计算：

$\left(\begin{array}{cc}{w}_{lj}=\frac{e^{-{\mathrm{\tau \theta }}_{lj}}}{{\rho }_{lj}}& w_{li}=-\frac{e^{-{\mathrm{\tau \theta }}_{li}}}{{\rho }_{li}}\end{array}\right)$

2.3则选出所有可能的两个邻居节点的组合(即要求两个邻居节点也互为邻居)。并按照上述步骤计算和其中n代表可能的组合，最后按下式计算邻居节点i相对未知节点l的角度权重：

$W_{li}=\frac{1}{N}{\Sigma }_{n=1}^N{w}_{li}^n$

其中：N为所有可能组合的个数。

进而，通过如下公式确定迭代步长ε：

$ϵ=\frac{1}{{||H||}_1{||H||}_{\infty }}$

其中，H根据所有未知节点的角度权重计算得到，其表达式如下：

步骤3，开始执行迭代算法，直到各个未知节点连续10次的估计值波动不超过0.01。以此时的位置估计结果作为最终的定位结果。每次迭代时进行如下操作：

3.1所有传感器节点将自身当前位置估计值p_l(t)发送给所有邻居节点。对于锚节点，其估计值就为当前的GPS结果。每个未知节点将一个辅助变量ζ_l(t)乘以自身与一个邻居节点的角度权重后发给该邻居节点。未知节点l计算辅助变量的公式如下：

${\zeta }_l\left(t\right)=-\underset{i\in N_l}{\Sigma }{W}_{li}[p_i(t-1)-p_l(t-1)]$

其中：p_i(t-1)是邻居节点i的上个时刻自身位置估计值，W_li是未知节点l按步骤2计算的关于邻居节点i的角度权重。

3.2每个未知节点根据接收到的邻居节点发送的位置估计值和辅助变量信息。迭代更新自己的估计值和辅助变量，更新公式如下：

$\left(\begin{array}{c}{p}_l(t+1)=p_l\left(t\right)-ϵ\underset{i\in N_l}{\Sigma }{W}_{il}^{*}{\zeta }_l\left(t\right)+ϵ\underset{i\in N_l}{\Sigma }{W}_{il}^{*}{\zeta }_i\left(t\right)\\ {\zeta }_l(t+1)=-\underset{i\in N_l}{\Sigma }{W}_{li}[p_i\left(t\right)-p_l\left(t\right)]\end{array}\right)$

其中：p_l(t)是未知节点l第t次迭代的位置估计结果，ζ_i(t)为邻居节点i第t次迭代的辅助变量，是邻居节点i计算的相对于l的角度权重W_il的共轭，t+1为本次迭代计算的次数。

图3为执行迭代算法时，未知节点的从初始估计值到最终坐标估计值的轨迹。两个锚节点的坐标取值为p₁＝(4,35)，p₂＝(43,47)；六个未知节点坐标准确值为p₃＝(36,76)，p₄＝(40,20)，p₅＝(20,72)，p₆＝(72,60)，p₇＝(69,37)，p₈＝(9,25)；迭代步长取值ε＝0.2003。

由图3可以看出，在无线传感网络中只存在两个锚节点的情况下，各未知节点对自身坐标的估计值能从任意初始位置(空心圆代表初始位置)收敛至实际的坐标值。

图4表示执行本迭代算法时的归一化误差-迭代次数关系曲线，归一化误差为每一次得到的定位结果的误差除以初始估计值的误差。从图4可以看出，误差指数收敛到0，收敛速度快。

上述的对实施例的描述是为便于本技术领域的普通技术人员能理解和应用本发明。熟悉本领域技术的人员显然可以容易地对上述实施例做出各种修改，并把在此说明的一般原理应用到其他实施例中而不必经过创造性的劳动。因此，本发明不限于上述实施例，本领域技术人员根据本发明的揭示，对于本发明做出的改进和修改都应该在本发明的保护范围之内。