CN113347707B - 一种基于加权迭代和双重选择的DV-Hop节点定位方法 - Google Patents

Abstract

本发明提出了一种基于加权迭代和双重选择的DV‑Hop节点定位方法，步骤为：首先，利用加权方式迭代的计算锚节点的平均跳距，并比较每次求得的平均跳距误差，以误差最小时的平均跳距作为锚节点的最优平均跳距；然后，减少标准DV‑Hop中的计算步骤，利用锚节点的最优平均跳距来求取未知节点与锚节点间的估计距离；最后，根据锚节点距离未知节点的远近，对锚节点进行分组，并通过变换参考节点来消除最小二乘法的潜在误差。计算每个锚节点组的最优未知节点坐标，然后选取误差最小的坐标作为未知节点的最终坐标。本发明能够提高锚节点平均跳距和未知节点到锚节点距离的准确度，且具有较好的节点定位精度和定位稳定性。

Description

一种基于加权迭代和双重选择的DV-Hop节点定位方法

技术领域

本发明涉及无线传感器网络中节点定位的技术领域，尤其涉及一种基于加权迭代和双重选择的DV-Hop节点定位方法。

背景技术

无线传感器网络(WSNs)作为一种全新的信息获取和处理技术，目前已被广泛应用于众多领域，例如：军事侦察、医疗卫生、城市交通、精准农业和森林火灾监测等方面。对于无线传感器网络的应用，大都需要知道事件发生的具体位置，以便做出相应的处理。因此，获取传感器节点的精确位置信息具有十分重要的研究意义。

对节点定位技术的研究方向主要可以分为两类：基于测距的定位方法和基于非测距的定位方法。常见的测距定位方法包括：到达时间差(TDOA)、接收信号的强度(RSSI)、到达时间(TOA)等。基于测距的定位方法具有较高的定位精度，但由于需要额外硬件测量节点间的角度、距离、信号强度等，增加了搭建网络的开销。DV-Hop定位方法作为典型的非测距定位方法之一，未知节点通过其平均跳距与到锚节点的最小跳数来计算节点间的估计距离，然后通过多边定位法或极大似然估计法计算未知节点的位置坐标。然而，由于网络的复杂性和算法本身的限制，DV-Hop定位方法具有较低的定位精度，限制了一些对节点精度要求较高的场景的应用。

标准的DV-Hop定位方法采用无偏估计方法计算锚节点的平均跳距，该方法得到的结果通常与真实网络中的平均跳距存在较大的误差(参考文献[1]算法)。Chen等考虑到误差的分布规律，提出一种基于最小均方误差准则的方法来计算锚节点的平均跳距(参考文献[2]算法)，该方法虽然一定程度上提高了锚节点的平均跳距精度，但并未考虑到锚节点间的相互影响程度。在标准DV-Hop定位方法中未知节点仅参考最近的锚节点的平均跳距作为自身的平均跳距，并不能反映出未知节点的真实平均跳距。Zhao等引入权重因子对锚节点的平均跳距进行加权，未知节点的平均跳距以距离其最近的三个锚节点的平均跳距加权求得(参考文献[3]算法)，该方法考虑到了不同锚节点的平均跳距对未知节点平均跳距的贡献度问题，但对于一些特殊网络结构而言，仅参考最近的三个锚节点并不能反映出未知节点在网络中的真实平均跳距。为了提高未知节点与锚节点之间的距离的准确度，Li等采用一种双通信半径的方式计算节点之间的跳数，细化了节点间的通信半径，一定程度上提高了未知节点的定位精度(参考文献[4]算法)，但由于需要二次广播通信半径，增加了传感器节点的能量消耗，降低了节点的使用寿命。

目前的DV-Hop定位方法采用各种不同方案提高了锚节点的平均跳距的精度，但并未考虑到锚节点之间的相互影响，不同的锚节点对平均跳距的求取应当具有不同的贡献度。同时，在计算未知节点的坐标时，所有的锚节点都参与了计算过程，但如果某个锚节点到未知节点的距离误差较大，将会影响到定位结果。此外，采用最小二乘法求解未知节点坐标时，方程组所产生的潜在误差未能消除。

发明内容

针对现有DV-Hop定位方法定位精度低，利用最小二乘法求解未知节点坐标时未能消除潜在误差的技术问题，本发明提出一种基于加权迭代和双重选择的DV-Hop节点定位方法，采用加权迭代的方式求取锚节点的最优平均跳距，并利用双重选择策略获取未知节点的坐标，降低了锚节点平均跳距的误差和节点间的距离误差，进一步提高了未知节点坐标的精度，提高了定位精度。

