基于聚類算法模型的移動通信基站站址的規(guī)劃研究

陳方芳

(黎明職業(yè)大學 通識教育學院,福建 泉州 362000)

1 引言

1.1 問題背景

移動通信飛速發(fā)展推動了5G網(wǎng)絡技術(shù)的廣泛應用,5G網(wǎng)絡大帶寬的特點大大提高了傳輸?shù)男?給人們帶來了極大的便利。運營商在努力滿足數(shù)據(jù)需求和新應用支持的建設過程中面臨一個關(guān)鍵問題就是基站密度的需求。所有無線通信都要面臨帶寬與覆蓋范圍之間的權(quán)衡,帶寬越大,每個基站能覆蓋的范圍就越小(如圖1)。

圖1 4G和5G無線信號傳播對比

新基站站址的選擇和參數(shù)配置[1],要遵循專業(yè)原則,合理規(guī)劃設計,確保網(wǎng)絡滿足覆蓋和容量等建設目標,在空間布局設計上保證基站規(guī)劃的科學性,追求提供更優(yōu)質(zhì)的客戶服務。實際的建設規(guī)劃中考慮到成本和一些其他因素必然會有區(qū)域弱覆蓋無法完全解決的情況,這時需要篩選出業(yè)務量高的弱覆蓋區(qū)域優(yōu)先安排解決。

1.2 研究現(xiàn)狀與文獻回顧

2019年6月6日,中國工信部向通信運營商發(fā)放5G商用牌照,我國正式進入5G商用階段。近幾年, 關(guān)于5G相關(guān)業(yè)務發(fā)展問題備受關(guān)注, 并對此展開了多層次、多角度的研究探討。

蘇麗芳2020年總結(jié)出我國未來建立健全電信業(yè)法律規(guī)制可資借鑒的有益經(jīng)驗[2]。高德金(2023)探討了5G網(wǎng)絡建設規(guī)劃中對無限資源配置的方法和準則[3]。何麗(2022)根據(jù)高鐵無線通信網(wǎng)絡建設需求,對5G網(wǎng)絡在高速鐵路環(huán)境下部署的參數(shù)及面臨的問題進行研究[4]。學者們從不同角度對5G時代的發(fā)展展開了不少研究。但是截至2023年3月4日0時,以“5G基站”為主題在中國知網(wǎng)數(shù)據(jù)庫中進行檢索后,再以“聚類分析”為主題,在結(jié)果中檢索到的文獻總數(shù)只有6篇[5-10]。可見,對5G基站結(jié)合聚類分析的研究非常少,而對5G基站弱覆蓋區(qū)域的研究更是匱乏?；诖?本文運用聚類算法中的K-means聚類算法,與戴維森堡丁指數(shù)相結(jié)合,探索通過總時間復雜度盡量低的聚類模型,對弱覆蓋點進行區(qū)域聚類得到弱覆蓋區(qū)域,以期實現(xiàn)對不同的弱覆蓋區(qū)域分開管理,使得可以更好的解決弱覆蓋問題。

2 模型原理

2.1 K-means聚類算法

K-means聚類算法[11]在對所研究對象進行分類時,著眼于分類對象具體特征的相似程度,在劃分類別的過程中盡量使得不同類別對象之間的差異性最明顯,反之;對于同一類別中的分類對象則是具有盡量相似的具體特征,這樣以研究對象樣本間的相似與差異程度為依據(jù)的分類原則可以歸納為“增大類內(nèi)聚,減少類間距”(如圖2)。聚類屬于非監(jiān)督學習,K均值聚類是最基礎常用的聚類算法。它的基本思想是,通過迭代尋找k個簇(Cluster)的一種劃分方案,使得聚類結(jié)果對應的損失函數(shù)最小。其中,損失函數(shù)可以定義為各個樣本距離所屬簇中心點的誤差平方和:

圖2 聚類分析建模原理

其中Xi代表i個個體、Ci是Xi的簇、μCi代表簇對應的中心、M是樣本總數(shù)。

K-means聚類算法以空間中k個點為中心進行聚類,對最靠近他們的對象歸類。逐次計算各簇中心的值為新的中心值,迭代更新,直至簇中心位置不再改變或者達到最大迭代次數(shù)。其聚類具體過程[12]如下:

(1)首先確定一個k值,即我們希望將數(shù)據(jù)集經(jīng)過聚類得到k個集合;

(2)從數(shù)據(jù)集中隨機選擇k個數(shù)據(jù)點作為質(zhì)心;

(3)對數(shù)據(jù)集中每一個點,計算其與每一個質(zhì)心的距離(如歐式距離),離哪個質(zhì)心近,就劃分到那個質(zhì)心所屬的集合;

