[논문]무선 센서 네트워크에서 균등한 클러스터 밀도를 고려한 토큰 기반의 클러스터링 알고리즘

이현석; 허정석

doi:10.3745/kipstc.2010.17c.3.291

무선 센서 네트워크에서 균등한 클러스터 밀도를 고려한 토큰 기반의 클러스터링 알고리즘
A Token Based Clustering Algorithm Considering Uniform Density Cluster in Wireless Sensor Networks 원문보기

정보처리학회논문지. The KIPS transactions. Part C Part C, v.17C no.3, 2010년, pp.291 - 298

이현석 (울산대학교 컴퓨터정보통신공학부) , 허정석 (울산대학교 컴퓨터정보통신공학부)

초록
AI-Helper

무선 센서 네트워크에서 센서노드의 수명은 배터리에 의해 제한되므로 에너지는 가장 중요한 고려사항이다. 클러스터링은 네트워크의 에너지 소비를 효율적으로 관리하는데 사용되는 방법 중 하나이며, LEACH는 대표적인 클러스터링 알고리즘이다. LEACH는 센서 노드들의 에너지 소비를 공평하게 분산시키기 위해 에너지 소모적 기능을 하는 클러스터 헤드를 매 라운드마다 무작위로 순환시키는 방법을 사용하고 있다. 클러스터 헤드의 무작위 선정은 매 라운드 최적의 클러스터 헤드 수를 보장해주지 못한다. 그리고 밀도가 높은 클러스터에 위치한 클러스터 헤드는 과부하 상태가 된다. 본 논문에서는 클러스터 헤드의 수를 보장하기 위한 토큰 기반의 클러스터 헤드 선정 알고리즘과 균등한 밀도의 클러스터 형성을 위한 클러스터 선택 알고리즘을 제안한다. 시뮬레이션을 통하여 제안하는 알고리즘이 LEACH 보다 네트워크 수명이 9.3%정도 연장됨을 보여주었다.

Abstract ▼ AI-Helper

In wireless sensor networks, energy is the most important consideration because the lifetime of the sensor node is limited by battery. The clustering is the one of methods used to manage network energy consumption efficiently and LEACH(Low-Energy Adaptive Clustering Hierarchy) is one of the most famous clustering algorithms. LEACH utilizes randomized rotation of cluster-head to evenly distribute the energy load among the sensor nodes in the network. The random selection method of cluster-head does not guarantee the number of cluster-heads produced in each round to be equal to expected optimal value. And, the cluster head in a high-density cluster has an overload condition. In this paper, we proposed both a token based cluster-head selection algorithm for guarantee the number of cluster-heads and a cluster selection algorithm for uniform-density cluster. Through simulation, it is shown that the proposed algorithm improve the network lifetime about 9.3% better than LEACH.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 불균등한 밀도를 가진 네트워크 환경에서 노드의 균형적인 에너지 소모를 유도하여 전체 네트워크의 수명을 연장하였고 이를 시뮬레이션을 통해 검증하였다.
본 논문에서는 불균등한 밀도를 가진 네트워크 환경에서도 각 클러스터 헤드의 에너지 사용 공평성을 보장하기 위해서 클러스터 헤드 선택시 파라미터로 수신신호세기(RSSI) 뿐만 아니라 클러스터 멤버 노드의 수를 이용하여 클러스터 헤드를 선택하는 알고리즘을 제안한다.
본 논문에서는 클러스터 헤드 토큰을 기반으로 하는 에너지 효율적인 클러스터 헤드 선정 알고리즘과 클러스터의 밀도의 균등성을 보장하는 클러스터 선택 알고리즘을 제안하였다.
본 논문에서는 클러스터 헤드 토큰을 사용하여 최적의 클러스터 헤드 수를 보장하는 클러스터 헤드 선정 알고리즘과 과밀도 환경에서 각 클러스터의 평균 밀도를 균등하게 하여 네트워크의 수명을 연장하는 일반 노드의 클러스터 선택 알고리즘을 제안한다.
본 논문에서는 클러스터 헤드 토큰을 이용하여 최적의 클러스터 헤드 수를 보장하고 매 라운드마다 클러스터 헤드 선정으로 소모되는 에너지를 줄이기 위한 클러스터 헤드 선정 알고리즘과 불균등한 밀도를 가진 네트워크 환경에서 클러스터 헤드의 에너지 균등성을 보장하기 위한 클러스터 헤드 선택 알고리즘을 제안한다.
본 논문의 클러스터 헤드 선정 알고리즘은 클러스터 헤드의 수를 보장하기 위해 토큰을 사용하고, 클러스터 헤드의 변경을 최소화하여 에너지 효율성을 높이고자 한다.
최적의 클러스터 헤드의 수를 보장하기 위해 본 논문에서는 클러스터 헤드 토큰의 사용을 제안하였다. (그림 10)은 확률에 의해 무작위로 선택되어지는 LEACH와 토큰을 사용하는 Token 모델의 50 라운드 동안 선택되어진 클러스터 헤드의 수를 나타내고 있다.

