[논문]DTN에서 Markov Chain을 이용한 노드의 이동 예측 기법

전일규; 이강환

doi:10.6109/jkiice.2016.20.5.1013

DTN에서 Markov Chain을 이용한 노드의 이동 예측 기법
Prediction method of node movement using Markov Chain in DTN 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.20 no.5, 2016년, pp.1013 - 1019

전일규 (Interdisciplinary Program in Creative Engineering and Department of Computer Science Engineering, Korea University of Technology and Education) , 이강환 (Interdisciplinary Program in Creative Engineering and Department of Computer Science Engineering, Korea University of Technology and Education)

초록
AI-Helper

본 논문에서는 Delay Tolerant Network(DTN)에서 Markov chain으로 노드의 속성 정보를 분석하여 노드의 이동경로를 예측하는 알고리즘을 제안한다. 기존 DTN에서의 예측기반 라우팅 기법은 노드가 미리 정해진 스케줄에 따라 이동하게 된다. 이러한 네트워크에서는 스케줄을 예측할 수 없는 환경에서 노드의 신뢰성이 낮아지는 문제가 있다. 본 논문에서는 이러한 문제를 극복하기 위해 노드의 속성 정보를 Markov chain을 적용하고 일정 구간에서 시간에 따른 노드의 이동 경로를 예측하는 CMCP(Context-awareness Markov-Chain Prediction)알고리즘을 제안한다. 제안하는 알고리즘은 노드의 속성 정보 중 노드의 속력과 방향성을 근사한 후 Markov chain을 이용하여 제한된 주기와 버퍼의 범위에서 확률전이 매트릭스를 생성하여 노드의 이동 경로를 예측하는 알고리즘이다. 주어진 모의실험 환경에서 노드의 이동 경로 예측을 통해 중계 노드를 선정하여 라우팅 함으로써 메시지 전송 지연 시간이 감소하고 전송률이 증가함 보여주고 있다.

Abstract ▼ AI-Helper

This paper describes a novel Context-awareness Markov Chain Prediction (CMCP) algorithm based on movement prediction using Markov chain in Delay Tolerant Network (DTN). The existing prediction models require additional information such as a node's schedule and delivery predictability. However, network reliability is lowered when additional information is unknown. To solve this problem, we propose a CMCP model based on node behaviour movement that can predict the mobility without requiring additional information such as a node's schedule or connectivity between nodes in periodic interval node behavior. The main contribution of this paper is the definition of approximate speed and direction for prediction scheme. The prediction of node movement forwarding path is made by manipulating the transition probability matrix based on Markov chain models including buffer availability and given interval time. We present simulation results indicating that such a scheme can be beneficial effects that increased the delivery ratio and decreased the transmission delay time of predicting movement path of the node in DTN.

주제어

AI 본문요약
AI-Helper

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

문제 정의

기존 예측 알고리즘들은 노드의 스케줄이나 노드의 연결성을 알고 있어야 하는 문제점을 가지고 있다. 따라서 본 논문에서는 네트워크 환경이나 노드 간 정보를 알 수 없는 환경에서 노드의 속성 정보를 지표로 근사하여 근사된 정보를 Markov Chain을 이용하여 이동 경로를 예측하는 알고리즘을 제안한다.
이러한 문제를 해결하고자 본 논문에서 제안한 알고리즘은 저장된 노드의 속성 정보를 이용해 노드의 이동경로를 예측하여 노드의 스케줄을 알지 못하는 경우에도 노드의 이동 경로를 예측하는 것을 목적으로 하였다. 주어진 모의실험에서는 Random Way Point 이동 모델을 사용하였는데 실제 이동은 모의실험 환경보다 규칙이 존재하기 때문에 더 향상된 성능을 보여줄 수 있을 것이다.
그러나 PER기법은 동일한 랜드마크에서 두 노드가 통신이 가능하도록 네트워크를 랜드마크로 구성해야 하며, 각 노드의 이동 스케줄을 알고 있어 하는 문제점이 있다. 이러한 문제를 해결하기 위해 본 논문에서는 네트워크 환경에 제약을 두지 않고 노드의 이동경로를 예측하는 알고리즘을 제안하였다. 제안된 알고리즘은 기존의 노드의 이동경로를 Markov Chain로 노드의 전이확률 매트릭스를 생성하여 이동 경로를 예측한다.
이러한 문제점을 해결하기 위해서 본 논문에서는 노드 간 연결 상태를 알 수 없는 상황에서 기존의 노드의 이동 경로를 마르코프 모델을 이용하여 예측하는 알고리즘을 제안한다. 본 논문의 구성은 다음과 같다.

