FANET에서 신뢰성 있는 데이터 전달을 위한 개선된 OLSR 라우팅 기법

2.1 FANET 라우팅 프로토콜

FANET은 전용 프로토콜 없이 기존의 MANET의 프로토콜을 활용한다. 이에 따라 기존의 MANET 프로토콜 중 어느 프로토콜이 FANET에서 효율적으로 작동하는지 알아보는 연구가 진행되었다[5]-[7].

[8]에서는 실시간 통신에 적합한 FANET 라우팅 프로토콜에 대해 연구하였으며, AODV, DSR (Dynamic Source Routing), OLSR, GRP(Geographic Routing Protocol)의 4개의 프로토콜을 대상으로 분석하였다. 4개의 프로토콜 중 OLSR은 실시간 통신량을 2, 4, 8, 16으로 2배씩 증가하지만, 지터(Jitter)의 값은 5.5배로 GRP의 4.5배 다음으로 좋은 값을 나타내고, MOS(Mean Opinion Score)도 3.2로 DSR 다음으로 높은 값을 유지하였다. 또한, PDV(Packet Delay Variation)과 E2E delay에서도 각각 0.103과 0.020으로 가장 낮은 평균값을 가지며 실시간 통신에 적합함을 입증하였다.

또한, [9]에서는 FANET 환경에서 UAV 간 거리에 따른 세 라우팅 프로토콜 AODV, OLSR, DSR의 성능을 분석하였다. 해당 연구에서 OLSR은 500m 이상에서 지연이 가장 낮고, 부하도 OLSR이 대체로 낮다는 결론이 나왔다. 처리율도 DSR에 이어 2번째로 좋은 등 전반적으로 우수한 성능을 보이지만 재전송률이 3개의 프로토콜 중 가장 높은 것으로 나왔다. 이를 통해 OLSR은 노드 간 거리가 먼 경우와 네트워크 부하를 줄여야 하는 FANET 환경과 잘 맞음을 알 수 있지만, 재전송률을 낮추어야 한다는 개선점이 있다.

2.2 향상된 성능의 OLSR

[10]에서는 K-means 클러스터링을 활용하여 라우팅 성능을 올리려는 연구가 있었다. K-means 클러스터링을 사용하여 네트워크 노드를 여러 클러스터로 분류하고, 각 클러스터의 중심 노드를 선택한다. 이 과정에서 이동성, 밀도, 에너지와 같은 여러 안정성 지표를 고려하여 클러스터의 안정성을 향상한다. 선정된 클러스터의 중심 노드는 클러스터 내에서 노드들과 직접 통신하며 OLSR 프로토콜을 개선하며, 네트워크의 효율성을 높인다. 또한, 중심 노드 간의 통신 시에도 최적의 경로를 설정하여 통신을 관리한다. 이 연구에서는 K-means 클러스터링을 통해 네트워크의 PDR(Packet Delivery Ratio), E2E Delay(End-to-End Delay), 컨트롤 오버헤드를 개선했다.

[4]에서는 FANET에서 UAV 간 링크 상태 예측(OLSR-Pds)을 통해 라우팅 성능을 올리려는 연구가 있었다. 가우스-마르코프(Gauss-Markov) 알고리즘으로 이동성 모형을 만들고 이를 기반으로 UAV의 링크 상태를 예측하여 라우팅 테이블을 업데이트하여 네트워크의 전체적인 성능 향상을 연구하였다. 이를 통해 AODV, OLSR과 비교하여 PDR과 E2E delay의 값이 향상되었고 특히, 속도가 빠를수록 더욱 좋은 성능을 나타내었다. 네트워크 오버헤드의 경우 기존의 OLSR보다는 높지만, 속도가 빠를수록 급격하게 높아지는 AODV와 다르게 OLSR과 OLSR-Pds의 경우 속도가 높아져도 안정적인 값을 보여주었다.

[11]은 OLSR 프로토콜에서 동적 컨트롤 메시지 타이머로 인한 링크 유효 시간 불일치로 인한 문제를 다루었다. OLSR 프로토콜을 개선하기 위해 컨트롤 메시지 타이머를 동적으로 조절하여도, 링크 유효 시간은 바뀌지 않아 링크 유효 시간 불일치 문제가 발생한다. 이 연구에서는 네트워크의 링크 유효 시간을 일치시키고 네트워크 토폴로지를 구성할 때 최소 홉 수가 아닌 링크 유효 시간으로 설정하여 PDR과 평균 홉 수를 줄였다.