为了达到上述目的，本发明的技术方案是这样实现的：一种基于加权迭代和双重选择的DV-Hop节点定位方法，其步骤如下：

步骤一：采用加权迭代策略计算锚节点的最优平均跳距：首先利用最小均方误差准则求取锚节点的初始平均跳距，然后计算锚节点到其他锚节点每一跳的误差值；并将误差值作为锚节点的权重系数，利用加权后的最小均方误差准则重新计算锚节点的平均跳距；比较每次加权迭代后得到的锚节点平均跳距的误差，如果本次迭代求得的锚节点平均跳距的误差小于上次的误差，则继续迭代；否则，迭代结束，将上次求得锚节点的平均跳距作为锚节点的最优平均跳距；

步骤二：利用步骤一得到的锚节点的最优平均跳距计算未知节点与锚节点之间的估计距离；

步骤三：采用双重选择方案求取未知节点的坐标：依据不同锚节点到未知节点的距离远近，对锚节点进行分组，并将锚节点组内的每个锚节点分别作为一次参考节点，利用最小二乘法计算未知节点的坐标，从中选取误差最小的坐标作为锚节点组的最优未知节点坐标；最后，比较不同锚节点组求得的最优坐标误差的大小，选取误差最小的坐标作为未知节点的最终坐标。

所述步骤一中采用加权迭代策略计算锚节点的最优平均跳距的方法为：

步骤1：网络的初始化：所有锚节点采用泛洪的方式向网络中广播数据包，接收节点通过更改跳数值和传递数据包，获得网络中节点间的最小跳数；

步骤2：对所有锚节点赋予相同的权值，利用最小跳数和最小均方误差准则求取每个锚节点的初始平均跳距：

其中，AHD_i ^init为锚节点i的初始平均跳距，Dis_ij表示锚节点i和锚节点j之间的实际距离，Hop_ij代表锚节点i到锚节点j的最小跳数，n为网络中锚节点的总数目；

步骤3：利用步骤2计算的初始平均跳矩，计算锚节点的初始平均跳距的误差：

其中，η_i ^init代表锚节点i的初始平均跳距的误差，AHD_i ^init·Hop_ij为锚节点i到锚节点j的估计距离；

步骤4：利用步骤2得到的锚节点平均跳距AHD_i ^init计算锚节点之间的估计距离，参考锚节点之间的实际距离和最小跳数计算锚节点间每跳的误差值：

其中，EH_ij表示锚节点i到锚节点j的每一跳的误差值；

步骤5：利用锚节点间每跳的误差值对相应的锚节点赋予权值：

其中，α_ij表示在计算锚节点i的平均跳距时，对锚节点j赋予的权值；

步骤6：利用步骤5中得到的锚节点之间的权值，通过加权最小均方误差准则计算加权后的锚节点平均跳距：

其中，AHD_i ^(m)为第m次加权迭代后求得的锚节点i的平均跳距；

步骤7：根据步骤6得到的加权后的锚节点平均跳距，计算加权后求得的锚节点平均跳距的误差：

其中，η_i ^(m)表示第m次加权迭代后得到的锚节点i的平均跳距的误差；

步骤8：若当前加权迭代次数m＝1，比较第一次加权后求得的锚节点平均跳距的误差η_i ⁽¹⁾和锚节点的初始平均跳距的误差η_i ^init的大小，如果η_i ⁽¹⁾<η_i ^init，则继续对锚节点的平均跳距加权迭代求解，返回到步骤4，利用当前迭代得到的锚节点平均跳距AHD_i ⁽¹⁾作为步骤4中的初始平均跳距AHD_i ^init，重新计算锚节点间的每跳误差，并以每跳的误差值作为权值再次迭代计算锚节点的平均跳距；如果η_i ⁽¹⁾>η_i ^init，结束迭代计算过程，以步骤2求得的初始平均跳距AHD_i ^init作为锚节点i的最优平均跳；

若当前加权迭代次数m>1，比较第m-1次加权后求得的锚节点平均跳距的误差η_i ^(m-1)和当前迭代求得的锚节点平均跳距的误差η_i ^(m)的大小，如果η_i ^(m)<η_i ^(m-1)，则继续对锚节点的平均跳距加权迭代求解，返回到步骤4，利用当前迭代加权得到的AHD_i ^(m)作为步骤4中的初始平均跳距AHD_i ^init，重新计算锚节点间的每跳误差，并以每跳的误差值作为权值再次迭代计算锚节点的平均跳距；如果η_i ^(m)>η_i ^(m-1)，结束迭代计算过程，以上次迭代求得的锚节点平均跳距AHD_i ^(m-1)作为锚节点i的最优平均跳距。

