[논문]이동통신에서 리포팅 셀 계획을 위한 타부서치 기반 최적화 알고리즘

장길웅

doi:10.6109/jkiice.2020.24.9.1193

이동통신에서 리포팅 셀 계획을 위한 타부서치 기반 최적화 알고리즘
Tabu Search based Optimization Algorithm for Reporting Cell Planning in Mobile Communication 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.24 no.9, 2020년, pp.1193 - 1201

장길웅 (Department of Data Informatics, Korea Maritime and Ocean University)

초록
AI-Helper

이동통신에서 이동단말의 위치관리를 위해 셀 구조를 결정하는 셀 계획은 네트워크 성능을 결정하는 중요한 연구과제로 다루어지고 있다. 이동통신에서 셀 구조를 계획하는데 영향을 주는 요소 중 위치관리를 위한 신호비용이 가장 중요한 역할을 하고 있다. 본 논문에서는 이동통신에서 리포팅 셀 구조를 가진 네트워크에서 셀 구조를 계획하기 위해 사용되는 모든 셀의 위치관리비용을 최소화 하는 최적화 알고리즘을 제안한다. 제안된 알고리즘은 메타휴리스틱 알고리즘인 타부서치 알고리즘을 사용하며, 제안된 알고리즘은 새로운 이웃해 생성방식을 제안하여 최적해에 가까운 결과를 도출한다. 제안된 알고리즘의 성능을 평가하기 위해 위치관리비용과 알고리즘 수행시간 관점에서 시뮬레이션을 수행하였다. 평가 결과에서 기존의 유전 알고리즘 및 모의 담금질 기법과 비교 평가하여 제안된 알고리즘의 성능이 우수함을 볼 수 있었다.

Abstract ▼ AI-Helper

Cell planning, which determines the cell structure for location management of mobile terminals in mobile communications, has been dealt with as an important research task to determine network performance. Among the factors influencing the cell structure planning in mobile communication, the signal cost for location management plays the most important role. In this paper, we propose an optimization algorithm that minimizes the location management cost of all the cells used to plan the cell structure in the network with reporting cell structure in mobile communication. The proposed algorithm uses a Tabu search algorithm, which is a meta-heuristic algorithm, and the proposed algorithm proposes a new neighborhood generation method to obtain a result close to the optimal solution. In order to evaluate the performance of the proposed algorithm, the simulation was performed in terms of location management cost and algorithm execution time. The evaluation results show that the proposed algorithm outperforms the existing genetic algorithm and simulated annealing.

주제어

표/그림 (9)

그림 Fig. 1 Example of network with reporting cell
그림 Fig. 2 Process of vicinity value (a) initial values of cells (b) vicinity values of cells
그림 Fig. 3 Procedure of proposed Tabu search algorithm
그림 Fig. 5 Move examples (a) current solution (b) add move (c) remove move (d) replace move
그림 Fig. 4 Solution encoding structure
표 Table. 1 Performance comparison of proposed Tabu search, genetic algorithm and simulated annealing
표 Fig. 6 Average location management cost according to the network size
표 Fig. 7 Execution time according to the network size
표 Fig. 8 Average location management cost according to the number of generations

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 리포팅 셀 구조의 이동통신에서 이동단말의 위치관리를 위한 위치등록과 페이징 절차에 소모되는 비용을 최소화하는 최적화 알고리즘을 제안한다. 리포팅 셀 계획은 NP-complete 문제라는 것이 이전연구에서 증명되어 있다[5].
본 논문에서는 셀 i로 이동하는 이동단말의 수를 mi, 셀 j에 발생하는 콜의 수를 a_j라고 정의했을 때, 리포팅 셀에서 발생하는 위치등록 비용은 수식 (2)와 같이 리포팅 셀로 진입하는 이동단말의 총합으로 나타낼 수 있다. 반면에 페이징 비용은 수식 (3)과 같이 모든 셀에 대해 각 셀에서 발생하는 콜의 수와 각 셀에서 인접셀에 대한 검색 범위 v_j를 곱한 값의 총합과 같다.
본 논문에서는 이동통신에서 리포팅 셀 계획을 위하여 제안된 타부서치 알고리즘의 성능을 컴퓨터 시뮬레이션을 이용하여 평가하였다. 본 논문에서 수행한 컴퓨터 시뮬레이션은 윈도우 10 운영체제에서 3.
NP-complete 문제를 해결하기 위해서는 방대한 시간이 요구되며, 주로 이전 연구에서는 근사치를 이용한 휴리스틱 알고리즘을 사용하였다. 본 논문에서는 효율적인 결과를 얻기 위해 메타휴리스틱 기법 중 하나인 타부서치(Tabu search) 알고리즘을 적용한 최적화 알고리즘을 제안한다. 제안된 타 부서치 알고리즘은 다양한 조건하에서 위치관리를 위한 비용과 알고리즘 수행시간 측면에서 기존의 메타 휴리스틱 알고리즘과 성능을 비교한다.
본 논문은 이동통신에서 위치관리비용 관점에서 리포팅 셀 구조를 계획하기 위한 최적화 알고리즘을 제안하였다. 최적화 알고리즘은 위치관리비용을 최소화하는 타부서치 알고리즘을 사용하였으며, 제안된 타 부서치 알고리즘은 다음과 같은 절차에 따라 수행되었다.
본 절에서는 제안된 타부서치 알고리즘의 이동방식에 대하여 기술한다. 제안된 이동방식은 그림 4의 해의 인코딩에서 각각의 셀에 해당되는 요소에 적용하는 3가지 방식으로 구성된다.
[10]은 같은 문제에 대하여 모의 담금질(simulated annealing) 기법을 사용하여 최적에 가까운 위치관리비용을 찾는 알고리즘을 제안하였다. 이 논문에서는 다른 알고리즘과의 비교 없이 자체 알고리즘 변수만을 변경하여 결과를 제시하였다.
제안된 타부서치 알고리즘은 리포팅 셀 구조의 이동통신 네트워크의 셀 계획에서 위치관리비용을 최소화하는 데 목적이 있다. 결과적으로 이동통신 네트워크의 리포팅 셀 계획의 최적화 문제는 다음과 같은 목적함수를 가진 조합 최적화 문제로 정식화된다.

