Home

The Journal of Korean Institute of Information Technology - Vol. 16 , No. 9


[ Article ]
The Journal of Korean Institute of Information Technology - Vol. 16, No. 9, pp. 67-73
Abbreviation: Journal of KIIT
ISSN: 1598-8619 (Print) 2093-7571 (Online)
Print publication date 30 Sep 2018
Received 20 Jul 2018 Revised 05 Sep 2018 Accepted 08 Sep 2018
DOI: https://doi.org/10.14801/jkiit.2018.16.9.67
지연 허용 네트워크에서 노드의 접촉 이력을 이용한 향상된 메시지 전달 기법
송민경^* ; 강민욱^ ; 정윤원^*
*숭실대학교 전자정보공학부
**숭실대학교 정보통신공학과
***숭실대학교 전자정보공학부 교수
An Improved Message Delivery Scheme Based on Node's Contact History in Delay Tolerant Network
Min Kyung Song^* ; Min Wook Kang^ ; Yun Won Chung^*



Correspondence to : Yun Won Chung School of Electronic Engineering, Soongsil University, 369, Sangdo-Ro, Dongjak-gu, Seoul, 156-743, Korea Tel: +82-2-820-0908, E-mail: ywchung@ssu.ac.kr

초록

지연 허용 네트워크에서 노드는 번들(bundle) 계층에 메시지를 저장하고 이동하다가 다른 노드와 기회적으로 접촉 시 메시지를 전달하는 저장-이동-전달(store-carry-forward) 방식에 기반하여 동작한다. 본 논문에서는 지연 허용 네트워크에서 접촉 노드와의 중복 노드 및 여분 노드의 이력 정보를 이용하여 메시지를 효과적으로 전달하는 향상된 메시지 전달 기법을 제안한다. 버퍼의 크기 및 메시지 발생 간격을 변화시켜 가면서 전달률 및 부하율의 측면에서 성능 분석을 수행한 결과 제안 기법은 RPC(Reachable Probability Centrality) 및 FSF (Friendship and Selfishness Forwarding) 기법에 비해 부하율은 높지만 가장 좋은 전달률을 가지는 것을 알 수 있었다.

Abstract

In delay tolerant network (DTN), a node operates based on store-carry-forward approach, where a node stores messages in bundle layer, carries them while moving, and forwards them via opportunistic contact with another node. In this paper, we propose an improved message delivery scheme which delivers a message efficiently by using duplicated node and complemented node list of contact node in DTN. Performance analysis result shows that the proposed scheme has best delivery ratio, although it has higher overhead ratio than reachable probability centrality (RPC) and friendship and selfishness forwarding (FSF) schemes for varying buffer size and message generation interval.


Keywords: delay tolerant network, contact history, routing, opportunistic contact

Ⅰ. 서론

지연 허용 네트워크(DTN, Delay Tolerant Network)는 노드 간 연결이 단절된 상황에서 번들(Bundle) 계층에 메시지를 저장하고 이동 중 다른 노드와 접촉 시 기회적으로 메시지를 전달하는 저장-이동-전달(Store-carry-forward) 방식을 사용하여 메시지를 전달한다[1]-[3]. 기본적인 지연 허용 네트워크 프로토콜로는 Epidemic, Spray & Wait, PRoPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity) 등이 있다. Epidemic 프로토콜은 메시지를 가지고 있는 노드가 접촉하는 모든 노드에게 메시지를 복사하는 메시지 전달 방식을 사용한다. Epidemic 프로토콜은 신속하게 메시지를 확산하여 전달 지연이 낮은 반면 네트워크 내 메시지 복사본 수가 증가하여 부하가 높은 단점이 있다[4]. Spray & Wait 프로토콜은 네트워크 내 메시지의 총 복사본 수를 L개로 제한하고 메시지를 다른 L-1개의 노드로 확산하는 단계인 Spray phase와 목적지 노드로만 메시지를 전달하는 단계인 Wait phase를 통해 메시지를 전달한다. Spray & Wait 프로토콜은 Epidemic 프로토콜에 비해 네트워크 부하가 낮은 장점이 있다[5]. PRoPHET은 노드 간 접촉 횟수 및 접촉 이후 지난 시간을 이용하여 전달 예측률(Delivery Predictability)을 계산하고 메시지의 목적지 노드로의 전달 예측률이 더 높은 노드에게 메시지를 전달한다[6].