所述步骤二中未知节点到锚节点的估计距离的计算方法为：d_ui＝AHD_i ^best·Hop_ui；

其中，d_ui为未知节点u到锚节点i的估计距离，AHD_i ^best代表锚节点i的最优平均跳距；Hop_ui表示未知节点u到锚节点i的最小跳数，且u＝1,...,N，N为网络中未知节点总数。

所述步骤三中采用双重选择策略获取未知节点的坐标的步骤为：

S1：利用不同锚节点到未知节点距离的远近，由于对未知节点定位至少需要三个锚节点，将锚节点分为n-2个不同的锚节点组即锚节点集合ANSET_＜k＞，k＝3,…,n；其中，ANSET_＜k＞代表距离未知节点最近的k个锚节点；

S2：将锚节点集合ANSET_＜k＞中的每个锚节点都作为一次参考锚节点计算未知节点的坐标；

S3：根据步骤二计算的未知节点与锚节点之间的估计距离，利用最小二乘法和锚节点集合ANSET_＜k＞内的锚节点分别计算相应的未知节点候选坐标(x_u,y_u)，且u＝1,...,k；

S4：根据未知节点的坐标和锚节点的坐标，计算每个未知节点候选坐标的误差：

其中，(x_u,y_u)代表未知节点u的估计坐标，(x_i,y_i)代表锚节点i的坐标；

S5：比较每个锚节点集合ANSET_＜k＞求得的候选坐标误差的大小，将具有最小误差的候选坐标作为该锚节点集合求得的最优候选坐标；

S6：比较不同锚节点集合下求得的最优候选坐标误差的大小，选取误差最小的最优候选坐标作为未知节点的最终坐标。

所述步骤S3中最小二乘法计算未知节点的候选坐标(x_u,y_u)的步骤为：

S31：获取未知节点到每个锚节点的估计距离：

设未知节点的坐标为(x_u,y_u)，锚节点的坐标为(x_i,y_i),i＝1,2,…,k，未知节点到锚节点集合ANSET_＜k＞内锚节点的估计距离分别为d_u1,d_u2,…,d_uk，则有如下的方程组：

S32：将非线性方程组转化为线性方程组求解未知节点的坐标：

S33：将线性方程组表达成GX＝H的矩阵形式，其中：

利用最小二乘法求解未知节点的坐标为：

X＝(G^TG)^-1G^TH；

其中，G、H为步骤S32中线性方程组的矩阵表示形式，X表示求得的未知节点的坐标。

与现有技术相比，本发明的有益效果：利用基于最小均方误差准则的方法求得锚节点的初始平均跳距，然后计算出锚节点到其他锚节点每一跳的误差，并以此作为权重因子，对每个锚节点赋予不同的权值，然后采用基于加权的最小均方误差准则计算锚节点的平均跳距；利用锚节点间真实距离与估计距离的差值作为锚节点平均跳距的误差的评价指标，比较本次求得的平均跳距误差与上次求得的平均跳距误差的大小，如果小于上次，继续加权迭代计算，否则，以上次得到的平均跳距作为锚节点的最优平均跳距。本发明采用锚节点的最优平均跳距来计算未知节点与锚节点之间的估计距离，不仅能够降低节点间距离的误差，而且减少了标准DV-Hop定位方法中广播锚节点平均跳距的过程，减少了节点的能量消耗。本发明采用双重选择策略获取未知节点的位置坐标，考虑到锚节点距离未知节点的远近，将锚节点分为不同的锚节点集，同时使锚节点集内的每个锚节点都作为一次参考锚节点，能够有效降低方程组的潜在误差，提高节点的定位精度。最后，经过仿真实验表明，本发明在求取未知节点坐标的每一步都具有较高的精度，不仅降低了计算过程中误差的积累，而且定位精度和稳定性也得到了明显改善。本发明能够提高锚节点平均跳距和未知节点到锚节点距离的准确度，且具有较好的节点定位精度和定位稳定性。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明的流程图。

图2为本发明加权迭代策略计算锚节点最优平均跳距的流程图。

图3为本发明与对比算法的锚节点平均跳距计算精度的对比图。

图4为本发明与对比算法的未知节点到锚节点距离精度的对比图。

图5为本发明与对比算法的不同节点总数下未知节点定位精度的对比图。

