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

秦雪佩，羅相林

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都610039）

0 引言

目標(biāo)定位技術(shù)在無(wú)線電監(jiān)測(cè)、導(dǎo)航、環(huán)境監(jiān)測(cè)等領(lǐng)域應(yīng)用廣泛[1-2]。無(wú)線定位技術(shù)有著廣闊的應(yīng)用前景，大致可歸納為三類：一是在無(wú)線電監(jiān)測(cè)中，可以利用此類技術(shù)定位發(fā)射源，從而排除類似于“黑廣播”的干擾和非法頻率占用；二是為其他需要位置的系統(tǒng)提供必要的報(bào)告，如智能運(yùn)輸系統(tǒng)（ITS）和報(bào)警系統(tǒng)等；三是為移動(dòng)通信系統(tǒng)本身的資源管理和分配提供必要的信息。無(wú)線信號(hào)定位可以采用不同的方法來(lái)實(shí)現(xiàn)。

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

AOA 算法通過(guò)信號(hào)到達(dá)角度定位。然而，在實(shí)際應(yīng)用中AOA 算法對(duì)天線要求很高，需要部署天線陣列估計(jì)信號(hào)到達(dá)角度，提高了系統(tǒng)的復(fù)雜度與成本，并且隨著離基站的距離越遠(yuǎn)，波束也越寬，定位精度會(huì)隨著距離的增加而下降。TOA/TDOA 方法通過(guò)估計(jì)信號(hào)傳播時(shí)間（TOA）或時(shí)間差（TDOA）來(lái)計(jì)算信號(hào)源坐標(biāo)。這種方法中基站的同步對(duì)定位精度影響很大，1ns 的同步誤差對(duì)定位精度有約0.3m 的影響[6]。

與上述兩種方法相比，SSOA 方法易于實(shí)現(xiàn)，信號(hào)強(qiáng)度數(shù)據(jù)容易獲得，通過(guò)測(cè)量信號(hào)衰減程度來(lái)估計(jì)基站與信號(hào)源間的距離進(jìn)行定位。如使用移動(dòng)單站技術(shù)，則無(wú)需額外的硬件設(shè)備，簡(jiǎn)單靈活，成本低廉。SSOA 算法中，信號(hào)在傳播過(guò)程中的衰落是影響定位精度的關(guān)鍵因素。為提高定位精度，本文在Okumura-Hata 模型[7]的基礎(chǔ)上分析信號(hào)傳播過(guò)程，通過(guò)假設(shè)目標(biāo)位置，按照傳播原理計(jì)算得到多基站位置的強(qiáng)度值與實(shí)測(cè)強(qiáng)度值的區(qū)別，選擇適當(dāng)?shù)拇鷥r(jià)函數(shù)，利用最優(yōu)化算法迭代使得代價(jià)最小。然而，文獻(xiàn)[8]使用最優(yōu)化方法求解后，依然存在增根等問(wèn)題。本文為了解決此問(wèn)題，運(yùn)用了DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚類算法，使定位結(jié)果收斂，更加具有一般性。

1 系統(tǒng)模型以及問(wèn)題描述

本文主要研究在頻率相對(duì)較低（如FM 廣播段），區(qū)域范圍在約50km 以內(nèi)的二維信號(hào)源定位問(wèn)題，考慮二維（2-D）網(wǎng)絡(luò)，信號(hào)源TN，其目標(biāo)位置（x表示經(jīng)度,y）且θ ∈R2，發(fā)射功率為Pt(dBW)。通過(guò)n 個(gè)觀測(cè)點(diǎn)ANs 估計(jì)信號(hào)源TN 的位置。n 個(gè)觀測(cè)點(diǎn)ANs 的位置分別表示為，接收功率為Pi(dBW),i=1,…,n。信號(hào)源與第i 個(gè)觀測(cè)點(diǎn)距離為。通過(guò)這些模型發(fā)現(xiàn)，電波的損耗與電波接收和電波發(fā)射的相對(duì)位置有直接的關(guān)系，具體表現(xiàn)為電波的傳播損耗與lg(d )呈現(xiàn)出正比。雖然lg(d )的系數(shù)不盡相同，但是對(duì)應(yīng)特定的電波傳輸環(huán)境，參數(shù)相對(duì)固定，lg(d )的系數(shù)也相應(yīng)固定。從而可以推出：

