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

장길웅

doi:10.6109/jkiice.2015.19.5.1084

문제 정의

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

제안 방법

동적으로 타부 리스트의 크기를 변화시키는 방법은 NP-hard 문제에 대하여 효과적으로 좋은 결과를 검색하는데 중요한 역할을 한다. 본 논문에서 제안된 알고리즘은 N개의 센서 노드에 대하여 타부 리스트의 크기를 20번 주기마다 N과 3N 사이의 랜덤 값으로 변화시킨다. 타부 리스트가 포화 상태가 되면 가장 오래된 해를 삭제하고 새로운 해를 추가하는 방식으로 타부리스트 를 관리한다.
초기해 생성은 모든 센서 노드에 대하여 정해진 네트워크 크기 내에서 랜덤하게 노드의 위치를 결정하는 과정이다. 본 논문에서는 제안된 인코딩 방식에 적합한 초기해를 생성하여 제안된 타부 서치 알고리즘에 적용한다. 생성된 초기해에 대하여 목적함수인 네트워크 감시영역을 계산하고, 그해에 대한 정보를 타부 리스트에 저장하고 임시 최적해로 등록한다.
제안된 알고리즘에서는 센서 노드들의 좌표에 대한 집합을 해의 인코딩으로 사용한다. 본 논문에서는 해의 인코딩을 위해 센서 노드의 위치는 랜덤하게 미리 결정하고, 이웃해 생성방식에 따라 센서 노드의 위치는 변경된다. 그림 1은 센서 노드의 좌표를 구성된 해의 인코딩을 나타낸다.
초기해에 대하여 제안된 이웃 해 생성 방법에 따라 다수의 이웃해를 생성한다. 생성된 이웃해 중에 타부 리스트에 저장되어있지 않으면서 가장 우수한 해를 선택하여 타부 리스트에 저장하고 임시 최적해와 비교한다. 비교된 결과에서 새로 선택된 해가 임시 최적해보다 더 좋을 경우 이 해를 임시 최적 해로 바꾼다.
본 논문에서는 제안된 인코딩 방식에 적합한 초기해를 생성하여 제안된 타부 서치 알고리즘에 적용한다. 생성된 초기해에 대하여 목적함수인 네트워크 감시영역을 계산하고, 그해에 대한 정보를 타부 리스트에 저장하고 임시 최적해로 등록한다.
그림 5는 그림 4에서와 같은 조건에서 알고리즘의 평균 실행 시간을 비교한 것이다. 작은 크기의 네트워크에 서는 제안된 타부 서치 알고리즘과 랜덤 방법이 실행 시간이 빨랐다 제안된 알고리즘은 PSO 알고리즘과 마찬가지로 이웃해를 생성하지만 빠른 최적해 탐색으로 실 행시 간이 단축되었다. 그러나 네트워크의 크기가 커짐에 따라 이웃해 생성을 하지 않는 랜덤 방식이 가장 빠르고 제안된 타부 서치 알고리즘이 PSO 알고리즘보다 조금 더 느림을 알 수 있다.
제안된 알고리즘에서는 센서 노드들의 좌표에 대한 집합을 해의 인코딩으로 사용한다. 본 논문에서는 해의 인코딩을 위해 센서 노드의 위치는 랜덤하게 미리 결정하고, 이웃해 생성방식에 따라 센서 노드의 위치는 변경된다.
메타휴리스틱 알고리즘에서 최적의 해를 찾기 위해 현재 해에서 새로운 해를 생성하는 이웃해 생성 방법은 가장 중요한 단계이다. 제안된 타부 서치 알고리즘에서도 이웃해 생성을 위해 2가지 이웃해 생성 방법을 제안한다. 첫 번째 방법은 현재 센서 노드의 좌표에서 인접한 좌표로 이동하는 인접 이동 방법이고, 다른 한 가지 방법은 센서 노드의 (x, y) 좌표를 서로 바꾸는 교환이 동방 법이다.
본 논문은 무선센서 네트워크에서 일정한 수의 센서를 효과적으로 배치하여 네트워크 감시 영역을 최대화하는 타 부 서치 알고리즘을 제안하였다. 효과적인 알고리즘을 설계하기 위해 센서 노드 배치 문제에 적합한 인코딩과 초기 해 생성, 이웃해 검색을 위한 두 가지의 이웃해 생성방식을 제안하였다. 제안된 알고리즘을 평가하기 위해 네트워크 감시 영역과 알고리즘 실행 시간 관점에서 기존의 방식과 비교평가하였다.
본 논문에서는 센서 노드의 감시영역을 최대화하기 위한 센서 노드 배치 문제에 대하여 메타 휴리스틱 알고리즘인 타부 서치 알고리즘을 제안한다. 효율적으로 좋은 결과를 얻기 위해 제안된 알고리즘에서는 새로운 이웃해 생성 방식을 제안하며, 제안된 알고리즘을 평가하기 위해 다양한 조건하에서 감시영역과 알고리즘 실행 시간 관점에서 기존의 다른 알고리즘과 비교 평가한다.

