개선된 메시지 복사 제한을 이용한 지연 허용 네트워크 라우팅 프로토콜

I. 서 론

최근 자연 재해 혹은 테러 등으로 인한 통신 인프라의 파괴로 인한 극한 환경에서도 통신을 가능하게 해 주는 지연 허용 네트워크(DTN: Delay Tolerant Network)에 대한 연구가 활발히 진행되고 있다[1]-[3]. 지연 허용 네트워크에서는 소스 노드와 목적지 노드 사이에 통신 인프라 혹은 다른 노드를 통한 끊김 없는 라우팅 경로가 존재하지 않는 환경에서도 통신이 가능한 방식이다. 이를 위해 각 노드는 그림 1에서와 같이 전송 계층 위에 정의된 번들 계층의 기능을 이용하여 자신의 버퍼에 메시지를 저장하고 이동 중 주위 노드와 접촉 시 적절한 기준에 따라 주위 노드로 메시지를 전달하고 이러한 과정을 반복함으로써 최종 목적지 노드까지 메시지를 전달하는 방식으로 동작한다.

Fig. 1.

Message delivery in delay tolerant networks

대표적인 지연 허용 네트워크 프로토콜로는 Epidemic[4], Spray & Wait[5], PRoPHET[6] 프로토콜 등이 있다. Epidemic 프로토콜은 이름에서 알 수 있듯이 자신이 접촉하는 모든 노드에게 메시지를 복사함을 통해 최종 목적지 노드까지 메시지를 전달한다. 동작이 간단하고 메시지 확산이 빠른 장점이 있으나 메시지 복사가 많이 발생하게 되어 버퍼의 크기가 제한된 이동 단말로 구성된 지연 허용 네트워크 환경에 적합하지 않은 단점이 있다.

Spray & Wait 프로토콜에서는 특정 메시지에 대해 네트워크 전체에 복사될 수 있는 복사본의 수를 미리 지정하여 메시지 복사로 인한 네트워크 부하를 줄이고자 한 프로토콜이다. 메시지를 발생시킨 노드가 미리 지정된 복사본의 수만큼 주위 노드로 메시지를 복사하여 메시지를 확산시키는 Spray 단계와 메시지를 가진 노드가 최종 목적지 노드를 만나는 경우에만 메시지를 전달하는 Wait 단계로 구성된다. PRoPHET(Probabilistic Routing Protocol using History of Encounters and Transitivity) 프로토콜은 다른 노드와의 접촉 이력을 이용하여 전달 예측률(Delivery Predictability)를 정의하고 두 노드가 접촉 시 임의의 메시지에 대해 상대 노드가 목적지 노드로 더 큰 전달 예측률을 가지는 노드인 경우 메시지를 전달하는 프로토콜이다. 이를 통해 접촉하는 모든 노드에게 메시지를 전달하는 Epidemic 프로토콜이나 미리 지정된 복사본의 수만큼 접촉하는 노드에게 메시지를 조건 없이 전달하는 Spray & Wait 프토콜에 비해 좀 더 효과적으로 메시지를 전달하고자 하였다.

PRoPHET 프로토콜과 관련한 최근 연구[7]-[13]에서는 다른 노드와 접촉 시 메시지를 전달할지를 결정하는 알고리즘이 주요 핵심 기술로 메시지를 전달함으로써 발생하는 네트워크 부하와 이를 통한 효과적인 메시지 전달 간 이해상충(tradeoff)을 적절히 조절하는 것이 필요하다. 본 논문에서는 메시지 복사본의 수를 이용하여 효과적으로 메시지 확산을 조절하는 기존의 연구[9]에 메시지 복사본의 평균값을 추가적으로 활용하여 메시지의 확산 정도를 각 노드가 파악하고 이를 통해 메시지를 효과적으로 전달하는 개선된 메시지 복사 제한을 이용한 지연 허용 네트워크 라우팅 프로토콜을 제안하고자 한다.

본 논문의 2장에서는 관련 연구를 소개하고, 제안 프로토콜의 비교 대상인 기존 연구를 설명한다. 3장에서는 제안 프로토콜에 대해 설명하고, 4장에서는 제안 프로토콜의 성능을 ONE 시뮬레이터를 통해 검증 및 분석한다. 마지막으로 5장에서는 본 논문의 결과를 요약한다.

Ⅱ. 관련 연구

PRoPHET 프로토콜과 관련한 기존의 연구로는 노드의 버퍼 메모리 사용량, 전력 사용량, 전송 대역, 인기도 등을 고려하여 메시지의 도달 가능성을 도출하고 이를 이용하여 메시지를 선택적으로 전달하는 기법[7], 메시지가 최종 목적지 노드로 전달될 때 메시지를 최종적으로 전달한 노드와 이를 수신한 최종 목적지 노드가 메시지 전달 승인 메시지를 발생시키고 이후 이러한 노드가 이미 전달 승인된 메시지를 가진 노드와 접촉 시 그 노드에서 메시지를 삭제시킴으로 써 버퍼를 효과적으로 관리하는 기법[8], 메시지가 다른 노드에게 전달된 횟수를 측정하고 이 정보를 이용하여 메시지 전달 유무를 결정하는 기법[9], 근사치나 주관적 값들에 대해 규칙을 생성하는 규칙 기반 기술인 퍼지 논리 및 생체 모방 알고리즘의 개미 군집(Ant Colony) 기술을 활용하여 메시지 사본 수 및 노드 레벨을 고려하고 최종 목적지에 메시지를 전달할 수 있는 기회를 가진 중계 노드를 지능적으로 선택하여 에너지 효율을 도모하는 기법[10], 노드의 에너지 혹은 버퍼 공간의 부족으로 인해 메시지를 중계하지 못하는 상황을 극복하기 위해 커뮤니티 가중치라는 소셜 기반 수치를 활용하여 릴레이 노드를 고려하는 기법[11], 소셜 기반 기회적 네트워크의 버퍼 오버플로우(overflow) 문제를 해결하기 위해, 노드와 커뮤니티 사이의 가중치 분포를 설정하여 메시지 전달에 활용하는 소셜 기반 기회적 라우팅 기법[12], 전달 예측률 뿐 아니라 메시지 송수신 횟수를 이용하여 메시지 확산 초기에는 확산에 유리한 노드에게 메시지를 전달하고 메시지 확산 후기에는 목적지 노드까지의 전달이 유리한 노드에게 메시지를 전달하는 향상된 PRoPHET 프로토콜[13] 등의 연구가 진행되었다.

Ⅲ. 개선된 메시지 복사 제한을 이용한 제안 프로토콜

본 논문에서는 본 논문이 비교 대상으로 하는 기존의 연구[9]에서와 같이 임의의 메시지에 대한 네트워크 전체에서의 확산 정도를 간접적으로 유추하기 위한 지표로 메시지의 복사 횟수인 duplication counter(DupC로 약어 표기)를 정의하고 각 노드가 메시지를 주위 노드로 전달 시 이 값을 1씩 증가시키도록 한다. 반면, 동일한 메시지를 가진 다른 노드와 접촉 시 이 정보를 공유하여 더 큰 DupC 값으로 갱신하는 기존의 연구[9]와 달리 동일하게 가지고 있지 않은 메시지에 대해서도 주위 노드와 DupC 값을 공유하도록 한다. 이를 통해 기존의 연구에 비해 메시지가 전체적으로 확산되는 정도를 좀 더 정확하게 유추할 수 있다.

또한 기존 연구[9]에서 DupC 값이 미리 정의한 임계치인 DupC 임계치보다 큰 경우 메시지가 네트워크에 충분히 확산이 된 것으로 판단하여 메시지를 전달하지 않고, DupC의 값이 임계치보다 작은 경우 PRoPHET 프로토콜에서 정의된 전달 예측률을 이용하여 상대 노드가 고려하는 메시지의 최종 목적지 노드에 대한 전달 예측률이 더 큰 경우 이 메시지를 전달했던 것과 달리, 제안 기법에서는 노드에 저장된 메시지들의 DupC의 평균값을 추가적으로 이용하여 메시지의 확산 정도를 각 노드가 보다 효과적으로 파악하여 조절하고자 하였다.

본 논문에서 제안하는 프로토콜의 상세한 동작은 그림 2와 같다. 노드 A와 B 접촉 시 각 노드는 자신의 버퍼에 저장된 메시지 ID, 메시지의 목적지 노드 ID 등의 정보를 포함하는 SV(Summary Vector)를 교환 후 서로 전송해야 할 메시지가 있는지 확인한다. 두 노드가 동일한 메시지를 저장하고 있는 경우 해당 메시지에 대한 복사 횟수를 나타내는 DupC를 비교하여 이 값이 더 큰 값으로 서로의 DupC를 갱신한다. 동일하게 가지고 있지 않은 메시지에 대해서는 해당 메시지 ID에 대한 DupC 정보를 상대방 노드와 공유한다.

Fig. 2

Flow chart of the proposed protocol

노드 A가 송신 노드로 동작하는 경우 해당 메시지에 대한 DupC의 값이 미리 정의된 임계치인 DupC Threshold보다 작고, 노드 A에 저장된 모든 메시지들의 DupC의 평균값인 AvgDupC값보다 클 경우에는 PRoPHET에서 정의된 것처럼 이 메시지에 대해 접촉 노드 B의 목적지 노드 D에 대한 전달 예측률이 더 큰 경우 메시지를 전달한다.

반면, DupC가 AvgDupC보다 작은 경우 평균적인 관점에서 다른 메시지에 비해 확산이 덜 진행된 메시지로 판단하여 확산을 촉진시키기 위해 식 (1)과 같이 상대 노드 B의 목적지 노드 D로의 전달 예측률이 노드 A의 목적지 노드 D로의 전달 예측률에서 미리 설정된 상수 값인 delta를 뺀 값보다 더 큰 경우 메시지를 전달한다.

Ⅳ. 성능 분석

제안된 프로토콜은 ONE(Opportunistic Network Environment) 시뮬레이터[14][15]를 사용하여 아래의 식 (2)~(4)에서 정의된 전달률, 부하율, 전달 지연의 측면에서 분석되었다. 또한 가정하는 시뮬레이션 파라메터는 공정한 성능 비교를 위해 기존의 연구에서 사용한 것과 동일하게 표 1과 같이 설정하였다.

Table 1.

Simulation environment

시뮬레이션은 보행자(Pedestrian), 차량(Car) 및 트램(Tram) 노드로 구성된 ONE 시뮬레이터의 지연 허용 네트워크 시뮬레이션 환경에서 각 노드의 이동 모델(Movement model)을 보행자 및 차량 노드의 경우 지도 상 이동 경로의 최단 거리를 계산하여 이동하는 Shortest Path Map Based Movement로 정의하고, 트램의 경우 지도 상 특정 경로를 주기적으로 이동하는 Map Route Movement로 정의하여 표 1에서 가정된 환경에서 진행되었다.

그림 3은 DupC threshold 값의 변화에 따른 제안 기법의 성능을 기존 기법과 전달률 측면에서 비교한 그림이다. 제안 기법 및 기존 기법은 버퍼의 크기가 증가할수록 전달률도 증가하는데 이는 버퍼의 크기가 증가하게 되면 이로 인한 버퍼 오버플로우로 인한 메시지의 삭제 또한 감소하기 때문이다.

Fig. 3.

Delivery ratio

또한, 두 기법 모두 DupC threshold 값이 증가함에 따라 초기에는 전달률이 증가하지만 일정 값 이후부터는 전달률이 감소하는 것을 알 수 있는데 이는 DupC threshold 값이 작은 범위에서는 이 값이 클수록 메시지의 확산이 증가하고 이를 통해 메시지의 전달이 용이하기 때문이다. 반면, DupC threshold 값이 큰 범위에서는 이 값이 증가할수록 한정된 노드의 버퍼의 크기로 인해 새롭게 수신된 메시지를 저장하기 위해 삭제되는 기존의 메시지가 증가되어 결과적으로 전달률이 감소하게 된다. 예측할 수 있는 것처럼 최적의 DupC threshold 값은 버퍼의 크기가 증가할수록 더 큰 값을 가지는 것을 알 수 있다. 제안 기법은 DupC threshold 값이 매우 큰 경우 이외의 환경에서 기존 기법에 비해 최대 약 15.64% 정도 우수한 성능을 가지게 되며, 이는 제안 기법이 기존의 기법에 비해 좀 더 효과적으로 메시지의 확산을 조절할 수 있기 때문이다.

그림 4는 부하율을 비교한 그림으로 DupC threshold 값이 증가함에 따라 복사되는 메시지의 수가 증가함으로써 부하율 또한 증가하는 것을 알 수 있다. 제안 기법은 기존 기법에 비해 DupC가 AvgDupC보다 작은 경우 평균 관점에서 다른 메시지에 비해 확산이 덜 진행된 메시지로 판단하여 확산을 촉진시키게 되어 부하율은 기존 기법에 비해 평균 5.1% 정도로 다소 증가하는 것을 알 수 있다.