최근 기본적인 프로토콜 이외에 다양한 지연 허용 프로토콜이 제안되고 있다. 이동 노드의 에너지 잔여량에 기반한 메시지 전달 기법에서는 이동 노드의 에너지 잔여량에 기반하여 최대 전송 및 수신 가능한 메시지 수를 제한함으로써 성능 및 생존률을 향상시킨다[7]. 메시지의 송수신 횟수를 이용한 PRoPHET에서는 메시지 송수신 횟수 및 전달 예측률을 이용하여 메시지 전달 여부를 결정한다. 또한 메시지의 홉 수를 이용하여 메시지 확산 단계와 전달 단계 구분하여 메시지를 전달하는 기법을 제안하였다[8]. 도달 가능성을 이용한 메시지 전달 기법(RPC, Reachable Probability Centrality)에서는 접촉 횟수 및 멀티 홉 전달 확률을 이용하여 목적지 노드로의 도달 가능성을 계산하고 도달 가능성이 높은 노드에게 메시지를 전달하는 기법을 제안하였다[9]. FSF(Friendship and Selfishness Forwarding) 프로토콜에서는 목적지 노드와의 친밀도가 높고 잔여 버퍼량 및 배터리 에너지가 충분한 노드에게 메시지를 전달하는 기법을 제안했다. 노드 간 접촉 시 접촉 횟수, 접촉 지속 시간, 두 노드가 교환한 메시지의 양을 weak, middle, high로 나누고 친밀도를 계산한다[10]. FC(Friendship Community) 프로토콜에서는 단위 시간 동안 노드는 접촉 이력을 이용한 우정 커뮤니티를 형성한다. 노드 간 접촉 시 자신의 우정 커뮤니티에서의 목적지 노드 유무를 통해 목적지 노드에 대한 우정을 판별하고 목적지 노드와의 우정이 더 강한 노드에게 메시지를 전달한다[11].

상기의 연구 중 [7]의 연구에서는 최대 전송 및 수신 가능한 메시지 수를 제한하여 생존률을 증가시키고 있으나 메시지의 확산을 제한함으로써 전달률의 향상에는 제약이 있다. [8]의 연구에서는 우수한 메시지 전달을 위해 확산 초기 및 후기를 결정하기 위한 홉 수를 상황에 따라 적절히 설정하기 어려운 문제점이 있다. 노드 간 접촉 이력에 의존하여 메시지 복사본의 전달을 수행하는 [9]-[11]의 기법에서는 충분한 메시지의 확산을 통해 메시지의 전달을 도모하여야 하는 네트워크 환경에는 적합하지 않은 단점이 있다.

본 논문에서는 노드 간 접촉 시 노드 접촉 이력을 저장하고 상대 노드와 접촉 이력을 교환하여 목적지 노드로의 전달 가능성이 높거나 다른 노드로의 확산 능력이 뛰어난 노드에게 메시지를 복사하는 메시지 향상된 메시지 전달 기법을 제안한다. 본 논문의 2장에서는 제안 기법에 대하여 설명하고 3장에서는 제안 기법의 성능을 상세히 분석한다. 마지막으로 4장에서는 결론을 맺도록 한다.

Ⅱ. 제안 기법

제안 기법에서 노드 A는 다른 노드와 접촉 시 노드 리스트에 접촉 노드 및 접촉 횟수 정보를 기록한다. 이 때, 노드 A의 접촉 노드 집합은 L_A로 표기한다. 노드 A는 다른 노드와 접촉 시 노드 리스트에 저장된 노드를 중복 노드 s_A 및 여분 노드 m_A로 구분하고 중복 노드의 집합을 S_A, 여분 노드의 집합을 M_A로 표기한다. 중복 노드는 접촉한 두 노드의 노드 리스트에서 동일하게 존재하는 노드로 정의되고 여분 노드는 중복 노드에 포합되는 노드를 제외한 나머지 노드로 정의된다. 그림 1은 목적지 노드가 D인 메시지를 가지고 있는 노드 A와 노드 B가 접촉한 경우 노드 리스트를 교환하는 동작 예로 두 노드의 노드 리스트는 표 1과 같다.

