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

장길웅

doi:10.6109/jkiice.2017.21.5.929

수중 센서 네트워크에서 최소 비용 위치 결정 문제를 위한 타부 서치 알고리즘
A Tabu Search Algorithm for Minimum Cost Localization Problem in Underwater Sensor Networks 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.21 no.5, 2017년, pp.929 - 935

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

초록
AI-Helper

일반적으로 수중 센서 네트워크에서 모든 센서 노드는 위치가 결정된 앵커 노드를 이용하여 자신의 위치를 결정한다. 본 논문에서는 수중 센서 네트워크에서 모든 센서 노드의 위치를 결정하기 위해 최소의 수를 가진 앵커 노드를 결정하기 위한 타부 서치 알고리즘을 제안한다. 네트워크에서 센서 노드의 수가 증가함에 따라 앵커 노드의 수를 결정하는 계산량은 급격히 늘어나게 된다. 본 논문에서는 밀집도가 높은 네트워크에서 적정한 시간 내에 최소의 앵커 노드수를 결정하는 타부 서치 알고리즘을 제안하며, 효율적인 검색을 위해 타부 서치 알고리즘의 효과적인 이웃해 생성 동작을 제안한다. 제안된 알고리즘은 최소 앵커 노드의 수와 실행시간 관점에서 성능을 평가하며, 평가 결과에서 제안된 알고리즘이 기존의 알고리즘에 비해 성능이 5-10% 우수함을 보인다.

Abstract ▼ AI-Helper

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.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 수중 센서 네트워크에서 모든 센서 노드의 위치를 결정하기 위해 최소의 수를 가진 앵커 노드를 결정하기 위한 네트워크 모델과 제약조건을 우선 기술한다. 네트워크 모델은 비방향성 그래프인 G = (V, E)로 나타낼 수 있으며, V는 모든 센서 노드의 집합을 의미하며, E는 모든 노드간의 연결을 나타내는 링크의 집합을 의미한다.
본 논문에서는 수중 센서 네트워크에서 최소 비용 위치 결정 문제에 대하여 메타 휴리스틱 알고리즘인 타부 서치 알고리즘을 제안한다. 효율적으로 좋은 결과를 얻기 위해 제안된 알고리즘에서는 새로운 이웃해 생성 방식을 제안하며, 제안된 알고리즘을 평가하기 위해 다양한 조건하에서 최소 앵커 노드 수와 알고리즘 실행시간 관점에서 기존의 다른 알고리즘과 비교 평가한다.
본 논문에서는 수중 센서 네트워크에서의 최소 비용 위치 결정 문제에 대한 제안된 타부 서치 알고리즘의 성능을 컴퓨터 시뮬레이션을 이용하여 평가하였다. 모든 실험은 Windows OS 기반의 4GB 메모리와 2.
본 논문은 수중 센서 네트워크에서 모든 노드의 위치를 결정하기 위해 필요한 앵커 노드의 수를 최소화하는 최소 비용 위치 결정 문제의 타부 서치 알고리즘을 제안하였다. 효과적인 알고리즘을 설계하기 위해 최소 비용 위치 결정 문제에 적합한 인코딩과 초기해 생성, 인접해 검색을 위한 두 가지의 이웃해 생성방식을 제안하였다.
본 논문의 목적함수는 수중 센서 네트워크에서 앵커 노드의 수를 최소화하는 것이다. 따라서 제안된 네트워크 모델에서 앵커 노드의 수를 최소화하기 위한 문제는 다음과 같은 목적함수를 최소화하는 조합 최적화 문제로 정식화할 수 있다.

제안 방법

