[논문]무선 센서 네트워크에서 클러스터 헤드의 멀티 홉 라우팅 트리 구성

최혜경; 강상혁

doi:10.7840/kics.2014.39b.11.763

무선 센서 네트워크에서 클러스터 헤드의 멀티 홉 라우팅 트리 구성
A Method for Constructing Multi-Hop Routing Tree among Cluster Heads in Wireless Sensor Networks 원문보기

한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스, v.39B no.11, 2014년, pp.763 - 770

최혜경 (University of Seoul, Department of Electrical and Computer Engineering) , 강상혁 (University of Seoul, Department of Electrical and Computer Engineering)

초록
AI-Helper

무선 센서 네트워크를 위한 전통적인 계층기반 라우팅 프로토콜인 LEACH 방법은 센서 노드들의 에너지 소비가 싱크 노드까지의 거리에 비례하여 증가하기에 불균일한 에너지 소비패턴을 보인다. 센서 필드가 큰 경우 이를 해결하기 위하여 멀티 홉 라우팅에 관한 연구들이 활발히 진행되고 있다. 기존의 연구에서는 클러스터 헤드로부터 단순히 가장 가까운 노드를 중계 노드로 선택하여 멀티 홉 경로를 구성하는데 반하여, 본 논문에서 제안하는 LEACH-CHT 방법은 최종 목적지인 싱크 노드까지의 전체 전송 에너지를 최소화 하는 경로를 선택한다. 본 논문의 방법은 클러스터 헤드가 매 홉에서 싱크 노드까지의 최소 비용 경로를 선택함으로써 추가적인 에너지 소비 없이 클러스터 헤드 자신보다 싱크 노드에서 멀리 위치한 노드들이 중간 경로 상에서 제외 되도록 하며 라우팅 상의 looping 문제를 효과적으로 해결할 수 있다. 컴퓨터 시뮬레이션을 통하여 본 논문에서 제안하는 방법이 노드들의 에너지 소모를 보다 균일하게 함으로써 LEACH보다 센서 노드의 평균 수명을 36% 더 연장하였고 참고한 기존의 멀티 홉 프로토콜들보다 12% ~ 36% 더 연장함으로써 성능이 더 뛰어나다는 것을 보였다.

Abstract ▼ AI-Helper

In traditional routing protocols including LEACH for wireless sensor networks, nodes suffer from unbalanced energy consumption because the nodes require large transmission energy as the distance to the sink node increase. Multi-hop based routing protocols have been studied to address this problem. In existing protocols, each cluster head usually chooses the closest head as a relay node. We propose LEACH-CHT, in which cluster heads choose the path with least energy consumption to send data to the sink node. In our research, each hop, a cluster head selects the least cost path to the sink node. This method solves the looping problem efficiently as well as make it possible that a cluster head excludes other cluster heads placed farther than its location from the path, without additional energy consumption. By balancing the energy consumption among the nodes, our proposed scheme outperforms existing multi-hop schemes by up to 36% in terms of average network lifetime.

주제어

AI 본문요약
AI-Helper

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

문제 정의

이러한 원거리 전송에서 에너지 소모 측면에서 최적화를 위하여 클러스터 헤드는 다른 클러스터 헤드를 거쳐서 전송할 때의 에너지 소모와 직접 전송할 때의 에너지 소모를 비교하여 최소의 에너지를 소모하는 경로를 선택한다. 결과적으로 클러스터 헤드들 간의 에너지 최적화된 트리를 형성하는 방법을 제안한다.
본 논문에서는 센서 네트워크의 효율적인 프로토콜인 LEACH에 대하여 살펴보고 LEACH에 존재하는 에너지 소모가 불균일한 문제점을 다루었다. 기존의 LEACH에서 클러스터 헤드가 직접 데이터를 싱크 노드에게 전송하기에 싱크 노드와 멀리 떨어져 있는 노드가 일찍 죽게 된다.
본 논문에서는 클러스터 헤드들이 싱크 노드에게 데이터를 전송할 때 데이터 전송 에너지 모델을 바탕으로 한 에너지 사용량 비교를 통하여 에너지 소모가 제일 적은 경로를 선택하는 멀티 홉 라우팅 방법을 제시한다. 이를 위하여 클러스터 헤드 노드들은 자신과 싱크 노드사이의 거리 정보를 서로 교환하면서 멀티홉 경로구성을 위한 트리를 형성하며, 결과적으로 노드들 사이에 에너지 소모 불 균일 현상을 최소화하고 전체 네트워크의 수명을 연장함을 시뮬레이션을 통하여 검증한다.

제안 방법