제안 방법

노드는 최대 100개의 메시지를 저장할 수 있으며, 각 메시지의 수명은 1000초이다. 노드의 통신 범위는 10m, 25m, 50m, 100m로 설정하여 통신 범위에 따른 변화를 실험하였다. 실험 환경은 아래 표 1과 같다.
본 논문에서 제안하는 알고리즘은 노드의 다양한 속성 정보 중 노드의 속도를 Markov Chain을 이용하여 노드의 다음 이동 경로를 예측하는 알고리즘이다. 기존 예측 알고리즘들은 노드의 스케줄이나 노드의 연결성을 알고 있어야 하는 문제점을 가지고 있다.
본 논문에서 제안하는 알고리즘은 노드의 속성 정보를 활용하여 노드의 이동경로를 예측하여 목적지로 향하는 노드들을 중계노드로 선정한다. 알고리즘의 성능을 비교하기 위하여 노드의 연결성으로 중계노드를 선정하는 PROPHET을 비교 알고리즘으로 선정하였다.
이와 같은 문제로 인해 제안된 PROPHET (Probabilistic ROuting Protocol using History of Encounter and Transitivity)은 노드들의 과거 연결 정보를 이용하여 노드 간의 메시지의 전달 확률을 측정한다. 이를 이용해 목적지에 전달될 확률이 높은 노드를 중계 노드로 선정하여 메시지를 전달하므로 Epidemic 라우팅의 무분별한 메시지 복사를 줄이고, Direct Delivery에 비해 높은 전달성공률을 보인다[9].
이러한 문제를 해결하기 위해 본 논문에서는 네트워크 환경에 제약을 두지 않고 노드의 이동경로를 예측하는 알고리즘을 제안하였다. 제안된 알고리즘은 기존의 노드의 이동경로를 Markov Chain로 노드의 전이확률 매트릭스를 생성하여 이동 경로를 예측한다.

대상 데이터

실험 네트워크 크기는 3000m × 1500m이며, 네트워크 내의 노드의 수는 50, 100, 150개로 설정하여 노드의 수에 따른 변화를 실험하였다.

데이터처리

본 논문에서 제안하는 알고리즘은 노드의 속성 정보를 활용하여 노드의 이동경로를 예측하여 목적지로 향하는 노드들을 중계노드로 선정한다. 알고리즘의 성능을 비교하기 위하여 노드의 연결성으로 중계노드를 선정하는 PROPHET을 비교 알고리즘으로 선정하였다. 비교를 위해 다음과 같은 네트워크 환경을 설정하였다.

이론/모형

일정 구간에서 저장된 노드의 근사된 지표를 이용하여 전이 확률 매트릭스(transition probability matrix)를 생성한다. 전이 확률 매트릭스는 N행N열 매트릭스로 행은 현재 상태를 의미하며 열은 다음 상태를 의미한다.

성능/효과