비교결과에서 제안된 알고리즘이 기존의 방식보다 더 우수함을 볼 수 있었으며, 또한 수중 센서 네트워크에서 최소 비용 위치 결정 문제를 효과적으로 해결할 수 있음을 볼 수 있었다. 또한 제안된 알고리즘은 중앙 집중식 방식으로 동작이 되므로 이를 제어하기 위해 수중 센서 네트워크를 관리하는 기지국에서 제안된 알고리즘을 이용하여 위치를 결정할 수 있다.
제안된 알고리즘에서는 앵커 노드들의 좌표에 대한 집합을 해의 인코딩으로 사용한다. 본 논문에서는 해의 인코딩을 위해 모든 노드의 위치는 랜덤하게 미리 결정 하고, 인접해 생성방식에 따라 앵커 노드는 변경된다. 그림 1은 앵커 노드의 좌표로 구성된 해의 인코딩을 나타낸 것이다.
초기해에 대하여 제안된 이동 방법에 의하여 인접해를 생성한다. 생성된 인접해 중에 타부리스트에 저장되어있지 않은 해 중에 가장 우수한 해를 선택하여 타부리스트에 저장하고 임시 최적해와 비교한다. 비교된 결과에서 새로운 해가 임시 최적해보다 더 좋은 해일 경우 이 해를 임시 최적해로 바꾸고 임시 최적해를 이용하여 다음 단계의 인접해 생성을 위해 사용한다.
제안된 알고리즘의 성능을 비교평가하기 위해 앵커 노드의 수와 알고리즘 실행시간 관점에서 기존에 제안된 탐욕 알고리즘(greedy algorithm)[2]과 유전 알고리즘(genetic algorithm)[4]을 제안된 타부 서치 알고리즘과 비교하였다. 성능평가를 위해 노드의 전송범위(m)는 20, 25, 30 으로 정하고, 다양한 노드 밀도를 가진 네트워크 구성을 위해 노드의 개수는 100에서 1000까지로 구성하였다. 네트워크의 크기는 100 × 100m²로 설정하여 노드를 랜덤하게 배치하였다.
[2]은 3개 이상의 앵커 노드를 사용하여 위치가 결정되지 않은 노드의 위치를 결정하는 방식의 탐욕 알고리즘(greedy algorithm)을 제안하였다. 이 알고리즘에서는 위치가 결정되지 않은 노드의 인접한 앵커 노드의 수가 3개보다 작을 경우에는 그 노드는 앵커 노드로 설정하고 다음 단계부터는 인접 노드의 정보를 기반으로 앵커를 설정하고 모든 노드의 위치를 결정 하는 과정을 수행한다. Zhang et al.
[7]은 위치 결정 문제에 대한 이론적인 개념을 제시하였다. 이 연구에서는 미리 위치 정보를 가지는 앵커 노드를 일부 배치시키고, 위치가 결정되지 않은 나머지 노드는 인접한 노드로부터 거리를 측정함으로써 위치를 결정하게 된다. 이때 앵커 노드는 정지된 상태를 유지하고, 위치 결정 과정은 이동 노드에 의해 수행된다.
인코딩 설계에 따라 알고리즘의 성능은 달라지기 때문에 최적의 해를 찾기 위해 적절한 해에 대한 인코딩을 설계한다. 해에 대한 인코딩이 설계되면 제약식을 만족하는 하나의 초기해를 랜덤하게 생성한다.
특히 동적 크기의 타부리스트는 NP-hard 문제에 대하여 더 좋은 결과의 해를 검색하는데 중요한 역할을 한다[12]. 제안된 알고리즘에서는 N 개의 센서 노드에 대하여 타부리스트의 크기를 매 20번 주기마다 N/10과 N/5사이의 값으로 변화시킨다. 이 값은 실험적으로 가장 적절한 값으로 선택되었다.
제안된 알고리즘에서는 앵커 노드들의 좌표에 대한 집합을 해의 인코딩으로 사용한다. 본 논문에서는 해의 인코딩을 위해 모든 노드의 위치는 랜덤하게 미리 결정 하고, 인접해 생성방식에 따라 앵커 노드는 변경된다.
제안된 타부 서치 알고리즘의 이동방법은 현재해의 모든 요소에 대하여 순차적으로 적용된다. 제안된 타부 서치 알고리즘에서는 두 가지의 이동방식을 사용한다. 첫 번째 방식은 현재 앵커 노드를 인접한 센서 노드로 앵커를 바꾸는 교환 이동이고, 다른 한 가지 방식은 현재 앵커 노드를 삭제하는 삭제 이동이다.
제안된 해 인코딩 방식을 이용하여 타부 서치 알고리즘에 적용할 초기해를 생성한다. 초기해 생성은 다음과 같이 이루어진다.
초기해는 타부리스트라고 불리는 메모리 리스트에 저장되고 임시 최적값으로 일단 저장된다. 초기해에 대하여 제안된 이동 방법에 의하여 인접해를 생성한다. 생성된 인접해 중에 타부리스트에 저장되어있지 않은 해 중에 가장 우수한 해를 선택하여 타부리스트에 저장하고 임시 최적해와 비교한다.
본 논문은 수중 센서 네트워크에서 모든 노드의 위치를 결정하기 위해 필요한 앵커 노드의 수를 최소화하는 최소 비용 위치 결정 문제의 타부 서치 알고리즘을 제안하였다. 효과적인 알고리즘을 설계하기 위해 최소 비용 위치 결정 문제에 적합한 인코딩과 초기해 생성, 인접해 검색을 위한 두 가지의 이웃해 생성방식을 제안하였다. 제안된 알고리즘을 평가하기 위해 앵커 노드의 수와 알고리즘 실행시간 관점에서 기존의 방식과 비교 평가하였다.
본 논문에서는 수중 센서 네트워크에서 최소 비용 위치 결정 문제에 대하여 메타 휴리스틱 알고리즘인 타부 서치 알고리즘을 제안한다. 효율적으로 좋은 결과를 얻기 위해 제안된 알고리즘에서는 새로운 이웃해 생성 방식을 제안하며, 제안된 알고리즘을 평가하기 위해 다양한 조건하에서 최소 앵커 노드 수와 알고리즘 실행시간 관점에서 기존의 다른 알고리즘과 비교 평가한다.

