長期演進技術下異質網路之佈建演算法與最佳化方法設計及分析

The Design and Analysis of Deploying Algorithms along with Optimization Methods for the Long Term Evolution Heterogeneous Networks

謝松晏(Sung-Yen Hsieh)

指導教授 ： 張時中 ； 魏學文

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2014年)

https://doi.org/10.6342/NTU.2014.02931

摘要

在長期演進技術(LTE)下的異質網路中，諸如微微細胞(picocell，一種小型的無線通信網路)以及毫微微細胞(femtocell，一種微型的無線通信網路)等的小細胞(small cell)被佈建在原有的巨細胞(macrocell，傳統的大型無線通信網路)上來補償大型網路(macro network)的容量及信號涵蓋限制。電信業者在室外佈建picocell來提升網路的容量而femtocell則是被使用者建置在室內以補償信號涵蓋的不足。本研究探討室外LTE的picocell規劃的問題，在給定的大型網路架構下，企圖找出最佳的picocell佈建方式。

微微基地台(pico base station)是一種低功率的小型基地台，可以被電信業者佈建用以滿足室外使用者對數據傳輸速率的需求，特別是那些人口眾多的熱點區域(hotspot)。倘若微微基地台沒有被妥善的建置的話，LTE異質網路內部將會有細胞間干擾(inter-cell interference)問題。而電信業者在規劃微微網路時如果沒有考慮需求分布或是干擾問題的話，將會導致使用者的負面使用經驗，進而造成營收下降。

因此，在LTE微微細胞規劃的問題(LTE picocell planning problem)中，我們將從電信業者的觀點出發，企圖設計最佳的微微網路。亦即，我們想找出最佳的微微細胞數目、位置、功率以及頻率，還有微微細胞以及巨細胞的服務範圍。在給定由電信業者預估的需求分布以及可以佈建的微微細胞數目之下，企圖最大化LTE異質網路提供的傳輸速率(throughput)。為了貼切的描述我們想規劃異質網路的區域(target area)之需求分布，我們建立了數據需求分布點模型(throughput demand distribution grid model)。在這個模型中，欲佈建picocell的區域被切割成許多小的格子區域(grid)，在每個格子點中間都有一個需求點(demand point)來代替該格子點。藉由數據需求分布點模型的引入，我們建立了數個最佳化問題的數學模型來描述LTE微微網路規劃問題。我們證明了LTE微微網路規劃問題至少是一種NP-完全(NP-complete)的問題，亦即有很高的機會不存在有效率的演算法可以解決它。因此我們設計了一個名為依次佈建演算法(Sequential Deployment Algorithm，SDA)的近似演算法來求近似解(near-optimal solution)。

數值實驗顯示在平坦且需求均勻分布的區域中，SDA所產出的微微網路架構呈現完全均勻分布的樣態，而在不平坦或不均勻需求分布的區域中，SDA所產出的微微網路架構則是不均勻的。從數據實驗中可以看出兩項趨勢，第一個趨勢是高需求的區域會由較多的微微細胞以低功率所服務，反之低需求的區域會由較少的微微細胞以較高的功率所服務。第二個趨勢是坐落於大細胞天線(macro antenna)所指向的區域需要較少的微微細胞。

關鍵字

LTE異質網路 ； 巨細胞 ； 微微細胞 ； 毫微微細胞 ； 室外 ； 容量 ； LTE微微細胞規劃 ； 最佳的微微網路 ； 數據需求分布點模型 ； 細胞間干擾 ； NP-完全 ； 依次佈建演算法

並列摘要

In LTE heterogeneous networks, small cells such as picocells and femtocells are overlaid on originally-deployed macrocells to compensate the limited capacity and signal coverage of macro networks. Picocells are deployed by operators for outdoor capacity improvement while femtocells are installed by subscribers to compensate the indoor signal coverage. In this research, we study the outdoor LTE picocell planning problem that determines configuration of picocells under LTE macro networks. Pico base stations are tiny infrastructures with low transmission power, and hence can be deployed by operators to satisfy the throughput requirement of outdoor subscribers, especially in hotspots where many subscribers locate. However, LTE heterogeneous networks may have inter-cell interference if pico base stations are not well-configured. Bad subscriber experience arises when operators do not plan their picocells according to throughput demand distribution or plan picocells without taking interference issues into considerations.

Thus, in the LTE picocell planning problem, we stand in operators’ shoes, aiming to find the best design for picocells, i.e., the number, locations, transmission powers, carrier frequencies of picocells, and service areas of each cell. Assume the number of available picocells is given, we want to maximize the system throughput of LTE heterogeneous networks under the given throughput demand distribution estimated by operators. Still, to describe the throughput demand within the target area where we want to deploy picocells, we design the throughput demand distribution grid model. In this model, the target area is divided into several small grids with demand points as representatives of grids and site points where operators can deploy pico base stations. With the throughput demand distribution grid model, several optimization problems were formulated to model the LTE picocell planning problem. We show that the formulated LTE picocell planning problem belongs to NP-complete which is a set of problems generally believed that there exist no efficient algorithms to solve them. Therefore, we design an approximation algorithm called the sequential deployment algorithm that solves the near-optimal picocell configuration.

Our numerical experimentation results show that under a flat area with uniform demand distribution, the near-optimal picocell configuration is symmetric in picocell configuration, while in a flat area with non-uniform demand distribution, the resulting picocell configuration is asymmetric. In urban areas with uniform or non-uniform demand distribution, derived picocell configurations are both asymmetric. There are two main insights derived from our numerical experimentations, the first one is that many picocells with low transmission powers are tend to be deployed in regions with high throughput demands, and the vice versa, i.e., few picocells with high powers are tend to be deployed in areas with low throughput demands. The second one is that there tend to be less need for picocells in regions located at the direct signal paths of macro antennas.

並列關鍵字

LTE heterogeneous networks ； macrocell ； picocell ； femtocell ； outdoor ； capacity ； LTE picocell planning problem ； maximize the system throughput ； optimal picocell configuration ； throughput demand distribution grid model ； inter-cell interference ； NP-complete ； sequential deployment algorithm

參考文獻

[1] J. Zhang and G. de la Roche, “Femtocells: Technologies and Deployment,” John Wiley & Sons Ltd., 2010.

[2] I. Akyildiz, D. M. Gutierrez-Estevez, R. Balakrishnan, and E. Chavarria-Reyes, “LTE-Advanced and the evolution to Beyond 4G (B4G) systems,” Physical Communication, Vol. 10, pp. 31–60, March 2014.

[4] H. Shimodaira, G. Tran, S. Tajima, K. Sakaguchi, K. Araki, N. Miyazaki, S. Kaneko, S. Konishi, and Y. Kishi, “Optimization of Picocell Locations and Its Parameters in Heterogeneous Networks with Hotspots,” Proceedings of 2012 IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications, pp.124-129, Sept. 2012.

[5] K. Han, Y. Choi, D. Kim, M. Na, S. Choi, and K. Han, “Optimization of Femtocell Network Configuration under Interference Constraints,” Proceedings of 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, WiOPT, pp. 1-7, June 2009.

[6] A. F. Molish, “Wireless Communications,” John Wiley & Sons Ltd., 2011.