3.1 네트워크 모델

그림 1과같이 FANET은 최대 n개의 이동 노드가 사전 구축된 인프라에 의존하지 않고 자율적으로 네트워크를 구성한다. 이를 위해 본 연구에서는 OLSR을 이용하여 FANET 네트워크를 구성한다고 가정한다. 본 연구에서는 UAV가 3차원으로 자율 비행하는 일반적인 시스템 모델이 아닌, FANET 응용 시나리오를 기반으로 타겟 시스템 모델을 설정하였다. 구체적으로, 이동 노드는 UAV라 가정하며, 최대 n개의 드론이 장애물이 없는 동일한 고도 환경에서 빠른 속도로 이동한다. UAV들은 주어진 임무를 수행하기 위해 지속적으로 이동하므로 네트워크 토폴로지는 그에 따라 빈번하게 변동되며 각 노드의 빠른 이동속도로 인하여 그 변화가 자주 일어나는 상황을 가정한다.

Fig. 1.

Network topology of FANET

3.2 OLSR의 기본 동작

OLSR은 proactive 방식으로 작동하는 링크 상태 라우팅 프로토콜이다. 이 프로토콜에서 각 노드는 주기적으로 Hello 메시지를 전송하여 이웃 노드의 위치를 파악하고, TC(Topology Control) 메시지를 통해 네트워크 전체에 토폴로지 정보를 공유한다.

OLSR의 중요한 특징 중 하나는 MPR(Multi Point Relay)라는 기법을 사용하여 제어 메시지의 수를 줄이는 것이다. 기존 방식인 Link State Routing에서는 모든 노드가 주기적으로 TC 메시지를 보내기 때문에 컨트롤 오버헤드가 크지만, MPR은 네트워크에서 특정 노드들만이 TC 메시지를 전파하도록 선택하는 방식으로 제어 메시지의 오버헤드를 줄인다. MPR은 1-hop 노드 중에서 선택되며, 선택 기준은 가능한 많은 2-hop 노드를 커버할 수 있는지에 따라 결정된다. 선택된 MPR은 MPR 셀렉터로부터 받은 TC 메시지에 자신의 링크 상태 정보를 추가하여 전체 네트워크에 전파한다. 이를 통해 네트워크 내의 다른 노드들은 전체 토폴로지를 이해할 수 있게 된다.

OLSR의 토폴로지 생성 절차는 크게 5가지로 나뉜다. 우선, Hello 메시지를 주기적으로 전송하여 인접 노드의 상태를 파악한다. 두 번째로 각 노드는 이웃 노드 중에서 MPR을 선택한다. 세 번째로 TC 메시지를 보내어 전체 네트워크 토폴로지를 형성한다. 네 번째로 노드들은 수신한 TC 메시지를 기반으로 네트워크 토폴로지를 계산한다. 이때, 최단 경로 알고리즘을 사용하여 경로를 계산하고, 라우팅 테이블에 저장한다. 마지막으로 라우팅 테이블을 업데이트한다.

3.3 문제 정의

OLSR에서 Hello 타이머와 TC 타이머는 각각 2초와 5초로 설정되어 있다. 그러나 이동 속도가 빠른 FANET(Flying Ad-hoc Network) 환경에서는 노드의 이동으로 인해 링크 단절이 빈번하게 발생할 수 있다. 이 문제를 해결하기 위해 각 메시지 타이머를 동적으로 설정할 수 있다. 노드의 이동 속도가 빠른 경우 Hello 타이머와 TC 타이머를 줄여 네트워크 토폴로지의 변화를 빠르게 인식할 수 있게 하고, 노드의 이동 속도가 느린 경우 Hello 타이머와 TC 타이머를 늘려 컨트롤 메시지 오버헤드를 줄인다. 또한, 링크 유효 시간을 자신이 설정한 Hello Timer*3으로 한다. 하지만, 이 경우 각 노드가 동일한 링크에 대한 유효 시간이 서로 불일치하여 이미 소실된 링크를 활용하려는 문제가 발생할 수 있다.

