基于數據挖掘的RPMA低功耗廣域網網絡規劃方法

朱曉榮，沈瑤

?

基于數據挖掘的RPMA低功耗廣域網網絡規劃方法

朱曉榮，沈瑤

（南京郵電大學江蘇省無線通信重點實驗室，江蘇 南京 210003）

針對RPMA低功耗廣域網基站密度大、業務分布不均勻等特點，提出了一種基于數據挖掘的網絡規劃方法。首先，利用提升回歸樹算法建立了信號質量預測模型，用于提取網絡的覆蓋分布空間模式；然后，針對覆蓋分布空間模式，采用加權k-centroids分簇算法得到適應當前模式的最優基站部署；最后，根據總目標函數判定得到最終的基站拓撲。通過真實數據集的仿真實驗結果表明，與傳統的網絡規劃方法相比，所提的方法很好地提升低功耗廣域網網絡的覆蓋質量。

低功耗廣域網；提升回歸樹；加權k-centroids；基站部署

1 引言

隨著物聯網的快速發展，聯網設備的數量將有望增長到500億，并且業務量將增加一千倍以上[1]，傳統的短距離無線技術和蜂窩網技術已經無法滿足多樣化的物聯網業務需求，因此，新的通信模式——低功耗廣域網（LPWAN ，low power wide area network）[2]應運而生。LPWAN主要滿足大連接、低速率的物聯網業務，具有覆蓋范圍大、連接成本低、功耗低等特點，主要包括NB-IoT（narrow band internet of things）、LORA（long range）、RPMA（random phase multiple access）等無線通信技術，支持超大規模數量的設備接入網絡。

然而，在RPMA等LPWAN中基站密度大，覆蓋距離達到2~3 km，業務分布不均勻[3]，導致基站部署難度大，因此，面對LPWAN網絡規劃帶來的挑戰，需要針對其自身的特點，對網絡進行合理的部署與優化，從而提高網絡服務質量。在LPWAN的網絡規劃中，基站部署決定了網絡的整體性能，過密的部署會給基站帶來很大的干擾；過疏的部署會影響邊緣區域的覆蓋質量或者造成覆蓋盲區[4]。此外，基站的選址也是影響網絡質量的關鍵因素之一，不合理的選址會導致部分區域的信號覆蓋質量差、容量不足等問題，造成網絡運營困難，增加網絡建設的成本[5]。由此可見，合適的基站數量和站址規劃在網絡部署中起到了重要作用。然而，基站站址的確定屬于NP-hard問題[6]，如果采用傳統的選址模型來分析站址問題的各種因素，就會導致所建模型中的變量與約束條件的維度災難，此選址方法并不科學。網絡規劃不僅需要考慮覆蓋，還要考慮業務分布，需要處理和整合時空特性[7]，這使網絡規劃問題更加復雜，需要設計出合理的網絡規劃方案。

目前，國內外對網絡規劃已經做了大量的研究。文獻[5]針對異構網絡環境下，研究已安排預算的基站規劃問題，其目標是在給定預算的條件下，最大化業務需求點的數量，同時也要滿足業務需求點的速率需求。文獻[8]認為LTE（long term evolution）基站規劃的優化任務是確定基站的數量和位置，基于這2個目標，結合規劃過程的2個重要約束——區域覆蓋約束和基站容量約束，提出了一種最優的LTE無線規劃方法。文獻[9]認為基站規劃策略不應該只關注如何減少基站數目，能效也是一個重要的指標，所以考慮以最小的能量消耗為目標來獲取最優的基站數目和基站站址。文獻[10]認為蜂窩網絡的核心目標是能夠保證用戶的服務質量（QoS，quality of service）和無縫覆蓋的吞吐量，基于這2個目標，采用區域劃分技術解決異構網絡中的基站規劃問題，提出以負載均衡的方式部署基站，所提方案不僅能實現部署總成本達到最低（需要部署的基站數目最少），還能獲得更好的網絡性能。文獻[11]聯合所提出的基站定位算法和無線資源控制算法自動地規劃蜂窩網基站位置，實現以最少的基站數目提供必要的覆蓋和容量。

