結合K-均值聚類的無源目標定位技術*

陳 承，李 寧，郭 艷，盛金鋒，李華靜

（中國人民解放軍陸軍工程大學，江蘇 南京 210007）

0 引言

近年來，隨著物聯網“感知中國”之路的不斷建設，物聯網用戶對于對象的在線監測、目標的定位溯源等服務提出了更高的要求，推動了學者對定位技術的深入研究。[1]

目前應用最廣泛的定位技術是全球導航衛星系統（Global Navigation Satellite System，GNSS）[2]，它是根據導航衛星發出的無線信號來實現定位功能，其中最著名的是美國的全球定位系統（Global Positioning System，GPS）[3]，我國也自主研發了北斗衛星導航系統[4]。但是，GNSS 都是基于設備的定位，需要定位目標攜帶無線設備。為解決GNSS在受遮擋和非視距情況下定位受限的問題，無源目標定位（Device Free Localization，DFL）應運而生[5]。DFL 不需要目標攜帶無線設備，而是通過探測目標對監測區域內信號的影響來估計目標位置。目前，DFL 已廣泛應用于入侵者監測、野生動物追蹤、室內保安系統等[6]場景。

近年來，基于無線傳感器網絡（Wireless Sensor Network，WSN）的DFL 技術快速發展[7]。因為通過WSN 可以方便地采集接收信號強度（Received Signal Strength，RSS）信號，所以基于WSN 的DFL方法多以測量RSS 變化值來反映無線鏈路的陰影效應，估計目標位置[8]。針對如何利用RSS 變化值，有以下幾種類型的DFL 方法：

（1）基于幾何結構的DFL 方法[9]。它是根據RSS 變化值估計被遮擋鏈路與目標位置關系來實現定位的，但是該方法定位精度不高且需要預先獲取無線節點的位置信息。

（2）基于指紋的DFL 方法[10]。它是在離線階段建立指紋庫，在線階段通過對比目標對無線鏈路影響來估計位置的，但該方法需要耗費巨大資源去建立和更新指紋庫。

（3）基于無線層析成像（Radio Tomographic Imaging，RTI）的DFL 方法[11]。它是利用計算機層析成像原理估計目標位置，但該方法需要在監測區域內大量部署無線傳感器節點，對硬件資源要求較高。

（4）基于壓縮感知（Compressive Sensing，CS）的DFL 方法[12]。它是利用少量數據采樣和精確恢復稀疏信號來實現目標定位的，該方法只需要采集少量測量數據就能以高概率重構目標位置向量，是一種資源節約的可靠方法。

如前文所述，基于CS 的DFL 方法具有巨大的研究價值，其研究主要集中在信號的稀疏表示、觀測矩陣的設計和信號的重構3 個方面[13]。

在信號的稀疏表示研究中，根據字典中原子的正交性，將稀疏表示字典分為了正交基字典和非正交基字典。文獻[14]利用傅里葉變換得到正交基字典，文獻[15]利用離散余弦變換得到正交基字典，文獻[16]利用小波變換得到正交基字典。但在自然界中，信號往往是復雜的，多數不滿足在正交基字典下具有稀疏性的條件，所以文獻[17]提出了基于優化參數的非正交字典，文獻[18]提出了基于訓練樣本學習的非正交字典，這類字典將機器學習融入字典的構建，所構造出來的字典具有更強的稀疏表示能力，所以被廣為應用。

在觀測矩陣的設計中，通常以約束等距性質（Restricted Isometry Property，RIP）來衡量測量矩陣的優劣。觀測矩陣根據元素的隨機性不同，可以分為隨機性觀測矩陣和確定性觀測矩陣。典型的隨機觀測矩陣有文獻[19]中的高斯隨機矩陣、文獻[20]中的Bemoulli 隨機矩陣、文獻[21]中的Rademacher隨機矩陣。典型的確定性觀測矩陣有文獻[22]中的拓普利茲矩陣、文獻[23]中的循環矩陣、文獻[24]中的結構化測量矩陣。根據RIP 判斷，隨機性測量矩陣重構效果更好，適用性更強。