그림 7은 노드의 통신 범위가 50m일 때, 제안하는 알고리즘을 사용한 라우팅과 PROPHET을 노드 수에 따른 메시지 전송률을 나타낸 그래프이다. 노드의 수가 증가할수록 제안하는 알고리즘은 중계 노드의 수가 증가하고 PROPHET은 연결성이 더 높은 노드를 중계노드로 선정하므로 전송률이 증가한다. 제안하는 알고리즘이 PROPHET에 비해 5%에서 12%의 향상된 메시지 전송률을 보이고 있다.
특히 노드의 밀도가 낮을수록 더 효율적이다. 따라서 제안하는 알고리즘이 기존의 예측 알고리즘들의 단점을 보완하고 있음을 알 수 있다.
그림 5는 노드의 전송 범위가 50m일 때, 제안하는 알고리즘을 사용한 라우팅과 PROPHET을 노드 수에 따른 메시지 지연 시간을 나타낸 그래프이다. 제안하는 알고리즘은 네트워크 내의 노드의 수가 증가하면 통신범위 안에 들어오는 노드의 수가 증가하여 중계노드로 선정될 노드들이 증가하므로 평균 지연시간이 감소한다. PROPHET은 노드의 수가 증가할수록 통신 범위 안에 들어오는 노드의 수가 증가하여 더 높은 연결성을 가진 노드를 중계 노드로 선정하므로 평균 지연 시간이 감소한다.
그림 4는 네트워크 내의 노드 수가 50개일 때, PROPHET과 제안하는 알고리즘을 사용한 라우팅의 통신 범위 증가에 따른 메시지 전송 지연 시간을 비교한 그래프이다. 제안하는 알고리즘은 통신 범위가 증가할수록 선택될 수 있는 중계노드수가 증가하므로 평균 지연시간이 감소하고, PROPHET은 통신 범위가 증가할수록 접촉할 확률이 높은 중계 노드를 선정하여 평균지연시간이 감소한다. 제안하는 알고리즘을 사용한 라우팅은 중계 노드를 다중으로 선정하므로 PROPHET에 비해 메시지 지연 시간이 평균 17% 감소하였다.
그림 6은 네트워크 내의 노드 수가 50개일 때, 제안하는 알고리즘을 사용한 라우팅과 PROPHET을 통신범위 증가에 따른 메시지 전송률을 나타낸 그래프이다. 제안하는 알고리즘은 통신 범위가 증가할수록 중계 노드로 선정될 노드들이 증가하므로 전송률이 증가하고,PROPHET은 통신 범위가 증가할수록 연결성이 더 높은 노드를 선택하므로 전송률이 증가한다. 제안하는 알고리즘을 사용한 라우팅은 중계 노드를 다중으로 선정하므로 통신범위가 증가수록 PROPHET에 비해 메시지 전송률이 10% 증가하였다.
제안하는 알고리즘을 사용한 라우팅은 기존의 PROPHET에 비해 낮은 평균 전송 지연 시간과 높은 메시지 전송률을 보여주고 있다. 특히 노드의 밀도가 낮을수록 더 효율적이다.
제안하는 알고리즘은 통신 범위가 증가할수록 선택될 수 있는 중계노드수가 증가하므로 평균 지연시간이 감소하고, PROPHET은 통신 범위가 증가할수록 접촉할 확률이 높은 중계 노드를 선정하여 평균지연시간이 감소한다. 제안하는 알고리즘을 사용한 라우팅은 중계 노드를 다중으로 선정하므로 PROPHET에 비해 메시지 지연 시간이 평균 17% 감소하였다.
제안하는 알고리즘을 사용한 라우팅은 중계 노드를 다중으로 선정하므로 통신범위가 증가수록 PROPHET에 비해 메시지 전송률이 10% 증가하였다.
PROPHET은 노드의 수가 증가할수록 통신 범위 안에 들어오는 노드의 수가 증가하여 더 높은 연결성을 가진 노드를 중계 노드로 선정하므로 평균 지연 시간이 감소한다. 제안하는 알고리즘을 사용한 라우팅은 중계노드를 다중으로 선정하므로 PROPHET에 비해 6%에서 21% 향상된 메시지 전송 지연시간을 보이고 있다.
노드의 수가 증가할수록 제안하는 알고리즘은 중계 노드의 수가 증가하고 PROPHET은 연결성이 더 높은 노드를 중계노드로 선정하므로 전송률이 증가한다. 제안하는 알고리즘이 PROPHET에 비해 5%에서 12%의 향상된 메시지 전송률을 보이고 있다.

후속연구