가설 설정

클러스터 헤드의 수는 기존 연구 결과에서 평균적으로 5%의 클러스터 헤드를 가지는 것이 가장 효율적이기 때문이다. 또한 노드의 이동성은 없는 것으로 가정하고, 데이터 전송시 에러는 고려하지 않았다.

제안 방법

이를 보완하기 위해 퍼지 이론을 이용한 CHEF(Cluster Head Election mechanism using Fuzzy logic)[13], NECHS (eNergy-Efficient Cluster Head Selection)[14] 등의 클러스터 헤드 선정 알고리즘이 제안되었다. CHEF는 퍼지변수로 energy와 Local Distance를 사용하여 클러스터 헤드로 선정될 기회 chance를 계산하여 최적의 클러스터 헤드가 선정되도록 하였으며, NECHS는 CHEF를 보완하여 퍼지 변수로 energy와 node number를 이용하여 최적의 클러스터 헤드를 선정하였다.
④ 선정된 클러스터 헤드는 멤버 테이블을 초기화하고 다음 라운드의 set-up 단계에서 클러스터 멤버의 수에 대한 정보를 포함한 Advertisement 메시지를 브로드 캐스팅하고, 클러스터 변경이 일어나지 않은 기존의 클러스터 헤드는 멤버 테이블을 유지하고 Advertisement 메시지를 브로드 캐스팅한다.
먼저 과밀도의 클러스터에 속한 클러스터헤드의 과부하를 방지하기 위한 일반 노드의 클러스터 선택 알고리즘의 성능 평가를 위해 각 모델의 클러스터의 멤버 노드 수를 비교하였다. (그림 11)은 라운드별 각 클러스터의 멤버노드 수를 가지고 표준편차를 구한 값이며 표준편차가 작을수록 균등한 밀도를 가진 클러스터를 형성했음을 나타낸다.
새로운 라운드가 시작되면 각 노드들은 0과 1사이의 난수를 선택하고, 수식 1에 따라 threshold T(n)를 계산하여 두 수를 비교한다, 난수 값이 threshold T(n)보다 작으면 클러스터 헤드로 선정되고, 난수 값이 threshold T(n)보다 크거나 같으면 클러스터 멤버가 된다. 선정된 모든 클러스터 헤드들은 동일한 전송 에너지로 CSMA MAC 프로토콜을 사용하여 advertisement 메시지를 브로드캐스트 한다. 이 메시지를 받은 노드들은 수신된 신호의 세기(RSSI)가 가장 큰 노드를 자신의 클러스터 헤드로 선택하고 Join-REQ 메시지를 선택한 클러스터 헤드로 전송한다.
시뮬레이션은 NS-2.27에 MIT의 NS2-LEACH 패키지를 변형하여 사용하였으며, 시뮬레이션 환경과 에너지 모델은와 같다.
LEACH의 확률에 의한 클러스터 헤드 선정 알고리즘은 클러스터 헤드의 최적의 분포와 충분한 에너지를 보장하지 못한다. 이를 보완하기 위해 퍼지 이론을 이용한 CHEF(Cluster Head Election mechanism using Fuzzy logic)[13], NECHS (eNergy-Efficient Cluster Head Selection)[14] 등의 클러스터 헤드 선정 알고리즘이 제안되었다. CHEF는 퍼지변수로 energy와 Local Distance를 사용하여 클러스터 헤드로 선정될 기회 chance를 계산하여 최적의 클러스터 헤드가 선정되도록 하였으며, NECHS는 CHEF를 보완하여 퍼지 변수로 energy와 node number를 이용하여 최적의 클러스터 헤드를 선정하였다.
제안 알고리즘의 성능을 비교 평가하기 위해 과 같이 3가지 모델을 시뮬레이션 하였다.
제안하는 알고리즘은 매 라운드마다 클러스터 헤드 변경이 이루어지지 않고 에너지를 많이 소모한 클러스터 헤드만을 변경하게 되며, 일반 노드의 클러스터 선택은 매 라운드 발생할 수 있다.
최적의 클러스터 헤드 분포를 위한 확률 p는 시뮬레이션을 통하여 최적의 값을 구하였다.
클러스터 헤드가 최적의 분포를 가지는 확률 p를 구하기 위해 센서 노드를 (그림 6)과 같이 격자 형태로 균등하게 배치하고, 클러스터 헤드를 5개로 설정하고 CH-Token 메시지 5개를 전송하였다.
싱크노드는 각 라운드의 시작 단계인 set-up 단계에서 각 노드에 대한 위치정보와 에너지 보유량에 대한 정보를 전송받아 네트워크 전체 노드들의 평균 에너지를 계산한다. 평균 에너지보다 낮은 에너지를 보유한 노드는 클러스터 헤드 선정에서 제외되며, 평균보다 높은 에너지를 보유한 노드들 중에서 simulated annealing algorithm[12]을 이용하여 클러스터 헤드를 선정하여 이를 메시지를 전송하여 알린다. LEACH-C는 클러스터 멤버 노드들이 클러스터 헤드에게 데이터를 전송하는데 있어서 에너지를 최소화하는 최적의 클러스터 헤드를 선정함으로써 효율적인 클러스터를 구성할 수 있지만 이러한 최적의 클러스터 헤드를 선정하기 위한 오버헤드가 큰 것이 문제점이다.
제안 알고리즘의 성능을 비교 평가하기 위해 <표 3>과 같이 3가지 모델을 시뮬레이션 하였다. 확률에 의해 클러스터 헤드를 선택하고 RSSI를 이용해 클러스터를 결정하는 LEACH 모델과 LEACH와 동일하나 클러스터 헤드 선택 시 제안한 클러스터 헤드 토큰을 사용하는 Token 모델, 그리고 클러스터 헤드 토큰과 adjustRSSI 둘 다 사용하고 클러스터 내에서만 클러스터 헤드 변경이 이루어지는 Token-adjustRSSI 모델의 성능을 비교 평가하였다.