在信號的重構算法研究中，最有代表性的算法有凸松弛算法、貪婪追蹤算法和稀疏貝葉斯學習算法3 種。文獻[25]中提出的凸松弛算法，將典型的CS 重構問題松弛成 ?p范數優化問題；文獻[26]中提出的貪婪追蹤算法，利用信號稀疏性迭代地搜索信號中非0 元素的索引并確定其稀疏；文獻[27]中提出的稀疏貝葉斯學習算法，基于概率思想，根據參數的關系推理原始信號的分布。

目前，重構效果最好的算法是變分貝葉斯推理（Variational Bayesian Inference，VBI）算法[28]。基于VBI 稀疏重構算法的CS 無源目標定位技術雖然可以實現定位功能，但仍存在以下問題：

（1）定位精度不夠高，不能達到精確定位的目的；

（2）在噪聲環境下定位效果差，算法抗干擾能力差。

針對以上問題，本文提出了基于K-均值聚類算法[29]的無源目標定位技術。通過前期的稀疏恢復基礎，將多次估計結果作為K-均值聚類算法的初始聚類點；再采用K-均值聚類算法對目標結果進行優化，通過簇的劃分對聚類中心點進行迭代更新，并以迭代結束后的聚類中心點作為目標估計結果。本文主要貢獻有：

（1）K-均值聚類算法對目標定位優化問題有很好的兼容性，K-均值聚類算法和壓縮感知定位的有效結合在實現了對目標位置精確估計的同時，不增加算法的復雜度；

（2）在有噪聲的情況下，可以通過算法彌補定位偏差影響，降低誤差概率，同時增強魯棒性；

（3）本方法是一種提高定位精度的優化方案，為后續在定位精度上對算法進行改進提供了新思路。

1 壓縮感知原理

1.1 基本問題描述

若某個信號θ∈RN×1中最多包含K個非零元素，且K<

在實際應用中，某些信號雖然不滿足稀疏性，但在某個稀疏表示基B∈RN×N下是稀疏的，即θ=Bs，其中s∈RN×1為K階稀疏信號，即s∈SK。稱θ為K階條件稀疏信號。

對于稀疏信號θ，通過觀測矩陣Φ∈RM×N以低于奈奎斯特采樣的速率對其進行欠采樣，得到觀測向量y∈RM×1。根據壓縮感知理論，可根據觀測向量y以高概率重構原信號θ。具體地，觀測向量可以表示為：

式中：ε∈RM×1為測量噪聲向量。圖1 所示為稀疏信號的感知模型，其中M維觀測向量y可用觀測矩陣Φ和稀疏信號θ表示。

圖1 稀疏信號感知模型

若θ為條件稀疏信號，也可以通過觀測矩陣Φ以較低速率對其進行欠采樣，并根據得到的低維數據y，以高概率重構出原信號。此時，觀測值y可表示為：

式中：B為條件稀疏信號θ的稀疏表示基；s為稀疏信號表示系數。令D=ΦB，則式（3）可表示為：

式中：D∈RM×N為稀疏表示字典，其列向量dn∈RM×1，n=1,2,…,N屬于字典原子。

圖2 所示為條件稀疏信號的壓縮感知模型。其中，M維觀測向量y可以用稀疏表示字典D和稀疏信號s表示。

圖2 條件稀疏信號的壓縮感知模型

1.2 稀疏重構算法

稀疏重構算法是壓縮感知理論的核心內容，也是重構原信號的關鍵[30]。它是通過觀測矩陣Φ獲取的觀測值y為欠采樣數據，其維數M小于原信號的維數N。利用壓縮感知稀疏重構算法，可以在已知測量噪聲ε、觀測矩陣Φ以及觀測向量y的情況下，求解最為稀疏的信號作為重構信號θ。具體的計算公式為：

為了度量信號θ的稀疏性，將信號中非零元素的數目即θ的 ?0范數作為稀疏性指標。