图6为本发明与对比算法的不同锚节点比例下未知节点定位精度的对比图。

图7为本发明与对比算法的不同通信半径下未知节点定位精度的对比图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

一种基于加权迭代和双重选择的DV-Hop节点定位方法，其构思是：采用了对锚节点平均跳距加权迭代的方式，利用初始锚节点平均跳距计算锚节点到其他锚节点每一跳的误差，并将误差值作为权重系数，对每个锚节点赋予不同权值，然后采用加权的最小均方误差准则计算锚节点的平均跳距。如果本次求得平均跳距误差小于上次，继续迭代计算；否则，将上次求得的平均跳距作为锚节点的最优平均跳距。然后，减少了标准DV-Hop方法的计算过程，以锚节点的最优平均跳距求取节点间的估计距离。最后，采用双重选择策略求取未知节点的最终坐标。本发明考虑到了锚节点之间的相互影响，通过加权迭代策略得到的平均跳距更加接近网络中的真实平均跳距。同时，减少标准DV-Hop定位方法的计算步骤和采用双重选择策略计算坐标，不仅能够有效延长传感器节点的使用寿命，而且能够提高节点的定位精度。

如图1所示，本发明在利用泛洪方式得到锚节点间的最小跳数后，采用了加权迭代策略计算每个锚节点的最优平均跳距，然后参考上一步求得的相对精确的锚节点的最优平均跳距来计算其与未知节点的距离，最后利用双重选择策略来选取误差最小的候选坐标作为未知节点的最终坐标，其具体步骤为：

步骤一：采用加权迭代策略计算锚节点的最优平均跳距：首先利用最小均方误差准则求取锚节点的初始平均跳距，然后计算锚节点到其他锚节点每一跳的误差值；并将误差值作为锚节点的权重系数，利用加权后的最小均方误差准则重新计算锚节点的平均跳距；比较每次加权迭代后得到的锚节点平均跳距的误差，如果本次迭代求得的锚节点平均跳距误差小于上次的误差，则继续迭代计算过程；否则，迭代结束，将上次求得的平均跳距作为锚节点的最优平均跳距。

如图2所示，加权迭代策略计算锚节点的平均跳距的流程图，其计算方法为：

步骤1：网络的初始化：所有锚节点采用泛洪的方式向网络中广播数据包，接收节点通过更改跳数值和传递数据包，以此来获得网络中节点间的最小跳数。

该步骤对于网络的初始化与标准DV-Hop方法相同，首先锚节点通过泛洪方式向网络中广播数据包(包括锚节点的编号、坐标和初始值为0的跳数值)，接收节点收到数据包后判断是否收到过来自同一锚节点的数据包，若收到过，则比较新收到的数据包的跳数值与已记录的跳数值的大小。若小于记录的跳数值，则修改记录的跳数值为较小者，并将数据包传递给其他邻居节点；否则，丢弃该数据包。通过此方式，网络中的节点都可获得到其他节点的最小跳数的值。

步骤2：对所有锚节点赋予相同的权值，利用最小均方误差准则求取每个锚节点的初始平均跳距：

其中，AHD_i ^init为锚节点i的初始平均跳距，Dis_ij表示锚节点i和锚节点j之间的实际距离，Hop_ij代表锚节点i到锚节点j的最小跳数，n为网络中锚节点的总数目。

假设所有锚节点之间的影响程度相同，对所有锚节点赋予相同的权重(权重值全设置为1)，利用最小误差准则可得到每个锚节点的初始平均跳距。而在实际网络中，由于节点是随机分布的，节点间的相互影响并不相同，所以应当对不同锚节点赋予不同的权值。锚节点的初始平均跳距可为后续权值的计算提供依据。

步骤3：利用步骤2计算的初始平均跳矩，计算锚节点的初始平均跳距的误差：

其中，η_i ^init代表锚节点i的初始平均跳距的误差，AHD_i ^init·Hop_ij为锚节点i到锚节点j的估计距离。

由于锚节点配有GPS装置，便可获取到锚节点的具体位置坐标，锚节点之间的真实距离为

可利用求得的锚节点平均跳距计算得到锚节点间的估计距离为：AHD_i ^init·Hop_ij，使其与真实距离相比较，便可得到锚节点平均跳距的误差即准确度。

步骤4：利用步骤2中得到的锚节点平均跳距AHD_i ^init计算锚节点之间的估计距离，参考锚节点之间的真实距离和最小跳数计算锚节点间每跳的误差值：

其中，EH_ij表示锚节点i到锚节点j的每一跳的误差值。