대상 데이터

센서 네트워크의 크기는 100×100m, 센서 노드의 개수는 100개, 클러스터 헤드는 5개로 설정하였다.

성능/효과

LEACH 모델은 매 라운드 마다 무작위로 새로운 클러스터 헤드를 형성하고 일반노드는 수신신호세기에 따라서 클러스터를 선택하게 되어 클러스터내의 밀도가 평균 표준편차 9.87로 불균등한 것을 볼 수 있으며, Token 모델은 클러스터 헤드의 수만을 보장하므로 평균 표준편차 7.63으로 LEACH 모델에 비해 균등함을 보여준다. Token-adjustRSSI 모델은 클러스터 내에서만 클러스터 헤드를 변경하고 수신 신호세기와 클러스터 멤버노드의 수에 따라 클러스터를 결정하므로 클러스터내의 밀도가 평균 표준편차 4.
LEACH 모델은 확률에 의해 무작위로 클러스터 헤드가 선정되어 지므로 최적의 클러스터 헤드 수를 보장해주지 못하고 있으며, Token 모델은 클러스터 헤드 토큰을 사용하여 최적의 클러스터 헤드 수를 보장해 주고 있음을 알 수 있다.
매 라운드 클러스터 형성을 위한 set-up 과정에서 발생하는 제어 메시지수의 평균을 보면 LEACH 모델이 75.8개, Token 모델이 83.1개이며 Token-adjustRSSI 모델에서는 38.2개로 다른 방식보다 에너지 효율적임을 나타내고 있다. Token 모델은 최적의 클러스터 헤드의 수를 보장하여 LEACH 모델보다 균등한 밀도를 가지지만 매 라운드 클러스터 헤드 선정을 위해 사용되는 제어 메시지의 증가와 라운드 후반 전체 노드의 수가 감소되었음에도 불구하고 클러스터 헤드의 수는 5를 유지함으로써 에너지 효율성이 뛰어나지 못했다.
(그림 7)은 확률 p의 변화에 따른 클러스터 소모 에너지의 표준편차를 보여주고 있다. 시뮬레이션 결과 확률 p가 0.20 이었을 때 표준 편차가 가장 작으므로 최적의 클러스터 헤드 분포를 가지게 됨을 알 수 있다.
제안 알고리즘은 과밀도의 네트워크 환경에서 클러스터 헤드의 과부하를 줄이고, 클러스터 형성을 위한 set-up 과정에서 오버헤드를 감소시켜 LEACH 모델보다 균등한 에너지 소모를 하고 있으며, 이를 통해 네트워크 수명에서도 약 9.3% 정도의 향상을 보여주었다.
제안하는 알고리즘에서는 클러스터 헤드 변경이 일어나지 않고 일반 노드의 클러스터 변경도 일어나지 않으면 C-Join 메시지를 전송하지 않으므로 set-up 과정에서 소모되는 에너지를 절약할 수 있다.
확률 p는 0～1의 범위를 가지며 0.05 단위로 증가하여 측정하였으며, 최적의 클러스터 헤드 분포를 측정하기 위한 값으로 클러스터 형성후 1라운드 동안 각 클러스터의 소모 에너지를 측정하여 표준편차가 작을수록 최적의 클러스터 분포를 가진다고 보았다.

