基于粒子群與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 解決增根等問題。實驗結果表明，提出的方法有較高的精度且更具有一般性。