基于加權K-means聚類算法的機動通信網絡自動劃分方法

王均春 冀云剛

摘要：針對機動通信網絡規劃中的網絡劃分需求，提出了一種基于加權K-means聚類算法的網絡自動劃分方法。算法通過采用Elbow方法確定聚類數量，并在初始聚類中心選擇中考慮了節點連通度，克服了傳統K-means算法初始聚類中心的不確定性，通過對不同特征分配相應權重，進一步提升了聚類效果。實驗結果說明該算法在機動通信網絡自動劃分中具有良好的準確率，為后續網絡規劃提供了基礎支撐。

關鍵詞：網絡劃分;加權K-means;網絡規劃;節點聯通度

中圖分類號：TP393文獻標志碼：A文章編號：1008-1739（2022）02-56-4

0引言

機動通信網絡是為保障特殊任務而臨時開設的綜合性通信網絡，具有快速開設、組織結構復雜、動態變化等特點。機動通信網絡規劃負責在網絡開設前，根據通信保障需求統籌安排各類通信資源，進行網絡拓撲規劃、頻率規劃、IP規劃等，生成網絡開通所需的規劃參數文件，確保網絡快速開通。其中，網絡拓撲規劃是基礎。在開展其他規劃工作前，需先根據網絡拓撲結構和網絡組成，將整個網絡劃分成若干相對獨立的子網，然后再基于子網劃分結果進行各子網的頻率分配、IP地址規劃、路由協議規劃、聚合路由規劃等。目前在進行子網劃分時，一般多采用人工劃分或按所屬單位固定劃分方式，缺少自動化手段，無法適應機動通信網絡組織結構靈活多變的特點。尤其是當網絡規模較大時，對規劃人員要求高，影響網絡規劃效率。

K-means算法[1]作為一種經典的聚類算法，能夠將樣本中的對象劃分成不同的類簇，從而使同一類簇中對象具備相似性，不同類簇間對象具有差異性。K-means算法由于簡單、高效、良好的局部搜索能力、數據集類型多樣等特點在多種學科領域廣泛使用，尤其是對球狀分布的數據進行聚類時能達到理想的效果[2]。但同時存在需事先確定聚類數，且對初始聚類中心敏感，初始聚類中心的隨機選取導致聚類結果不穩定，容易陷入局部最優解，并易受孤立點的影響等缺點。本文主要針對機動通信網絡子網劃分任務，提出一種根據通信節點連通度和物理位置確定K值和初始聚類中心的方法，并設計一種加權K-means聚類算法，能夠提升機動通信網絡劃分效果。

1相關背景

1.1 K-means算法

K-means算法屬于聚類算法，是一種無監督的機器學習方法，與有監督的機器學習方法不同，K-means算法不需要具有數據的先驗知識，根據數據對象的相似度對集合中數據對象進行劃分[3]。從理論上說，聚類算法是將數據集中的樣本劃分為若干個通常不相交的子集，每個子集稱為一個簇。聚類分析的最終目標是使屬于同一簇的數據對象具有最大的相似度，屬于不同簇的數據對象具有最大的差異度。

1.2網絡結構

從網絡組成方面來看，機動通信網絡一般由骨干網絡和用戶網絡組成，如圖1所示，用戶網絡之間通過骨干網絡實現互連互通。從網絡規模方面，機動通信網絡規模靈活可變，根據任務保障需求從幾十個通信節點到幾千個通信節點不等。在網絡傳輸手段方面，根據部署位置和使用需求不同，采用光纖、有線遠傳、微波、衛通、自組網等多種通信手段。其中，光纖、有線遠傳、自組網等傳輸手段一般多用于用戶網絡，衛通、微波等多用于骨干網絡。

根據機動通信網絡組織結構，在進行網絡劃分時一般要考慮通信手段、地理位置、所屬網絡、業務關系等因素。

（1）通信節點類型根據在網絡中位置、功能定位等不同，可將通信節點分為骨干網節點和用戶網節點兩類。骨干節點主要用于搭建連通各用戶網的骨干網絡，因此其通信手段主要滿足大帶寬、遠距離傳輸需求，如衛通、微波等。用戶網節點用于在小地域范圍內構建用戶網絡，主要采用光纖、有線遠傳、自組網等。通信節點類型在很大程度上決定該節點在網絡中的位置。因此，通信節點類型是判斷該節點所屬網絡類型的關鍵因素。

（2）地理位置

通信節點間距離或覆蓋地域也是反映網絡特點的重要因素。一般來說，骨干網各通信節點間距離較遠，多采用大跨距遠距離傳輸的衛通、微波等;用戶網通信節點間距離相對較近，一般采用有線、自組網等傳輸距離相對較近的通信手段。在地理位置上，一般同一網絡內的通信節點位置相對集中。比如各用戶子網一般限定在數公里范圍之內，骨干網覆蓋地域相對較遠。

