전달 노드의 특성을 이용한 효과적인 지연 허용 네트워크 라우팅 프로토콜

I. 서 론

지연 허용 네트워크(DTN, Delay Tolerant Network)는 송신 노드와 수신 노드 간 안정된 통신 경로가 존재하는 경우에만 통신이 가능한 기존의 통신 네트워크와 달리 송신 노드와 수신 노드 간 안정된 통신 경로가 존재하지 않는 환경에서도 통신이 가능한 통신 네트워크이다[1]-[3]. 이를 위해 지연 허용 네트워크에서는 전송 계층 위에 번들 계층을 정의하여 주위에 통신이 가능한 노드를 만날 때까지 오랜 시간 동안 메시지를 저장할 수 있도록 하였다. 지연 허용 네트워크에서는 전달해야 할 메시지를 가진 노드가 주위 노드와의 기회적인 접촉을 통해 한 홉 떨어진 주위 노드로 메시지를 전달한다. 메시지를 가진 노드는 번들 계층의 도움으로 메시지를 자신의 버퍼에 저장하고 이동하다가 다른 노드와 접촉 시 미리 정의된 전달 조건을 만족하는 경우 메시지를 전달하고, 이러한 메시지 전달 과정을 반복하여 수행함으로써 최종 목적지로 메시지의 전달을 도모한다. 이러한 지연 허용 네트워크에서의 메시지 전달 방식은 통상 저장-운반-전달(Store-carry-forward) 방식이라 한다.

지연 허용 네트워크에서는 다른 노드와 접촉 시 접촉 노드로 메시지를 전달할지를 결정하는 기법이 라우팅 프로토콜의 성능에 가장 큰 영향을 미치며 다양한 기법들이 연구되어 왔다. 가장 간단한 지연 허용 라우팅 프로토콜인 Epidemic 프로토콜[4]에서는 주위 노드와 접촉 시 자신이 가진 메시지를 무조건적으로 전달하는 방식으로 동작이 간단하고 메시지의 확산이 빠르다는 장점이 있으나 메시지가 많이 복사되어 이러한 메시지들을 충분히 수용할 수 있을 만큼 버퍼의 크기가 크지 않은 환경에서는 버퍼 오버플로우(Overflow)로 인한 성능 저하가 발생하는 단점이 있다. 인터넷 표준을 제정하는 IETF(Internet Engineering Task Force)에서 표준으로 제정된 라우팅 프로토콜인 PRoPHET(Probabilistic Routing Protocol using History of Encounters and Transitivity) 프로토콜[5]에서는 노드 간 과거의 접촉 정보를 이용하여 전달 예측률(Delivery predictability)을 계산하고, 내가 가진 메시지의 목적지 노드에 대해 접촉 노드가 자신보다 더 큰 전달 예측률을 가지는 경우 메시지를 전달한다. 두 노드 간 전달 예측률은 매 접촉 시마다 그 값이 증가하고 가장 최근에 접촉한 이후 시간이 증가함에 따라 그 값이 지수적으로 감소하는 특성을 가진 값으로 정의된다.

본 논문에서는 PRoPHET 프로토콜을 기본 프로토콜로 가정하며 PRoPHET 프로토콜 관련 기존 연구[6]-[12] 중 보행자, 차량, 트램으로 구성된 지연 허용 네트워크에서 우수한 버퍼 크기를 가지고 지정된 노선을 주기적으로 이동하는 트램의 특성을 활용한 기존의 연구[12]를 확장한다. 이를 위해 보행자보다 더 큰 버퍼 크기를 가지고 더 고속으로 넓은 범위를 이동하는 차량의 특성을 추가적으로 고려하는 효과적인 라우팅 프로토콜을 제안하고 그 성능을 분석하고자 한다. 제안 프로토콜에서는 두 노드의 접촉 시 총 4개로 구분된 접촉 노드 간의 관계에 기반한 동작으로 구성된 기존의 기법에 대비하여 총 9개로 구분된 접촉 노드의 관계를 이용하여 각각의 관계에서 효과적인 메시지 전달 기준을 정의하고 이를 통해 성능 향상을 도모하고자 한다.

본 논문의 2장에서는 관련 연구를 상세히 설명하고, 3장에서는 제안 프로토콜에 대해 설명한다. 4장에서는 제안 프로토콜의 성능을 시뮬레이션을 통해 전달률, 부하율, 전달 지연 측면에서 분석한다. 마지막으로 5장에서는 본 논문의 결론을 맺는다.

Ⅱ. 관련 연구