주어진 모의실험에서는 Random Way Point 이동 모델을 사용하였는데 실제 이동은 모의실험 환경보다 규칙이 존재하기 때문에 더 향상된 성능을 보여줄 수 있을 것이다. 제안하는 알고리즘의 신뢰성을 향상하기 위해 향후 예측률을 비교하는 연구를 통해 제안하는 알고리즘의 신뢰성이 향상될 것이다.
이러한 문제를 해결하고자 본 논문에서 제안한 알고리즘은 저장된 노드의 속성 정보를 이용해 노드의 이동경로를 예측하여 노드의 스케줄을 알지 못하는 경우에도 노드의 이동 경로를 예측하는 것을 목적으로 하였다. 주어진 모의실험에서는 Random Way Point 이동 모델을 사용하였는데 실제 이동은 모의실험 환경보다 규칙이 존재하기 때문에 더 향상된 성능을 보여줄 수 있을 것이다. 제안하는 알고리즘의 신뢰성을 향상하기 위해 향후 예측률을 비교하는 연구를 통해 제안하는 알고리즘의 신뢰성이 향상될 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	Delay Tolerant Network란?	Delay Tolerant Network(DTN)은 종단간의 연결성이 불안정한 네트워크에서도 통신이 가능하도록 디자인된 네트워크 구조이다[1]. 전쟁이나 재해재난과 같이 네트워크 기반 시설을 상실한 환경에서는 통신의 단절이 빈번하게 일어나, 기존의 TCP/IP 방식의 프로토콜을 적용하기 어렵다.
	네트워크 기반 시설을 상실한 환경에서 통신의 단절이 빈번하게 일어나 기존의 TCP/IP 방식의 프로토콜을 적용하기 어려울 때 해결책은?	전쟁이나 재해재난과 같이 네트워크 기반 시설을 상실한 환경에서는 통신의 단절이 빈번하게 일어나, 기존의 TCP/IP 방식의 프로토콜을 적용하기 어렵다. DTN은 이를 해결하기 위해 저장 및 전송 (Store-Carry-Forward)기반의 메시지 전달 방식을 사용하여 종단 간 연결성이 불안정한 상황에서도 중계 노드를 통해 메시지를 보존하여 통신을 가능하게 한다.
	DTN에서 네트워크 성능에 큰 영향을 미치는 것은?	DTN에서 중계 노드의 선정은 네트워크 성능에 큰 영향을 미친다. 선정된 중계 노드의 수가 많으면 메시지 전달 지연 시간은 줄지만 네트워크 오버헤드는 증가한다.

참고문헌 (11)

Delay Tolerant Networking research group [Internet]. Available : http://www.dtnrg.org.
A. Lindgren, A. Doria, and O. Schelen, "Probabilistic routing in intermittently connected networks," in Service Assurance with Partial and Intermittent Resources, Springer Berlin Heidelberg, pp. 239-254, 2004.
E. Wang, Y. Yang, B. Jia and T. Guo "The DTN Routing Algorithm Based on Markov Meeting Time Span Prediction Model," International Journal of Distributed Sensor Networks, vol.2013, no. 2013, pp. 1-7, Aug. 2014.
Q. Yuan, I. Cardei and J. Wu "Predict and relay: an efficient routing in disruption-tolerant networks," in Proceedings of the 10th ACM international symposium on Mobile ad hoc networking and computing, pp. 95-104, 2009.
X. F. Guo and M. C. Chan, "Plankton: An efficient DTN routing algorithm," in IEEE SECON, New Orleans, LA, pp. 550-558, June 2013.
F. Segundo, E. S. Silva, J-M. Farines, "Predicting journeys for dtn routing in a public transportation system," in Proceedings of the 10th International Conference on Wireless and Mobile Computing, Networking and Communications, Larnaca, pp. 494-499, 2014.
S. Ganguly, S. Basu, S. Roy and S. Mitra, "A location based mobility prediction scheme for post disaster communication network using DTN," in Proceedings of the Applications and Innovations in Mobile Computing (AIMoC) 2015, Kolkata, pp. 25-28, 2015.
A. Vahdat and D. Becker, "Epidemic Routing for Partially-Connected Ad Hoc Networks," Duck Univ. tech. rep. CS-2000-06, 2000.
T. Spyropoulos, K. Psounis, and C. S. Raghavendra, "Single-copy routing in intermittently connected mobile networks," in Proc. of IEEE Secon, Apr. 2004.
T. Camp, J. Boleng, V. Davies, "A survey of mobility models for ad hoc network research," Wireless Communications & Mobile Computing, vol. 2, no. 5, pp. 483-502, Aug. 2002.

상세보기
A. Mehto and M. Chawla, "Modified Different Neighbor History Spray and Wait using PROPHET in Delay Tolerant Network," International Journal of Computer Applications, vol. 86, no.18, pp. 30-35, Jan. 2014.

저자의 다른 논문 :

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

연합인증