第三代行動通訊系統(3G)發展至今已經超過十年,台灣的3G系統主要是以W-CDMA (Wideband Code-Division Multiple Access,寬頻分碼多工)系統為主,根據今年政府提供的國情統計情報,今年一月3G用戶已經超過兩千一百萬戶,較去年同期增加11%以上,故系統供應商需要增加基地台的數量,以應付增加中的用戶。本研究目的為於昂貴的成本以及使用者需求下,如何於以存在或是完全無配置基地台的區域中進行設置。 在W-CDMA系統中,可以透過系統的表現以及成本進行基地臺配置結果的評估,而系統的表現又可以分成訊號覆蓋率、使用者流量需求滿足率、基地台負載率以及訊號干擾率數項因子,而這些因子之間會有互相影響的現象產生,因此,要同時滿足上述各項條件則成為一NP-Hard的問題,故需要運用演算法找出規畫過程中可能解中的最佳解。 本研究所使用的啟發式演算法為基因演算法,經常使用在網路規劃的研究上,其自然演化的特性可以使基地台配置之演化過程中比較不會受到人為因素的控制以及影響,並且能透過突變來跳脫區域最佳解的情況,以得到在可行解中配適程度較高的配置結果,並透過實驗以及禁忌演算法(Tabu Search)驗證其可用性。
Third generation communication system has now been developed over ten years and has several systems in used. In Taiwan, WCDMA system is mainly proposed and tenants are still in growth. According to Government Statistic Report, number of tenants in 3G system aroused over 21 million, which represents the need of 3G base stations to cover the requirement of increasing users. This paper proposed a multi-criteria system that can deploy the base station in different kinds of deploying environment. In WCDMA system, the system can be evaluated through performance and cost, which the performance of the system is divided into signal coverage, user requirement fulfill rate, base station loading and signal interference. The goal of the research is to maximum the value of each criterion, but to find a deployment with all criteria fulfilled is a NP-Hard problem, so we need to solve the problem through heuristic algorithm. This paper proposed Genetic Algorithm, which is often used in network planning. The natural inspire of algorithm makes the result less to be controlled and affect by human factors, also, genetic algorithm has mutation mechanism to escape from local Optimal Solution to gain more opportunity to reach better deployment. This paper prove the availability of system through experiments and finally obtain the results that the system can be proposed in different kind requirement of the system provider and is well performed than Tabu search in some conditions.