대상 데이터

성능평가를 위해 노드의 전송범위(R)는 20, 센서 노드의 개수(N)는 네트워크의 크기에 따라 다르게 구성하였다. 네트워크의 크기는 M 乂 M m2로 설정하였으며, M 100, 200, 300으로 하였다. 각 알고리즘은 10번씩 시도하여 평균값으로 결과로 나타내었다.

데이터처리

효과적인 알고리즘을 설계하기 위해 센서 노드 배치 문제에 적합한 인코딩과 초기 해 생성, 이웃해 검색을 위한 두 가지의 이웃해 생성방식을 제안하였다. 제안된 알고리즘을 평가하기 위해 네트워크 감시 영역과 알고리즘 실행 시간 관점에서 기존의 방식과 비교평가하였다. 비교 결과에서 제안된 알고리즘이 비슷한 실행시간에서 기존의 방식보다 감시영역 관점에서 더 우수함을 볼 수 있었으며, 또한 무선센서 네트워크에서 센서 노드 배치 문제를 효과적으로 해결할 수 있음을 볼 수 있었다.
67GHz Intel processor로 구성된 PC 상 에서 수행되었으며, 각 알고리즘은 C++ 언어를 이용하여 구현되었다. 제안된 알고리즘의 성능을 비교 평가하기 위해 네트워크 감시영역과 알고리즘 실행 시간 관점에서 랜덤(Random) 방식과 기존에 제안된 PSO 알고리 즘[9]을 제안된 타부 서치 알고리즘과 비교하였다.

성능/효과

