무선 메쉬 네트워크에서 라우터 노드 배치를 위한 타부 서치 알고리즘

장길웅,Jang, Kil-Woong 한국정보통신학회 2015 한국정보통신학회논문지 Vol.19 No.1

본 논문에서는 무선 메쉬 네트워크에서 라우터 노드와 클라이언트 노드간의 연결설정 최대화를 위해 라우터 노드를 효과적으로 배치하는 타부 서치 알고리즘을 제안한다. 네트워크에서 라우터 노드와 클라이언트 노드의 수가 증가함에 따라 두 종류의 노드 간 연결을 위한 계산량은 급격히 늘어나게 된다. 본 논문에서는 밀집도가 높은 네트워크에서 적정한 시간 내에 최적의 노드 연결을 위한 타부 서치 알고리즘을 제안하며, 효율적인 검색을 위해 타부 서치 알고리즘의 효과적인 이웃해 생성 동작을 제안한다. 제안된 알고리즘은 라우터 노드와 클라이언트 노드간의 최대 연결수와 실행시간 관점에서 성능을 평가하며, 평가 결과에서 제안된 알고리즘이 기존의 알고리즘에 비해 성능이 우수함을 보인다. This paper proposes a Tabu search algorithm to maximize the connectivity between the router nodes and the client nodes in wireless mesh networks. As the number of the router nodes and the client nodes in the networks increases, the amount of calculation for finding the solution would be too much increased. To obtain the optimal solution within a reasonable computation time for a high-density network, we propose a Tabu search algorithm to obtain the optimal solution for maximizing the connectivity. In order to make a search more efficient, we propose some efficient neighborhood generating operations of the Tabu search algorithm. We evaluate those performances through some experiments in terms of the maximum number of the connectivity and the execution time of the proposed algorithm. The comparison results show that the proposed algorithm outperforms other existing algorithms.

애드혹 네트워크에서 협력통신을 위한 유전 알고리즘

장길웅,Jang, Kil-Woong 한국정보통신학회 2014 한국정보통신학회논문지 Vol.18 No.1

본 논문에서는 애드혹 네트워크에서 협력통신을 위한 이동노드 간 연결을 최대화하는 유전 알고리즘을 제안한다. 일반적으로 네트워크에서 이동노드의 이동량이 증가하면 노드 연결을 위한 계산량은 급격히 늘어나게 된다. 본 논문에서는 밀집도가 높은 네트워크에서 적정한 시간 내에 최적의 노드 연결을 위한 유전 알고리즘을 제안하며, 효율적인 검색을 위해 유전 알고리즘의 효과적인 이웃해 생성 동작을 제안한다. 제안된 알고리즘은 최대 노드 연결 수와 실행시간 관점에서 성능을 평가하며, 평가 결과에서 제안된 알고리즘이 기존의 알고리즘들에 비해 성능이 우수함을 보인다. This paper proposes a genetic algorithm to maximize the connectivity among the mobile nodes for the cooperative communication in ad-hoc networks. In general, as the movement of the mobile nodes in the networks increases, the amount of calculation for finding the solution would be too much increased. To obtain the optimal solution within a reasonable computation time for a high-density network, we propose a genetic algorithm to obtain the optimal solution for maximizing the connectivity. In order to make a search more efficient, we propose some efficient neighborhood generating operations of the genetic algorithm. We evaluate those performances through some experiments in terms of the maximum number of connections and the execution time of the proposed algorithm. The comparison results show that the proposed algorithm outperforms other existing algorithms.

무선 메쉬 네트워크에서 네트워크 설계 문제를 위한 타부 서치 알고리즘

장길웅,Jang, Kil-woong 한국정보통신학회 2020 한국정보통신학회논문지 Vol.24 No.6

