분할된 지연 감내 네트워크에서 UAV를 이용한 효과적인 메시지 전달 기법

Ⅰ. 서 론

지연 감내 네트워크인 DTN(Delay Tolerant Networking)은 메시지의 소스 노드에서 메시지의 목적지 노드로 안정적인 라우팅 경로가 존재하지 않는 극한 네트워크 환경에서도 주위 노드와의 기회적 접촉(Opportunistic contact)을 이용하여 효과적으로 메시지를 전달할 수 있는 네트워크이다[1]-[3]. 이를 위해 노드는 목적지 노드로의 라우팅 경로가 존재하지 않는 경우 자신이 가지고 있는 메시지를 전달 계층과 응용 계층 사이에 새롭게 정의된 번들 계층(Bundle layer)의 기능을 이용하여 저장하여 메시지의 손실을 방지한다. 이후, 이동 중 주위 노드가 자신의 통신 범위 안에 들어오는 경우 메시지를 전달한다. 이러한 저장-운반-전달(Store-carry-forward) 과정을 통해 DTN에서는 안정적인 단대단(End-to-end) 라우팅 경로가 존재하지 않는 경우에도 목적지로 메시지를 효과적으로 전달할 수 있다.

DTN은 본래 통신 범위에 비해 매우 먼 거리로 떨어져 있어 단대단 라우팅 경로가 존재하기 힘든 행성 간 네트워크를 위해 제안된 기술로 이후 재난, 전쟁 등의 이유로 네트워크 인프라가 파괴되어 기존 인프라를 이용해 데이터를 전달하기 어려운 환경에서 주위 노드와의 기회적 접촉을 이용해 효과적인 데이터 전달을 수행할 수 있는 유용한 기술로 인식되고 있다. 이동 애드 혹 네트워크인 MANET(Mobile Ad-hoc NETwork)에서도 인프라가 존재하지 않는 환경에서 주위 노드와의 통신을 통해 데이터을 전달할 수 있지만 노드의 밀도가 매우 낮거나 노드의 이동성이 제한된 분할 네트워크 환경에서는 노드 간 단대단 라우팅 경로가 존재하기 어려워 MANET을 통한 데이터 전달은 가능하지 않으며 DTN을 통해 데이터를 전달하여야 한다.

DTN의 대표적인 라우팅 프로토콜로는 접촉하는 주위 노드에게 자신이 가진 메시지 중 접촉 노드가 가지고 있지 않은 메시지를 모두 전달하는 Epidemic 프로토콜[4], 네트워크에 존재할 수 있는 특정 메시지의 복사본의 수를 L개로 제한하여 트래픽 부하가 매우 큰 Epidemic 프로토콜의 단점을 보완한 Spray & Wait 프로토콜[5] 및 노드 간 과거의 접촉 이력에 기반하여 목적지 노드로 메시지를 좀 더 효과적으로 전달할 수 있는 노드로 메시지를 전달하는 PRoPHET(Probabilistic Routing Protocol using History of Encounters and Transitivity)[6] 등이 있다.

DTN 프로토콜 연구에서는 통상 노드의 이동성에 제한을 두지 않는 환경이 일반적이나 노드가 그룹으로 이동하거나[7][8] 재난, 전쟁 등으로 인해 대부분의 노드의 이동성이 분할된 네트워크 내부로 제한되는 분할된 네트워크[9]-[11] 등도 주요 고려 대상이다. [9],[10]의 연구에서는 분할된 서로 다른 지상 네트워크에 속한 노드 간 DTN으로 동작하는 공중 UAV(Unmanned Aerial Vehicle)를 이용하여 데이터를 전달하는 방안을 제시하고 있으며 [11]의 연구에서는 분할된 지상 네트워크 환경에서 각 분할 네트워크의 게이트웨이 노드는 분할 네트워크 주위를 이동하는 데이터 뮬(Data mule)과 DTN을 통해 데이터를 전송하는 방안을 제시하고 있다.

