基于加權(quán)K-means聚類算法的機(jī)動通信網(wǎng)絡(luò)自動劃分方法

王均春 冀云剛

摘要：針對機(jī)動通信網(wǎng)絡(luò)規(guī)劃中的網(wǎng)絡(luò)劃分需求，提出了一種基于加權(quán)K-means聚類算法的網(wǎng)絡(luò)自動劃分方法。算法通過采用Elbow方法確定聚類數(shù)量，并在初始聚類中心選擇中考慮了節(jié)點(diǎn)連通度，克服了傳統(tǒng)K-means算法初始聚類中心的不確定性，通過對不同特征分配相應(yīng)權(quán)重，進(jìn)一步提升了聚類效果。實(shí)驗(yàn)結(jié)果說明該算法在機(jī)動通信網(wǎng)絡(luò)自動劃分中具有良好的準(zhǔn)確率，為后續(xù)網(wǎng)絡(luò)規(guī)劃提供了基礎(chǔ)支撐。

關(guān)鍵詞：網(wǎng)絡(luò)劃分;加權(quán)K-means;網(wǎng)絡(luò)規(guī)劃;節(jié)點(diǎn)聯(lián)通度

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A文章編號：1008-1739（2022）02-56-4

0引言

機(jī)動通信網(wǎng)絡(luò)是為保障特殊任務(wù)而臨時開設(shè)的綜合性通信網(wǎng)絡(luò)，具有快速開設(shè)、組織結(jié)構(gòu)復(fù)雜、動態(tài)變化等特點(diǎn)。機(jī)動通信網(wǎng)絡(luò)規(guī)劃負(fù)責(zé)在網(wǎng)絡(luò)開設(shè)前，根據(jù)通信保障需求統(tǒng)籌安排各類通信資源，進(jìn)行網(wǎng)絡(luò)拓?fù)湟?guī)劃、頻率規(guī)劃、IP規(guī)劃等，生成網(wǎng)絡(luò)開通所需的規(guī)劃參數(shù)文件，確保網(wǎng)絡(luò)快速開通。其中，網(wǎng)絡(luò)拓?fù)湟?guī)劃是基礎(chǔ)。在開展其他規(guī)劃工作前，需先根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)組成，將整個網(wǎng)絡(luò)劃分成若干相對獨(dú)立的子網(wǎng)，然后再基于子網(wǎng)劃分結(jié)果進(jìn)行各子網(wǎng)的頻率分配、IP地址規(guī)劃、路由協(xié)議規(guī)劃、聚合路由規(guī)劃等。目前在進(jìn)行子網(wǎng)劃分時，一般多采用人工劃分或按所屬單位固定劃分方式，缺少自動化手段，無法適應(yīng)機(jī)動通信網(wǎng)絡(luò)組織結(jié)構(gòu)靈活多變的特點(diǎn)。尤其是當(dāng)網(wǎng)絡(luò)規(guī)模較大時，對規(guī)劃人員要求高，影響網(wǎng)絡(luò)規(guī)劃效率。

K-means算法[1]作為一種經(jīng)典的聚類算法，能夠?qū)颖局械膶ο髣澐殖刹煌念惔兀瑥亩雇活惔刂袑ο缶邆湎嗨菩裕煌惔亻g對象具有差異性。K-means算法由于簡單、高效、良好的局部搜索能力、數(shù)據(jù)集類型多樣等特點(diǎn)在多種學(xué)科領(lǐng)域廣泛使用，尤其是對球狀分布的數(shù)據(jù)進(jìn)行聚類時能達(dá)到理想的效果[2]。但同時存在需事先確定聚類數(shù)，且對初始聚類中心敏感，初始聚類中心的隨機(jī)選取導(dǎo)致聚類結(jié)果不穩(wěn)定，容易陷入局部最優(yōu)解，并易受孤立點(diǎn)的影響等缺點(diǎn)。本文主要針對機(jī)動通信網(wǎng)絡(luò)子網(wǎng)劃分任務(wù)，提出一種根據(jù)通信節(jié)點(diǎn)連通度和物理位置確定K值和初始聚類中心的方法，并設(shè)計一種加權(quán)K-means聚類算法，能夠提升機(jī)動通信網(wǎng)絡(luò)劃分效果。

