内容发布更新时间 : 2024/5/4 5:47:02星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

质心和DV—Hop定位算法概率分布特征的研究

作者：梁建国 傅游

来源：《电脑知识与技术》2013年第24期

摘要：为了对质心定位算法和DV-Hop定位算法的概率分布特征进行研究，在深入研究质心定位算法和DV-Hop定位算法的基础上，提出了一种概率分布特征的分析算法，并在MATLAB平台上进行了仿真实验。实验结果表明，在相同的节点分布密度以及网络连通度的条件下，在锚节点数量较少情况下，DV-Hop定位算法比质心定位算法落在规定范围内概率大，在锚节点数量上升到一定数量后，质心定位算法将接近并超过DV-Hop定位算法的概率分布。

关键词：质心定位算法；DV-Hop定位算法；概率分布；无线传感器网络；定位 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）24-5509-04

节点定位作为无线传感器网络（ Wireless Sensor Network，WSN）的基本功能，是无线传感器网络的关键支撑技术之一[1]。在无线传感器网络的各种应用中，如目标跟踪、物流管理、生态环境监测、地震洪水火灾、医疗监护等的现场监控中，都需要获取传感器节点的位置信息，从而对信息来源的位置进行精准的定位，同时，节点的位置信息还可以辅助实现数据路由。因此，节点定位对无线传感器的有效性起着至关重要的作用。

目前，大多节点定位技术都是利用少数已知位置信息的节点通过某种机制来确定未知节点的位置。根据是否需要测量相邻节点间的距离或角度信息，将定位算法分为基于测距的算法和无需测距的算法[2]。基于测距的算法通过测量相邻节点间的距离或角度信息，并利用实际测量的距离来计算未知节点的位置，定位精度较高，但对硬件依赖性高，不适合低功耗、低成本的无线传感器网络应用领域。常用的基于测距的算法有TOA和TDOA、AOA和RSSI[3]。无需测距的算法无需测量相邻节点间的距离或角度信息，利用网络的连通性等信息，来估计未知节点的位置或可能存在的区域，虽然定位精度较低，但对节点的硬件要求不高，能够满足多数无线传感器网络的定位要求。目前无需测距的定位算法主要有质心定位算法、凸规划定位算法、DV-Hop定位算法和APIT算法等[4]。

质心定位算法和DV-Hop定位算法作为两种经典的无需测距的定位算法，一直以来都是研究的热点。文献[5]在分析质心定位算法和DV-Hop定位算法基础上，提出了质心和DV-Hop混合算法，文献[6-7]则从影响算法定位精度的因素入手，对算法进行改进。该文则从对质心定位算法和DV-Hop定位算法概率分布特征分析入手，研究质心定位算法和DV-Hop定位算法概率分布特征，并设计了相应的分析算法，对质心定位算法和DV-Hop定位算法的概率特征进行定量分析。

龙源期刊网 http://www.qikan.com.cn

1 一种质心定位算法和DV-Hop定位算法概率分布特征的分析算法的研究

本文所研究的质心定位算法和DV-Hop定位算法概率分布特征的分析算法主要包括三个部分：首先利用质心和DV-Hop定位算法分别对未知节点进行定位；其次是利用概率分布检测方法对定位后的节点进行判断；最后分别计算两种定位算法落在规定范围内的概率大小。概率分布检测方法的设计是算法的核心部分，本部分重点对其进行研究。 1.1 概率分布检测方法设计

质心定位算法和DV-Hop定位算法概率分布检测方法的主要思想是在利用质心和DV-Hop定位算法分别估算出目标节点位置的基础上，分别以两种算法估算出的目标节点位置为基准点进行研究，判断目标节点是否落在规定的范围内，落在规定范围内则进行记录，否则不记录。 在选择规定范围方面，由于质心和DV-Hop定位算法都有一定的误差，通过对节点的定位跟踪分析，我们发现如果目标节点如果落在2倍半径之外，说明估算出的目标点和实际目标节点差距很大，失去了定位的意义；如果目标节点落在0.5倍半径之内，说明估算出的目标节点非常接近实际目标节点位置。为此，该文以1倍半径为参照，并对讨论的范围适当进行放大和缩小至2倍和0.5倍半径，分析两种定位算法的概率分布特征。

下面以质心定位和DV-Hop定位算法估算出的目标节点位置为基准节点，即圆心，以两种算法分别估算出目标节点位置之间的距离的2倍、1倍和0.5倍为半径所围成的圆这三种情况下实际目标节点的概率分布特征。如图1所示，假设A、B两点分别为DV-Hop定位和质心定位算法估算出的目标节点的位置，r为AB之间的距离，以估算出的目标节点位置A为基准点进行分析，实际目标节点可能出现的位置有两种情况，一种是落在以A为圆心，r为半径的圆内；另一种情况是落在以A为圆心，r为半径的圆外。D、D′、D〞为目标节点在这三种情况下可能出现的位置。

按照如上描述方法，以1倍半径为例讨论如何建立概率分布检测模型，假设目标节点di的位置为（xi， yi），通过DV-Hop定位算法求出的未知节点的位置为ai，坐标为（pi， qi），通过质心定位算法求出的未知节点的位置为bi，坐标为（mi，ni），则目标节点与通过DV-Hop定位算法估算出的目标节点的距离为[l（ai，di）=（xi-pi）2+（yi-qi）2]。 目标节点与通过质心定位算法估算出的目标节点的距离为[l′（bi，di）=（xi-mi）2+（yi-ni）2]。

通过DV-Hop定位算法估算出的目标节点ai与通过质心定位算法估算出的目标节点bi之间的距离为[r（ai，bi）=（pi-mi）2+（qi-ni）2]。

如果以DV-Hop定位算法估算出的目标节点A为基准节点进行分析，其概率检测公式如（1）所示：

龙源期刊网 http://www.qikan.com.cn

如果以质心定位算法估算出的目标节点B为基准节点进行分析，其概率检测公式如（2）所示：

2倍和0.5倍半径情况下的概率分布检测模型的建立和上述相同。 1倍、2倍和0.5倍半径情况下的概率检测公式可以统一归纳如下：

如果以DV-Hop定位算法估算出的目标节点A为基准节点进行分析，其概率检测公式为（3）所示。

其中[α]为常量，其值为2，1或者0.5。

如果以质心定位算法估算出的目标节点B为基准节点进行分析，其概率检测公式为（4）所示。

其中[α]为常量，其值为2，1或者0.5。 1.2 概率分布特征分析算法

概率分布特征分析算法的伪代码如下： begin

Initialize the network node.

Estimating location of the destination node by centroid and DV-Hop algorithm， they are ai（pi， qi） and bi（mi， ni）. for each unknown node do

Using two-point distance formula to calculate its distance ai（pi， qi），bi（mi， ni）and di（xi， yi）.

if A is the reference node， test the relationship with the estimation ai（pi， qi） of the target node and di（xi， yi）using detection probability formula （3）；

if B is the reference node， test the relationship with the estimation bi（mi， ni） of the target node and di（xi， yi）using detection probability formula （4）. endfor

Respectively to calculate the probability distribution of two cases.