대상 데이터

최소 비용 위치 결정 문제에서 앵커 노드를 결정함에 있어 앵커 노드들 중에 이 노드에 인접한 앵커 노드이거나 위치가 미리 결정된 노드가 3개 이상이면 앵커 노드에서 제외하고 위치가 결정된 노드로 변경한다[11]. 따라서 본 논문에서 사용되는 노드는 앵커 노드, 위치가 결정된 비앵커 노드, 위치가 결정되지 않은 비앵커 노드로 구분된다.

데이터처리

효과적인 알고리즘을 설계하기 위해 최소 비용 위치 결정 문제에 적합한 인코딩과 초기해 생성, 인접해 검색을 위한 두 가지의 이웃해 생성방식을 제안하였다. 제안된 알고리즘을 평가하기 위해 앵커 노드의 수와 알고리즘 실행시간 관점에서 기존의 방식과 비교 평가하였다.
67GHz Intel processor로 구성된 PC상에서 수행되었으며, 각 알고리즘은 C++ 언어를 이용하여 구현되었다. 제안된 알고리즘의 성능을 비교평가하기 위해 앵커 노드의 수와 알고리즘 실행시간 관점에서 기존에 제안된 탐욕 알고리즘(greedy algorithm)[2]과 유전 알고리즘(genetic algorithm)[4]을 제안된 타부 서치 알고리즘과 비교하였다. 성능평가를 위해 노드의 전송범위(m)는 20, 25, 30 으로 정하고, 다양한 노드 밀도를 가진 네트워크 구성을 위해 노드의 개수는 100에서 1000까지로 구성하였다.

성능/효과

