基于聚類算法的站址規(guī)劃和區(qū)域聚類

周樹濤 蘇俊玉

（廣東海洋大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院，廣東湛江 524088）

0 引言

根據(jù)某區(qū)域現(xiàn)網(wǎng)的弱覆蓋區(qū)域，將給定的區(qū)域用很小的柵格進(jìn)行劃分，只考慮每個柵格的中心點(diǎn)。區(qū)域可以劃分成有限個點(diǎn)。每個點(diǎn)屬性值包括坐標(biāo)、是否為弱覆蓋點(diǎn)、業(yè)務(wù)量等。

在實(shí)際網(wǎng)絡(luò)規(guī)劃中，考慮基站的建設(shè)成本和一些其他因素，盡量優(yōu)先解決業(yè)務(wù)量高的弱覆蓋區(qū)域。從區(qū)域內(nèi)的2500×2500 個點(diǎn)中進(jìn)行站址規(guī)劃，使得弱覆蓋點(diǎn)總業(yè)務(wù)量的90%被規(guī)劃基站覆蓋。

同時，新建站址之間以及新建站址和現(xiàn)有站址之間的距離不能小于等于給定門限10。給定兩種基站分別為：宏基站（覆蓋范圍30，成本10），微基站（覆蓋范圍10，成本1）。

1 分析

建設(shè)成本最低的基站群，以達(dá)到甚至超過弱覆蓋點(diǎn)總業(yè)務(wù)量的一定比例。根據(jù)區(qū)域內(nèi)弱覆蓋點(diǎn)和現(xiàn)有基站的位置坐標(biāo)，考慮新建基站之間以及新建基站和現(xiàn)有站址之間的距離不能小于門限，進(jìn)行初步的優(yōu)化選址[1]。

不能忽視的一點(diǎn)是，需要存在一個界定值α，判斷新建基站建設(shè)的種類（宏基站/微基站），因此在初始時，需假設(shè)值，模型建立后，改變界定值，建立插值優(yōu)化，尋找最優(yōu)選址。

通過采取較為合適的聚類分析[2]，對聚類效果進(jìn)行評估，使得模型更為完整。

2 建模

先對數(shù)據(jù)進(jìn)行預(yù)處理，根據(jù)二范數(shù)公式，計算所有弱覆蓋點(diǎn)與現(xiàn)網(wǎng)站址間的距離。

對現(xiàn)有弱覆蓋點(diǎn)的坐標(biāo)進(jìn)行清洗，公式如下：

對不在現(xiàn)網(wǎng)站址門限內(nèi)的弱覆蓋點(diǎn)進(jìn)行研究，以業(yè)務(wù)量多少進(jìn)行降序排序，以業(yè)務(wù)量最大的點(diǎn)作為新基站建設(shè)的預(yù)選點(diǎn)。從所有不在現(xiàn)網(wǎng)站址門限內(nèi)的弱覆蓋點(diǎn)的集合中，選出大于10 且小于等于30 的點(diǎn)為一類，小于等于10 的點(diǎn)為一類，對歸屬于一類的弱覆蓋點(diǎn)的業(yè)務(wù)量進(jìn)行相加統(tǒng)計。

這里a為界定值，需要優(yōu)化，現(xiàn)在只是假定為10。

若Ci＞0，則選擇建設(shè)宏基站；若Ci≤0，則建設(shè)微基站。

選擇完畢后剔除在新基站范圍內(nèi)的點(diǎn)，再對下一業(yè)務(wù)量（次大值）的點(diǎn)進(jìn)行循環(huán)。需要注意的是，隨著新基站的預(yù)計建設(shè)，若弱覆蓋點(diǎn)與某一新基站的門限在小于10的范圍內(nèi)，則跳過該弱覆蓋點(diǎn)。次循環(huán)為在已覆蓋點(diǎn)的點(diǎn)業(yè)務(wù)量總和與不在現(xiàn)網(wǎng)站址門限內(nèi)的點(diǎn)的業(yè)務(wù)量總和之比大于等于0.9 時結(jié)束。

設(shè)不同基站建設(shè)的成本為弱覆蓋點(diǎn)總業(yè)務(wù)量。目標(biāo)函數(shù)為：

其中，

在現(xiàn)有網(wǎng)站址門限內(nèi)的弱覆蓋點(diǎn)不能作為基站建設(shè)的位置，設(shè)所有弱覆蓋點(diǎn)的坐標(biāo)為不在現(xiàn)有網(wǎng)站址門限內(nèi)的弱覆蓋點(diǎn)的坐標(biāo)。因此將弱覆蓋點(diǎn)分為兩類數(shù)據(jù)。

