两种基本定位算法仿真分析

陈 帅，张水锋，束仁义，2，郑晓东

(1.淮南师范学院 电气信息工程学院，安徽 淮南 232038;2.安徽大学 电子信息工程学院，安徽 合肥 230039)

根据是否需要测量实际节点间的距离将定位算法分为基于距离定位和与距离无关的定位算法[1].基于距离的方法又分为：基于到达时间的测距；基于到达时间差的测距；基于达到角度的测距;基于接收信号强度的测距[2].距离无关的定位方法分为：质心算法；DV-HOP算法；Amorfous算法；APIT算法[3].三边测量法是基于距离的基本定位方法，质心算法是距离无关方法的典型代表.为分析这两种定位方法的精度，本文对三边测量法和质心算法这两种基本的定位方法进行了介绍，并进行了定位仿真实验.

1 三边测量定位法

设未知盲节点(简称盲节点)D(x，y)可以感知三个节点A(xa，ya)，B(xb，yb)，C(xc，yc)，且未知盲节点到该三个节点的距离分别为da，db，dc，如图1所示.

图1 三边测量法示意图 图2 质心定位算法图示

根据两点间距离计算公式，得：

(1)

求解方程组(1)就可以求得D点的定位坐标(简称定位节点)为[4]：

(2)

因此，借助参考点A、B、C和距离测量，就可以求得未知盲节点D的位置坐标.

2 质心算法定位

质心算法就是采用未知盲节点所在区域的质心作为估计位置.

如图2所示.设未知盲节点(x，y)所在的区域内可以感知的参考信标节点为(x1，y1)，(x2，y2)，…，(xN，yN)，其中N为未知盲节点在周边区域内可感知节点总数，r0为未知盲节点通信感知半径，且满足：

(3)

则取：

(4)

作为未知盲节点的定位坐标.

3 定位算法的仿真实验

3.1 三边测量法仿真

在区域1000米×1000米矩形区域随机分布1000个位置已知的参考节点，随机分布200个位置未知盲节点.假设每个未知节点任意获取三个参考节点的位置坐标，计算这三点间的距离，然后采用三边测量法进行自身的定位计算.定位结果如图3，可见盲节点通过三边测量法计算的定位与盲节点重合很好，表明精度较高.

图3 三边测量法定位结果

图4 质心算法定位结果

3.2 质心算法仿真

在区域1000米×1000米矩形区域随机分布1000个位置已知的参考节点，随机分布200个位置

未知盲节点.假设每个未知盲节点取在感知范围内的参考节点的位置坐标来进行质心算法定位计算，取感知半径r0=100米.先计算未知节点到所有参考节点的距离，取出距离小于r0的所有参考节点，然后采用质心算法进行定位计算.定位结果如图4，可见盲节点通过质心算法计算的定位与盲节点有许多不重合，表明存在较大误差.

4 分析

从三边测量法与质心算法实验可见，基于测距的三边测量定位法定位准确性高，而与距离无关的质心定位法误差大.这是因为基于测距的定位方法是通过感知区域内三个参考节点及其精确的测距，由数学精确求解得到唯一确定的定位坐标.而基于距离无关的质心算法定位是采用感知区域内的参考节点进行计算，一旦区域内感知参考节点确定，则质心也确定了，而区域内的未知节点位置却是不确定的.质心算法正是采用质心代替区域内未知节点的定位坐标，因而误差较大.通过缩小区域，尽管可以提高质心算法的精度，但未知节点在区域内的位置仍然是不定的，因而总是存在误差.

定位具有实际的意义.本文简介了两类基本的定位算法，通过仿真结果可见基于距离的定位方法相对于距离无关定位方法精度高.这为进一步开展新的定位算法和定位技术提供了积极的指导意义.

参考文献：

[1]He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks[C]//Proc 9th Annual Int'l Conf on Mobile Computing and Networking(MobiCom)，San Diego，CA.，2003：81-95.

[2]车云舟，须文波.基于RSSI的无线传感器网络定位技术的研究[J].微计算机信息，2010，26(10):82～84.

[3]王永才，赵千川，郑大钟.传感器网络自身定位方法的设计与实现[J]，计算机工程与应用，2005(13).

[4]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.