（3）網絡連通度

從節點間互連關系來看，屬于同一網絡內的節點間互連關系更為緊密。比如在用戶網絡內一般構建全連通的自組網，在骨干網絡中構建全連通的衛星網絡等。因此，網絡內部相比網絡之間的連通度高。

2改進的K-means算法

2.1自動確定K值

Elbow法核心思想[5]是：隨著聚類數的不斷增大，樣本劃分結果也將更加精細，所劃分的每個簇的聚合程度會逐步提高，使逐漸變小。在計算過程中，當的取值小于實際的聚類數目時，隨著取值的不斷增大，每個簇的聚合程度將大幅度提高，計算結果也會大幅下降;當值等于實際的聚類數目時，隨著取值的增加，計算所得的聚合程度會大幅變小，計算結果的下降幅度也會銳減，最終會隨著取值的不斷增大趨于平緩。從圖形上來看，和值的關系圖呈現為一個手肘的形狀，圖中肘部對應的的取值就是數據的實際聚類數目。

2.2初始聚類中心選擇

在選擇初始聚類中心時，采用K-means+聚類算法中初始聚類中心的選擇方法，并結合機動通信網絡特點，將網絡中各節點的連通度作為選擇初始聚類中心的關鍵因素之一。初始聚類中心選擇步驟如下：

①采用隨機選取方式從數據集中選取一個樣本點作為初始聚類中心;

在本文中，機動通信網絡數據的主要特征包括節點位置、節點類型、節點連通度、節點對外連接關系等。其中，節點位置信息一般采用經緯度表示，在本文中為方便計算，采用對應的屏幕坐標。節點類型包括骨干節點、接入節點和用戶節點3類。節點連通度是該節點對外的鏈路數量。以上3類特征分別賦予不同權值直接參與歐氏距離計算。節點對外連接關系不直接參與計算，作為獨立判斷因子，在進行聚類時，根據節點對外連接關系判斷孤立點的所屬聚類。

3實驗及結果分析

為驗證本文中改進后K-means算法的實際聚類效果，分別選取了70，150，320個節點的3個不同規模的機動通信網絡拓撲數據進行了測試，機動通信網絡拓撲數據如圖2所示。

（1）選取值

針對3個不同規模的網絡拓撲數據，采用Elbow方法進行K值的選取。值與之間關系如圖3～圖5所示。

從圖3可以看出，針對節點數為70的機動通信網絡拓撲數據，當值從5開始繼續增大時，SSE取值變化趨向平緩，因此選擇=5作為聚類數。

從圖4可以看出，針對節點數為150的機動通信網絡拓撲數據，當值從3開始繼續增大時，取值變化趨向平緩，因此選擇=3作為聚類數。

從圖5可以看出，針對節點數為320的機動通信網絡拓撲數據，當值從8開始繼續增大時，取值變化趨向平緩，因此選擇=8作為聚類數。

（2）聚類結果

3種不同規模機動通信網絡拓撲數據聚類結果如圖6所示。其中，在考慮節點連通度的因素下，初始聚類中心選擇符合預期。

4結束語

本文針對機動通信網絡規劃實際需求，通過采用基于加權的K-means聚類算法，實現機動通信網絡自動劃分，為后續的頻率規劃、IP規劃、路由規劃等奠定了基礎。通過3種不同規模網絡拓撲數據的實驗驗證，采用的基于加權的K-means算法基本能夠按照預期實現網絡自動劃分。

參考文獻

[1]楊志，羅可.一種改進的基于粒子群的聚類算法[J].計算機應用研究，2014，31（9）：2597-2599，2605.

[2]李梅蓮.基于密度分布的K-Means初始聚類中心選擇算法[J].許昌學院學報，2017，36（2）：20-24.

[3] EVERITT B， HOTHORN T. Cluster Analysis[J].Quality & Quantity，2011，14（1）：75-100.

[4]黃偉明，楊建宇，陳彥清，等.基于扇形篩選法的矢量數據壓縮方法[J].武漢大學學報（信息科學版），2016，41（4）：487-491.

[5] HRUSCHKA E R， CAMPELLO A， FREITAS.A. A Survey of Evolutionary Algorithms for Clustering [J].IEEE Transactions on Systems， Man and Cybernetics-Part C，2009（39）：133-155.

[6]周志華.機器學習[M].北京：清華大學出版社，2016.

[7]郭靖.對K-means聚類算法歐氏距離加權系數的研究[J].網絡安全技術與應用，2016（10）：74-75

3805501908279