朱 军， 王吉平， 杨家丰， 姚 泽

(桂林电子科技大学 认知无线电与信息处理省部共建教育部重点实验室，广西 桂林 541004)

目前室内定位算法主要分成两类：1)基于距离的算法(range-base)；2)无需测距离的算法(range-free)。基于Range-base的算法常用的测量技术有：接收信号强度估计(received signal strength indicator，简称RSSI)[1]，到达时差(time difference of arrival，简称TDOA)[2]，到达时间(time of arrival，简称TOA)[3]，到达角度(angle of arrival，简称AOA)[4]等，基于距离的算法精度非常高，在传感器采集数据误差较小情况下精度可达到厘米级。无需测距的算法通常利用无线传感器网络系统的连通性进行目标节点的位置估计，典型的算法有Dv-hop[5]、质心算法[6]、近似三角形内点测试法(approximate point-in-triangulation test，简称APIT)，基于Range-free的算法要获得更高的精度，可通过改变参考节点分布密度或者改变盲节点通信半径获得。

针对影响质心算法定位精度的问题，Huang等[8]提出通过对路径损耗系数进行分类，并利用欧氏距离判断实际的RSSI值选择相应的路径损耗类别。王恩良等[9]使用k-近邻算法求解。谷广等[10]提出一种改善参考节点分布不均匀时改进型质心定位算法，通过判断检测到的参考节点是否构成三角形以及盲节点是否在三角形内来决定使用何种算法来提高定位精度并且通信半径越大误差越小。李卫东等[11]指出可以在3个参考节点的基础上增加一个或者多个参考节点，再利用相交圆的2个交点的连线延长的交点求解盲节点坐标。

基于文献[10]，研究质心定位算法的误差率与通信半径和参考节点分布密度之间的关系，找出一个三者之间的最优点。

1 通信半径和参考节点分布密度对定位精度的影响

1.1 信号传输模型

无线信号传输中普遍采用的理论模型为渐变模型[12]，

(1)

其中：d为盲节点到参考节点的距离；p(d)表示距离参考节点距离为d时，盲节点接收到的信号强度；p(d0)表示距离参考节点为d0时，盲节点接收到的信号强度，其中d0为参考距；n为路径损耗系数,该值随着环境的复杂度而改变，一般障碍物越多，n取值越大，正常的范围在2～6；X是一个服从正态分布的高斯随机变量，单位为dBm。

实际工程应用中一般采用简化模型，

(2)

为了简化计算过程，d0一般取1 m，并令p(d)为接收信号强度估计(received signal strength indicator,简称RSSI)，p(d0)=A，于是有：

IRSS=A-10nlg(d)，

(3)

A为盲节点距离参考节点1 m时，盲节点接收到信号强度值。

1.2 质心算法原理

质心算法的基本原理为：盲节点检测到与其相互连通的参考节点，根据参考节点提供的位置信息估计自身位置。具体实现过程为：参考节点向四周周期性发送自身位置信息，盲节点根据接收到的不同参考节点发送的位置信息进行自身位置估计。当盲节点接收到的参考节点的个数或者信号强度达到一定阈值时，盲节点就记录符合一定阈值参考节点位置坐标，并利用这些参考节点所构成的多边形的质心作为自身位置，如图1所示。

图1 质心定位原理示意图

假设盲节点F(x,y)接收到5个参考节点坐标A～E，对应的坐标值为(xi,yi)，i=1,2,3,4,5。则盲节点F的估计坐标为：

(4)

1.3 通信半径对定位误差的影响

理论猜想：当盲节点的通信半径增大后，同时也引入了新的参考节点，新的多边形就会产生，从而得到新的质心，那么这对定位误差会产生什么样的影响？

图2是在100 m×100 m的区域内随机生成20个参考节点和一个实际节点，通过改变通信半径为20、30 m获得2个新的定位节点：d=20和d=30，仿真获得的结果。

根据图2可知，在一定的通信范围内，参考节点分布密度增大，绝对误差存在减小和增大2种情况。结合图1可知，就单个节点而言，参考节点分布密度对绝对误差的影响不能一概而论，可能与其通信半径和参考节点分布密度都有关系。

1.4 参考节点分布密度对定位误差的影响

根据质心算法的原理可知，在一定的通信范围内，盲节点周围分布的参考节点密度会影响定位的结果，那么参考节点的分布密度具体是多少才可以获得最小定位误差?

图3是在100 m×100 m的区域内随机产生20个参考节点和一个实际节点，通信距离为30 m，不引入新的参考节点时实际节点的定位结果为方形的节点，在实际节点通信范围内，引入3个菱形的参考节点后定位的结果为五角星形的节点。

