Both present and future communication networks are expected to support multiple and diverse applications and meet various quality of service (QoS) requirements. Accordingly, a key issue in the design and operation of a network is how the related resources should be provided in order to meet the requirements of each connection. Thus, this thesis addresses three kinds of network optimization problems for resource management in communication networks from the viewpoint of efficiently and effectively constructing and managing the network using limited resources
In order to solve the problems considered in this thesis, we introduce the following evolutionary computation algorithms-the genetic algorithm (GA) and coevolutionary algorithm (Co-EA)- as well as the tabu search (TS), all of which have proven useful in solving combinatorial problems. In applying the proposed methods to each problem, many of the elements are contrived to improve solution quality and computational efficiency, such as the genetic representation, evaluation function, genetic operators and procedures for GA and Co-EA; and the neighborhood structure and search strategy for TS. To promote population diversity and search efficiency in the algorithm, we also adopt strategies of localized evolution and steady-state reproduction, and develop the methods of selecting environmental individuals and evaluating fitness for Co-EA.
In the first problem, we propose heuristic evolutionary computation algorithms that can simultaneously solve the route selection and rate allocation problem in multirate multicast networks; that is, the problem of constructing multiple multicast trees and simultaneously allocating the rate of receivers f01 maximizing the sum of utilities over all receivers, subject to link capacity and delay constraints tor high-band width delay-sensitive applications in point-to point Communication networks. The results of extensive computational simulations show that the proposed algorithms provide high quality solutions, respond well to various situations of the network, and can be easily applied to the actual network.
In the second problem, we propose a genetic algorithm application to a nonhierarchical Multimedia-On-Demand (MOD) network and heuristic methods (TS and GA) for a two-level hierarchical MOD network design. Both server location and storage allocation are considered under network resource optimization based on cost analyses that include the installation costs for servers, program storage costs' and transmission costs. The comparisons made for various problem modifications are used for verifying the efficiency of the proposed methods, and high quality solutions are received within a reasonable time period of computations. the results of design for relatively large two-level hierarchical MOD networks are shown and the effects of several factors on network design are also analyzed.
In the third problem, we propose a distributed power control algorithm that employs the GA-based evolutionary computation (EC) algorithm in order to solve linear systems of equations for power update in CDMA cellular radio systems. The calculation results show that our proposed algorithm has a high potential advantage for decreasing mobile terminal power consumption and increasing CDMA cellular radio network capacity. DUE to the intrinsic features of the genetic algorithm, we are able to design a power control algorithm that adjusts the power level of each mobile to one of the discrete power levels. This aspect is quite important since we can imagine a direct application of the algorithm in a real system.
Furthermore, the most attractive feature of the proposed algorithms in this thesis is their reasonable flexibilities. These algorithms have the ability to handle various types of optimizations criteria and restrictions. With a little modification, they can be applied to solve many variants of problems.
현재 또는 미래의 정보통신 네트워크는 다양한 응용서비스를 제공할 수 있을 뿐만 아니라 서비스 품질에 대한 여러 요구도 만족시킬 것으로 기대된다. 이에 따라 서비스를 제공하기 위한 네트워크의 설계 및 운영에 있어서 각 연결의 요구조건을 만족하기 위하여 관련된 자원을 적절하게 제공 및 분배하는 방법에 관한 연구는 매우 중요하다. 따라서 본 논문은 제한된 자원 제약 하에서 효율적이며 효과적으로 네트워크를 구성하고 관리하기 위한 연구로, 정보통신 네트워크 자원 관리를 위한 세 가지 네트워크 최적화 문제를 다루고 있다.
문제의 크기가 커짐에 따라 이를 해결하는데 소요되는 계산 노력은 더욱 많이 필요로 하며, 계산 용량이 제한적이고 의사결정이 신속히 이루어져야 하는 때에 대규모 문제는 실제적으로 해결하기 어려울 수 있다. 이러한 경우에는 보다 적은 계산 시간 내에서 좋은 해를 구할 수 잇는 휴리스틱 접근법을 이용하는 것이 효율적일 수 있다. 이 방법은 항상 최적해를 보장하지는 않지만 근사 최적해를 비교적 짧은 시간 내에 구할 수 있으며 상대적으로 단순하고 효과적이다. 본 논문에서 다루는 문제들은 상대적으로 복잡도가 높은 문제에 해당된다. 따라서 이 문제들을 해결하기 위해 조합 최적화 문제를 해결하는데 유용하다고 알려진 진화 계산 알고리듬과 tabu search를 적용한다. 여기에서 진화 알고리듬은 단일 모집단을 이루고 잇는 개체들이 세대가 진행될수록 생물의 진화과정-자연선별(natural selection)과 유전법칙(genetic rules)-을 통해 평균적으로 더욱 좋아진다는 개념을 모형화하여 개발된 탐색기법이며, tabu search는 해의 탐색 과정을 기억한 후 되돌아가는 것을 금지(tabu)함으로써 해의 순환을 방지하고 부분 최적에서 벗어나 근사 최적해를 찾는 기법이다. 특히, 공진화 알고리듬은 자연계의 종들이 다른 종들과 서로 영향을 주고 받으며 진화하는 과정을 모방한 확률적 탐색 기법으로, 이는 여러 문제들이 서로 결합되어 있고 한 문제의 해가 변함에 따라 다른 문제들의 해가 영향을 받는 상황과 유사하다고 볼 수 있다. 따라서 이러한 특징을 가지는 첫 번째 최적화 문제-여러 전송률을 갖는 멀티캐스트 네트워크에서 트래픽이 전송되는 루트 선택과 각 루트의 전송률 할당을 동시에 결정하는 문제-를 해결하기 위해 이에 적합한 공진화 알고리듬을 제안한다. 본 논문에서 다루는 세가지 문제에 제안한 방법을 적용하면서 해의 결과 계산 효율성을 향상시키기 위해서, 진화 계산 알고리듬에서는 유전 표현, 평가 함수, 유전 연산자 및 알고리듬의 단계별 절차가, tabu search에서는 이웃 구조와 탐색 전략 및 단계별 절차 등의 여러 요소들이 각 문제의 특성에 맞도록 제안된다. 진화 알고리듬에서는 모집단의 다양성과 탐색 효율성을 높이기 위해 지역적인 (이웃) 진화 전략과 안정상태(steady-state) 재생산 방법이 사용되고, 공진화 알고리듬에서는 좋은 환경의 선택이 탐색 성능을 향상시킬 수 있는 중요한 요소가 되므로 환경 개체를 선택하는 방법과 적응도 평가방법이 개발된다.
본 논문에서 다루는 첫 번째 문제는 여러 전송률을 갖는 멀티캐스트 네트워크에서 트래픽이 전송되는 루트 선택과 동시에 각 루트의 전송률 할당에 관한 것이다. 다루는 문제는 링크 용량과 지연 시간에 대한 제약 조건을 만족 하면서 대 용량 대역폭을 필요로 하고 지연시간에 민감한 어플리케이션을 점대점 통신 네트워크에서 제공하기 위해 트래픽을 제공 받는 이용자들의 효용의 합을 최대화 하는 것을 목적으로 한다. 다수의 멀티 캐스트 트리 구성과 동시에 각 루트의 전송률을 할당하는 문제를 해결하기 위해 유전 알고리듬 뿐만 아니라 보다 효율적으로 해를 탐색하기 위한 공진화 알고리듬이 제안되었다. 다양한 시뮬레이션 결과, 제안한 알고리듬은 계층적 방법에 비하여 우수한 성능을 보이고 네트워크의 여러 상황에 잘 적응하며 실제 어플리케이션을 제공하는 네트워크에 쉽게 이용 가능함을 보였다.
두 번째 문제에서, 프로그램 저장 서버의 구축 비용과 프로그램 저장비용 및 프로그램 전송비용을 포함하여 관련된 비용 분석을 바탕으로 네트워크의 자원 최적화를 위한 MOD(Multimedia-On-Demand) 네트워크에서 프로그램 저장 서버의 위치와 프로그램 저장용량을 결정하는 방법을 제안하였다. 비계층 MOD 네트워크 설계에 유전 알고리듬을 이용하고, 2계층 MOD 네트워크 설계에 tabu search 와 유전 알고리듬이 각각 적용되었다. 해외 수준과 계산 시간측면에서 열거법과 비교를 통해 제안한 알고리듬의 성능을 분석하고, 다양한 형태의 문제에 응용하여 제안한 방법의 성능을 평가하였다. 실험 결과, 제안한 방법들은 적절한 시간 냉에 좋은 해를 찾음을 알 수 있었다. 추가적으로 상대적으로 규모가 큰 2 계층 MOD 네트워크의 설계 결과 및 네트워크 설계에 영향을 주는 다양한 요인에 대한 효과 분석이 제시되었다.
세 번째 문제에서는 CDMA 셀롤러 무선 시스템의 전력 조절을 위해 진화 계산 알고리듬을 적용한 분산 전력 제어 (power control) 알고리듬이 제안되었다. 시뮬레이션 결과에서, 제안한 알고리듬은 무선 단말기의 전력 소비를 줄이면서 CDMA 셀룰러 무선 네트워크의 용량을 증가시키는 잠재적 이점을 가지는 것으로 나타났다. 유전 알고리듬의 본질적인 특징에 의해, 이산적인 수준으로 각 무선 단말기의 전력 수준을 조정할 수 있는 전력 제어 알고리듬의 설계가 가능하며, 이는 실제 운영 시스템에 제안한 알고리듬을 직접 활용할 수 있다는 점에서 의미가 있다.
본 논문에서 제안한 알고리듬의 특징 중에 하나는 진화 알고리듬이 갖는 적용의 유연성을 갖는다는 것이다. 목적이 변경되거나 제약이 추가되는 문제뿐만 아니라, 복잡하고 동적인 여러 형태의 문제에 쉽게 응용 가능하다. 따라서 제안한 알고리듬은 다양한 최적화 문제의 목적과 제약을 다룰 수 있고, 조금 수정하게 되면 여러 다양한 최적화 문제를 해결하는데 이용할 수 있다.
