선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 클러스터 센서 네트워크를 구성하는 많은 센서 노드와 베이스 스테이션을 연결하여 트리 또는 네트워크를 구축함에 있어, 최소 신장 트리를 적절히 활용한 근사 최소 스타이너 트리의 생성 및 적용 방법을 제안한다. 이 방법에서 클러스터 센서 네트워크의 각 클러스터에 소속된 입력 노드들을 완전 연결하는 간선(edge)들과, 각 클러스터 사이를 최소 거리로 연결하는 간선들을 생성한 후, 입력 노드들과 이러한 간선들을 이용하여 최소 신장 트리를 생성하고, 이를 기반으로 근사 최소 스타이너 트리를 미리 정의해 둔 종료조건이 만족될 까지 반복적으로 생성한다.
- 본 논문에서는 클러스터 센서 네트워크의 신속한 구축을 위해, 각 클러스터 내에 존재하는 모든 노드들을 완전 연결하는 간선과, 각 클러스터들을 최소 거리로 연결하는 간선을 생성하여 이를 이용하여 최소 신장 트리를 구축하고 이 트리내의 노드와 간선를 이용하여 스타이너 포인트들을 적절히 생성하고, 이를 이용하여 근사 최소 스타이너 트리를 반복적으로 생성하는 방법을 제안한다. 이 방법은 모든 입력 단말 노드를 완전 연결하여 간선을 생성하는 유클리드 최소 신장 트리를 활용하여 구축한 naive spanning 방법의 센서 네트워크와 비교할 때, 생성 시간은 1770.
제안 방법
- 이 방법에서 클러스터 센서 네트워크의 각 클러스터에 소속된 입력 노드들을 완전 연결하는 간선(edge)들과, 각 클러스터 사이를 최소 거리로 연결하는 간선들을 생성한 후, 입력 노드들과 이러한 간선들을 이용하여 최소 신장 트리를 생성하고, 이를 기반으로 근사 최소 스타이너 트리를 미리 정의해 둔 종료조건이 만족될 까지 반복적으로 생성한다. 종료 조건을 만족하는 어떤 근사 최소 스타이너 트리의 간선 중에서 제한 전송 거리를 초과하는 간선들을 찾고, 이들을 분해하여 제한 전송 길이 이내의 간선들로 대체하는 연결들을 생성한다. 이 제한 전송 거리는 무선통신에서의 최대 전송 거리와 동일하다.
- 또한 근사 스타이너 트리를 이용하여 원격 무선 검침 시스템의 네트워크를 효과적으로 구성한 연구가 발표되었다. 이 연구는 원격 검침 시스템을 구성하는 검침기, 중계기, 집중기의 배치 및 연결을 근사 스타이너 트리를 이용한 방안을 제안하였고, 이를 최소 신장 트리를 이용한 방법과 비교하였다[10]. 비 방향 스타이너 트리 문제를 위한 연구로, 그래프 축소 규칙을 이용하여, 먼저 불필요한 노드들과 간선들을 제거한 후, Prim의 알고리즘을 적용한 Max-Min Ant Colony 최적화 방법에 관한 연구가 발표되었다[11].
- L을 한 변으로 하여 정삼각형을 생성하고, 이 정삼각형의 구성을 위해 새로 도입된 정점을 Q라 정의할 때, 이 정삼각형의 외접원과 정점 Q와 R을 연결한 직선의 교점을 스타이너 포인트로 정의한다. 모든 간선의 쌍에 대해 이와 같은 방법으로 스타이너 포인트들을 생성하고 이를 활용하여 스타이너 트리를 생성한다. 즉, 고려 대상인 트리에서, 서로 인접한 모든 두 간선을 구성하는 세 개의 노드들의 집합에 대해 삼각형들을 형성하고, 위의 방법을 이용하여 스타이너 포인트를 생성하여 최소 스타이너 트리를 생성한다.
- 모든 간선의 쌍에 대해 이와 같은 방법으로 스타이너 포인트들을 생성하고 이를 활용하여 스타이너 트리를 생성한다. 즉, 고려 대상인 트리에서, 서로 인접한 모든 두 간선을 구성하는 세 개의 노드들의 집합에 대해 삼각형들을 형성하고, 위의 방법을 이용하여 스타이너 포인트를 생성하여 최소 스타이너 트리를 생성한다.
- 본 논문에서 제안하는 방법은 각 클러스터내의 모든 입력 노드들을 완전 연결하고 또 각 클러스터를 최소의 길이로 연결할 수 있는 노드들을 각 클러스터에서 찾아 서로 연결하는 간선들을 생성한다. 입력 노드들과 생성된 간선들을 이용하여 최소 신장 트리를 생성한 후, 적절한 방법을 이용하여 스타이너 포인트들을 생성한다[17].
- 입력 노드들과 생성된 간선들을 이용하여 최소 신장 트리를 생성한 후, 적절한 방법을 이용하여 스타이너 포인트들을 생성한다[17]. 생성된 스타이너 포인트들을 이와 관련된 노드들과 연결하여 스타이너 그래프를 생성한 후, 이 그래프의 노드들과, 스타이너 포인트, 간선을 이용하여 최소 신장 트리를 생성한다. 생성된 최소 신장 트리에서 필요 없는 스타이너 포인트나 연결을 삭제하여 중간 단계의 근사 최소 스타이너 트리를 생성한다.
- 생성된 최소 신장 트리에서 필요 없는 스타이너 포인트나 연결을 삭제하여 중간 단계의 근사 최소 스타이너 트리를 생성한다. 이 중간 단계의 트리를 좀 더 최적화하기 위해, 스타이너 포인트들을 생성하여 새로운 스타이너 그래프와 최소 신장 트리를 생성하고 필요 없는 스타이너 포인트와 연결을 삭제하는 작업을 다시 차례로 반복하여 새로운 근사 최소 스타이너 트리를 생성한다. 미리 정해진 종료 조건을 만족할 때까지 이러한 과정으로 반복적으로 근사 최소 스타이너 트리를 생성하여 최종 트리를 생성하고, 이 트리의 간선 중에서 최대 전송거리를 초과하는 간선에 대하여 최대 전송 거리 단위로 두 노드 사이에 중계 노드를 추가한다.
- 따라서 위에서 기술한 과정을 수행하기 위한 총 수행시간은 단계 1과 단계 2의 완전 연결 간선을 생성하는 과정을 포함하여 O(N2)+(2k+1-2)×O(N×logN)인데, 노드의 수 N에 비해 반복 회수 k를 작게 할 경우, 이 값은 O(N2)이 된다. 따라서 정해진 반복회수 k를 외부 인자로 입력하여 상수화 했을 경우, 본 논문에서 제안하는 방법은 O(N2) 시간 내에 클러스터 센서 네트워크를 형성할 수 있다. 이는 본 연구에서 제안하는 방법과 비교대상인 naïve spanning 방법과 동일하다.
- 또한 3장에서 기술한 naïve spanning 방법, cluster spanning 방법, 그리고 본 논문에서 제안한 방법의 센서 네트워크들의 길이와 생성 시간을 비교한다.
- <표 1>에는 본 실험의 인자인 입력 단말 노드 수 5가지, 클러스터 수 5가지, 최대 연결 길이 4가지를 조합한 100가지 종류의 입력환경에서 주어진 방법에 따라 생성된 트리들의 평균 결과를 보인다. 본 논문에서 제안한 방법은 최종 클러스터 센서 네트워크 트리를 생성하기 위해 200번의 중간 단계의 근사 최소 스타이너 트리를 반복적으로 생성한다. 그 이유는 스타이너 트리의 생성은 비다항식적 시간(Non-Polynomial Time) 문제에 속하므로, 이것의 최적 해를 현실 세계에서 다항식적 시간 내에 생성하는 것은 불가능하기 때문이다.
- 본 논문에서 제안하는 방법인 proposed Steiner(opt), proposed Steiner(200), proposed Steiner(0.1%opt)도 clustering을 통한 지역적 최적화를 일부 채용하지만, 그 실행 과정에서 근사 스타이너 트리를 위한 최소 신장 트리를 반복적으로 생성하고 이를 변형, 사용하므로, 단 한번의 신장 트리를 생성하는 naïve spanning이나 cluster spanning 방법보다 생성 시간이 많이 필요하게 된다.
- 그 이유는 스타이너 트리의 생성은 비다항식적 시간(Non-Polynomial Time) 문제에 속하므로, 이것의 최적 해를 현실 세계에서 다항식적 시간 내에 생성하는 것은 불가능하기 때문이다. 따라서 200번의 근사 스타이너 트리를 생성하는 가운데 최소 길이 Dmin를 갖는 트리를 찾아 클러스터 센서 네트워크를 모델링하는 최종 근사 스타이너 트리로 출력하고 proposed Steiner(200)으로 표시한다. proposed Steiner(opt) 는 200번 반복 생성되는 과정에서 첫 번째 생성되는 트리의 길이가 Dmin인 트리이고, proposed Steiner(0.
대상 데이터
- 본 논문에서 제안하는 방법을 검증하기 위한 비교대상은 naïve spanning 센서 네트워크 이다.
- 본 논문의 제안 방법을 검증하기 위한 실험의 인자로 입력 노드의 수 N, 클러스터의 수 C, 그리고 각 노드들의 최대 연결 길이 L이 이용된다. 본 연구에서는 각 노드의 최대 전송 거리를 1로 정의한다.
- 본 연구에서는 각 노드의 최대 전송 거리를 1로 정의한다. 관찰 대상은 생성된 센서 네트워크 트리의 길이 및 생성 시간, 최종 네트워크를 생성하기 위한 근사 스타이너 트리의 최소 반복 생성 회수이다. 또한 3장에서 기술한 naïve spanning 방법, cluster spanning 방법, 그리고 본 논문에서 제안한 방법의 센서 네트워크들의 길이와 생성 시간을 비교한다.
- 또한 3장에서 기술한 naïve spanning 방법, cluster spanning 방법, 그리고 본 논문에서 제안한 방법의 센서 네트워크들의 길이와 생성 시간을 비교한다. 실험을 위해 무작위로 생성된 노드의 수 N은 600, 1200, 1800, 2400, 3000개이다. 각 노드의 생성 방법은 무작위로 C개의 각 클러스터를 대표하는 중심 노드를 생성하고, 가장 가까운 중심 노드와의 거리가 최대 L만큼 떨어진 입력 단말 노드들을 생성한다.
- 0 사이의 x, y 좌표에 위치한다. 실험 환경은 Intel 1.83 GHz (T5600) 프로세서와 4기가 메모리의 랩탑 컴퓨터이고, 본 논문에서 제안하는 메카니즘은 C++로 구현하였다.
성능/효과
- 본 연구의 실험에서 cluster spanning 방법이 naïve spanning 방법에 비해 평균 51.7%의 시간 절감을 보였다.
- 본 논문에서 제안한 방법은 10개의 클러스터로 구성된 600개의 입력 단말 노드와 최대 전송 거리가 1인 환경에서, naïve 최소 신장 트리에 비해 2.2%, cluster spanning 방법에 비해 3.1%의 네트워크 길이의 절감을 보인다.
- 본 논문에서 제안하는 방법인 proposed Steiner(opt), proposed Steiner(200)은 naïve spanning 방법보다 평균 1.9%의 트리 길이의 절감을 보였고, 노드 수가 3000, 클러스터의 수가 2, 최대 연결 길이가 2인 입력 환경에서, 제안된 방법으로 생성된 트리는 최대 3.7%의 트리 길이의 절감을 보였다.
- 연결 최대 길이가 증가 함에 따라 본 논문에서 제안하는 방법인 proposed Steiner 방법은 naïve spanning 방법에 비해 네트워크 길이의 절감율이 점차 감소하지만 clustering spanning 방법에 비해서는 점차 증가함을 알 수 있다.
- 본 논문에서 제안하는 방법인 proposed Steiner(opt), proposed Steiner(200), poposed Steiner(0.1%opt) 방법도 clustering을 통한 지역적 최적화를 일부 채용하지만, 그보다는 Steiner 트리라는 비다항식적 시간에서의 최적화를 목표로 휴리스틱이 구현되었기 때문에, 이 방법은 naïve spanning 방법보다는 네트워크 길이가 절감되는 것이다.
- 이는 생성되는 트리들이 반복 생성되는 초기 단계에서 급속한 길이의 감소 변화를 보이고, 그 이후에 생성되는 트리들의 길이의 변화가 미세하기 때문이다. 본 논문의 실험에서 종료조건으로 설정한 근사 최소 스타이너 트리의 중복 생성 회수는 최대 200회이지만, 최소 길이의 트리들 중 최초로 생성하는 proposed Steiner(opt) 방법의 평균 반복 실행 회수는 110.7회이고, 최대 0.1%길이가 더해진 근사 스타이너 트리를 생성하는 proposed Steiner(opt) 방법의 평균 반복 회수는 평균 약 2.8회이다. 따라서 본 논문에서 제안하는 방법은 비교적 짧은 시간 내에 센서 네트워크의 길이의 절감이 필요한 응용에 잘 적용될 수 있음을 보인다.
- 이는 연결 최대 길이가 증가하면, 각 입력 노드가 소속된 클러스터의 중심 노드가 반드시 근접한 클러스터의 중심 노드일 보장이 없으므로, 각 입력 노드의 클러스터 중심 노드를 사전에 할당하는 방법에서는, 클러스터링을 고려치 않는 naïve spanning 방법에 비해 최적화에 근접하는 것이 어렵기 때문이다. 그러나 같은 클러스터링 기법을 사용하는 경우라도, Steiner 트리를 생성하는 과정에서 지역적 최적화의 문제점을 어느 정도 상쇄할 수 있는, 본 논문에서 제안하는 방법이 clustering spanning 방법보다 네트워크 길이 절감율이 높아지는 것이다. (그림 9)에서는 제안된 방법이 입력 단말 노드의 수가 증가함에 따라 naïve spanning 방법에 비해 네트워크 길이의 절감율이 높아짐을 확인할 수 있다.
- 이 실험 결과를 종합하면, 본 논문에서 제안하는 방법은 네트워크의 길이 측면과 네트워크 생성 시간 측면에서 모두 naïve spanning 방법에 비해, 최대 연결 길이가 작을수록, 입력 노드가 많을 수록, 클러스터의 수가 적을수록 좋은 성능을 보인다.
- 이는 전체 입력 노드를 고려 대상으로 생성된 최소 신장 트리를 이용하는 naïve spanning 방법이 입력 노드의 수가 증가함에 따라 실행 시간이 매우 많이 필요하기 때문에, 클러스터링 기법으로 인하여, 노드 수의 증가가 상대적으로 영향을 덜 미치는 cluster spanning과 본 논문에서 제안하는 방법은, 실행시간이 naïve clustering 방법에 비해서 감소되는 것이다.
- 따라서 (그림 10)에서 나타난 것 같이, cluster 수가 증가할수록, 클러스터링 기법을 사용한 cluster spanning과 본 논문에서 제안된 방법은 naïve spanning 트리에 대한 네트워크 길이를 비교했을 때, 증가율이 점차 커짐을 확인할 수 있다.
- 이는 본 논문에서 제안하는 방법의 문제점인 실행 시간이 큰 것에 대해서, 근사 최적화 길이보다 0.1% 증가된 네트워크의 길이를 허용한다면 naïve spanning 방식에 비해 비교적 크지 않은 추가 시간으로, 클러스터 센서 네트워크를 구축할 수 있음을 보이고, 결과적으로 클러스터 ad-hoc 센서 네트워크, 클러스터 이동 센서 네트워크 등과 같은 실시간 응용에 적용할 수 있는 가능성을 보인다.
- 본 논문에서 제안하는 방법은, 짧은 연결 최대 길이를 갖는 많은 수의 입력 단말 노드들이 적은 수의 클러스터들에 소속되어있는 환경에서, naïve spanning 방법으로 생성된 센서 네트워크 보다 높은 네트워크 길이의 절감율을 얻을 수 있고, 또한 실행 시간적인 측면에서 상대적으로 긍정적인 특성을 나타낸다.
- 이 실험 결과를 종합하면, 본 논문에서 제안하는 방법은 네트워크의 길이 측면과 네트워크 생성 시간 측면에서 모두 naïve spanning 방법에 비해, 최대 연결 길이가 작을수록, 입력 노드가 많을 수록, 클러스터의 수가 적을수록 좋은 성능을 보인다. 또한 clustering spanning 방법과 비교한다면, 제안하는 방법은 최대 연결 길이가 길수록, 네트워크의 길이 측면에서 약간 좋은 성능을 보이며, 실행시간 측면에서는 최대 연결길이가 짧을 수록, 입력 노드가 많을수록, cluster 수가 적을수록 상대적으로 좋은 성능을 보인다.
- 본 논문에서는 클러스터 센서 네트워크의 신속한 구축을 위해, 각 클러스터 내에 존재하는 모든 노드들을 완전 연결하는 간선과, 각 클러스터들을 최소 거리로 연결하는 간선을 생성하여 이를 이용하여 최소 신장 트리를 구축하고 이 트리내의 노드와 간선를 이용하여 스타이너 포인트들을 적절히 생성하고, 이를 이용하여 근사 최소 스타이너 트리를 반복적으로 생성하는 방법을 제안한다. 이 방법은 모든 입력 단말 노드를 완전 연결하여 간선을 생성하는 유클리드 최소 신장 트리를 활용하여 구축한 naive spanning 방법의 센서 네트워크와 비교할 때, 생성 시간은 1770.5%의 증가했지만 네트워크 길이를 최대 3.7%, 평균 1.9% 감소시켰다. 주목할만한 점은 naïve spanning 방법의 평균 실행시간에 20.
후속연구
- 센서 네트워크는 인간의 생활을 편리하게 하는 여러 다양한 기구나 장치, 장비에 송수신장비를 부착하여 이를 연결하고 통신할 수 있게 하거나, 사람의 접근이 힘든 공간에 많은 센서 노드를 설치하여, 각 센서 노드에서 수집한 정보를 유무선으로 연결하고 이를 이용하여 감시활동 등에 이용할 수 있다[1, 2]. 최근의 무선 개인 영역 네트워크 기술 및 초소형 네트워크 장비 기술 등 관련 기술의 급속한 발전에 힘입어 센서 네트워크를 활용한 응용이 활성화되고 있으며 향 후에 다양한 분야에 유용하게 널리 활용될 전망이다.
- 8회이다. 따라서 본 논문에서 제안하는 방법은 비교적 짧은 시간 내에 센서 네트워크의 길이의 절감이 필요한 응용에 잘 적용될 수 있음을 보인다.
- 향 후 연구는, 네트워크 길이 및 실행시간의 감소를 위한 제안된 방법의 개선이다. 또한 클러스터 센서 네트워크의 실 세계 응용에서 중요한, 매우 많은 센서 노드들을 효과적으로 처리하기 위해 다항적 시간 근사구조 (Polynomial Time Approximation Scheme)의 적용에 관하여 연구할 예정이다[9].
- 향 후 연구는, 네트워크 길이 및 실행시간의 감소를 위한 제안된 방법의 개선이다. 또한 클러스터 센서 네트워크의 실 세계 응용에서 중요한, 매우 많은 센서 노드들을 효과적으로 처리하기 위해 다항적 시간 근사구조 (Polynomial Time Approximation Scheme)의 적용에 관하여 연구할 예정이다[9].
※ AI-Helper는 부적절한 답변을 할 수 있습니다.