步骤5：利用锚节点间每跳的误差值对相应的锚节点赋予权值：

其中，α_ij表示在计算锚节点i的平均跳距时，对锚节点j赋予的权值。

将锚节点间的每一跳的误差值的倒数的平方作为权值，能够反映出每个锚节点对平均跳距的影响程度。如果到某个锚节点的每一跳的误差较大，则分配一个较小的权值，以此来削弱该锚节点对求取平均跳距结果的影响。与此相反，分配一个较大的权值。

步骤6：利用步骤5中得到的锚节点之间的权值，通过加权最小均方误差准则计算加权后的锚节点平均跳距：

其中，AHD_i ^(m)为第m次加权迭代后求得的锚节点i的平均跳距。

将权值作为加权系数，利用基于加权的最小均方误差准则方式计算锚节点平均跳距，考虑到了不同锚节点的贡献度，有助于提高锚节点平均跳距的精度。

步骤7：根据步骤6得到的加权后的锚节点平均跳距，计算加权后求得的锚节点平均跳距的误差：

其中，η_i ^(m)表示第m次加权迭代后得到的锚节点i的平均跳距的误差。

步骤8：若当前加权迭代次数m＝1，比较第一次加权后求得的锚节点平均跳距的误差η_i ⁽¹⁾和步骤3中求得的锚节点的初始平均跳距的误差η_i ^init的大小，如果η_i ⁽¹⁾<η_i ^init，则继续对锚节点的平均跳距加权迭代求解，返回到步骤4，利用当前迭代得到的AHD_i ⁽¹⁾作为步骤4中的锚节点平均跳距AHD_i ^init，重新计算锚节点间的每跳误差，并以每跳的误差值作为权值再次迭代计算锚节点的平均跳距；如果η_i ⁽¹⁾>η_i ^init，结束迭代计算过程，以步骤2中的求得的AHD_i ^init作为锚节点i的最优平均跳距(记为AHD_i ^best)。

本步骤的优势在于可通过比较第一次迭代得到的锚节点平均跳距的误差与初始锚节点平均跳距误差的大小，来判定是否需要继续迭代计算。

步骤9：若当前加权迭代次数m>1，比较第m-1次加权后求得的锚节点平均跳距的误差η_i ^(m-1)和当前迭代求得的锚节点平均跳距的误差η_i ^(m)的大小，如果η_i ^(m)<η_i ^(m-1)，则继续对锚节点的平均跳距加权迭代求解；返回到步骤4，利用当前迭代加权得到的AHD_i ^(m)作为步骤4中的锚节点平均跳距AHD_i ^init，重新计算锚节点间的每跳误差，并以每跳的误差值作为权值再次迭代计算锚节点的平均跳距；如果η_i ^(m)>η_i ^(m-1)，结束迭代计算过程，以上次迭代求得的AHD_i ^(m-1)作为锚节点i的最优平均跳距(记为AHD_i ^best)。

本发明利用最新求得的锚节点平均跳距重新计算权值分配，反复对锚节点平均跳距进行加权迭代计算，并比较每次求得的平均跳距的误差，能够得到每个锚节点的最优平均跳距。本发明采用的加权迭代方案，能够对锚节点的平均跳距迭代求精，使得到的平均跳距更加接近真实网络中的平均跳距，并能够有效降低定位过程中误差的积累。

步骤二：利用步骤一得到的锚节点的最优平均跳距计算未知节点与锚节点之间的估计距离。

未知节点到锚节点的估计距离的具体计算方法为：d_ui＝AHD_i ^best·Hop_ui；

其中，d_ui为未知节点u到锚节点i的估计距离，AHD_i ^best代表锚节点i的最优平均跳距。Hop_ui表示未知节点u到锚节点i的最小跳数。且u＝1,...,N，N为网络中未知节点总数。

本步骤的的优势在于减少了标准DV-Hop定位方法中未知节点的平均跳距的计算过程，并且锚节点求得最优平均跳距后也不需再次广播，降低了传感器节点的能量消耗，提高了节点的使用寿命。同时，利用锚节点的最优平均跳距求取估计距离，能够更加接近真实网络中的欧式距离。

步骤三：采用双重选择方案求取未知节点的坐标：依据不同锚节点到未知节点的距离远近，对锚节点进行分组，并将锚节点组内的每个锚节点分别作为一次参考节点，利用最小二乘法计算未知节点的坐标，从中选取误差最小的坐标作为锚节点组的最优未知节点坐标；最后，比较不同锚节点组求得的最优坐标误差的大小，选取误差最小的坐标作为未知节点的最终坐标。

