楊晉生，吳旭曌

WKPowerMeans多徑簇識別算法

楊晉生，吳旭曌

(天津大學(xué)電子信息工程學(xué)院，天津 300072)

針對KPowerMeans聚類算法多徑散射簇的估計過程復(fù)雜及聚類結(jié)果高度依賴隨機初始簇中心的問題，提出了一種改進的多徑簇識別算法——WKPowerMeans算法．首先利用小波變換的尖峰檢測技術(shù)估計出多徑散射簇的數(shù)目和初始簇中心的位置，然后以結(jié)合了多徑功率加權(quán)的多徑分量距離為準(zhǔn)則進行多徑簇聚類．仿真結(jié)果表明：與KPowerMeans算法相比，采用所提出的WKPowerMeans算法能得到更穩(wěn)定、準(zhǔn)確的聚類結(jié)果，而且具有較低的時間復(fù)雜度．

多徑簇識別；KPowerMeans算法；信息熵；尖峰檢測

在無線通信中，電磁波的傳播可以用傳播徑近似表征．傳播徑可以通過一個多維參數(shù)集描述，該參數(shù)集一般包括能量、時延、到達角和離開角等多徑特性．一般將具有相近參數(shù)的多徑歸為一個簇進行統(tǒng)計特性研究，一些主流的無線寬帶信道模型(SCM/SCME/WINNER)都是基于多徑散射簇進行建模的．對傳播徑進行簇識別的準(zhǔn)確性有助于分析多徑簇的生滅過程和多徑分量的簇統(tǒng)計特性，進而影響信道建模的準(zhǔn)確性．

多徑簇識別算法是目前基于多徑簇的信道建模和信道特性分析領(lǐng)域的研究熱點．將模式識別中的聚類算法應(yīng)用于無線信道自動簇識別研究的多徑簇識別算法大致分為3類：基于層次的多徑簇識別聚類算法[1]、基于劃分的多徑簇識別聚類算法[2]和基于密度的[3]多徑簇識別聚類算法．

基于劃分的聚類算法的代表是KMeans算法．文獻[2]提出了一種基于KMeans算法的改進的簇識別算法KPowerMeans，此算法在計算相互鄰近的多徑的距離時考慮了多徑功率的影響，并且引入了2個衡量聚類效果的參數(shù)來確定多徑簇的數(shù)目．但該算法沒有考慮多徑屬性的差異性對多徑加權(quán)因子的影響，并且有嚴重依賴于對初始聚類中心的選擇、容易陷入局部最優(yōu)解等缺陷．針對這些不足，本文引入了小波變換和信息熵自適應(yīng)加權(quán)技術(shù)以改進KPowerMeans聚類算法．

本文提出的改進KPowerMeans算法在進行多徑聚類之前通過小波尖峰檢測技術(shù)確定多徑簇的數(shù)目及初始簇中心，有效克服了KPowerMeans算法對初始聚類中心的敏感性，然后根據(jù)多徑的屬性對于分類不同的貢獻度，利用信息熵原理對多徑分量距離進行特征加權(quán)以提高分類精度．由于引入了小波尖峰檢測技術(shù)和自適應(yīng)信息熵加權(quán)算法，筆者將此算法命名為WKPowerMeans(wavelet weighted KPowerMeans)算法．

本文詳細介紹了所提出的改進算法的框架、流程及相關(guān)技術(shù)，并通過仿真給出了與文獻[2]算法的性能比較．

1 KPowerMeans算法

KPowerMeans算法通過對可能范圍內(nèi)的多徑簇的數(shù)目[Kmin，Kmax]進行多徑聚類，引入了2個衡量聚類效果的參數(shù)CH(calinski-harabasz)和DB(daviesbouldin)，取最大的CH或DB指數(shù)所對應(yīng)的K作為最優(yōu)的的多徑簇的數(shù)目[4]．KPowerMeans算法的具體流程如圖1所示，步驟如下所述．

圖1 KPowe rMeans算法流程Fig.1 Flow chart of KPowerMeans algorithm

步驟2 將不同多徑分量分配給不同的簇，并保存索引值．

步驟3 重新計算K個簇中心的位置cK(0)，根據(jù)新分配的每一個簇內(nèi)的多徑信息，使得簇內(nèi)多徑的差異性之和D最小，即

2 WKPowerMeans算法

本文提出的WKPowerMeans算法的基本流程和KPowerMeans算法有相同的框架，但在具體步驟中有所改進．流程如圖2所示．