基于變分貝葉斯推理的稀疏向量重構算法是當前重構算法中一個比較好的算法，此算法的測量模型如下：

式中：Ψ(1)∈RM×N和Ψ(2)∈RM×N為已知矩陣；ε∈RN×1為測量噪聲向量；ω(1)∈RN×1和ω(2)∈RN×1為稀疏表示系數。根據字典環境參數取值，向量ω(1)和ω(2)具有公共支撐集T?{1,2,…,N}。該稀疏表示模型中，要估計目標位置向量θ，需要同時重構出ω(1)和ω(2)，得到兩者的公共支撐集T，實現聯合稀疏重構。為了誘導ω(1)和ω(2)的聯合稀疏性，建立了兩層的高斯先驗模型。兩層先驗分布可表示為：

基于所建立的兩層高斯先驗模型，ω(1)和ω(2)的先驗分布可表示為：

利用變分貝葉斯推理估計隱含變量的后驗分布，可表示為：

式中：q*(w)為w的后驗分布；N(w|μ,Σ)表示自變量為w，均值為μ，協方差為Σ的高斯分布。

其中，

式中：μ(2)為w(2)后驗分布的均值向量；Σ(2)為w(2)后驗分布的協方差矩陣。

由于β服從伽馬分布，其后驗分布可表示為：

同理，α服從伽馬分布，其后驗分布可表示為：

基于以上結果，可通過迭代地更新隱含變量w(1)，w(2)，β和α的后驗分布，實現稀疏向量的重構。

2 K-均值聚類算法

聚類算法是一種對研究對象進行統計分類的方法，根據研究對象的相似性，將具有相似特征的對象分為同一類。聚類算法有多種具體方法，本文選取其中最具代表性的K-means 均值聚類算法進行分析講解，其具體流程如圖3 所示。具體步驟如下文所述。

圖3 K-均值聚類算法流程

（1）初始化聚類中心點。要想把研究對象分為K類，需要選取K個數據點作為初始化聚類中心點。

（2）對數據點進行聚類。以所有數據點到K個聚類中心點的歐式距離最小值進行分類，形成K類數據。

（3）更新聚類中心點。求每個簇中的數據點的橫縱坐標的算術平均值，把算術平均值作為新的聚類中心點，以此更新聚類中心點，并計算聚類完成后，各點到相應聚類中心點的歐式距離之和。

有目標才能有的放矢，目標管理工作首先要制定明確的工程目標，通常情況需要從以下幾方面推進：第一，管理人員要對施工企業的內部情況進行了解，充分掌握內部人物信息和工程數據后對工程項目本身進行研究，據此做出科學合理的目標定位。第二，先制定工程總目標，然后基于時間制定年度、季度、月度、旬、周等目標，基于空間制定各工種分目標，基于專業制定質量、進度、安全、成本等目標。

（4）迭代更新并停止。比較前后兩次聚類后歐式距離之和是否相等，若不相等則循環更新簇和聚類中心點，若相等則結束循環。

（5）輸出結果，即數據點分類情況和聚類中心點位置。

3 結合K-均值聚類算法的無源目標定位

3.1 定位模型

結合K-均值聚類算法的無源目標定位模型如圖4 所示。為了應用壓縮感知原理，首先需要對地面監測區域進行網格化處理，也就是將監測區域劃分為N個大小相同的正方形網格，并按順序編號，即1,2,3,…,n,…,N；其次用N維向量θN×1來表征K個目標位置信息，因為K<

圖4 結合K-均值聚類算法的無源目標定位模型

監測區域周圍部署有適量的傳感器裝置，用來收集監測區域內M條無線鏈路上接收信號強度的變化情況，以此反映目標引起的陰影效應，估計目標位置。在監測區域的N個網格內隨機放置K個目標，此時測量第m條無線鏈路上接收信號強度的值，再與目標監測區域為空時的接收信號強度作差，得到第m條無線鏈路的接收信號變化量。第m條鏈路在任意時刻t的接收信號強度值可表示為：