동일한 살아있는 노드개수에 대응하는 round도 LEACH-CHT에서 제일 크므로 LEACH-CHT의 노드의 평균수명이 제일 길며 전체 네트워크의 생존도 제일 길다는 것을 알 수 있다. 각 방법에 따라서 평균수명(L_AVG), 처음으로 죽는 노드(FND; first node death), 마지막으로 죽는 노드(LND; last node death)의 시간(round)을 표 2에 비교하였다.
그 결과 R이 약 100 [m]일 때 노드의 평균 수명이 제일 길게 나타난다. 그러므로 본 논문에서 R을 100 [m]로 하고 시뮬레이션을 통하여 본 논문에서 제안한 LEACH-CHT의 성능을 평가한다.
이것을 해결하기 위하여서 본 논문에서는 클러스터 헤드가 데이터를 전송할 때 에너지 비교를 통하여 싱글 홉과 멀티 홉 중 에너지를 더 절약하는 방법을 실시간으로 선택한다. 또한 일부 메시지들의 전송 범위가 전체 네트워크여서 네트워크 크기가 큰 경우에는 과도한 에너지 소모가 있는데 이를 줄이기 위해 제어 메시지 전송 범위 R에 대한 최적값을 시뮬레이션을 통하여 분석하였다.
먼저 제어 메시지 전송거리 R에 대하여, 기존의 LEACH 프로토콜에서 사용한 R = 282 [m] 값과 비교하여 본 논문에서 제안한 멀티 홉 프로토콜에서 사용할 최적의 값을 4.1절에서 제안한 R_min = 50 [m]과 R_max = 225 [m]의 사이에서 찾기 위하여 시뮬레이션을 수행하였다. 그림 6은 R을 50 [m]부터 변화시키면서 관측한 센서 노드의 평균수명을 나타낸다.
본 논문에서 제안하는 방법은 네트워크가 처음 형성될 때 싱크 노드가 정해진 출력 P_BS으로 전 네트워크에 beacon 메시지를 뿌리는 것으로 시작한다. 각 노드 i는 이 메시지를 수신하고 RSS (Received Signal Strength) 에 의해 자신과 싱크 노드 사이의 거리 d_i = d(P_BS,P_r) 을 계산 할 수 있다.
본 논문에서는 Set-up phase 단계에서 헤드와 멤버노드, 헤드 사이의 전송거리 R값을 기존의 방법인 네트워크 최대크기 #보다 작게 하면서 동시에 클러스터 헤드 사이의 트리구성을 위한 송수신을 고려하여 다음과 같이 R의 최소, 최대값 범위를 정한다.
센싱 기능과 네트워크 수명을 극대화하기 위하여서는 센서 노드들이 균일한 에너지 사용량을 보이는 것이 바람직한데, 본 논문에서는 이를 위하여 클러스터 헤드들이 트리를 구성하여서 싱크 노드에 데이터를 멀티 홉으로 전송하는 방법을 다음과 같이 제안한다.
기존의 LEACH에서 클러스터 헤드가 직접 데이터를 싱크 노드에게 전송하기에 싱크 노드와 멀리 떨어져 있는 노드가 일찍 죽게 된다. 이것을 해결하기 위하여서 본 논문에서는 클러스터 헤드가 데이터를 전송할 때 에너지 비교를 통하여 싱글 홉과 멀티 홉 중 에너지를 더 절약하는 방법을 실시간으로 선택한다. 또한 일부 메시지들의 전송 범위가 전체 네트워크여서 네트워크 크기가 큰 경우에는 과도한 에너지 소모가 있는데 이를 줄이기 위해 제어 메시지 전송 범위 R에 대한 최적값을 시뮬레이션을 통하여 분석하였다.
본 논문에서는 클러스터 헤드들이 싱크 노드에게 데이터를 전송할 때 데이터 전송 에너지 모델을 바탕으로 한 에너지 사용량 비교를 통하여 에너지 소모가 제일 적은 경로를 선택하는 멀티 홉 라우팅 방법을 제시한다. 이를 위하여 클러스터 헤드 노드들은 자신과 싱크 노드사이의 거리 정보를 서로 교환하면서 멀티홉 경로구성을 위한 트리를 형성하며, 결과적으로 노드들 사이에 에너지 소모 불 균일 현상을 최소화하고 전체 네트워크의 수명을 연장함을 시뮬레이션을 통하여 검증한다.
이와 같은 방법을 사용하여 각 클러스터 헤드는 주변의 다른 클러스터 헤드에서 온 advertisement를 수신하였을 때 대응하는 모든 주변 헤드에 대하여 그 헤드를 중계 노드로 하여 데이터를 전송할 때 소모하는 에너지를 계산한다. 직접 전송하는 것보다 에너지 소모가 적은 중계 노드들이 있다면 그중 에너지 소모가 가장 적은 중계 노드를 선택한다.
일반 노드는 클러스터 헤드가 정해준 TDMA 스케줄에 따라 자신의 슬롯에 데이터를 클러스터 헤드에게 전송한다. 클러스터 헤드는 자신의 멤버 노드로부터 수신한 데이터를 병합한 후 4.3절에서 제안한 에너지 비교 방법으로 정해진 결과에 따라서 싱글 홉으로 싱크 노드에게 직접 전송하거나 또는 멀티 홉으로 데이터를 전송한다.
한편, 그림 2에 나타난 바와 같이 LEACH에서 제기된 싱크 노드와 멀리 떨어진 노드가 훨씬 더 많은 에너지를 소모하며 결국 먼저 죽게 되는 에너지 소모 불균일 문제점에 대한 LEACH-CHT의 성능을 검증하였다. 그림 7에 LEACH-CHT 방법으로 300 round까지 시뮬레이션을 실행한 결과를 싱크 노드에서의 거리에 대하여 노드들의 잔여 에너지로 나타내었다.