유전 알고리즘은 노드의 수가 증가함에 따라 같은 비율로 교배와 돌연변이 동작을 수행하지만 제안된 타부 서치는 교환 이동과 삭제 이동에 의한 이웃해 생성방식으로 해에 빠르게 접근함으로써 실행시간을 줄이고 있다. 결론적으로 성능평가 결과에서 제안된 알고리즘이 NP-hard 문제인 최소 비용 위치 결정 문제를 적정한 실행시간 내에 좋은 결과를 얻을 수 있으며 최소 비용 위치 결정 문제를 효과적으로 해결할 수 있음을 알 수 있었다.
그림 5는 노드의 전송 반경이 20, 25, 30일 때 노드의 수가 변함에 따라 최소의 앵커 노드의 수를 비교한 것이다. 그림에서 제안된 알고리즘이 기존의 유전 알고리즘과 탐욕 알고리즘에 비해 성능이 5-10% 우수함을 볼 수 있다. 같은 유형의 메타 휴리스틱 알고리즘인 유전 알고리즘도 탐욕 알고리즘에 비해 성능이 우수함을 볼 수 있다.
비교결과에서 제안된 알고리즘이 기존의 방식보다 더 우수함을 볼 수 있었으며, 또한 수중 센서 네트워크에서 최소 비용 위치 결정 문제를 효과적으로 해결할 수 있음을 볼 수 있었다. 또한 제안된 알고리즘은 중앙 집중식 방식으로 동작이 되므로 이를 제어하기 위해 수중 센서 네트워크를 관리하는 기지국에서 제안된 알고리즘을 이용하여 위치를 결정할 수 있다.
특히 노드의 수가 커짐에 따라 이웃해 생성을 하지 않는 탐욕 알고리즘이 가장 빠르고 제안된 타부 서치 알고리즘이 유전 알고리즘보다 실행속도가 빠름을 알 수 있다. 유전 알고리즘은 노드의 수가 증가함에 따라 같은 비율로 교배와 돌연변이 동작을 수행하지만 제안된 타부 서치는 교환 이동과 삭제 이동에 의한 이웃해 생성방식으로 해에 빠르게 접근함으로써 실행시간을 줄이고 있다. 결론적으로 성능평가 결과에서 제안된 알고리즘이 NP-hard 문제인 최소 비용 위치 결정 문제를 적정한 실행시간 내에 좋은 결과를 얻을 수 있으며 최소 비용 위치 결정 문제를 효과적으로 해결할 수 있음을 알 수 있었다.
또한 같은 메타 휴리스틱 방식인 유전 알고리즘보다 제안된 타부 서치 알고리즘이 성능이 우수한 이유는 기존의 검색 방식은 지역 최적해에 빨리 수렴한 반면에 제안된 알고리즘은 보다 향상된 결과를 가진 해에서 수렴하기 때문이다. 즉, 제안된 타부 서치 알고리즘의 이웃해 생성방식인 교환 이동과 삭제 이동이 효과적으로 동작하고 있음을 나타낸다.
메타 휴리스틱 방식인 타부 서치와 유전 알고리즘은 실행시간이 탐욕 알고리즘에 비해 많이 소모됨을 알 수 있다. 특히 노드의 수가 커짐에 따라 이웃해 생성을 하지 않는 탐욕 알고리즘이 가장 빠르고 제안된 타부 서치 알고리즘이 유전 알고리즘보다 실행속도가 빠름을 알 수 있다. 유전 알고리즘은 노드의 수가 증가함에 따라 같은 비율로 교배와 돌연변이 동작을 수행하지만 제안된 타부 서치는 교환 이동과 삭제 이동에 의한 이웃해 생성방식으로 해에 빠르게 접근함으로써 실행시간을 줄이고 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	네트워크에서 계산량은 무엇에 따라 늘어나는가?	본 논문에서는 수중 센서 네트워크에서 모든 센서 노드의 위치를 결정하기 위해 최소의 수를 가진 앵커 노드를 결정하기 위한 타부 서치 알고리즘을 제안한다. 네트워크에서 센서 노드의 수가 증가함에 따라 앵커 노드의 수를 결정하는 계산량은 급격히 늘어나게 된다. 본 논문에서는 밀집도가 높은 네트워크에서 적정한 시간 내에 최소의 앵커 노드수를 결정하는 타부 서치 알고리즘을 제안하며, 효율적인 검색을 위해 타부 서치 알고리즘의 효과적인 이웃해 생성 동작을 제안한다.
	위치 정보는 어디에 사용될 수 있는가?	위치 정보는 이벤트 탐지, 목표 추적, 환경 감시, 노드 배치와 같은 다양한 무선 센서 네트워크의 응용에 사용될 수 있다[1]. 한편, 위치 정보는 센서 네트워크의 성능을 향상시킬 수 있는 네트워크 프로토콜에 영향을 줄 수 있으며, 위치 기반 라우팅을 이용한 데이터 전송이나 지리적 방법을 이용한 네트워크 토폴로지 제어, 위치 정보를 이용한 라우팅에서의 트래픽 배분 등에 사용된다.
	무선 센서 네트워크에서 위치 결정 문제가 중요한 이유는?	한편, 위치 정보는 센서 네트워크의 성능을 향상시킬 수 있는 네트워크 프로토콜에 영향을 줄 수 있으며, 위치 기반 라우팅을 이용한 데이터 전송이나 지리적 방법을 이용한 네트워크 토폴로지 제어, 위치 정보를 이용한 라우팅에서의 트래픽 배분 등에 사용된다. 그러나 각 노드의 위치를 수동적으로 조정하거나 GPS를 가진 노드를 배치하는 것은 비용이 많이 드는 단점이 있으며, 대부분의 센서 네트워크에서는 사용 불가능한 경우가 발생한다. 따라서 무선 센서 네트워크의 설계에서 위치 결정 문제는 기본적이며 중요한 문제이다[2].