圖2 WKPowerMeans算法流程Fig.2 Flow chart of WKPowerMeans algorithm

WKPowerMeans算法的改進點在于：在步驟1中，采用小波變換的尖峰檢測技術(shù)代替隨機選擇，這種帶監(jiān)督的聚類算法能克服對初始聚類中心的敏感性，從而獲得穩(wěn)定的聚類效果；步驟2中，在考慮了多徑功率影響的基礎(chǔ)上，引入信息熵原理計算多徑屬性自適應(yīng)加權(quán)的多徑分量距離(MCD)．

2.1 小波尖峰檢測技術(shù)

根據(jù)Saleh-Valenzuela信道模型的描述[5]，接收信號的多徑分量以簇的形式到達，并且多徑幅度大小呈雙指數(shù)形式衰減．圖3所示為Saleh-Valenzuela信道模型的功率時延譜(power delay profile，PDP)．

圖3 SV模型功率時延譜Fig.3 PDP of SV model

這種多徑成簇的現(xiàn)象導(dǎo)致功率時延譜有明顯的尖峰，因而可采用小波變換來得到多徑能量的跳變點的位置[6]．小波基函數(shù)一般可用尺度參數(shù)α和位移參數(shù)β來表示[7]．對信道沖擊響應(yīng)CIR進行小波變換，可得到

式中ψ(·)為母小波．本文選擇Daubechies小波來進行多徑能量的峰值檢測，因為相比于其他小波，Daubechies小波的瞬時消失特性更適于用來檢測信號的跳變點[8]．

2.2 多徑分量距離

文獻[9]用多徑分量距離來衡量多徑分量之間、簇心之間、多徑分量和簇心之間的距離，即多徑分量i與j之間的距離可表示為

式中：wAOA、wAOD、wτ分別表示dAOA,ij、dAOD,ij、dτ,ij等不同屬性參數(shù)所對應(yīng)的權(quán)值；dAOA,ij和dAOD,ij分別表示到達角、離開角的角度距離MCD值；dτ,ij為多徑時延的多徑分量距離；stdτ為時延的標(biāo)準(zhǔn)差．

2.3 信息熵加權(quán)

由于不同的多徑屬性對MCD的影響權(quán)值隨著不同的場景、頻段而變化．借助信息論中的信息熵原理[10]，本文提出的改進算法根據(jù)各多徑屬性的變異程度，計算各多徑屬性對MCD的權(quán)重影響因子，為無序數(shù)據(jù)對象集聚類提供依據(jù)[11]．

(1) 假設(shè)有n條多徑(即n個待聚類數(shù)據(jù)對象)，每一徑數(shù)據(jù)對象具有m維屬性．根據(jù)實時數(shù)據(jù)可構(gòu)造一個n×m大小的屬性值矩陣，即

式中xij為第i條多徑分量的第j維屬性．

本文的算法中取m=3，分別對應(yīng)多徑的到達角AOA、離開角AOD和時延τ這三維信道的屬性參數(shù).

(2) 計算第j維屬性對應(yīng)的第i個數(shù)據(jù)對象的屬性值比重．由于角度屬性的范圍是(-π，π]，為保證計算的影響因子為正數(shù)，將角度數(shù)據(jù)集進行線性映射變換，即將數(shù)據(jù)壓縮到區(qū)間[0，1]上，再計算其屬性比重，即

式中：Mij為xij屬性值所占比重；j∈[1，m]且j∈Z；i∈[1，n]且i∈Z．

(3) 計算第j維屬性的熵值．

式中Hj為屬性熵值，當(dāng)Mij=0時，令Hj=0．(4) 計算第j維屬性的差異性系數(shù)．

式中qj為差異性系數(shù)．qj越小，該屬性的聚類作用就越?。?/p>

(5)計算第j維屬性的權(quán)值比重．

式中0≤wj≤1．∑wj=1，j∈[1，m]且j∈Z．將得到的各屬性的權(quán)值wj帶入式(5)，用于計算多徑分量的MCD．而KPowerMeans聚類算法在進行多徑簇的識別的過程中，將屬性參數(shù)的權(quán)值wj分別設(shè)置為經(jīng)驗值[12]：wAOA=0.5，wAOD=0.5，wτ=5，不具有普適性．

3 實例分析

