基于粒子群与DBSCAN 的SSOA 定位算法

秦雪佩，罗相林

（西华大学计算机与软件工程学院，成都610039）

0 引言

目标定位技术在无线电监测、导航、环境监测等领域应用广泛[1-2]。无线定位技术有着广阔的应用前景，大致可归纳为三类：一是在无线电监测中，可以利用此类技术定位发射源，从而排除类似于“黑广播”的干扰和非法频率占用；二是为其他需要位置的系统提供必要的报告，如智能运输系统（ITS）和报警系统等；三是为移动通信系统本身的资源管理和分配提供必要的信息。无线信号定位可以采用不同的方法来实现。

其基本技术手段有3 种[3-5]：基于SSOA（Signal Strength Of Arrival）、基于AOA（Angle Of Arrive）和基于TOA/TDOA（Time Of Arrive/Time Difference Of Arrive）。

AOA 算法通过信号到达角度定位。然而，在实际应用中AOA 算法对天线要求很高，需要部署天线阵列估计信号到达角度，提高了系统的复杂度与成本，并且随着离基站的距离越远，波束也越宽，定位精度会随着距离的增加而下降。TOA/TDOA 方法通过估计信号传播时间（TOA）或时间差（TDOA）来计算信号源坐标。这种方法中基站的同步对定位精度影响很大，1ns 的同步误差对定位精度有约0.3m 的影响[6]。

与上述两种方法相比，SSOA 方法易于实现，信号强度数据容易获得，通过测量信号衰减程度来估计基站与信号源间的距离进行定位。如使用移动单站技术，则无需额外的硬件设备，简单灵活，成本低廉。SSOA 算法中，信号在传播过程中的衰落是影响定位精度的关键因素。为提高定位精度，本文在Okumura-Hata 模型[7]的基础上分析信号传播过程，通过假设目标位置，按照传播原理计算得到多基站位置的强度值与实测强度值的区别，选择适当的代价函数，利用最优化算法迭代使得代价最小。然而，文献[8]使用最优化方法求解后，依然存在增根等问题。本文为了解决此问题，运用了DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，使定位结果收敛，更加具有一般性。

1 系统模型以及问题描述

本文主要研究在频率相对较低（如FM 广播段），区域范围在约50km 以内的二维信号源定位问题，考虑二维（2-D）网络，信号源TN，其目标位置（x表示经度,y）且θ ∈R2，发射功率为Pt(dBW)。通过n 个观测点ANs 估计信号源TN 的位置。n 个观测点ANs 的位置分别表示为，接收功率为Pi(dBW),i=1,…,n。信号源与第i 个观测点距离为。通过这些模型发现，电波的损耗与电波接收和电波发射的相对位置有直接的关系，具体表现为电波的传播损耗与lg(d )呈现出正比。虽然lg(d )的系数不尽相同，但是对应特定的电波传输环境，参数相对固定，lg(d )的系数也相应固定。从而可以推出：

其中ξ0表示距离为单位长度路径衰落。k 表示路径衰落指数。b 参数可以看作是其余参数的函数，在一个固定的电波传播环境中为定值。由Okumura-Hata模型[7]可知：

h 为发射天线高度。

根据电波传播模型的简化公式可以得到，在等效全向发射功率为EIRP(dBW)，电波接收距离为d(km)的信号接收能量为：

式中，Pi是第i 个观测点的接收功率。Pt是辐射源的发射功率，Gt是发射天线增益（包含损耗），Gr是接收天线增益（包含损耗）。

由于信号源TN 属性位置，电波传播环境未知，所以发射功率EIRP，参数b 无法确定，不能直接求解。为此本文通过做差的方式消除EIRP，b 带来的影响。假设信号源的位置，N 个观测点θ1,θ2,…,θn的接收功率为P1,P2,…Pi。提出代价函数：

