[논문]무선 센서 네트워크에서 에너지 효율적 패킷 전송을 위한 부하 균형 클러스터링 모델

이재희; 김병기; 강승호

doi:10.3745/ktccs.2015.4.12.409

무선 센서 네트워크에서 에너지 효율적 패킷 전송을 위한 부하 균형 클러스터링 모델
A Load Balanced Clustering Model for Energy Efficient Packet Transmission in Wireless Sensor Networks 원문보기

정보처리학회논문지. KIPS transactions on computer and communication systems 컴퓨터 및 통신 시스템, v.4 no.12, 2015년, pp.409 - 414

이재희 (전남대학교 전산학과) , 김병기 (전남대학교 전자컴퓨터공학부) , 강승호 (동신대학교 정보보안학과)

초록
AI-Helper

제한된 에너지 자원으로 동작하는 무선 센서 네트워크에서는 에너지 소비를 최소화하여 통신하는 방법이 중요한 연구 주제이다. 클러스터 헤드를 가진 구분되는 클러스터 안에 센서 노드를 그룹으로 묶는 클러스터링은 에너지 절약에 가장 효과적인 기술로 알려져 있다. 그러나 클러스터 기반 무선 센서 네트워크에서 클러스터 헤드나 게이트웨이는 수집된 정보를 싱크로 보내는 역할 등을 수행하기 때문에 더 많은 에너지를 소비하게 된다. 부적절한 클러스터의 구성은 게이트웨이에 오버로드를 가중시켜 전체 네트워크의 성능을 저하시킨다. 본 논문에서는 에너지 효율을 높이고 네트워크 수명을 향상시키기 위하여 새로운 부하 균형 클러스터링 모델을 제시하고 이를 분기한정 알고리즘과 다중시작 지역탐색 알고리즘을 설계하여 기존에 제시된 부하 균형 클러스터링 모델과 비교한 후 성능 측정 실험 후 결과를 제시한다.

Abstract ▼ AI-Helper

The energy conservation is the most important subject for long run operation of the sensor nodes with limited power resources. Clustering is one of most energy efficient technique to grouped the sensor nodes into distinct cluster. But, in a cluster based WSN, CHs and gateways bear an extra work load to send the processed data to the sink. The inappropriate cluster formation may cause gateways overloaded and may increase latency in communication. In this paper, we propose a novel load balanced clustering model for improving energy efficiency and giving a guarantee of long network lifetime. We show the result of performance measurement experiments that designs using a branch and bound algorithm and a multi-start local search algorithm to compare with the existing load balanced clustering model.

주제어

AI 본문요약
AI-Helper

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

문제 정의

우리는 네트워크 부하로 거리의 제곱을 사용하여 시뮬레이션한 결과 더 좋은 성능을 확인했다. 본 논문에서는 [7]의 내용을 확장한 것으로 항상 최적해를 보장해주는 분기한정 알고리즘과 큰 해공간에서 최적해에 가까운 해를 보장하는 다중시작 지역탐색 알고리즘을 설계하여 클러스터링 모델의 효율성을 검증해본다. 논문의 구성은 다음과 같다.
분기한 정 알고리즘은 모든 후보해를 나열해서 최적화할 수치의 상한이나 하한을 추정하여 해공간의 탐색 영역을 줄이는 방법으로 불필요한 영역을 제거하여 시간 소모를 줄일 수 있다. 본 논문에서는 최적해를 보장해주는 분기한정 알고리즘을 설계하여 제안 모델의 성능을 확인한다. 기존의 모델들의 방법(∑d)과 본 논문이 제시한 방법(∑d²)을 LEACH의 에너지 모델을 사용하여 에너지 효율성을 비교하기 위해 최적해를 보장하는 분기한정 알고리즘을 설계하였다.
따라서 에너지 효율을 높이고 네트워크 수명을 높이기 위해서는 적절한 클러스터링 모델을 사용하여 클러스터링을 수행하고 적용 가능한 휴리스틱 알고리즘을 설계하여 클러스터를 구성하는 것이 필요하다. 본 논문에서는 효과적인 부하 균형 클러스터링을 구성하기 위한 새로운 클러스터링 모델을 제시한다. 일반적으로 패킷 전송에 소모되는 에너지는 노드 간 거리의 제곱에 비례하는데 기존에 제시된 방법들은 이를 간과하고 거리를 네트워크 부하로 사용하는 한계를 보여주었다.
본 논문은 센서의 에너지 효율과 네트워크 수명을 보장하기 위한 부하 균등 클러스터링 모델을 제시하였다. 게이트웨이를 사용하여 구성된 센서 네트워크 아키텍처에서 노드 사이의 거리의 제곱을 부하로 사용하였다.

가설 설정