본 논문에서는 재난, 전쟁 등으로 인한 분할 네트워크 환경에서 최근 활발한 연구가 진행되고 있는 공중 노드인 UAV를 이용하여 분할 네트워크 간 효과적인 메시지 전달 기법을 제안하고 성능을 상세히 분석하고자 한다. 본 논문에서는 분할 네트워크 내부의 노드 간 연결성이 보장된 기존 [9]-[11]의 연구에서와 달리 노드 간 간헐적(Intermittent) 연결 환경을 가정한다. 또한, 각 분할 네트워크의 게이트웨이 노드를 통해 데이터 뮬과 통신하는 [11]의 연구와 달리 모든 지상 노드는 공중 UAV 노드와 DTN을 이용하여 직접 통신이 가능한 환경을 가정한다. 마지막으로. 재난 등으로 인해 주위 노드와 멀리 떨어져 있어 주로 공중 UAV 노드와만 통신이 가능한 환경에서 하나 혹은 다수의 UAV 노드가 경로를 이동 중 지상 노드와 접촉 시 데이터를 교환하는 [12]-[14]의 연구와 달리, 지상 노드는 주위 지상 노드 및 공중 UAV 노드와 직접 기회적 접촉을 통한 DTN 통신이 가능하다. 또한, 두 노드의 접촉 시 메시지를 가진 노드 및 접촉 노드가 지상 노드 혹은 공중 UAV 노드인지에 따라 각각 정의된 메시지 전달 조건을 체크하고 이를 충족시키는 경우 메시지를 전달하는 UAV를 이용한 효과적인 메시지 전달 기법을 제안한다.

본 논문의 구성을 다음과 같다. 2장에서는 대표적인 DTN 라우팅 프로토콜에 대해 설명하고 이후 UAV 혹은 데이터 뮬을 활용한 DTN 라우팅 프로토콜과 관련한 기존 연구를 소개한다. 3장에서는 본 논문에서 제안하는 분할 네트워크 환경에서 UAV를 이용한 효과적인 메시지 전달 기법에 대해 상세히 설명한다. 4장에서는 제안 기법의 성능을 시뮬레이션을 통해 상세히 분석한다. 마지막으로 5장에서는 결론 및 향후 연구에 대해 기술한다.

Ⅱ. 관련 연구

Ⅲ. 제안하는 라우팅 기법

본 연구에서는 그림 1과 같이 재난, 전쟁 등으로 인해 노드의 이동성이 분할된 네트워크 내부로 제한되는 분할된 네트워크로 구성된 지상 네트워크를 가정하고, 분할 네트워크 간 메시지 전달을 위해 공중 UAV 노드를 활용한다. UAV는 지상의 분할된 네트워크 간 DTN 라우팅을 위해 제안된 도로를 따라 이동하고 분할 네트워크의 게이트웨이와 주로 통신하는 지상 데이터 뮬에 비해 이동 범위의 제약이 없고 분할 네트워크 내 임의의 노드와 직접 통신이 가능하여 효율적이다. 각 분할 네트워크에 속하는 지상 노드는 자신과 동일한 분할 네트워크에 속하는 다른 지상 노드 혹은 다른 분할 네트워크에 속하는 지상 노드를 목적지 노드로 전달할 메시지를 발생시키고 다른 지상 노드 혹은 공중 UAV 노드와의 기회적 접촉을 통해 메시지를 전달한다.

Fig. 1.

Considered network environment

그림 1에서 지상 노드는 메시지의 소스 노드, 중계 노드, 혹은 목적지 노드로 동작하며 반면, 공중 UAV 노드는 메시지의 중계 노드로만 동작한다. 메시지 1은 G1이 소스 노드로 G1은 주위 노드와 기회적 접촉 시 미리 정의된 전달 조건을 비교하고 이를 충족하는 경우 메시지를 전달한다. 이를 수신한 중계 노드 또한 유사한 동작을 수행하여 메시지 1은 G2-U1-U3- U4-U5 혹은 G2-U1-U3-U4-G9-G10의 중계 노드를 거쳐 최종 목적지 노드인 G11로 전달된다. 메시지 2는 G1이 소스 노드로 G3-G4의 중계 노드를 거쳐 목적지 노드인 G6으로 전달된다. 메시지 3은 G2가 소스 노드로 U1-U2의 중계 노드를 거쳐 목적지 노드인 G5로 전달된다.