가설 설정

같다. 네트워크는 셀 단위로 적용되었으며, 각 셀은 그림 1처럼 바로 인접한 셀이 최대 6개인 육각형 형태로 가정하였다. 네트워크의 구조는 4 × 4, 6 × 6, 8 × 8, 10 × 10, 12 × 12 셀 구조를 가진 5가지 네트워크로 구성하였다.

제안 방법

최적화 알고리즘은 위치관리비용을 최소화하는 타부서치 알고리즘을 사용하였으며, 제안된 타 부서치 알고리즘은 다음과 같은 절차에 따라 수행되었다. 먼저 위치관리문제에 적합한 해의 인코딩을 우선 설계하였으며, 이를 이용해 하나의 초기해를 생성하고 추가이동, 삭제이동, 교환이동이라는 새로운 3가지의 이웃해 생성방식을 제안하여 최적해에 접근하였다. 제안된 알고리즘의 성능은 이동통신에 적용된 모든 셀의 위치관리를 위한 비용을 계산하였으며, 이전 연구에서 제안된 유전 알고리즘 및 모의 담금질 기법과 비교 평가하였다.
이용하여 평가하였다. 본 논문에서 수행한 컴퓨터 시뮬레이션은 윈도우 10 운영체제에서 3.6GHz 인텔 CPU와 4G 바이트의 메모리로 구성된 컴퓨터에서 수행하였으며, 제안된 알고리즘과 비교 평가된 알고리즘은파이썬을 사용하여 구현되었다. 제안된 타부서치 알고리즘을 평가하기 위한 항목은 모든 셀에서 발생하는 위치관리비용이며, 위치관리비용은 위치등록과 페이징에 소모되는 비용을 합한 값으로 계산하였다.
제안된 이동방식은 그림 4의 해의 인코딩에서 각각의 셀에 해당되는 요소에 적용하는 3가지 방식으로 구성된다. 본 논문에서는 3가지 이동방식을 추가이동, 삭제이동, 교환이동이라고 칭한다.
타부서치 알고리즘의 성능을 높이기 위해 타부리스트의 길이를 가변적으로 변경함으로써 NP-complete 문제를 효율적으로 처리할 수 있다는 결과도 이전 연구에서 제시되고 있다[10]. 본 논문에서도 제안된 타부서치 알고리즘에 동적으로 크기가 변하는 타부 리스트를 적용하였으며, n개의 요소를 가진 해에 대하여 타부리스트의 크기를 매번 10번 주기마다 n/2에서 n 사이의 값으로 변경시킨다. 타부리스트는 큐의 형태로 구성되며, 선택된 새로운 해가 계속적으로 저장되어 타부 리스트가 가득 차게 되면 가장 먼저 입력된 해를 제거함으로써 새로운 해를 저장하게 된다.
이웃해 생성 방식은 문제와 인코딩 방식에 따라 다양한 방식이 사용될 수 있다. 새로 생성된 이웃해 중 가장 좋은 결과를 가진 해를 선택하여 기존의 임시해와 비교한다. 만약 새로운 해가 임시해보다 더 좋은 결과를 가질 경우 이 해를 임시해로 변경하고 타부 리스트에 저장한다.
본 절에서는 제안된 타부서치 알고리즘의 이동방식에 대하여 기술한다. 제안된 이동방식은 그림 4의 해의 인코딩에서 각각의 셀에 해당되는 요소에 적용하는 3가지 방식으로 구성된다. 본 논문에서는 3가지 이동방식을 추가이동, 삭제이동, 교환이동이라고 칭한다.
본 논문에서는 효율적인 결과를 얻기 위해 메타휴리스틱 기법 중 하나인 타부서치(Tabu search) 알고리즘을 적용한 최적화 알고리즘을 제안한다. 제안된 타 부서치 알고리즘은 다양한 조건하에서 위치관리를 위한 비용과 알고리즘 수행시간 측면에서 기존의 메타 휴리스틱 알고리즘과 성능을 비교한다.
제안된 타부서치 알고리즘에서는 3가지 이동방식을 이용하여 새로운 이웃해를 생성하고, 그 중 가장 좋은 해를 임시해와 비교하여 최종적으로 최적해를 찾는다. 이 때 새로 구해진 해와 임시해를 비교할 때 제안된 알고리즘에서 미리 반복횟수를 설정하여 새로운 해가 임시해보다 좋은 결과가 연속적으로 나타나는 횟수가 반복 횟수만큼 발생하지 않으면 알고리즘은 종료된다.
제안된 타부서치 알고리즘을 수행하기 위해 리포팅 셀 계획에 적합한 인코딩 작업을 우선 수행한다. 인코딩 작업은 해결하고자 하는 문제에 맞는 해 구조(solution structure)를 설계하는 과정으로 해 구조에 따라 프로그램 성능이 차이가 나타남으로 인하여 중요한 요소 기술이 된다.
6GHz 인텔 CPU와 4G 바이트의 메모리로 구성된 컴퓨터에서 수행하였으며, 제안된 알고리즘과 비교 평가된 알고리즘은파이썬을 사용하여 구현되었다. 제안된 타부서치 알고리즘을 평가하기 위한 항목은 모든 셀에서 발생하는 위치관리비용이며, 위치관리비용은 위치등록과 페이징에 소모되는 비용을 합한 값으로 계산하였다. 또한 많은 계산을 요하는 NP-complete 문제에서 알고리즘 수행 시간 관점에서도 기존 알고리즘과 비교 평가하였다.
이동단말의 위치를 관리하기 위한 방식으로 크게 3가지 방식이 주로 사용되고 있다[3]. 첫 번째 방식은 이동단말이 새로운 셀로 진입할 때 마다 항상 위치 정보를 기지국으로 전송하여 위치를 등록하는 것이다. 이 방식은 이동단말로 수신 콜이 발생했을 때 별도의 페이징 동작 없이 콜을 수신할 수 있지만 위치등록을 위한 자원 소비가 높다는 것이 특징이다.