데이터처리

본 논문에서 제안하는 LEACH-CHT의 성능을 평가하기 위하여 C-language를 이용한 시뮬에이션 결과를 LEACH^[4]와 기존의 멀티 홉 프로토콜 MH-LEACH(Neto)^[8], MH-LEACH^[9], MR-LEACH^[10]과 비교하였다. 시뮬레이션에서 사용한 에너지 모델 관련 상수 값은 E_elec=50 nJ/bit, ε_fs=10 pJ/bit/m², ε_mp=0.

성능/효과

예를 들어서 한 변의 길이가 M인 정사각형의 필드가 있을 때 LEACH 프로토콜은 Advertisement의 전송범위를 네트워크상의 최대거리 #으로 한다. 그러나 본 논문에서 가정하는 넓은 센서필드 상에서 네트워크를 구성할 때 클러스터의 멤버 노드나 클러스터 헤드간의 중계전송을 고려하면 제어 메시지 전송 거리 R을 전체 네트워크 크기와 같게 하는 것은 에너지를 과다하게 소모한다는 것을 관찰하였다.
가로축은 round를 나타내고 세로축은 살아있는 노드개수를 나타내는데 그림에서 보면 LEACH-CHT에서 처음으로 죽는 노드가 제일 늦게 나타난다. 동일한 살아있는 노드개수에 대응하는 round도 LEACH-CHT에서 제일 크므로 LEACH-CHT의 노드의 평균수명이 제일 길며 전체 네트워크의 생존도 제일 길다는 것을 알 수 있다. 각 방법에 따라서 평균수명(L_AVG), 처음으로 죽는 노드(FND; first node death), 마지막으로 죽는 노드(LND; last node death)의 시간(round)을 표 2에 비교하였다.
표 2를 보면 본 논문의 제안방법은 LEACH보다 평균수명이 36% 늘었고 기존의 다른 멀티 홉 프로토콜보다는 12~36% 늘었다. 또한 처음으로 죽는 노드가 나타 난 것도 LEACH 보다 60% 개선되었고 다른 멀티 홉 프로토콜보다 24~38% 개선되었다.
시뮬레이션을 통하여 검증한 결과 본 논문에서 제안하는 LEACH-CHT 프로토콜이 기존의 LEACH와 기존의 멀티 홉 프로토콜들보다 노드들의 에너지 소모가 적고 균일하여 전체적인 네트워크의 수명을 효율적으로 연장한 것을 알 수 있다. 표 2를 보면 본 논문의 제안방법은 LEACH보다 평균수명이 36% 늘었고 기존의 다른 멀티 홉 프로토콜보다는 12~36% 늘었다.
스케줄의 앞부분은 멤버 노드의 전송 순서에 따라 멤버 노드의 ID를 적은 것이고 뒤 부분은 멤버 클러스터 헤드의 ID인데 전송 순서와 관계되는 것이 아니고 join-requset에 대한 reply이다. 클러스터 헤드가 중계 헤드로부터 TDMA schedule을 받고 자신의 ID가 있다는 것을 확인하면 전송 트리가 성공적으로 구축되었다는 것을 알 수 있다. 그림 5는 LEACH-CHT의 TDMA schedule 포맷이다.
시뮬레이션을 통하여 검증한 결과 본 논문에서 제안하는 LEACH-CHT 프로토콜이 기존의 LEACH와 기존의 멀티 홉 프로토콜들보다 노드들의 에너지 소모가 적고 균일하여 전체적인 네트워크의 수명을 효율적으로 연장한 것을 알 수 있다. 표 2를 보면 본 논문의 제안방법은 LEACH보다 평균수명이 36% 늘었고 기존의 다른 멀티 홉 프로토콜보다는 12~36% 늘었다. 또한 처음으로 죽는 노드가 나타 난 것도 LEACH 보다 60% 개선되었고 다른 멀티 홉 프로토콜보다 24~38% 개선되었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	클러스터링 기법의 특징은 무엇인가?	센서 네트워크의 에너지 소모를 최소화 하는 라우팅 방법으로서, 클러스터링 기법은 노드들의 효율적인 클러스터 구성과 데이터 병합을 통하여 노드들의 평균 에너지 소모를 줄이고 전체 네트워크의 수명을 연장하는 대표적인 방법이다. 클러스터링 기반 센서 네트워크 라우팅 기법으로 가장 유명한 방법은 LEACH[4] 라우팅 방법이다.
	LEACH[4] 라우팅 프로토콜은 노드들이 자발적으로 클러스터들을 형성하는데 이 때 클러스터 헤드는 어떻게 선출되는가?	무선 센서 네트워크를 위한 기존의 LEACH[4] 라우팅 프로토콜은 노드들이 자발적으로 클러스터들을 형성한다. 클러스터 헤드는 에너지 소모가 크므로 임의적으로 돌아가면서 선출된다. 클러스터 헤드가 아닌 모든 노드는 자신의 클러스터 헤드에게 자신의 데이터를 전송하고 클러스터 헤드는 자신의 클러스터 멤버 노드로부터 받은 데이터를 병합하여 싱크 노드에게 직접 전송하며 이는 싱글 홉 방식에 해당한다.
	Set-up phase는 어떤 단계로 이루어지는가?	Set-up phase는 클러스터 헤드 선출, Advertisement, Join-request, TDMA scheduling 단계로 이루어지며, 각 단계의 동작은 다음과 같다.

