一种基于单移动机器人的分布式无线传感网络节点定位方法

摘要

本发明公开了一种基于单移动机器人的分布式无线传感网络节点定位方法，其利用单个配备GPS的移动机器人辅助无线传感器网络进行定位，移动机器人在无线传感器网络内最少只需要进行三次广播即可；每个未知节点不需要能直接测量到机器人，只需要和邻居节点进行通信就可以进行定位，网络拓扑连接更加灵活。同时本发明方法不需要全局信息，每个未知节点仅仅需要和邻居节点通信即可，算法具有指数收敛性质，收敛速度快，而且是全局收敛，不会陷入局部最优值。

说明书

技术领域

本发明属于无线传感网络技术领域，具体涉及一种基于单移动机器人的分布式无线传感网络节点定位方法。

背景技术

在无线传感器网络应用中，传感器节点的位置信息在军事监控，目标跟踪，地理探索等应用中起到至关重要的作用。

在大规模无线传感器网络中，无线传感器节点受到节点体积，制造成本和电能消耗等限制，一般都不安装全局定位装置如GPS。为了定位传感器节点，派遣一个装备GPS的移动机器人到无线传感器网络所在区域，并基于节点间通信和节点与移动机器人间的通信设计算法使传感器节点可以估计出自己的位置。由于节点的数量巨大以及单个节点计算能力的不足，让一个节点充当计算中心并获得其他所有节点的测量信息的方法费时费力。因此，采用分布式定位算法，传感器节点只需与邻近节点进行通信，就可以通过设计的算法估计出自己的位置，从而充分使用每个节点的计算能力。

距离信息是无线传感网络中最常用的测量信息之一，研究使用距离信息的分布式定位算法，在无线传感器网络定位领域中具有重要的现实意义。公开号为CN104159295A的中国专利申请提出了一种利用距离测量进行定位的方法，但是需要每个待定位节点都能找到至少三个锚节点作为邻居节点，但是当无线传感器网络中存在很少的锚节点时，此方法便不起作用，而且大量的锚节点需要很多GPS，需要更多的造价。

此外，现有使用重心坐标进行分布式定位的算法，在有误差存在的时候无法有效判断重心坐标符号位。然而距离测量误差是实用中必须要考虑的问题，所以现有方法具有很大局限性。

发明内容

针对现有技术所存在的上述技术问题，本发明提供了一种基于单移动机器人的分布式无线传感网络节点定位方法，其针对没有配备GPS的无线传感器网络节点，派遣带有GPS的移动机器人到传感器网络区域，每个未知节点不需要能直接测量到机器人，只需要和邻居节点进行通信就可以进行定位。

一种基于单移动机器人的分布式无线传感网络节点定位方法，包括如下步骤：

(1)派遣一安装有GPS的移动机器人行至网络区域中任一位置并广播自身的GPS信息，进而随意行至另一位置再次进行广播；依此执行该操作若干次，使移动机器人每次广播GPS信息的位置即作为一个虚拟节点且虚拟节点已知其自身的位置信息；

(2)对于网络中的任一传感器节点l，确定其邻居节点集合N_l并通过信号收发装置RSSI(接收信号强度指示)测量每个邻居节点至传感器节点l的距离；

(3)对于邻居节点集合N_l中的任一节点i，根据其至传感器节点l的距离计算节点i相对传感器节点l的距离权重，同时使非邻居节点相对传感器节点l的距离权重均设为0；

(4)根据步骤(2)～(3)遍历网络中所有传感器节点，进而根据得到的所有距离权重计算出网络的迭代步长ε；

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