대상 데이터

네트워크는 셀 단위로 적용되었으며, 각 셀은 그림 1처럼 바로 인접한 셀이 최대 6개인 육각형 형태로 가정하였다. 네트워크의 구조는 4 × 4, 6 × 6, 8 × 8, 10 × 10, 12 × 12 셀 구조를 가진 5가지 네트워크로 구성하였다. 각 네트워크에서 셀 i로 이동하는 단말의 수(m_i)는 0에서 1000 사이의 랜덤값으로 설정하고, 셀 i에 발생하는 콜의 수(a_i)는 0에서 2000 사이의 랜덤값으로 설정하였다.

데이터처리

관점에서 비교한 것이다. 각 알고리즘을 10번씩 시도하여 평균값과 최소값, 최대값, 표준편차로 나타내었다. 결과에서 제안된 타부서치 알고리즘의 성능이 기존의 유전 알고리즘이나 모의 담금질 기법에 비해 성능이 우수함을 알 수 있다.
제안된 타부서치 알고리즘을 평가하기 위한 항목은 모든 셀에서 발생하는 위치관리비용이며, 위치관리비용은 위치등록과 페이징에 소모되는 비용을 합한 값으로 계산하였다. 또한 많은 계산을 요하는 NP-complete 문제에서 알고리즘 수행 시간 관점에서도 기존 알고리즘과 비교 평가하였다. 비교 대상 알고리즘은 제안된 타부서치 알고리즘과 같은 유형의 메타휴리스틱 알고리즘인 유전 알고리즘[9]과 모의 담금질 기법[10]을 비교 평가하였다.
또한 많은 계산을 요하는 NP-complete 문제에서 알고리즘 수행 시간 관점에서도 기존 알고리즘과 비교 평가하였다. 비교 대상 알고리즘은 제안된 타부서치 알고리즘과 같은 유형의 메타휴리스틱 알고리즘인 유전 알고리즘[9]과 모의 담금질 기법[10]을 비교 평가하였다.
먼저 위치관리문제에 적합한 해의 인코딩을 우선 설계하였으며, 이를 이용해 하나의 초기해를 생성하고 추가이동, 삭제이동, 교환이동이라는 새로운 3가지의 이웃해 생성방식을 제안하여 최적해에 접근하였다. 제안된 알고리즘의 성능은 이동통신에 적용된 모든 셀의 위치관리를 위한 비용을 계산하였으며, 이전 연구에서 제안된 유전 알고리즘 및 모의 담금질 기법과 비교 평가하였다. 성능평가에서 제안된 타부서치 알고리즘이 기존의 방식에 비해 성능이 우수함을 볼 수 있었으며, 결론적으로 제안된 타부서치 알고리즘이 이동통신에서 리포팅 셀구조를 계획함에 있어 최적화 기법으로 적용될 수 있음을 확인할 수 있었다.