참고문헌 (11)

W. Park, "Fast link-setup protocol for wireless multimedia sensor networks," J. KICS, vol. 39C, no. 03, pp. 247-254, Mar. 2014.

원문보기 상세보기
S. Kim, C. Kim, H. Cho, Y. Yim, and S.-H. Kim, "Continuos moving object tracking using query relaying in tree-based sensor networks," J. KICS, vol. 39B, no. 05, pp. 271-280, May 2014.
W. Park, "Low power MAC protocol design for wireless sensor networks using recursive estimation methods," J. KICS, vol. 39C, no. 03, pp. 239-246, Mar. 2014.

원문보기 상세보기
W. Heinzelman, "An application-specific protocol architecture for wireless micro sensor networks," IEEE Trans. Wirel. Commun., vol. 1, no. 4, pp. 660-670, Oct. 2002.

상세보기
L. Zhang, D. Wang, and Y. Sun, "Research on cluster-based routing protocol with multi-hop," 2013 3rd Int. Conf. Instrument, Measurement, Computer, Commun. Control, pp. 1578-1581, Shenyang, China, Sept. 2013.
L. Xu, G. M. P. O'Hare, and R. Collier, "A balanced energy-efficient multihop clustering scheme for wireless sensor networks," Wirel. Mob. Netw. Conf., pp. 1-8, Vilamoura, Portugal, May 2014.
B, Manjuprasad and A. Dharani, "Uniform multihop clustering for low communication overhead in sensor networks," C2SPCA Int. Conf. pp. 1-4, Bangalore, India, Oct. 2013.
J. Neto, A. Rego, A. Cardose, and J. Junior, "MH-LEACH: A distributed algorithm for multi-hop communication in wireless sensor networks," ICN 2014, pp. 55-61, Nice, France, Feb. 2014.
G. Wang, H. Zhu, and H. Dai, "The clustering algorithm of wireless sensor networks based on multi-hop between clusters," Comput. Sci. Inf. Eng., pp. 177-181, Los Angeles, USA, Mar. 2009.
M. O. Farooq, "MR-LEACH: Multi-hop routing with low energy adaptive clustering hierarchy," 2010 4th Int. Conf. Sensor Technol. Appl., pp. 262-268, Venice, Italy, Jul. 2010.
U. Hari, B. Ramachandran, and C. Johnson, "An unequally clustered multihop protocol for wireless sensor networks," 2013 Int. Conf. Advances in Comput., Commun. Informatics (ICACCI), pp. 1007-1011, Mysore, USA, Aug. 2013.

저자의 다른 논문 :

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

연합인증