Energy Efficient Epidemic Routing for Delay Tolerant Networks

Abstract

최근 지연 감내 네트워크는 기존의 무선 이동 네트워크와는 다는 특성들을 가지고 있기 때문에 많은 주목을 받고 있으며 연구가 활발히 진행되고 있다. 지연 감내 네트워크는 이동 애드혹 네트워크와 마찬가지로 PDA, 노트북 컴퓨터, 무선 센서들로 구성된다. 지연 감내 네트워크의 특성들을 살펴 보면, 노드들이 이동특성을 가지고 있고, 매우 밀도가 낮은 노드 분포, 그로 인해서 노드간 통신 링크가 지속적으로 형성되는 것이 아니고 간헐적으로 형성된다. 이런 특성들은 지연 감내 네트워크에서 매우 긴 데이터 전송지연을 유발한다. 그러므로 기존의 애드혹 네트워크에서 사용되는 AODV, DSR 등과 같은 경로설정 프로토콜들은 지연 감내 네트워크에서는 사용될 수 없다. 에피데믹 라우팅이라는 경로설정 방법이 지연 감내 네트워크에서는 많이 사용되고 있다. 그 이유는 에피데믹 라우팅은 목적지 노드까지 데이터 전송을 보장하는 특성을 가지고 있기 때문이다. 에피데믹 라우팅에서는 만약 전송할 데이터가 있는 노드가 어떤 새로운 노드를 만나게 되면, 자신이 가지고 있는 데이터를 복사한 후 그 복사본을 전달한다. 마치 병원균이 다른 것을 감염시키는 동작과 유사한 과정이 진행된다. 데이터 복사본을 받은 노드, 즉, 감염된 노드들도 같은 방식으로 새로운 노드들을 만날 때 마다 계속 감염(데이터 전달)을 진행한다. 그래서 에피데믹 라우팅은 저장-운반-전달(store-carry-forwarding) 방식으로 불리기도 한다. 에피데믹 라우팅에서는 데이터 전달 성능을 향상시키기 위하여 가능한 많은 데이터 복사본을 전파하는 전략을 사용한다. 그러나 비교적 짧은 전송지연으로 목적지까지 데이터 전달을 보장하더라도 대역폭, 전송 에너지, 메모리 등과 같은 자원을 많이 소모하게 된다. 에피데믹 라우팅에서는 전송지연과 자원간에 트레이드오프가 존재한다. 예를 들어 긴 전송거리는 다른 노드를 만날 확률을 증가시키게 되어 더 짧은 전송지연을 갖게 되나, 에너지를 더 많이 소모하게 된다. 전송지연과 자원 소모간에 트레이드오프를 고려하여 자원들의 효율성을 향상시키기 위하여 에피데믹 라우팅을 변형한 경로설정 방법들이 제안되고 있다. 감염된 노드가 새로운 노드를 만났을 때 불필요한 재전송을 제한하기 위하여 확률, 유용성 등을 고려하여 감염시키는 방식들이 여기에 해당된다. 그 결과로 불필요한 에너지, 메모리 자원 등을 절약할 수 있을 것이다. 지연 감내 네트워크의 예로는 전술 네트워크, 행성 네트워크, 무선 이동 센서 네트워크 등이 있다. 이런 지연 감내 네트워크에서 적용되는 응용 프로그램들은 상대적으로 긴 전송 지연을 감내할 수 있을 지라도, 어떤 전송지연 이상으로 전달되는 것은 불필요한 것으로 간주할 것이다. 길지만 어떤 전송지연이 요구된다면, 전송지연과 자원 운영간에 트레이드 오프를 고려하여 에너지 자원 소모를 최소화하는 방법을 찾을 수 있을 것이다. 본 논문에서는 주어진 전송 요구조건, 특히, 목적지까지의 전송지연 및 전달 확률에 대하여 지연 감내 네트워크를 위한 새로운 경로설정 방법을 제안한다. 제안하는 방법은 에너지 효율성을 최대화한 에피데믹 라우팅의 새로운 한 방법이 된다. 제안하는 방법에서는 에너지를 절약하기 위하여 감염되는 노드 수와 전송 거리를 제한다. 이를 위한 필요한 변수를 찾기 위하여 에피데믹 라우팅 및 Spraying & wait 경로 설정 방법의 전달 메커니즘을 분석하고, 마코프 체인을 이용하여 수치적으로 모델링 하였다. 이 모델을 이용하여 감염 노드 수에 따른 전송 지연 분포를 구할 수 있고, 최종적으로는 에너지 소비를 최소화하는 최적의 감염 노드 수와 전송 거리를 구하였다. 이 최적의 변수를 이용하여 전송지연과 전달확률을 보장하는 새로운 에너지 효율적인 경로설정 방법을 구축할 수 있다. 또한 감염방식 경로설정을 구현할 때 사용되는 토큰 기반 전달 방식에 토큰 조화(token balancing)라는 새로운 방식을 제안하였다. 제안하는 에너지 효율적인 경로설정 방법을 (n, R)-에피데믹 라우팅이라 부른다. 이 논문에서 기여하는 점은 에너지 효율성을 최적화는 감염 노드 수 및 전송거리를 구하고, 이를 이용 새로운 경로설정 방법을 구현하는 것이다. 기존의 경로설정 방법들과 실험 및 수치적 분석을 통한 성능 평가 시, 제안하는 방법이 에너지 효율성 등에서 우수한 성능을 보여줌을 확인 되었다.