노드의 이동성 모델과 관련하여 지상 노드는 자신이 속한 분할된 지상 네트워크 영역에서 제한적으로 이동하는 클러스터 이동성 모델(Cluster mobility model)[15]을 따르는 것으로 가정한다. 클러스터 이동성 모델에서는 노드가 클러스터의 중심을 기준으로 정해진 영역 내에서만 이동이 가능한데 본 논문에서는 클러스터 이동성 모델의 제한 영역을 사각형 클러스터 영역으로 정의하고 각 클러스터 내부에서 지상 노드는 random waypoint 이동성 모델에 기반하여 이동한다. 공중 UAV 노드는 공중에 위치하며 분할된 지상 네트워크 사이를 random waypoint 이동성 모델에 기반하여 자유롭게 이동하는 것을 가정하였다.

본 논문에서는 기본 DTN 프로토콜로 PRoPHET 프로토콜을 가정한다. PRoPHET 프로토콜에서 메시지를 가진 노드는 PRoPHET 프로토콜에서 정의된 전달 예측률을 비교하여 목적지 노드로 더 높은 전달 예측률을 가진 노드로 메시지를 전달한다. 즉, 노드 A가 노드 B와 접촉 시 메시지의 목적지 노드 D에 대해 P(B,D) > P(A,D)인 경우 노드 A는 노드 B에게 메시지를 전달한다. 본 논문에서 각 노드는 자신이 가진 메시지의 목적지 노드 ID를 통해 목적지 노드가 현재 속한 분할 네트워크를 미리 알 수 없는 환경을 가정하며 따라서, 두 노드의 접촉 시 메시지는 노드들의 과거 접촉 이력에 기반하여 계산된 전달 예측률을 활용하여 전달된다. 본 논문에서는 두 노드의 접촉 시 메시지를 가진 노드와 접촉 노드가 지상 노드 혹은 공중 UAV 노드인지에 따라 다음과 같이 4가지 경우로 나누고 각 경우에 적합한 메시지 전달 조건을 제안한다. 이 때, 각 노드는 접촉 노드가 지상 노드인지 혹은 공중 UAV 노드인지를 식별 가능한 것으로 가정하며 편의 상 메시지를 가진 노드는 전송 노드로, 접촉 노드는 수신 노드로 표현한다.

Case 1: 전송 노드 A, 수신 노드 B 및 목적지 노드 D가 모두 지상 네트워크에 속하는 경우로 P(B,D) > P(A,D)이면 A는 B로 메시지를 전달한다.

Case 2: 전송 노드 A는 지상 네트워크, 수신 노드 B는 공중 네트워크, 목적지 노드 D는 지상 네트워크에 속하는 경우로 P(B,D) > P(A,D) + δ 이면 A는 B로 메시지를 전달한다. 이 때, δ는 상수 값으로 정의된다.

Case 3: 전송 노드 A는 공중 네트워크, 수신 노드 B 및 목적지 노드 D는 지상 네트워크에 속하는 경우로 P(B,D) > P(A,D)이면 A는 B로 메시지를 전달한다.

Case 4: 전송 노드 A 및 수신 노드 B는 공중 네트워크, 목적지 노드 D는 지상 네트워크에 속하는 경우로 P(B,D) > P(A,D) 이면 A는 B로 메시지를 전달한다.

제안 기법에서는 상기 Case 1~4 중 Case 1, 3, 4의 경우에는 PRoPHET 프로토콜에서 기본적으로 정의된 전달 예측률 비교 조건을 적용하여 접촉 노드의 전달 예측률 P(B,D)가 자신의 전달 예측률 P(A,D)보다 더 큰 경우 메시지를 전달한다. 반면, 메시지를 가진 지상 노드가 UAV 노드와 접촉하는 Case 2의 경우에는 [16]의 연구와 유사하게 지상 노드의 전달 예측률 P(A,D)에 가중치 δ를 더한 P(A,D) + δ를 공중 UAV 노드의 전달 예측률인 P(B,D)와 비교하여 P(B,D) > P(A,D) + δ를 만족하는 경우 메시지를 전달한다. 이는 지상 노드에 비해 상대적으로 적은 수로 구성된 공중 네트워크 UAV 노드의 제한된 버퍼를 효과적으로 활용하기 위함으로 가중치 δ의 값을 적절히 조절함으로써 UAV 노드로의 메시지 전달을 적절히 조절할 수 있는 특징이 있다.