하지만 제안된 타부 서치 알고리즘이 기존의 방식에 비해 비슷한 실행 시간 내에서 더 넓은 감시영역을 찾고 있음을 알 수 있다. 결론적으로 성능평가 결과에서 제안된 알고리즘이 NP-hard 문제인 센서 노드 배치 문제를 적정한 실행 시간 내에 더 넓은 감시영역을 찾고 있으며 센서 노드 배치 문제를 효과적으로 해결할 수 있음을 알 수 있었다.
작은 크기의 네트워크에 서는 제안된 타부 서치 알고리즘과 랜덤 방법이 실행 시간이 빨랐다 제안된 알고리즘은 PSO 알고리즘과 마찬가지로 이웃해를 생성하지만 빠른 최적해 탐색으로 실 행시 간이 단축되었다. 그러나 네트워크의 크기가 커짐에 따라 이웃해 생성을 하지 않는 랜덤 방식이 가장 빠르고 제안된 타부 서치 알고리즘이 PSO 알고리즘보다 조금 더 느림을 알 수 있다. 이것은 네트워크 노드의 밀도가 커짐에 따라 제안된 타부 서치 알고리즘이 PSO 알고리즘보다 더 많은 이웃해 생성을 하기 때문이다.
앞선 결과와 마찬가지로 제안된 타부 서치 알고리즘이 기존의 알고리즘에 비해 성능이 우수함을 알 수 있다. 네트워크 크기가 증가하더라도 제안된 타부 서치 알고리즘이 기존의 다른 방식에 비해 성능이 우수함을 볼 수 있었다. 이는 제안된 타부 서치 알고리즘이 기존의 검색 방식보다 성능이 우수함을 나타내며 기존의 검색 방식은 로컬 최적해에 수렴한 반면에 제안된 알고리즘은 보다 향상된 결과를 가진 해에서 수렴하기 때문이다.
즉, 제안된 타 부 서치 알고리즘의 이웃해 생성방식인 인접 이동방식과 교환 이동방식이 효과적으로 동작하고 있음을 나타낸다. 또한 결과에서 어떠한 검색을 수행하지 않는 랜덤 방법보다 메타휴리스틱 방법을 사용하는 방법이 더 우수함을 볼 수 있다.
제안된 알고리즘을 평가하기 위해 네트워크 감시 영역과 알고리즘 실행 시간 관점에서 기존의 방식과 비교평가하였다. 비교 결과에서 제안된 알고리즘이 비슷한 실행시간에서 기존의 방식보다 감시영역 관점에서 더 우수함을 볼 수 있었으며, 또한 무선센서 네트워크에서 센서 노드 배치 문제를 효과적으로 해결할 수 있음을 볼 수 있었다.
그림 4(c)는 M = 300이고, N이 50에서 90일 때 센서 노드의 감시영역을 나타낸 것이다. 앞선 결과와 마찬가지로 제안된 타부 서치 알고리즘이 기존의 알고리즘에 비해 성능이 우수함을 알 수 있다. 네트워크 크기가 증가하더라도 제안된 타부 서치 알고리즘이 기존의 다른 방식에 비해 성능이 우수함을 볼 수 있었다.
이는 제안된 타부 서치 알고리즘이 기존의 검색 방식보다 성능이 우수함을 나타내며 기존의 검색 방식은 로컬 최적해에 수렴한 반면에 제안된 알고리즘은 보다 향상된 결과를 가진 해에서 수렴하기 때문이다. 즉, 제안된 타 부 서치 알고리즘의 이웃해 생성방식인 인접 이동방식과 교환 이동방식이 효과적으로 동작하고 있음을 나타낸다. 또한 결과에서 어떠한 검색을 수행하지 않는 랜덤 방법보다 메타휴리스틱 방법을 사용하는 방법이 더 우수함을 볼 수 있다.
이것은 네트워크 노드의 밀도가 커짐에 따라 제안된 타부 서치 알고리즘이 PSO 알고리즘보다 더 많은 이웃해 생성을 하기 때문이다. 하지만 제안된 타부 서치 알고리즘이 기존의 방식에 비해 비슷한 실행 시간 내에서 더 넓은 감시영역을 찾고 있음을 알 수 있다. 결론적으로 성능평가 결과에서 제안된 알고리즘이 NP-hard 문제인 센서 노드 배치 문제를 적정한 실행 시간 내에 더 넓은 감시영역을 찾고 있으며 센서 노드 배치 문제를 효과적으로 해결할 수 있음을 알 수 있었다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

타부 서치 알고리즘 기반의 무선 센서 네트워크에서 센서 노드 배치
Sensor Node Deployment in Wireless Sensor Networks Based on Tabu Search Algorithm 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

데이터처리

성능/효과

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

타부 서치 알고리즘 기반의 무선 센서 네트워크에서 센서 노드 배치 Sensor Node Deployment in Wireless Sensor Networks Based on Tabu Search Algorithm 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

데이터처리

성능/효과

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

장길웅 (35)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

타부 서치 알고리즘 기반의 무선 센서 네트워크에서 센서 노드 배치
Sensor Node Deployment in Wireless Sensor Networks Based on Tabu Search Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper