애드-혹 네트워크에서 트래픽 감소를 위한 플러딩 알고리즘

Flooding Algorithms for Decreasing Traffic in Ad Hoc Networks

무선 애드-혹 네트워크는 자율적인 노드들이 서로 무선으로 통신하며 분산 관리되는 네트워크이다. 무선 애드-혹 네트워크에서 이동성으로 인한 빈번한 연결 단절과 같은 요인으로 유선 네트워크와 비교하여 처리량 저하를 경험할 수 있다. 특히, 라우팅 프로토콜들이 위치를 알 수 없는 모든 노드들에게 데이터를 전송하는 플러딩을 사용하고 있다. 플러딩은 간단한 방식으로 구현하기 쉬운 장점이 있는 반면에 브로드캐스트 스톰 문제로 네트워크 성능에 심각한 영향을 준다. 플러딩 문제를 최소화시키기 위하여 쓸데없이 네트워크상에 돌아다니는 패킷을 최소화시킬 필요가 있다. 본 논문에서는 도미넌트 프루닝을 개선한 빈도수 기반 플러딩 알고리즘을 제안한다. 제안한 알고리즘은 이웃 노드들의 패킷 중복 전송을 최소화하기 위하여 빈도수 기반 개선된 탐욕 집합피복 알고리즘을 이용하여 토폴러지 기반 이웃 노드의 정보로 최소 크기의 포워드 리스트를 생성한다. 목적지까지 최단 거리의 경로에서 너무 멀어진 경로를 방지하기 위하여 홉 수 제한 플러딩을 제안한다. 제안한 알고리즘이 성능 분석을 통해 도미넌트 프루닝과 비교하여 성능을 최대 79% 개선시키고 있음 보여주고 있다.

A wireless ad hoc network is a network in which autonomous nodes communicate with each other wirelessly and are distributed. In wireless ad hoc networks, such factors as frequent disconnections due to mobility may lead to lower throughput compared to wired networks. In particular, routing protocols are using flooding to transmit data to all nodes whose location is unknown. While flooding has the advantage of being easy to implement in a simple way, it has a serious impact on network performance due to a broadcast storm problem. In order to minimize the flooding problem, it is necessary to minimize the number of packets traveling on the network unnecessarily. In this paper, we propose a frequency - based flooding algorithm with improved dominant pruning. The proposed algorithm generates a minimum size forward list with topology based neighbor node information using frequency - based greedy set cover algorithm to minimize packet redundancy transmission of neighbor nodes. We propose a hop-count-constrained flooding scheme to prevent routes that are too far from the shortest path to the destination. We show that the proposed algorithm improves the performance compared to the dominant-pruning through performance analysis.