林永松臺灣大學：資訊管理學研究所林明立Lin, Ming-LiMing-LiLin2007-11-262018-06-292007-11-262018-06-292004http://ntur.lib.ntu.edu.tw//handle/246246/54197無論是使用者或是電信業者都迫切地期待著第三代行動通訊的來臨，而本論文的目的在於提供電信業者一有效率的基地台架設演算法使其在知道使用者分佈的情況下得到最大利潤。 在WCDMA系統中，容量限制以訊雜比(signal-to-interference ratio, SIR)為主要依據，而本篇論文以能量為資源，加入頻寬切割之要素，依此設計出一基地台架設演算法，並讓電信業者能規劃出適當的頻寬切割方式。本論文針對WCDMA的系統，同時考慮上下行系統容量限制、漂亮地設計出此非線性問題並採用拉格蘭氏鬆弛法處理此一複雜問題而得到一令人滿意的結果。The diffusion and demand of mobile communication services are still growing rapidly nowadays. Users are no longer satisfied with merely speeches but eager to communicate with each other by multimedia services. That’s the reason why the approach to the base station deployment optimization problem is so urgent and important. Many researches have been pronounced to solve the deployment problem. We combined the most important issues, such as downlink SIR constraint, uplink SIR constraint, soft handover, sectorization, and power control, frequency assignment into consideration. We developed a mathematical programming model to describe this joint design problem. It turns out to be a non-linear non-convex mixed integer programming problem. A set of heuristic solution procedures based on Lagrangian relaxation methods is proposed to solve the complicated problem.謝 詞 I 論文摘要 III THESIS ABSTRACT V Table of Contents VII List of Tables IX List of Figures XI Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Literature Survey 3 1.2.1 WCDMA technique 3 1.2.2 WCDMA interference model, capacity issue 4 1.2.3 Frequency assignment issues 5 1.2.4 Relative Works in 3G Base Station Deployment 6 1.2.5 Soft Handoff 8 1.2.6 Sectorization and Softer handoff 10 1.2.7 Lagrangian Relaxation 12 1.3 Proposed Approach 13 Chapter 2 Problem Formulation 15 2.1 Problem Description 15 2.2 Notation 17 2.3 Problem Formulation 19 Chapter 3 Solution Approach 25 3.1 Lagrangian Relaxation 25 3.1.1 Subproblem 1 ( ) 28 3.1.2 Subproblem 2 ( ) 30 3.1.3 Subproblem 3 (related to decision variables ) 33 3.2 The Dual Problem and the Subgradient Method 33 3.3 Model Extension and Modification 34 3.4 Alternative approach to model downlink SIR problem and complexity comparison 38 Chapter 4 Getting Primal Feasible Solutions 45 4.1 Heuristic for deployment selection 46 4.2 Heuristic for Uplink Power Adjustment 47 4.3 Heuristic for Downlink Power Adjustment 48 Chapter 5 Computational Experiments 49 5.1 Lagrangian Relaxation Base Algorithm (LR) 49 5.2 Parameters and Cases of the Experiment 50 5.3 Experiment result 53 5.4 Result Discussion 55 Chapter 6 Conclusion 57 6.1 Summary 57 6.2 Future Work 58 References 59332634 bytesapplication/pdfen-US容量管理數學最佳化服務品質第三代行動通訊系統基地台架設寬頻分工多重擷取系統(WCDMA)拉格蘭氏鬆弛法OptimizationMathematical ProgrammingLagrangian Relaxation Method3rd Generation Wireless SystemQuality of ServiceWCDMABase Station Deployment Algorithmotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54197/1/ntu-93-R91725025-1.pdf