DBSCAN算法在無線網(wǎng)絡(luò)優(yōu)化中的應(yīng)用

魯飛，王任，翁維波，陳明，涂志龍

（1.中國移動通信集團(tuán)浙江有限公司寧波分公司，浙江 寧波 315040；2.杭州華星創(chuàng)業(yè)通信技術(shù)股份有限公司，浙江 杭州 310052）

1 引言

在無線網(wǎng)絡(luò)優(yōu)化中，故障、性能質(zhì)差、投訴等經(jīng)常呈現(xiàn)出空間聚集的區(qū)域特征，如何及時發(fā)現(xiàn)這些問題是網(wǎng)絡(luò)優(yōu)化的重點工作。終端用戶在通信過程中會產(chǎn)生海量的數(shù)據(jù)，收集這些數(shù)據(jù)并從這些數(shù)據(jù)中發(fā)掘出價值信息并應(yīng)用到網(wǎng)絡(luò)優(yōu)化工作中去是一個不錯的研究方向。

機器學(xué)習(xí)算法在各個行業(yè)中得到越來越廣泛的應(yīng)用。其中聚類算法是在不清楚數(shù)據(jù)類別的情況下，根據(jù)相似性將數(shù)據(jù)集劃分為不同的類簇，在數(shù)據(jù)挖掘領(lǐng)域有著廣泛的應(yīng)用。常用的聚類算法包括K_means（K均值聚類）、DBSCAN（密度聚類）、BIRCH（層次聚類）等。其中，DBSCAN算法和其他算法相比，它不需要預(yù)先確定類別數(shù)量，對噪聲不敏感，可以區(qū)分任意形狀的數(shù)據(jù)集，適合空間分布密度不同的數(shù)據(jù)聚類。本文在研究DBSCAN密度聚類算法的基礎(chǔ)上，遵循層次聚類的思想，依次應(yīng)用采樣點篩選、數(shù)據(jù)劃分、聚類、統(tǒng)計分析等方法探討機器學(xué)習(xí)算法在網(wǎng)絡(luò)優(yōu)化中的應(yīng)用。

以SINR質(zhì)差為例，干擾及弱覆蓋等都會引起SINR質(zhì)差導(dǎo)致網(wǎng)速降低，進(jìn)而影響用戶感知，傳統(tǒng)方法一般采用DT測試或MR性能統(tǒng)計確定質(zhì)差情況，存在人工耗費大且定位精度差的問題。終端在通信中產(chǎn)生大量包含SINR等測量信息的數(shù)據(jù)，并通過一些終端APP收集并上報，這些數(shù)據(jù)能直接反應(yīng)用戶當(dāng)時所在位置的網(wǎng)絡(luò)情況，但是現(xiàn)階段對這類數(shù)據(jù)的應(yīng)用還不充分，也缺少這類數(shù)據(jù)的聚類研究。

2 基于DBSCAN算法的SINR質(zhì)差聚類

2.1 SINR對下載速率的影響及質(zhì)差門限

TD-LTE下行SINR是有效參考信號功率和干擾信號及噪聲信號的比值，反映無線下行信號質(zhì)量。SINR決定網(wǎng)絡(luò)性能，將直接影響到終端的下載速率和用戶感知。SINR值和下載速率之間具有明顯的正相關(guān)性，下載速率會隨著SINR的惡化而變差。

TD-LTE網(wǎng)絡(luò)質(zhì)量評估測試規(guī)范要求覆蓋率按照RSRP≥-105 dBm和SINR≥0 dB統(tǒng)計。本文也以0 dB作為SINR的質(zhì)差門限，如果某個區(qū)域SINR低于0 dB的采樣點上報的越多，該區(qū)域SINR質(zhì)差的采樣點密度越高。

2.2 SINR質(zhì)差聚類的建模邏輯

手機終端在與無線通信網(wǎng)絡(luò)進(jìn)行信息交互的過程中，會不斷地檢測無線信號強度和質(zhì)量信息。假設(shè)網(wǎng)絡(luò)內(nèi)的終端分布均勻，質(zhì)差區(qū)域的質(zhì)差采樣點的密度一定會大于正常區(qū)域的密度。應(yīng)用DBSCAN密度聚類算法可以快速地篩選出SINR質(zhì)差密度較高區(qū)域，然后對目標(biāo)區(qū)域內(nèi)的樣本特性做統(tǒng)計，評估聚類結(jié)果的準(zhǔn)確度。質(zhì)差區(qū)域聚類流程如圖1所示。