이론/모형

최적화 알고리즘은 위치관리비용을 최소화하는 타부서치 알고리즘을 사용하였으며, 제안된 타 부서치 알고리즘은 다음과 같은 절차에 따라 수행되었다. 먼저 위치관리문제에 적합한 해의 인코딩을 우선 설계하였으며, 이를 이용해 하나의 초기해를 생성하고 추가이동, 삭제이동, 교환이동이라는 새로운 3가지의 이웃해 생성방식을 제안하여 최적해에 접근하였다.

성능/효과

결과에서 평균값은 기댓값을 의미하며, 최대값은 최악의 경우(worst case)를 의미하는 것으로 각 알고리즘이 각 네트워크 상황에서 가장 최악의 성능을 나타낸다. 결과에서 기댓값이나 최악의 경우에도 제안된 타부서치가 다른 알고리즘에 비해 좋은 성능을 나타내고 있다. 리포팅 셀 계획에서 제안된 타 부서치 알고리즘이 같은 종류의 메타휴리스틱 알고리즘인 유전 알고리즘과 모의 담금질 기법보다 좋은 성능을 보인 이유는 제안된 타부서치 알고리즘에서 사용된 이웃해 이동방식이 적절히 잘 동작하여 최적해에 가까운 해로 빠르게 수렴하였기 때문이다.
각 알고리즘을 10번씩 시도하여 평균값과 최소값, 최대값, 표준편차로 나타내었다. 결과에서 제안된 타부서치 알고리즘의 성능이 기존의 유전 알고리즘이나 모의 담금질 기법에 비해 성능이 우수함을 알 수 있다. 결과에서 평균값은 기댓값을 의미하며, 최대값은 최악의 경우(worst case)를 의미하는 것으로 각 알고리즘이 각 네트워크 상황에서 가장 최악의 성능을 나타낸다.
그림에서 제안된 타부서치 알고리즘은 다른 알고리즘에 비해 적은 횟수에서 빠르게 최종해에 접근함을 볼 수 있으며, 다른 알고리즘은 10회 이후에 최종해에 근접함을 볼 수 있다. 결론적으로 NP-complete인 리포팅 셀 계획에 대하여 제안된 타부서치 알고리즘이 적절한 알고리즘 수행시간 내에 위치관리용비용을 최소화할 수 있다는 것을 알 수 있었다.
반면에 유전 알고리즘은 고정된 수의 해를 이용하여 이웃해를 검색하기 때문에 네트워크의 크기가 증가하더라도 알고리즘 수행시간은 거의 선형증가를 하게 된다. 따라서 네트워크의 크기가 증가할수록 제안된 타부서치 알고리즘은 유전 알고리즘에 비해 수행 시간은 더 크게 증가하게 된다. 반면에 제안된 타 부서치 알고리즘이 모의 담금질 기법에 비해 수행시간이 적게 걸리는 이유는 제안된 타부서치 알고리즘의 이웃해 이동방식이 빠르게 최적해로 접근함으로써 수행 시간을 줄였기 때문이다.
그림 2에서 설명한 바와 같이 각 셀은 리포팅 셀 여부, 인접값, 페이징 될 셀 목록을 가져야 한다. 따라서 본 논문에서 구현된 타부 서치 알고리즘에서도 네트워크 모델과 같이 각 셀은 리포팅 셀 여부, 인접값, 페이징 될 셀 목록을 가진 클래스 형태로 구현되었다.
즉 해의 길이가 길면 상대적으로 이웃해를 많이 발생하게 된다. 따라서 본 논문에서 적용되는 네트워크의 크기가 커짐에 따라 셀의 수가 기하급수적으로 증가하게 되고, 동시에 이웃해의 수도 기하급수적으로 증가함으로써 알고리즘 수행시간도 그림에서와 같이 기하급수적으로 증가하게 된다. 반면에 유전 알고리즘은 고정된 수의 해를 이용하여 이웃해를 검색하기 때문에 네트워크의 크기가 증가하더라도 알고리즘 수행시간은 거의 선형증가를 하게 된다.
제안된 알고리즘의 성능은 이동통신에 적용된 모든 셀의 위치관리를 위한 비용을 계산하였으며, 이전 연구에서 제안된 유전 알고리즘 및 모의 담금질 기법과 비교 평가하였다. 성능평가에서 제안된 타부서치 알고리즘이 기존의 방식에 비해 성능이 우수함을 볼 수 있었으며, 결론적으로 제안된 타부서치 알고리즘이 이동통신에서 리포팅 셀구조를 계획함에 있어 최적화 기법으로 적용될 수 있음을 확인할 수 있었다.
[9]은 또 다른 메타 휴리스틱 알고리즘인 유전 알고리즘(genetic algorithm)과 개미 군체 알고리즘(ant colony algorithm)을 적용하여 위치관리비용을 최소화하는 알고리즘을 제안하였다. 제안된 논문에서 개비 군체 알고리즘이 유전 알고리즘에 비해 성능이 우수한 것으로 나타났다. Mehta.