根据图3可知，在一定的通信范围内，参考节点分布密度增大，绝对误差存在减小和增大2种情况。结合图2可知，就单个节点而言，参考节点分布密度对绝对误差的影响不能一概而论，可能与其通信半径和参考节点分布密度都有关系。

图2 盲节点通信半径对绝对误差的影响

图3 参考节点分布密度对绝对误差的影响

2 仿真与分析

根据第一节的分析可知，质心算法的定位误差与其通信半径和参考节点分布密度均有关系，同时文献[13]也指出，质心算法的定位误差与参考节点的分布存在一定关系，所以本次仿真不考虑参考节点的分布，减小由于随机生成的参考节点分布位置不同而带来的误差影响，只考虑通信半径和参考节点分布密度。

2.1 网络部署

本次仿真在100 m×100 m的区域内随机生成20个盲节点，相邻的参考节点分布成矩形分布，参考节点密度可以改变，通信距离也可以改变。参考节点密度主要通过改变Excel表格定义的横纵坐标实现，通信距离通过改变参考节点和盲节点之间的检测距离的阈值d2实现，整个定位程序实现流程如图4所示。

图4 定位程序流程图

图5 定位效果图

图5为定位效果图。结合图4和图5可知，在一定的通信半径下，当参考节点之间的距离过大，盲节点可能出现无法定位的情况。

2.2 最佳通信半径的仿真与分析

盲节点是随机产生的，为了减少这一因素对算法的影响，首先在130 m×100 m区域内随机生成20个盲节点，固定盲节点检测距离(距离为10 m至70 m，间隔为5 m，共13个不同的检测距离)，在改变参考节点分布密度的情况下进行仿真，将每组的仿真结果取平均值得到图6。

图6 盲节点通信半径与误差率的关系图

从图6可看出，误差率随通信半径先减小后增加，仿真结果拟合的是一条二次曲线，在最低点的定位误差率大约为0.230 8，与之对应的通信半径为41 m，即为最佳通信半径。在此基础上，该点对应的就是一个较好的定位精度，且在该条件下需要的成本也相对较低。因此达到最佳通信半径的要求后，所使用的方法能够得到一个成本和定位误差率的平衡点，也就是寻找最佳通信半径所具有的实际意义。

2.3 通信半径、参考节点分布密度与定位精度的关系

随着盲节点的通信半径变大，参考节点增多，平均误差减少，但是随着节点密度的增大，建设成本也增加，所以实际应用中要综合考虑成本和定位精度，需要选取一个合适的实际应用方案。因此最后对通信半径、参考节点分布密度和定位精度三者之间的关系进行仿真。

使用与2.2节类似的方法，首先在130 m×100 m区域内随机生成20个盲节点，固定参考节点分布密度(均匀分布130、90、70、63、50、45、40、36、30、25、20、16、12个参考节点)，然后改变盲节点的通信半径的情况下进行仿真，最后将每组的仿真结果取平均值得到图7。

图7 参考节点分布密度与误差率关系图

从图6和图7可看出，参考节点的分布密度和盲节点的通信半径之间存在一定的关系，可以用数学公式表达为

e=0.000 172 5×d2-0.014 18×d+0.522 2，

(5)

e=1.148×10-5×p2-0.002 967×p+0.389 4，

(6)

其中：e为误差率；d为盲节点通信半径；p为参考节点的分布密度。

利用式(5)和式(6)进行仿真可得图8所示，盲节点的通信半径和参考节点分布密度与误差率三者之间的关系。从图8可知，盲节点的通信半径为41 m，参考节点分布密度为41 个(分布区域130×100=13 000 m2)时，误差率为最小0.232 4，即最小误差距离为9.462 8 m。

图8 盲节点通信半径和参考节点分布密度与误差率的关系

3 结束语

分析了盲节点的通信半径和参考节点的分布密度对定位精度的影响，虽然提高参考节点的分布密度能够有效提高定位精度，但在实际应用过程中需要考虑成本问题，所以不能盲目增加参考节点密度，因此最终基于质心算法的定位精度与成本的问题，将定位误差率分别与盲节点的通信半径和参考节点的分布密度之间的关系进行仿真，再拟合出三者关系的曲线，并且找到了一个平衡三者关系的最优点。该点的存在为室内定位领域提供了非常重要的参考价值。

该研究虽然在经典质心算法的基础上达到了预期的目的，但参考节点的分布仍会对定位误差产生较大的影响，所以今后研究的重点方向是找到参考节点最合理的分布方法。