WKPowerMeans多徑簇識(shí)別算法

楊晉生，吳旭曌

WKPowerMeans多徑簇識(shí)別算法

楊晉生，吳旭曌

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

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

多徑簇識(shí)別；KPowerMeans算法；信息熵；尖峰檢測(cè)

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

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

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

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

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

1 KPowerMeans算法

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

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

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

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

2 WKPowerMeans算法

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

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

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

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

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

圖3 SV模型功率時(shí)延譜Fig.3 PDP of SV model

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

式中ψ(·)為母小波．本文選擇Daubechies小波來進(jìn)行多徑能量的峰值檢測(cè)，因?yàn)橄啾扔谄渌〔?，Daubechies小波的瞬時(shí)消失特性更適于用來檢測(cè)信號(hào)的跳變點(diǎn)[8]．

2.2 多徑分量距離

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

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

2.3 信息熵加權(quán)

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)例分析

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

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

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

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

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

圖5 小波變換的能量跳變點(diǎn)Fig.5 Energy peak using wavelet transformation

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

3.1 聚類精確度分析

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

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

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

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

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

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

4 結(jié) 語

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

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

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

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