후속연구

그러나 토큰을 사용하는 모델은 라운드 초기 클러스터 헤드의 최적의 수를 보장해주지만 라운드 후반 전체 노드의 수가 감소함에 따른 최적의 클러스터 헤드 수 재설정과 토큰의 재분배 등 추가 연구가 필요함을 보여주었다.
무선 센서 네트워크에서 에너지 효율성은 중요한 네트워크 설계 기준이며 향후 에너지 효율적인 라우팅 프로토콜뿐만 아니라 무선 환경에서 발생하는 링크에러에 따른 재전송시 소모되는 에너지를 줄이기 위한 트랜스포트 프로토콜의 개발이 필요하다.

질의응답

핵심어	질문	논문에서 추출한 답변
	무선 센서 네트워크의 라우팅 프로토콜은 무엇으로 분류되는가?	무선 센서 네트워크의 라우팅 프로토콜은 네트워크 구조에 의해 크게 모든 노드가 동등한 입장에서 공통된 하나의 라우팅 기법을 사용하는 SPIN(Sensor Protocols for Information via Negotiation)[5], Directed Diffusion[6]등의 평면 기반 라우팅, 센서 노드의 위치 정보를 기반으로 라우팅 경로를 설정하는 GAF(Geographic Adaptive Fidelity)[7], GEAR(Geographic and Energy Aware Routing)[8]등의 위치기반 라우팅 그리고 클러스터링을 기반으로 노드 간의 계층적 단계를 두어 데이터를 전송하는 LEACH(Low-Energy Adaptive Clustering Hierarchy)[9], TEEN(Threshold-sensitive Energy Efficient Protocols)[11]등의 계층기반 라우팅으로 분류된다.
	LEACH란 무엇인가?	LEACH(Low-Energy Adaptive Clustering Hierarchy)[9]는 클러스터링 기반 라우팅 기법으로, 클러스터헤드가 클러스터의 멤버 노드들로부터 데이터를 전송 받아 데이터 병합(data aggregation)을 통해 데이터를 싱크노드로 전달하여 전체적인 통신비용을 줄인다. 그리고 네트워크를 구성하는 모든 노드들의 에너지 소모를 공정하게 분산시키기 위해 에너지 집약적인 기능을 하는 클러스터 헤드를 라운드(round)라는 시간 단위마다 무작위로 순환시켜 네트워크의 생존시간을 최대화한다.
	LEACH는 네트워크를 구성하는 모든 노드들의 에너지 소모를 공정하게 분산시키기 위해 무엇을 하는가?	LEACH(Low-Energy Adaptive Clustering Hierarchy)[9]는 클러스터링 기반 라우팅 기법으로, 클러스터헤드가 클러스터의 멤버 노드들로부터 데이터를 전송 받아 데이터 병합(data aggregation)을 통해 데이터를 싱크노드로 전달하여 전체적인 통신비용을 줄인다. 그리고 네트워크를 구성하는 모든 노드들의 에너지 소모를 공정하게 분산시키기 위해 에너지 집약적인 기능을 하는 클러스터 헤드를 라운드(round)라는 시간 단위마다 무작위로 순환시켜 네트워크의 생존시간을 최대화한다.