Fig. 1.
Example of proposed scheme

Table 1.
Example of node list

Node A		Node B
ID	Contact Count	ID	Contact Count
C	4	C	1
E	4	D	4
D	3	G	3
F	10	O	9
G	5	P	6
B	1	A	1

표 1에서 노드 A, B는 교환된 두 노드의 노드 리스트에 동일하게 존재하는 노드 C, D, G를 중복 노드로 분류한다. 또한 노드 A의 노드 리스트에서 중복 노드에 속하는 노드를 제외한 나머지 노드 E, F를 노드 A의 여분 노드, 노드 B의 노드 리스트에서 중복 노드에 속하는 노드를 제외한 나머지 노드 O, P를 노드 B의 여분 노드로 각각 분류한다. 본 논문에서 메시지 전달은 다음의 3가지 방법으로 구분된다.

i) 목적지 노드가 중복 노드에 포함되는 경우
ii) 목적지 노드가 수신 노드의 여분 노드인 경우
iii) 목적지 노드가 노드 리스트에 존재하지 않는 경우

상기 i)의 경우 목적지 노드로의 전달 가능성이 높은 노드에게 메시지를 복사한다. 식 (1)은 목적지 노드 D가 두 노드의 노드 리스트에서 중복 노드에 포함되는 경우 메시지 전달 여부를 결정하기 위한 식이다. 식 (1)에서 P_B,D는 노드 B의 중복 노드에 포함되는 목적지 노드 D와의 접촉 횟수 비율을 의미하고 노드 B와 노드 D 간 접촉 횟수 C(B,D)를 노드 B와 노드 B의 중복 노드 간 접촉 횟수 C(s_B)의 총 합으로 나누어 계산한다. P_B,D가 P_A,D보다 큰 경우 노드 B는 노드 A보다 목적지 노드로의 메시지 전달 가능성이 더 높으므로 노드 A에서 노드 B로 메시지가 복사된다.

PB,D=CB,D∑sB∈SBCsB

(1)

상기 ii)의 경우 수신 노드에서 목적지 노드로의 전달 가능성이 높은 경우 메시지를 복사한다. 식 (2)와 식 (3)은 노드 B의 노드 리스트 중 목적지 노드가 여분 노드에 포함되는 경우 메시지 전달 여부를 결정하기 위한 식이다. 식 (2)에서 R_B,D는 노드 B의 여분 노드에 포함되는 목적지 노드 간 접촉 횟수 비율을 의미하고 노드 B와 노드 D의 접촉 횟수 C(B,D)를 노드 B와 노드 B의 중복 노드 간 접촉 횟수 C(s_B)의 합과 여분 노드 간 접촉 횟수 C(m_B)의 합으로 나누어 계산한다. 식 (3)에서 H_B,D는 노드 B의 목적지 노드와의 접촉 횟수를 제외한 나머지 노드 간 평균 접촉 횟수 비율을 의미하고 목적지 노드와의 접촉 횟수를 제외한 나머지 노드들과의 접촉 횟수의 평균을 총 접촉 횟수로 나누어 계산한다. R_B,D가 H_B,D보다 큰 경우 노드 B는 평균적으로 다른 노드들에 비해 목적지 노드로의 메시지 전달 가능성이 더 높으므로 노드 A에서 노드 B로 메시지가 복사된다.

RB,D=CB,D∑sB∈SBCsB+∑mB∈MBCmB

(2)

HB,D=∑sB,i∈SBCsB+∑mB∈MBCmB-CB,D∑sB∈SBCsB+∑mB∈MBCmB×nLB

(3)

상기 iii)의 경우 다른 노드로의 확산 가능성이 높은 노드에게 메시지를 복사한다. 식 (4)는 노드 A와 B의 노드 리스트에 목적지 노드 D가 없는 경우 메시지 전달 여부를 결정하기 위한 식이다. E_B는 노드 B의 여분 노드의 접촉 횟수 비율을 의미하고 여분 노드의 접촉 횟수의 합을 총 접촉 횟수로 나누어 계산한다. E_B가 E_A보다 큰 경우 노드 B는 노드 A 보다 다른 노드로의 확산 가능성이 높으므로 노드 A에서 노드 B로 메시지가 복사된다.