（1）DBSCAN算法的技術(shù)原理

圖1 網(wǎng)絡(luò)質(zhì)差聚類流程圖

DBSCAN算法的基本思想就是計算某個eps半徑范圍內(nèi)采樣點的數(shù)量是否大于設(shè)定值minPts。其中eps和minPts是DBSCAN算法中最重要的兩個參數(shù)，分別限定算法的區(qū)域半徑和最少樣本點數(shù)量。

對于SINR質(zhì)差定位還有一些概念需要定義，這也是DBSCAN算法的主要概念。

定義1：SINR質(zhì)差核心點。如果eps鄰域內(nèi)的SINR質(zhì)差樣本點數(shù)量大于等于minPts，則鄰域內(nèi)的樣本點稱為質(zhì)差核心點。

定義2：SINR質(zhì)差邊界點。如果某個eps鄰域內(nèi)質(zhì)差樣本點數(shù)量小于minPts，但是它在其他核心點的鄰域內(nèi)，則稱為質(zhì)差邊界點。

定義3：SINR質(zhì)差噪音點。數(shù)據(jù)集內(nèi)既不屬于核心點也不屬于邊界點的質(zhì)差點。產(chǎn)生噪音數(shù)據(jù)的原因是由于快衰落等無線傳播特性導(dǎo)致的波動或者是用戶數(shù)據(jù)量太少等。

如圖2所示，設(shè)定minPts=11，數(shù)據(jù)集X={xi}為采樣點，x1的eps鄰域內(nèi)包含12個質(zhì)差點，則x1為核心質(zhì)差點；而x2的eps鄰域內(nèi)包含9個質(zhì)差點，但x2由于在x1的鄰域內(nèi)，其為邊界質(zhì)差點；x3不在其他樣本點的鄰域內(nèi)，其自己的鄰域內(nèi)樣本點數(shù)也少于11，為噪音點。

圖2 密度聚類示意圖

定義4：直接密度可達(dá)。如果某個樣本點在核心點x的鄰域內(nèi)，則該樣本點從核心點x直接密度可達(dá)。

定義5：密度可達(dá)。給定樣本序列x1, x2, …, xn，設(shè)xi=x1，假如從xi直接密度可達(dá)xi+1，那么從x1密度可達(dá)xn，密度可達(dá)滿足傳遞性。

定義6：密度相連。如果某兩個樣本點通過另外的樣本點密度可達(dá)，則稱這兩個樣本點密度相連。

定義7：SINR質(zhì)差簇。由密度相連的所有樣本點組成的密度區(qū)域，稱為一個SINR質(zhì)差簇，最小半徑是eps，不限定最大半徑。如圖2可以將x3以外的點聚類成一個質(zhì)差簇。

（2）DBSCAN算法的特點

DBSCAN密度聚類算法可以將滿足密度要求的相鄰區(qū)域連接起來，能有效處理噪聲數(shù)據(jù)，適合用于空間數(shù)據(jù)的聚類，但是也有比較顯著的缺點，主要有以下兩個方面：

1）當(dāng)數(shù)據(jù)量增大時，需要較大的內(nèi)存支持，I/O消耗也很大。

2）對于空間密度不均勻的數(shù)據(jù)，聚類間距相差很大時，聚類質(zhì)量較差，因為這種情況下參數(shù)minPts和eps選取困難。eps設(shè)置過大及minPts設(shè)置過小說明聚類條件比較寬松，導(dǎo)致噪音點被納入目標(biāo)類；反之則聚類條件較嚴(yán)苛，導(dǎo)致目標(biāo)簇判定為噪聲。

2.3 SINR質(zhì)差聚類的實現(xiàn)

（1）數(shù)據(jù)采集及數(shù)據(jù)處理

數(shù)據(jù)采集和預(yù)處理是數(shù)據(jù)挖掘分析的前提，所采集的數(shù)據(jù)集是與分析目標(biāo)相關(guān)的總數(shù)據(jù)的一個子集。某些APP插件在通信中可以自動采集一些網(wǎng)絡(luò)信息，包括但不限于設(shè)備號、服務(wù)小區(qū)、RSRP及SINR等字段。本文以研究SINR質(zhì)差定位為目標(biāo)，所以只采集部分與SINR質(zhì)差相關(guān)的字段，數(shù)據(jù)格式如表1所示。