예를 들어, 그림 2에서 노드 B의 Hello 타이머가 2초이고, 노드 C의 Hello 타이머가 1초일 때, 각 노드가 링크 L을 인식하는 유효 시간은 6초, 3초이다. 이러한 시간 차이로 인해 노드 B는 링크 L이 유효하다고 판단하여 링크 L을 활용하지만, 실제로는 링크 L이 이미 끊어진 상태여서 통신에 실패할 수 있다.

Fig. 2.

Link inconsistency issues caused by dynamic timers

이를 방지하기 위해 TC 메시지에 자신의 Hello Timer를 같이 보내는 방법이 있다. 표 1과 같이 TC 메시지에 Hello Timer를 같이 보냄으로써 라우팅 테이블을 구성할 때 각 노드 간의 링크 유효 시간 불일치 문제를 해결할 수 있다.

Table 1.

Modified TC message format

하지만, 링크 유효 시간만을 고려하여 그래프를 생성하면 가까운 거리를 돌아갈 수 있다는 문제가 발생한다. 이러한 문제를 해결하기 위해 이 논문에서는 GPS 정보를 활용하여 위치 기반 최단 거리 경로 생성 알고리즘과 링크 유효 시간을 함께 고려하여 목적지 노드까지 최적의 경로를 찾아내는 Adjust Timer 기반의 WL(Weighted LinkLifeTime)-OLSR을 제안한다.

4.1 토폴로지 생성 절차

본 논문에서 제안하는 WL-OLSR에서 각 노드는 GPS 정보를 활용하여 자신의 속력을 계산한다.

$$ NS=\left( NewPosition - LastPosition \right)/\Delta Time$$

그리고 계산된 속력을 바탕으로 hello 타이머와 TC 타이머를 동적으로 변경한다. 자신의 속력이 25m/s 이하일 경우 hello 타이머와 TC 타이머를 각 2초, 3초로 설정하고, 40m/s 이하일 경우 각 타이머를 1초, 2초로 설정한다. 그리고, 40m/s 이상일 경우 각 타이머를 0.5초, 1초로 설정한다. TC 메시지는 변경된 hello 타이머와 노드의 위치를 포함한다.

토폴로지 그래프의 생성 절차는 기존의 OLSR과 비슷하나 hello 타이머가 고정값이 아니라 동적으로 전송하도록 바뀌고, TC 메시지를 전송할 때 자신의 위치와 hello 타이머를 추가하여 보낸다. 네트워크 토폴로지를 형성할 때 hello 타이머를 사용하여 링크 유효 시간을 알아내어 토폴로지를 형성한다. 라우팅 테이블을 생성할 때는 링크 유효 시간에 노드의 거리를 가중치로 두어 경로를 생성한다.

4.2 경로 생성 절차

알고리즘 1은 이웃 노드의 라우팅 테이블 계산 과정이다. TC 메시지로 수신한 이웃 노드의 위치는 자신의 위치와 함께 거리를 계산하는 데 사용되고, hello 타이머는 각 링크 유효 시간을 계산하기 위해 사용된다. 링크의 유효 시간은 Hello Timer*3으로 설정되며 여기에 추가로 거리 기반 가중치를 둔다.

Algorithm 1

Neighbor node table update

노드의 좌표를 통해 유클리드 거리를 구하고 여기에 가중치를 곱한다. 가중치의 값은 0.01로 설정하여 100m당 1의 값을 가지도록 설계하였다. 기존의 경로 생성 방법은 Dijkstra 알고리즘을 사용하지만, 실제 거리가 아닌 홉의 개수로 계산하므로 실제 거리가 더 길 수도 있는 반면, GPS를 사용하여 노드 사이의 거리를 계산하면 더욱 가까이 있는 노드를 선택할 수 있으므로 빠른 이동 속도를 고려하더라도 안정적인 링크를 생성할 수 있다. 본 논문에서 제안하는 알고리즘을 통해 노드들은 경로를 생성할 때 안정적인 이웃 노드를 다음 홉으로 선택함으로써 신뢰성이 높은 경로를 통해 데이터를 전송할 수 있다.

5.1 실험 환경 설정