본 논문에서는 PRoPHET 프로토콜을 기본 프로토콜로 가정하는데 PRoPHET 프로토콜 관련 최신 연구를 살펴보면 다음과 같다. [6]의 연구에서는 PRoPHET 프로토콜에서 정의된 전달 예측률 계산 시 노드 간 접촉 유지 시간과 접촉 주기를 동시에 고려하였고, [7]의 연구에서는 생체 모방 알고리즘인 개미군집최적화(Ant-colony optimization) 이론을 PRoPHET에 적용하였다. [8]의 연구에서는 송신 노드의 전달 예측률 뿐만 아니라, 노드가 과거 접촉했던 노드의 전달 예측률을 접촉 노드의 전달 예측률과 동시에 비교하는 HESnW(History Encounter-based Spray and Wait) 기법을 제안하였다. [9]의 연구에서는 메시지 전달 조건 결정 시 노드가 목적지 노드와 접촉하기까지의 평균 시간 및 평균 거리를 전달 예측률과 동시에 활용하였다. [10]의 연구에서는 노드가 과거에 접촉했던 노드의 정보를 이용하여 노드 간 접촉 이력 및 목적지 노드로의 전달 주기를 메시지 전달 조건으로 활용하였다. [11]의 연구에서는 노드 간 접촉 기간 및 비 접촉 기간 정보 기반의 퍼지 이론(Fuzzy logic)을 이용하여 전달 예측값을 계산하였다. [12]의 연구에서는 보행자, 차량, 트램으로 구성된 지연 허용 네트워크에서 우수한 버퍼 크기를 가지고 지정된 노선을 주기적으로 이동하는 트램의 특성을 활용하였다.

본 논문에서 비교 대상으로 하는 기존 연구[12]에서는 노드를 1) 트램, 2) 차량/보행자의 2개의 그룹으로 나누어 각각의 그룹이 송신 노드 및 수신 노드인 4개의 조합에서 각 조합별로 적절한 메시지 전달 기준을 제안하고 이를 통해 성능 향상을 도모하였다. 즉, 보행자, 차량 및 트램으로 구성된 네트워크 환경에서, 전원을 공급받으며 이동하여 우수한 버퍼 공간을 운용할 수 있고 지정된 노선을 주기적으로 이동하는 트램의 특성을 활용하여 성능을 향상시키기 위해 표 1과 같이 노드를 트램과 차량/보행자의 2개의 그룹으로 나누고 각각의 그룹이 송신 노드 및 수신 노드인 4개의 조합에서 각 조합의 특성에 맞는 메시지 전달 기준을 제시하였다. 이 때, DP(t,d) 및 DP(r,d)는 목적지 노드 d에 대한 송신 노드 및 수신 노드의 전달 예측률을 의미한다.

Table 1.

Message forwarding condition of conventional protocol

표 1에서와 같이 충분한 버퍼 크기 및 넓은 이동 범위를 가지는 트램이 수신 노드인 경우에는 송신 노드는 모든 메시지를 전달하고 이를 위해 P1 및 P3의 값을 통상 0으로 설정한다. 반면, 많은 메시지를 버퍼에 저장하고 있는 트램이 송신 노드이고 차량/보행자가 수신 노드인 경우 차량/보행자가 목적지인 경우에만 메시지를 수신하고 이를 위해 P2의 값을 통상 1로 설정한다. 송신 노드 및 수신 노드가 모두 차량/보행자인 경우 수신 노드의 전달 예측률이 더 큰 경우 수신 노드로 메시지를 전달한다.

그림 1은 표 1의 기존 연구[12]에서 제안하고 있는 노드 간 접촉 관계에 따른 메시지 전송 동작의 시나리오를 보여준다.

Fig. 1.

Message delivery scenario of conventional protocol

Ⅲ. 제안 프로토콜

제안 프로토콜에서는 배터리로 동작하는 보행자 단말에 비해 충분한 전원을 가지고 충분한 버퍼 공간을 가질 수 있으며 더 고속으로 넓은 범위를 이동하는 차량의 특성을 고려하여 성능 향상을 도모하고자 한다. 이를 위해 표 2와 같이 보행자와 차량을 분리하여 송신 노드 및 수신 노드가 각각 트램, 차량, 보행자인 경우의 총 9가지 조합을 고려한다.

Table 2.

Message forwarding condition of the proposed protocol

이후, 수신 노드가 차량인 경우 P2, P5 및 P8의 값을 0과 1사이의 적절한 값으로 정의하고 고려하는 메시지의 목적지 노드에 대한 수신 차량인 차량의 전달 예측률이 이 값보다 더 큰 경우 메시지를 전달하도록 한다.

단, 기존 프로토콜과의 공정한 비교를 위해 시뮬레이션 수행 시 트램이 수신 노드인 경우 P1, P4 및 P7의 값은 기존과 동일하게 0으로 가정하였고, 송신 노드가 보행자가 아닌 경우 수신 노드가 보행자인 경우에 해당하는 P3 및 P6의 값은 1로 가정하였다. 이를 통해 수신 노드가 트램인 경우 항상 메시지를 전송하고, 송신 노드가 트램이고 수신 노드가 차량/보행자인 경우 수신 노드가 목적지 노드인 경우에만 메시지를 전달하는 프로토콜의 성능을 향상시키고자 하였다.