무선 메쉬 네트워크는 메쉬 클라이언트와 메쉬 라우터, 메쉬 액세스 포인트로 구성된다. 메쉬 라우터는 메쉬 클라이언트에게 무선 네트워크 서비스를 연결해주며, 메쉬 액세스 포인트는 유선 링크를 사용하여 백본 네트워크에 연결하고 메쉬 클라이언트에게 인터넷 액세스 서비스를 제공한다. 본 논문에서는 제한된 수의 메쉬 라우터와 메쉬 액세스 포인트를 사용하여 무선 메쉬 네트워크에 대한 네트워크 설계를 위한 최적화 알고리즘을 제안한다. 본 논문에서 제안된 최적화 알고리즘은 메타휴리스틱방식의 하나인 타부서치 알고리즘을 적용하였으며, 라우터와 메쉬 액세스 포인트의 배치에 따른 전송지연을 최소화하고 적절한 수행 시간 안에 결과가 도출되도록 설계되었다. 제안된 타부서치 알고리즘은 메쉬 라우터와 메쉬 액세스 포인트의 배치를 위한 전송지연과 알고리즘 수행시간 관점에서 비교 평가되었으며, 성능평가에서 기존의 제안된 메타휴리스틱 방식에 비해 우수한 성능을 보였다. Wireless mesh networks consist of mesh clients, mesh routers and mesh access points. The mesh router connects wireless network services to the mesh client, and the mesh access point connects to the backbone network using a wired link and provides Internet access to the mesh client. In this paper, a limited number of mesh routers and mesh access points are used to propose optimization algorithms for network design for wireless mesh networks. The optimization algorithm in this paper has been applied with a sub-subscription algorithm, which is one of the meta-heuristic methods, and is designed to minimize the transmission delay for the placement of mesh routers and mesh access points, and produce optimal results within a reasonable time. The proposed algorithm was evaluated in terms of transmission delay and time to perform the algorithm for the placement of mesh routers and mesh access points, and the performance evaluation results showed superior performance compared to the previous meta-heuristic methods.

타부 서치 알고리즘 기반의 무선 센서 네트워크에서 센서 노드 배치

장길웅,Jang, Kil-woong 한국정보통신학회 2015 한국정보통신학회논문지 Vol.19 No.5

본 논문에서는 무선 센서 네트워크에서 네트워크의 감시영역을 최대화하기 위해 센서 노드를 효과적으로 배치하는 타부 서치 알고리즘을 제안한다. 무선 센서 네트워크에서 센서 노드의 수가 증가하게 되면 네트워크의 감시영역을 최대화하기 위한 계산량은 급격히 늘어나게 된다. 본 논문에서는 센서 배치 밀도가 높은 네트워크에서 적정한 실행 시간 내에 네트워크의 감시영역을 최대화하는 타부 서치 알고리즘을 제안하며, 효율적인 검색을 위해 타부 서치 알고리즘의 새로운 이웃해 생성 동작을 제안한다. 제안된 알고리즘은 네트워크의 최대 감시영역과 실행속도 관점에서 성능을 평가하며, 평가 결과에서 제안된 알고리즘이 기존의 알고리즘에 비해 성능이 우수함을 보인다. In this paper, we propose a Tabu search algorithm to efficiently deploy the sensor nodes for maximizing the network sensing coverage in wireless sensor networks. As the number of the sensor nodes in wireless sensor networks increases, the amount of calculation for searching the solution would be too much increased. To obtain the best solution within a reasonable execution time in a high-density network, we propose a Tabu search algorithm to maximize the network sensing coverage. In order to search effectively, we propose some efficient neighborhood generating operations of the Tabu search algorithm. We evaluate those performances through some experiments in terms of the maximum network sensing coverage and the execution time of the proposed algorithm. The comparison results show that the proposed algorithm outperforms other existing algorithms.

무선 센서 네트워크에서 해양 수색 및 구조를 위한 에너지 최적화 알고리즘

장길웅,Jang, Kil-woong 한국정보통신학회 2018 한국정보통신학회논문지 Vol.22 No.4

In wireless sensor networks, we propose an optimization algorithm in order to minimize the consumed energy of nodes for maritime search and rescue. In the marine environment, search and rescue operations are mainly performed on the surveillance side and passively on the rescued side. A self-configurable wireless sensor network can build a system that can send rescue signals in the operations. A simulated annealing algorithm is proposed to minimize the consumed energy of nodes in the networks with many nodes. As the density of nodes becomes higher, the algorithmic computation will increase highly. To search the good result in a proper execution time, the proposed algorithm proposes a new neighborhood generating operation and improves the efficiency of the algorithm. The proposed algorithm was evaluated in terms of the consumed energy of the nodes and algorithm execution time, and the proposed algorithm performed better than other optimization algorithms in the performance results. 무선 센서 네트워크에서 해양 수색 및 구조를 목적으로 노드의 소모 에너지를 최소화하기 위한 최적화 알고리즘을 제안한다. 해양 환경에서 수색 및 구조작업은 감시하는 측에서 주로 이루어지며, 구조되는 측에서는 수동적으로 기다려야 한다. 이에 반해 자가 구성 이 가능한 무선 센서 네트워크는 해양 수색 및 구조작업에서 능동적으로 구조 신호를 보낼 수 있는 시스템을 구축할 수 있다. 본 논문에서는 많은 수의 노드가 배치된 네트워크에서 노드의 소모 에너지를 최소화하기 위하여 시뮬레이티드 어닐링 알고리즘을 제안한다. 네트워크에서 노드의 밀도가 높으면 일반적으로 알고리즘 계산양이 급격히 늘어난다. 따라서 제안된 알고리즘은 적정한 실행 시간 내에 최적의 결과를 찾기 위해 새로운 이웃해 생성 동작을 제안하고 알고리즘의 효율성을 높인다. 제안된 알고리즘은 노드의 소모 에너지와 알고리즘 실행시간 면에서 성능 평가를 하였으며, 성능 평가 결과에서 기존의 방식에 비해 성능이 우수하였다.