그림 2는 제안 기법의 흐름도이다. 모든 노드는 다른 노드와 접촉 시 PRoPHET 방식의 전달 예측률 갱신 동작을 수행한다. 지상 네트워크에 속한 노드가 다른 노드와 접촉하고 버퍼에 전송 가능한 메시지가 존재하는 경우 접촉한 상대 노드가 속한 네트워크를 확인한다. 접촉한 상대 노드가 지상 네트워크에 속한 노드인 경우 Case 1에 해당하는 전송 조건을 통해 메시지 전달 여부를 결정하고 접촉한 상대 노드가 공중 UAV 네트워크에 속한 노드인 경우 Case 2에 해당하는 전송 조건을 통해 메시지 전달 여부를 결정한다. 공중 네트워크에 속한 UAV 노드가 다른 노드와 접촉하고 버퍼에 전송 가능한 메시지가 존재하는 경우 접촉한 상대 노드를 확인한다. 접촉한 상대 노드가 지상 네트워크에 속한 노드인 경우 Case 3에 해당하는 전송 조건을 통해 메시지 전달 여부를 결정하고, 접촉한 상대 노드가 공중 네트워크에 속한 노드인 경우 Case 4에 해당하는 전송 조건을 통해 메시지 전달 여부를 결정한다.

Fig. 2.

Flowchart of the proposed scheme

Table 1.

Message forwarding condition

Ⅳ. 시뮬레이션을 통한 성능 분석

본 연구에서는 DTN 연구에서 많이 사용되는 ONE(Opportunistic Network Environment)) 시뮬레이터[17][18]를 이용하여 제안 기법의 성능을 분석하였다. 본 시뮬레이션에서는 표 2의 시뮬레이션 파라미터 설정 환경에서 기존 Epidemic 및 PRoPHET 프로토콜과 제안 기법의 성능을 전달률(Delivery ratio), 부하율(Overhead ratio) 및 전달지연(Delivery latency)의 측면에서 분석하였으며 각각의 정의는 아래 식 (1)~(3)과 같다.

Table 2.

Simulation parameter setting

그림 3은 버퍼 크기 변화에 따른 전달률을 비교한 그래프이다. 버퍼 크기가 증가함에 따라 버퍼 오버플로우로 인해 버퍼에서 제거되는 메시지가 감소하여 모든 라우팅 프로토콜의 전달률이 증가하는 것을 알 수 있다. 제안 기법은 δ = 0.05, 0.15인 경우 Epidemic 및 PRoPHET 보다 높은 전달률을 가지며 특히 δ = 0.1인 경우 유사 비교 기법인 PRoPHET에 비해 최대 9% 높은 전달률이 나타남을 확인하였다. 반면 δ = 0.2인 경우 Epidemic 보다 높은 전달률을 가지나 PRoPHET 보다 낮은 전달률을 가지는 것을 확인했다. 이를 통해 δ의 값을 매우 작은 값으로부터 증가시키는 경우 UAV로의 메시지 복사를 제한하고 이를 통한 UAV의 버퍼 오버플로우 감소로 인해 제안 기법의 전달률은 증가하지만 일정 값 이상 δ의 값이 커지는 경우 UAV로의 메시지 확산이 부족하여 전달률은 오히려 감소하는 것을 알 수 있다.

Fig. 3.

Delivery ratio for varying buffer size