데이터 전송량이 규칙적이지 못한 네트워크에서는 에너지 효율이 떨어진다.2) 싱글 홉 전송방식을 사용하므로 싱크에 직접적으로 데이터를 전송해야 한다. 이는 결과적으로 더 많은 에너지 소비가 발생된다.

제안 방법

200m×200m 공간에 3개의 게이트웨이와 10, 15, 20개의 센서들을 무작위로 배치하고 거리를 부하로 사용한 경우와 본 논문이 제시한 거리의 제곱을 부하로 사용한 경우각각에 대해 최적 클러스터링을 계산하였다.
게이트웨이가 15개, 30개이고, 센서 수가 50개와 400개 사이의 개수로 주어졌을 경우, 각각의 네트워크에서 50에서 400개까지의 센서를 가지고 최대 5000라운드에 도달할 때까지 수명을 다한 센서의 수를 거리를 사용하는 경우와 거리 제곱을 사용하는 경우를 비교하였다. Fig.
기존의 모델들의 방법(∑d)과 본 논문이 제시한 방법(∑d2)을 LEACH의 에너지 모델을 사용하여 에너지 효율성을 비교하기 위해 최적해를 보장하는 분기한정 알고리즘을 설계하였다.
노드 간 거리를 부하로 사용한 경우와 거리의 제곱을 부하로 사용한 경우의 부하 균형 클러스터링의 성능을 측정하기 위해 분기 한정 알고리즘을 설계하였다. 본 논문에서는 거리(∑d)와 거리의 제곱(∑d²)을 사용하는 클러스터링의 성능을 비교하여 거리를 부하로 사용하는 것보다 거리의 제곱을 사용하는 방법이 에너지 효율성을 높여줌을 보여준다.
게이트웨이를 사용하여 구성된 센서 네트워크 아키텍처에서 노드 사이의 거리의 제곱을 부하로 사용하였다. 노드 사이의 거리를 부하로 사용하는 기존 모델들이 제시한 부하 균형 클러스터링 모델과 에너지 효율에서의 성능을 비교 분석하기 위하여 최적해를 보장하지만 큰 네크워크에서는 적용이 어려운 분기한정 알고리즘과 항상 최적해를 보장하지는 못하지만 대규모 네트워크를 대상으로도 클러스터링이 가능한 메타 휴리스틱 알고리즘인 다중 시작 지역탐색 알고리즘을 설계하였다. 성능을 분석하기 위하여 다양한 실험 환경을 구성하여 실시하였다.
그리고 부하를 거리로 사용한 경우와 거리의 제곱을 사용한 경우의 부하 균형 클러스터링 문제는 같지 않으며 따라서 그 해가 항상 일치하는 것은 아니다. 본 논문은 노드간 거리가 아니라 거리의 제곱을 부하로 사용하여 부하 균형 클러스터링 문제를 다시 정의한다.
노드 사이의 거리를 부하로 사용하는 기존 모델들이 제시한 부하 균형 클러스터링 모델과 에너지 효율에서의 성능을 비교 분석하기 위하여 최적해를 보장하지만 큰 네크워크에서는 적용이 어려운 분기한정 알고리즘과 항상 최적해를 보장하지는 못하지만 대규모 네트워크를 대상으로도 클러스터링이 가능한 메타 휴리스틱 알고리즘인 다중 시작 지역탐색 알고리즘을 설계하였다. 성능을 분석하기 위하여 다양한 실험 환경을 구성하여 실시하였다. 실험 결과 게이트웨이에 노드를 분배하는 경우 노드 간의 거리를 부하로 고려하는 방법에 비하여 노드 간 거리 제곱을 부하로 고려한 최적 클러스터링이 네트워크의 수명과 에너지 효율성 모두에서 더 좋은 것으로 나타났다.
큰 규모의 네트워크에서도 최적해에 가까운 해를 보장해주는 다중 시작 지역탐색 알고리즘으로 설계하여 노드 간 거리를 고려한 방법과 비교한 후 라운드에 따른 dead 센서 수를 비교하여 시뮬레이션하기 위하여 Table 2와 같은 실험조건을 사용하였다. 센서 노드와 게이트웨이의 수를 제외한 나머지 조건은 Table 1에서 사용한 것과 같다.

이론/모형

네트워크의 에너지 소비 모델은 LEACH의 제안 모델을 사용한다[8]. 기존의 제안 방법에서도 동일한 에너지 모델을 사용하였기에 비교에 문제가 없을 것으로 판단된다.
만약 거리가 임계값 d₀보다 적다면 e_fs모델을, 크면 e_mp모델을 사용한다. e_fs와 e_mp는 에너지 서킷에 의해서 요구되는 에너지량이고, k bit 패킷을 수신할 때 소모되는 에너지량은 다음 식으로 계산한다.

