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

陳方芳

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

1 引言

1.1 問題背景

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

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

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

1.2 研究現狀與文獻回顧

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

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

2 模型原理

2.1 K-means聚類算法

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

圖2 聚類分析建模原理

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

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

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

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

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

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

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

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

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

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

2.2 戴維森堡丁指數

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

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

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

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

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

3 模型準備與分析

3.1 實證分析數據給定

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

3.2 數據的區域化柵格結構

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

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

3.3 數據的初步整理

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

4 模型建立與求解

4.1 模型建立

4.1.1 建立聚類結果圖,計算聚類中心點

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

圖4 聚類結果圖

4.1.2 擬合區域弱覆蓋點,推選最優解法

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

圖5 區域中的弱覆蓋點

4.1.3 擬合現網站址坐標,得出聚類中心值以及類別

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

圖6 現網站站址坐標

4.2 模型求解

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

表1 現網址坐標聚類中心值

4.3 DBI指數聚類評估

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

圖7 指數變化情況

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

表3 時間復雜度評價分類

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

5 結語

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