圖1 給出弱覆蓋點(diǎn)可視化圖（紅點(diǎn)代表在現(xiàn)網(wǎng)站址內(nèi)門限里的點(diǎn)，藍(lán)點(diǎn)代表不在現(xiàn)網(wǎng)站址門限內(nèi)的點(diǎn)）。

圖1 弱覆蓋點(diǎn)可視化

現(xiàn)有基站站址位置的散點(diǎn)圖如圖2 所示。

圖2 現(xiàn)有基站站址位置可視化

設(shè)已規(guī)劃建設(shè)基站的坐標(biāo)，為達(dá)到弱覆蓋總業(yè)務(wù)量的90%被規(guī)劃基站覆蓋，優(yōu)先考慮業(yè)務(wù)量大的點(diǎn)作為基站建設(shè)的位置，因此有以下解法。

再對所有弱覆蓋點(diǎn)進(jìn)行遍歷。

設(shè)α為界定值，此時假設(shè)界定值為α=10。α此時為假定值，在算法完全建設(shè)后，需要對其進(jìn)行插值優(yōu)化，以尋找最優(yōu)值。并在p'中剔除已覆蓋的點(diǎn)，記錄規(guī)劃基站已覆蓋點(diǎn)的總業(yè)務(wù)為tF'。

重要約束條件：

由上述模型可得到：當(dāng)界定值α=10 時，由此可得出規(guī)劃基站所用費(fèi)用為6046 萬元。

但由于此界定值α為假設(shè)值，可能存在更優(yōu)點(diǎn)[3]，在模型不變的情況下對α進(jìn)行插值優(yōu)化處理，得到變化圖如圖3 所示。

圖3 規(guī)劃基站費(fèi)用隨α的變化圖

因此通過MATLAB 找尋規(guī)劃基站的建設(shè)成本最低點(diǎn)，即

宏基站建設(shè)238 個，微基站建設(shè)3060 個，此時界定值α=85.28。

規(guī)劃基站已覆蓋的弱覆蓋點(diǎn)業(yè)務(wù)量：

實(shí)際工作中，把距離近的弱覆蓋點(diǎn)聚成一類，可以得到弱覆蓋區(qū)域，這樣可以對不同的弱覆蓋區(qū)域分開管理，可以更好地解決弱覆蓋問題[4]。

若2 個弱覆蓋點(diǎn)的距離不大于20，則這2 個弱覆蓋點(diǎn)應(yīng)聚為一類，并且考慮聚類性質(zhì)具有傳遞性，即若點(diǎn)A 和點(diǎn)B 是一類的，點(diǎn)B 和點(diǎn)C 是一類的，則點(diǎn)A、B 和C 都是一類的。首先篩選出距離不大于20 的點(diǎn)，使用平均值點(diǎn)進(jìn)行替代。選擇聚類算法[4]對弱覆蓋點(diǎn)進(jìn)行聚類并計算時間復(fù)雜度，聚類算法流程圖如圖4 所示。

圖4 聚類算法流程圖

得出了聚類中心值以及類別，如表1 所示。

表1 聚類中心值

接下來需要再次分析弱覆蓋點(diǎn)，對距離較近的弱覆蓋點(diǎn)進(jìn)行分類。隨后對區(qū)域進(jìn)行分段聚類，計算并比較每個區(qū)域中的時間復(fù)雜度[5]。

DBI，又稱為分類適確性指標(biāo)，是一種評估聚類算法優(yōu)劣的指標(biāo)。DBI 值越小，分散程度越低，分類效果越好。具體定義如下：

式中，DBI為DBI 指標(biāo)值；為第i類樣本到其類中心的平均歐氏距離；為第i和第j類的類中心歐氏距離。

前100 個聚類中心點(diǎn)DBI 指數(shù)如圖5、表2 所示。

圖5 DBI指數(shù)變化情況

表2 時間復(fù)雜度評價

3 結(jié)語

通過優(yōu)先考慮業(yè)務(wù)量大的弱覆蓋點(diǎn)建設(shè)基站，保證該區(qū)域內(nèi)業(yè)務(wù)量覆蓋能達(dá)到預(yù)期的90%，若模型衍生基站數(shù)據(jù)傳輸速度隨區(qū)域的變化而變化，則可保證業(yè)務(wù)量大的點(diǎn)一定在覆蓋區(qū)域內(nèi)，且區(qū)域越大數(shù)據(jù)傳輸速度越快[6]。

通過規(guī)范界定值的數(shù)值，為規(guī)劃基站建設(shè)種類提供參考，并為現(xiàn)實(shí)中不規(guī)則覆蓋面積的規(guī)劃基站種類提供可參考的閾值[7]。

通過綜合比較多種不同的聚類算法以及對應(yīng)的時間復(fù)雜度，采取較為合適的聚類分析對聚類效果進(jìn)行評估，使得模型更為完整。