基于DBSCAN聚類的基站選址與扇區(qū)角度規(guī)劃研究

盛屹濤，鄭曉璇

（江蘇師范大學(xué) 敬文書院，江蘇 徐州 221116）

隨著5G網(wǎng)絡(luò)大規(guī)模發(fā)展，用戶業(yè)務(wù)對(duì)于頻段資源的需求也隨之快速增長(zhǎng)。從技術(shù)標(biāo)準(zhǔn)層次分析，5G網(wǎng)絡(luò)工作處于3 000～5 000 MHz頻段，遠(yuǎn)高于2G、3G、4G網(wǎng)絡(luò)。頻率越高，信號(hào)在實(shí)際傳播進(jìn)程中的衰減也越大[1]，使得通信網(wǎng)絡(luò)規(guī)劃特別是站址選擇變得越來(lái)越困難。在實(shí)際網(wǎng)絡(luò)規(guī)劃與基站建設(shè)中，考慮建設(shè)成本和其他因素，應(yīng)盡量?jī)?yōu)先解決業(yè)務(wù)量高的弱覆蓋問(wèn)題，同時(shí)兼顧基站建設(shè)成本最低化與業(yè)務(wù)量最大化。本文針對(duì)2022年MathorCup高校數(shù)學(xué)建模挑戰(zhàn)賽D題[2]，給出基站建設(shè)規(guī)劃的最優(yōu)化方案，擬解決兩方面問(wèn)題：一是通過(guò)設(shè)計(jì)聚類算法，使運(yùn)算量最小化；二是設(shè)計(jì)基站種類、位置及扇區(qū)主方向，使得弱覆蓋點(diǎn)總業(yè)務(wù)量的90%被基站覆蓋。

1 數(shù)據(jù)預(yù)處理

1.1 數(shù)據(jù)描述與分析

數(shù)據(jù)來(lái)源于賽題附件1和附件2，其中附件1給出了某地弱覆蓋點(diǎn)的位置和業(yè)務(wù)量，附件2給出了現(xiàn)有基站的位置。2種基站和其覆蓋范圍、建設(shè)成本如表1。

表1 可建設(shè)基站的種類、覆蓋范圍與成本

1.2 數(shù)據(jù)處理

首先，尋找已被現(xiàn)有基站覆蓋的弱覆蓋點(diǎn)?？紤]基站有三個(gè)扇區(qū)，且扇區(qū)主方向角度是變化的[3]，為使覆蓋區(qū)域最大化，首先需對(duì)不同角度下基站的輻射距離進(jìn)行討論，再通過(guò)距離計(jì)算，剔除可能受影響的點(diǎn)，得到極弱覆蓋區(qū)域。篩選不能受任何現(xiàn)有基站輻射的區(qū)域，在聚類中心鋪設(shè)基站，可優(yōu)先解決此類地區(qū)的極弱覆蓋問(wèn)題，也能避免因基站部署密集造成終端來(lái)回切換導(dǎo)致的信號(hào)差、資源浪費(fèi)等現(xiàn)象[4]。

1.3 基站扇區(qū)主方向與覆蓋半徑的關(guān)系

根據(jù)賽題條件，一個(gè)基站只有3個(gè)扇區(qū)進(jìn)行覆蓋，因此各基站扇區(qū)的主方向不同時(shí)，其所覆蓋的坐標(biāo)點(diǎn)各不相同。根據(jù)要求建立站址間、新建站址與現(xiàn)有站址間的距離門限是10，各站中任意兩個(gè)主方向間的夾角不能小于π/4，設(shè)置限制條件，且考慮基站成本等因素進(jìn)行規(guī)劃。

首先，建立基站半徑函數(shù)。設(shè)基站輻射半徑為R，坐標(biāo)點(diǎn)和基站間連線和其中一個(gè)主方向的夾角為θ，且此時(shí)坐標(biāo)點(diǎn)與基站間連線的距離為r。利用插值法[5]，計(jì)算半徑隨角度線性變化的系數(shù)，由此確定半徑和夾角關(guān)系式如下：

在基站規(guī)劃中，任意兩扇區(qū)間的主方向夾角要大于π/4，同時(shí)每個(gè)基站只有3個(gè)扇區(qū)，進(jìn)一步分析不同扇區(qū)主方向間角度β變化后的基站覆蓋半徑r與夾角θ的關(guān)系式。為方便表示，以其中一個(gè)扇區(qū)的主方向?yàn)闃O軸，討論該扇區(qū)與另一扇區(qū)的輻射半徑，3個(gè)扇區(qū)的情況可類比得到。由于每個(gè)扇區(qū)主方向左右π/3的范圍內(nèi)都能起覆蓋作用，考慮兩個(gè)扇區(qū)間的重疊部分，需分三種情況對(duì)兩個(gè)扇區(qū)間的夾角β進(jìn)行討論。