所述采用双重选择策略获取未知节点的坐标的实施步骤为：

S1：利用不同锚节点到未知节点距离的远近，优先考虑将距离未知节点最近的锚节点参与计算。由于对未知节点定位至少需要三个锚节点，可将锚节点分为n-2个不同的锚节点集合，表示为ANSET_＜k＞，k＝3,…,n；其中，ANSET_＜k＞代表距离未知节点最近的k个锚节点。

由于距离未知节点越远的锚节点，其相应的最小跳数值越大，则未知节点到锚节点的估计距离存在较大误差的可能性也越大。如果定位过程中，存在距离误差较大的锚节点，将会影响到未知节点的坐标的精度。因此，优先将距离未知节点最近的锚节点参与定位，一定程度上能够降低误差产生的可能性。

S2：为了消除最小二乘法存在的固有误差，将锚节点集合ANSET_＜k＞中的每个锚节点都作为一次参考锚节点计算未知节点的坐标，若锚节点集合ANSET_＜k＞存有k个锚节点，则可以得到k个未知节点的候选坐标。

在利用最小二乘法求解方程组时，分别将其他方程减去最后一个方程，以此来将非线性方程组变成线性方程组。但如果最后一个方程的距离误差较大，则会影响到整个方程组的求解结果。因此，可让每个方程都作为一次最后一个方程，并从中选取最优解，这能够有效消除线性方程组所产生的潜在误差。

S3：根据步骤二计算的未知节点与锚节点之间的估计距离，利用最小二乘法和锚节点集合ANSET_＜k＞内的锚节点分别计算相应的未知节点候选坐标(x_u,y_u)，且u＝1,...,k。

利用最小二乘法计算未知节点的候选坐标(x_u,y_u)的步骤为：

S31：获取未知节点到每个锚节点的估计距离：

设未知节点的坐标为(x_u,y_u)，锚节点的坐标为(x_i,y_i),i＝1,2,…,k，未知节点到锚节点集合ANSET_＜k＞内锚节点的估计距离分别为d_u1,d_u2,…,d_uk，则有如下的方程组：

本步骤的优势在于能够将已有的锚节点信息和求得的估计距离联立起来，通过求解方程组来获得未知节点的坐标。

S32：将非线性方程组转化为线性方程组求解未知节点的坐标：

可将上述方程组表达成GX＝H的矩阵形式，其中：

最后，利用最小二乘法求解未知节点的坐标为：

X＝(G^TG)^-1G^TH；

其中，G、H分别为线性方程组的矩阵表示形式，X表示求得的未知节点坐标。计算得到的候选坐标作为未知节点最终坐标的备选之一。

本步骤的优势在于利用方程组相减能够将非线性方程组转化为线性方程组，再利用最小二乘法进行求解，简化了求解过程。

S4：根据未知节点的坐标和锚节点的坐标，计算每个未知节点候选坐标的误差：

其中，(x_u,y_u)代表未知节点u的估计坐标，(x_i,y_i)代表锚节点i的坐标，

为求得的未知节点候选坐标的误差。

利用候选坐标计算到每个锚节点的欧式距离，并与利用最优锚节点平均跳距求得的估计距离做比较，能够得到未知节点候选坐标的误差，便于获取未知节点的最佳候选坐标。

S5：比较每个锚节点集合下求得的候选坐标误差的大小，将具有最小误差的候选坐标作为该锚节点集合求得的最优候选坐标。

S6：比较不同锚节点集合下求得的最优候选坐标误差的大小，选取误差最小的最优候选坐标作为未知节点的最终坐标。

本发明首先，利用加权方式迭代的计算锚节点的平均跳距，并比较每次求得的平均跳距误差，以误差最小时的平均跳距作为锚节点的最优平均跳距；然后，减少标准DV-Hop中的计算步骤，利用锚节点的最优平均跳距来求取未知节点与锚节点间的估计距离；最后，根据锚节点距离未知节点的远近，对锚节点进行分组，并通过变换参考节点来消除最小二乘法的潜在误差，计算每个锚节点组的最优未知节点坐标，然后选取误差最小的坐标作为未知节点的最终坐标。

按照本发明的方法，100个传感器节点随机的分布在100m×100m的区域中，网络中锚节点总数保持为30个不变，未知节点总数为70个，节点的最大通信半径为30m；为了避免仿真结果的偶然性，所有的实验结果为相同实验条件下500次结果的均值。