(4)把所有數(shù)據(jù)歸好集合后,一共有k個集合,重新計算每個集合的質(zhì)心;

(5)如果新計算出來的質(zhì)心和原來的質(zhì)心之間的距離小于某一個設置的閾值(也就是新計算出來的質(zhì)心坐標位置相較之前沒有明顯變化,具有一定的穩(wěn)定性,我們稱之為達到收斂的狀態(tài)),這時可以認為聚類已經(jīng)達到期望的結(jié)果,算法終止;

(6)如果新質(zhì)點和原質(zhì)點距離變化很大,需要迭代3～5步驟。

用K-means聚類算法對數(shù)據(jù)進行聚類分析前,需要對給定的原始數(shù)據(jù)進行必要的數(shù)據(jù)清洗,把孤立的不合理的點進行剔除,以免影響聚類結(jié)果的精確度。根據(jù)以上的分析步驟可以將K-means聚類算法計算過程用以下流程圖表示(圖3):

圖3 K-means聚類算法計算流程圖

2.2 戴維森堡丁指數(shù)

戴維森堡丁指數(shù)(DBI)[13]是由大衛(wèi)L·戴維斯和唐納德·Bouldin提出的一種評估聚類算法優(yōu)劣的指標。它是一個內(nèi)部衡量的指標,即對于聚類效果的評估,是通過使用數(shù)據(jù)集內(nèi)部的數(shù)量和特征進行衡量的,主要考慮不同類間數(shù)據(jù)離散程度和同一類內(nèi)數(shù)據(jù)的緊密性。DBI指數(shù)是計算任意兩類別的類內(nèi)距離平均距離之和除以兩聚類中心距離求最大值,它先根據(jù)簇的直徑的長度找到與直徑最相似的簇,然后計算它們之間的相似度,最后算得整個聚類結(jié)果的平均相似度。具體計算指標如下:

(1)首先定義聚類中n個m維樣本點之間的平均值avg,它表明了簇內(nèi)點的分散程度,代表了簇內(nèi)的所有點到簇中心的平均距離:

(2)根據(jù)兩個類內(nèi)樣本間的平均距離,得到DBI指數(shù)的計算公式如下:

其中,ci和cj表示類Ci和Cj的聚類中心,k代表著簇中心表征的第k個值,而‖ci-cj‖則是第i個簇和第j個簇之間的中心距離。最后,通過一個基于簇的個數(shù)的平方為時間復雜度的循環(huán),來找到每個簇和剩下所有簇中的哪個相似度最高(表現(xiàn)最差的結(jié)果),在對所有相似度之和做平均就能得到戴維森堡丁指數(shù)。

戴維森堡丁指數(shù)(DBI)的值越小,意味著類內(nèi)距離越小,同時類間距離越大,即類內(nèi)相似度高,類間相似度低,說明聚類結(jié)果越好,給定的聚類個數(shù)越接近真實的聚類個數(shù)。

3 模型準備與分析

3.1 實證分析數(shù)據(jù)給定

本文對模型實證分析的數(shù)據(jù)來源于2022 年第十二屆 MathorCup 高校數(shù)學建模挑戰(zhàn)賽中D題提供的材料[14]。給定材料的數(shù)據(jù)包含給定討論區(qū)域目前弱覆蓋點的已知信息,包括各個弱覆蓋點的坐標指數(shù)、現(xiàn)有網(wǎng)絡基站對應的業(yè)務量以及弱覆蓋點區(qū)域的業(yè)務量信息,一共552,849條數(shù)據(jù)。為了更好的解決弱覆蓋問題,需要對弱覆蓋點進行區(qū)域聚類,把距離近的弱覆蓋點聚成一類,可以得到弱覆蓋區(qū)域,這樣可以對不同的弱覆蓋區(qū)域分開管理使得可以更好的解決弱覆蓋問題。

3.2 數(shù)據(jù)的區(qū)域化柵格結(jié)構(gòu)

對已知數(shù)據(jù)進行區(qū)域化柵格結(jié)構(gòu)的處理方法操作簡單,尤其適用于對數(shù)據(jù)量較大時的空間聚合研究。數(shù)據(jù)的柵格化[15]首先需要對研究的數(shù)據(jù)空間通過規(guī)律性的網(wǎng)格進行劃分,然后對每個網(wǎng)格所對應的單元用對應的屬性值進行標志,在劃分的過程中數(shù)據(jù)的區(qū)域化柵格結(jié)構(gòu)的精確度決定于所劃分柵格的大小。通過對數(shù)據(jù)空間進行柵格化聚合分析,可以實現(xiàn)對異網(wǎng)覆蓋的地理化指標的分析和評估。