根據(jù)上述任意兩個(gè)扇區(qū)形狀所覆蓋的半徑隨著θ變化的函數(shù)表達(dá)式，選定扇區(qū)主方向角度最小的方向所在直線為極軸，再通過(guò)旋轉(zhuǎn)正方向β角度，就可得到第二個(gè)主方向。依次類推，可構(gòu)造出一個(gè)基站的三個(gè)主方向之間的夾角關(guān)系，從而得到該基站在任意角度的輻射半徑。

2 基站扇區(qū)主方向角度規(guī)劃

首先，根據(jù)基站建設(shè)要求，每個(gè)站的任意兩扇區(qū)的主方向間的夾角不能小于π/4，每個(gè)基站有三個(gè)扇區(qū)，且每個(gè)扇區(qū)指向一個(gè)方向時(shí)，設(shè)第i個(gè)基站的三個(gè)扇區(qū)主方向角度分別為φi，1、φi，2、φi，3，其關(guān)系如下：

為優(yōu)化算法，考慮扇區(qū)的主方向時(shí)，分別計(jì)算各點(diǎn)和基站連線與x軸正方向的夾角，以距離最遠(yuǎn)的點(diǎn)與基站的連線作為其基站中一個(gè)扇區(qū)所指方向，記為φi，far，根據(jù)覆蓋點(diǎn)到基站的距離，采用條件期望[6]對(duì)剩下兩扇區(qū)所指方向進(jìn)行規(guī)劃。設(shè)該基站能輻射的弱覆蓋點(diǎn)中最小角度為φi，min，最大角度為φi，max，與極軸正方向的角度為φi，j，分三種情況討論。

（1）當(dāng)φi，far=φi，min時(shí)，記集合{φi，1，φi，2，φi，3，…}的中位數(shù)為φi，mid，取φi，1=φi，far。對(duì)于剩余的兩個(gè)扇區(qū)，考察其與中位數(shù)φi，mid的關(guān)系，對(duì)于該基站能輻射到的弱覆蓋點(diǎn)，若φi，j＜φi，mid，根據(jù)其到基站的距離計(jì)算條件期望，并注意的限制條件，可得

若φi，j≥φi，mid，根據(jù)距離計(jì)算條件期望，注意到取所對(duì)應(yīng)的角度

（3）當(dāng)φi，far=φi，max時(shí)，同理可得，

根據(jù)上述扇區(qū)的主方向，可求得現(xiàn)有基站對(duì)于已知弱覆蓋點(diǎn)的覆蓋范圍，經(jīng)篩選即可得到未被覆蓋點(diǎn)的集合。

3 基于DBSCAN聚類算法的基站站址規(guī)劃

3.1 基于DBSCAN的弱覆蓋點(diǎn)聚類

使用聚類算法可以較好地篩選數(shù)據(jù)，在聚類中心位置建設(shè)基站可全面覆蓋周圍區(qū)域，使每個(gè)類的每個(gè)點(diǎn)都被覆蓋。聚類算法主要有K-means算法[7]、系統(tǒng)（層次）聚類算法[8]和DBSCAN聚類算法[9-10]三種。由于具體需聚類的數(shù)量未知，與K-means比較而言，DBSCAN不需輸入要?jiǎng)澐值木垲悅€(gè)數(shù)[11]，但樣本數(shù)過(guò)大時(shí)，如隨機(jī)指定聚類數(shù)量不科學(xué)，且會(huì)增加計(jì)算量，過(guò)小則不能很好體現(xiàn)弱覆蓋點(diǎn)間關(guān)系?？紤]弱覆蓋點(diǎn)是坐標(biāo)形式，因此通過(guò)DBSCAN聚類的兩個(gè)參數(shù)EPS和Minpts體現(xiàn)其關(guān)系，根據(jù)基站輻射半徑和基站間的門限要求設(shè)置EPS。同時(shí)，基于密度定義，能處理任意形狀和大小的簇也可在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)，異常點(diǎn)可視為偏遠(yuǎn)地區(qū)。如果該點(diǎn)處業(yè)務(wù)量較大，可通過(guò)設(shè)立基站解決弱覆蓋問(wèn)題。綜上可知，DBSCAN算法更適用于弱覆蓋點(diǎn)的聚類。

DBSCAN算法聚類執(zhí)行過(guò)程為：在已篩選的143 528組數(shù)據(jù)中隨機(jī)選取某個(gè)對(duì)象點(diǎn)X，查詢X的EPS鄰域半徑內(nèi)所有密度可達(dá)點(diǎn)是否大于MinPts，如果大于，則創(chuàng)建一個(gè)以該點(diǎn)為核心的聚類簇；然后，迭代聚集核心點(diǎn)密度可達(dá)的所有對(duì)象，該過(guò)程可能會(huì)將已經(jīng)形成的簇進(jìn)行合并，在算法執(zhí)行過(guò)程中，某些核心點(diǎn)的密度可達(dá)對(duì)象會(huì)被重復(fù)查詢驗(yàn)證是否在一簇里；完成一個(gè)簇聚類后，選取下一個(gè)點(diǎn)開始聚類，直至沒(méi)有任何新的點(diǎn)添加到任一簇時(shí)，聚類結(jié)束。