그림 4는 버퍼 크기 변화에 따른 부하율을 비교한 그래프이다. 버퍼 크기가 증가함에 따라 모든 라우팅 프로토콜의 부하율은 다소 증가한 이후 감소하는 추세를 보인다. 제안 기법은 δ = 0.05, 0.1, 0.15인 경우 Epidemic 및 PRoPHET 보다 낮은 부하율을 가지며 δ = 0.15인 경우 유사 비교 기법인 PRoPHET에 비해 최대 10% 낮은 부하율이 나타남을 확인하였다. 반면 δ = 0.2인 경우 Epidemic 보다 낮은 부하율을 가지나 PRoPHET 보다는 높은 부하율을 가지는 것을 볼 수 있다. 이는 식 (2)의 부하율 정의에 따라 전달되는 메시지가 증가하는 경우 부하율은 감소하기 때문이다.

Fig. 4.

Overhead ratio for varying buffer size

그림 5는 버퍼 크기 변화에 따른 전달지연을 비교한 그래프이다. 버퍼 크기가 증가함에 따라 Epidemic을 제외한 모든 라우팅 프로토콜의 전달지연이 증가하는 추세를 보인다. 일반적으로 DTN에서 전달지연은 노드의 이동성, 메시지 확산 정도, 전송 속도 등 다양한 요소에 의해 결정될 수 있는데 고려하는 시뮬레이션 환경에서 Epidemic은 다른 프로토콜에 비해 메시지 확산이 가장 활발하여 가장 낮은 전달 지연을 가지게 된다. 제안 기법은 δ = 0.05, 0.1, 0.15인 경우 Epidemic 및 PRoPHET 보다 높은 전달지연을 가지며 δ = 0.15인 경우 유사 비교 기법인 PRoPHET에 비해 최대 7% 높은 전달지연이 나타남을 확인하였다. δ = 0.2인 경우 메시지 전달 조건을 만족하여 접촉 노드로 전달될 수 있는 메시지의 수가 감소하여 제한된 접촉 시간 및 전송 속도 환경에서 이러한 메시지들이 접촉 노드로 전송될 수 있는 기회 또한 증가하게 되고 따라서, 목적지 노드로 메시지가 전달되는 데 소요되는 전달 지연은 감소하게 된다.

Fig. 5.

Delivery latency for varying buffer size

Ⅴ. 결론 및 향후 연구

본 논문에서는 분할된 지상 네트워크 환경에서 공중 UAV 노드를 이용하여 분할 네트워크 간 효과적인 메시지 전달 기법을 제안하였다. 이를 위해, 두 노드의 접촉 시 메시지를 가진 지상 노드가 공중 UAV 노드에게 메시지를 전달하는 경우 전달 예측률 비교 시 지상 노드의 전달 예측률에 가중치 δ를 더하여 비교함으로써 UAV 노드로의 메시지 확산을 적절히 조절하였다. 시뮬레이션을 통한 성능 분석 결과 제안 기법은 적절한 가중치 δ의 선택 시 PRoPHET 보다 최대 9% 높은 전달률 및 10% 낮은 부하율을 가지는 것을 알 수 있었다. 반면, 전달지연은 제안 기법이 우수한 전달률 및 부하율을 가지는 환경에서 PRoPHET에 비해 최대 7% 증가하는 것을 알 수 있었다. 성능 분석 결과 제안 기법의 성능은 δ 값의 선택에 많은 영향을 받는 것을 알 수 있는데, 향후 연구에서는 변화하는 네트워크 및 노드의 특성을 고려하여 적절한 δ 값을 적응적으로 선택하여 동작하는 적응적 메시지 전달 기법을 제안하고 그 성능을 상세히 분석하고자 한다.

Acknowledgments

본 연구는 방위사업청과 국방과학연구소가 지원하는 미래전투체계 네트워크기술 특화연구센터 사업의 일환으로 수행되었습니다(UD190033ED).

References