표 3은 기존 프로토콜과 제안 프로토콜의 특성을 송신 노드 및 수신 노드의 특성 분류, 노드의 버퍼 크기, 고려하는 송신 노드 및 수신 노드의 메시지 전달 조건 조합, 수신 노드가 차량인 경우 메시지 전달 조건의 관점에서 비교한다. 제안 프로토콜은 기존 연구에서 동일하게 고려된 차량/보행자의 특성을 좀 더 세분화하여 보행자보다 더 큰 버퍼를 가지는 차량을 고려한다. 이후, 이러한 특성을 효과적으로 반영하기 위해 수신 노드가 차량인 경우와 보행자인 경우 서로 다른 메시지 전달 조건을 가정하여 효과적인 메시지 전달을 도모한다.

Table 3.

Comparison of protocols

Ⅳ. 성능 분석

제안 프로토콜의 성능을 상세히 분석하기 위해 지연 허용 네트워크와 같은 기회적 네트워크 환경을 위한 시뮬레이터로 널리 사용되고 있는 ONE(Opportunistic Network Environment) 시뮬레이터[13][14]를 사용하여 식 (1)~(3)에서 정의된 전달률, 부하율, 전달지연을 분석하였다.

본 시뮬레이션에서는 제안 프로토콜(Proposed)과 기존 프로토콜[12](Conventional)와의 공정한 비교를 위해 표 4와 같이 기존 프로토콜에서 사용한 것과 동일한 시뮬레이션 환경을 가정하였다. 다만, 전원을 공급받아 보행자 단말에 비해 우수한 버퍼 공간을 운용할 수 있는 차량의 특성을 반영한 제안 프로토콜의 성능 분석 시뮬레이션을 위해 기존 연구의 보행자 단말의 버퍼 크기와 동일하게 10Mbytes~100Mbytes로 설정한 차량의 버퍼 크기는 제안 프로토콜 및 기존 프로토콜 모두에서 500Mbytes로 설정하였다.

Table 4.

Simulation environment

그림 2는 보행자의 버퍼 크기를 10Mbytes에서 100Mbytes까지 10Mbytes의 단위로 변화시키면서 전달률을 비교한 그래프이다. 제안 프로토콜은 P2, P5, P8의 값을 0, 0.4, 08로 다양하게 변화시킨 상황에서 기존 프로토콜에 비해 항상 우수한 성능을 가지며 최대 약 2.4% 정도 우수한 성능을 가지는 것을 알 수 있다. 이는, 보행자와 차량의 특성을 동일하게 가정하여 송신 노드가 트램인 경우 차량이 목적지 노드인 경우에만 메시지를 수신하는 기존 프로토콜에 비해 제안 프로토콜에서는 차량의 경우 목적지 노드인 경우 이외에도 미리 설정한 P2, P5, P8보다 전달 예측률이 더 큰 경우 메시지를 수신하게 함으로써 메시지의 확산을 적절히 도모할 수 있고 이를 통해 메시지의 효과적으로 전달할 수 있기 때문이다.

Fig. 2.

Delivery ratio

그림 3은 보행자의 버퍼 크기를 10Mbytes에서 100Mbytes까지 10Mbytes의 단위로 변화시키면서 부하율을 비교한 그래프이다. 제안 프로토콜은 P2, P5, P8의 값을 0, 0.4, 08로 다양하게 변화시킨 상황에서 기존 프로토콜에 비해 차량이 수신 노드인 경우 전달된 메시지의 수는 증가하지만 전달된 메시지의 수가 상대적으로 증가하여 식 (2)에서 유추하여 볼 수 있는 것처럼 제안 프로토콜에 비해 다양한 P2, P5, P8의 값에 상관없이 항상 우수한 성능을 가지며 최대 17.5% 정도 더 적은 부하율을 가지는 것을 알 수 있다.

Fig. 3.

Overhead ratio

그림 4는 보행자의 버퍼 크기를 10Mbytes에서 100Mbytes까지 10Mbytes의 단위로 변화시키면서 전달지연을 비교한 그래프이다. 제안 프로토콜은 이동 속도 및 이동 범위가 보행자보다 더 큰 차량에게 더 많은 메시지를 전달하여 줌으로써 다양한 P2, P5, P8의 값에 상관없이 기존 프로토콜에 비해 항상 우수한 성능을 가지며 최대 4.9% 적은 전달지연을 가지는 것을 알 수 있다. 또한, 모든 프로토콜에서 전달지연은 보행자의 버퍼의 크기가 증가함에 따라 오버플로우 되는 메시지가 줄어들어 전달지연 또한 감소하는 것을 알 수 있다.