图3为锚节点平均跳距精度的对比图。参考文献[2]基于最小均方误差准则求得结果优于参考文献[1]中的标准DV-Hop方法，而本发明采用加权迭代方案得到的锚节点平均跳距精度优于参考文献[1]和参考文献[2]中得到的结果。

图4为未知节点到锚节点距离精度的对比图。参考文献[3]通过对锚节点平均跳距加权得到的结果优于参考文献[1]中的标准DV-Hop方法，而本发明所设计的距离计算方法得到的结果最准确。

图5为不同节点总数下未知节点定位精度的比较图。仿真实验条件中节点总数不断变化，其他条件保持不变。结果表明本发明在不同节点总数下仍具有较高的定位精度。

图6为不同锚节点总数下未知节点定位精度的比较图。仿真实验条件中锚节点总数不断变化，其他条件保持不变。本发明求得的定位精度远优于参考文献[1]和参考文献[4]中的方法。

图7为不同通信半径下未知节点定位精度的比较图。仿真实验条件中节点的通信半径不断变化，其他条件保持不变。本发明得到的未知节点坐标的精度仍具有相对较高的优势，更加接近未知节点的真实坐标。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (5)

1.一种基于加权迭代和双重选择的DV-Hop节点定位方法，其特征在于，其步骤如下：

步骤一：采用加权迭代策略计算锚节点的最优平均跳距：首先利用最小均方误差准则求取锚节点的初始平均跳距，然后计算锚节点到其他锚节点每一跳的误差值；并将误差值作为锚节点的权重系数，利用加权后的最小均方误差准则重新计算锚节点的平均跳距；比较每次加权迭代后得到的锚节点平均跳距的误差，如果本次迭代求得的锚节点平均跳距的误差小于上次的误差，则继续迭代；否则，迭代结束，将上次求得锚节点的平均跳距作为锚节点的最优平均跳距；

在计算锚节点i的平均跳距时，对锚节点j赋予的权值为：

其中，EH_ij表示锚节点i到锚节点j的每一跳的误差值；

步骤二：利用步骤一得到的锚节点的最优平均跳距计算未知节点与锚节点之间的估计距离；

步骤三：采用双重选择方案求取未知节点的坐标：依据不同锚节点到未知节点的距离远近，对锚节点进行分组，并将锚节点组内的每个锚节点分别作为一次参考节点，利用最小二乘法计算未知节点的坐标，从中选取误差最小的坐标作为锚节点组的最优未知节点坐标；最后，比较不同锚节点组求得的最优坐标误差的大小，选取误差最小的坐标作为未知节点的最终坐标；

所述分组中优先将距离未知节点最近的锚节点参与定位，将锚节点分为n-2个不同的锚节点组即锚节点集合ANSET_＜k＞，k＝3,…,n；其中，ANSET_＜k＞代表距离未知节点最近的k个锚节点；n为网络中锚节点的总数目。

2.根据权利要求1所述的基于加权迭代和双重选择的DV-Hop节点定位方法，其特征在于，所述步骤一中采用加权迭代策略计算锚节点的最优平均跳距的方法为：

步骤1：网络的初始化：所有锚节点采用泛洪的方式向网络中广播数据包，接收节点通过更改跳数值和传递数据包，获得网络中节点间的最小跳数；

步骤2：对所有锚节点赋予相同的权值，利用最小跳数和最小均方误差准则求取每个锚节点的初始平均跳距：

其中，AHD_i ^init为锚节点i的初始平均跳距，Dis_ij表示锚节点i和锚节点j之间的实际距离，Hop_ij代表锚节点i到锚节点j的最小跳数，n为网络中锚节点的总数目；

步骤3：利用步骤2计算的初始平均跳矩，计算锚节点的初始平均跳距的误差：

其中，η_i ^init代表锚节点i的初始平均跳距的误差，AHD_i ^init·Hop_ij为锚节点i到锚节点j的估计距离；

步骤4：利用步骤2得到的锚节点平均跳距AHD_i ^init计算锚节点之间的估计距离，参考锚节点之间的实际距离和最小跳数计算锚节点间每跳的误差值：

其中，EH_ij表示锚节点i到锚节点j的每一跳的误差值；

步骤5：利用锚节点间每跳的误差值对相应的锚节点赋予权值α_ij：

步骤6：利用步骤5中得到的锚节点之间的权值，通过加权最小均方误差准则计算加权后的锚节点平均跳距：

其中，AHD_i ^(m)为第m次加权迭代后求得的锚节点i的平均跳距；