手機檢測網(wǎng)絡(luò)信號的速度在毫秒級，APP插件則每10 s采集一次網(wǎng)絡(luò)信息，眾多用戶上報的數(shù)據(jù)量將非常巨大。為了增加數(shù)據(jù)的可信度，減少數(shù)據(jù)量，在采集數(shù)據(jù)的時候設(shè)定時間窗口并做均值處理。這里選擇1分鐘作為時間窗口，表1在時間窗口內(nèi)被匯聚成一條數(shù)據(jù)，均值更能反映終端用戶所在位置的網(wǎng)絡(luò)性能特征。

APP上報數(shù)據(jù)的大部分是正常的，而我們重點關(guān)注的是那些質(zhì)差的采樣點，所以在數(shù)據(jù)處理階段還可以過濾掉SINR值較好的數(shù)據(jù)，減少了DBSCAN算法對內(nèi)存和讀寫性能的要求。設(shè)定SINR≤3 dB，可以過濾掉那些基本不存在質(zhì)差的網(wǎng)絡(luò)區(qū)域。

（2）DBSCAN算法在SINR質(zhì)差聚類時的參數(shù)選擇

eps和minPts是DBSCAN算法的兩個重要參數(shù)，聚類結(jié)果對這兩個參數(shù)的設(shè)置非常敏感。一般會根據(jù)K-dist曲線圖選擇設(shè)置eps的大小，對于minPts的設(shè)置也有一些文獻(xiàn)討論，并提出了一些自適應(yīng)設(shè)定eps和minPts的方法，即通過分析數(shù)據(jù)集統(tǒng)計特性來自動確定eps和minPts參數(shù)，從而避免了聚類過程的人工干預(yù)，實現(xiàn)聚類過程的自動化，但是對于通信數(shù)據(jù)密度分布不均勻的情況并不理想，參數(shù)的設(shè)置還是需要結(jié)合實際，不斷地進(jìn)行優(yōu)化直到得到合適值。

LTE終端位置信息的采集精度受GPS衛(wèi)星信號的影響，室內(nèi)甚至沒有衛(wèi)星信號，鄰域半徑設(shè)置小于50 m的意義不大，本文設(shè)定質(zhì)差最小統(tǒng)計區(qū)域是方圓50 m的范圍。即使對于大面積的干擾區(qū)域，較小的鄰域半徑也不影響聚類結(jié)果。

由于移動通信用戶的分布很不均勻，終端測量數(shù)據(jù)的空間分布也不均勻。另外SINR樣本數(shù)據(jù)是每天累積起來的，單位區(qū)域內(nèi)的樣本點密度會不斷增加，這些都影響到minPts的選擇。如果對全局采用統(tǒng)一的minPts，則會影響聚類準(zhǔn)確度。具體的參數(shù)選擇按照以下三步進(jìn)行處理。

表1 數(shù)據(jù)采集信息表

首先，進(jìn)行大數(shù)據(jù)集劃分。對于密度不均勻的全局?jǐn)?shù)據(jù)，一些文獻(xiàn)提出來“分而治之”的改進(jìn)思想，或提出基于數(shù)據(jù)劃分的方法來選擇參數(shù)，主體思路都是類似的。本文遵循數(shù)據(jù)劃分和層次聚類的思想將數(shù)據(jù)集由大化小。如圖3（a）將23 km×10 km的區(qū)域人工劃分為5個密度大致相近的區(qū)塊（A/B/C/D/E）。也可采用DBSCAN、K-means等算法完成初步聚類，劃分出密度類似的較小區(qū)塊。本文采用DBSCAN算法，eps設(shè)置為100 m～500 m，minPts設(shè)置為5～15，做迭代運算后選擇聚類形態(tài)較好且噪聲較少的參數(shù)值用于數(shù)據(jù)集劃分。根據(jù)迭代結(jié)果，選擇eps=250 m，minPts=8作為數(shù)據(jù)劃分時的參數(shù)，全局區(qū)域劃分如圖3（b），顏色代表密度不同的數(shù)據(jù)集，可以看出不同密度區(qū)域基本區(qū)分開了且和人為劃分結(jié)果類似，其中3個區(qū)塊（A/D/E）為重點關(guān)注區(qū)域。但是也有些區(qū)域劃分過小，后續(xù)可以采用其他方法對區(qū)域進(jìn)行規(guī)整或直接判定為噪音，這里規(guī)定噪音不參與后續(xù)計算。

圖3 SINR樣本分布及初步劃分區(qū)塊