上述文獻主要針對蜂窩網絡進行規劃，對LPWAN的技術進行綜述，并未提出合理的規劃方案。另外，很多研究者都把基站規劃問題當作優化問題進行處理，針對不同的研究場景，提出優化目標和約束，再采用合適的算法進行解決。然而，這些文獻所提出的網絡規劃方法是以大量的假設為前提，算法模型有一定的局限性，沒有從本質上提出有效的規劃方法來快速地規劃和部署大量的基站。

針對上述問題，本文將大數據的分析方法和網絡規劃相結合，以低功耗廣域網在通信系統中的應用為背景，利用獲得的網絡數據進行性能分析，將基站選址問題由傳統的模型驅動轉變為數據驅動，以海量的數據為分析主線，克服傳統網絡規劃模型的求解缺點，并結合聚類算法探索以數據驅動的基站選址方法，從而提升站點選擇的合理化水平。

2 系統模型

本文研究場景如圖1所示。RPMA網絡屬于典型的星形拓撲結構，多個終端以無線的方式連接到鄰近的RPMA網關，由網關負責接收來自終端的上行鏈路數據，并將數據聚集到各自的回程連接，實現多路數據的收集和轉發。網絡服務器和網關之間通過4G/5G/以太網回傳建立通信鏈路，其中，網絡服務器主要負責介質訪問（MAC，media access control）層處理，包括網關的管理和選擇、重復數據分組的消除、進程的確認等。

圖1 RPMA星形網絡拓撲結構

針對RPMA網絡特點，本文提出了一種基于數據挖掘的網絡規劃方法，系統框圖如圖2所示。首先，考慮網絡規劃的覆蓋目標，采集RPMA網絡的實測數據，主要包括基站基本信息數據、終端測試點數據、地理位置數據等。基于網絡規劃知識數據庫，對實測數據進行初步清洗與分析，去除具有大量重復和缺省值的屬性，并且通過分析提取影響信號覆蓋質量的相關特征，將其輸入到學習模型中進行訓練，從而獲得最終的基站部署，其中，學習模型分為預測模型和規劃模型，如圖2所示。本文中，基站站址的選定是根據每一次基站部署好后網絡的空間覆蓋情況進行調整，由于每一次基站調整，會使整個網絡的信號覆蓋情況發生變化，因此，需要針對網絡信號覆蓋的變化，利用相應的數據學習得到預測模型，對每一次的網絡拓撲下的覆蓋情況進行預測。而規劃模型則是根據預測所得的覆蓋情況，確定合適的基站部署。整個規劃的總目標是通過每一次基站調整逐漸縮小信號覆蓋差的區域，并且使區域中信號覆蓋質量接近所要求的標準。

圖2 基于數據挖掘的網絡規劃系統框架

3 信號質量預測模型

如圖2所示，本文首先從覆蓋目標著手，針對無線網絡中弱覆蓋問題進行分析，重點對覆蓋盲區和弱覆蓋區域進行優化，并且根據網絡覆蓋情況進行基站位置的調整，使調整后的基站能滿足所要求的覆蓋效果。一般來說，區域弱覆蓋主要是因為接收到的信號強度不足造成的，具體影響因素涉及以下三方面：1) 基站側影響覆蓋的因素，比如發射功率、天線方位角、天線掛高、天線增益等；2) 信號傳輸路徑影響覆蓋的因素，比如由于障礙物遮擋造成的路徑損耗、陰影衰落等；3) 干擾對覆蓋的影響，比如多個相鄰基站重疊覆蓋區內產生的同頻干擾，以及建筑、山巒等地表物對電播反射造成的多徑干擾等。

