- 學位論文
無線通訊系統中行動小型基地台之部署
Mobile Small Cell Deployment in Wireless Communication Systems
摘要
在次世代蜂巢式網路中引入小型基地台為一種實際可行且具經濟效益的低成本方式，能有效紓解呈爆炸性增長的行動寬頻數據流量。然而，靜態小型基地台的佈建無法符合隨時空環境變化之動態資料流需求，若小型基地台處於閒置或低使用效率的狀態將會導致資源浪費，進而降低整體系統效能。有鑒於此，本論文運用行動小型基地台的概念，並試圖尋找最佳之佈建策略。若能使用有限個行動小型基地台盡可能地長時間服務多數使用者，則愈能彰顯行動小型基地台佈建之效益。為了展現佈建策略對於系統效能之影響性，本論文分別以車輛和空中飛行載具作為搭載行動小型基地台之載具。我們首先著眼於二維平面上行動小型基地台的佈建議題，主要目標為最大化車載行動小型基地台可提供給使用者的總服務時間。尤其是，我們觀察到該最大化服務時間的問題展現了一個有趣的取捨現象―介於使用者稠密度和移動小型基地台所花費的移動時間之間。我們證明此問題為NP-hard問題，並證明此問題在多項式時間內可找到之最佳近似解比例為(1-1/e)，除非P=NP。隨後，我們提出一個可在多項式時間內執行之(1-1/e)倍近似演算法來解該問題，而該演算法亦為其中一種最佳近似演算法。得到二維平面行動小型基地台的佈建初步成果後，我們進一步探討三維空間中行動小型基地台的佈建議題。透過無人機載具搭載小型基地台，以使用者為服務對象，旨在最大化無人機傳送之總資料量。由於該問題的非凸非線性特性，我們使用Lagrangian dual relaxation和subgradient projection方法來解該佈建規劃問題，同時亦提出一個啟發式演算法來處理飛行高度、移動時間及飛行壽命之間的權衡問題。最後，透過一系列具真實環境參數設定之實驗來評估提出方法的性能，以提供更多有助於無線通訊系統動態佈建與規劃移動型小型基地台之觀點。
並列摘要
One viable and low-cost method of accommodating the explosive growth of mobile broadband traffic is to introduce small cells for next generation cellular networks. However, static small cells cannot be flexibly placed to meet the demand of time/space-varying traffic, and idle or under-utilized cells would result in resource wastage and system performance degradation. Therefore, this dissertation adopts the mobile small cell concept and seeks to optimize the deployment of mobile small cells. If a finite number of mobile small cells can serve more users for more time, the mobile small cell deployment will have more gains. To reveal the performance gains from proper deployment strategies, this dissertation uses ground and airborne vehicles respectively to serve as the carriers for mobile small cells. We first target the deployment problem on the ground with the objective of maximizing the total service time of all users. Specifically, service time maximization exhibits an interesting trade-off between the user density and the travel time of mobile small cells. We prove that our target problem is NP-hard and cannot be approximated in polynomial time with a ratio better than (1 – 1/e), unless P = NP. To solve the problem, we propose a polynomial time (1 – 1/e)-approximation algorithm, and the proposed algorithm is one of the best approximation algorithms based on the inapproximability ratio. Next, we extend our preliminary results on 2D deployment to further accommodate the flexible deployment of flying unmanned aerial vehicles (UAVs). As the residual battery capacity available to UAVs determines the lifetime of an airborne network, it is essential to account for the energy expenditure on various flying actions in a flight plan. The focus of this part is therefore on studying the 3D deployment problem for a swarm of UAVs, with the goal of maximizing the total amount of data transmitted by UAVs. In particular, we address a thrilling trade-off among the flight altitude, the energy expense and the travel time. We formulate the problem as a non-convex non-linear optimization problem and propose an energy-aware 3D deployment algorithm to resolve it with the aid of Lagrangian dual relaxation, interior-point and subgradient projection methods. Afterwards, we prove the optimality of a special case derived from the convexification transformation. The capabilities of the above-mentioned proposed algorithms are evaluated by conducting a series of simulations with realistic parameter settings, providing insightful and encouraging results in mobile small cell deployment for wireless communication systems.