本文以3,GPP的SCM信道模型[13]為例，實際測量中可通過SAGE算法進行信道參數(shù)的提取，得到每一條多徑分量的到達角AOA、離開角AOD和時延信息．本文使用多徑分量的信道參數(shù)由3,GPP的SCM信道模型自動生成，沒有涉及信道參數(shù)的提取過程．根據(jù)SCM模型的定義，所有的角度信息均為二維的方位角(不考慮俯仰角)．然后利用本文提出的WKPowerMeans算法對多徑分量進行聚類分析，并與文獻[2]提出的KPowerMeans算法的聚類結(jié)果進行分析比較．

SCM模型設(shè)置為收發(fā)端均采用8元均勻線性天線陣，天線間隔為0.5,λ，場景設(shè)置為城市微小區(qū)(urban micro)．SCM信道模型中的多徑時延通過指數(shù)分布確定(其中均方根時延擴展為高斯分布的隨機變量)，而每一路徑的到達角與離開角由均勻分布的簇到達角和服從拉式分布的簇內(nèi)偏移角度隨機變量疊加構(gòu)成．

圖4是從SCM信道沖擊響應(yīng)提取的多徑分量的到達角AOA、離開角AOD和時延的分布．圖中每一個點表示每一條多徑分量，每一個點的灰度值表示此多徑分量的功率．圖中，通過SCM信道模型得到的多徑分量共有120條，可分辨出6組多徑散射簇．

圖5為對信道沖擊響應(yīng)CIR進行3層小波分解后的一級細節(jié)信號的小波系數(shù)．圖中的能量峰值即為多徑能量的跳變點的位置，即每一多徑散射簇中的能量主徑．能量峰值的數(shù)目即檢測到的多徑散射簇的數(shù)目，能量峰值所對應(yīng)的x軸的數(shù)值即是簇的中心位置所對應(yīng)的多徑分量的編號．可見，采用尖峰檢測技術(shù)不僅確定了多徑散射簇的數(shù)目K=6，同時還得到了聚類算法的初始簇中心的位置x=(4，25，44， 64，81，102)．

圖4 信道沖擊響應(yīng)的一次實現(xiàn)Fig.4 Snapshot of channel impulse response

圖5 小波變換的能量跳變點Fig.5 Energy peak using wavelet transformation

圖6 為分別采用KPowerMeans算法和WKPower Means算法對圖4中SCM模型得到的多徑分量進行自動簇識別的結(jié)果對比．不同形狀的點標(biāo)識用于區(qū)分多徑分量所屬的不同的多徑散射簇．圖6(a)和圖6(b)顯示的KPowerMeans算法聚類的結(jié)果與圖4所示有偏差，原本不屬于同一散射簇的多徑分量被錯誤地歸為一類．通過圖6(a)和圖6(b)對比還顯示，由于初始簇中心位置的隨機性導(dǎo)致每一次聚類的結(jié)果不盡相同．圖6(c)顯示的結(jié)果則為通過本文提出的WKPowerMeans算法得到的多徑散射簇的分布圖．多次仿真的結(jié)果顯示，由于采用小波變換的尖峰檢測技術(shù)，唯一地確定了初始簇中心位置，從而保證了聚類結(jié)果的唯一性．

3.1 聚類精確度分析

表1為2種算法對SCM信道模型的多徑數(shù)據(jù)集的聚類精確度比較，改進后的WKPowerMeans算法的聚類精確度不僅提高到98.33%，并且由于所有的多徑簇都以每個多徑簇中的最強徑為中心，不會出現(xiàn)文獻[2] WKPowerMeans算法的聚類結(jié)果不穩(wěn)定的情況．

表1 兩種算法的聚類比較Tab.1 Comparison of two kinds of clustering algorithm

圖6 自動多徑簇識別結(jié)果Fig.6 Results of automatic clustering identifitio n

3.2 時間復(fù)雜度分析

KPowerMeans算法由于需要先通過遍歷可能范圍內(nèi)的多徑簇的數(shù)目[Kmin，Kmax]進行多徑聚類，取最大的CH或DB指數(shù)所對應(yīng)的K作為最優(yōu)的多徑簇的數(shù)目．其算法的時間復(fù)雜度為O(Ltkn)，其中n為待聚類數(shù)據(jù)對象數(shù)，k為聚類的類數(shù)，t為聚類穩(wěn)定的迭代次數(shù)，L為可能的多徑簇數(shù)目的范圍(L=Kmax-Kmin+1)．

本文提出的WKPowerMeans算法由于利用信道沖擊響應(yīng)的特性直接確定多徑簇的數(shù)目，其時間復(fù)雜度為O(tkn)，是KPowerMeans算法的1/L．

4 結(jié) 語