Fig. 4.

Delivery latency

Ⅴ. 결 론

본 논문에서는 보행자보다 더 큰 버퍼 크기를 가지고 더 고속으로 넓은 범위를 이동하는 차량의 특성을 고려하여 성능 향상을 도모하는 전달 노드의 특성을 이용한 효과적인 라우팅 프로토콜을 제안하고 그 성능을 분석하였다. 성능 분석 결과 제안 프로토콜은 수신 노드의 메시지 전달 기준을 차량과 보행자 노드와 구분하여 차량 노드의 이동성을 효율적으로 활용함으로써 기존 프로토콜에 비해 최대 2.4% 향상된 메시지 전달율, 최대 17.5% 적은 부하율 및 최대 4.9% 적은 전달 지연을 가지는 것을 알 수 있었다. 본 논문의 결과를 통해 다양한 노드로 구성된 지연 허용 네트워크 환경에서는 노드의 이동 범위, 이동 경로, 이동 속도 등 다양한 노드의 특성을 효과적으로 고려한 각 노드의 특성에 맞는 메시지 전달 조건을 설정함으로써 성능을 효과적으로 개선할 수 있음을 알 수 있었다.

References

• 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, Vol. 41, No. 6, pp. 128-136, Jun. 2003. [https://doi.org/10.1109/MCOM.2003.1204759]
• IRTF Delay Tolerant Networking research group, https://irtf.org/concluded/dtnrg, . [accessed: Sep. 16, 2019]
• Z. Zhang, "Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges", IEEE Communications Survey and Tutorial, Vol. 8, No. 1, pp. 24-37. Jan. 2006. [https://doi.org/10.1109/COMST.2006.323440]
• X. Zhang, G. Neglia, J. Kurose, and D. Towsley, "Performance Modeling of Epidemic Routing", Computer Networks, Vol. 51, No. 10, pp. 2867-2891, Jul. 2007 [https://doi.org/10.1016/j.comnet.2006.11.028]
• A. Lindgren, A. Doria, E. Davies, and S. Grasic, "Probabilistic Routing Protocol for Intermittently Connected Networks", Internet Research Task Force (IRTF), Request for Comments 6693, Aug. 2012. [https://doi.org/10.17487/rfc6693]
• H. J. Lee, J. C. Nam, W. K. Seo, J. I. Choi, and Y. Z. Cho, "An Efficient DTN Routing Protocol with Considering Contact Duration", Proceedings of KICS Annual Winter Conference, Jeongseon, Korea, pp. 921-922, Jan. 2015.
• M. Ababou, R. Elkouch, M. Mellafkih, and N. Ababou, "AntProPHET: A New Routing Protocol for Delay Tolerant Networks", Proceedings of Mediterranean Microwave Symposium, Marrakech, Morocco, pp. 235-240, Dec. 2015. [https://doi.org/10.1109/MMS.2014.7088999]
• S. Gan, J. Zhou, and K. Wei, "HESnW: History Encounters-Based Spray-and-Wait Routing Protocol for Delay Tolerant Networks", Journal of Information Processing Systems, Vol. 13, No. 3, pp. 618-629, Jun. 2017.
• K. M. Baek, D. Y. Seo, and Y. W. Chung, "An Improved Opportunistic Routing Protocol Based on Context Information of Mobile Nodes", Applied Science, Vol. 8, No. 8, 1344, 15pages, Aug. 2018. [https://doi.org/10.3390/app8081344]
• J. Wan, H. Zhang, F. Liu, and Y. Chen, "Routing in Delay Tolerant Networks with Fine-Grained Contact Characterisation and Dynamic Message Replication", Proceedings of IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks, Coimbra, Portugal, pp. 1-6, Jun. 2016.
• K. Sabeetha, A. V. A. Kumar, and R. S. D. Wahidabanu, "Encounter Based Fuzzy Logic Routing in Delay Tolerant Networks", Wireless Networks, Vol. 21, No. 1, pp. 173-185, Jan. 2015. [https://doi.org/10.1007/s11276-014-0780-4]
• D. Y. Seo and Y. W. Chung, "An Efficient Context-aware Opportunistic Routing Protocol", Transactions of Korean Institute of Electrical Engineers Vol. 65, No. 12, pp. 2218-2224, Dec. 2016. [https://doi.org/10.5370/KIEE.2016.65.12.2218]
• The Opportunistic Network Environment Simulator, http://www.netlab.tkk.fi/tutkimus/dtn/theone/, [accessed: Sep. 16, 2019]
• A. Keranen, J. Ott, and T. Karkkainen, "The ONE Simulator for DTN Protocol Evaluation", Proceedings of International Conference on Simulation Tools and Techniques, Rome, Italy, Article No. 55:1-10, Mar. 2009. [https://doi.org/10.4108/ICST.SIMUTOOLS2009.5674]