式中：ΔCm為時間t內，由目標造成的信號衰減變化量；Δvm為時間t內測量噪聲的變化量。

從上文可知，接收信號強度只與目標位置和測量噪聲變化有關，由于在初始時刻t0時，監測區域不存在目標，所以有：

式中：為t時刻時第m條鏈路上接收信號強度值。

因為無線傳感器接收到的信號同時受到多個目標的影響，當監測區域存在多個目標，并且各目標滿足稀疏分布時，可認為是多個目標對第m條鏈路所造成陰影效應的線性疊加，則第m條無線鏈路上接收信號強度的變化情況可表示為：

式中：θn為目標位置向量θ∈RN×1的 第n個 元素，當目標監測區域中第n個網格內存在目標時，θn=1，否則θn=0；?m,n為稀疏表示字典Φ∈RM×N的第(m,n)個元素。根據公式（28），可把M條鏈路上的接收信號強度變化表示為：

式中：y∈RM×1為觀測向量，其第m個元素ε∈RM×1為噪聲向量，其第m個元素εm=Δvm；由于目標個數K遠小于監測區域劃分的網格數N，因此θ為K階稀疏向量。

3.2 鞍面模型字典

鞍面模型中無線鏈路目標影響區域如圖5所示。

圖5 鞍面模型影響區域

在鞍面模型中，無線鏈路的目標影響區域為橢圓形影響區域。該橢圓的長半軸為λ1，短半軸為λ2，以該鏈路的中點為原心，以該鏈路的視距線為橫軸建立U-V坐標系，則位于該橢圓目標影響區域的網格滿足條件：

式中：(Um,n,Vm,n)表示網格n相對于鏈路m的坐標。圖5 中深色表示滿足約束條件的網格，對于處在橢圓形區域的網格，如果該網格內存在目標，則其對鏈路m上接收信號強度的影響可表示為：

式中：γ為接收信號強度的最大衰減；Ωm為該鏈路上最小信號衰減與γ的比值。

3.3 稀疏恢復中的網格修剪機制

如上文所述，稀疏恢復模型采用變分貝葉斯推理的稀疏重構算法，測量模型為：

由于字典環境參數取非零值作為特征值，則稀疏表示系數w(1)和w(2)具有公共支撐集T?{1,2,…,N}，所以基于該稀疏表示模型，要估計目標位置向量θ，需要同時重構w(1)和w(2)，實現聯合稀疏重構。

但因為存在噪聲的影響，導致重構稀疏向量會出現不嚴格稀疏的情況，其中包含一些數值較小的非零向量，考慮到這些是噪聲干擾下的不良影響，可忽略。因此可以通過閾值設定ηth來消除干擾，得到理想的重構稀疏向量以及目標位置。目標位置向量的支撐集估計公式如下：

修剪后可獲得目標位置的支撐集，可估計目標的位置，坐標集如下：

3.4 結合K-均值聚類算法的定位流程

圖6 為結合K-均值聚類算法的定位流程。

圖6 結合K-均值聚類算法的定位流程

式中：(xi,yi)為第i個數據點的坐標，i=1,2,…,10K；為第k個聚類中心點坐標，k=1,2,…,K；dik為第i個數據點到第k個聚類中心點的歐式距離，i=1,2,…,10K且k=1,2,…,K。通過比較，可以得到每個數據點到K個聚類中心點的距離最小值dimin，i=1,2,…,10K，并以此將數據點歸到相應的簇，相應的簇內數據點表示為ck=(xk1,xk2,…,yk1,yk2,…)，其中，k=1,2,…,K，簇內數據點的個數不定。分類完成后計算出所有點到各自聚類中心的距離之和D，計算方式為：

接下來繼續根據各數據點到聚類中心點的歐式距離繼續更新簇內數據點和聚類中心坐標，更新時配合網格修剪機制，將離聚類中心點距離超過1.5 m的網格判斷為誤差較大的情況，并將其修剪掉。如此循環迭代，直到滿足迭代條件，即沒有網格被修剪且前后兩次迭代的距離之和D無變化，則迭代結束，跳出循環。