Fig. 4.

Overhead ratio

그림 5는 전달지연을 나타낸 그림으로 두 기법 모두 DupC threshold가 매우 작아 메시지의 확산이 잘 발생하지 않거나 DupC threshold가 너무 커서 버퍼에서 메시지의 삭제가 많이 발생하는 환경에서 큰 전달지연을 가지는 반면 적절한 DupC threshlod 범위에서 우수한 전달 지연을 가지는 것을 보여준다. 제안 기법은 적절한 메시지의 확산을 통해 모든 DupC threshold 구간에서 기존 기법 대비 최대 약 25.7% 정도 더 적은 전달 지연을 가지게 된다.

Fig. 5.

Delivery latency

Ⅴ. 결 론

본 논문에서는 메시지의 복사 횟수 및 메시지의 평균 복사 횟수를 활용하여 메시지를 효과적으로 전달하는 개선된 메시지 복사 제한을 이용한 지연 허용 네트워크 라우팅 프로토콜을 제안하였다. 제안 프로토콜은 기존의 비교 프로토콜에 비해 부하율은 평균 5.1% 정도로 다소 증가하지만 고려하는 대부분의 DupC threshold 범위에서 최대 15.6% 증가된 전달률 및 최대 25.7% 감소된 전달지연을 가지는 것을 알 수 있었다. 추후 DupC threshold를 지연 허용 네트워크에서 노드가 이동할 수 있는 범위(Area), 노드의 개수 등 변화하는 네트워크의 환경에 따라 동적으로 적절히 설정함으로써 최적의 성능을 도출할 수 있는 기법에 대해 연구하고자 한다.

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]
• T. Spyropoulos, K. Psounis, and Cauligi S. Raghavendra, "Spray and Wait: an Efficient Routing Scheme for Intermittently Connected Mobile Networks", Proceedings of ACM SIGCOMM workshop on Delay-tolerant networking, 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", IETF RFC 6683, Aug. 2012. [https://doi.org/10.17487/rfc6693]
• T. K. Huang, C K. Lee, and L. J. Chen, "PRoPHET: an adaptive PRoPHET-based routing protocol for opportunistic network", Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications, Perth, WA, Australia, pp. 112-119, Apr. 2010. [https://doi.org/10.1109/AINA.2010.162]
• P. Wang and F. Shen, "Method to Improve the Performance of PROPHET Routing Protocol", Proceedings of the 2nd IEEE International Workshop on Education Technology and Computer Science, Wuhan, China, pp. 248-251, Mar. 2010. [https://doi.org/10.1109/ETCS.2010.350]
• H. H. Lim, D. Y. Seo, and Y. W. Chung, "An Improved PRoPHET Routing Protocol through the Restriction of Message Duplication", Journal of KIIT, Vol. 14, No. 6, pp. 81-86, Jun. 2016. [https://doi.org/10.14801/jkiit.2016.14.6.81]
• M. Ababou and M. Bellafkih, "Energy Efficient Routing Protocol for Delay Tolerant Network Based on Fuzzy Logic and Ant Colony", International Journal of Intelligent Systems and Applications, Vol. 11, No. 1, pp. 69-77, Jan. 2018. [https://doi.org/10.5815/ijisa.2018.01.08]
• A. K. Singh, T. Bera, and R. Pamula, "PRCP: Packet Replication Control based Prophet Routing Strategy for Delay Tolerant Network", Proceedings of the IEEE 4th International Conference on Recent Advances in Information Technology (RAIT), Dhanbad, India, pp. 1-5, Mar. 2018. [https://doi.org/10.1109/RAIT.2018.8389087]
• J. Wu, Z. Chen, and M. Zhao, "Weight Distribution and Community Reconstitution based on Communities Communications in Social Opportunistic Networks", Peer-to-Peer Networking and Applications, Vol. 12, No. 1, pp. 158-166, Apr. 2019. [https://doi.org/10.1007/s12083-018-0649-x]
• 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, Vol. 14, No. 7, pp. 71-77, Jul. 2016. [https://doi.org/10.14801/jkiit.2016.14.7.71]
• 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 the 2nd International Conference on Simulation Tools and Techniques, Rome, Italy, pp. 55:1-10, Mar. 2009. [https://doi.org/10.4108/ICST.SIMUTOOLS2009.5674]