$\left(\begin{array}{c}{p}_l(t+1)=p_l\left(t\right)-{\mathrm{ϵ\zeta }}_l\left(t\right)+ϵ\underset{i\in N_l}{\Sigma }{A}_{il}{\zeta }_i\left(t\right)\\ {\zeta }_l(t+1)=p_l\left(t\right)-\underset{i\in N_l}{\Sigma }{A}_{li}{p}_i\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的辅助变量，A_il为传感器节点l相对节点i的距离权重，若节点i为虚拟节点则A_il＝0；A_li为节点i相对传感器节点l的距离权重，p_i(t)和ζ_i(t)分别为第t次迭代节点i的位置坐标值和辅助变量，t为迭代次数；若节点i为虚拟节点，则其各次迭代 下的辅助变量均为0，其各次迭代下的位置坐标值均为移动机器人在该虚拟节点处通过GPS测量得到的真实位置坐标数据。

所述的步骤(1)中移动机器人在网络区域中广播GPS信息的操作过程所得到的虚拟节点个数至少需要三个。

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

所述的步骤(3)中计算节点i相对传感器节点l的距离权重，具体过程如下：

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

3.2对于任一三点邻居组合，该组合包含节点i、j和k；通过求解以下优化目标得到节点i、j和k所对应的坐标向量q_i、q_j和q_k；

$\underset{q_i,q_j,q_k}{min}\underset{d_{ab}=d_{li},d_{lj},d_{lk},d_{ij},d_{jk},d_{ki}}{\Sigma }{\left(\right||q_a-q_b|{|}^2-{\left(d_{ab}\right)}^2)}^2$

s.t.q_l＝[0,0]^T>iy＝0>jy＞0

其中：q_l为传感器节点l的坐标向量，q_i＝[q_ix,q_iy]^T，q_j＝[q_jx,q_jy]^T，q_k＝[q_kx,q_ky]^T，^T表示转置；q_ix和q_iy分别为坐标向量q_i的x轴分量和y轴分量，q_jx和q_jy分别为坐标向量q_j的x轴分量和y轴分量，q_kx和q_ky分别为坐标向量q_k的x轴分量和y轴分量，d_li、d_lj和d_lk分别为节点i、j和k至传感器节点l的距离，d_ij为节点j至节点i的距离，d_jk为节点k至节点j的距离，d_ki为节点i至节点k的距离；若d_ab＝d_li，则q_a＝q_l，q_b＝q_i，依此类推；

3.3根据坐标向量q_l、q_i、q_j和q_k通过以下公式计算出节点i相对传感器节点l的局部距离权重a_li、节点j相对传感器节点l的局部距离权重a_lj以及节点k相对传感器节点l的局部距离权重a_lk：

$a_{li}=\frac{S_{ljk}}{S_{ijk}},a_{lj}=\frac{S_{lki}}{S_{ijk}},a_{lk}=\frac{S_{lij}}{S_{ijk}}$

$S_{ljk}=\frac{1}{2}\left(\begin{array}{ccc}{q}_l& q_j& q_k\\ 1& 1& 1\end{array}\right),S_{lki}=\frac{1}{2}\left(\begin{array}{ccc}{q}_l& q_k& q_i\\ 1& 1& 1\end{array}\right)$

$S_{lij}=\frac{1}{2}\left(\begin{array}{ccc}{q}_l& q_i& q_j\\ 1& 1& 1\end{array}\right),S_{ijk}=\frac{1}{2}\left(\begin{array}{ccc}{q}_i& q_j& q_k\\ 1& 1& 1\end{array}\right)$

其中：S_ljk、S_lki、S_lij和S_ijk均为中间变量；

3.4根据步骤3.2～3.3遍历所有三点邻居组合，得到N个关于节点i相对传感器节点l的局部距离权重a_li，进而根据以下公式计算出节点i相对传感器节点l的距离权重A_li：

$A_{li}=\frac{1}{N}\underset{n=1}{\overset{N}{\Sigma }}{a}_{li}^n$

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

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

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

其中：||||₁表示L1范数，||||_∞表示无穷范数，H为距离权重矩阵。

所述距离权重矩阵H的表达式如下：

其中：A_pk为网络中第k传感器节点相对第p传感器节点的距离权重，第k传感器节点相对其自身的距离权重A_kk＝0，p和k均为自然数且1≤p≤M，1≤k≤M，M为网络中所有传感器节点的个数。

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

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

与现有技术相比，本发明利用单个配备GPS的移动机器人辅助无线传感器网络进行定位，移动机器人在无线传感器网络内最少只需要进行三次广播即可；每个未知节点不需要能直接测量到机器人，只需要和邻居节点进行通信就可以进行定位，网络拓扑连接更加灵活。同时本发明方法不需要全局信息，每个未知节点仅仅需要和邻居节点通信即可，算法具有指数收敛性质，收敛速度快，而且是全局收敛，不会陷入局部最优值。

附图说明

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

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

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

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

具体实施方式

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

如图1所示，本发明基于单移动机器人的分布式无线传感网络节点定位方法包括以下步骤：

步骤1，本实施例在80×80的仿真区域内分布5个传感器节点，派遣装备GPS的移动机器人到无线传感器网络区域广播GPS数据，一共在3个地点广播。移动机器人广播GPS的地点记为{O₁,O₂,O₃}，传感器节点记为{1,2,3,4,5}。

步骤2，所有传感器节点进行首次广播，若传感器节点l能接收到节点i发送的广播数据包，则认为传感器节点l与节点i互为邻居节点。每个传感器节点通过RSSI可以获得每个邻居节点到自身的距离信息。网络拓扑如图2所示。

步骤3，根据距离测量计算传感器节点相对于其邻居节点的重心坐标，并确定迭代步长。

以传感器节点l为例进行说明，其中l＝1,2,3,4,5：

步骤3-1，判断其任意三个邻居节点是否互为邻居节点，若互为邻居节点，则利用如下方法计算相对于该三个邻居节点的距离权重，即重心坐标。针对未知节点l及其三个邻居节点i、j和k。用d_li、d_lj、d_lk、d_ij、d_jk和d_ki表示测量到的距离。解如下最优化问题，获得q_l、q_i、q_j和q_k；

$\underset{q_i,q_j,q_k}{min}\underset{d_{ab}=d_{li},d_{lj},d_{lk},d_{ij},d_{jk},d_{ki}}{\Sigma }{\left(\right||q_a-q_b|{|}^2-{\left(d_{ab}\right)}^2)}^2$

s.t.q_l＝[0,0]^T>iy＝0>jy＞0

其中，q_i＝[q_ix,q_iy]^T，q_j＝[q_jx,q_jy]^T，q_k＝[q_kx,q_ky]^T。

步骤3-2，获得q_l、q_i、q_j和q_k后，按照下面公式计算重心坐标{a_li,a_lj,a_lk}：

$a_{li}=\frac{S_{ljk}}{S_{ijk}},a_{lj}=\frac{S_{lki}}{S_{ijk}},a_{lk}=\frac{S_{lij}}{S_{ijk}}$

$S_{ljk}=\frac{1}{2}\left(\begin{array}{ccc}{q}_l& q_j& q_k\\ 1& 1& 1\end{array}\right),S_{lki}=\frac{1}{2}\left(\begin{array}{ccc}{q}_l& q_k& q_i\\ 1& 1& 1\end{array}\right)$

$S_{lij}=\frac{1}{2}\left(\begin{array}{ccc}{q}_l& q_i& q_j\\ 1& 1& 1\end{array}\right),S_{ijk}=\frac{1}{2}\left(\begin{array}{ccc}{q}_i& q_j& q_k\\ 1& 1& 1\end{array}\right)$

步骤3-3，将S1-1中选出的每一组组合按照上述步骤计算和其中n代表可能的组合，最后按下式计算邻居节点i相对于传感器节点l的距离权重：

$A_{li}=\frac{1}{N}\underset{n=1}{\overset{N}{\Sigma }}{a}_{li}^n$

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

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

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

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

步骤4，开始执行迭代算法，设置执行时间为80秒。对位置估计值设置一个初始值，传感器节点按下述方法迭代更新。

步骤4-1，所有传感器节点将自身当前位置估计值p_l(t)发送给所有邻居节点。每个传感器节点任意选择一个数值作为初始估计值。同时针对每个邻居节点，每个传感器节点将一个辅助变量ζ_l(t)乘以自身与该邻居节点的距离权重后发给该邻居节点。传感器节点l计算辅助变量的公式如下，

${\zeta }_l\left(t\right)=p_l(t-1)-\underset{i\in N_l}{\Sigma }{A}_{li}{p}_i(t-1)$

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

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

$\left(\begin{array}{c}{p}_l(t+1)=p_l\left(t\right)-{\mathrm{ϵ\zeta }}_l\left(t\right)+ϵ\underset{i\in N_l}{\Sigma }{A}_{il}{\zeta }_i\left(t\right)\\ {\zeta }_l(t+1)=p_l\left(t\right)-\underset{i\in N_l}{\Sigma }{A}_{li}{p}_i\left(t\right)\end{array}\right)$

其中，p_l(t)是第t次迭代的估计结果，ζ_i(t)为邻居节点i的第t次迭代的辅助变量；t+1为本次迭代计算的次数。如果到80秒，停止迭代，以此时的数值作为位置估计值，如果没有到80秒，进行下一步。

步骤5：如果传感器节点收到了机器人发出的新的数据，说明邻居列表增加了一个邻居，回到步骤2。否则继续按照步骤4迭代更新。

图3为执行迭代算法时，未知节点的从初始估计值到最终坐标估计值的轨迹。三个广播点的坐标为O₁＝(24,22)，O₂＝(38,40)，O₃＝(60,35)。五个传感器节点坐标准确值为p₁＝(14,60)，p₂＝(4,30)，p₃＝(42,3)，p₄＝(78,44)，p₅＝(62,90)。

由图3可以看出，在测量误差存在的情况下，各个传感器节点对自身坐标的估计值能从任意初始位置(空心圆代表初始位置)收敛至实际的坐标值的附近。

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

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