以螞蟻演算法求解蜂巢式行動通訊系統之頻率指派問題

Using an Hybrid Ant Algorithm to Solving the Frequency Assignment Problem in Cellular Mobile Telecommunication Systems

周志隆(Chih-Lung Chou)

指導教授 ： 王孔政

中原大學/工學院/工業工程研究所/碩士(2003年)

https://doi.org/10.6840/cycu200300069

摘要

儘管行動式電話服務之需求日與遽增，然而，可供使用之電磁頻譜資源卻是嚴重短缺。蜂巢式行動通訊系統中的頻率指派計畫，其目的係用來妥善指配工作頻率給各基地台以服務眾多之使用者，並求其頻譜資源之最大使用效益。由於此類頻率指派問題是屬於NP-hard 最佳化問題，因此，對於現代複雜的大型行動式電話系統而言，若應用一般性數學解析法來求解是相當不切實際的。針對頻率指派問題所提出之研究文獻中，在1970至1990年代間，大多數根基於圖形著色理論所發展出之啟發式演算法均可歸類為非迭代演算法。自1990年代後，不同類型且較先進之迭代演算法陸續被提出，諸如限制滿足演算法、類神經演算法、模擬退火演算法、禁忌演算法以及基因演算法等等。然而，非迭代演算法與迭代演算法卻各有其優缺點。
在本論文中我們設計發展完成一種新的混合式演算法來求解之頻率指派問題，其目的是透過求解最小使用頻寬以達成頻譜資源之最大使用效益。我們將目前較新穎之螞蟻演算法以及傳統式循序指派策略中的頻率窮舉指派方法加以結合運用來快速計算出最佳頻率指派，此種混合式演算法我們稱之為混合式螞蟻演算法。混合式螞蟻演算法之效能驗證，係分別透過文獻上常被引用之兩類難易度不同之典範問題來求證。由實證結果得知：對較簡單之八個問題個案，我們的混合式螞蟻演算法均能快速求得最佳解，雖然對較困難之另五個問題個案，我們的方法雖無法在有限時間內求得最佳解，然而，卻能在合理誤差範圍內(平均6%以內)快速地求得良好的頻率指派，因此，我們設計的混合式螞蟻演算法是適合運用於快速求解蜂巢式行動通訊系統中的頻率指派問題。

關鍵字

蜂巢式行動通訊系統 ； 螞蟻演算法 ； 頻率指派問題

並列摘要

The demand for mobile telephone service is growing rapidly. On the other hand, the available electromagnetic frequency spectrum is severely limited. The aim of frequency assignment in the cellular mobile telecommunication system is to assign frequency channels to the radio transmitters in base stations in order to maximize some measures of spectral efficiency. The frequency assignment problem is known to be an NP-hard optimization problem. Thus, it is impractical to use the exact algorithms for realistic large sized problems. Most of the heuristic algorithms presented during the 1970’s to early 1990’s were categorized as the non-iterative approaches, which is based on the graph-coloring algorithms. Since 1990, different iterative approaches have been proposed for solving various versions of frequency assignment problem, such as the constraint satisfaction, artificial neural networks, simulated annealing, tabu search, genetic algorithm, etc. However, both kinds of solution approaches have its advantage and disadvantage.
In this thesis we present the designing and implement of a hybrid heuristic algorithm, which is the ant-based algorithm conjunction with one of the sequential assignment strategies (i.e., the frequency-exhaustive assignment) to compute the minimum span frequency assignment problem. The performance is verified through solving two sets of well-known Philadelphia benchmark test problems in the literature, called the easy problem and the difficult problem, respectively. For the easy problems, our algorithm is easy to find optimum solutions for all eight variants of the given test problem. For difficult problems, though our method did not reach optimum solutions (lower bounds) in limited time, in some cases, we get better solutions than some existing algorithm. And, for each of these harder problems, we always quickly obtained a solution within average 6% deviation of the optimum, which can be considered a promising result.

並列關鍵字

Cellular Mobile Telecommunication Systems. ； Frequency Assignment Problem ； Ant Algorithm ； Channel Assignment Problem

參考文獻

[Eisenblatter and Koster, 2000] Eisenblatter A. and Koster A. M. C. A., FAP web - A website devoted to frequency assignment, URL: http://fap.zib.de, 2000.

[Anderson, 1973] Anderson L.G., “A Simulation Study of Some Dynamic Channel Assignment Algorithms in a High Capacity Mobile Telecommunications System”, IEEE Trans. on Communications, COM-21: 1294-1301, 1973.

[Battiti et al., 2000] Battiti R., Bertossi A. and Cavallaro D., “A Randomized Saturation Degree Heuristic for Channel Assignment in Cellular Radio Networks”, Technique Report, University of Trento, Italy, 2000.

[Beckmann and Killat, 1999] Beckmann D. and Killat U., “A New Strategy for the Application of Genetic Algorithms to the Channel-Assignment Problem”, IEEE Transactions on Vehicular Technology, vol.48, no. 4, 1261-1269, 1999.

[Box, 1978] Box F., “A Heuristic Technique for Assigning Frequencies to Mobile Radio Nets”, IEEE Transactions on Vehicular Technology, vol.27, 57-74, 1978.