• V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall, and H. Weiss, "Delay-Tolerant Networking Architecture", IRTF, RFC 4838, Apr. 2007. [https://doi.org/10.17487/rfc4838]
• Z. Zhang, "Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenge", IEEE Communications Surveys & Tutorials, Vol. 8, No. 1, pp. 24-37, First Quarter 2006. [https://doi.org/10.1109/COMST.2006.323440]
• Y. Cao and Z. Sun, "Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges", IEEE Communications Surveys & Tutorials, Vol. 15, No. 2, pp. 654-677, Second Quarter 2013. [https://doi.org/10.1109/SURV.2012.042512.00053]
• A. Vahdat and D. Becker, "Epidemic routing for partially-connected ad hoc networks", Tech. Rep. CS-200006, Duke University, Durham, NC, USA, Jun. 2000.
• T. Spyropoulos, K. Psounis, and C. S. Raghavendra, "Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks", Proceedings of WDTN, Philadelphia Pennsylvania USA, pp. 252-259, Aug. 2005. [https://doi.org/10.1145/1080139.1080143]
• A. Lindgren, A. Doria, E. Davies, and S. Grasic, "Probabilistic Routing Protocol for Intermittently Connected Networks", IRTF RFC 6693, Aug. 2012. [https://doi.org/10.17487/rfc6693]
• M. W. Kang and Y. W. Chung, "An Efficient Routing Protocol with Overload Control for Group Mobility in Delay-Tolerant Networking", Electronics, Vol. 10, No. 4, 521, Feb. 2021. [https://doi.org/10.3390/electronics10040521]
• L. F. Xie, P. H. J. Chong, Y. L. Guan, and B. C. Ng, "G-ER: Group-epidemic routing for mobile ad hoc networks with buffer sharing mechanism", Proceedings of IWCMC, Harbin, China, pp. 2237-2242, Jul. 2011.
• M. Le, J. Park, and G. Mario, "UAV assisted disruption tolerant routing", Proceedings of MILCOM, Washington, DC, USA, pp. 1-5, Oct. 2006.
• T. H. Kim, Y. J. Lim, and J. S. Park, "Routing in UAV Based Disruption Tolerant Networks", Journal of KIPS, Vol. 16-C, No. 4, pp. 521-526. Aug. 2009. [https://doi.org/10.3745/KIPSTC.2009.16-C.4.521]
• E. Monticelli, B. M. Schubert, M. Arumaithurai, X. Fu, and K. K. Ramakrishnan, "An Information Centric Approach for Communications in Disaster Situations", Proceedings of LANMAN, Reno, NV, USA, pp. `1-6, May 2014. [https://doi.org/10.1109/LANMAN.2014.7028630]
• C. Barroca, A. Grilo, and P. R. Pereira, "Improving Message Delivery in UAV-Based Delay Tolerant Networks", Proceedings of ITST, pp. 1-7, Oct. 2018. [https://doi.org/10.1109/ITST.2018.8566956]
• A. Bujari, C. T. Calafate, J. C. Cano, P. Manzoni, C. E. Palazzi, and D. Ronzani, "A Location-Aware Waypoint-Based Routing Protocol for Airbone DTNs in Search and Rescue Scenarios", Sensors (Basel, Switzerland), Vol. 18, No. 11, 3758, Nov. 2018. [https://doi.org/10.3390/s18113758]
• J. C. Albuquerque, S. C. Luccena, and C. A. V. Campos, "Evaluating Data Communicaations in Natural Disaster Scenarios using Opportunistic Networks with Unmanned Aerial Vehicles", Proceedings of ITST, pp. 1452-1457, Nov. 2016. [https://doi.org/10.1109/ITSC.2016.7795748]
• Cluster Mobility Model, https://github.com/akeranen/the-one/blob/master/src/movement/ClusterMovement, , [accessed: Oct. 10, 2021]
• D. S. Kim and Y. W. Chung, "Message Delivery Considering Quality of Service in Delay Tolerant Network", Journal of KIIT, Vol. 10, No. 11, pp. 121-127, Nov. 2012.
• The ONE (Opportunistic Network Environment) simulator, https://akeranen.github.io/the-one/, , [accessed: Oct. 10, 2021]
• A. Keränen, J. Ott, and T. Kärkkäinen, "The ONE Simulator for DTN Protocol Evaluation", Proceedings of SIMUTools, Rome Italy, pp. 1-10, Mar. 2009. [https://doi.org/10.4108/ICST.SIMUTOOLS2009.5674]