綜合上述分析，可以知道網絡中某個位置的終端接收信號質量，基本和上述三方面的因素相關，是揉合了這些因素之后的結果，因此，本文考慮先得到信號質量和這些因素之間的映射關系，即進行信號質量預測，用于輔助基站的站址確定。

信號質量預測問題在機器學習任務中是屬于回歸問題，即運用機器學習算法可以訓練得到特定的某個函數將所輸入的一系列變量映射為一個連續輸出值，因此，可以先通過現有的路測數據來構建出適應當前無線網絡環境的數據模型。當需要對新規劃方案的覆蓋效果進行預測時，只要給出對應的無線網絡特征，就可以預測出符合新規劃方案的信號覆蓋情況，然后根據預測結果，進行基站站址的進一步調整。

3.1 數據特征選取

信號質量預測是基于當前部署網絡所獲取的基站側數據和測試點側數據，如表1和表2所示。

表1 基站側屬性

表2 測試點側屬性

首先，需要對數據進行初步清洗與分析，去除具有大量重復和缺省值的屬性，如UL PER、network state等。對于deploy region屬性，本文認為經緯度已經代表了基站的位置差異特性，該屬性可以剔除。另外，結合上述所分析的三方面區域覆蓋影響因素，剔除last connect time、last connect address等無關屬性，最終選定基站位置B_loc（包括經緯度）、基站高度B_alt、基站功率B_power、天線掛高A_height和終端位置P_loc（包括經緯度）作為輸入特征，將這些輸入特征整合為一條記錄，如式(1)所示。

這些記錄的集合作為信號質量預測模型的訓練數據集。由于RPMA網絡采用功率控制，收到的上行信號強度總是在接收靈敏度附近，所以選定終端接收的下行RSSI（received signal strength indication）作為衡量信號質量的指標，即輸出變量。建立無線網絡數據模型的過程，就是通過訓練已有的數據集找到兩者之間的映射函數的過程，如式(2)所示。

3.2 信號預測模型建立

本文采用提升回歸樹算法[12]來構建式(2)所示的函數映射關系。提升回歸樹（BRT, boosting regression tree）算法屬于集成學習方法中的一種，通過集成多個基學習器共同完成學習任務。相比于單一的回歸算法，如線性回歸、對數幾率回歸算法等，BRT算法以組合多個決策樹的方式，能夠獲取更加優越的泛化能力，從而提升了模型的預測精度。BRT模型可以用棵決策樹的加法模型，如式(3)所示。

其中，每棵樹表示為

BRT采用前向分步算法，按照從前向后的順序學習每一棵決策樹，即通過優化如式(5)所示的損失函數學習每棵樹的參數。

式(5)中的損失函數采用平方誤差，即樣本的預測值和實際值差的平方和，如式(6)所示。

算法1 基于最小平方誤差代價函數的提升回歸樹算法

輸入 訓練數據集合

end for

3) 得到回歸問題提升樹

3.3 預測變量的重要性度量

本文所要研究的信號預測模型，不僅要求精確地預測出信號質量，還希望能夠通過模型了解哪些變量是影響信號覆蓋質量的主要因素。

在訓練單棵決策樹時，輸入的變量對響應變量的影響程度不同，用J(T)表示第個輸入變量X對于響應變量的相關性度量[12]，如式(7)所示。

當比較各個輸入變量對預測結果的影響力時，一般先將式(8)結果進行歸一化處理，即令所有輸入變量對結果的相對影響力之和為1，以百分數的形式來表示每個變量的重要性。

4 基站位置確定

典型的均值聚類算法是將數據集{1,...,x}中的點進行劃分，把原來獨立的個點通過設定距離相似度劃分進個簇當中，簇集合{1,...,c}。一般會以兩點之間的歐式距離作為相似性度量，把數據點劃分進距離較近的簇中心所在的簇中。算法一般是以最小化簇內位置誤差平方和（SSE, sum of the squared error）為目標函數，如式(9)所示。