其次，對上一步產(chǎn)生的不同區(qū)塊做密度聚類。根據(jù)不同區(qū)塊的密度特征來設(shè)定不同minPts門限，密度較高的區(qū)塊采用較大的minPts，密度較低的區(qū)塊采用較小的minPts。區(qū)塊劃分后的密度聚類，可以采用并行方法進(jìn)行處理，提升算法的數(shù)據(jù)處理速度。這里選取E區(qū)塊進(jìn)一步聚類分析。minPts參數(shù)需要選擇不同的值做迭代計算，直到找到符合要求的參數(shù)值。圖4為E區(qū)塊eps=50 m，minPts選擇{10, 25, 30, 40}時的不同聚類結(jié)果。其中minPts等于30時的聚類結(jié)果形態(tài)較好且分類數(shù)量符合SINR質(zhì)差實際分布，所以區(qū)塊E選擇eps=50 m，minPts=30時的結(jié)果為質(zhì)差聚類結(jié)果。

最后，隨數(shù)據(jù)集變化的情況調(diào)整參數(shù)。比如數(shù)據(jù)集隨時間的累積而密度增加，要隨數(shù)據(jù)量的變化及時做minPts參數(shù)調(diào)整。一個方法是以一周的數(shù)據(jù)為基礎(chǔ)設(shè)定minPts的值，然后用累積的數(shù)據(jù)量和基礎(chǔ)數(shù)據(jù)的時長相比較得到的倍數(shù)乘以基礎(chǔ)minPts，可以得到變動后的minPts，minPts不符合要求時仍需要及時進(jìn)行調(diào)整。

3 聚類結(jié)果準(zhǔn)確性提升及驗證

3.1 質(zhì)差評估算法

對于密度不均勻的數(shù)據(jù)集，即使采用了初步區(qū)域劃分，較小區(qū)域內(nèi)的樣本分布仍不均勻。如果僅憑密度聚類結(jié)果就判定是否為質(zhì)差問題點還不夠充分，需要對聚類結(jié)果進(jìn)一步進(jìn)行分析評估。其主要思想是統(tǒng)計聚類區(qū)域內(nèi)質(zhì)差采樣點的數(shù)量占區(qū)域內(nèi)總采樣點的數(shù)量的比例以及特征均值，質(zhì)差點比例越高且均值越低，則其為質(zhì)差問題點的可能性越大，需要優(yōu)先處理。SINR質(zhì)差占比和簇內(nèi)SINR均值的計算公式如下：

圖4 E區(qū)塊不同minPts的聚類結(jié)果對比

以E區(qū)塊聚類結(jié)果為例，共得到12個質(zhì)差簇，其中簇3和簇5的質(zhì)差占比遠(yuǎn)大于其他簇，評估結(jié)果如表2所示。如果結(jié)合區(qū)域內(nèi)的信號強度就可以判斷質(zhì)差是弱覆蓋引起的還是干擾引起的，這將對網(wǎng)絡(luò)優(yōu)化工作具指導(dǎo)意義。

表2 E區(qū)塊聚類結(jié)果評估及實測

3.2 聚類結(jié)果驗證

E區(qū)塊聚類結(jié)果的空間分布如圖5所示，這些聚類點的現(xiàn)場實測結(jié)果如表2實測部分所示，測試結(jié)果表明聚類區(qū)域內(nèi)SINR值普遍偏低。雖然有些簇內(nèi)的SINR測試值高于質(zhì)差門限，這是因為測試發(fā)生在室外道路而用戶通信行為一般發(fā)生在室內(nèi)，所以SINR測試值和APP上報值有一定的差別。

圖5 E區(qū)塊聚類結(jié)果的分布圖

4 結(jié)束語

本文主要研究了DBSCAN密度聚類算法在基于大數(shù)據(jù)的網(wǎng)絡(luò)優(yōu)化中的應(yīng)用，介紹了SINR質(zhì)差干擾排查思想。針對密度不均勻的數(shù)據(jù)特性，通過數(shù)據(jù)處理、分層聚類和性能評估等方法，降低了DBSCAN的參數(shù)選擇難度，實現(xiàn)了對網(wǎng)絡(luò)質(zhì)差區(qū)域的排查及定位。實測結(jié)果表明：該方法聚類結(jié)果準(zhǔn)確，區(qū)域定位準(zhǔn)確性能滿足工作要求，但后續(xù)還要加強室內(nèi)APP定位精度的研究及實現(xiàn)minPts參數(shù)的自動化選擇。