Tabu Search Algorithm for Minimum Weight Connected Dominating Set Problem in Wireless Sensor Networks

무선 센서 네트워크에서 최소 가중치 연결 지배 집합 문제는 백본 구성, 라우팅, 스케줄링과 같은 다양한 응용 분야에서 핵심적인 역할을 한다. 본 논문은 각 노드가 가중치를 가지는 무선 센서 네트워크에서 전체 네트워크를 소그룹을 나누고, 각 그룹의 헤더의 역할을 하는 지배자의 가중치 합을 최소화는 최적화 알고리즘을 제안한다. 제안된 최적화 알고리즘은 메타 휴리스틱 방식의 타부서치 알고리즘을 적용하여 주어진 문제를 해결한다. 제안된 타부서치 알고리즘에서는 효율적인 인코딩 구조와 이웃해 생성방식을 제안하여 지배자의 가중치를 최소화하도록 설계되었다. 제안된 타부서치 알고리즘의 성능평가는 노드의 수가 많은 네트워크에서 다양한 네트워크 환경에서 상용된 모든 지배자의 가중치 합과 실행시간 관점에서 수행되었다. 평가 결과에서 제안된 타부서치 알고리즘이 기존의 최적화 알고리즘보다 약 10-20% 우수한 성능을 보임을 알 수 있었다.