참고문헌 (16)

J. N. Al-Karaki, A. E. Karnal, 'Routing Techniques in wireless sensor networks : A Survey,' Wireless Communications, IEEE, Vol.11, No.6, pp.6-28, 2004.

상세보기
I. F. Akyldiz, W. Su, Y. Sankarusubramaniam, and E. Cyirci, ‘Wireless sensors networks: a survey,’ Computer Networks, Vol.38, No.4, pp.393-422, Aug., 2002.

상세보기
K. Akkaya, M. Younis, ‘A survey on routing protocols for wireless sensor networks,’ Ad Hoc Networks, Vol.3, No.3, pp.325-349, 2005.

상세보기
S. Bandyopadhyay and E. Coyle, 'An energy efficient hierarchical clustering algorithm for Wireless Sensor Networks,' in Proc. of INFOCOM 2003, vol. 3, pp.1713-1723, 2003.
J. Kulik, W. R. Heinzelman, and H. Balakrishnan, ‘Negotiation-based protocols for disseminating information in wireless sensor networks,’ Wireless Networks, Vol.8, pp.169-185, 2002.

상세보기
C. Intanagonwiwat, R. Govindan, and D. Estrin, 'Directed diffusion: a scalable and robust communication paradigm for sensor networks,' Proceedings of ACM MobiCom '00, Boston, MA, pp.56-67, 2000.
Y. Xu, J. Heidemann, D. Estrin, 'Geography-informed Energy Conservation for Ad-hoc Routing,' In Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp.70-84, 2001.
Y. Yu, D. Estrin, and R. Govindan, ‘Geographical and Energy-Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks,’ UCLA Computer Science Department Technical Report, UCLA-CSD TR-01-0023, May 2001.
W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, ‘Energy-Efficient Communication Protocol for Wireless Microsensor Networks,’ Proceedings of HICSS, pp.3005-3014, Jan. 2000.
W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, ‘An Application-Specific Protocol Architecture for Wireless Microsensor Networks,’ IEEE Transactions on Wireless Communications, Vol.1, No.4, pp.660-670, Oct., 2002.

상세보기
A. Manjeshwar and D. P. Agarwal, 'TEEN: a routing protocol for enhanced efficiency in wireless sensor networks,' In 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, April, 2001.
T. Murata and H. Ishibuchi, 'Performance evaluation of genetic algorithm for flowshop scheduling problems,' Proc. 1st IEEE Conf. Evolutionary Computation, Vol.2, pp.812-817, June, 1994.
J.M. Kim, S.H. Park, Y.J. Han and T.M. Chung, ‘CHEF: Cluster Head Election mechanism using Fuzzy logic in Wireless Sensor Networks,’ Advanced Communication Technology, pp.654-659, 2008.
Yu Hu, Xiaorui Shen, Zhenhua Kang, 'Energy-Efficient Cluster Head Selection in Clustering Routing for Wireless Sensor Networks,' WiCom '09. 5th International Conference on Networking and Mobile Computing, Digital Object Identifier 10.1109/WICOM.2009.5303808, 2009.
J.M. Hong, J.J. Kook, S.J. Lee, D.S. Kwon, S.H. Yi, ‘T-LEACH: The method of threshold-based cluster head replacement for wireless sensor networks,’ Information Systems Frontiers, Vol.11, No.5, pp.513-521, 2009.

상세보기
Z.G. Sun, Z.W. Zheng, S.J. Xu, 'An Efficient Routing Protocol Based on Two Step Cluster Head Selection for Wireless Sensor Networks,' WiCom '09. 5th International Conference on Networking and Mobile Computing, Digital Object Identifier 10.1109/WICOM.2009.5303948, 2009.

저자의 다른 논문 :

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

연합인증