在經典的K-means算法中，每個數據點對定位簇中心的位置有著同樣的重要性。然而，本文把基站位置的選擇當作基于覆蓋分布空間模式的加權問題進行處理，即認為空間中的每一個點不再對簇中心有等價的影響，引入權重來衡量數據點對基站位置的影響度，從而提出加權K-centroids算法。

算法2 加權K-centroids分簇算法決定基站位置

輸出個簇的中心位置

1) 以現有的基站位置和數量作為初始的簇中心位置和簇數量

2) repeat

end for

end for

由加權K-centroids算法得到的網絡拓撲，已經針對當前網絡覆蓋情況進行了優化，但是并不一定是最終的最優結果，仍然需要對其進行覆蓋預測分析，根據分析結果再次進行基站位置優化，直到滿足下述的總目標函數，得到最優的網絡拓撲。

整個規劃過程的總目標函數，如式(12)所示。

5 仿真分析與性能評估

本實驗數據來源于37個RPMA基站和經過數據清洗后的131 454條測試點的路測數據，包含基站基本信息數據、終端測試點數據以及相應的地理位置數據，用于驗證本文所提出的網絡規劃方法的可行性，并且采用Python Matplotlib工具將實驗結果可視化。

5.1 信號預測模型結果與分析

在應用提升回歸樹算法之前，需要確定3個參數來調整BRT算法的學習過程。首先是基學習器數量。雖然其數量的增加，會提升BRT算法對訓練數據的擬合效果，但是基學習器的數量超過一定的值，很有可能會造成過擬合，導致得到的模型對未知數據的預測效果差。其次是基學習器的大小，它表示了被BRT模型捕捉到的多個特征之間相互作用的程度，選用樹的深度來控制基學習器的大小。對于這2個參數的選取，本文采用了sk-learn中的GridSearchCV網格追蹤法，它能夠根據給定的數據集，遍歷需要優化的參數的多種取值組合，通過交叉驗證獲得最佳效果的參數取值，基學習器數量為530，樹的深度為11。最后，為了防止對訓練數據的過度擬合，會引入正則化因子，即學習率LR（learning rate），來衡量每個基學習器對最終結果的影響程度，一般LR設置為一個低于0.1的較小常數，本文中設定為0.1。

給定好參數之后，選取數據集的85%作為訓練數據集，15%為測試數據集。圖3橫軸表示迭代次數（即基學習器數量），縱軸表示損失誤差值，圖中線條分別表示了每一次迭代的測試誤差和訓練誤差。從圖中可以發現，隨著迭代次數的增加，訓練誤差和測試誤差都逐漸減少，訓練誤差的減少說明模型在訓練數據集上的擬合效果隨著迭代次數的增加逐漸提高。圖中顯示測試誤差要高于訓練誤差，是由于測試集和訓練集存在一定的差異性，使模型在未知數據集上的學習能力要弱于原訓練數據集，屬于正?，F象。另外，2條曲線的趨勢也說明GridSearchCV得到的參數適當。

圖3 損失誤差與基學習器數量的關系

圖4表示了預測變量的相對重要性。分析認為測試點距離基站的距離diff與預測值RSSI的關系最為密切，其相對最重要性達到最高。其次是測試點位置和基站所處位置，其中經度的相對重要性要小于緯度。天線掛高和基站高度的重要性稍低，最低的是基站發射功率，這是因為采集到的RPMA基站功率值只有30 dBm、31 dBm這2個值，即其取值變化較小，所以對預測值的影響作用不大。

圖4 預測變量的相對重要性

5.2 最優基站部署確定

圖5為所采集到的初始基站位置和測試點分布情況，以星形點標記基站的位置，圓點標記測試點的位置，其中圓點的顏色深淺代表RSSI值的大小，顏色越深代表RSSI值越低，信號覆蓋情況越差，可見在初始的基站部署下，還是存在部分弱覆蓋區域，圖中RSSI單位為dBm。