참고문헌 (12)

I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer Networks. vol. 38, no. 4, pp. 393-422, 2002.

상세보기
M. Huang, I. Chen, and Y. Wang, "Minimum cost localization problem in wireless sensor networks," Ad Hoc Networks, vol. 9, no. 3, pp. 387-399, May 2011.

상세보기
M. Erol-Kantarci, H. Mouftah, and S. Oktug, "A survey of architectures and localization techniques for underwater acoustic sensor networks," IEEE Communications Surveys Tutorials, vol. 13, no. 3, pp. 487-502, 2011.

상세보기
A. F. Assis, L. M. Veeira, M. R. Rodrigues, and G. L. Pappa, "A genetic algorithm for the minimum cost localization problem in wireless sensor networks," in Proceeding of IEEE Congress on Evolutionary Computation, pp. 797-804, 2013.
D. K. Goldenberg, P. Bihler, M. Cao, J. Fang, B. D. O. Anderson, A. Stephen Morse, and Y. Richard Yang, "Localization in sparse networks using sweeps," in Proceeding of ACM MobiCom, 2006.
Z. Yang, Y. Liu, and X. Y. Li, "Beyond trilateration: On the localizability of wireless ad-hoc networks," in Proceeding of IEEE INFOCOM, 2009.
J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R. Yang, B. D. O. Anderson, and P. N. Belhumeur, "A theory of network localization," IEEE Transaction Mobile Computer, vol. 5, no. 12, pp. 1663- 1678, 2006.

상세보기
F. Glover, "Future paths for integer programming and links to artificial intelligence," Computers and Op. Res., vol. 5, pp. 533-549, 1986.
C. H. Wu, W. Sheng, and Y. Zhang, "Mobile sensor etworks self localization based on multi-dimensional scaling," in Proceeding of IEEE International Conference on Robotics and Automation, pp. 4038-4043, April 2007.
M. Azim, Z. Aung, W. Xiao, and V. Khadkikar, "Localization in wireless sensor networks by cross entropy method," in Preceeding of International Conference on Ad Hoc Networks, pp. 103-118, 2012.
A. Savvides, H. Park, and M. B. Srivastava, "The bits and flops of the n-hop multilateration primitive for node localization problems," in Proceeding of ACM International Workshop on Wireless Sensor Networks & Applications, 2002.
S. Kultuel-Konak, A. E. Norman, and D. W. Coit, "Efficiently solving the redundancy allocation problem using Tabu search," IIE Transactions, vol. 35, pp. 515-526, 2003.

상세보기

저자의 다른 논문 :

표제어: 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

연합인증