其中ξ0表示距離為單位長(zhǎng)度路徑衰落。k 表示路徑衰落指數(shù)。b 參數(shù)可以看作是其余參數(shù)的函數(shù)，在一個(gè)固定的電波傳播環(huán)境中為定值。由Okumura-Hata模型[7]可知：

h 為發(fā)射天線高度。

根據(jù)電波傳播模型的簡(jiǎn)化公式可以得到，在等效全向發(fā)射功率為EIRP(dBW)，電波接收距離為d(km)的信號(hào)接收能量為：

式中，Pi是第i 個(gè)觀測(cè)點(diǎn)的接收功率。Pt是輻射源的發(fā)射功率，Gt是發(fā)射天線增益（包含損耗），Gr是接收天線增益（包含損耗）。

由于信號(hào)源TN 屬性位置，電波傳播環(huán)境未知，所以發(fā)射功率EIRP，參數(shù)b 無(wú)法確定，不能直接求解。為此本文通過(guò)做差的方式消除EIRP，b 帶來(lái)的影響。假設(shè)信號(hào)源的位置，N 個(gè)觀測(cè)點(diǎn)θ1,θ2,…,θn的接收功率為P1,P2,…Pi。提出代價(jià)函數(shù)：

通過(guò)使cos tf( θ' )最小，用最優(yōu)化算法迭代不斷逼近信號(hào)源位置。

2 粒子群+DBSCAN算法

2.1 粒子群算法

損失函數(shù)cos tf( θ' )為標(biāo)準(zhǔn)進(jìn)行評(píng)價(jià)。假定其最優(yōu)解為θ，將θ 看做二維空間中的一個(gè)粒子，其位置在二維（2-D）空間中，選擇m 個(gè)粒子用來(lái)模擬信號(hào)源的位置，粒子ci=[ ci1,ci2]T,i=1,…,m。每個(gè)粒子的速度vi=[ vi1,vi2]T,i=1,…,m。把粒子作為假設(shè)信號(hào)源的位置，求得cos tf( θ' )，粒子i 代價(jià)最小歷史最好位置：pi=(pi1,pi2,

粒子群算法是Kennedy 等在1995 年提出的一種群智能計(jì)算方法[9]。在算法中，將優(yōu)化問(wèn)題的解看作是搜索空間中無(wú)質(zhì)量無(wú)體積的粒子，通過(guò)迭代找到最優(yōu)解。在每一次迭代中,粒子通過(guò)跟蹤個(gè)體最優(yōu)位置(pi)和全局最優(yōu)位置(pg)來(lái)更新自己。

將信號(hào)源定位作為目標(biāo)優(yōu)化問(wèn)題,其解的優(yōu)劣以…，pim)。群體內(nèi)所有粒子代價(jià)最小的位置：pg=(pg1,pg2,…,pgm)。在第k 次迭代中粒子在搜索空間的速度和位置根據(jù)如下公式確定：

其中c1,c2為學(xué)習(xí)因子，一般為正常數(shù)。r1,r2為兩個(gè)隨機(jī)數(shù)，取值范圍是[0 ,1]，以增加搜索隨機(jī)性，ω 為慣性權(quán)重，調(diào)節(jié)對(duì)空間的搜索能力。

在達(dá)到一定迭代次數(shù)或損失函數(shù)cos tf( θ' )小于某個(gè)極小值? 后，當(dāng)前群體內(nèi)所有粒子中cos tf( θ' )最小的粒子位置即被認(rèn)為是信號(hào)源位置θ。

2.2 DBSCAN算法

基于2.1 小節(jié)的粒子群算法，可以由強(qiáng)度數(shù)據(jù)計(jì)算出信號(hào)源位置的近似結(jié)果，但仍存在以下幾個(gè)問(wèn)題：①粒子隨機(jī)區(qū)域的選擇對(duì)算法的結(jié)果影響很大。②因?yàn)楦鶕?jù)最優(yōu)化方法求解定位問(wèn)題的求解結(jié)果存在增根[8]。③粒子群算法的初始位置與初始速度都為隨機(jī)數(shù)，所以最優(yōu)化處理的結(jié)果往往不會(huì)收斂在一點(diǎn)上，甚至可能會(huì)出現(xiàn)比較糟糕的結(jié)果，在實(shí)際工作中參考性不大。為此，本文在2.1 小節(jié)的算法基礎(chǔ)之上運(yùn)用聚類算法，將相似的定位結(jié)果聚為一個(gè)簇，選擇權(quán)重最大的簇作為最終結(jié)果。從而避免結(jié)果有增根與不收斂。