3.2 已有基站扇區(qū)的主方向規(guī)劃

找到剩下143 528數(shù)據(jù)中不能被任何現(xiàn)有基站輻射的極弱覆蓋區(qū)域，對(duì)現(xiàn)有基站扇區(qū)主方向角度進(jìn)行規(guī)劃，得到所有弱覆蓋點(diǎn)業(yè)務(wù)量的覆蓋率，達(dá)38.73%。表2給出了部分現(xiàn)有基站的主方向角度規(guī)劃。

表2 現(xiàn)有基站的主方向角度規(guī)劃

3.3 聚類中心處基站扇區(qū)的主方向規(guī)劃

對(duì)極弱覆蓋區(qū)域進(jìn)行DBSCAN聚類，參數(shù)EPS[12]為5，最少樣本數(shù)目設(shè)置為1，得到4 942類，柵格的聚類情況如圖4。由圖4可發(fā)現(xiàn)，同一類內(nèi)部的坐標(biāo)位置都相對(duì)較近，表明這些坐標(biāo)在同一類中心的覆蓋下出現(xiàn)次數(shù)較多，即DBSCAN聚類作用下分類情況較好，能最大限度地覆蓋這些坐標(biāo)點(diǎn)。

圖4 聚類效果可視化結(jié)果

在聚類中心建立基站還需滿足基站間門限大于10，記聚類中心為Ui，i=1，2，3…，已建立基站為Pj，j=1，2，3…，于是對(duì)?i∈{1，2，3…}，對(duì)?j∈{1，2，3…}，滿足‖Ui-Pj‖＞10；還要滿足新建立的基站間門限也大于10，對(duì)?i∈{1，2，3…}，對(duì)?k∈{1，2，3，…，i-1}，滿足‖Ui-Uk‖>10?？紤]聚類中心周圍的點(diǎn)較為密集，為使覆蓋率盡可能大，在所有聚類中心處考慮建立宏基站[13]。在滿足門限條件下，共建立宏基站1 877個(gè)。根據(jù)主方向角度的規(guī)劃，求得此時(shí)覆蓋率達(dá)72.76%。在聚類中心建立的部分宏基站位置和主方向角度規(guī)劃如表3所示。

表3 在聚類中心建立的宏基站位置和主方向角度規(guī)劃

3.4 極弱覆蓋點(diǎn)處建立基站的扇區(qū)主方向規(guī)劃

上文在聚類中心建立宏基站覆蓋率雖達(dá)72.76%，仍未達(dá)90%，因此，考慮在極弱覆蓋點(diǎn)處建立微基站，以確保成本最低化，同時(shí)獲得較高的覆蓋率。在門限大于10的條件下，根據(jù)基站扇區(qū)主方向角度規(guī)劃，得到覆蓋率為89.56%，此時(shí)建立微基站2 292個(gè)。求解與所建宏基站之間覆蓋率相差最大的基站，并將其排序，覆蓋率小于90%時(shí)，將差距最大的微基站改為宏基站。最終，將兩個(gè)微基站改為宏基站，即可使覆蓋率達(dá)90.21%。兩個(gè)基站修改后得到的坐標(biāo)和三個(gè)扇區(qū)主方向角度規(guī)劃如表4所示，其余部分微基站的位置和主方向角度規(guī)劃如表5所示。

表4 極弱覆蓋點(diǎn)處微基站修改成宏基站的位置和主方向角度規(guī)劃

表5 建立的微基站位置和主方向角度規(guī)劃

4 結(jié) 語(yǔ)

本文針對(duì)線性遞減情況，通過(guò)求解扇區(qū)輻射半徑與角度關(guān)系，根據(jù)弱覆蓋點(diǎn)到基站的距離，對(duì)扇區(qū)主方向角度進(jìn)行規(guī)劃，再用DBSCAN聚類模型對(duì)極弱覆蓋點(diǎn)進(jìn)行聚類，最終共計(jì)建立1 879個(gè)宏基站和2 290個(gè)微基站，覆蓋率達(dá)90.21%。此外，對(duì)已有基站的三個(gè)扇區(qū)主方向進(jìn)行規(guī)劃，假定扇區(qū)主方向角度均為0、2π/3、4π/3，覆蓋率只能達(dá)26.82%，而采用聚類法，覆蓋率可達(dá)38.73%，表明在考慮優(yōu)化算法復(fù)雜度情況下，聚類較為有效。