基于聚類算法的站址規劃和區域聚類

周樹濤 蘇俊玉

（廣東海洋大學數學與計算機學院，廣東湛江 524088）

0 引言

根據某區域現網的弱覆蓋區域，將給定的區域用很小的柵格進行劃分，只考慮每個柵格的中心點。區域可以劃分成有限個點。每個點屬性值包括坐標、是否為弱覆蓋點、業務量等。

在實際網絡規劃中，考慮基站的建設成本和一些其他因素，盡量優先解決業務量高的弱覆蓋區域。從區域內的2500×2500 個點中進行站址規劃，使得弱覆蓋點總業務量的90%被規劃基站覆蓋。

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

1 分析

建設成本最低的基站群，以達到甚至超過弱覆蓋點總業務量的一定比例。根據區域內弱覆蓋點和現有基站的位置坐標，考慮新建基站之間以及新建基站和現有站址之間的距離不能小于門限，進行初步的優化選址[1]。

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

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

2 建模

先對數據進行預處理，根據二范數公式，計算所有弱覆蓋點與現網站址間的距離。

對現有弱覆蓋點的坐標進行清洗，公式如下：

對不在現網站址門限內的弱覆蓋點進行研究，以業務量多少進行降序排序，以業務量最大的點作為新基站建設的預選點。從所有不在現網站址門限內的弱覆蓋點的集合中，選出大于10 且小于等于30 的點為一類，小于等于10 的點為一類，對歸屬于一類的弱覆蓋點的業務量進行相加統計。

這里a為界定值，需要優化，現在只是假定為10。

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

選擇完畢后剔除在新基站范圍內的點，再對下一業務量（次大值）的點進行循環。需要注意的是，隨著新基站的預計建設，若弱覆蓋點與某一新基站的門限在小于10的范圍內，則跳過該弱覆蓋點。次循環為在已覆蓋點的點業務量總和與不在現網站址門限內的點的業務量總和之比大于等于0.9 時結束。

設不同基站建設的成本為弱覆蓋點總業務量。目標函數為：

其中，

在現有網站址門限內的弱覆蓋點不能作為基站建設的位置，設所有弱覆蓋點的坐標為不在現有網站址門限內的弱覆蓋點的坐標。因此將弱覆蓋點分為兩類數據。

圖1 給出弱覆蓋點可視化圖（紅點代表在現網站址內門限里的點，藍點代表不在現網站址門限內的點）。

圖1 弱覆蓋點可視化

現有基站站址位置的散點圖如圖2 所示。

圖2 現有基站站址位置可視化

設已規劃建設基站的坐標，為達到弱覆蓋總業務量的90%被規劃基站覆蓋，優先考慮業務量大的點作為基站建設的位置，因此有以下解法。

再對所有弱覆蓋點進行遍歷。

設α為界定值，此時假設界定值為α=10。α此時為假定值，在算法完全建設后，需要對其進行插值優化，以尋找最優值。并在p'中剔除已覆蓋的點，記錄規劃基站已覆蓋點的總業務為tF'。

重要約束條件：

由上述模型可得到：當界定值α=10 時，由此可得出規劃基站所用費用為6046 萬元。

但由于此界定值α為假設值，可能存在更優點[3]，在模型不變的情況下對α進行插值優化處理，得到變化圖如圖3 所示。

圖3 規劃基站費用隨α的變化圖

因此通過MATLAB 找尋規劃基站的建設成本最低點，即

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

規劃基站已覆蓋的弱覆蓋點業務量：

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

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

圖4 聚類算法流程圖

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

表1 聚類中心值

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

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

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

前100 個聚類中心點DBI 指數如圖5、表2 所示。

圖5 DBI指數變化情況

表2 時間復雜度評價

3 結語

通過優先考慮業務量大的弱覆蓋點建設基站，保證該區域內業務量覆蓋能達到預期的90%，若模型衍生基站數據傳輸速度隨區域的變化而變化，則可保證業務量大的點一定在覆蓋區域內，且區域越大數據傳輸速度越快[6]。

通過規范界定值的數值，為規劃基站建設種類提供參考，并為現實中不規則覆蓋面積的規劃基站種類提供可參考的閾值[7]。

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