步骤7：根据步骤6得到的加权后的锚节点平均跳距，计算加权后求得的锚节点平均跳距的误差：

其中，η_i ^(m)表示第m次加权迭代后得到的锚节点i的平均跳距的误差；

步骤8：若当前加权迭代次数m＝1，比较第一次加权后求得的锚节点平均跳距的误差η_i ⁽¹⁾和锚节点的初始平均跳距的误差η_i ^init的大小，如果η_i ⁽¹⁾<η_i ^init，则继续对锚节点的平均跳距加权迭代求解，返回到步骤4，利用当前迭代得到的锚节点平均跳距AHD_i ⁽¹⁾作为步骤4中的初始平均跳距AHD_i ^init，重新计算锚节点间的每跳误差，并以每跳的误差值作为权值再次迭代计算锚节点的平均跳距；如果η_i ⁽¹⁾>η_i ^init，结束迭代计算过程，以步骤2求得的初始平均跳距AHD_i ^init作为锚节点i的最优平均跳；

若当前加权迭代次数m>1，比较第m-1次加权后求得的锚节点平均跳距的误差η_i ^(m-1)和当前迭代求得的锚节点平均跳距的误差η_i ^(m)的大小，如果η_i ^(m)<η_i ^(m-1)，则继续对锚节点的平均跳距加权迭代求解，返回到步骤4，利用当前迭代加权得到的AHD_i ^(m)作为步骤4中的初始平均跳距AHD_i ^init，重新计算锚节点间的每跳误差，并以每跳的误差值作为权值再次迭代计算锚节点的平均跳距；如果η_i ^(m)>η_i ^(m-1)，结束迭代计算过程，以上次迭代求得的锚节点平均跳距AHD_i ^(m-1)作为锚节点i的最优平均跳距。

3.根据权利要求1或2所述的基于加权迭代和双重选择的DV-Hop节点定位方法，其特征在于，所述步骤二中未知节点到锚节点的估计距离的计算方法为：d_ui＝AHD_i ^best·Hop_ui；

其中，d_ui为未知节点u到锚节点i的估计距离，AHD_i ^best代表锚节点i的最优平均跳距；Hop_ui表示未知节点u到锚节点i的最小跳数，且u＝1,...,N，N为网络中未知节点总数。

4.根据权利要求3所述的基于加权迭代和双重选择的DV-Hop节点定位方法，其特征在于，所述步骤三中将锚节点组内的每个锚节点分别作为一次参考节点，利用最小二乘法计算未知节点的坐标，从中选取误差最小的坐标作为锚节点组的最优未知节点坐标；比较不同锚节点组求得的最优坐标误差的大小，选取误差最小的坐标作为未知节点的最终坐标的步骤为：

S1：将锚节点集合ANSET_＜k＞中的每个锚节点都作为一次参考锚节点计算未知节点的坐标；

S2：根据步骤二计算的未知节点与锚节点之间的估计距离，利用最小二乘法和锚节点集合ANSET_＜k＞内的锚节点分别计算相应的未知节点候选坐标(x_u,y_u)，且u＝1,...,k；

S3：根据未知节点的坐标和锚节点的坐标，计算每个未知节点候选坐标的误差：

其中，(x_u,y_u)代表未知节点u的估计坐标，(x_i,y_i)代表锚节点i的坐标；

S4：比较每个锚节点集合ANSET_＜k＞求得的候选坐标误差的大小，将具有最小误差的候选坐标作为该锚节点集合求得的最优候选坐标；

S5：比较不同锚节点集合下求得的最优候选坐标误差的大小，选取误差最小的最优候选坐标作为未知节点的最终坐标。

5.根据权利要求4所述的基于加权迭代和双重选择的DV-Hop节点定位方法，其特征在于，所述步骤S2中最小二乘法计算未知节点的候选坐标(x_u,y_u)的方法为：

S31：获取未知节点到每个锚节点的估计距离：

设未知节点的坐标为(x_u,y_u)，锚节点的坐标为(x_i,y_i),i＝1,2,…,k，未知节点到锚节点集合ANSET_＜k＞内锚节点的估计距离分别为d_u1,d_u2,…,d_uk，则有如下的方程组：

S32：将非线性方程组转化为线性方程组求解未知节点的坐标：

S33：将线性方程组表达成GX＝H的矩阵形式，其中：

利用最小二乘法求解未知节点的坐标为：

X＝(G^TG)^-1G^TH；

其中，G、H为步骤S32中线性方程组的矩阵表示形式，X表示求得的未知节点的坐标。

Images