圖5 初始基站位置及周圍測試點的RSSI值變化情況

本文中，采取基于覆蓋分布空間模式來部署基站，以RSSI作為衡量覆蓋強弱的權重值，結合加權 K-centroids分簇算法，從而決定基站位置，并根據總目標函數值來判定當前基站部署是否達到最優。表3為每一輪規劃迭代后，求得的總目標函數值，由表3可知，隨著迭代次數的增多，總目標函數值逐漸減少，即信號覆蓋情況逐漸得到改善，直到第10次迭代后終止，得到總目標函數的最小值為535.41。圖6為最終基站位置及周圍測試點的RSSI值變化情況，可見深色區域相比于圖5有所減少，即應用本文的規劃方法后，信號覆蓋情況得到改善。圖7為對應的分簇結果，以黑色星形點標記基站的位置，圓點標記測試點的位置，同一顏色的點表示屬于離其最近的基站簇中。

表3 每輪迭代的總目標函數值

圖7 分簇結果

為了驗證本文所提方法的優越性，將本文所提方法與基于k-means的優化方法[14]進行比較。利用同一組實測數據，使用基于k-means的優化方法進行基站位置調整，圖8為應用該方法得到的基站位置及周圍的測試點的RSSI值變化情況。相比于圖5，圖8中深色區域減少，但與圖6比較，深色區域依舊很多，可見應用k-means優化方法雖然能使信號覆蓋情況有所改善，但與本文所提的方法相比，信號覆蓋提升能力不足。同時，可以利用式(12)計算每一輪迭代后的總目標函數值，其迭代結果趨于584.22，大于本文所提方法的目標函數最小值535.41。因此，從信號覆蓋率提升方面，本文所提的方法優于基于k-means的優化方法，能夠更好地提升信號覆蓋率。另外，從迭代次數上看，基于k-means的優化方法只考慮了位置距離來調節基站，需要迭代16次才能收斂到最小值，而本文方法在調節過程中引入了覆蓋權重來協助調節，可以加速收斂，僅需要表3中所示的10次迭代，收斂速度上具有一定的優勢。

圖8 應用基于k-means的優化方法得到的基站位置及周圍測試點的RSSI值變化情況

6 結束語

針對RPMA網絡特點，本文提出了一種基于數據挖掘的網絡規劃方法。首先利用獲取的實測數據對整體網絡進行初步分析，選取對覆蓋質量的影響特征。然后，采用BRT算法和K-centroids分簇算法對網絡的覆蓋分布空間模式進行提取，并且獲得最優的RPMA網絡基站部署。最后，利用實測數據驗證了本文所提方法的可行性，并與基于k-means的優化方法相比較。實驗結果表明，該方法能夠很好地提升低功耗廣域網網絡的覆蓋質量，對網絡規劃具有一定的參考價值。

在實際網絡規劃中，基站部署需要考慮多方面的因素，而本文僅考慮了網絡規劃的覆蓋目標，因此，下一步的工作將會引入容量目標，結合兩方面的目標進行基站的最優部署，使得網絡規劃更加完善。

[1] PATEL D, WON M. Experimental study on low power wide area networks (LPWAN) for mobile internet of things[C]// Vehicular Technology Conference. IEEE,2017:1-5.

[2] HERNANDEZ D M, PERALTA G, MANERO L, et al. Energy and coverage study of LPWAN schemes for Industry 4.0[C]// Electronics, Control, Measurement, Signals and their Application to Mechatronics .IEEE, 2017:1-6.

[3] KRUPKA L, VOJTECH L, NERUDA M. The issue of LPWAN technology coexistence in IoT environment[C]//International Conference on Mechatronics–Mechatronika. IEEE, 2016:1-8.