針對KPowerMeans算法確定類別數(shù)的過程復(fù)雜和由于隨機簇中心導(dǎo)致聚類結(jié)果不穩(wěn)定的問題，本文提出的WKPowerMeans算法采用小波尖峰檢測技術(shù)進行初始聚類中心點選擇和多徑簇數(shù)目的估計，并根據(jù)待聚類的數(shù)據(jù)集進行自適應(yīng)的屬性加權(quán)，強化了不同屬性對多徑分量距離(MCD)的聚類影響．仿真結(jié)果表明：相比于KPowerMeans算法，本文提出的WKPowerMeans算法提高了多徑簇識別的穩(wěn)定性和準(zhǔn)確度，降低了時間復(fù)雜度．

［1］ Czink N，Mecklenbrauker C，Del G G. A novel automatic cluster tracking algorithm [C]// IEEE 17th International Symposium on Personal，Indoor and Mobile Radio Communication. Helsinki，F(xiàn)inland，2006：1-5.

［2］ Czink N，Cera P，Salo J，et al. A Framework for automatic clustering of parametric MIMO channel data including path powers [C] // IEEE 64th Vehicular Technology Conference 2006. Montreal，Canada，2006：1-5.

［3］ Bernado L，Roma A，Czink N，et al. Cluster-based scatterer identification and characterization in vehicularchannels [C] // Wireless Conference 2011 Sustainable Wireless Technologies(European Wireless)，11th European. Vienna，Austria，2011：1-6.

［4］ Li Tian，Yin Xuefeng. Multi-path grouping using a novel clustering algorithm for stochastic channel modeling[C]// 2010 6th International Conference on Wireless Communications Networking and Mobile Computing(WiCOM). Chengdu，China，2010：1-4.

［5］ Saleh A A M，Valenzuela R. A statistical model for indoor multipath propagation [J]. IEEE Journal on Selected Areas in Communications，1987(5)：128-137.

［6］ Liang J Y，Zhao X W，Li D Y，et al. Determining the number of clusters using information entropy for mixed data [J]. Pattern Recognition，2011，45：2251-2265.

［7］ Du Pan，Kibbe W A，Lin S M. Improved peak detection in mass spectrum by incorporating continuous wavelet transform-based pattern matching[J]. Bioinformatics，2006，22(17)：2059-2065.

［8］ Fard P J M，Moradi M H，Tajvidi M R. A Novel approach in R peak detection using hybrid complex wavelet(HCW)[J]. International Journal of Cardiology， 2008，124(2)：250-253.

［9］ Czink N. Improving clustering performance using multipath component distance[J]. Electronics Letters，2006，42(1)：33-35

［10］ Zhang Zhen，Yeung R W. On characterization of entropy function via information inequalities [J]. IEEE Transactions on Information Theory，1998，44(4)：1440-1452.

［11］ Jing Liping，Ng M K，Huang J Z. An entropy weighting k-means algorithm for subspace clustering of highdimensional sparse data [J]. IEEE Transactions on Knowledge and Data Engineering，2007，19(8)：1026-1041.

［12］ Huang J Z，Ng M K，Rong H Q，et al. Automated variable weighting in k-means type clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(5)：657-668.

［13］ Salo J，Galdo D G，Salmi P，et al. MATLAB implementation of the 3,GPP spatial channel model(3,GPP TR 25.996)[EB/OL]. http： //www.ist-winner.org/3gpp_scm. html，2012-07-06.

(責(zé)任編輯：金順愛)

WKPowerMeans Approach to Multipath Cluster Identification

Yang Jinsheng，Wu Xuzhao
(School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China)

In order to solve the problems of KPowerMeans multipath cluster recognition algorithm，which has a complex process of multipath scattering cluster estimation and whose clustering result is highly dependent on the random initial cluster cancroids. An improved algorithm，named WKPowerMeans，is proposed. The peak detection and information entropy methods are combined to develop the framework of automatic cluster identification. The improved algorithm not only acquires the number of cluster and initial centroids by using the wavelet transformation，but also adaptively obtains the different weights of the attributes of the multipath component. Simulation results indicate that the proposed WKPowerMeans clustering method can produce more robust and more accurate solutions than KPowerMeans method；furthermore it has lower time complexity.

multipath cluster identification；KPowerMeans algorithm；information entropy；peak detection

TN929

A

0493-2137(2014)03-0237-06

10.11784/tdxbz201209015

2012-09-06；

2012-12-14.

國家科技重大專項資助項目(2010ZX03005-001).

楊晉生（1965— ），男，博士，副教授．

楊晉生，jsyang@tju.edu.cn.