본 논문에서 제안하는 알고리즘의 성능 분석을 위해 구성한 네트워크 모델은 표 2와 같다. 노드의 개수는 20 ~ 40개이고 랜덤한 위치에 배치된다. 네트워크 사이즈는 2,000m × 2,000m ~ 4,000m × 4,000m의 정사각형 구조로 설정하였다. 각 노드에 적용된 이동성 모델은 Random WayPoint Model을 사용하였고, UAV의 높은 이동성을 반영하여 속도는 20m/s ~ 100m/s로 설정하였다. 송/수신 노드의 개수는 각 6개이고, 송신 노드는 서로 다른 임의의 목적지로 전송된다. MAC 프로토콜은 IEEE 802.11을 사용하였다.

Table 2.

Simulation parameters

성능 비교를 위한 파라미터는 PDR(Packet Delivery Ratio)과 Throughput의 평균값을 사용하였다. 노드의 개수에 따른 변화를 측정할 때에는 3,000m × 3,000m의 네트워크 사이즈에 노드 개수를 20, 25, 30, 35, 40으로 변경하며 테스트하였고, 네트워크 사이즈에 따른 측정할 때에는 노드 개수 30개에 네트워크 사이즈를 2,000m, 2,500m, 3,000m, 3,500m, 4,000m로 변경하며 테스트하였다. 또한, 네트워크 사이즈와 노드 개수를 각각 3,000m x 3,000m, 40개로 고정한 후 노드의 이동 속도를 20m/s, 50m/s, 70m/s로 변경하며 이동 속도에 따라 네트워크 성능의 변화를 테스트하였다.

5.2 노드의 개수에 따른 성능

OLSR의 성능은 노드의 개수와 밀접한 연관이 있다. 노드의 개수가 많으면 링크가 단절되어도 다른 노드를 통해 우회할 수 있고, 경로도 여러 가지가 생기게 되므로 링크 단절의 확률이 낮아지기 때문에 PDR도 올라가게 된다.

그림 3은 노드의 개수에 따른 평균 PDR을 분석하였다. 노드의 개수가 올라갈수록 전체적인 안정성이 올라가는 모습을 확인할 수 있으며, 본 논문에서 제안하는 알고리즘이 Original OLSR보다 평균적으로 약 10% 이상 향상된 성능을 보여주고 있다.

Fig. 3.

Impact of varying number of nodes on packet delivery ratio

그림 4는 노드의 개수에 따른 평균 Throughput을 보여준다. 전반적으로 본 논문에서 제안하는 알고리즘의 성능이 약 10% 정도 높다.

Fig. 4.

Impact of varying number of nodes on Throughput

전반적으로 노드의 개수가 낮을 때에는 비슷한 성능을 보이지만 노드의 개수가 늘어날수록 성능에서 차이가 나는 모습을 보여주고 있다.

5.3 네트워크 사이즈에 따른 성능

그림 5에서 네트워크 사이즈에 대한 평균적인 PDR을 보여준다. 네트워크 사이즈가 커질수록 노드의 밀집도가 떨어지다 보니 PDR이 점점 낮아지지만, 본 논문에서 제안하는 알고리즘이 Original OLSR보다 평균적으로 10% 정도 높은 성능을 보여준다.

Fig. 5.

Impact of varying network sizes on packet delivery ratio

그림 6 역시 네트워크 사이즈에 대한 평균적인 Throughput을 보여주는데 위 결과와 마찬가지로 네트워크 사이즈가 커질수록 평균 Throughput이 감소하지만, 본 논문에서 제안하는 알고리즘이 Original OLSR보다 평균적으로 10% 정도 높은 성능을 보여준다.

Fig. 6.

Impact of varying network sizes on Throughput

5.4 노드 속도에 따른 성능

그림 7, 그림 8에서는 노드의 속도에 따른 평균 PDR과 Throughput을 보여준다. 노드의 속도가 느릴 때는 기존의 Original OLSR과 hello 타이머가 같으므로, Original OLSR, OLSR-Lifetime과 WL-OLSR이 비슷한 성능을 보여주지만, 노드의 속도가 높아질수록 자신의 속도에 맞춰 컨트롤 메시지 타이머를 동적으로 조절하는 OLSR-Lifetime과 WL-OLSR이 평균 PDR과 Throughput이 좋아지는 모습을 보인다.

Fig. 7.

Impact of varying speed of nodes on packet delivery ratio

Fig. 8.

Impact of varying speed of nodes on Throughput