1相關(guān)背景

1.1 K-means算法

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

1.2網(wǎng)絡(luò)結(jié)構(gòu)

從網(wǎng)絡(luò)組成方面來看，機(jī)動通信網(wǎng)絡(luò)一般由骨干網(wǎng)絡(luò)和用戶網(wǎng)絡(luò)組成，如圖1所示，用戶網(wǎng)絡(luò)之間通過骨干網(wǎng)絡(luò)實(shí)現(xiàn)互連互通。從網(wǎng)絡(luò)規(guī)模方面，機(jī)動通信網(wǎng)絡(luò)規(guī)模靈活可變，根據(jù)任務(wù)保障需求從幾十個通信節(jié)點(diǎn)到幾千個通信節(jié)點(diǎn)不等。在網(wǎng)絡(luò)傳輸手段方面，根據(jù)部署位置和使用需求不同，采用光纖、有線遠(yuǎn)傳、微波、衛(wèi)通、自組網(wǎng)等多種通信手段。其中，光纖、有線遠(yuǎn)傳、自組網(wǎng)等傳輸手段一般多用于用戶網(wǎng)絡(luò)，衛(wèi)通、微波等多用于骨干網(wǎng)絡(luò)。

根據(jù)機(jī)動通信網(wǎng)絡(luò)組織結(jié)構(gòu)，在進(jìn)行網(wǎng)絡(luò)劃分時一般要考慮通信手段、地理位置、所屬網(wǎng)絡(luò)、業(yè)務(wù)關(guān)系等因素。

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

（2）地理位置

通信節(jié)點(diǎn)間距離或覆蓋地域也是反映網(wǎng)絡(luò)特點(diǎn)的重要因素。一般來說，骨干網(wǎng)各通信節(jié)點(diǎn)間距離較遠(yuǎn)，多采用大跨距遠(yuǎn)距離傳輸?shù)男l(wèi)通、微波等;用戶網(wǎng)通信節(jié)點(diǎn)間距離相對較近，一般采用有線、自組網(wǎng)等傳輸距離相對較近的通信手段。在地理位置上，一般同一網(wǎng)絡(luò)內(nèi)的通信節(jié)點(diǎn)位置相對集中。比如各用戶子網(wǎng)一般限定在數(shù)公里范圍之內(nèi)，骨干網(wǎng)覆蓋地域相對較遠(yuǎn)。

（3）網(wǎng)絡(luò)連通度

從節(jié)點(diǎn)間互連關(guān)系來看，屬于同一網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)間互連關(guān)系更為緊密。比如在用戶網(wǎng)絡(luò)內(nèi)一般構(gòu)建全連通的自組網(wǎng)，在骨干網(wǎng)絡(luò)中構(gòu)建全連通的衛(wèi)星網(wǎng)絡(luò)等。因此，網(wǎng)絡(luò)內(nèi)部相比網(wǎng)絡(luò)之間的連通度高。

2改進(jìn)的K-means算法

2.1自動確定K值

Elbow法核心思想[5]是：隨著聚類數(shù)的不斷增大，樣本劃分結(jié)果也將更加精細(xì)，所劃分的每個簇的聚合程度會逐步提高，使逐漸變小。在計算過程中，當(dāng)?shù)娜≈敌∮趯?shí)際的聚類數(shù)目時，隨著取值的不斷增大，每個簇的聚合程度將大幅度提高，計算結(jié)果也會大幅下降;當(dāng)值等于實(shí)際的聚類數(shù)目時，隨著取值的增加，計算所得的聚合程度會大幅變小，計算結(jié)果的下降幅度也會銳減，最終會隨著取值的不斷增大趨于平緩。從圖形上來看，和值的關(guān)系圖呈現(xiàn)為一個手肘的形狀，圖中肘部對應(yīng)的的取值就是數(shù)據(jù)的實(shí)際聚類數(shù)目。

2.2初始聚類中心選擇