考慮到需要計(jì)算的數(shù)據(jù)維度低（2-D），并且事先不確定聚類的個(gè)數(shù)，所以本文使用了DBSCAN 算法進(jìn)行聚類分析。DBSCAN 是一種基于空間密度的聚類算法。它克服了基于距離的聚類方法只能得到“類圓形”簇的缺點(diǎn)，可將任意形狀的簇劃分開來(lái)，且對(duì)噪聲不敏感[10]。該方法提出密度可達(dá)和密度相連的概念，將簇定義為基于密度可達(dá)性的最大密度相連對(duì)象的集合。利用DBSCAN 可將樣本集D 劃分為多個(gè)簇。

在實(shí)際采集過(guò)程中，n 個(gè)觀測(cè)點(diǎn)數(shù)據(jù)采集存在時(shí)序上的先后（如車載移動(dòng)采集）。設(shè)某一時(shí)刻采集到n 個(gè)觀測(cè)數(shù)據(jù)，對(duì)這些觀測(cè)數(shù)據(jù)運(yùn)用2.1 小節(jié)中的算法，將其結(jié)果為。令1 到T 時(shí)刻的粒子群算法計(jì)算結(jié)果構(gòu)成了樣本集D，即。因?yàn)椴煌瑫r(shí)刻得到的觀測(cè)數(shù)據(jù)點(diǎn)個(gè)數(shù)n 不同，所以本文對(duì)每個(gè)對(duì)象pi都賦予了不同的權(quán)值ω()i。對(duì)樣本集D進(jìn)行DBSCAN 算法進(jìn)行聚類分析后，對(duì)于每一個(gè)簇Ci，都有權(quán)重：

選擇權(quán)重最高的簇C'，目標(biāo)位置θ 即為簇中所有對(duì)象的加權(quán)平均值。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文選取成都市郫都區(qū)廣播電視臺(tái)（FM96.5）作為信號(hào)源，使用車載接收機(jī)以采集到的頻率為96.5MHz的信號(hào)強(qiáng)度數(shù)據(jù)作為衡量本節(jié)方法的數(shù)據(jù)源，通過(guò)本算法求得的信號(hào)源位置θ'。通過(guò)實(shí)際測(cè)量，可以得到郫都區(qū)廣播的GPS 坐標(biāo)，再以采集到的673 條信號(hào)的能量數(shù)據(jù)和GPS 數(shù)據(jù)作為運(yùn)算數(shù)據(jù)，得到所需要的定位實(shí)際誤差。GPS 數(shù)據(jù)轉(zhuǎn)換距離的公式為：

其中x1,y1,x2,y2分別為需要求距離兩點(diǎn)的經(jīng)緯度。

3.2 結(jié)果分析

運(yùn)用上述數(shù)據(jù)得到結(jié)果如圖1 所示：

圖1 聚類分析結(jié)果

圖1 中不同形狀表示聚類得到的簇，空心圓圈為權(quán)重最大的簇。五角星為真實(shí)位置，六角星為本方法定位結(jié)果。用距離轉(zhuǎn)換公式計(jì)算，定位誤差為0.81km。

表1 性能對(duì)比

由表1 可知，粒子群+DBSCAN 算法在不丟失精度的前提下解決了增根以及最優(yōu)化算法依賴初始位置選擇的問(wèn)題，有著較好的收斂性。

4 結(jié)語(yǔ)

相比較于AOA、TOA/TDOA 而言，SSOA 更容易實(shí)現(xiàn)，有著更低的復(fù)雜度。為此選擇信號(hào)強(qiáng)度作為數(shù)據(jù)源，通過(guò)分析信號(hào)傳播原理，使用粒子群算法求得信號(hào)源位置最優(yōu)解，并用DBSCAN 解決增根等問(wèn)題。實(shí)驗(yàn)結(jié)果表明，提出的方法有較高的精度且更具有一般性。