해양 센서 네트워크에서 네트워크 클러스터링을 위한 유전 알고리즘

장길웅,Jang, Kil-Woong 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.12

해양 센서 네트워크에서 클러스터링 문제는 네트워크 수명 및 확장성을 향상시키기 위한 문제 중 하나이다. 본 논문은 모든 노드가 클러스터 헤더를 통하여 싱크 노드로 데이터를 전송하는데 사용되는 전송 에너지를 최소화할 수 있는 클러스터링 문제의 최적 결과를 찾는 알고리즘을 제안한다. 일반적으로 네트워크에서 노드의 수가 증가하면 적절한 클러스터 구성을 위한 계산량은 급격히 늘어나게 된다. 본 논문에서는 적정한 시간 내에 최적의 클러스터 구성을 위한 유전 알고리즘을 제안하며, 효율적인 검색을 위해 유전 알고리즘의 효과적인 이웃해 생성 동작을 제안한다. 제안된 알고리즘은 전송 에너지와 실행시간 관점에서 성능을 평가하며, 평가 결과에서 제안된 알고리즘이 해양 센서 네트워크에서 클러스터를 효과적으로 구성함을 보인다. A Clustering problem is one of the organizational problems to improve network lifetime and scalability in underwater acoustic sensor networks. This paper propose an algorithm to obtain an optimal clustering solution to be able to minimize a total transmission power for all deployed nodes to transmit data to the sink node through its clusterhead. In general, as the number of nodes increases, the amount of calculation for finding the solution would be too much increased. To obtain the optimal solution within a reasonable computation time, we propose a genetic algorithm to obtain the optimal solution of the cluster configuration. In order to make a search more efficient, we propose some efficient neighborhood generating operations of the genetic algorithm. We evaluate those performances through some experiments in terms of the total transmission power of nodes and the execution time of the proposed algorithm. The evaluation results show that the proposed algorithm is efficient for the cluster configuration in underwater acoustic sensor networks.

무선 센서 네트워크에서 최대 수명 데이터 수집 문제를 위한 시뮬레이티드 어닐링 알고리즘

장길웅,Jang, Kil-Woong 한국정보통신학회 2013 한국정보통신학회논문지 Vol.17 No.7

The maximum lifetime data aggregation problem is to maximize the network lifetime as minimizing the transmission energy of all deployed nodes in wireless sensor networks. In this paper, we propose a simulated annealing algorithm to solve efficiently the maximum lifetime data aggregation problem on the basis of meta-heuristic approach in wireless sensor networks. In order to make a search more efficient, we propose a novel neighborhood generating method and a repair function of the proposed algorithm. We compare the performance of the proposed algorithm with other existing algorithms through some experiments in terms of the network lifetime and algorithm computation time. Experimental results show that the proposed algorithm is efficient for the maximum lifetime data aggregation problem in wireless sensor networks. 무선 센서 네트워크에서 최대 수명 데이터 수집 문제는 네트워크에 배치된 모든 노드의 데이터 전송 에너지를 최소화함으로써 네트워크의 수명을 최대화하는 문제이다. 본 논문은 무선 센서 네트워크에서 최대 수명 데이터 수집문제를 효과적으로 해결하기 위한 메타휴리스틱 기법 중 하나인 시뮬레이티드 어닐링 알고리즘을 제안한다. 제안된 알고리즘에서는 보다 효과적인 해를 찾기 위해 새로운 이웃해 생성방식과 복구함수를 적용한다. 제안된 알고리즘의 성능은 네트워크 수명과 알고리즘 실행시간 관점에서 기존의 알고리즘과 비교평가 하였으며, 실험 결과에서 제안된 알고리즘이 최대 수명 데이터 수집 문제에 효과적으로 적용됨을 보여준다.