EB=∑mB∈MBCmB∑sB∈SBCsB+∑mB∈MBCmB

(4)

본 논문에서 제안하는 기법은 그림 2와 같이 동작한다. 노드 A와 노드 B 간 접촉 시 두 노드는 노드 리스트를 교환하고 접촉 횟수를 갱신한다. 이후 노드 리스트를 이용하여 노드를 중복 노드와 여분 노드로 구분하고 송신 노드인 노드 A에서 선택된 메시지의 목적지 노드가 두 노드의 노드 리스트에서 중복 노드에 포함되는 경우 중복 노드의 목적지노드 접촉 횟수 비율인 P_A,D와 P_B,D를 비교하여 P_B,D가P_A,D보다 큰 경우 노드 A에서 노드 B로 메시지를 복사한다.

Fig. 2.
Flowchart of proposed scheme

메시지의 목적지 노드가 B의 노드 리스트에서 여분 노드에 속한다면 B의 목적지 노드 접촉 횟수 비율 R_B,D이 노드 B의 노드 리스트의 평균 노드 접촉 횟수 비율 H_B,D보다 높은 경우 노드 A에서 노드 B로 메시지를 복사한다. 목적지 노드가 중복 노드 및 여분 노드에 속하지 않는다면 여분노드 접촉 횟수 비율인 E_A와 E_B를 비교하여 E_B가 E_A보다 높은 경우 노드 A에서 노드 B로 메시지를 복사한다.

Ⅲ. 성능 평가

본 논문에서는 성능 평가를 위해 헬싱키 대학에서 개발한 시뮬레이터인 ONE(Opportunistic Network Environment) 시뮬레이터[12]를 사용하였고 시뮬레이션 환경은 표 2와 같다. 제안기법과 FC[11], RPC[9] 및 FSF[10]의 버퍼 크기 및 메시지 생성 시간 간격을 변화시키며 식 (5) 및 식 (6)에서 정의된 전달률 및 부하율을 평가한다.

Table 2.
Simulation environment

Parameter	Value
Area Size(m²)	4,500×3,400
Simulation Time(s)	43,200
Transmission Range(m)	10
Movement model	Pedestrians, cars: Shortest Path Map Based Movement Trams: Map Route Movement
Speed (m/s)	Pedestrians: U[0.5,1.5] Cars: U[2.7,13.9] Trams: U[7,10]
Number of hosts (groups)	Pedestrians: 40(2) Cars: 40(1) Trams: 2(3)
Message size (Bytes)	U[500k,1M]
Buffer size (MBytes)	50(default), 10~100
Message interval(s)	U[25,35](default) U[5,15]~U[95,105]

전달률=전달된메시지수생성된메시지수

(5)

부하율=노드간전송된메시지수-전달된메시지수전달된메시지수

(6)

그림 3, 4는 각각 노드의 버퍼 크기를 변화시키면서 전달률과 부하율을 보여준다. 그림 3과 같이 모든 기법은 버퍼 크기가 커질수록 전달률이 증가하는 것을 확인 할 수 있다. 이는 버퍼의 크기가 커질수록 노드에서 손실되는 메시지 수가 감소하여 목적지 노드로 메시지 전달 가능성이 높아지기 때문이다. 제안 기법은 효과적인 메시지 전송을 통해 가장 우수한 전달률을 가지는 것을 알 수 있다.

Fig. 3.
Delivery ratio

Fig. 4.
Overhead ratio

그림 4에서와 같이 모든 기법은 버퍼 크기가 커질수록 부하율이 감소하는 것을 확인 할 수 있는데 이는 식 (6)에서 목적지 노드로 전달된 메시지 수가 증가하는 영향이 커서 부하율이 감소하기 때문이다. 제안 기법은 RPC, FSF에 비해 높은 부하율을 가지는데 이는 제안 기법은 메시지의 적절한 확산을 통해 전달률을 향상시키는 기법이기 때문이다.