성능/효과

그러나 이 방법은 몇 가지 문제점을 가지고 있다.1) 한번 CH로 선택되면 이후 모든 노드들이 CH 역할을 끝마칠 때까지 다시 CH로 선택되지 않는다. 데이터 전송량이 규칙적이지 못한 네트워크에서는 에너지 효율이 떨어진다.
3은 센서 노드 수가 200개, 400개인 경우를 비교한 그래프이다. 그 결과 제안 방법이 평균 103개, 거리를 사용하는 방법은 153.3개로 약 50개, 33% 더 적은 데드 센서의 수로 나은 결과를 나타냈다.
2는 분기한정 알고리즘으로 설계하여 20개의 네트워크를 생성해 시뮬레이션하고 네트워크 수명을 평균한 것이다. 모든 센서 수에서 거리의 제곱을 부하로 사용한 방법의 네트워크 수명이 길다는 사실을 알 수 있다.
본 논문에서는 거리(∑d)와 거리의 제곱(∑d2)을 사용하는 클러스터링의 성능을 비교하여 거리를 부하로 사용하는 것보다 거리의 제곱을 사용하는 방법이 에너지 효율성을 높여줌을 보여준다.
분기한정 알고리즘은 한정 함수를 이용하여 탐색 영역을 줄인다 하더라도 전체 해공간을 대상으로 탐색해야 하기 때문에 센서의 수가 많을 경우 적용함에 있어 한계를 보인다. 분기한정 알고리즘의 문제점인 큰 규모의 네트워크에 적용이 어려운 점을 고려하여 다중시작 지역탐색 알고리즘을 설계하여 큰 규모의 네트워크에서도 클러스터링이 가능함을 보여준다. 다중시작 지역탐색 알고리즘에서 다음번 탐색의 대상이 되는 특정 해에 대한 이웃해는 그와 1비트 다른 해로 정의한다.
성능을 분석하기 위하여 다양한 실험 환경을 구성하여 실시하였다. 실험 결과 게이트웨이에 노드를 분배하는 경우 노드 간의 거리를 부하로 고려하는 방법에 비하여 노드 간 거리 제곱을 부하로 고려한 최적 클러스터링이 네트워크의 수명과 에너지 효율성 모두에서 더 좋은 것으로 나타났다. 이러한 결과를 바탕으로 무선 센서 네트워크의 구성을 설계할 때 센서의 수뿐 아니라 거리에 따른 센서의 선택 등에 있어 참고 자료로 이용될 것으로 기대된다.
일반적으로 패킷 전송에 소모되는 에너지는 노드 간 거리의 제곱에 비례하는데 기존에 제시된 방법들은 이를 간과하고 거리를 네트워크 부하로 사용하는 한계를 보여주었다. 우리는 네트워크 부하로 거리의 제곱을 사용하여 시뮬레이션한 결과 더 좋은 성능을 확인했다. 본 논문에서는 [7]의 내용을 확장한 것으로 항상 최적해를 보장해주는 분기한정 알고리즘과 큰 해공간에서 최적해에 가까운 해를 보장하는 다중시작 지역탐색 알고리즘을 설계하여 클러스터링 모델의 효율성을 검증해본다.
전체적으로 모든 라운드에서 거리의 제곱을 사용한 방법의 에너지 소비율이 고르게 낮음을 확인하였고 평균 65.5J 약 15%의 에너지의 소비량이 감소됨을 확인하였다.

후속연구