참고문헌 (10)

A. Mukherjeej and D. De, "Location management in mobile network: a survey," Computer Science Review, vol. 19, pp. 1-14, Feb. 2016.

상세보기
S. Parija and P. K. Sahu, "A metaheuristic bat inspired technique for cellular network optimization," In Proceeding of 2nd International Conference Man and Machine Interfacing, vol. 1, no. 1, pp. 1-6, Dec. 2017.
A. Hac and X. Zhou, "Locating strategies for personal communication networks: A novel tracking strategy," IEEE Journal on Selected Areas in Communications, vol. 15, no. 8, pp. 1425-1436, Oct. 1997.

상세보기
S. R. Parija, P. K. Sahu, and S. S. Singh, "Cost reduction in location management using reporting cell planning and particle swarm optimization," Wireless Personal Communications, vol. 96, pp. 1613-1633, Apr. 2017

상세보기
S. Prateek, Swayamsiddha, S. S. Singh, S. Parija, and P. Sahu, "Impact of dwell time distribution on location management in cellular networks," Journal of Engineering Science and Technology, vol. 13, no. 5, pp. 1330-1344, 2018.
D. Plassmann, "Location management strategies for mobile cellular networks of 3rd generation," in Proceeding of IEEE 44th Vehicular Technology Conference, vol. 1, no. 1, pp. 649-653, Jun. 1994.
N. A. Bar and I. Kessler, "Tracking mobile users in wireless communications networks," IEEE Transaction Information Theory, vol. 39, no. 6, pp. 1877-1886, Nov. 1993.

상세보기
S. Parija, S. Singh, and S. Swayamsiddha, "Particle swarm optimization for cost reduction in mobile location management using reporting cell planning approach," in Recent Developments in Intelligent Nature Inspired Computing, IGI Golobal Pub, ch. 8, pp. 171-189, Mar. 2017.
R. Subrata and A. Y. Zomaya, "A comparison of three artificial life techniques for reporting cell planning in mobile computing," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 2, pp 142-153, Feb. 2003.

상세보기
F. Mehta and P. Swadas, "A simulated annealing Approach to reporting cell planning problem of mobile location management," International Journal of Recent Trends in Engineering, vol. 2, no. 2, pp. 99-102, Nov. 2009.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증