最后，輸出結果，記錄下最后聚類中心點坐標，并將其作為最終的目標估計位置

4 實驗仿真與結果分析

本節通過仿真實驗驗證所提定位算法的性能。對比算法有基于貪婪匹配追蹤的無源目標定位算法（Device-free Localization Based on Greedy Matching Pursuit，DFL-GMP）、基于樹型正交匹配追蹤的無源目標定位算法（Device-free Localization Based on Tree-Based Orthogonal Matching Pursuit，DFLTOMP）、基于稀疏貝葉斯學習的無源目標定位算法（Device-free Localization Based on Sparse Bayesian Learning，DFL-SBL）、基于變分期望最大化的無源目標定位算法（Device-free Localization Based on Variational Expectation Maximization，DFL-VEM）。在仿真中，目標監測區域為14 m×14 m 的正方形區域，將其劃分為N=784 個大小相同的正方形網格，且覆蓋該區域的鏈路數M=56。假定Δεm(f)為加性的高斯白噪聲信號，并且信噪比可表示為。為了評價結合K-均值聚類算法的無源目標定位算法的定位性能，分別定義平均定位誤差（Average Localization Error，ALE）和準確率作為評判指標。ALE 為估計目標位置和真實位置間的平均歐式距離；準確率為估計目標位置和真實位置之間正確估計的百分比。結果如圖7 所示。

圖7 中*為可能的目標位置，○為真實的目標位置。可以看出K-均值聚類之前，基于VBI 的10次目標定位結果并不理想，有很多偏差較大的情況。

圖7 K-均值聚類之前的目標定位結果

圖8 表示網格圖中的聚類情況，其中○（注：黑色圓圈）為真實的目標位置，+、×、▽、☆、＊表示5 個類型，◇表示最終目標估計位置。通過最終聚類中心點的目標估計位置與實際目標位置結果比對可以看出，結合K-均值聚類算法的無源目標定位技術準確地估計出了真實的目標位置，證明K-均值聚類算法對定位結果有優化的效果，實現了無源目標的精確定位。

圖8 結合K-均值聚類的無源目標定位結果

圖9 中對比了在不同信噪比條件下，通過多次實驗得出的各種算法的平均定位誤差，可以看到，本方法相比于其他類型的方法有明顯的優勢。縱向對比，可以看到在15～35 dB 的信噪比區間內，本方法的平均定位誤差總是低于其他4 種方法。并且可以看出本方法相較于其他方法的抗干擾能力較強，在大于等于15 dB 的情況下，本方法的定位誤差幾乎穩定在了0.2～0.7 m 之內。由此可以看出本方法是一種定位精度高，且抗干擾能力強的定位技術。

圖9 不同信噪比下不同算法的ALE 對比

圖10 為在不同信噪比條件下，各種算法的準確率對比圖，從中可以更加明確地看到所提方法在定位準確性上的突出優勢，在大于15 dB 的信噪比之后，定位準確性高達90%，可見本方法的定位準確性相對較高。

圖10 不同信噪比下各種算法準確率對比

由以上結果分析可知，結合K-均值聚類算法的無源目標定位技術不僅定位精度高，而且抗干擾能力強。除此之外，采用K-均值聚類算法，在不增加算法復雜度的情況下，很好地達到了對無源目標定位問題優化的目的，為后續在定位精度和抗干擾能力的改進方面提供了新思路。

5 結語

為了解決當前無線傳感器網絡定位技術中定位精度差、定位準確性不高、抗干擾能力差的問題，本文設計了一種基于K-均值聚類算法的多目標定位技術。該方法在變分貝葉斯重構方法恢復目標向量的基礎上，添加K-均值聚類算法進一步對結果進行優化，運用K-均值聚類算法的優化特點，在加強定位精度的同時，又增強了定位算法的抗干擾能力，是一種有價值的定位方法。