[4] YU G J, YEH K Y. A k-means based small cell deployment algorithm for wireless access networks[C]//International Conference on Networking and Network Applications. IEEE, 2016:393-398.

[5] WANG S, ZHAO W, WANG C. Budgeted cell planning for cellular networks with small cells[J]. IEEE Transactions on Vehicular Technology, 2015, 64(10):4797-4806.

[6] AMALDI E, CAPONE A, MALUCELLI F. Planning UMTS base station location: optimization models with power control and algorithms[J]. IEEE Transactions on Wireless Communications, 2003, 2(5):939-952.

[7] LEE C Y, KANG H G. Cell planning with capacity expansion in mobile communications: a tabu search approach[J]. IEEE Transactions on Vehicular Technology, 2000, 49(5):1678-1691.

[8] GHAZZAI H, YAACOUB E, ALOUINI M S, et al. Optimized LTE cell planning with varying spatial and temporal user densities[J]. IEEE Transactions on Vehicular Technology, 2016, 65(3):1575-1589.

[9] YANG Z H, CHEN M, WEN Y P, et al. Cell planning based on minimized power consumption for LTE networks[C]// IEEE Wireless Communications and Networking Conference. IEEE, 2016: 1-6.

[10] WANG S, RAN C. Rethinking cellular network planning and optimization[J]. IEEE Wireless Communications, 2016, 23(2):118-125.

[11] ISTV S, FAZEKAS P. An algorithm for automatic base station placement in cellular network deployment[C]// EUNICE/IFIP WG 6.6 Conference on Networked Services and Applications: Engineering, Control and Management. Springer-Verlag, 2010:21-30.

[12] FRIEDMAN J H. Greedy function approximation: a gradient boosting machine[J]. The Annals of Statistics, 2001, 29(5):1189-1232.

[13] WEN R, YAN W, ZHANG A N. Weighted clustering of spatial pattern for optimal logistics hub deployment[C]//IEEE International Conference on Big Data. IEEE, 2016:3792-3797.

[14] KANUNGO T, MOUNT D M, NETANYAHU N S, et al. An efficient k-means clustering algorithm: analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,40(7): 881-892.

RPMA low-power wide-area network planning method based on data mining

ZHU Xiaorong, SHEN Yao

Jiangsu Key Laboratory of Wireless Communications, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

A network planning method based on data mining was proposed for RPMA low-power wide-area network with large density of base stations and uneven traffic distribution. First, a signal quality prediction model was established by using the boosting regression trees algorithm, which was used to extract the coverage distribution spacial pattern of the network. Then , the weighted k-centroids clustering algorithm was utilized to obtain the optimal base station deployment for the current spacial pattern. Finally, according to the total objective function, the best base station topology was determined. Experiment results with the real data sets show that compared with the traditional network planning method, the proposed method can improve the coverage of low-power wide-area networks.

low power wide area network, boosting regression trees, weighted k-centroids, base station deployment

TN915.81

A

10.11959/j.issn.1000?436x.2019050

2018?04?23；

2019?01?16

江蘇省研究生科研實踐創新計劃基金資助項目（No.KYCX17_0766）；國家自然科學基金資助項目（No.61871237）；江蘇省高校自然科學研究重大項目基金資助項目（No.16KJA510005）

The Post Graduate Research & Practice Innovation Program of Jiangsu Province (No.KYCX17_0766), The National Natural Science Foundation of China (No.61871237), The Natural Science Foundation of the Higher Education Institutions of Jiangsu (No.16KJA510005)

朱曉榮（1977? ），女，山東臨沂人，博士，南京郵電大學教授、博士生導師，主要研究方向為5G網絡、異構網絡、無線傳感器網絡等無線資源管理、跨層優化算法及協議設計、性能評估及建模分析等。

沈瑤（1994? ），女，江蘇常州人，南京郵電大學碩士生，主要研究方向為5G網絡優化、無線大數據處理等。