為了計算過程的簡化,在進行柵格劃分的過程中,用很小的柵格對給定區(qū)域進行劃分,并且將每個小柵格視作一個個點,這樣任意給定的區(qū)域就都可以相應地被劃分為有限個的點。這些點都包含相應柵格范圍的屬性,包括點的坐標、是否屬于弱覆蓋點以及相應的業(yè)務量等。

3.3 數(shù)據(jù)的初步整理

實現(xiàn)對所有弱覆蓋點進行有效聚類,并且使得聚類所用方法的總時間復雜度盡量低,需要先對給定數(shù)據(jù)進行初步整理。移動網(wǎng)絡站址在規(guī)劃建設中要求不同基站站址之間的距離不能小于等于給定門限10,這就包括了新建基站站址之間距離和新基站與原有基站站址之間的距離,所以,我們需要先對題目附件給出的數(shù)據(jù)進行數(shù)據(jù)清洗,也就是將弱覆蓋點坐標和舊基站點坐標之間的門限低于10的點進行剔除。通過Excel軟件對數(shù)據(jù)進行整理和篩選,除去數(shù)據(jù)多余化,獲得有效數(shù)據(jù)量377,646條。

4 模型建立與求解

4.1 模型建立

4.1.1 建立聚類結(jié)果圖,計算聚類中心點

通過Matlab[16]建立出聚類結(jié)果圖(圖4),選擇特征空間內(nèi)的k個點,設置為聚類中心的初始值,依次計算其他每個點到這個中心點的距離,選擇K-means求平均的方法,計算并選擇最近的一個點標記為新的聚類中心,然后再計算并獲取新的聚類中心點。

圖4 聚類結(jié)果圖

4.1.2 擬合區(qū)域弱覆蓋點,推選最優(yōu)解法

擬合出區(qū)域中的弱覆蓋點(圖5),可以觀察到弱覆蓋點的大概位置,選擇基站要盡量在較為密集的區(qū)域。區(qū)域中的覆蓋坐標分布較為偏遠地區(qū),中心受影響小,通過區(qū)域的弱覆蓋點方位的規(guī)劃,推選最優(yōu)的解法。

圖5 區(qū)域中的弱覆蓋點

4.1.3 擬合現(xiàn)網(wǎng)站址坐標,得出聚類中心值以及類別

根據(jù)現(xiàn)有數(shù)據(jù)值,擬合出現(xiàn)網(wǎng)站址坐標(圖6),增加基站盡量選擇較為稀疏的地方,比如圖中圓圈的地方。使用 K-means 聚類進行分析,得出了聚類中心值以及類別。

圖6 現(xiàn)網(wǎng)站站址坐標

4.2 模型求解

借助Excel對最佳數(shù)據(jù)值進行編輯運算,得到現(xiàn)網(wǎng)站址坐標的聚類中心值(表1)和聚類頻數(shù)與百分比情況(表2)。

表1 現(xiàn)網(wǎng)址坐標聚類中心值

4.3 DBI指數(shù)聚類評估

使用Matlab對其中100個聚類中心點計算DBI指數(shù)如圖7所示。

圖7 指數(shù)變化情況

進一步地,根據(jù)DBI指數(shù)的變化情況,得到時間復雜度評價情況,表3是時間復雜度數(shù)據(jù)按區(qū)間分類匯總情況。

表3 時間復雜度評價分類

通過DBI指數(shù)對聚類方法進行聚類評估,100個聚類中心點中只有17個是屬于時間復雜度非常高的情況,評估效果較好。

5 結(jié)語

5G基站站址的選擇和參數(shù)配置要遵循專業(yè)原則,合理規(guī)劃,本文在充分考慮業(yè)務量的情況下,結(jié)合信號分布,基于柵格數(shù)據(jù)結(jié)構(gòu)的基礎上,通過對數(shù)據(jù)進行Matlab軟件擬合繪圖,確定決策變量和約束條件,對弱覆蓋點進行K-means聚類分析,然后對結(jié)果進行綜合取優(yōu)的方式在限定的區(qū)域范圍內(nèi)選擇最有價值的解,實現(xiàn)對相應范圍內(nèi)的基站選址進行合理規(guī)劃,列表給出宏基站和微基站的規(guī)劃址坐標信息,可以在盡量降低時間復雜度的基礎上,實現(xiàn)對不同的弱覆蓋區(qū)域分開管理,形成高價值問題區(qū)域,使5G基站資源的高價值充分落實,對移動通信基站站址的規(guī)劃提出有效建議。