실험 결과 게이트웨이에 노드를 분배하는 경우 노드 간의 거리를 부하로 고려하는 방법에 비하여 노드 간 거리 제곱을 부하로 고려한 최적 클러스터링이 네트워크의 수명과 에너지 효율성 모두에서 더 좋은 것으로 나타났다. 이러한 결과를 바탕으로 무선 센서 네트워크의 구성을 설계할 때 센서의 수뿐 아니라 거리에 따른 센서의 선택 등에 있어 참고 자료로 이용될 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	대부분의 무선 센서 네트워크의 구성은 어떻게 되는가?	센서 네트워크는 환경 감시, 재난 정보 시스템, 의료 보건, 침입 탐지 등을 포함한 다양한 분야에서의 유용성으로 인하여 많은 연구가 이루어지고 있다[1]. 대부분 무선 센서 네트워크는 감지, 데이터 전송, 전력 공급 유닛을 가진 수많은 작은 센서 노드를 분산 배치하여 구성한다. 제한된 에너지 자원으로 작동하는 무선 센서 네트워크에서는 에너지 소비를 최소화하여 통신하는 기법은 중요한 연구 분야이다.
	클러스터링이란 무엇인가?	제한된 에너지 자원으로 작동하는 무선 센서 네트워크에서는 에너지 소비를 최소화하여 통신하는 기법은 중요한 연구 분야이다. 클러스터 헤드(Cluster Head, 이하 CH)를 가진 구분되는 클러스터 안에 센서 노드를 그룹으로 묶는 클러스터링은 에너지 절약에 매우 효과적인 기술이다[2]. 클러스터 기반 무선센서 네트워크는 1) 데이터 수집, 라우팅 프로세스와 같이 각각의 클러스터에서 수행되어야 되는 대표적인 작업등을 하나의 노드에서 수행하므로 에너지 소비를 감소시킬 수 있으며 2) 자신의 클러스터 헤드만 통신할 필요가 있기 때문에 통신 대역폭을 상당히 절약할 수 있고, 중복 메시지 교환을 피할 수 있다.
	LEACH로 알려진 분산 클러스터를 구성하는 방법의 문제점은 무엇인가?	그러나 이 방법은 몇 가지 문제점을 가지고 있다. 1) 한번 CH로 선택되면 이후 모든 노드들이 CH 역할을 끝마칠 때까지 다시 CH로 선택되지 않는다. 데이터 전송량이 규칙적이지 못한 네트워크에서는 에너지 효율이 떨어진다. 2) 싱글 홉 전송방식을 사용하므로 싱크에 직접적으로 데이터를 전송해야 한다. 이는 결과적으로 더 많은 에너지 소비가 발생된다. 이러한 문제점을 개선한 PEGASIS(Power-Efficient Gathering in Sensor Information Systems)[9], HEED(Hybrid Energy-Efficient Distributed clustering)[10], TEEN(Threshold sensitive Energy Efficient sensor Network protocol)[11], TL-LEACH(Two-Level Hierarchy LEACH)[12] 등의 많은 알고리즘이 제시되었다.

참고문헌 (15)

K. Akkaya and M. Younis, "A survey on routing protocols for wireless sensor networks," Ad Hoc Networks, Vol.3, No.3, pp.325-349, 2005.

상세보기
J. Yick, B. Mukherjee and D. Ghosal, "Wireless sensor network survey," Computer Networks, Vol.52, No.12, pp.2292-2330, 2008.

상세보기
A. A. Abbasi and M. Younis, "A survey on clustering algorithms for wireless sensor networks," Computer Communications, Vol.30, No.14, pp.2826-2841, 2007.

상세보기
G. Gupta and M. Younis, "Load-balanced clustering of wireless sensor networks," Communications, ICC'03. IEEE International Conference on, IEEE, pp.1848-1852. 2003.
C. P. Low, C. Fang, J. M. Ng, and Y. H. Ang, "Efficient load-balanced clustering algorithms for wireless sensor networks," Computer Communications, Vol.31, No.4, pp.750-759, 2008.

상세보기
P. Kuila and P. K. Jana, "Improved load balanced clustering algorithm for wireless sensor networks," Advanced Computing, Networking and Security, Springer Berlin Heidelberg, pp.399-404, 2012.
J. H. Lee, B. K. Kim, and S. H. Kang, "Energy Effective Load Balanced Clustering Model for Wireless Sensor Networks," The 2015 Fall Conference of the KIPS, Vol.2, No.22, pp.379-382, 2015.
W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," Wireless Communications, IEEE Transactions on, Vol.1, Issue.4, pp.660-670, 2002.

상세보기
S. Lindsey and C. S. Raghavendra, "PEGASIS: Power-efficient gathering in sensor information systems," Aerospace Conference Proceedings IEEE, Vol.3, pp.3-1125-3-1130, 2002.
O. Younis and S. Fahmy, "HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks," Mobile Computing, IEEE Transactions on, Vol.3, Issue.4, pp.366-379, 2004.

상세보기
A. Manjeshwar and D. P. Agrawal, "TEEN: a routing protocol for enhanced efficiency in wireless sensor networks," IEEE, pp.2009-2015, 2001.
V. Loscri, G. Morabito, and S. Marano, "A two-levels hierarchy for low-energy adaptive clustering hierarchy (TL-LEACH)," IEEE Vehicular Technology Conference, pp.1809-1813, 2005.
P. Kuila and P. K. Jana, "Energy efficient load-balanced clustering algorithm for wireless sensor networks," Procedia Technology, Vol.6, pp.771-777, 2012.

상세보기
P. Kuila, S. K. Gupta, and P. K. Jana, "A novel evolutionary approach for load balanced clustering problem for wireless sensor networks," Swarm and Evolutionary Computation, Vol.12, pp.48-56, 2013.

상세보기
J. Hromkovic, "Algorithmics for Hard Problems," 2nd ed., Springer, 2004.

저자의 다른 논문 :

LOADING...

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

연합인증