무선 센서 네트워크에서의 Max k-Cut 기반의 클러스터링 알고리즘
Max k-Cut based Clustering Algorithm for Wireless Sensor Networks
- 발행기관 서강대학교 일반대학원
- 지도교수 장형수
- 발행년도 2009
- 학위수여년월 2009. 2
- 학위명 석사
- 실제URI http://www.dcollection.net/handler/sogang/000000044812
- 본문언어 한국어
초록/요약
무선 센서 네트워크 (Wireless Sensor Networks(WSNs))상에서 에너지 효율을 위한 대표적인 클러스터링 알고리즘인 LEACH(Low-Energy Adaptive Clustering Hierarchy)는 모든 노드들이 랜덤하게 돌아가면서 클러스터 헤드로 선출되는 방식으로 특정 노드가 모든 에너지를 소모하여 첫 번째로 죽는 시간인 수명을 연장시켰지만 클러스터 헤드가 확률적으로 선출되기 때문에 효율적인 클러스터링을 구성하지 못하는 경우가 발생한다. 이를 보완하는 방법으로 원하는 클러스터 헤드의 수보다 많은 클러스터 헤드 후보자들이 에너지 비교를 하여 경합하는 방식을 통해 고른 분포의 클러스터 헤드 선출을 유도하는 EECS(Energy Efficient Clustering Scheme)가 제안되었지만 이 역시 확률에 의한 방법으로 완벽하게 효율적인 클러스터링을 한다는 보장이 없다. 본 논문에서는 WSNs에서 Max k-Cut Problem을 기반으로 위치 정보를 사용하지 않고 클러스터 헤드를 적절히 분산하여 선출함으로써 에너지 효율적인 클러스터링을 하는 중앙처리 방식의 새로운 알고리즘 “MCCA : Max k-Cut based Clustering Algorithm for Wireless Sensor Networks”을 제안한다. MCCA는 이웃 노드와의 상대적이고 근사적인 거리 정보만을 사용하여 클러스터 헤드 사이의 거리를 알맞게 유지하도록 하기 위하여 Max k-Cut Problem을 사용한다. 또한 에너지가 적은 노드는 클러스터 헤드 선출에서 일정 기간 제외되는 방법을 사용함으로써 수명을 연장시키는 효과를 가져온다. LEACH보다 50%가량, EECS보다 20%가량 에너지 효율이 증대됨과 GPS를 사용한 BCDCP(Base-Station Controlled Dynamic Clustering Protocol)와 에너지 효율이 비슷함을 실험을 통하여 보인다.
more목차
제1장 서론 = 1
제2장 문제 정의 = 4
2.1 Network Model = 4
2.2 연구 목적 = 5
제3장 관련 연구 = 7
3.1 LEACH(Low-Energy Adaptive Clustering Hierarchy) = 9
3.2 EECS(An Energy Efficient Clustering Scheme in Wireless Sensor Networks) = 12
3.3 BCDCP(Base-Station Controlled Dynamic Clustering Protocol) = 15
제4장 MCCA(Max k-Cut Based Clustering Algorithm) = 18
4.1 기본 착안 = 18
4.2 알고리즘 = 26
4.2.1 이웃 노드 설정 및 전송 단계 = 30
4.2.2 Max k-Cut Problem 해결 단계 = 31
4.2.3 클러스터 헤드 선출 및 클러스터링 단계 = 33
4.2.4 감지 및 데이터 전송 단계 = 34
4.2.5 클러스터 헤드 재선출 = 34
제5장 실험 결과 및 분석 = 37
5.1 실험 환경 = 37
5.2 결과 및 분석 = 39
제6장 결론 및 향후 과제 = 50
참고문헌 = 51
그림목차
[그림 1] 클러스터 헤드로 선출되는 노드의 수에 따른 전체 에너지 감소율 = 10
[그림 2] BCDCP에서 분할 알고리즘이 두 번 수행되었을 때 클러스터들 = 16
[그림 3] 전송 세기에 따른 이웃 노드 설정 = 19
[그림 4] 서로의 이웃이 아닌 노드들의 배치 = 19
[그림 5] 네트워크 공간에서의 20개의 노드 분포 = 22
[그림 6] 노드 C의 거리별 이웃 노드 구분 = 23
[그림 7] 노드 C의 이웃 노드와의 가중치 부여 = 23
[그림 8] 노드 C와 같은 집합에 속한 노드 d, e, f = 24
[그림 9] 초기 노드의 배치 = 26
[그림 10] 각 노드 사이의 가중치 테이블 = 27
[그림 11] Max k-Cut Problem을 통하여 얻은 partition P = 28
[그림 12] P_(0)에서 P(k-1)까지 클러스터 헤드로 사용하면서 알고리즘 진행 = 29
[그림 13] 라운드에 따른 살아있는 노드의 수 (LEACH, MCCA) - Nomal size area = 40
[그림 14] 라운드에 따른 살아있는 노드의 수 (LEACH, MCCA) - Large size area = 40
[그림 15] 라운드에 따른 전체 누적 에너지 소모량 (LEACH, MCCA) - Normal size area = 41
[그림 16] 라운드에 따른 전체 누적 에너지 소모량 (LEACH, MCCA) - Large size area = 41
[그림 17] 라운드에 따른 살아있는 노드의 수 (LEACH, EECS, MCCA) - Normal size area = 43
[그림 18] 라운드에 따른 살아있는 노드의 수 (LEACH, EECS, MCCA) - Large size area = 43
[그림 19] 라운드에 따른 살아있는 노드의 수 (LEACH, BCDCP, MCCA) - Normal size area = 45
[그림 20] 라운드에 따른 살아있는 노드의 수 (LEACH, BCDCP, MCCA) - Large size area = 45
[그림 21] □에 따른 첫 번째로 죽는 노드가 발생하는 라운드 - BS=(50,200) = 47
[그림 22] □에 따른 첫 번째로 죽는 노드가 발생하는 라운드 - BS=(50,120) = 47
[그림 23] 전파 세기에 따른 수명 = 49
표목차
[표 1] EECS에서 용어의 의미 = 12
[표 2] 실험 환경 = 38