그림 5와 그림 6은 메시지 생성 시간 간격을 변화시켜 가면서 전달률과 부하율을 보여준다. 메시지 생성 시간 간격이 증가함에 따라 모든 기법의 전달률이 증가하는데 이는 생성된 메시지 수가 감소함에 따라 노드의 버퍼에 손실되는 메시지 수가 감소하여 목적지 노드로의 전달 가능성이 높아지기 때문에다. 제안 기법은 효과적인 메시지 전송을 통해 가장 우수한 전달률을 가지는 것을 알 수 있다.

Fig. 5.
Delivery ratio

Fig. 6.
Overhead ratio

그림 6에서와 같이 메시지 생성 시간 간격이 증가함에 따라 모든 기법은 부하율이 증가하는데 이는 식 (6)에서 목적지 노드로 전달된 메시지의 수가 감소하는 영향이 더 커서 부하율이 증가하기 때문이다. 그림 4와 유사하게 제안 기법은 RPC, FSF에 비해 높은 부하율을 가지는 것을 볼 수 있다.

Ⅳ. 결론

본 논문에서는 지연 허용 네트워크에서 두 노드의 접촉 시 접촉하는 노드와의 중복 노드 및 여분 노드의 이력 정보를 이용하여 메시지를 효과적으로 전달하는 향상된 메시지 전달 기법을 제안하였다. 이후, 제안 기법의 성능을 버퍼의 크기 및 메시지 발생 간격을 변화시켜 가면서 전달률 및 부하율의 측면에서 시뮬레이션을 통해 분석하였고 기존의 FC, RPC 및 FSF 기법과도 성능을 비교하였다. 성능 분석 결과 제안 기법은 고려된 시뮬레이션 환경에서 부하율은 RPC 및 FSF 기법에 비해 높지만 가장 좋은 전달률을 가지는 것을 알 수 있었다.

References


1.	S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, and K. Scott, "Delay-tolerant networking: an approach to interplanetary internet", IEEE Communications Magazine, 41(6), p128-136, Jun, 2003.
2.	IRTF Delay Tolerant Networking research group, https://irtf.org/concluded/dtnrg. [accessed: Jan. 11, 2018]
3.	Z. Zhang, "Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges", IEEE Communications Survey and Tutorial, 8(1), p24-37, Jan, 2006.
4.	X. Zhang, G. Neglia, J. Kurose, and D. Towsley, "Performance modeling of epidemic routing", Computer Networks, 51(10), p2867-2891, Jul, 2007.
5.	T. Spyropoulos, K. Psounis, and C. S. Raghavendra, "Spray and wait: an efficient routing scheme for intermittently connected mobile networks", Proceedings of the ACM SIGCOMM Workshop on Delay-tolerant Networking, p252-259, Aug, 2005.
6.	A. Lindgren, A. Doria, E. Davies, and S. Grasic, "Probabilistic routing protocol for intermittently connected networks", IETF RFC 6693, Aug, 2012.
7.	M. W. Kang, and Y. W. Chung, "An Opportunistic Message Forwarding Scheme based on the Residual Energy of Mobile Nodes", Journal of KIIT, 14(5), p105-111, May, 2016.
8.	M. K. Lee, M. W. Kang, and Y. W. Chung, "An Improved PRoPHET Protocol Using Message Transmission/Reception Counter in Delay Tolerant Networks", Journal of KIIT, 14(7), p71-77, Jul, 2016.
9.	J. Wu, J. Wang, L. Liu, M. Tanha, and J. Pan, "A Data Forwarding Scheme with Reachable Probability Centrality in DTNs", I2016 IEEE Wireless Communications and Networking Conference, p1-6, Apr, 2016.
*10.*	C. Souza, E. Mota, L. Galvao, P. Manzoni, and J. Carlos, "FSF: Friendship and Selﬁshness Forwarding for Delay Tolerant Networks", 2016 IEEE Symposium on Computers and Communication (ISCC), p1200-1207, Jun, 2016.
*11.*	E. Bulut, and B. K. Szymanski, "Friendship Based Routing in Delay Tolerant Mobile Social Networks", 2010 IEEE Global Telecommunications Conference GLOBECOM 2010, p1-5, Dec, 2010.
*12.*	The ONE simulator, https://www.netlab.tkk.fi/tutkimus/dtn/theone/, [accessed: Jan. 11, 2018]