在選擇初始聚類中心時，采用K-means+聚類算法中初始聚類中心的選擇方法，并結(jié)合機(jī)動通信網(wǎng)絡(luò)特點(diǎn)，將網(wǎng)絡(luò)中各節(jié)點(diǎn)的連通度作為選擇初始聚類中心的關(guān)鍵因素之一。初始聚類中心選擇步驟如下：

①采用隨機(jī)選取方式從數(shù)據(jù)集中選取一個樣本點(diǎn)作為初始聚類中心;

在本文中，機(jī)動通信網(wǎng)絡(luò)數(shù)據(jù)的主要特征包括節(jié)點(diǎn)位置、節(jié)點(diǎn)類型、節(jié)點(diǎn)連通度、節(jié)點(diǎn)對外連接關(guān)系等。其中，節(jié)點(diǎn)位置信息一般采用經(jīng)緯度表示，在本文中為方便計算，采用對應(yīng)的屏幕坐標(biāo)。節(jié)點(diǎn)類型包括骨干節(jié)點(diǎn)、接入節(jié)點(diǎn)和用戶節(jié)點(diǎn)3類。節(jié)點(diǎn)連通度是該節(jié)點(diǎn)對外的鏈路數(shù)量。以上3類特征分別賦予不同權(quán)值直接參與歐氏距離計算。節(jié)點(diǎn)對外連接關(guān)系不直接參與計算，作為獨(dú)立判斷因子，在進(jìn)行聚類時，根據(jù)節(jié)點(diǎn)對外連接關(guān)系判斷孤立點(diǎn)的所屬聚類。

3實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證本文中改進(jìn)后K-means算法的實(shí)際聚類效果，分別選取了70，150，320個節(jié)點(diǎn)的3個不同規(guī)模的機(jī)動通信網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)進(jìn)行了測試，機(jī)動通信網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)如圖2所示。

（1）選取值

針對3個不同規(guī)模的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)，采用Elbow方法進(jìn)行K值的選取。值與之間關(guān)系如圖3～圖5所示。

從圖3可以看出，針對節(jié)點(diǎn)數(shù)為70的機(jī)動通信網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)，當(dāng)值從5開始繼續(xù)增大時，SSE取值變化趨向平緩，因此選擇=5作為聚類數(shù)。

從圖4可以看出，針對節(jié)點(diǎn)數(shù)為150的機(jī)動通信網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)，當(dāng)值從3開始繼續(xù)增大時，取值變化趨向平緩，因此選擇=3作為聚類數(shù)。

從圖5可以看出，針對節(jié)點(diǎn)數(shù)為320的機(jī)動通信網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)，當(dāng)值從8開始繼續(xù)增大時，取值變化趨向平緩，因此選擇=8作為聚類數(shù)。

（2）聚類結(jié)果

3種不同規(guī)模機(jī)動通信網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)聚類結(jié)果如圖6所示。其中，在考慮節(jié)點(diǎn)連通度的因素下，初始聚類中心選擇符合預(yù)期。

4結(jié)束語

本文針對機(jī)動通信網(wǎng)絡(luò)規(guī)劃實(shí)際需求，通過采用基于加權(quán)的K-means聚類算法，實(shí)現(xiàn)機(jī)動通信網(wǎng)絡(luò)自動劃分，為后續(xù)的頻率規(guī)劃、IP規(guī)劃、路由規(guī)劃等奠定了基礎(chǔ)。通過3種不同規(guī)模網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)的實(shí)驗(yàn)驗(yàn)證，采用的基于加權(quán)的K-means算法基本能夠按照預(yù)期實(shí)現(xiàn)網(wǎng)絡(luò)自動劃分。

參考文獻(xiàn)

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

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

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

[4]黃偉明，楊建宇，陳彥清，等.基于扇形篩選法的矢量數(shù)據(jù)壓縮方法[J].武漢大學(xué)學(xué)報（信息科學(xué)版），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]周志華.機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2016.

[7]郭靖.對K-means聚類算法歐氏距離加權(quán)系數(shù)的研究[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2016（10）：74-75

3805501908279