通过使cos tf( θ' )最小，用最优化算法迭代不断逼近信号源位置。

2 粒子群+DBSCAN算法

2.1 粒子群算法

损失函数cos tf( θ' )为标准进行评价。假定其最优解为θ，将θ 看做二维空间中的一个粒子，其位置在二维（2-D）空间中，选择m 个粒子用来模拟信号源的位置，粒子ci=[ ci1,ci2]T,i=1,…,m。每个粒子的速度vi=[ vi1,vi2]T,i=1,…,m。把粒子作为假设信号源的位置，求得cos tf( θ' )，粒子i 代价最小历史最好位置：pi=(pi1,pi2,

粒子群算法是Kennedy 等在1995 年提出的一种群智能计算方法[9]。在算法中，将优化问题的解看作是搜索空间中无质量无体积的粒子，通过迭代找到最优解。在每一次迭代中,粒子通过跟踪个体最优位置(pi)和全局最优位置(pg)来更新自己。

将信号源定位作为目标优化问题,其解的优劣以…，pim)。群体内所有粒子代价最小的位置：pg=(pg1,pg2,…,pgm)。在第k 次迭代中粒子在搜索空间的速度和位置根据如下公式确定：

其中c1,c2为学习因子，一般为正常数。r1,r2为两个随机数，取值范围是[0 ,1]，以增加搜索随机性，ω 为惯性权重，调节对空间的搜索能力。

在达到一定迭代次数或损失函数cos tf( θ' )小于某个极小值ϵ 后，当前群体内所有粒子中cos tf( θ' )最小的粒子位置即被认为是信号源位置θ。

2.2 DBSCAN算法

基于2.1 小节的粒子群算法，可以由强度数据计算出信号源位置的近似结果，但仍存在以下几个问题：①粒子随机区域的选择对算法的结果影响很大。②因为根据最优化方法求解定位问题的求解结果存在增根[8]。③粒子群算法的初始位置与初始速度都为随机数，所以最优化处理的结果往往不会收敛在一点上，甚至可能会出现比较糟糕的结果，在实际工作中参考性不大。为此，本文在2.1 小节的算法基础之上运用聚类算法，将相似的定位结果聚为一个簇，选择权重最大的簇作为最终结果。从而避免结果有增根与不收敛。

考虑到需要计算的数据维度低（2-D），并且事先不确定聚类的个数，所以本文使用了DBSCAN 算法进行聚类分析。DBSCAN 是一种基于空间密度的聚类算法。它克服了基于距离的聚类方法只能得到“类圆形”簇的缺点，可将任意形状的簇划分开来，且对噪声不敏感[10]。该方法提出密度可达和密度相连的概念，将簇定义为基于密度可达性的最大密度相连对象的集合。利用DBSCAN 可将样本集D 划分为多个簇。

在实际采集过程中，n 个观测点数据采集存在时序上的先后（如车载移动采集）。设某一时刻采集到n 个观测数据，对这些观测数据运用2.1 小节中的算法，将其结果为。令1 到T 时刻的粒子群算法计算结果构成了样本集D，即。因为不同时刻得到的观测数据点个数n 不同，所以本文对每个对象pi都赋予了不同的权值ω()i。对样本集D进行DBSCAN 算法进行聚类分析后，对于每一个簇Ci，都有权重：

选择权重最高的簇C'，目标位置θ 即为簇中所有对象的加权平均值。

3 实验及结果分析

3.1 实验设计

本文选取成都市郫都区广播电视台（FM96.5）作为信号源，使用车载接收机以采集到的频率为96.5MHz的信号强度数据作为衡量本节方法的数据源，通过本算法求得的信号源位置θ'。通过实际测量，可以得到郫都区广播的GPS 坐标，再以采集到的673 条信号的能量数据和GPS 数据作为运算数据，得到所需要的定位实际误差。GPS 数据转换距离的公式为：

其中x1,y1,x2,y2分别为需要求距离两点的经纬度。

3.2 结果分析

运用上述数据得到结果如图1 所示：

图1 聚类分析结果

图1 中不同形状表示聚类得到的簇，空心圆圈为权重最大的簇。五角星为真实位置，六角星为本方法定位结果。用距离转换公式计算，定位误差为0.81km。

表1 性能对比

由表1 可知，粒子群+DBSCAN 算法在不丢失精度的前提下解决了增根以及最优化算法依赖初始位置选择的问题，有着较好的收敛性。

4 结语

相比较于AOA、TOA/TDOA 而言，SSOA 更容易实现，有着更低的复杂度。为此选择信号强度作为数据源，通过分析信号传播原理，使用粒子群算法求得信号源位置最优解，并用DBSCAN 解决增根等问题。实验结果表明，提出的方法有较高的精度且更具有一般性。