무선 멀티미디어 센서 네트워크의 서비스 수명을 위한 클러스터 라우팅
이종득*
전북대학교 전자공학부*
Cluster Routing for Service Lifetime of Wireless Multimedia Sensor Networks
Chongdeuk Lee*
Division of Electronic Engineering, Chonbuk National University*
요 약 본 논문에서는 무선 멀티미디어 센서 네트워크의 서비스 수명 보장을 위해 클러스터 기반의 새로운 라우팅 프로토콜을 제안한다. 제안된 프로토콜은 무선 센서 멀티미디어 컴퓨팅 환경에서 에너지 소모를 줄이고 서비스 오류를 줄이기 위해 인트라 클러스터 라우팅과 인터 클러스터 라우팅을 수행한다. 또한 제안된 클러스터 라우팅은 라우팅 신 뢰성을 향상시키고, 패킷 손실을 최소화하며, 관리 오버헤드를 최소화하고, 에너지 소모를 최소화한다. 본 논문에서는 시뮬레이션 결과를 통해서 제안된 기법이 DSR (Dynamic Source Routing) 기법, AODV(Adhoc On-demand Distance Vector routing) 기법에 비해서 효율성이 우수함을 보인다.
주제어 : 센서 네트워크, 서비스 수명, 인트라 클러스터, 인터 클러스터, 클러스터 라우팅
Abstract This paper proposes a new cluster-based routing protocol for assuring the service lifetime of wireless multimedia sensor networks. The proposed protocol performs the intra-cluster routing and inter-cluster routing to reduce the energy consumption and service lifetime in the wireless sensor multimedia computing environment, and the proposed mechanism enhances the routing reliability, and it minimizes the packet loss, overhead, and energy consumption. The simulation results show that the proposed mechanism outperforms DSR and AODV.
Key Words : Sensor Network, Service Lifetime, Intra Cluster, Inter cluster, Cluster Routing
Received 9 April 2013, Revised 29 April 2013 Accepted 20 May 2013
Corresponding Author: Chong-Deuk Lee(Chonbuk National University)
Email: [email protected]
Ⓒ The Society of Digital Policy & Management.
All rights reserved. This is an open-access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.otg/licenses/by-nc/3.0), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
ISSN: 1738-1916
1. 서론
최근에 무선 멀티미디어 센서 컴퓨팅 환경에서 강력 한 처리 기능과 서비스 수명 연장을 위해 다양한 클러스
터 라우팅 기법들이 제안되고 있다[1, 2, 3].
센서 네트워크 환경에서 센서 노드들은 네트워킹을 수 행하기 위하여 서로 상호 협력하며, 네트워킹을 통해서 언제, 어디에서든지 주변 정보들을 상호 접근하게 된다.
또한 싱크 노드는 일반 센서 노드들로부터 전송된 메 시지를 수집하여 모바일 하드웨어 장치를 사용하는 사용 자들에게 정보를 전송하는 역할을 수행한다.
무선 멀티미디어 센서 네트워크 환경에서 메시지들이 성공적으로 수집되면 싱크 노드들은 통신 채널을 통해서 관리자들에게 실제 데이터를 처리하고 전송한다.
일반적으로 클러스터 라우팅을 위한 라우팅 프로토콜 들은 주문형 프로토콜, 테이블 지향 프로토콜, 그리고 하 이브리드 지향 프로토콜로 구성되어 있다[4, 5].
주문형 라우팅 프로토콜에서 라우팅 식별은 소스 노 드에 의해 수행되며, 이때 라우팅 식별을 위한 목적지 주 소는 제공되지 않는다. 이 기법은 라우팅 경로를 발견하 기 위하여 비교적 적은 대역폭을 이용하고, 네트워크 오 버헤드를 최소화하고 있지만 단말 간 평균 지연이 비교 적 높게 발생하는 문제점을 가지고 있다[6].
이와는 반대로 테이블-지향의 라우팅 프로토콜은 라 우팅 경로가 발견될 때 네트워크가 사용되지 않더라도 가끔씩 라우팅 테이블을 유지한다. 이 프로토콜은 라우 팅 경로 발견에 따른 지연은 낮지만 새로운 노드 또는 호 단절이 발생하면 많은 제어 패킷들로 인하여 높은 네트 워크 오버헤드가 발생한다. 또한 테이블 지향 라우팅 프 로토콜은 라우팅 테이블을 유지하기 위해 보다 많은 대 역폭을 소모하게 된다. 하이브리드 지향 프로토콜은 주 문형 라우팅 프로토콜과 테이블 지향의 라우팅 프로토콜 을 혼합한 라우팅 프로토콜이다. 이 프로토콜은 단말 간 평균 지연을 해결하고 호 단절 문제를 개선하였지만 클 러스터들 간의 특성을 반영하지 않아 서비스 성능과 네 트워크 성능이 떨어지는 문제가 발생하고 있다.
이러한 문제를 해결하기 위하여 AODV와 DSR과 같 은 라우팅 프로토콜들이 제안되었다[4, 5]. 그러나 이들 프로토콜들 또한 채널 오류와 네트워크 오류 등으로 인 하여 에너지 소모를 가중시키고, 라우팅 혼잡이 발생하 는 문제가 발생하고 있다[7, 8].
이러한 문제를 해결하기 위하여 본 논문에서는 퍼지 논리 기반의 새로운 클러스터 라우팅 프로토콜을 제안한 다. 제안된 클러스터 라우팅 프로토콜은 플러딩 범위 (flooding scope)안에서 퍼지 논리에 따라 라우팅 정보를 교환하는 기능을 수행한다. 따라서 제안된 클러스터 라 우팅 프로토콜은 대역폭 제약에 따른 네트워크 오버헤드 를 줄이고, 또한 에너지 소모를 줄인다. 이와 같은 장점으 로 인하여 제안된 프로토콜은 무선 멀티미디어 센서 네
트워크의 응용분야에 폭넓게 적용될 것으로 예상된다.
본 논문의 구성은 다음과 같다. 2장에서는 관련 연구에 대해서 살펴보며, 3장에서는 제안된 클러스터 기반의 라 우팅 프로토콜에 대해서 살펴본다. 그리고 4장에서는 시 뮬레이션 결과에 대해서 기술하며, 끝으로 결론에 대해 서 살펴본다.
2. 관련 연구
무선 멀티미디어 센서 네트워크에서 클러스터 라우팅 은 중요한 이슈이다. 라우팅 전송 범위 안에 없는 노드들 은 릴레이 노드로 사용되는 중간 노드들을 통하여 서로 통신을 수행한다. 라우팅은 소스 노드와 목적지 노드 사 이의 경로를 구축하는 과정이며, 최근에 서비스 수명을 극대화하기 위해 많은 클러스터 라우팅 프로토콜들이 제 안되고 있다[1, 6, 9].
무선 멀티미디어 센서 네트워크에서 클러스터 라우팅 을 위해서는 확장성, 데이터 수집, 이동성, 낮은 복잡도, 에너지 효율성, 고장 허용, 그리고 다중 경로 등의 기능이 고려되어야 한다. 이러한 기능을 제공하기 Bai at el. [8]
은 DSR(Dynamic Source Routing) 프로토콜을 제안하였 다. DSR 프로토콜은 대표적인 주문형 라우팅 프로토콜 로서 기존의 다른 네트워크의 기반 시설 없이도 스스로 네트워크를 자가 구성하는 기능을 가지고 있다. 그러나 이 프로토콜은 라우트의 갱신이 빈번하게 발생하면 라우 팅 패킷 오버헤드가 크게 발생하는 문제점을 가지고 있 다. AODV[5] 프로토콜은 인접 노드가 한 개 이상일 때 비콘 패킷을 전달하는 기법으로서 분산 경로 상에 많은 노드가 존재할 경우 라우팅 혼잡이 가중되는 문제점을 가지고 있다. Jiang at el. [9]는 Lowest-ID 기반의 1-hop 클러스터 라우팅 프로토콜을 제안하였으며, 이 프로토콜 은 노드의 ID, 클러스터의 역할 그리고 노드에 대한 링크 상태 등의 노드정보를 사용하여 클러스터 라우팅을 수행 한다. 그러나 이 프로토콜은 모바일 애드 혹 네트워크의 크기가 확장되거나 이동성이 증가할 때 많은 클러스터헤 드가 생성되는 문제점을 가지고 있다. Basu at el. [10]은 이웃노드들의 에너지를 측정하여 클러스터링을 구성하 기 위하여 MOBIC 클러스터링 프로토콜을 제안하였다.
이 프로토콜은 노드의 신호강도에 따라 클러스터헤드를 선정하는 기법으로서 신호강도에 따른 클러스터 라우팅
이 어렵다는 문제를 가지고 있다. 그리고 Kadri at el.
[11]은 믿음값(trust value)에 기반한 SCA(Secured Clustering Algorithm)을 제안하였다. 이 알고리즘은 믿 음 값에 의해서 1-hop 및 2-hop의 클러스터 문제가 부분 적으로 개선되었으나 노드의 규모가 커질 때 적응성의 저하로 서비스 수명이 줄어들고 에너지 낭비가 심하게 발생하는 문제점을 가지고 있다[12]. 따라서 이들 프로토 콜은 네트워크 크기가 가변적이고, 이동성이 증가할 때 라우팅 성능과 서비스 신뢰성이 떨어지는 문제점이 발생 한다.
3. 클러스터 라우팅 프로토콜
이 장에서는 무선 멀티미디어 센서 네트워크의 서비 스 수명을 극대화하기 위해 클러스터 라우팅 전략과 라 우팅 프로토콜을 기술하며, 클러스터 라우팅을 위해 다 음을 가정한다.
∙모든 센서 노드들이 일단 배치된 후에는 센서 노드 들은 초기 위치에 고정되어 있다.
∙모든 센서 노드들은 제한된 에너지를 가지고 있다.
∙센서 네트워크는 클러스터링 기법에 따라 클러스터 들을 구성하며, 모든 노드들은 그 자신의 클러스터 를 결정하기 위해 고유한 식별자를 가진다.
3.1 클러스터 라우팅 전략
클러스터 라우팅 전략에서 노드들은 서로 라우팅 정 보를 교환한다. 자신의 테이블 정보가 변경되면 클러스 터 안의 노드는 그 자신의 이웃 노드들에게 자신의 테이 블 정보를 브로드캐스트 한다. 각각의 노드는 그 자신의 클러스터 안에서 목적지, 다음 홉, 목적지 노드의 클러스 터 id, 홉 수, 시퀀스 넘버, 그리고 퍼지 중요도 등 다른 노 드들의 라우팅 정보를 유지한다. 또한 각 인접 클러스터 에 있는 경계 노드들의 정보는 로컬 라우팅 테이블에 추 가되며, 이 경우 인접한 클러스터로의 라우팅이 가능해진 다. 각 노드의 라우팅 테이블은 퍼지 중요도 정보와 홉 수 정보를 가지고 있다. 퍼지 중요도는 에너지 소모와 온도, 조도, 습도, 압력, 소음 수준 등과 같은 여러 파라미터들을 고려하여 결정한다[6]. 그림1은 라우팅과 서비스 관계에 따른 클러스터 라우팅의 예를 보여주고 있으며, 여기서 노드들 간의 에지는 퍼지 중요도를 나타내고 있다.
[Fig. 1]에 의해 클러스터 라우트가 발견되며, 클러스 터 라우트는 클러스터 테이블 정보를 구축하게 된다. 구 축된 테이블 정보는 클러스터와 클러스터 간, 그리고 클 러스터 내에서의 노드들에게 라우팅 경로, 퍼지 중요도 그리고 홉 수 정보를 RREQ 패킷에 첨부하여 전송한다.
이러한 라우팅 정보는 그림2와 같이 라우트 발견을 선택 하는데 이용되며, 퍼지 중요도는 클러스터 라우팅이 유 지되는 동안 라우팅 경로 길이를 최소화하는데 적용된다.
[Fig. 1] Routing and Service Relation
[Fig. 2] Routing Discovery
3.2 인터-클러스터 라우팅 프로토콜
인터-클러스터 라우팅 프로토콜은 클러스터 라우팅에 서 클러스터스와 클러스터 간의 라우팅 적합도이다. 인 터-클러스터 라우팅 프로토콜은 클러스터의 트래픽과 버스트 동기화에 의해 결정되며 트래픽의 크기는 캐시 용량을 초과해서는 안 된다. 만일 트래픽의 크기가 캐시 용량을 초과하면 인코딩율과 디코딩율의 불균형으로 인
하여 지터 지연이 발생한다. 따라서 본 논문에서는 이러 한 문제를 해결하기 위하여 라우팅 적합도 모니터링 기 법을 이용한다. 이 기법은 퍼지 중요도[6]을 이용하여 클 러스터들 간의 라우팅 적합도를 판단하며, 클러스터 에 대한 라우팅 적합도는 다음과 같이 정의한다.
정의1. ={ ≥ , ∈, ∈이다.
여기서 만일 ∈이면, a(x)= ≠ 로 표현된
다. 우리는 퍼지수가 정규이고, 적합도가 매우 큰 상의 퍼지부분집합을 ∃←,
=1로 표현한다.
이것은 상의 퍼지집합의 소속 값(membership value) 의 최대값이 1임을 의미하며, 이는 적합도가 매우 높음을 의미한다. 적합도는 =[, ]의 성질을 만족해 야 하며, 다음과 같은 포함관계를 만족해야 한다.
정의2. (´<)⇒( ′ ≤ , ′ ≥)이면, (′〈 )⇒( A⊂ A′)이다.
3.3 인트라-클러스터 라우팅 프로토콜 인트라-클러스터 라우팅 프로토콜은 클러스터 내의 미디어 트래픽이 싱크 노드의 캐시 용량을 초과할 때 라 우팅과 싱크 노드의 서비스관계를 최적화하기 위한 프로 토콜이다. 클러스터 내에서의 라우팅은 퍼지 적합도에 의해 좌우되며, 퍼지적합도가 낮을수록 지터지연에 의한 서비스 수명은 낮아지게 된다. 이러한 문제를 해결하기 위해 클러스터 내에서의 라우트들에 대한 퍼지 적합도가 적용되며, 클러스터 내에서의 라우팅 적합도는 다음과 같이 정의한다.
정의3. 클러스터 라우팅 A에 대하여 = { ≥ }이다.
여기서 의 값이 작을수록 라우팅 적합도는 낮게 되 며, 의 값이 클수록 라우팅 적합도는 향상된다. 이것은 결과적으로 라우팅 적합도에 따라 라우팅 서비스가 정렬 됨을 의미하며, 정렬된 라우팅 서비스는 센서 노드들의 서비스 수명을 극대화하게 된다.
예를 들어 클러스터 상에서 노드들 간의 라우팅 적 합도을 가정하자.
라우팅 적합도에서 보듯이 ≥0.2일 때는 {,
,,,,}로의 라우팅 적합도가 구성되며, 이때 는 서비스 수명이 매우 낮음을 의미한다. 그러나 만일
≥0.8이면, 에서 보듯이 라우팅 관계는 {,}, {, }, 그리고 {, }로 라우팅이 구성되게 된다.
따라서 ≥0.6, ≥0.8, ≥1.0으로 증가할 때는 라 우팅 관계가 보다 명료해지며, 이로 인해 서비스 수명과 라우팅이 최적화되게 된다.
4. 시뮬레이션 분석
4.1 시뮬레이션 환경
이 절에서는 시뮬레이션을 위해 네트워크 크기를 500m×500m로 제한하였으며, 라우팅 센서 노드는 100개 를 배치하였다. 각각의 데이터 패킷 크기는 64kbyte로 설 정 하였으며, 질의 패킷과 다른 패킷들은 36kbyte로 설정 하였다. 소스 노드는 초 당 한 개의 데이터 패킷을 생성 하도록 하였으며, 시뮬레이션 시간은 550s로 설정하였다.
노드들에 대한 에너지 소모는 각각 전송 시에는 660mW, 수신시에는 359mW, 그리고 데이터를 송수신하지 않고 정지되었을 때는 35mW가 소모되도록 하였다. 시스템 성 능 척도는 평균 지연율, 처리율, 그리고 시스템 수명 시간 으로 구분하여 평가하였다.
4.2 시뮬레이션 결과 4.2.1 평균 지연율
제안된 기법과 비교할 때 DSR과 AODV 기법의 라우 트 발견은 패킷 전송을 지연시킨다. 이것은 라우트 발견
에 따른 패킷 정보를 버퍼 큐에서 큐잉하기 때문이다. 따 라서 DSR과 AODV 기법의 평균 지연은 제안된 기법 보 다 높게 발생함을 알 수 있다. 제안된 기법에서는 인트라 -클러스터 라우팅 정보를 이용하여 하나의 노드에서 다 음 노드로 라우팅할 때 라우팅 적합도를 이용하기 때문 에 패킷 지연이 낮게 발생한다. 따라서 제안된 기법은 하 나의 경로 또는 센서 노드에 트래픽이 발생할 때 라우팅 경로를 빠르게 변경할 수 있는 장점을 가지며, [Fig. 3]은 클러스터 내에서 라우트들 간의 평균 지연율을 보여주고 있다. 이것은 클러스터 내에서 라우팅 적합도를 이용하 여 송신측에서 목적지 까지 패킷을 전송하는데 걸린 지 연 시간을 측정한 것이다.
[Fig. 3] Average Delay Ratio
4.2.2 처리율
[Fig. 4]는 제안된 기법, DSR 기법, 그리고 AODV 기 법에 대한 평균 처리율 결과이다. [Fig. 4]에서 보듯이 라 우팅 적합도가 낮을수록 처리율이 떨어지고 있음을 알 수 있다. 일반적으로 패킷을 전송할 때 데이터 패킷들이 집중되거나 혼잡이 발생하면 라우팅 오버헤드가 발생하 게 된다. 본 논문에서는 이러한 문제를 해결하기 위하여 클러스터 내에서 라우팅 적합도를 이용하였다. 따라서 제안된 기법은 데이터 패킷들이 집중되거나 혼잡이 발생 되어도 라우팅 적합도를 적용함으로써 처리율이 높게 나 타남을 알 수 있다. 그 결과 네트워크 크기가 증가되어도 좋은 처리율 결과를 얻을 수 있게 된다.
[Fig. 4] Average throughput
4.2.3 서비스 수명
[Fig. 5]는 네트워크상에서 노드 수명이 소멸되지 않 고 살아있는 노드의 수를 보여주고 있다. 제안된 기법은 클러스터 기법을 이용함으로서 노드들을 효과적으로 관 리하게 된다. 또한 제안된 기법은 인트라-클러스터 라우 팅 기법과 라우팅 적합도를 적용함으로서 센서 노드들에 대한 평균 에너지 소모를 줄일 수가 있으며 불필요한 에 너지 소모를 줄일 수 있다. 따라서 이것은 무선 센서 네 트워크에서 노드들에 대한 서비스 수명을 연장시키게 되 며, 이로 인하여 처리율 또한 향상되게 된다. 그림5는 시 뮬레이션 시간에 따른 노드 수명을 나타내고 있으며, 그림 에서 보듯이 제안된 기법은 DSR과 AODV 기법에 비해서 노드들의 서비스 수명이 비교적 높게 나타남을 알 수 있다.
이것은 제안된 기법의 성능이 우수함을 의미한다.
[Fig. 5] Service lifetime
5. 결론
최근에 다중 홉 멀티미디어 무선 멀티미디어 센서 네 트워크 환경에서 서비스 수명을 극대화하기 위한 많은 클러스터 라우팅 기법이 제안되었다. 본 논문에서는 멀 티 홉 라우팅 환경에서 클러스터 라우팅을 안정적으로 유지하고 서비스 수명을 극대화하기 위해 퍼지 적합도 기반의 클러스터 라우팅 프로토콜을 제안하였다. 제안된 기법은 지연율을 감소시키고, 처리율이 향상되도록 클러 스터 라우팅에 라우팅 적합도를 적용하였으며, 라우팅 적합도가 클수록 성능이 향상됨을 알 수 있었다. 또한 라 우팅과 서비스관계가 최적화되도록 라우팅을 인터 클러 스터 라우팅과 인트라 클러스터 라우팅으로 구분하였으 며, 시뮬레이션 결과 제안된 기법이 DSR, AODV 기법에 비해서 처리 성능이 효율적임을 알 수 있었다.
REFERENCES
[1] C. D. Lee, Object segment grouping for wireless mobile streaming media services. The Society of Digital Policy & management, Vol. 10, No. 4, pp.
199-206, 2012.
[2] C. D. Lee, Proxy-based caching optimization for mobile ad hoc streaming services. The Society of Digital Policy & management, Vol. 10, No. 4, pp.
207-216, 2012.
[3] C. D. Lee, Similarity-based caching replacement loss minimization in wireless mobile proxy systems.
The Journal of Korean Navigation Institute, Vol. 16, No. 3, pp. 455-462.
[4] C. D. Lee, Profit-based segment caching for wireless streaming QoS. The Journal of Korean Navigation Institute, Vol. 16, No. 3, pp. 463-470.
[5] I. F. Akyildiz, T. Melodia, K. R. Chowdhury, A survey on wireless multimedia sensor network.
Computer networks, Vol. 51, pp. 921-960, 2007.
[6] C. D. Lee, T. W. Jeong, FRCA: A fuzzy relevance- based cluster head selection algorithm for wireless mobile ad-hoc sensor networks. Sensors, Vol. 11, No. 3, pp. 1-19, 2011.
[7] M. Zarei, Reverse AODV Routing Protocol Extension
using Learning Automata in Ad hoc Networks. In Proceedings of the International Conference on Computer, Control and Communication, Karachi, Pakistan, February, pp. 1–5, 2009.
[8] R. Bai, M. Singhai, DOA: DSR over AODV Routing for Mobile Ad hoc Networks, IEEE Trans. Mobile Computing. Vol. 5, pp. 1403–1416, 2006.
[9] M. Jiang, J. Li, Y. Chiang, Cluster Based Routing Protocol(CBRP) Functional Specification. IETF Internet Draft, 1998.
[10] P. Basu, N. Khan, and T.D.C. Little, A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks. Proc. IEEE ICDCS 2001 Workshop on Wireless Networks and Mobile Computing, Phoenix, AZ, pp. 1-19, 2001.
[11] B. Kadri, A. Mohamed, M. Feham, Secured Clustering for Mobile Ad Hoc Networks. IJCSNS International Journal of Computer Science and Network Security, Vol. 7, No. 3, pp. 27-34, 2007.
[12] Y. Wang, T.Liang, X. Yang and D. Zhang, Scalable and Effective Cluster Based Routing Algorithm Using Node's Location for Mobile Ad Hoc Networks. Information Technology Journal, Vol. 7, No. 7, 958-97, 2008.
이 종 득(李鍾得)
․1983년 2월 : 전북대학교 컴퓨터과 학과(이학사)
․1989년 2월 : 전북대학교 컴퓨터과 학과(이학석사)
․1998년 2월 : 전북대학교 컴퓨터과 학과(이학박사)
․1992년 3월 ～ 2002년 2월 : 서남대 학교 컴퓨터통신학과 교수
․2002년 2월 ～ 현재 : 전북대학교 전자공학부 교수
․관심분야 : Smart Proxy System, 무선 모바일 네트워크, 무 선센서 네트워크, MIMO, 유비쿼터스 통신 등
․E-Mail : [email protected]