무선 센서 네트워크에서 노드 재프로그래밍을 위한 타부 서치 알고리즘

장길웅,Jang, Kil-woong 한국정보통신학회 2019 한국정보통신학회논문지 Vol.23 No.5

무선 센서 네트워크에서 배치된 노드의 기능을 변경하거나 갱신하기 위해 노드의 소프트웨어 코드를 업데이트하는 재프로그래밍 동작은 필수적이다. 본 논문은 무선 센서 네트워크에서 노드의 재프로그래밍을 목적으로 노드의 전송에너지를 최소화하는 최적화 알고리즘을 제안한다. 또한 네트워크의 수명을 오래 유지하기 위해 전체 노드의 에너지 소모를 균형있게 유지하도록 알고리즘을 설계한다. 본 논문에서는 많은 수의 노드가 배치된 무선 센서 네트워크에서 전송에너지의 최소화와 에너지 소모의 균형화를 위해 새로운 이웃해 생성방식을 가진 타부서치 알고리즘을 제안한다. 제안된 알고리즘은 적정한 수행 시간 내에 최적의 결과를 도출하도록 설계되었다. 제안된 타부서치 알고리즘의 성능은 노드의 전송에너지와 남은 에너지, 알고리즘 수행시간 측면에서 평가되었으며, 성능 평가 결과에서 이전의 방식에 비해 우수한 성능을 보였다. A reprogramming operation is necessary to update the software code of the node to change or update the functionality of the deployed node in wireless sensor networks. This paper proposes an optimization algorithm that minimizes the transmission energy of a node for the purpose of reprogramming a node in wireless sensor networks. We also design an algorithm that keeps energy consumption of all nodes balanced in order to maintain the lifetime of the network. In this paper, we propose a Tabu search algorithm with a new neighborhood generation method for minimizing transmission energy and energy consumption in wireless sensor networks with many nodes. The proposed algorithm is designed to obtain optimal results within a reasonable execution time. The performance of the proposed Tabu search algorithm was evaluated in terms of the node's transmission energy, remaining energy, and algorithm execution time. The performance evaluation results showed better performance than the previous methods.

수중 센서 네트워크에서 최소 비용 위치 결정 문제를 위한 타부 서치 알고리즘

장길웅,Jang, Kil-woong 한국정보통신학회 2017 한국정보통신학회논문지 Vol.21 No.5

일반적으로 수중 센서 네트워크에서 모든 센서 노드는 위치가 결정된 앵커 노드를 이용하여 자신의 위치를 결정한다. 본 논문에서는 수중 센서 네트워크에서 모든 센서 노드의 위치를 결정하기 위해 최소의 수를 가진 앵커 노드를 결정하기 위한 타부 서치 알고리즘을 제안한다. 네트워크에서 센서 노드의 수가 증가함에 따라 앵커 노드의 수를 결정하는 계산량은 급격히 늘어나게 된다. 본 논문에서는 밀집도가 높은 네트워크에서 적정한 시간 내에 최소의 앵커 노드수를 결정하는 타부 서치 알고리즘을 제안하며, 효율적인 검색을 위해 타부 서치 알고리즘의 효과적인 이웃해 생성 동작을 제안한다. 제안된 알고리즘은 최소 앵커 노드의 수와 실행시간 관점에서 성능을 평가하며, 평가 결과에서 제안된 알고리즘이 기존의 알고리즘에 비해 성능이 5-10% 우수함을 보인다. All sensor nodes generally determine their positions using anchor nodes that are located in underwater sensor networks. This paper proposes a Tabu search algorithm to determine the minimum number of anchor nodes for the location of all sensor nodes in underwater sensor networks. As the number of the sensor nodes increases in the network, the amount of calculation that determines the number of anchor nodes would be too much increased. In this paper, we propose a Tabu search algorithm that determines the minimum number of anchor nodes within a reasonable computation time in a high dense network, and propose an efficient neighborhood generating operation of the Tabu search algorithm for efficient search. The proposed algorithm evaluates those performances through some experiments in terms of the minimum number of anchor nodes and execution time. The proposed algorithm shows 5-10% better performance than the conventional algorithm.

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

장길웅,Jang, Kil-woong 한국정보통신학회 2020 한국정보통신학회논문지 Vol.24 No.9

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